lex_scalar.c (28517B)
1 /* kit_gram_lex_scalar.c - utf8 scalar lexer pipeline: scalar NFA, scalar 2 * determinization, and the joint per-state UTF-8 trie lowering to a byte 3 * DFA. Excluded from the build under KIT_GRAM_NO_UNICODE. */ 4 #include "internal.h" 5 6 typedef struct { 7 unsigned char lo[4], hi[4]; 8 int n; 9 } Utf8Seq; 10 11 /* A UTF-8 byte sequence (with per-position [lo,hi] byte ranges) tagged with the 12 * byte-DFA entry state it leads to. The joint-trie lowering collects these for 13 * all of a scalar state's outgoing edges, then splits them deterministically. 14 */ 15 typedef struct { 16 Utf8Seq seq; 17 uint16_t target; 18 } TrieItem; 19 20 typedef struct { 21 GramgenContext* ctx; 22 TrieItem* items; 23 size_t n, cap; 24 uint16_t target; /* applied to items appended while collecting one edge */ 25 } TrieItemSink; 26 27 static void trie_item_append(TrieItemSink* sink, const Utf8Seq* seq) { 28 if (sink->n == sink->cap) { 29 sink->cap = sink->cap ? sink->cap * 2 : 16; 30 sink->items = 31 xrealloc(sink->ctx, sink->items, sink->cap * sizeof *sink->items); 32 } 33 sink->items[sink->n].seq = *seq; 34 sink->items[sink->n].target = sink->target; 35 sink->n++; 36 } 37 38 typedef struct { 39 int n; 40 TrieItemSink* sink; /* collects the trie items for one scalar edge */ 41 unsigned char bases[4]; 42 unsigned char max_digits[4]; 43 } Utf8RangeCtx; 44 45 static void utf8_emit_seq(Utf8RangeCtx* ctx, const Utf8Seq* seq) { 46 trie_item_append(ctx->sink, seq); 47 } 48 49 static void utf8_emit_full(Utf8RangeCtx* ctx, int pos, Utf8Seq seq) { 50 for (int i = pos; i < ctx->n; i++) { 51 seq.lo[i] = ctx->bases[i]; 52 seq.hi[i] = (unsigned char)(ctx->bases[i] | ctx->max_digits[i]); 53 } 54 seq.n = ctx->n; 55 utf8_emit_seq(ctx, &seq); 56 } 57 58 static void utf8_range_recur(Utf8RangeCtx* ctx, const unsigned char* lo_digits, 59 const unsigned char* hi_digits, int pos, 60 Utf8Seq seq) { 61 if (pos == ctx->n) { 62 seq.n = ctx->n; 63 utf8_emit_seq(ctx, &seq); 64 return; 65 } 66 unsigned char lo = lo_digits[pos]; 67 unsigned char hi = hi_digits[pos]; 68 unsigned char base = ctx->bases[pos]; 69 if (lo == hi) { 70 seq.lo[pos] = (unsigned char)(base | lo); 71 seq.hi[pos] = (unsigned char)(base | lo); 72 utf8_range_recur(ctx, lo_digits, hi_digits, pos + 1, seq); 73 return; 74 } 75 76 unsigned char first_hi[4]; 77 memcpy(first_hi, lo_digits, sizeof first_hi); 78 first_hi[pos] = lo; 79 for (int i = pos + 1; i < ctx->n; i++) first_hi[i] = ctx->max_digits[i]; 80 seq.lo[pos] = (unsigned char)(base | lo); 81 seq.hi[pos] = (unsigned char)(base | lo); 82 utf8_range_recur(ctx, lo_digits, first_hi, pos + 1, seq); 83 84 if ((unsigned)lo + 1u <= (unsigned)hi - 1u) { 85 Utf8Seq mid = seq; 86 mid.lo[pos] = (unsigned char)(base | (lo + 1)); 87 mid.hi[pos] = (unsigned char)(base | (hi - 1)); 88 utf8_emit_full(ctx, pos + 1, mid); 89 } 90 91 unsigned char last_lo[4]; 92 memcpy(last_lo, hi_digits, sizeof last_lo); 93 last_lo[pos] = hi; 94 for (int i = pos + 1; i < ctx->n; i++) last_lo[i] = 0; 95 seq.lo[pos] = (unsigned char)(base | hi); 96 seq.hi[pos] = (unsigned char)(base | hi); 97 utf8_range_recur(ctx, last_lo, hi_digits, pos + 1, seq); 98 } 99 100 static void utf8_digits_for(uint32_t cp, const unsigned char* widths, int n, 101 unsigned char* out) { 102 for (int i = n - 1; i >= 0; i--) { 103 uint32_t mask = ((uint32_t)1 << widths[i]) - 1u; 104 out[i] = (unsigned char)(cp & mask); 105 cp >>= widths[i]; 106 } 107 } 108 109 static const unsigned char utf8_widths_by_len[5][4] = { 110 {0}, {7}, {5, 6}, {4, 6, 6}, {3, 6, 6, 6}, 111 }; 112 static const unsigned char utf8_bases_by_len[5][4] = { 113 {0}, {0x00}, {0xC0, 0x80}, {0xE0, 0x80, 0x80}, {0xF0, 0x80, 0x80, 0x80}, 114 }; 115 116 /* Decompose one same-length scalar sub-range [lo,hi] into UTF-8 byte sequences 117 * and dispatch each through ctx (NFA fragment or trie-item collection). */ 118 static void utf8_range_emit_len(Utf8RangeCtx* ctx, uint32_t lo, uint32_t hi, 119 int nbytes) { 120 ctx->n = nbytes; 121 for (int i = 0; i < nbytes; i++) { 122 ctx->bases[i] = utf8_bases_by_len[nbytes][i]; 123 ctx->max_digits[i] = 124 (unsigned char)(((unsigned)1 << utf8_widths_by_len[nbytes][i]) - 1u); 125 } 126 unsigned char lo_digits[4] = {0}, hi_digits[4] = {0}; 127 utf8_digits_for(lo, utf8_widths_by_len[nbytes], nbytes, lo_digits); 128 utf8_digits_for(hi, utf8_widths_by_len[nbytes], nbytes, hi_digits); 129 Utf8Seq seq = {0}; 130 utf8_range_recur(ctx, lo_digits, hi_digits, 0, seq); 131 } 132 133 /* Split a scalar range at UTF-8 length boundaries (and the surrogate gap) and 134 * decompose each piece. */ 135 static void utf8_range_emit(Utf8RangeCtx* ctx, uint32_t lo, uint32_t hi) { 136 static const struct { 137 uint32_t lo, hi; 138 int nbytes; 139 } limits[] = { 140 {0x0000u, 0x007Fu, 1}, 141 {0x0080u, 0x07FFu, 2}, 142 {0x0800u, 0xD7FFu, 3}, 143 {0xE000u, 0xFFFFu, 3}, 144 {0x10000u, UNICODE_MAX_SCALAR, 4}, 145 }; 146 for (size_t i = 0; i < sizeof limits / sizeof limits[0]; i++) { 147 uint32_t part_lo = lo > limits[i].lo ? lo : limits[i].lo; 148 uint32_t part_hi = hi < limits[i].hi ? hi : limits[i].hi; 149 if (part_lo <= part_hi) 150 utf8_range_emit_len(ctx, part_lo, part_hi, limits[i].nbytes); 151 } 152 } 153 154 /* Collect the UTF-8 byte sequences of scalar range [lo,hi] as trie items that 155 * all lead to byte-DFA entry state `target`. */ 156 static void utf8_collect_range(TrieItemSink* sink, uint16_t target, uint32_t lo, 157 uint32_t hi) { 158 sink->target = target; 159 Utf8RangeCtx ctx = {.sink = sink}; 160 utf8_range_emit(&ctx, lo, hi); 161 } 162 163 /* UTF-8 literal leaf: one scalar edge per decoded code point. Stays in the 164 * scalar TU (the combinators it threads are the shared range core). */ 165 static NfaFrag scalar_nfa_literal(ScalarNfaBuilder* nfa, Str s, Loc loc) { 166 if (!s.len) return scalar_nfa_empty(nfa); 167 int start = scalar_nfa_new_state(nfa); 168 int cur = start; 169 size_t i = 0; 170 while (i < s.len) { 171 uint32_t cp = 0; 172 size_t nbytes = 0; 173 KitGramUtf8Status st = kit_gram_utf8_decode_one((const unsigned char*)s.s + i, 174 s.len - i, &cp, &nbytes); 175 if (st != KIT_GRAM_UTF8_OK) 176 kit_gram_error(nfa->ctx, loc, "invalid UTF-8 in Unicode lexer literal"); 177 int nxt = scalar_nfa_new_state(nfa); 178 scalar_nfa_edge(nfa, cur, scalar_set_from_single_value(nfa->ctx, cp), nxt, 179 loc); 180 cur = nxt; 181 i += nbytes; 182 } 183 return (NfaFrag){start, cur}; 184 } 185 186 /* The utf8 scalar alphabet: Unicode leaves over the shared range core. A bare 187 * NAME never reaches here (it is a %def reference inlined by desugaring, or an 188 * error); leaf_name preserves the old "not desugared" internal error. */ 189 static NfaFrag scalar_leaf_literal(ScalarNfaBuilder* nfa, const LexAlphabet* a, 190 AstLexNode* node) { 191 (void)a; 192 return scalar_nfa_literal(nfa, node->scalar_value, node->loc); 193 } 194 static NfaFrag scalar_leaf_class(ScalarNfaBuilder* nfa, const LexAlphabet* a, 195 AstLexNode* node) { 196 (void)a; 197 return scalar_nfa_scalar_set( 198 nfa, kit_gram_unicode_char_class_set(nfa->ctx, node->value, node->loc), 199 node->loc); 200 } 201 static NfaFrag scalar_leaf_prop(ScalarNfaBuilder* nfa, const LexAlphabet* a, 202 AstLexNode* node) { 203 (void)a; 204 return scalar_nfa_scalar_set( 205 nfa, kit_gram_unicode_prop_atom_set(nfa->ctx, node->value, node->loc), 206 node->loc); 207 } 208 static NfaFrag scalar_leaf_any(ScalarNfaBuilder* nfa, const LexAlphabet* a, 209 AstLexNode* node) { 210 (void)a; 211 return scalar_nfa_scalar_set(nfa, kit_gram_scalar_set_universe(nfa->ctx), 212 node->loc); 213 } 214 static NfaFrag scalar_leaf_name(ScalarNfaBuilder* nfa, const LexAlphabet* a, 215 AstLexNode* node) { 216 (void)a; 217 kit_gram_error(nfa->ctx, node->loc, "internal: lex node not desugared"); 218 return scalar_nfa_empty(nfa); 219 } 220 221 static const LexAlphabet scalar_alphabet = { 222 .ud = NULL, 223 .exclude_surrogates = 1, 224 .leaf_literal = scalar_leaf_literal, 225 .leaf_class = scalar_leaf_class, 226 .leaf_prop = scalar_leaf_prop, 227 .leaf_any = scalar_leaf_any, 228 .leaf_name = scalar_leaf_name, 229 }; 230 231 /* Direct, deterministic lowering of a scalar DFA to a byte DFA via a joint 232 * per-state UTF-8 trie. Replaces "lower each edge to a byte NFA, then run a 233 * second subset construction": within a scalar state the outgoing atom edges 234 * are disjoint scalar ranges, so their UTF-8 encodings can be split jointly at 235 * each byte position into disjoint byte intervals -- producing a DFA directly, 236 * with no nondeterminism to resolve. */ 237 typedef struct { 238 GramgenContext* ctx; 239 Loc loc; 240 uint16_t* trans; /* 256-wide rows; UINT16_MAX = dead */ 241 uint16_t* accept; /* UINT16_MAX = non-accepting */ 242 size_t nstates, cap; 243 } ByteDfaBuilder; 244 245 static uint16_t byte_dfa_new_state(ByteDfaBuilder* bd) { 246 if (bd->nstates >= 65535) 247 kit_gram_error(bd->ctx, bd->loc, "too many lexer DFA states"); 248 if (bd->nstates == bd->cap) { 249 bd->cap = bd->cap ? bd->cap * 2 : 64; 250 bd->trans = xrealloc(bd->ctx, bd->trans, bd->cap * 256 * sizeof *bd->trans); 251 bd->accept = xrealloc(bd->ctx, bd->accept, bd->cap * sizeof *bd->accept); 252 } 253 uint16_t s = (uint16_t)bd->nstates++; 254 uint16_t* row = &bd->trans[(size_t)s * 256]; 255 for (int b = 0; b < 256; b++) row[b] = UINT16_MAX; 256 bd->accept[s] = UINT16_MAX; 257 return s; 258 } 259 260 static int u16_cmp(const void* a, const void* b) { 261 uint16_t x = *(const uint16_t*)a, y = *(const uint16_t*)b; 262 return (x > y) - (x < y); 263 } 264 265 /* Build the deterministic byte trie for `items` at byte position `pos`, rooted 266 * at byte-DFA state `node`. All items share the consumed byte prefix and, for 267 * pos > 0, the same encoded length (UTF-8 lead bytes separate the lengths at 268 * pos 0). The current byte position is split into maximal intervals whose 269 * covering item set is constant; each interval becomes one byte transition -- 270 * to the target entry state at the final byte, or to a fresh child otherwise. 271 * Disjoint scalar ranges guarantee at most one covering item at a final byte, 272 * so transitions are deterministic. */ 273 /* Structural hash-cons of interior trie nodes (re2-style UTF-8 suffix cache). 274 * A node's subtree is fully determined by (relative position, the set of item 275 * suffixes from here on). Keying interior nodes by that structure shares 276 * identical subtrees -- crucially the universal [80-BF] continuation tails and 277 * any equal target sub-tries -- across every scalar state, so the byte DFA fed 278 * to minimization is already small. The key uses positions *relative* to the 279 * node (suffix length), so e.g. a [80-BF]->[80-BF]->target tail is one node 280 * regardless of the lead length that reaches it. */ 281 typedef struct { 282 size_t off; 283 uint32_t len; 284 uint64_t hash; 285 uint16_t state; 286 int next; 287 } TrieCacheEnt; 288 289 typedef struct { 290 GramgenContext* ctx; 291 uint16_t* blob; 292 size_t blob_n, blob_cap; 293 TrieCacheEnt* ent; 294 size_t nent, ent_cap; 295 int* buckets; 296 size_t nbuckets; 297 } TrieCache; 298 299 static void trie_cache_init(GramgenContext* ctx, TrieCache* c) { 300 memset(c, 0, sizeof *c); 301 c->ctx = ctx; 302 c->nbuckets = 1024; 303 c->buckets = xmalloc(ctx, c->nbuckets * sizeof *c->buckets); 304 for (size_t i = 0; i < c->nbuckets; i++) c->buckets[i] = -1; 305 } 306 307 static void trie_cache_free(TrieCache* c) { 308 xfree(c->ctx, c->blob); 309 xfree(c->ctx, c->ent); 310 xfree(c->ctx, c->buckets); 311 } 312 313 static int trie_cache_get(const TrieCache* c, const uint16_t* toks, 314 uint32_t len, uint64_t hash) { 315 size_t bk = (size_t)(hash & (uint64_t)(c->nbuckets - 1)); 316 for (int i = c->buckets[bk]; i >= 0; i = c->ent[i].next) { 317 if (c->ent[i].hash == hash && c->ent[i].len == len && 318 memcmp(c->blob + c->ent[i].off, toks, (size_t)len * sizeof *toks) == 0) 319 return (int)c->ent[i].state; 320 } 321 return -1; 322 } 323 324 static void trie_cache_put(TrieCache* c, const uint16_t* toks, uint32_t len, 325 uint64_t hash, uint16_t state) { 326 if ((c->nent + 1) * 2 > c->nbuckets) { 327 size_t nb = c->nbuckets * 2; 328 int* b = xmalloc(c->ctx, nb * sizeof *b); 329 for (size_t i = 0; i < nb; i++) b[i] = -1; 330 for (size_t i = 0; i < c->nent; i++) { 331 size_t bk = (size_t)(c->ent[i].hash & (uint64_t)(nb - 1)); 332 c->ent[i].next = b[bk]; 333 b[bk] = (int)i; 334 } 335 xfree(c->ctx, c->buckets); 336 c->buckets = b; 337 c->nbuckets = nb; 338 } 339 if (c->blob_n + len > c->blob_cap) { 340 c->blob_cap = c->blob_cap ? c->blob_cap * 2 : 1024; 341 while (c->blob_cap < c->blob_n + len) c->blob_cap *= 2; 342 c->blob = xrealloc(c->ctx, c->blob, c->blob_cap * sizeof *c->blob); 343 } 344 size_t off = c->blob_n; 345 memcpy(c->blob + off, toks, (size_t)len * sizeof *toks); 346 c->blob_n += len; 347 if (c->nent == c->ent_cap) { 348 c->ent_cap = c->ent_cap ? c->ent_cap * 2 : 64; 349 c->ent = xrealloc(c->ctx, c->ent, c->ent_cap * sizeof *c->ent); 350 } 351 size_t bk = (size_t)(hash & (uint64_t)(c->nbuckets - 1)); 352 c->ent[c->nent] = (TrieCacheEnt){off, len, hash, state, c->buckets[bk]}; 353 c->buckets[bk] = (int)c->nent; 354 c->nent++; 355 } 356 357 /* Serialized lookup key for one item at a node: (suffix length, target, 358 * lo/hi for each remaining byte position). Positions are relative, so the key 359 * is independent of how deep the node sits. */ 360 typedef struct { 361 uint16_t v[10]; 362 int len; 363 } TrieItemKey; 364 365 static void trie_item_key(const TrieItem* it, int pos, TrieItemKey* k) { 366 int j = 0; 367 k->v[j++] = (uint16_t)(it->seq.n - pos); 368 k->v[j++] = it->target; 369 for (int p = pos; p < it->seq.n; p++) { 370 k->v[j++] = it->seq.lo[p]; 371 k->v[j++] = it->seq.hi[p]; 372 } 373 k->len = j; 374 } 375 376 static int trie_item_key_cmp(const void* a, const void* b) { 377 const TrieItemKey *x = a, *y = b; 378 int n = x->len < y->len ? x->len : y->len; 379 for (int i = 0; i < n; i++) 380 if (x->v[i] != y->v[i]) return x->v[i] < y->v[i] ? -1 : 1; 381 return (x->len > y->len) - (x->len < y->len); 382 } 383 384 static void byte_trie_fill(ByteDfaBuilder* bd, TrieCache* cache, uint16_t node, 385 int pos, const TrieItem* items, size_t nitems); 386 387 /* Return (creating if needed) the cached interior byte-DFA state for the trie 388 * node at `pos` covering `items`. */ 389 static uint16_t trie_child(ByteDfaBuilder* bd, TrieCache* cache, int pos, 390 const TrieItem* items, size_t nitems) { 391 TrieItemKey* keys = xmalloc(bd->ctx, nitems * sizeof *keys); 392 for (size_t i = 0; i < nitems; i++) trie_item_key(&items[i], pos, &keys[i]); 393 qsort(keys, nitems, sizeof *keys, trie_item_key_cmp); 394 uint32_t ntoks = 0; 395 for (size_t i = 0; i < nitems; i++) ntoks += (uint32_t)keys[i].len; 396 uint16_t* toks = xmalloc(bd->ctx, (ntoks ? ntoks : 1) * sizeof *toks); 397 uint32_t t = 0; 398 uint64_t hash = 1469598103934665603ull; 399 for (size_t i = 0; i < nitems; i++) 400 for (int j = 0; j < keys[i].len; j++) { 401 toks[t++] = keys[i].v[j]; 402 hash = (hash ^ keys[i].v[j]) * 1099511628211ull; 403 } 404 xfree(bd->ctx, keys); 405 406 int found = trie_cache_get(cache, toks, ntoks, hash); 407 if (found >= 0) { 408 xfree(bd->ctx, toks); 409 return (uint16_t)found; 410 } 411 uint16_t s = byte_dfa_new_state(bd); 412 byte_trie_fill(bd, cache, s, pos, items, nitems); 413 trie_cache_put(cache, toks, ntoks, hash, s); 414 xfree(bd->ctx, toks); 415 return s; 416 } 417 418 /* Set node's transitions by splitting byte position `pos` into maximal 419 * constant-cover intervals. A final-byte interval maps to the target entry 420 * state; an interior interval maps to a (shared) child node. */ 421 static void byte_trie_fill(ByteDfaBuilder* bd, TrieCache* cache, uint16_t node, 422 int pos, const TrieItem* items, size_t nitems) { 423 uint16_t* bounds = xmalloc(bd->ctx, 2 * nitems * sizeof *bounds); 424 size_t nb = 0; 425 for (size_t i = 0; i < nitems; i++) { 426 bounds[nb++] = items[i].seq.lo[pos]; 427 bounds[nb++] = (uint16_t)(items[i].seq.hi[pos] + 1u); 428 } 429 qsort(bounds, nb, sizeof *bounds, u16_cmp); 430 size_t nbnd = 0; 431 for (size_t i = 0; i < nb; i++) 432 if (!nbnd || bounds[i] != bounds[nbnd - 1]) bounds[nbnd++] = bounds[i]; 433 434 TrieItem* sub = xmalloc(bd->ctx, nitems * sizeof *sub); 435 for (size_t k = 0; k + 1 < nbnd; k++) { 436 unsigned a = bounds[k]; 437 unsigned b = 438 (unsigned)bounds[k + 1] - 1u; /* inclusive [a,b], all <= 0xFF */ 439 size_t nsub = 0; 440 int is_leaf = 0; 441 for (size_t i = 0; i < nitems; i++) { 442 if (items[i].seq.lo[pos] <= a && a <= items[i].seq.hi[pos]) { 443 sub[nsub++] = items[i]; 444 is_leaf = items[i].seq.n - 1 == pos; 445 } 446 } 447 if (!nsub) continue; /* gap -> dead */ 448 uint16_t dest = is_leaf 449 ? sub[0].target /* disjoint scalars => unique target */ 450 : trie_child(bd, cache, pos + 1, sub, nsub); 451 uint16_t* row = 452 &bd->trans[(size_t)node * 256]; /* refetch: realloc may move */ 453 for (unsigned bb = a; bb <= b; bb++) row[bb] = dest; 454 } 455 xfree(bd->ctx, sub); 456 xfree(bd->ctx, bounds); 457 } 458 459 /* Lower the scalar DFA into a 256-column byte DFA: byte state `s` (for 460 * s < scalar_nstates) is the entry point of scalar state `s`, carrying its 461 * accept value; trie interior nodes are appended afterwards. */ 462 static void lower_scalar_dfa_to_byte_dfa( 463 GramgenContext* ctx, Loc loc, const ScalarClasses* sc, 464 const uint16_t* scalar_trans, const uint16_t* scalar_accept, 465 uint16_t scalar_nstates, uint16_t** trans_out, uint16_t** accept_out, 466 uint16_t* nstates_out) { 467 ByteDfaBuilder bd = {.ctx = ctx, .loc = loc}; 468 for (uint16_t s = 0; s < scalar_nstates; s++) { 469 byte_dfa_new_state(&bd); 470 bd.accept[s] = scalar_accept[s]; 471 } 472 TrieCache cache; 473 trie_cache_init(ctx, &cache); 474 TrieItemSink sink = {.ctx = ctx}; 475 for (uint16_t s = 0; s < scalar_nstates; s++) { 476 sink.n = 0; 477 const uint16_t* srow = &scalar_trans[(size_t)s * sc->nclasses]; 478 for (uint16_t cls = 0; cls < sc->nclasses; cls++) { 479 if (srow[cls] == UINT16_MAX) 480 continue; /* dead <=> all the class's atoms dead */ 481 for (uint32_t r = sc->off[cls]; r < sc->off[cls + 1]; r++) 482 utf8_collect_range(&sink, srow[cls], sc->ranges[r].lo, 483 sc->ranges[r].hi); 484 } 485 if (sink.n) byte_trie_fill(&bd, &cache, s, 0, sink.items, sink.n); 486 } 487 xfree(ctx, sink.items); 488 trie_cache_free(&cache); 489 *trans_out = bd.trans; 490 *accept_out = bd.accept; 491 *nstates_out = (uint16_t)bd.nstates; 492 } 493 494 /* Partition the columns of a row-major nrows x ncols matrix by whole-column 495 * equality, numbering groups by ascending index of first occurrence. Visiting 496 * columns in ascending order yields canonical "by smallest member" numbering. 497 * Fills group_of[ncols]; returns the group count. */ 498 static uint16_t group_columns(GramgenContext* ctx, Loc loc, const uint16_t* m, 499 size_t nrows, size_t ncols, uint16_t* group_of) { 500 size_t nbuckets = 1024; 501 while (nbuckets < ncols * 2) nbuckets *= 2; 502 int* buckets = xmalloc(ctx, nbuckets * sizeof *buckets); 503 int* next = xmalloc(ctx, (ncols ? ncols : 1) * sizeof *next); 504 int* rep = xmalloc(ctx, (ncols ? ncols : 1) * sizeof *rep); 505 uint64_t* gh = xmalloc(ctx, (ncols ? ncols : 1) * sizeof *gh); 506 for (size_t i = 0; i < nbuckets; i++) buckets[i] = -1; 507 uint16_t ngroups = 0; 508 for (size_t c = 0; c < ncols; c++) { 509 uint64_t h = 1469598103934665603ull; 510 for (size_t r = 0; r < nrows; r++) 511 h = (h ^ (uint64_t)m[r * ncols + c]) * 1099511628211ull; 512 size_t bk = (size_t)(h & (uint64_t)(nbuckets - 1)); 513 int g = -1; 514 for (int i = buckets[bk]; i >= 0; i = next[i]) { 515 if (gh[i] != h) continue; 516 size_t rc = (size_t)rep[i]; 517 int eq = 1; 518 for (size_t r = 0; r < nrows; r++) 519 if (m[r * ncols + c] != m[r * ncols + rc]) { 520 eq = 0; 521 break; 522 } 523 if (eq) { 524 g = i; 525 break; 526 } 527 } 528 if (g < 0) { 529 if (ngroups >= 256) 530 kit_gram_error(ctx, loc, "too many lexer byte classes"); 531 g = ngroups++; 532 rep[g] = (int)c; 533 gh[g] = h; 534 next[g] = buckets[bk]; 535 buckets[bk] = g; 536 } 537 group_of[c] = (uint16_t)g; 538 } 539 xfree(ctx, buckets); 540 xfree(ctx, next); 541 xfree(ctx, rep); 542 xfree(ctx, gh); 543 return ngroups; 544 } 545 546 /* Byte classes straight from the lowered 256-column byte DFA: two bytes share a 547 * class iff every state transitions identically on them. This fuses byte-class 548 * derivation with the lowering (the trie's per-position splits are exactly the 549 * boundaries) -- no equivalence scan over a byte NFA. */ 550 static uint16_t* dfa_byte_classes_from_table(GramgenContext* ctx, Loc loc, 551 const uint16_t* trans256, 552 size_t nstates, 553 uint8_t class_of[256], 554 uint16_t* nclasses_out) { 555 uint16_t group_of[256]; 556 uint16_t ncls = group_columns(ctx, loc, trans256, nstates, 256, group_of); 557 int rep_byte[256]; 558 for (int c = 0; c < ncls; c++) rep_byte[c] = -1; 559 for (int b = 0; b < 256; b++) { 560 class_of[b] = (uint8_t)group_of[b]; 561 if (rep_byte[group_of[b]] < 0) rep_byte[group_of[b]] = b; 562 } 563 uint16_t* trans = xmalloc(ctx, nstates * (size_t)ncls * sizeof *trans); 564 for (size_t s = 0; s < nstates; s++) 565 for (uint16_t c = 0; c < ncls; c++) 566 trans[s * (size_t)ncls + c] = trans256[s * 256 + (size_t)rep_byte[c]]; 567 *nclasses_out = ncls; 568 return trans; 569 } 570 571 /* Recompute byte classes after minimization by merging pre-min classes whose 572 * columns became identical in the minimized DFA, without the 256-column 573 * expand/recompact round-trip. Pre-min classes are already ordered by smallest 574 * member byte, so numbering groups by ascending pre-min class keeps class_of 575 * canonical. */ 576 static uint16_t* dfa_recompact_after_min(GramgenContext* ctx, Loc loc, 577 const uint16_t* trans, size_t nstates, 578 uint16_t nclasses_in, 579 uint8_t class_of[256], 580 uint16_t* nclasses_out) { 581 uint16_t* group_of = xmalloc(ctx, (size_t)nclasses_in * sizeof *group_of); 582 uint16_t ncls = 583 group_columns(ctx, loc, trans, nstates, nclasses_in, group_of); 584 int rep_cls[256]; 585 for (int g = 0; g < ncls; g++) rep_cls[g] = -1; 586 for (uint16_t c = 0; c < nclasses_in; c++) 587 if (rep_cls[group_of[c]] < 0) rep_cls[group_of[c]] = c; 588 for (int b = 0; b < 256; b++) class_of[b] = (uint8_t)group_of[class_of[b]]; 589 uint16_t* out = xmalloc(ctx, nstates * (size_t)ncls * sizeof *out); 590 for (size_t s = 0; s < nstates; s++) 591 for (uint16_t g = 0; g < ncls; g++) 592 out[s * (size_t)ncls + g] = 593 trans[s * (size_t)nclasses_in + (size_t)rep_cls[g]]; 594 xfree(ctx, group_of); 595 *nclasses_out = ncls; 596 return out; 597 } 598 599 /* Full UTF-8 lexer table build from a scalar DFA: direct byte-DFA lowering, 600 * one minimization, byte-class derivation, and canonical relabeling -- the 601 * single-determinization replacement for compose_utf8_byte_nfa + 602 * byte_nfa_to_tables. */ 603 static void scalar_dfa_to_byte_tables( 604 GramgenContext* ctx, Loc loc, const ScalarClasses* sc, 605 const uint16_t* scalar_trans, const uint16_t* scalar_accept, 606 uint16_t scalar_nstates, const AcceptSigMap* sigmap, uint8_t class_of[256], 607 uint16_t* nclasses_out, uint16_t** trans_out, uint16_t* nstates_out, 608 uint16_t** accept_out, uint16_t** accept_text_out, 609 uint16_t** accept_line_out, uint16_t* start_text, uint16_t* start_line) { 610 uint16_t *byte_trans = NULL, *accept = NULL, nstates = 0; 611 lower_scalar_dfa_to_byte_dfa(ctx, loc, sc, scalar_trans, scalar_accept, 612 scalar_nstates, &byte_trans, &accept, &nstates); 613 614 uint16_t nclasses = 0; 615 uint16_t* trans = dfa_byte_classes_from_table(ctx, loc, byte_trans, nstates, 616 class_of, &nclasses); 617 xfree(ctx, byte_trans); 618 619 /* Scalar entry states map 1:1 to byte states 0..scalar_nstates-1, so the 620 * start ids carry over; remap them through minimization and relabeling. */ 621 uint16_t starts[2] = {*start_line, *start_text}; 622 dfa_minimize(ctx, loc, &trans, &accept, &nstates, nclasses, starts, 2); 623 624 uint16_t final_nclasses = 0; 625 uint16_t* ftrans = dfa_recompact_after_min(ctx, loc, trans, nstates, nclasses, 626 class_of, &final_nclasses); 627 xfree(ctx, trans); 628 trans = ftrans; 629 nclasses = final_nclasses; 630 uint16_t roots[3] = {0, starts[0], starts[1]}; 631 dfa_canonical_relabel(ctx, trans, accept, nstates, nclasses, roots, 3, starts, 632 2); 633 *start_line = starts[0]; 634 *start_text = starts[1]; 635 636 /* Expand the per-state accept signature ids into the three runtime accept 637 * tables; collapse an all-none end table to NULL. */ 638 uint16_t* accept_text = 639 xmalloc(ctx, (nstates ? nstates : 1) * sizeof *accept_text); 640 uint16_t* accept_line = 641 xmalloc(ctx, (nstates ? nstates : 1) * sizeof *accept_line); 642 int any_text = 0, any_line = 0; 643 for (uint16_t s = 0; s < nstates; s++) { 644 uint16_t sig = accept[s]; 645 if (sig == UINT16_MAX) { 646 accept[s] = UINT16_MAX; 647 accept_text[s] = UINT16_MAX; 648 accept_line[s] = UINT16_MAX; 649 } else { 650 AcceptTriple tr = sigmap->triples[sig]; 651 accept[s] = tr.plain; 652 accept_text[s] = tr.text; 653 accept_line[s] = tr.line; 654 if (tr.text != UINT16_MAX) any_text = 1; 655 if (tr.line != UINT16_MAX) any_line = 1; 656 } 657 } 658 if (!any_text) { 659 xfree(ctx, accept_text); 660 accept_text = NULL; 661 } 662 if (!any_line) { 663 xfree(ctx, accept_line); 664 accept_line = NULL; 665 } 666 667 *nclasses_out = nclasses; 668 *trans_out = trans; 669 *nstates_out = nstates; 670 *accept_out = accept; 671 *accept_text_out = accept_text; 672 *accept_line_out = accept_line; 673 } 674 675 /* Compile the utf8 branch of compile_lexer(): scalar NFA -> scalar DFA -> byte 676 * DFA tables. Split out so the byte path/driver in kit_gram_lex_byte.c carries 677 * no scalar-pipeline references. */ 678 void kit_gram_compile_lexer_utf8( 679 GramgenContext* ctx, Loc loc, LexRecognizer* recognizers, 680 const size_t* compile_indices, size_t ncompile, uint8_t class_of[256], 681 uint16_t* nclasses_out, uint16_t** trans_out, uint16_t* nstates_out, 682 uint16_t** accept_out, uint16_t** accept_text_out, 683 uint16_t** accept_line_out, uint16_t* start_text_out, 684 uint16_t* start_line_out) { 685 ScalarNfaBuilder scalar_nfa = {.ctx = ctx}; 686 int scalar_start = scalar_nfa_new_state(&scalar_nfa); 687 for (size_t i = 0; i < ncompile; i++) { 688 size_t rec_idx = compile_indices[i]; 689 LexRecognizer* rec = &recognizers[rec_idx]; 690 NfaFrag frag = 691 range_nfa_from_lex_alt(&scalar_nfa, &scalar_alphabet, rec->alts); 692 /* Start anchor: zero-width edge from the global start; else plain eps. */ 693 if (rec->start_anchor == KIT_GRAM_LEX_ANCHOR_TEXT) 694 scalar_nfa_bnd(&scalar_nfa, scalar_start, NFA_BND_BT, frag.start); 695 else if (rec->start_anchor == KIT_GRAM_LEX_ANCHOR_LINE) 696 scalar_nfa_bnd(&scalar_nfa, scalar_start, NFA_BND_BL, frag.start); 697 else 698 scalar_nfa_eps(&scalar_nfa, scalar_start, frag.start); 699 /* End anchor: zero-width edge to a terminal accept node; else accept body 700 * end. */ 701 if (rec->end_anchor == KIT_GRAM_LEX_ANCHOR_TEXT) { 702 int acc = scalar_nfa_new_state(&scalar_nfa); 703 scalar_nfa.states[acc].accept = (int)rec_idx; 704 scalar_nfa_bnd(&scalar_nfa, frag.end, NFA_BND_ET, acc); 705 } else if (rec->end_anchor == KIT_GRAM_LEX_ANCHOR_LINE) { 706 int acc = scalar_nfa_new_state(&scalar_nfa); 707 scalar_nfa.states[acc].accept = (int)rec_idx; 708 scalar_nfa_bnd(&scalar_nfa, frag.end, NFA_BND_EL, acc); 709 } else { 710 scalar_nfa.states[frag.end].accept = (int)rec_idx; 711 } 712 } 713 714 ScalarClasses classes = {0}; 715 uint16_t* scalar_trans = NULL; 716 uint16_t* scalar_accept = NULL; 717 uint16_t scalar_nstates = 0; 718 AcceptSigMap sigmap = {0}; 719 uint16_t start_text = 0, start_line = 0; 720 scalar_nfa_to_dfa(ctx, loc, &scalar_nfa, scalar_start, 721 /*exclude_surrogates=*/1, &classes, &scalar_trans, 722 &scalar_accept, &scalar_nstates, &sigmap, &start_text, 723 &start_line); 724 725 scalar_dfa_to_byte_tables(ctx, loc, &classes, scalar_trans, scalar_accept, 726 scalar_nstates, &sigmap, class_of, nclasses_out, 727 trans_out, nstates_out, accept_out, accept_text_out, 728 accept_line_out, &start_text, &start_line); 729 accept_sig_map_free(ctx, &sigmap); 730 scalar_classes_free(ctx, &classes); 731 *start_text_out = start_text; 732 *start_line_out = start_line; 733 }