1 files changed, 456 insertions, 0 deletions
diff --git a/text/syllabic.py b/text/syllabic.py
new file mode 100644
index 0000000..6eb7c93
--- /dev/null
+++ b/text/syllabic.py
@@ -0,0 +1,456 @@
+#!/usr/bin/env python3
+"""The tables HarfBuzz's syllabic shapers read, as C (text/syllabic-data.c).
+
+    python3 text/syllabic.py HARFBUZZ_SRC > text/syllabic-data.c
+    python3 text/syllabic.py HARFBUZZ_SRC --check
+
+HARFBUZZ_SRC is HarfBuzz 10.2.0's src/ directory; what is read from it:
+
+- Each character's Indic category and position: hb-ot-shaper-indic-
+  table.cc, the table HarfBuzz's gen-indic-table.py made from Unicode 16's
+  IndicSyllabicCategory and IndicPositionalCategory with its own overrides,
+  read cell for cell (Unicode here is 15.1: the table is taken as HarfBuzz
+  has it). Khmer and Myanmar read the same table.
+
+- The syllable machines: hb-ot-shaper-*-machine.rl, the Ragel grammars.
+  This compiles each to a DFA with Ragel's scanner semantics (the longest
+  match from each position, ties to the pattern listed first), its symbols
+  folded into classes that behave alike. --check runs the DFAs beside the
+  machines Ragel generated from the same grammars (hb-ot-shaper-*-
+  machine.hh) on random runs of symbols, and counts where they differ.
+
+The output is deterministic: the same inputs give the same file.
+"""
+import random
+import re
+import sys
+from pathlib import Path
+
+HB = Path(sys.argv[1] if len(sys.argv) > 1 else '.')
+MACHINES = ['indic', 'khmer', 'myanmar']
+ALPHABET = 64  # categories past 63 are folded into 63, which only `any` takes
+
+
+# ---- Grammars: Ragel's regular expressions over symbols
+
+class Parser:
+    """Ragel's expressions as the machines use them: names, `a | b`,
+    `a . b` or `a b`, postfix `? * +`, parentheses."""
+
+    def __init__(self, text, names):
+        self.tokens = re.findall(r'[A-Za-z_][A-Za-z_0-9]*|[()|.?*+]', text)
+        self.at = 0
+        self.names = names
+
+    def peek(self):
+        return self.tokens[self.at] if self.at < len(self.tokens) else None
+
+    def take(self):
+        self.at += 1
+        return self.tokens[self.at - 1]
+
+    def alternation(self):
+        node = self.concatenation()
+        while self.peek() == '|':
+            self.take()
+            node = ('alt', node, self.concatenation())
+        return node
+
+    def concatenation(self):
+        node = self.postfix()
+        while self.peek() not in (None, '|', ')'):
+            if self.peek() == '.':
+                self.take()
+            node = ('cat', node, self.postfix())
+        return node
+
+    def postfix(self):
+        node = self.atom()
+        while self.peek() in ('?', '*', '+'):
+            node = ({'?': 'opt', '*': 'star', '+': 'plus'}[self.take()], node)
+        return node
+
+    def atom(self):
+        token = self.take()
+        if token == '(':
+            node = self.alternation()
+            assert self.take() == ')'
+            return node
+        return self.names[token]
+
+
+def parse(text, names):
+    parser = Parser(text, names)
+    node = parser.alternation()
+    assert parser.peek() is None, (text, parser.peek())
+    return node
+
+
+class Grammar:
+    """A machine's .rl: its symbols (exports), syllable types (the enum), and
+    the scanner's patterns in order, each with the type it finds."""
+
+    def __init__(self, name):
+        text = (HB / f'hb-ot-shaper-{name}-machine.rl').read_text()
+        enum = re.search(r'enum \w+_syllable_type_t \{(.*?)\};', text, re.S).group(1)
+        self.types = [t.strip() for t in enum.split(',') if t.strip()]
+        body = '\n'.join(block for block in re.findall(r'%%\{(.*?)\}%%', text, re.S) if 'main :=' in block)
+        body = re.sub(r'#[^\n]*', '', body)
+        main = re.search(r'main := \|\*(.*?)\*\|;', body, re.S).group(1)
+        rest = body.replace(re.search(r'main := \|\*.*?\*\|;', body, re.S).group(0), '')
+        self.symbols = {name: int(value) for name, value in re.findall(r'export (\w+)\s*=\s*(\d+);', rest)}
+        names = {name: ('sym', frozenset([value])) for name, value in self.symbols.items()}
+        names['any'] = ('any',)
+        for statement in rest.split(';'):
+            statement = statement.strip()
+            if not statement or statement.startswith('export'):
+                continue
+            name, expression = statement.split('=', 1)
+            names[name.strip()] = parse(expression, names)
+        self.patterns = []
+        for pattern, action in re.findall(r'([^;{}]+?)=>\s*\{(.*?)\};', main, re.S):
+            kind = re.search(r'found_syllable \((\w+)\)', action).group(1)
+            self.patterns.append((parse(pattern, names), self.types.index(kind)))
+        self.broken = next(i for i, t in enumerate(self.types) if t.endswith('broken_cluster'))
+
+
+class NFA:
+    def __init__(self):
+        self.edges = []   # state: [(symbols or None for epsilon, target)]
+        self.accept = {}  # state: pattern index
+
+    def state(self):
+        self.edges.append([])
+        return len(self.edges) - 1
+
+    def build(self, node):
+        """Thompson's construction: (start, end) of node."""
+        kind = node[0]
+        if kind in ('sym', 'any'):
+            a, b = self.state(), self.state()
+            symbols = frozenset(range(ALPHABET)) if kind == 'any' else frozenset(min(s, ALPHABET - 1) for s in node[1])
+            self.edges[a].append((symbols, b))
+            return a, b
+        if kind == 'alt':
+            a, b = self.state(), self.state()
+            for part in node[1:]:
+                s, e = self.build(part)
+                self.edges[a].append((None, s))
+                self.edges[e].append((None, b))
+            return a, b
+        if kind == 'cat':
+            s1, e1 = self.build(node[1])
+            s2, e2 = self.build(node[2])
+            self.edges[e1].append((None, s2))
+            return s1, e2
+        s, e = self.build(node[1])
+        a, b = self.state(), self.state()
+        self.edges[a].append((None, s))
+        self.edges[e].append((None, b))
+        if kind in ('opt', 'star'):
+            self.edges[a].append((None, b))
+        if kind in ('star', 'plus'):
+            self.edges[e].append((None, s))
+        return a, b
+
+    def closure(self, states):
+        seen, stack = set(states), list(states)
+        while stack:
+            for symbols, target in self.edges[stack.pop()]:
+                if symbols is None and target not in seen:
+                    seen.add(target)
+                    stack.append(target)
+        return frozenset(seen)
+
+
+def machine(grammar):
+    """The scanner's DFA, minimal: each state's transitions by symbol (None
+    for none) and the syllable type it accepts (the first pattern's), or
+    None; the start is state 0."""
+    nfa = NFA()
+    start = nfa.state()
+    for index, (tree, kind) in enumerate(grammar.patterns):
+        s, e = nfa.build(tree)
+        nfa.edges[start].append((None, s))
+        nfa.accept[e] = index
+    first = nfa.closure([start])
+    states, order, transitions = {first: 0}, [first], []
+    for current in order:
+        row = []
+        for symbol in range(ALPHABET):
+            targets = [t for s in current for symbols, t in nfa.edges[s] if symbols is not None and symbol in symbols]
+            if not targets:
+                row.append(None)
+                continue
+            target = nfa.closure(targets)
+            if target not in states:
+                states[target] = len(order)
+                order.append(target)
+            row.append(states[target])
+        transitions.append(row)
+    accepts = []
+    for current in order:
+        matched = [nfa.accept[s] for s in current if s in nfa.accept]
+        accepts.append(grammar.patterns[min(matched)][1] if matched else None)
+    # Moore's partition refinement
+    n = len(transitions)
+    block = list(accepts)
+    while True:
+        signature = [(block[s],) + tuple(None if t is None else block[t] for t in transitions[s]) for s in range(n)]
+        numbering = {}
+        refined = [numbering.setdefault(signature[s], len(numbering)) for s in range(n)]
+        if len(numbering) == len(set(block)):
+            break
+        block = refined
+    new = {}
+    for s in range(n):
+        new.setdefault(block[s], len(new))
+    table, accept = [None] * len(new), [None] * len(new)
+    for s in range(n):
+        table[new[block[s]]] = [None if t is None else new[block[t]] for t in transitions[s]]
+        accept[new[block[s]]] = accepts[s]
+    # every symbol starts a syllable: the scanner never stalls
+    assert all(table[0][symbol] is not None and accept[table[0][symbol]] is not None for symbol in range(ALPHABET))
+    return table, accept
+
+
+def classes(table):
+    """Symbols whose columns are the same, folded."""
+    columns, of = {}, []
+    for symbol in range(ALPHABET):
+        of.append(columns.setdefault(tuple(row[symbol] for row in table), len(columns)))
+    return of, len(columns)
+
+
+def scan(table, accept, symbols):
+    """Syllables of a run of symbols by a DFA: (start, end, type)."""
+    found, p = [], 0
+    while p < len(symbols):
+        state, end, kind = 0, None, None
+        for q in range(p, len(symbols)):
+            state = table[state][min(symbols[q], ALPHABET - 1)]
+            if state is None:
+                break
+            if accept[state] is not None:
+                end, kind = q + 1, accept[state]
+        found.append((p, end, kind))
+        p = end
+    return found
+
+
+# ---- The Indic table
+
+def indic_table(grammars):
+    """Code point to (category, position) for the characters HarfBuzz's
+    table has, and the default for the others."""
+    text = (HB / 'hb-ot-shaper-indic-table.cc').read_text()
+    positions = {name: int(value) for name, value in
+                 re.findall(r'(POS_\w+) = (\d+)', (HB / 'hb-ot-shaper-indic.hh').read_text())}
+    machines = {'I': grammars['indic'].symbols, 'K': grammars['khmer'].symbols, 'M': grammars['myanmar'].symbols}
+    long_names = {name: machines[m][cat] for name, m, cat in re.findall(r'#define (OT_\w+) ([IKM])_Cat\((\w+)\)', text)}
+    short = {name: long_names[target] for name, target in re.findall(r'#define (_OT_\w+)\s+(OT_\w+)', text)}
+    short.update({name: positions[target] for name, target in re.findall(r'#define (_POS_\w+)\s+(POS_\w+)', text)})
+
+    def cell(s, m):
+        return short['_OT_' + s], short['_POS_' + m]
+
+    cells = {}
+    table = text[text.index('static const uint16_t indic_table[]'):text.index('}; /* Table items:')]
+    for start, row in re.findall(r'/\* ([0-9A-F]{4,5}) \*/(.*)', table):
+        for k, (s, m) in enumerate(re.findall(r'_\((\w+),(\w+)\)', row)):
+            cells[int(start, 16) + k] = cell(s, m)
+    lookup = text[text.index('hb_indic_get_categories (hb_codepoint_t u)'):]
+    for code, s, m in re.findall(r'u == 0x([0-9A-F]+)u\)\) return _\((\w+),(\w+)\);', lookup):
+        cells[int(code, 16)] = cell(s, m)
+    default = cell(*re.search(r'return _\((\w+),(\w+)\);\s*\}', lookup).groups())
+    return cells, default
+
+
+def runs_of(cells):
+    """Runs of covered code points, gaps under 16 kept inside."""
+    runs = []
+    for code in sorted(cells):
+        if runs and code - runs[-1][1] <= 16:
+            runs[-1][1] = code
+        else:
+            runs.append([code, code])
+    return runs
+
+
+# ---- Checking against Ragel's machines (hb-ot-shaper-*-machine.hh)
+
+def ragel(name):
+    """A scanner from the flat tables and actions Ragel generated: symbols
+    to (start, end, type)."""
+    text = (HB / f'hb-ot-shaper-{name}-machine.hh').read_text()
+    grammar = Grammar(name)
+
+    def array(field):
+        body = re.search(rf'_{name}_syllable_machine_{field}\[\] = \{{(.*?)\}};', text, re.S).group(1)
+        return [int(v) for v in re.findall(r'-?\d+', body)]
+
+    keys, spans, offsets, indicies = array('trans_keys'), array('key_spans'), array('index_offsets'), array('indicies')
+    targets, actions = array('trans_targs'), array('trans_actions')
+    to_state, from_state, eof_trans = array('to_state_actions'), array('from_state_actions'), array('eof_trans')
+    start = int(re.search(rf'{name}_syllable_machine_start = (\d+);', text).group(1))
+
+    def cases(switch):
+        """The action cases of the switch on an array: number to code."""
+        at = text.index(f'switch ( _{name}_syllable_machine_{switch}[')
+        depth, begin = 0, text.index('{', at)
+        for k in range(begin, len(text)):
+            depth += {'{': 1, '}': -1}.get(text[k], 0)
+            if depth == 0:
+                body = text[begin + 1:k]
+                break
+        out, depth, current, k = {}, 0, None, 0
+        while k < len(body):
+            m = re.compile(r'case (\d+):').match(body, k) if depth == 0 else None
+            if m:
+                current = int(m.group(1))
+                out[current] = ''
+                k = m.end()
+                continue
+            depth += {'{': 1, '}': -1}.get(body[k], 0)
+            if current is not None:
+                out[current] += body[k]
+            k += 1
+        return out
+
+    trans_cases, to_cases, from_cases = cases('trans_actions'), cases('to_state_actions'), cases('from_state_actions')
+
+    def run(code, st):
+        # the `switch( act )` of a backtracking action: only the chosen case
+        m = re.search(r'switch\( act \) \{(.*)\}', code, re.S)
+        if m:
+            chosen = re.search(rf'case {st["act"]}:(.*?)break;', m.group(1), re.S)
+            code = code[:m.start()] + (chosen.group(1) if chosen else '')
+        for statement in re.findall(r'ts = p;|ts = 0;|te = p\+1;|te = p;|p--;|p = \(\(te\)\)-1;|act = \d+;|'
+                                    r'found_syllable \(\w+\)', code):
+            if statement == 'ts = p;': st['ts'] = st['p']
+            elif statement == 'ts = 0;': st['ts'] = 0
+            elif statement == 'te = p+1;': st['te'] = st['p'] + 1
+            elif statement == 'te = p;': st['te'] = st['p']
+            elif statement == 'p--;': st['p'] -= 1
+            elif statement == 'p = ((te))-1;': st['p'] = st['te'] - 1
+            elif statement.startswith('act'): st['act'] = int(statement[6:-1])
+            else:
+                kind = statement[len('found_syllable ('):-1]
+                st['found'].append((st['ts'], st['te'], grammar.types.index(kind)))
+
+    def scanner(symbols):
+        st = {'ts': 0, 'te': 0, 'act': 0, 'p': 0, 'found': []}
+        cs, pe = start, len(symbols)
+        state = 'resume' if pe else 'test_eof'
+        while True:
+            if state == 'resume':
+                if from_state[cs]:
+                    run(from_cases[from_state[cs]], st)
+                c, low, high, span = symbols[st['p']], keys[2 * cs], keys[2 * cs + 1], spans[cs]
+                trans = indicies[offsets[cs] + (c - low if span > 0 and low <= c <= high else span)]
+                state = 'eof_trans'
+            if state == 'eof_trans':
+                cs = targets[trans]
+                if actions[trans]:
+                    run(trans_cases[actions[trans]], st)
+                if to_state[cs]:
+                    run(to_cases[to_state[cs]], st)
+                st['p'] += 1
+                state = 'resume' if st['p'] != pe else 'test_eof'
+                continue
+            if state == 'test_eof':
+                if st['p'] == pe and eof_trans[cs] > 0:
+                    trans = eof_trans[cs] - 1
+                    state = 'eof_trans'
+                    continue
+                return st['found']
+    return scanner
+
+
+def check(runs=100000):
+    rng = random.Random(1)
+    for name in MACHINES:
+        grammar = Grammar(name)
+        table, accept = machine(grammar)
+        theirs = ragel(name)
+        symbols = sorted(set(grammar.symbols.values())) + [0, 19, 63]
+        differ = 0
+        for _ in range(runs):
+            run = [rng.choice(symbols) for _ in range(rng.randint(1, 14))]
+            a, b = scan(table, accept, run), theirs(run)
+            if a != b:
+                differ += 1
+                if differ <= 3:
+                    print(name, 'differ:', run, a, b, file=sys.stderr)
+        print(f'{name}: {len(table)} states, {runs} runs, {differ} differ')
+
+
+# ---- The C file
+
+def emit_machine(out, name, grammar):
+    table, accept = machine(grammar)
+    of, count = classes(table)
+    dead = len(table)
+    column_of = {}
+    for symbol in range(ALPHABET):
+        column_of.setdefault(of[symbol], symbol)
+    width = 'uint8_t' if dead < 256 else 'uint16_t'
+    out.append(f'/* {name} (hb-ot-shaper-{name}-machine.rl): {len(table)} states, {count} classes of symbol;'
+               f' types {", ".join(grammar.types)}. */')
+    out.append(f'static const uint8_t {name}_class[{ALPHABET}] = {{')
+    for k in range(0, ALPHABET, 32):
+        out.append('    ' + ', '.join(str(c) for c in of[k:k + 32]) + ',')
+    out.append('};')
+    out.append(f'static const {width} {name}_next[{len(table)}][{count}] = {{')
+    for row in table:
+        out.append('    {' + ', '.join(str(dead if row[column_of[k]] is None else row[column_of[k]])
+                                      for k in range(count)) + '},')
+    out.append('};')
+    out.append(f'static const uint8_t {name}_accept[{len(table)}] = {{')
+    cells = [str(0 if a is None else a + 1) for a in accept]
+    for k in range(0, len(cells), 32):
+        out.append('    ' + ', '.join(cells[k:k + 32]) + ',')
+    out.append('};')
+    out.append(f'const VegaMachine vega_{name}_machine = {{{name}_class, {count}, {len(table)}, {name}_next[0], '
+               f'sizeof({name}_next[0][0]), {name}_accept, {grammar.broken + 1}}};')
+    out.append('')
+
+
+def main():
+    if len(sys.argv) > 2 and sys.argv[2] == '--check':
+        check()
+        return
+    grammars = {name: Grammar(name) for name in MACHINES}
+    cells, default = indic_table(grammars)
+    flat, starts = [], []
+    for a, b in runs_of(cells):
+        starts.append((a, b, len(flat)))
+        flat.extend(cells.get(code, default) for code in range(a, b + 1))
+    out = ['/* Generated by text/syllabic.py from HarfBuzz 10.2.0\'s sources; do not edit. */',
+           '#include "syllabic.h"', '',
+           '/* Each character\'s Indic category and position (hb-ot-shaper-indic-table.cc, Unicode 16):',
+           ' * category | position << 8. */',
+           f'static const uint16_t indic_cells[{len(flat)}] = {{']
+    for k in range(0, len(flat), 12):
+        out.append('    ' + ', '.join(f'0x{c | p << 8:04X}' for c, p in flat[k:k + 12]) + ',')
+    out.append('};')
+    out.append(f'static const struct {{ uint32_t first, last, at; }} indic_runs[{len(starts)}] = {{')
+    for a, b, at in starts:
+        out.append(f'    {{0x{a:04X}, 0x{b:04X}, {at}}},')
+    out.append('};')
+    out.append('')
+    out.append('uint16_t vega_indic_categories(uint32_t u) {')
+    out.append(f'    for (unsigned i = 0; i < {len(starts)} && u >= indic_runs[i].first; ++i)')
+    out.append('        if (u <= indic_runs[i].last) return indic_cells[indic_runs[i].at + u - indic_runs[i].first];')
+    out.append(f'    return 0x{default[0] | default[1] << 8:04X};')
+    out.append('}')
+    out.append('')
+    out.append('/* The syllable machines: a DFA over classes of symbol; a state\'s accept is')
+    out.append(' * the syllable type it ends, plus one. */')
+    for name in MACHINES:
+        emit_machine(out, name, grammars[name])
+    sys.stdout.write('\n'.join(out) + '\n')
+
+
+if __name__ == '__main__':
+    main()