Skip to content

armgit / laya

Public Imported from GitHub
0

Non-autoregressive System 1 decision engine. Typed choice, score and yes/no decisions over any text in a single forward pass, in 100+ languages, with a router that picks the right checkpoint per request.

29.4 KB
Raw Blame
#!/usr/bin/env python3
"""Generate laya-go's compiled-in Unicode and language tables as Go source.

Three files, three sources, and the split is the point:

  * internal/unicodedata/tables_gen.go -- recorded from CPython (the header names the minor
    version and the Unicode release, never the patch: the tables are a function of the Unicode
    database, which a patch release does not change, and a patch in the header made --check fail
    on every runner whose interpreter was not the one the file was generated on), because `laya/lang.py` is
    written against `str.isalpha()`, `str.lower()` and `re`'s `\\w`, and Go's own `unicode`
    package follows whichever Unicode the Go toolchain ships (it moves between releases).
  * lang/tables_gen.go -- read straight from `laya.lang`: the script ranges, the per-language
    function words and the thresholds.
  * tokenizer/tables_gen.go -- probed from the `tokenizers` crate (the reference the
    Python package tokenizes with), whose Unicode is NOT CPython's: it classifies Unicode 15.1/16
    additions as letters and decomposes 135 code points CPython does not.

Everything is regenerated, never edited. `--check` fails when a committed file differs.

    python laya-go/scripts/gen_tables.py            # write
    python laya-go/scripts/gen_tables.py --check    # fail if a committed copy is stale
"""
import argparse
import os
import re
import sys
import unicodedata

HERE = os.path.dirname(os.path.abspath(__file__))
GO = os.path.normpath(os.path.join(HERE, ".."))
REPO = os.path.dirname(GO)
MAX = 0x110000
SURROGATES = range(0xD800, 0xE000)
HANGUL = range(0xAC00, 0xD7A4)
OUT_UNICODE = os.path.join(GO, "internal", "unicodedata", "tables_gen.go")
OUT_LANG = os.path.join(GO, "lang", "tables_gen.go")
OUT_TOKENIZER = os.path.join(GO, "tokenizer", "tables_gen.go")
OUT_CPP_UNICODE = os.path.join(REPO, "laya-cpp", "src", "unicodedata_tables.inc")
OUT_CPP_LANG = os.path.join(REPO, "laya-cpp", "src", "lang_tables.inc")
OUT_CPP_TOKENIZER = os.path.join(REPO, "laya-cpp", "src", "tokenizer_tables.inc")


def wrap(values, indent="\t", width=100):
    """Comma-separated items wrapped to `width`, one trailing comma, ready for a Go literal."""
    lines, current = [], indent
    for item in values:
        piece = str(item) + ", "
        if len(current) + len(piece) > width and current.strip():
            lines.append(current.rstrip())
            current = indent
        current += piece
    if current.strip():
        lines.append(current.rstrip())
    return "\n".join(lines)


def ranges(predicate):
    """Inclusive (lo, hi) runs where `predicate(cp)` holds. Surrogates never hold."""
    out, start = [], None
    for cp in range(MAX):
        hit = False if cp in SURROGATES else bool(predicate(cp))
        if hit and start is None:
            start = cp
        elif not hit and start is not None:
            out.append((start, cp - 1))
            start = None
    if start is not None:
        out.append((start, MAX - 1))
    return out


def table(name, rows, doc):
    flat = [v for row in rows for v in row]
    return "// %s\n// %d ranges covering %d code points.\nvar %s = [...]rune{\n%s\n}\n\n" % (
        doc, len(rows), sum(b - a + 1 for a, b in rows), name, wrap(flat))


def tok_array(cpp, go_name, cpp_name, values, doc, ctype="uint32_t"):
    """One generated array of the tokenizer tables, as Go (`var goName = [...]rune{`) or C++."""
    if cpp:
        return "// %s\ninline constexpr %s %s[] = {\n%s\n};\n\n" % (doc, ctype, cpp_name, wrap(values, indent="    "))
    gotype = "uint64" if ctype == "uint64_t" else "uint32" if ctype == "uint32_t" and go_name.endswith("Offsets") else "rune"
    return "// %s\nvar %s = [...]%s{\n%s\n}\n\n" % (doc, go_name, gotype, wrap(values))


