kit

lex_tokens.c (33538B)

---

 /* kit_gram_lex_tokens.c - token-alphabet (%machine) lexer pipeline.
  *
  * A %machine declares a regular language whose symbols are abstract named
  * tokens (not bytes/scalars). The combinator layer (concat / | / ( ) / ? * +
  * {n,m} / %def) is alphabet-independent, so this TU supplies only the *leaves*
  * (a symbol
  * -> [k,k]; a [ A B ] set -> a union of singletons; . -> [0,NSYM-1]) and a
  * direct atom-DFA emit, feeding the shared range-set NFA + one determinization
  * in gen/kit_gram_lex_range.c. There is no UTF-8 lowering: the symbol id IS the
  * atom, so the determinized atom DFA is the final table (after minimize +
  * relabel).
  *
  * Codegen-only: a token machine never materializes an KitGramLexGrammar, so this
  * carries its uint16 symbol->class map / per-state liveness in
  * generator-internal LexDFA fields and never crosses the runtime ABI. Non-gated
  * (the token alphabet is unrelated to Unicode), so it survives
  * KIT_GRAM_NO_UNICODE. See doc/DESIGN.md "Token machines". */
 #include "internal.h"
 
 /* ---- symbol alphabet ---------------------------------------------------- */
 
 typedef struct {
   GramgenContext* ctx;
   char** names; /* interned symbol name by id (first-use order) */
   size_t n, cap;
   NameIndexMap index; /* interned name -> id */
 } TokenAlphabet;
 
 /* Intern a symbol name and return its id, assigning a fresh id (in first-use
  * order) on first sight. `name` must be an interned, NUL-terminated pointer. */
 static int token_alpha_intern(TokenAlphabet* a, const char* name) {
   int id;
   if (name_index_find(&a->index, name, &id)) return id;
   if (a->n == a->cap) {
     a->cap = a->cap ? a->cap * 2 : 16;
     a->names = xrealloc(a->ctx, a->names, a->cap * sizeof *a->names);
   }
   id = (int)a->n;
   a->names[a->n++] = (char*)name;
   name_index_put(a->ctx, &a->index, name, id);
   return id;
 }
 
 /* Tokenize a `[ A B C ]` / `[^ A B ]` symbol set into its raw member
  * identifiers
  * ([A-Za-z0-9_]+, interned) and the `[^ … ]` complement flag. No case check and
  * no empty check: callers impose their own (kit_gram_machine_class_names
  * requires UPPERCASE leaves; the set resolver also accepts lowercase set
  * references). Caller frees *names. */
 static char* const* machine_class_raw(GramgenContext* ctx, Str raw, Loc loc,
                                       size_t* nout, int* complement) {
   if (raw.len < 2 || raw.s[0] != '[' || raw.s[raw.len - 1] != ']')
     kit_gram_error(ctx, loc, "malformed symbol set");
   size_t i = 1, end = raw.len - 1;
   *complement = 0;
   if (i < end && raw.s[i] == '^') {
     *complement = 1;
     i++;
   }
   char** names = NULL;
   size_t n = 0, cap = 0;
   while (i < end) {
     unsigned char c = (unsigned char)raw.s[i];
     if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == ',') {
       i++;
       continue;
     }
     size_t start = i;
     while (i < end) {
       unsigned char d = (unsigned char)raw.s[i];
       if ((d >= 'A' && d <= 'Z') || (d >= 'a' && d <= 'z') ||
           (d >= '0' && d <= '9') || d == '_')
         i++;
       else
         break;
     }
     if (i == start) kit_gram_error(ctx, loc, "invalid symbol in token set");
     char* name = intern_len(ctx, raw.s + start, i - start);
     if (n == cap) {
       cap = cap ? cap * 2 : 8;
       names = xrealloc(ctx, names, cap * sizeof *names);
     }
     names[n++] = name;
   }
   *nout = n;
   return (char* const*)names;
 }
 
 /* Parse a `[ A B C ]` / `[^ A B ]` symbol set into its member names (interned,
  * validated UPPERCASE), returning the count and the `[^ … ]` complement flag.
  * Pure: it neither interns into an alphabet nor resolves the complement, so it
  * is shared by NFA construction and the post-compile sampler. Any lowercase
  * set reference was already inlined to UPPERCASE by kit_gram_compile_machine, so
  * a lowercase member here is an internal/grammar error. Caller frees *names. */
 char* const* kit_gram_machine_class_names(GramgenContext* ctx, Str raw, Loc loc,
                                          size_t* nout, int* complement) {
   size_t n = 0;
   char* const* names = machine_class_raw(ctx, raw, loc, &n, complement);
   for (size_t k = 0; k < n; k++)
     if (!is_token_name(names[k]))
       kit_gram_error(ctx, loc,
                     "token-set member '%s' must be an UPPERCASE symbol name",
                     names[k]);
   if (!n && !*complement) kit_gram_error(ctx, loc, "empty symbol set");
   *nout = n;
   return names;
 }
 
 /* Parse a symbol set and intern each member into the alphabet, appending its id
  * to *ids (caller frees). Sets *complement for the `[^ ... ]` form. */
 static void token_parse_class(GramgenContext* ctx, TokenAlphabet* alpha,
                               Str raw, Loc loc, int** ids, size_t* nids,
                               size_t* cap_ids, int* complement) {
   size_t nm = 0;
   char* const* names =
       kit_gram_machine_class_names(ctx, raw, loc, &nm, complement);
   for (size_t k = 0; k < nm; k++) {
     int id = token_alpha_intern(alpha, names[k]);
     if (*nids == *cap_ids) {
       *cap_ids = *cap_ids ? *cap_ids * 2 : 8;
       *ids = xrealloc(ctx, *ids, *cap_ids * sizeof **ids);
     }
     (*ids)[(*nids)++] = id;
   }
   xfree(ctx, (void*)names);
 }
 
 /* ---- alphabet collection (pass 1) --------------------------------------- */
 
 /* DFS the desugared AST assigning symbol ids in first-use order, so `.` /
  * complement leaves (pass 2) see the final NSYM. UPPERCASE LEX_NAME survives
  * desugaring as a symbol; LEX_CLASS holds a `[ … ]` symbol set. */
 static void token_collect_alt(GramgenContext* ctx, TokenAlphabet* alpha,
                               AstLexAlt* alt);
 
 static void token_collect_node(GramgenContext* ctx, TokenAlphabet* alpha,
                                AstLexNode* node) {
   switch (node->kind) {
     case LEX_NAME:
       token_alpha_intern(alpha, node->value.s);
       break;
     case LEX_CLASS: {
       int* ids = NULL;
       size_t nids = 0, cap = 0, complement = 0;
       token_parse_class(ctx, alpha, node->value, node->loc, &ids, &nids, &cap,
                         (int*)&complement);
       xfree(ctx, ids);
       break;
     }
     case LEX_ANY:
       break;
     case LEX_GROUP:
     case LEX_OPT:
     case LEX_REP:
       token_collect_alt(ctx, alpha, node->alts);
       break;
     case LEX_LITERAL:
       kit_gram_error(ctx, node->loc,
                     "string literals are not allowed in %%machine (symbols are "
                     "UPPERCASE names)");
       break;
     case LEX_PROP:
       kit_gram_error(ctx, node->loc,
                     "Unicode properties are not allowed in %%machine");
       break;
     case LEX_ANCHOR:
       kit_gram_error(ctx, node->loc, "anchors are not supported in %%machine");
       break;
     case LEX_REPEAT:
       kit_gram_error(ctx, node->loc, "internal: %%machine node not desugared");
       break;
   }
 }
 
 static void token_collect_alt(GramgenContext* ctx, TokenAlphabet* alpha,
                               AstLexAlt* alt) {
   for (size_t i = 0; i < alt->nseqs; i++) {
     AstLexSeq* seq = alt->seqs[i];
     for (size_t j = 0; j < seq->nitems; j++)
       token_collect_node(ctx, alpha, seq->items[j]);
   }
 }
 
 /* ---- symbol set -> ScalarSet -------------------------------------------- */
 
 static int int_cmp_asc(const void* a, const void* b) {
   int x = *(const int*)a, y = *(const int*)b;
   return (x > y) - (x < y);
 }
 
 /* Canonical (sorted, merged, non-adjacent) ScalarSet from a list of symbol ids.
  */
 static ScalarSet token_set_from_ids(GramgenContext* ctx, int* ids, size_t n) {
   ScalarSet out = {.ctx = ctx};
   if (!n) return out;
   qsort(ids, n, sizeof *ids, int_cmp_asc);
   size_t cap = 0;
   for (size_t i = 0; i < n;) {
     uint32_t lo = (uint32_t)ids[i], hi = lo;
     size_t j = i + 1;
     while (j < n && (uint32_t)ids[j] <= hi + 1u) {
       if ((uint32_t)ids[j] > hi) hi = (uint32_t)ids[j];
       j++;
     }
     if (out.n == cap) {
       cap = cap ? cap * 2 : 4;
       out.v = xrealloc(ctx, out.v, cap * sizeof *out.v);
     }
     out.v[out.n++] = (ScalarRange){lo, hi};
     i = j;
   }
   out.cap = cap;
   return out;
 }
 
 /* Full symbol universe [0, nsym-1]. */
 static ScalarSet token_set_universe(GramgenContext* ctx, uint16_t nsym) {
   ScalarSet out = {.ctx = ctx};
   out.v = xmalloc(ctx, sizeof *out.v);
   out.v[0] = (ScalarRange){0, (uint32_t)nsym - 1u};
   out.n = 1;
   out.cap = 1;
   return out;
 }
 
 /* Complement of a canonical id-set over [0, nsym-1] (the gaps). */
 static ScalarSet token_set_complement(GramgenContext* ctx, const ScalarSet* in,
                                       uint16_t nsym) {
   ScalarSet out = {.ctx = ctx};
   size_t cap = 0;
   uint32_t cur = 0;
   for (size_t i = 0; i < in->n; i++) {
     if (in->v[i].lo > cur) {
       if (out.n == cap) {
         cap = cap ? cap * 2 : 4;
         out.v = xrealloc(ctx, out.v, cap * sizeof *out.v);
       }
       out.v[out.n++] = (ScalarRange){cur, in->v[i].lo - 1u};
     }
     cur = in->v[i].hi + 1u;
   }
   if (cur <= (uint32_t)nsym - 1u) {
     if (out.n == cap) {
       cap = cap ? cap * 2 : 4;
       out.v = xrealloc(ctx, out.v, cap * sizeof *out.v);
     }
     out.v[out.n++] = (ScalarRange){cur, (uint32_t)nsym - 1u};
   }
   out.cap = cap;
   return out;
 }
 
 /* ---- token NFA leaves (the token instance of LexAlphabet) ---------------- */
 
 /* Per-build leaf state: the (already collected) alphabet plus NSYM, reached via
  * LexAlphabet.ud. Symbol interning here is idempotent — pass 1 assigned every
  * id. */
 typedef struct {
   TokenAlphabet* alpha;
   uint16_t nsym;
 } TokenLeafCtx;
 
 static NfaFrag token_leaf_name(ScalarNfaBuilder* nfa, const LexAlphabet* a,
                                AstLexNode* node) {
   TokenLeafCtx* t = a->ud;
   int id = token_alpha_intern(t->alpha, node->value.s);
   return scalar_nfa_scalar_set(
       nfa, scalar_set_from_single_value(nfa->ctx, (uint32_t)id), node->loc);
 }
 static NfaFrag token_leaf_class(ScalarNfaBuilder* nfa, const LexAlphabet* a,
                                 AstLexNode* node) {
   TokenLeafCtx* t = a->ud;
   GramgenContext* ctx = nfa->ctx;
   int* ids = NULL;
   size_t nids = 0, cap = 0;
   int complement = 0;
   token_parse_class(ctx, t->alpha, node->value, node->loc, &ids, &nids, &cap,
                     &complement);
   ScalarSet set = token_set_from_ids(ctx, ids, nids);
   xfree(ctx, ids);
   if (complement) {
     ScalarSet comp = token_set_complement(ctx, &set, t->nsym);
     xfree(ctx, set.v);
     set = comp;
   }
   return scalar_nfa_scalar_set(nfa, set, node->loc);
 }
 static NfaFrag token_leaf_any(ScalarNfaBuilder* nfa, const LexAlphabet* a,
                               AstLexNode* node) {
   TokenLeafCtx* t = a->ud;
   return scalar_nfa_scalar_set(nfa, token_set_universe(nfa->ctx, t->nsym),
                                node->loc);
 }
 /* String literals and Unicode properties are rejected earlier (token_collect),
  * so these never fire; keep them as a clear internal guard. */
 static NfaFrag token_leaf_invalid(ScalarNfaBuilder* nfa, const LexAlphabet* a,
                                   AstLexNode* node) {
   (void)a;
   kit_gram_error(nfa->ctx, node->loc, "internal: invalid %%machine leaf");
   return scalar_nfa_empty(nfa);
 }
 
 /* ---- per-state liveness ------------------------------------------------- */
 
 /* live[s] = an accepting state is reachable from s over non-dead edges. Reverse
  * reachability from the accepting set, by iterate-to-fixpoint (nstates small).
  */
 static uint8_t* token_compute_live(GramgenContext* ctx, const uint16_t* trans,
                                    const uint16_t* accept, uint16_t nstates,
                                    uint16_t nclasses) {
   uint8_t* live = xcalloc(ctx, nstates ? nstates : 1, sizeof *live);
   for (uint16_t s = 0; s < nstates; s++)
     if (accept[s] != UINT16_MAX) live[s] = 1;
   int changed = 1;
   while (changed) {
     changed = 0;
     for (uint16_t s = 0; s < nstates; s++) {
       if (live[s]) continue;
       const uint16_t* row = &trans[(size_t)s * nclasses];
       for (uint16_t c = 0; c < nclasses; c++) {
         uint16_t t = row[c];
         if (t != UINT16_MAX && live[t]) {
           live[s] = 1;
           changed = 1;
           break;
         }
       }
     }
   }
   return live;
 }
 
 /* ---- named symbol sets + bracket set algebra ----------------------------
  * Inside a %machine a `[ … ]` is a set expression with the same algebra the
  * UTF-8 character classes use (gen/kit_gram_lex_unicode.c): atoms are UPPERCASE
  * symbols and lowercase %def set references; juxtaposition is union, `&&` is
  * intersection, `--` is difference, and a leading `^` complements the whole
  * class. A %def used as a set names a set expression too (its body, a union
  * written with `|`). Composition is by named set, not by literal nesting — the
  * meta lexer's class token ends at the first `]`, just as for UTF-8 classes.
  *
  * Resolution works over symbol *names*, never ids, by carrying a complement
  * flag (an RSet is either a finite name list or its complement over the
  * alphabet) and applying De Morgan identities — so the alphabet need not exist
  * yet. Each class resolves to one RSet which is then re-emitted as plain `[ …
  * ]` / `[^ … ]` text; the NFA leaf, the alphabet pass, and both samplers
  * re-parse that text and only ever see UPPERCASE symbols (the leaf still
  * applies a top-level complement over the final alphabet). */
 
 /* complement ? (alphabet \ names) : names. `names` is deduped, interned. */
 typedef struct {
   int complement;
   char** names;
   size_t n, cap;
 } RSet;
 
 typedef struct {
   RSet set;
   uint8_t state; /* 0 unseen, 1 resolving (cycle guard), 2 resolved */
 } SetSlot;
 
 typedef struct {
   GramgenContext* ctx;
   AstLexLine** defs; /* the machine's %def lines (candidate named sets) */
   size_t ndefs;
   SetSlot* slots; /* parallel to defs; memoized resolutions */
 } MachineSets;
 
 static int nl_contains(char* const* a, size_t n, const char* name) {
   for (size_t i = 0; i < n; i++)
     if (strcmp(a[i], name) == 0) return 1;
   return 0;
 }
 
 static void rset_push(GramgenContext* ctx, RSet* r, char* name) {
   if (nl_contains(r->names, r->n, name)) return;
   if (r->n == r->cap) {
     r->cap = r->cap ? r->cap * 2 : 8;
     r->names = xrealloc(ctx, r->names, r->cap * sizeof *r->names);
   }
   r->names[r->n++] = name;
 }
 
 static void rset_free(GramgenContext* ctx, RSet* r) {
   if (r->names) xfree(ctx, r->names);
   r->names = NULL;
   r->n = r->cap = 0;
 }
 
 static RSet rset_single(GramgenContext* ctx, char* name) {
   RSet r = {0};
   rset_push(ctx, &r, name);
   return r;
 }
 
 static RSet rset_copy(GramgenContext* ctx, const RSet* s) {
   RSet r = {.complement = s->complement};
   for (size_t i = 0; i < s->n; i++) rset_push(ctx, &r, s->names[i]);
   return r;
 }
 
 /* Positive-list primitives: union / intersection / difference of two finite
  * name lists, each returning a fresh positive RSet. */
 static RSet pl_union(GramgenContext* ctx, const RSet* a, const RSet* b) {
   RSet r = {0};
   for (size_t i = 0; i < a->n; i++) rset_push(ctx, &r, a->names[i]);
   for (size_t i = 0; i < b->n; i++) rset_push(ctx, &r, b->names[i]);
   return r;
 }
 static RSet pl_intersect(GramgenContext* ctx, const RSet* a, const RSet* b) {
   RSet r = {0};
   for (size_t i = 0; i < a->n; i++)
     if (nl_contains(b->names, b->n, a->names[i]))
       rset_push(ctx, &r, a->names[i]);
   return r;
 }
 static RSet pl_diff(GramgenContext* ctx, const RSet* a, const RSet* b) {
   RSet r = {0};
   for (size_t i = 0; i < a->n; i++)
     if (!nl_contains(b->names, b->n, a->names[i]))
       rset_push(ctx, &r, a->names[i]);
   return r;
 }
 
 /* Set algebra over the complement-tagged representation (De Morgan). C(x) is
  * the complement of x over the alphabet; the four cases reduce every op to the
  * positive-list primitives without ever materializing the alphabet. */
 static RSet rset_union(GramgenContext* ctx, const RSet* a, const RSet* b) {
   if (!a->complement && !b->complement) return pl_union(ctx, a, b);
   RSet r;
   if (!a->complement) /* P(a) ∪ C(b) = C(b\a) */
     r = pl_diff(ctx, b, a);
   else if (!b->complement) /* C(a) ∪ P(b) = C(a\b) */
     r = pl_diff(ctx, a, b);
   else /* C(a) ∪ C(b) = C(a∩b) */
     r = pl_intersect(ctx, a, b);
   r.complement = 1;
   return r;
 }
 static RSet rset_intersect(GramgenContext* ctx, const RSet* a, const RSet* b) {
   if (!a->complement && !b->complement) return pl_intersect(ctx, a, b);
   if (!a->complement) return pl_diff(ctx, a, b); /* P(a) ∩ C(b) = a\b */
   if (!b->complement) return pl_diff(ctx, b, a); /* C(a) ∩ P(b) = b\a */
   RSet r = pl_union(ctx, a, b);                  /* C(a) ∩ C(b) = C(a∪b) */
   r.complement = 1;
   return r;
 }
 static RSet rset_diff(GramgenContext* ctx, const RSet* a, const RSet* b) {
   if (!a->complement && !b->complement) return pl_diff(ctx, a, b);
   if (!a->complement) return pl_intersect(ctx, a, b); /* P(a) \ C(b) = a∩b */
   if (!b->complement) {                               /* C(a) \ P(b) = C(a∪b) */
     RSet r = pl_union(ctx, a, b);
     r.complement = 1;
     return r;
   }
   return pl_diff(ctx, b, a); /* C(a) \ C(b) = b\a */
 }
 
 static int machine_sets_find(const MachineSets* st, const char* name) {
   for (size_t i = 0; i < st->ndefs; i++)
     if (strcmp(st->defs[i]->name, name) == 0) return (int)i;
   return -1;
 }
 
 static const RSet* resolve_set(MachineSets* st, size_t idx);
 
 /* ---- bracket set-expression parser (a char cursor over the `[ … ]` text) --
  */
 
 typedef struct {
   MachineSets* st;
   const char* s;
   size_t i, len;
   Loc loc;
 } ClassParser;
 
 static int cp_peek(const ClassParser* p, size_t k) {
   return p->i + k < p->len ? (unsigned char)p->s[p->i + k] : 0;
 }
 static void cp_skip_ws(ClassParser* p) {
   while (p->i < p->len) {
     char c = p->s[p->i];
     if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == ',')
       p->i++;
     else
       break;
   }
 }
 
 /* atom = UPPERCASE symbol | lowercase set reference. (There is no literal
  * nested
  * `[ … ]`: the meta lexer's class token ends at the first `]`, exactly as in
  * the UTF-8 classes; compose with named %def sets instead.) */
 static RSet cp_atom(ClassParser* p) {
   cp_skip_ws(p);
   size_t start = p->i;
   while (p->i < p->len) {
     unsigned char d = (unsigned char)p->s[p->i];
     if ((d >= 'A' && d <= 'Z') || (d >= 'a' && d <= 'z') ||
         (d >= '0' && d <= '9') || d == '_')
       p->i++;
     else
       break;
   }
   if (p->i == start)
     kit_gram_error(p->st->ctx, p->loc, "invalid symbol in token set");
   char* name = intern_len(p->st->ctx, p->s + start, p->i - start);
   if (is_token_name(name)) return rset_single(p->st->ctx, name);
   int idx = machine_sets_find(p->st, name);
   if (idx < 0)
     kit_gram_error(p->st->ctx, p->loc, "unknown symbol set '%s'", name);
   return rset_copy(p->st->ctx, resolve_set(p->st, (size_t)idx));
 }
 
 /* union = atom+ : juxtaposition, stopping at `]`, `&&`, `--`, or end. */
 static RSet cp_union(ClassParser* p, int* saw) {
   RSet out = {0};
   *saw = 0;
   for (;;) {
     cp_skip_ws(p);
     int c = cp_peek(p, 0);
     if (!c || c == ']') break;
     if (c == '&' && cp_peek(p, 1) == '&') break;
     if (c == '-' && cp_peek(p, 1) == '-') break;
     RSet item = cp_atom(p);
     if (!*saw) {
       out = item;
       *saw = 1;
     } else {
       RSet u = rset_union(p->st->ctx, &out, &item);
       rset_free(p->st->ctx, &out);
       rset_free(p->st->ctx, &item);
       out = u;
     }
   }
   return out;
 }
 
 /* expr = union ( ('&&' | '--') union )* : intersection/difference, left to
  * right, both below union in precedence (matching the UTF-8 class parser). */
 static RSet cp_expr(ClassParser* p) {
   int saw;
   RSet out = cp_union(p, &saw);
   for (;;) {
     cp_skip_ws(p);
     int c = cp_peek(p, 0);
     int is_and = c == '&' && cp_peek(p, 1) == '&';
     int is_sub = c == '-' && cp_peek(p, 1) == '-';
     if (!is_and && !is_sub) break;
     p->i += 2;
     int saw_rhs;
     RSet rhs = cp_union(p, &saw_rhs);
     if (!saw_rhs)
       kit_gram_error(p->st->ctx, p->loc, "expected a symbol set after '%s'",
                     is_and ? "&&" : "--");
     RSet r = is_and ? rset_intersect(p->st->ctx, &out, &rhs)
                     : rset_diff(p->st->ctx, &out, &rhs);
     rset_free(p->st->ctx, &out);
     rset_free(p->st->ctx, &rhs);
     out = r;
   }
   return out;
 }
 
 static RSet cp_class(ClassParser* p) {
   cp_skip_ws(p);
   if (cp_peek(p, 0) != '[')
     kit_gram_error(p->st->ctx, p->loc, "malformed symbol set");
   p->i++; /* '[' */
   cp_skip_ws(p);
   int neg = 0;
   if (cp_peek(p, 0) == '^') {
     neg = 1;
     p->i++;
   }
   RSet r = cp_expr(p);
   cp_skip_ws(p);
   if (cp_peek(p, 0) != ']')
     kit_gram_error(p->st->ctx, p->loc, "malformed symbol set");
   p->i++; /* ']' */
   if (neg) r.complement = !r.complement;
   /* A positive class that resolves to nothing (e.g. `[ ]`, `[ A -- A ]`) is
    * empty; `[^ ]` is the universe and stays valid. */
   if (!r.complement && r.n == 0)
     kit_gram_error(p->st->ctx, p->loc, "empty symbol set");
   return r;
 }
 
 /* ---- %def-as-set resolution (the body AST, post-desugar) ----------------- */
 
 static RSet resolve_set_alt(MachineSets* st, const AstLexAlt* alt, Loc def_loc);
 
 static RSet resolve_set_atom(MachineSets* st, const AstLexNode* node,
                              Loc def_loc) {
   switch (node->kind) {
     case LEX_NAME:
       if (is_token_name(node->value.s))
         return rset_single(st->ctx, node->value.s);
       else {
         int idx = machine_sets_find(st, node->value.s);
         if (idx < 0)
           kit_gram_error(st->ctx, node->loc, "unknown symbol set '%s'",
                         node->value.s);
         return rset_copy(st->ctx, resolve_set(st, (size_t)idx));
       }
     case LEX_CLASS: {
       ClassParser p = {.st = st,
                        .s = node->value.s,
                        .i = 0,
                        .len = node->value.len,
                        .loc = node->loc};
       return cp_class(&p);
     }
     case LEX_GROUP: /* a parenthesized / desugared sub-union */
       return resolve_set_alt(st, node->alts, def_loc);
     default:
       kit_gram_error(st->ctx, node->loc,
                     "a set definition must be a union of symbols, sets, and "
                     "[ … ] classes");
       return (RSet){0}; /* unreachable */
   }
 }
 
 /* A set body is a union: each alternative (`|`) is a single set atom. */
 static RSet resolve_set_alt(MachineSets* st, const AstLexAlt* alt,
                             Loc def_loc) {
   RSet out = {0};
   int saw = 0;
   for (size_t i = 0; i < alt->nseqs; i++) {
     const AstLexSeq* seq = alt->seqs[i];
     if (seq->nitems != 1)
       kit_gram_error(
           st->ctx, def_loc,
           "a set definition must be a union of symbols and sets, not a "
           "sequence");
     RSet item = resolve_set_atom(st, seq->items[0], def_loc);
     if (!saw) {
       out = item;
       saw = 1;
     } else {
       RSet u = rset_union(st->ctx, &out, &item);
       rset_free(st->ctx, &out);
       rset_free(st->ctx, &item);
       out = u;
     }
   }
   return out;
 }
 
 static const RSet* resolve_set(MachineSets* st, size_t idx) {
   SetSlot* slot = &st->slots[idx];
   if (slot->state == 2) return &slot->set;
   if (slot->state == 1)
     kit_gram_error(st->ctx, st->defs[idx]->loc, "recursive set '%s'",
                   st->defs[idx]->name);
   slot->state = 1;
   slot->set = resolve_set_alt(st, st->defs[idx]->alts, st->defs[idx]->loc);
   slot->state = 2;
   return &slot->set;
 }
 
 /* Re-emit a class node's text as `[ … ]` / `[^ … ]` over its resolved members.
  */
 static void machine_class_rewrite(GramgenContext* ctx, AstLexNode* node,
                                   const RSet* r) {
   Buf b;
   buf_init(ctx, &b);
   buf_append(&b, r->complement ? "[^" : "[");
   for (size_t i = 0; i < r->n; i++) {
     buf_append(&b, " ");
     buf_append(&b, r->names[i]);
   }
   buf_append(&b, " ]");
   node->value = str_dup_len(ctx, b.s, b.len);
   xfree(ctx, b.s);
 }
 
 /* Resolve a class's set expression and re-emit it as plain symbol text. */
 static void machine_expand_class(MachineSets* st, AstLexNode* node) {
   ClassParser p = {.st = st,
                    .s = node->value.s,
                    .i = 0,
                    .len = node->value.len,
                    .loc = node->loc};
   RSet r = cp_class(&p);
   cp_skip_ws(&p);
   if (p.i != p.len)
     kit_gram_error(st->ctx, node->loc, "trailing characters in symbol set");
   machine_class_rewrite(st->ctx, node, &r);
   rset_free(st->ctx, &r);
 }
 
 static void machine_expand_alt(MachineSets* st, AstLexAlt* alt);
 
 static void machine_expand_node(MachineSets* st, AstLexNode* node) {
   switch (node->kind) {
     case LEX_CLASS:
       machine_expand_class(st, node);
       break;
     case LEX_GROUP:
     case LEX_OPT:
     case LEX_REP:
       machine_expand_alt(st, node->alts);
       break;
     default:
       break;
   }
 }
 
 static void machine_expand_alt(MachineSets* st, AstLexAlt* alt) {
   for (size_t i = 0; i < alt->nseqs; i++)
     for (size_t j = 0; j < alt->seqs[i]->nitems; j++)
       machine_expand_node(st, alt->seqs[i]->items[j]);
 }
 
 /* ---- compile ------------------------------------------------------------ */
 
 LexDFA* kit_gram_compile_machine(GramgenContext* ctx, const char* name,
                                 LexRecognizer* recognizers, size_t nrecognizers,
                                 AstLexLine** sets, size_t nsets, Loc loc) {
   if (!nrecognizers) kit_gram_error(ctx, loc, "%%machine %s has no rules", name);
   if (nrecognizers >= 65535)
     kit_gram_error(ctx, loc, "%%machine %s has too many rules", name);
 
   /* Pass 0: resolve each `[ … ]` set expression (algebra + %def set references)
    * and re-emit it as plain symbol text, so the alphabet pass, NFA leaves, and
    * samplers only ever see UPPERCASE symbols. */
   MachineSets st = {.ctx = ctx, .defs = sets, .ndefs = nsets};
   st.slots = nsets ? xcalloc(ctx, nsets, sizeof *st.slots) : NULL;
   for (size_t i = 0; i < nrecognizers; i++)
     machine_expand_alt(&st, recognizers[i].alts);
   for (size_t i = 0; i < nsets; i++) rset_free(ctx, &st.slots[i].set);
   xfree(ctx, st.slots);
 
   /* Pass 1: collect the symbol alphabet in first-use order. */
   TokenAlphabet alpha = {.ctx = ctx};
   for (size_t i = 0; i < nrecognizers; i++)
     token_collect_alt(ctx, &alpha, recognizers[i].alts);
   if (!alpha.n) kit_gram_error(ctx, loc, "%%machine %s has no symbols", name);
   if (alpha.n >= 65535)
     kit_gram_error(ctx, loc, "%%machine %s has too many symbols", name);
   uint16_t nsym = (uint16_t)alpha.n;
 
   /* Pass 2: one Thompson NFA over the symbol alphabet, accepts stamped per
    * recognizer (rule). No anchors -> all start contexts coincide at state 0. */
   TokenLeafCtx tctx = {.alpha = &alpha, .nsym = nsym};
   LexAlphabet token_alphabet = {
       .ud = &tctx,
       .exclude_surrogates = 0,
       .leaf_literal = token_leaf_invalid,
       .leaf_class = token_leaf_class,
       .leaf_prop = token_leaf_invalid,
       .leaf_any = token_leaf_any,
       .leaf_name = token_leaf_name,
   };
   ScalarNfaBuilder nfa = {.ctx = ctx};
   int start = scalar_nfa_new_state(&nfa);
   for (size_t i = 0; i < nrecognizers; i++) {
     NfaFrag frag =
         range_nfa_from_lex_alt(&nfa, &token_alphabet, recognizers[i].alts);
     scalar_nfa_eps(&nfa, start, frag.start);
     nfa.states[frag.end].accept = (int)i;
   }
 
   ScalarClasses sc = {0};
   uint16_t *trans = NULL, *accept = NULL, nstates = 0;
   AcceptSigMap sigmap = {0};
   uint16_t start_text = 0, start_line = 0;
   scalar_nfa_to_dfa(ctx, loc, &nfa, start, /*exclude_surrogates=*/0, &sc,
                     &trans, &accept, &nstates, &sigmap, &start_text,
                     &start_line);
 
   /* The atom DFA is the final DFA (symbol id == atom; no UTF-8 lowering).
    * Minimize + canonically relabel over the symbol classes. accept[] is the
    * opaque accept-signature key through both passes. */
   dfa_minimize(ctx, loc, &trans, &accept, &nstates, sc.nclasses, NULL, 0);
   dfa_canonical_relabel(ctx, trans, accept, nstates, sc.nclasses, NULL, 0, NULL,
                         0);
 
   /* Expand the per-state accept signature into the winning recognizer index
    * (the kind report). Token machines have no anchors, so only `plain` is set.
    */
   for (uint16_t s = 0; s < nstates; s++) {
     uint16_t sig = accept[s];
     accept[s] = (sig == UINT16_MAX) ? UINT16_MAX : sigmap.triples[sig].plain;
   }
 
   /* Dense symbol -> class map straight from the atom partition. */
   uint16_t* sym_class_of = xmalloc(ctx, (size_t)nsym * sizeof *sym_class_of);
   for (uint16_t c = 0; c < sc.nclasses; c++)
     for (uint32_t r = sc.off[c]; r < sc.off[c + 1]; r++)
       for (uint32_t v = sc.ranges[r].lo; v <= sc.ranges[r].hi; v++)
         sym_class_of[v] = c;
 
   uint8_t* live = token_compute_live(ctx, trans, accept, nstates, sc.nclasses);
 
   char** sym_names = xmalloc(ctx, (size_t)nsym * sizeof *sym_names);
   for (uint16_t i = 0; i < nsym; i++) sym_names[i] = alpha.names[i];
 
   LexDFA* dfa = xcalloc(ctx, 1, sizeof *dfa);
   if (!dfa) die_oom(ctx);
   dfa->name = (char*)name;
   dfa->loc = loc;
   dfa->recognizers = recognizers;
   dfa->nrecognizers = nrecognizers;
   dfa->input = KIT_GRAM_LEX_INPUT_TOKENS;
   dfa->is_machine = 1;
   dfa->nclasses = sc.nclasses;
   dfa->trans = trans;
   dfa->nstates = nstates;
   dfa->accept = accept;
   dfa->sym_class_of = sym_class_of;
   dfa->nsym = nsym;
   dfa->sym_names = sym_names;
   dfa->live = live;
 
   scalar_classes_free(ctx, &sc);
   accept_sig_map_free(ctx, &sigmap);
   xfree(ctx, alpha.names);
   xfree(ctx, alpha.index.keys);
   xfree(ctx, alpha.index.values);
   return dfa;
 }
 
 /* ---- in-memory AST-directed sampler ------------------------------------- */
 /* Mirror of the emitted gen_* sampler (same PRNG, same stop-coin), so the CLI's
  * --sample-traces prints exactly what the generated code would produce for a
  * given seed. Produces symbol-name pointers (into the machine's sym_names). */
 
 typedef struct {
   GramgenContext* ctx;
   const char** out;
   size_t cap, n, max_tokens, max_repeat;
   uint64_t rng;
   double stop_prob;
   int limit;
   char* const* sym_names;
   uint16_t nsym;
 } MachineSampler;
 
 static uint64_t ms_rng_next(uint64_t* s) {
   *s = *s * 6364136223846793005ull + 1442695040888963407ull;
   uint64_t x = *s;
   x ^= x >> 33;
   x *= 0xff51afd7ed558ccdull;
   x ^= x >> 33;
   return x;
 }
 static int ms_coin(MachineSampler* s) {
   uint64_t r = ms_rng_next(&s->rng);
   double u = (double)(r >> 11) * (1.0 / 9007199254740992.0);
   return u >= s->stop_prob;
 }
 static void ms_emit(MachineSampler* s, const char* name) {
   if (s->n >= s->max_tokens) {
     s->limit = 1;
     return;
   }
   if (s->n < s->cap) s->out[s->n] = name;
   s->n++;
 }
 
 static void ms_alt(MachineSampler* s, const AstLexAlt* alt);
 
 static void ms_node(MachineSampler* s, const AstLexNode* node) {
   switch (node->kind) {
     case LEX_NAME:
       ms_emit(s, node->value.s);
       break;
     case LEX_ANY: {
       uint64_t r = ms_rng_next(&s->rng);
       ms_emit(s, s->sym_names[r % s->nsym]);
       break;
     }
     case LEX_CLASS: {
       size_t nm = 0;
       int comp = 0;
       char* const* names = kit_gram_machine_class_names(s->ctx, node->value,
                                                        node->loc, &nm, &comp);
       /* Resolve to machine-owned sym_names pointers (the parsed names live in a
        * scratch arena). Member order matches the emitted sampler: declaration
        * order for an enumerated set, symbol-id order for a complement. */
       const char** mem = xmalloc(s->ctx, (size_t)s->nsym * sizeof *mem);
       size_t k = 0;
       if (!comp) {
         for (size_t j = 0; j < nm; j++)
           for (uint16_t si = 0; si < s->nsym; si++)
             if (strcmp(s->sym_names[si], names[j]) == 0) {
               mem[k++] = s->sym_names[si];
               break;
             }
       } else {
         for (uint16_t si = 0; si < s->nsym; si++) {
           int in = 0;
           for (size_t j = 0; j < nm; j++)
             if (strcmp(s->sym_names[si], names[j]) == 0) {
               in = 1;
               break;
             }
           if (!in) mem[k++] = s->sym_names[si];
         }
       }
       if (k) {
         uint64_t r = ms_rng_next(&s->rng);
         ms_emit(s, mem[r % k]);
       }
       xfree(s->ctx, mem);
       xfree(s->ctx, (void*)names);
       break;
     }
     case LEX_GROUP:
       ms_alt(s, node->alts);
       break;
     case LEX_OPT:
       if (ms_coin(s)) ms_alt(s, node->alts);
       break;
     case LEX_REP:
       for (size_t i = 0; i < s->max_repeat && ms_coin(s); i++)
         ms_alt(s, node->alts);
       break;
     default:
       break;
   }
 }
 
 static void ms_seq(MachineSampler* s, const AstLexSeq* seq) {
   for (size_t i = 0; i < seq->nitems; i++) ms_node(s, seq->items[i]);
 }
 
 static void ms_alt(MachineSampler* s, const AstLexAlt* alt) {
   if (alt->nseqs == 1) {
     ms_seq(s, alt->seqs[0]);
     return;
   }
   uint64_t r = ms_rng_next(&s->rng);
   ms_seq(s, alt->seqs[r % alt->nseqs]);
 }
 
 KitGramGenStatus kit_gram_machine_sample(GramgenContext* ctx, const LexDFA* m,
                                        size_t which, uint64_t* seed,
                                        double stop_prob, size_t max_repeat,
                                        size_t max_tokens, const char** out,
                                        size_t cap, size_t* n) {
   MachineSampler s = {
       .ctx = ctx,
       .out = out,
       .cap = cap,
       .n = 0,
       .max_tokens = max_tokens,
       .max_repeat = max_repeat,
       .rng = *seed,
       .stop_prob = stop_prob,
       .limit = 0,
       .sym_names = m->sym_names,
       .nsym = m->nsym,
   };
   if (which < m->nrecognizers) ms_alt(&s, m->recognizers[which].alts);
   *seed = s.rng;
   if (n) *n = s.n;
   return s.limit ? KIT_GRAM_GEN_LIMIT : KIT_GRAM_GEN_DONE;
 }