def ascii_masks(name, predicate):
    low = sum(1 << cp for cp in range(0, 64) if predicate(cp))
    high = sum(1 << (cp - 64) for cp in range(64, 128) if predicate(cp))
    return "var %sASCII = [2]uint64{%#x, %#x}\n\n" % (name, low, high)


def header(source, extra=""):
    return ("// Code generated by laya-go/scripts/gen_tables.py from %s; DO NOT EDIT.\n"
            "//\n// Regenerate with: python laya-go/scripts/gen_tables.py\n%s\n" % (source, extra))


# ---------------------------------------------------------------------------------------------
# CPython: the character predicates laya/lang.py leans on.
# ---------------------------------------------------------------------------------------------
def render_unicode(cpp=False):
    word = re.compile(r"[^\W\d_]", re.UNICODE)
    digit = re.compile(r"\d", re.UNICODE)
    preds = [
        ("alpha", "Python's str.isalpha(): categories Lu, Ll, Lt, Lm and Lo.",
         lambda cp: chr(cp).isalpha()),
        ("word", "Python's [^\\W\\d_]: letters plus the Nl and No numeric categories.",
         lambda cp: word.fullmatch(chr(cp)) is not None),
        ("combining", "Code points with a non-zero canonical combining class.",
         lambda cp: unicodedata.combining(chr(cp)) != 0),
        ("digit", "Python's \\d: the Nd category.", lambda cp: digit.fullmatch(chr(cp)) is not None),
        ("upper", "Python's str.isupper() for one character.", lambda cp: chr(cp).isupper()),
        ("lower", "Python's str.islower() for one character.", lambda cp: chr(cp).islower()),
        ("space", "Python's str.isspace().", lambda cp: chr(cp).isspace()),
        ("printable", "Python's str.isprintable(), which is what repr leaves unescaped.",
         lambda cp: chr(cp).isprintable()),
        ("mark", "The Mn, Mc and Me categories, which laya/email.py spells unicodedata.category(ch)\n"
         "// startswith(\"M\").", lambda cp: unicodedata.category(chr(cp)).startswith("M")),
        ("initial", "The Lu, Lt and Lo categories: a letter that is not lowercase.",
         lambda cp: unicodedata.category(chr(cp)) in ("Lu", "Lt", "Lo")),
        ("title", "The Lt category: cased, but neither upper nor lower, so str.isupper() on a\n"
         "// string holding one is false.", lambda cp: unicodedata.category(chr(cp)) == "Lt"),
    ]
    out = [header("CPython %d.%d (Unicode %s)" % (sys.version_info[:2] + (unicodedata.unidata_version,))),
           "package unicodedata\n\n"
           "// Version is the Unicode release these tables were recorded from.\n"
           "const Version = %r\n\n" % unicodedata.unidata_version]
    out[-1] = out[-1].replace("'", '"')
    pred_tables = []
    for name, doc, pred in preds:
        rows = ranges(pred)
        pred_tables.append((name, rows, pred))
        out.append(table(name, rows, doc))
        out.append(ascii_masks(name, lambda cp, p=pred: p(cp)))

    simple, multi = [], []
    for cp in range(MAX):
        if cp in SURROGATES:
            continue
        low = chr(cp).lower()
        if len(low) > 1:
            multi.append((cp, [ord(c) for c in low]))
        elif low != chr(cp):
            simple.append((cp, ord(low)))
    out.append("// lowerFrom lists every code point whose lowercase is one different code point;\n"
               "// lowerTo holds what each maps to.\nvar lowerFrom = [...]rune{\n%s\n}\n\n"
               % wrap([c for c, _ in simple]))
    out.append("var lowerTo = [...]rune{\n%s\n}\n\n" % wrap([t for _, t in simple]))
    out.append("// lowerMulti holds the lowercase of a code point that lowercases to several.\n"
               "var lowerMulti = map[rune][]rune{\n%s\n}\n\n"
               % "\n".join("\t%#x: {%s}," % (cp, ", ".join("%#x" % c for c in low))
                           for cp, low in multi))

    # Final sigma (Greek capital sigma lowercases to U+03C2 at a word end, U+03C3 elsewhere) is
    # context-dependent in CPython, so it is recorded by behaviour rather than from a property:
    #   P1 = 'A' + ch + SIGMA  is final iff ch is case-ignorable OR (cased and not ignorable)
    #   P2 = 'A' + SIGMA + ch  is final iff NOT (cased and not ignorable)
    # which separates the two sets exactly.
    sigma = "Σ"
    blocking, ignorable = [], []
    for cp in range(MAX):
        if cp in SURROGATES:
            continue
        ch = chr(cp)
        p1 = ("A" + ch + sigma).lower()[-1] == "ς"
        p2 = ("A" + sigma + ch).lower()[1] == "ς"
        if not p2:
            blocking.append(cp)
        if p1 and p2:
            ignorable.append(cp)

    def runs(cps):
        rows, start, prev = [], None, None
        for cp in cps:
            if start is None:
                start = prev = cp
            elif cp == prev + 1:
                prev = cp
            else:
                rows.append((start, prev))
                start = prev = cp
        if start is not None:
            rows.append((start, prev))
        return rows

    out.append(table("cased", runs(blocking),
                     "Code points that make a capital sigma non-final when they follow it, and\n"
                     "// final when they precede it: cased and not case-ignorable."))
    out.append(table("caseIgnorable", runs(ignorable),
                     "Case-ignorable code points, which final-sigma detection skips."))
    if cpp:
        return render_unicode_cpp(pred_tables, simple, multi, runs(blocking), runs(ignorable))
    return "".join(out)


def cpp_array(name, values, ctype="uint32_t"):
    return "inline constexpr %s %s[] = {\n%s\n};\n\n" % (ctype, name, wrap(values, indent="    "))


def render_unicode_cpp(pred_tables, simple, multi, cased_rows, ignorable_rows):
    """The same CPython tables as render_unicode, as a C++ include for laya-cpp/src/unicodedata.cpp."""
    out = ["// Code generated by laya-go/scripts/gen_tables.py --lang cpp from CPython %d.%d (Unicode %s); "
           "DO NOT EDIT.\n//\n// Regenerate with: python laya-go/scripts/gen_tables.py --lang cpp\n\n"
           "inline constexpr const char* kUnicodeVersion = \"%s\";\n\n"
           % (sys.version_info[:2] + (unicodedata.unidata_version, unicodedata.unidata_version))]
    for name, rows, pred in pred_tables:
        flat = [v for row in rows for v in row]
        out.append(cpp_array("k_" + name, flat))
        low = sum(1 << cp for cp in range(0, 64) if pred(cp))
        high = sum(1 << (cp - 64) for cp in range(64, 128) if pred(cp))
        out.append("inline constexpr uint64_t k_%s_ascii[2] = {%#x, %#x};\n\n" % (name, low, high))
    out.append(cpp_array("k_lower_from", [c for c, _ in simple]))
    out.append(cpp_array("k_lower_to", [t for _, t in simple]))
    assert all(len(low) <= 3 for _, low in multi)
    out.append("struct LowerMulti { uint32_t from; uint32_t count; uint32_t to[3]; };\n"
               "inline constexpr LowerMulti k_lower_multi[] = {\n%s\n};\n\n"
               % "\n".join("    {%#x, %d, {%s}}," % (cp, len(low), ", ".join("%#x" % c for c in low + [0] * (3 - len(low))))
                          for cp, low in multi))
    out.append(cpp_array("k_cased", [v for row in cased_rows for v in row]))
    out.append(cpp_array("k_case_ignorable", [v for row in ignorable_rows for v in row]))
    return "".join(out)


# ---------------------------------------------------------------------------------------------
# laya.lang: script ranges, function words and thresholds.
# ---------------------------------------------------------------------------------------------
def go_str(text):
    import json
    return json.dumps(text, ensure_ascii=False)


def render_lang():
    sys.path.insert(0, REPO)
    from laya import lang

    flat = sorted((lo, hi, name) for name, rs in lang._SCRIPT_RANGES for lo, hi in rs)
    for (a_lo, a_hi, a_name), (b_lo, b_hi, b_name) in zip(flat, flat[1:]):
        if a_hi >= b_lo:
            raise SystemExit("gen_tables: script ranges %s and %s overlap, so the sorted lookup "
                             "would lose the first-match rule" % (a_name, b_name))
    names = [name for name, _ in lang._SCRIPT_RANGES]
    index_of = {name: n for n, name in enumerate(names)}

    def word_set(words):
        return "newSet(%s)" % ", ".join(go_str(w) for w in sorted(words))

    out = [header("laya/lang.py"), "package lang\n\n"]
    out.append("// The named non-Latin scripts, in the order lang.py declares them.\nconst (\n%s)\n\n"
               % "".join("\t%s Script = %s\n" % (("Script" + n.capitalize()).ljust(max(len(x) for x in names) + 6),
                                               go_str(n)) for n in names))
    out.append("// scriptNames indexes those scripts by their position in lang.py's table.\n"
               "var scriptNames = [...]Script{%s}\n\n"
               % ", ".join("Script%s" % n.capitalize() for n in names))
    out.append("// scriptLookup is every script range sorted by code point, as inclusive lo, hi\n"
               "// pairs; scriptLookupIndex names the script each pair belongs to. They replace\n"
               "// lang.py's ordered scan, which they equal because no two ranges overlap (the\n"
               "// generator refuses an overlap).\n"
               "var scriptLookup = [...]rune{\n%s\n}\n\n" % wrap([v for lo, hi, _ in flat for v in (lo, hi)]))
    out.append("var scriptLookupIndex = [...]uint8{\n%s\n}\n\n" % wrap([index_of[n] for _, _, n in flat]))
    out.append("const scriptMaxCodePoint = %#x\n\n" % max(hi for _, hi, _ in flat))
    out.append("// stopLists are the function words per language, in the order lang.py declares them:\n"
               "// the language that wins a tied score is the first one listed.\n"
               "var stopLists = [...]stopList{\n")
    for code, words in lang._STOP.items():
        out.append("\t{%s, %s},\n" % (go_str(code), word_set(words)))
    out.append("}\n\n")
    for name, words, doc in (
        ("shortSwedishWords", lang._SHORT_SWEDISH_WORDS,
         "Distinctive Swedish words that name the language from a short input."),
        ("sharedWords", lang._SHARED_WORDS,
         "Function words several lists hold, which therefore name no language."),
        ("nordicOverlapWords", lang._NORDIC_OVERLAP_WORDS,
         "Markers shared by Swedish and Danish: evidence of non-English, not of which."),
        ("enOnlyWords", lang._EN_ONLY_WORDS, "English function words no other list holds."),
        ("enCollisionWords", lang._EN_COLLISION_WORDS,
         "Words that collide with English, counted once however often they repeat."),
    ):
        out.append("// %s %s\nvar %s = %s\n\n" % (name, doc, name, word_set(words)))
    diac = sorted(ord(c) for c in lang._NON_EN_DIACRITICS)
    assert all(len(c) == 1 for c in lang._NON_EN_DIACRITICS)
    out.append("// nonEnDiacritics are the letters whose presence is evidence the text is not\n"
               "// English, sorted by code point.\nvar nonEnDiacritics = [...]rune{\n%s\n}\n\n" % wrap(diac))
    consts = (("nonEnDiacriticRate", lang.NON_EN_DIACRITIC_RATE),
              ("englishRescueDiacriticRate", lang.ENGLISH_RESCUE_DIACRITIC_RATE),
              ("nonLatinFraction", lang.NON_LATIN_FRACTION),
              ("nonLatinMinFraction", lang.NON_LATIN_MIN_FRACTION),
              ("nonLatinMinLetters", lang.NON_LATIN_MIN_LETTERS))
    width = max(len(name) for name, _ in consts)
    out.append("const (\n%s)\n" % "".join("\t%s = %r\n" % (name.ljust(width), value)
                                         for name, value in consts))
    return "".join(out)


def render_lang_cpp():
    """laya.lang's script ranges, function words and thresholds, as a C++ include for src/lang.cpp."""
    sys.path.insert(0, REPO)
    from laya import lang

    flat = sorted((lo, hi, name) for name, rs in lang._SCRIPT_RANGES for lo, hi in rs)
    for (a_lo, a_hi, a_name), (b_lo, b_hi, b_name) in zip(flat, flat[1:]):
        if a_hi >= b_lo:
            raise SystemExit("gen_tables: script ranges %s and %s overlap" % (a_name, b_name))
    names = [name for name, _ in lang._SCRIPT_RANGES]
    index_of = {name: n for n, name in enumerate(names)}

    def words(name, ws):
        return "inline constexpr const char* %s[] = {\n%s\n};\n\n" % (
            name, wrap([go_str(w) for w in sorted(ws)], indent="    "))

    out = ["// Code generated by laya-go/scripts/gen_tables.py --lang cpp from laya/lang.py; DO NOT EDIT.\n"
           "//\n// Regenerate with: python laya-go/scripts/gen_tables.py --lang cpp\n\n"]
    out.append("inline constexpr const char* k_script_names[] = {%s};\n\n" % ", ".join(go_str(n) for n in names))
    out.append(cpp_array("k_script_lookup", [v for lo, hi, _ in flat for v in (lo, hi)]))
    out.append(cpp_array("k_script_lookup_index", [index_of[n] for _, _, n in flat], "uint8_t"))
    out.append("inline constexpr uint32_t k_script_max_code_point = %#x;\n\n" % max(hi for _, hi, _ in flat))
    stops = list(lang._STOP.items())
    for n, (code, ws) in enumerate(stops):
        out.append(words("k_stop_%d" % n, ws))
    out.append("struct StopSpec { const char* code; const char* const* words; size_t count; };\n"
               "// In lang.py declaration order: the language that wins a tied score is the first listed.\n"
               "inline constexpr StopSpec k_stop_lists[] = {\n%s\n};\n\n"
               % "\n".join("    {%s, k_stop_%d, %d}," % (go_str(c), n, len(ws)) for n, (c, ws) in enumerate(stops)))
    for name, ws in (("k_short_swedish", lang._SHORT_SWEDISH_WORDS), ("k_shared", lang._SHARED_WORDS),
                     ("k_nordic_overlap", lang._NORDIC_OVERLAP_WORDS), ("k_en_only", lang._EN_ONLY_WORDS),
                     ("k_en_collision", lang._EN_COLLISION_WORDS)):
        out.append(words(name, ws))
    out.append(cpp_array("k_non_en_diacritics", sorted(ord(c) for c in lang._NON_EN_DIACRITICS)))
    for name, value in (("k_non_en_diacritic_rate", lang.NON_EN_DIACRITIC_RATE),
                        ("k_english_rescue_diacritic_rate", lang.ENGLISH_RESCUE_DIACRITIC_RATE),
                        ("k_non_latin_fraction", lang.NON_LATIN_FRACTION),
                        ("k_non_latin_min_fraction", lang.NON_LATIN_MIN_FRACTION)):
        out.append("inline constexpr double %s = %r;\n" % (name, value))
    out.append("inline constexpr int k_non_latin_min_letters = %d;\n" % lang.NON_LATIN_MIN_LETTERS)
    return "".join(out)


# ---------------------------------------------------------------------------------------------
# The tokenizers crate: pre-tokenizer classes, single_word flank, lowercase, normalization.
# ---------------------------------------------------------------------------------------------
def render_tokenizer(cpp=False):
    import tokenizers
    from tokenizers import AddedToken, Tokenizer, models, normalizers, pre_tokenizers

    if cpp:
        out = ["// Code generated by laya-go/scripts/gen_tables.py --lang cpp from tokenizers %s; DO NOT EDIT.\n//\n"
               "// Regenerate with: python laya-go/scripts/gen_tables.py --lang cpp\n\n"
               "inline constexpr const char* kTokenizerReference = \"tokenizers %s\";\n\n"
               % (tokenizers.__version__, tokenizers.__version__)]
    else:
        out = [header("tokenizers %s" % tokenizers.__version__), "package tokenizer\n\n"]
        out.append("// Reference names the implementation the tables below were probed from.\n"
                   "const Reference = \"tokenizers %s\"\n\n" % tokenizers.__version__)

    def rng(go_name, cpp_name, rows, doc):
        if not cpp:
            return table(go_name, rows, doc)
        flat = [v for row in rows for v in row]
        return tok_array(True, go_name, cpp_name, flat, "%s\n// %d ranges covering %d code points."
                         % (doc.replace("\n//", "\n//"), len(rows), sum(b - a + 1 for a, b in rows)))

    # Letter / number: "a<cp>" stays ONE piece only if ` ?\p{L}+` consumed the code point;
    # "1<cp>" only if ` ?\p{N}+` did. Anything else splits.
    pre = pre_tokenizers.ByteLevel(add_prefix_space=False, use_regex=True)

    def one_piece(prefix):
        def test(cp):
            try:
                return len(pre.pre_tokenize_str(prefix + chr(cp))) == 1
            except Exception:
                return False
        return test

    out.append(rng("letter", "k_letter", ranges(one_piece("a")),
                     "letter is the pre-tokenizer pattern's \\p{L}, probed from the reference."))
    out.append(rng("number", "k_number", ranges(one_piece("1")),
                     "number is the pre-tokenizer pattern's \\p{N}, probed from the reference."))

    # single_word: an added token is refused when the adjacent character is a word character.
    tok = Tokenizer(models.BPE(vocab={"a": 0}, merges=[], unk_token=None))
    tok.add_tokens([AddedToken("TOK", single_word=True)])
    tid = tok.token_to_id("TOK")

    def flanks(cp):
        try:
            left = tid not in tok.encode(chr(cp) + "TOK").ids
            right = tid not in tok.encode("TOK" + chr(cp)).ids
        except Exception:
            return False
        if left != right:
            raise SystemExit("gen_tables: single_word treats U+%04X differently on each side" % cp)
        return left

    out.append(rng("wordChar", "k_word_char", ranges(flanks),
                     "wordChar is what the reference counts as a word character beside a\n"
                     "// single_word added token."))

    # Lowercase, per code point. The crate lowercases character by character (no final sigma).
    low = normalizers.Lowercase()
    simple, multi = [], []
    for cp in range(MAX):
        if cp in SURROGATES:
            continue
        mapped = low.normalize_str(chr(cp))
        if mapped == chr(cp):
            continue
        if len(mapped) == 1:
            simple.append((cp, ord(mapped)))
        else:
            multi.append((cp, [ord(c) for c in mapped]))
    if cpp:
        out.append(tok_array(True, "", "k_lower_from", [c for c, _ in simple], "lowercase, one code point to one"))
        out.append(tok_array(True, "", "k_lower_to", [t for _, t in simple], "the lowercase of k_lower_from"))
        assert all(len(m) <= 3 for _, m in multi)
        out.append("struct TokLowerMulti { uint32_t from; uint32_t count; uint32_t to[3]; };\n"
                   "inline constexpr TokLowerMulti k_lower_multi[] = {\n%s\n};\n\n"
                   % "\n".join("    {%#x, %d, {%s}}," % (cp, len(m), ", ".join("%#x" % c for c in m + [0] * (3 - len(m))))
                              for cp, m in multi))
    else:
        out.append("var lowerFrom = [...]rune{\n%s\n}\n\n" % wrap([c for c, _ in simple]))
        out.append("var lowerTo = [...]rune{\n%s\n}\n\n" % wrap([t for _, t in simple]))
        out.append("var lowerMulti = map[rune][]rune{\n%s\n}\n\n"
                   % "\n".join("\t%#x: {%s}," % (cp, ", ".join("%#x" % c for c in m)) for cp, m in multi))

    out.append(render_normalization(normalizers, cpp))
    return "".join(out)


def render_normalization(normalizers, cpp=False):
    nfc, nfd = normalizers.NFC(), normalizers.NFD()
    nfkd = normalizers.NFKD()
    canon, compat = {}, {}
    for cp in range(MAX):
        if cp in SURROGATES or cp in HANGUL:
            continue
        ch = chr(cp)
        d = nfd.normalize_str(ch)
        k = nfkd.normalize_str(ch)
        if d != ch:
            canon[cp] = [ord(c) for c in d]
        if k != d:
            compat[cp] = [ord(c) for c in k]

    # Canonical combining class, probed from the crate and NOT taken from CPython: the crate
    # reorders against a different set (56 marks CPython gives a class, such as U+07FD and U+0C3C,
    # never reorder in it). A mark sorts before one of higher class, so X swaps with a reference
    # mark of class v exactly when 0 < ccc(X) < v. References are CPython marks accepted only if
    # the crate orders them consistently with the marks accepted before them.
    def swaps(x, mark, before):
        pair = mark + x if before else x + mark
        return nfd.normalize_str(pair) != pair

    refs = {}
    for cp in range(MAX):
        if cp in SURROGATES:
            continue
        c = unicodedata.combining(chr(cp))
        if not c or c in refs or nfd.normalize_str(chr(cp)) != chr(cp):
            continue
        ch = chr(cp)
        if all(swaps(ch, other, True) == (u > c) and swaps(ch, other, False) == (c > u)
               for u, other in refs.items()):
            refs[c] = ch
    values = sorted(refs)
    top, bottom = refs[values[-1]], refs[values[0]]

    def probe_ccc(cp):
        x = chr(cp)
        top_swap = swaps(x, top, True)
        if not top_swap:
            return values[-1] if swaps(x, bottom, False) else 0
        for i, v in enumerate(values):
            if swaps(x, refs[v], True):
                return values[i - 1] if i else 0
        return values[-1]

    ccc = {}
    for cp in range(MAX):
        if cp in SURROGATES or nfd.normalize_str(chr(cp)) != chr(cp):
            continue
        probed = probe_ccc(cp)
        if probed:
            ccc[cp] = probed
    # Where the crate's classes differ from CPython's. Reported, not asserted: the crate is the
    # reference, and a class it does not know is simply a starter to it.
    differing = [cp for cp in range(MAX) if cp not in SURROGATES
                 and nfd.normalize_str(chr(cp)) == chr(cp)
                 and ccc.get(cp, 0) != unicodedata.combining(chr(cp))]
    print("gen_tables: %d refs; the crate's combining class differs from CPython's at %d code points"
          % (len(refs), len(differing)), file=sys.stderr)
    rows, start, prev, val = [], None, None, None
    for cp in sorted(ccc):
        if start is not None and cp == prev + 1 and ccc[cp] == val:
            prev = cp
            continue
        if start is not None:
            rows.append((start, prev, val))
        start = prev = cp
        val = ccc[cp]
    rows.append((start, prev, val))

    # Composition pairs: for each code point that recomposes from its own decomposition, the
    # pair is (compose(all but the last), last). Each is then re-verified against the crate.
    pairs = {}
    for cp, d in canon.items():
        if len(d) < 2 or nfc.normalize_str("".join(map(chr, d))) != chr(cp):
            continue
        first = nfc.normalize_str("".join(map(chr, d[:-1])))
        if len(first) != 1 or nfc.normalize_str(first + chr(d[-1])) != chr(cp):
            raise SystemExit("gen_tables: cannot express U+%04X as a composition pair" % cp)
        pairs[(ord(first), d[-1])] = cp
    keys = sorted(pairs)

    def pool(mapping, name, doc):
        ks = sorted(mapping)
        offsets, flat = [0], []
        for k in ks:
            flat.extend(mapping[k])
            offsets.append(len(flat))
        if cpp:
            return (tok_array(True, "", "k_%s_keys" % name, ks, doc)
                    + tok_array(True, "", "k_%s_offsets" % name, offsets, "offsets into k_%s_pool" % name)
                    + tok_array(True, "", "k_%s_pool" % name, flat, "the decompositions of k_%s_keys" % name))
        return ("// %s\nvar %sKeys = [...]rune{\n%s\n}\n\nvar %sOffsets = [...]uint32{\n%s\n}\n\n"
                "var %sPool = [...]rune{\n%s\n}\n\n"
                % (doc, name, wrap(ks), name, wrap(offsets), name, wrap(flat)))

    text = []
    text.append(pool(canon, "canon", "canon* hold the full canonical decomposition (NFD) of every code\n"
                     "// point that has one, except Hangul syllables, which are algorithmic."))
    text.append(pool(compat, "compat", "compat* hold the full compatibility decomposition (NFKD) of every code\n"
                     "// point where it differs from the canonical one."))
    ccc_doc = "cccRanges are (lo, hi, class) triples of the canonical combining class, sorted."
    comp_doc = "composeKeys are (first<<32 | second) of each primary composition pair, sorted;\n// composeValues is the composite."
    if cpp:
        text.append(tok_array(True, "", "k_ccc_ranges", [v for r in rows for v in r], ccc_doc))
        text.append(tok_array(True, "", "k_compose_keys", ["%#xULL" % ((a << 32) | b) for a, b in keys], comp_doc, "uint64_t"))
        text.append(tok_array(True, "", "k_compose_values", [pairs[k] for k in keys], "the composite of k_compose_keys"))
        return "".join(text)
    text.append("// %s\nvar cccRanges = [...]rune{\n%s\n}\n\n" % (ccc_doc, wrap([v for r in rows for v in r])))
    text.append("// %s\nvar composeKeys = [...]uint64{\n%s\n}\n\n"
                % (comp_doc, wrap(["%#x" % ((a << 32) | b) for a, b in keys])))
    text.append("var composeValues = [...]rune{\n%s\n}\n" % wrap([pairs[k] for k in keys]))
    return "".join(text)


TARGETS = ((OUT_UNICODE, render_unicode), (OUT_LANG, render_lang), (OUT_TOKENIZER, render_tokenizer))
# laya-cpp generated tables.
CPP_TARGETS = ((OUT_CPP_UNICODE, lambda: render_unicode(cpp=True)), (OUT_CPP_LANG, render_lang_cpp),
               (OUT_CPP_TOKENIZER, lambda: render_tokenizer(cpp=True)))


def main(argv=None):
    parser = argparse.ArgumentParser(description=__doc__.splitlines()[0])
    parser.add_argument("--check", action="store_true",
                        help="do not write; exit 1 if a committed copy would change")
    parser.add_argument("--lang", choices=("go", "cpp"), default="go",
                        help="which port's tables to write or check (default go)")
    args = parser.parse_args(argv)
    stale = 0
    for path, render in (CPP_TARGETS if args.lang == "cpp" else TARGETS):
        fresh = render().rstrip("\n") + "\n"
        rel = os.path.relpath(path, REPO)
        if args.check:
            try:
                with open(path, encoding="utf-8") as handle:
                    current = handle.read()
            except OSError:
                current = None
            if current != fresh:
                print("gen_tables: %s is stale; run laya-go/scripts/gen_tables.py and commit it" % rel,
                      file=sys.stderr)
                stale += 1
            else:
                print("gen_tables: %s matches" % rel)
        else:
            os.makedirs(os.path.dirname(path), exist_ok=True)
            with open(path, "w", encoding="utf-8") as handle:
                handle.write(fresh)
            print("wrote %s (%d bytes)" % (rel, len(fresh.encode("utf-8"))))
    return 1 if stale else 0


if __name__ == "__main__":
    sys.exit(main())