lex_range.c (21821B)
1 /* kit_gram_lex_range.c - alphabet-neutral range-set NFA, atom partition, and the 2 * one determinization, shared by the utf8 scalar pipeline and the 3 * token-alphabet 4 * (%machine) pipeline. See kit_gram_lex_range.h. Pure code move out of 5 * gen/kit_gram_lex_scalar.c: scalar/UTF-8 output stays byte-identical (the 6 * C<->Python parity stamps guard it). Non-gated, so it survives 7 * KIT_GRAM_NO_UNICODE. */ 8 #include "internal.h" 9 10 /* Moved here (from the gated kit_gram_lex_unicode.c) so the non-gated range core 11 * and the token pipeline can call it under KIT_GRAM_NO_UNICODE. The Unicode 12 * pipeline still calls it (this TU is always linked). */ 13 void kit_gram_scalar_set_require_nonempty(GramgenContext* ctx, 14 const ScalarSet* set, Loc loc) { 15 if (!set->n) kit_gram_error(ctx, loc, "empty Unicode character class"); 16 } 17 18 void scalar_classes_free(GramgenContext* ctx, ScalarClasses* sc) { 19 xfree(ctx, sc->ranges); 20 xfree(ctx, sc->off); 21 *sc = (ScalarClasses){0}; 22 } 23 24 int scalar_nfa_new_state(ScalarNfaBuilder* nfa) { 25 if (nfa->nstates == nfa->cap_states) { 26 nfa->cap_states = nfa->cap_states ? nfa->cap_states * 2 : 32; 27 nfa->states = 28 xrealloc(nfa->ctx, nfa->states, nfa->cap_states * sizeof *nfa->states); 29 } 30 ScalarNfaState st; 31 memset(&st, 0, sizeof st); 32 st.accept = -1; 33 nfa->states[nfa->nstates] = st; 34 return (int)nfa->nstates++; 35 } 36 37 void scalar_nfa_eps(ScalarNfaBuilder* nfa, int src, int dst) { 38 intset_add(nfa->ctx, &nfa->states[src].eps, dst); 39 } 40 41 void scalar_nfa_bnd(ScalarNfaBuilder* nfa, int src, NfaBndKind kind, int dst) { 42 ScalarNfaState* st = &nfa->states[src]; 43 if (st->nbnd == st->cap_bnd) { 44 st->cap_bnd = st->cap_bnd ? st->cap_bnd * 2 : 4; 45 st->bnd = xrealloc(nfa->ctx, st->bnd, st->cap_bnd * sizeof *st->bnd); 46 } 47 st->bnd[st->nbnd++] = (NfaBndEdge){.kind = (int)kind, .dst = dst}; 48 } 49 50 void scalar_nfa_edge(ScalarNfaBuilder* nfa, int src, ScalarSet chars, int dst, 51 Loc loc) { 52 kit_gram_scalar_set_require_nonempty(nfa->ctx, &chars, loc); 53 ScalarNfaState* st = &nfa->states[src]; 54 if (st->nedges == st->cap_edges) { 55 st->cap_edges = st->cap_edges ? st->cap_edges * 2 : 4; 56 st->edges = 57 xrealloc(nfa->ctx, st->edges, st->cap_edges * sizeof *st->edges); 58 } 59 st->edges[st->nedges++] = (ScalarNfaEdge){.chars = chars, .dst = dst}; 60 } 61 62 ScalarSet scalar_set_from_single_value(GramgenContext* ctx, uint32_t cp) { 63 ScalarSet out = {.ctx = ctx}; 64 out.v = xmalloc(ctx, sizeof *out.v); 65 out.v[0] = (ScalarRange){cp, cp}; 66 out.n = 1; 67 out.cap = 1; 68 return out; 69 } 70 71 NfaFrag scalar_nfa_empty(ScalarNfaBuilder* nfa) { 72 int start = scalar_nfa_new_state(nfa); 73 int end = scalar_nfa_new_state(nfa); 74 scalar_nfa_eps(nfa, start, end); 75 return (NfaFrag){start, end}; 76 } 77 78 NfaFrag scalar_nfa_scalar_set(ScalarNfaBuilder* nfa, ScalarSet set, Loc loc) { 79 int start = scalar_nfa_new_state(nfa); 80 int end = scalar_nfa_new_state(nfa); 81 scalar_nfa_edge(nfa, start, set, end, loc); 82 return (NfaFrag){start, end}; 83 } 84 85 NfaFrag scalar_nfa_concat(ScalarNfaBuilder* nfa, NfaFrag* parts, size_t n) { 86 if (!n) return scalar_nfa_empty(nfa); 87 NfaFrag cur = parts[0]; 88 for (size_t i = 1; i < n; i++) { 89 scalar_nfa_eps(nfa, cur.end, parts[i].start); 90 cur.end = parts[i].end; 91 } 92 return cur; 93 } 94 95 NfaFrag scalar_nfa_alt(ScalarNfaBuilder* nfa, NfaFrag* parts, size_t n) { 96 int start = scalar_nfa_new_state(nfa); 97 int end = scalar_nfa_new_state(nfa); 98 for (size_t i = 0; i < n; i++) { 99 scalar_nfa_eps(nfa, start, parts[i].start); 100 scalar_nfa_eps(nfa, parts[i].end, end); 101 } 102 return (NfaFrag){start, end}; 103 } 104 105 NfaFrag scalar_nfa_opt(ScalarNfaBuilder* nfa, NfaFrag part) { 106 int start = scalar_nfa_new_state(nfa); 107 int end = scalar_nfa_new_state(nfa); 108 scalar_nfa_eps(nfa, start, part.start); 109 scalar_nfa_eps(nfa, start, end); 110 scalar_nfa_eps(nfa, part.end, end); 111 return (NfaFrag){start, end}; 112 } 113 114 NfaFrag scalar_nfa_rep(ScalarNfaBuilder* nfa, NfaFrag part) { 115 int start = scalar_nfa_new_state(nfa); 116 int end = scalar_nfa_new_state(nfa); 117 scalar_nfa_eps(nfa, start, part.start); 118 scalar_nfa_eps(nfa, start, end); 119 scalar_nfa_eps(nfa, part.end, part.start); 120 scalar_nfa_eps(nfa, part.end, end); 121 return (NfaFrag){start, end}; 122 } 123 124 /* Alphabet-neutral combinator walk over a desugared recognizer AST: dispatch 125 * the leaves through the LexAlphabet vtable, recurse the combinators. After 126 * desugaring no LEX_REPEAT survives, and a LEX_NAME is alphabet-specific (a 127 * symbol in token mode, an error in scalar mode) so it goes through leaf_name. 128 */ 129 static NfaFrag range_nfa_from_lex_node(ScalarNfaBuilder* nfa, 130 const LexAlphabet* a, AstLexNode* node) { 131 switch (node->kind) { 132 case LEX_LITERAL: 133 return a->leaf_literal(nfa, a, node); 134 case LEX_CLASS: 135 return a->leaf_class(nfa, a, node); 136 case LEX_PROP: 137 return a->leaf_prop(nfa, a, node); 138 case LEX_ANY: 139 return a->leaf_any(nfa, a, node); 140 case LEX_NAME: 141 return a->leaf_name(nfa, a, node); 142 case LEX_GROUP: 143 return range_nfa_from_lex_alt(nfa, a, node->alts); 144 case LEX_OPT: 145 return scalar_nfa_opt(nfa, range_nfa_from_lex_alt(nfa, a, node->alts)); 146 case LEX_REP: 147 return scalar_nfa_rep(nfa, range_nfa_from_lex_alt(nfa, a, node->alts)); 148 case LEX_ANCHOR: 149 /* Lowered to per-recognizer flags before NFA construction. */ 150 kit_gram_error(nfa->ctx, node->loc, 151 "mid-pattern assertions are not supported (Tier 2)"); 152 break; 153 case LEX_REPEAT: 154 kit_gram_error(nfa->ctx, node->loc, "internal: lex node not desugared"); 155 break; 156 } 157 return scalar_nfa_empty(nfa); 158 } 159 160 static NfaFrag range_nfa_from_lex_seq(ScalarNfaBuilder* nfa, 161 const LexAlphabet* a, AstLexSeq* seq) { 162 NfaFrag* parts = NULL; 163 if (seq->nitems) parts = xmalloc(nfa->ctx, seq->nitems * sizeof *parts); 164 for (size_t i = 0; i < seq->nitems; i++) 165 parts[i] = range_nfa_from_lex_node(nfa, a, seq->items[i]); 166 NfaFrag out = scalar_nfa_concat(nfa, parts, seq->nitems); 167 xfree(nfa->ctx, parts); 168 return out; 169 } 170 171 NfaFrag range_nfa_from_lex_alt(ScalarNfaBuilder* nfa, const LexAlphabet* a, 172 AstLexAlt* alt) { 173 NfaFrag* parts = NULL; 174 if (alt->nseqs) parts = xmalloc(nfa->ctx, alt->nseqs * sizeof *parts); 175 for (size_t i = 0; i < alt->nseqs; i++) 176 parts[i] = range_nfa_from_lex_seq(nfa, a, alt->seqs[i]); 177 NfaFrag out = scalar_nfa_alt(nfa, parts, alt->nseqs); 178 xfree(nfa->ctx, parts); 179 return out; 180 } 181 182 static IntSet scalar_nfa_closure(ScalarNfaBuilder* nfa, IntSetScratch* scratch, 183 const IntSet* states) { 184 IntSet out = {0}; 185 intset_scratch_reset(scratch); 186 intset_scratch_union(nfa->ctx, scratch, &out, states); 187 size_t pos = 0; 188 while (pos < out.n) { 189 int st = out.v[pos++]; 190 for (size_t i = 0; i < nfa->states[st].eps.n; i++) { 191 int dst = nfa->states[st].eps.v[i]; 192 intset_scratch_add(nfa->ctx, scratch, &out, dst); 193 } 194 } 195 intset_sort_in_place(&out); 196 return out; 197 } 198 199 static IntSet* scalar_nfa_state_closures(ScalarNfaBuilder* nfa) { 200 IntSet* closures = xcalloc(nfa->ctx, nfa->nstates, sizeof *closures); 201 IntSetScratch scratch; 202 intset_scratch_init(nfa->ctx, &scratch, nfa->nstates); 203 for (size_t st = 0; st < nfa->nstates; st++) { 204 IntSet one = {0}; 205 intset_add(nfa->ctx, &one, (int)st); 206 closures[st] = scalar_nfa_closure(nfa, &scratch, &one); 207 } 208 return closures; 209 } 210 211 static int scalar_set_intersects_range(const ScalarSet* set, uint32_t lo, 212 uint32_t hi) { 213 for (size_t i = 0; i < set->n; i++) { 214 if (set->v[i].hi < lo) continue; 215 if (set->v[i].lo > hi) return 0; 216 return 1; 217 } 218 return 0; 219 } 220 221 /* Equality of two edge sets, used to dedup the per-edge refinement passes in 222 * scalar_atom_classes. ScalarSets are kept sorted and merged (canonical) by 223 * every constructor, so elementwise comparison is exact -- no false positives 224 * (a false positive would skip a real refinement and under-split atoms). */ 225 static int scalar_set_equal(const ScalarSet* a, const ScalarSet* b) { 226 if (a->n != b->n) return 0; 227 for (size_t i = 0; i < a->n; i++) 228 if (a->v[i].lo != b->v[i].lo || a->v[i].hi != b->v[i].hi) return 0; 229 return 1; 230 } 231 232 static int scalar_is_value(uint32_t cp) { 233 return cp <= UNICODE_MAX_SCALAR && 234 !(cp >= UNICODE_SURROGATE_FIRST && cp <= UNICODE_SURROGATE_LAST); 235 } 236 237 static int u32_cmp(const void* a, const void* b) { 238 uint32_t x = *(const uint32_t*)a; 239 uint32_t y = *(const uint32_t*)b; 240 return (x > y) - (x < y); 241 } 242 243 static void u32_append(GramgenContext* ctx, uint32_t** v, size_t* n, 244 size_t* cap, uint32_t value) { 245 if (*n == *cap) { 246 *cap = *cap ? *cap * 2 : 32; 247 *v = xrealloc(ctx, *v, *cap * sizeof **v); 248 } 249 (*v)[(*n)++] = value; 250 } 251 252 static void scalar_range_append(GramgenContext* ctx, ScalarRange** v, size_t* n, 253 size_t* cap, uint32_t lo, uint32_t hi) { 254 if (*n == *cap) { 255 *cap = *cap ? *cap * 2 : 32; 256 *v = xrealloc(ctx, *v, *cap * sizeof **v); 257 } 258 (*v)[(*n)++] = (ScalarRange){lo, hi}; 259 } 260 261 /* Partition the alphabet universe into atoms: maximal ranges with constant edge 262 * membership. `exclude_surrogates` drops the UTF-8 surrogate gap (scalar/UTF-8 263 * universe); token alphabets pass 0 (dense 0..NSYM-1, no holes). */ 264 static ScalarRange* scalar_atom_ranges(GramgenContext* ctx, Loc loc, 265 ScalarNfaBuilder* nfa, 266 int exclude_surrogates, 267 uint16_t* natoms_out) { 268 uint32_t* points = NULL; 269 size_t npoints = 0, cap_points = 0; 270 for (size_t st = 0; st < nfa->nstates; st++) { 271 for (size_t ei = 0; ei < nfa->states[st].nedges; ei++) { 272 ScalarSet* set = &nfa->states[st].edges[ei].chars; 273 for (size_t ri = 0; ri < set->n; ri++) { 274 u32_append(ctx, &points, &npoints, &cap_points, set->v[ri].lo); 275 u32_append(ctx, &points, &npoints, &cap_points, set->v[ri].hi + 1u); 276 } 277 } 278 } 279 if (!npoints) 280 kit_gram_error(ctx, loc, "generated lexer has no scalar transitions"); 281 qsort(points, npoints, sizeof *points, u32_cmp); 282 size_t unique = 0; 283 for (size_t i = 0; i < npoints; i++) { 284 if (!unique || points[i] != points[unique - 1]) 285 points[unique++] = points[i]; 286 } 287 288 ScalarRange* atoms = NULL; 289 size_t natoms = 0, cap_atoms = 0; 290 for (size_t i = 0; i + 1 < unique; i++) { 291 uint32_t lo = points[i]; 292 uint32_t hi = points[i + 1] - 1u; 293 if (lo > hi) continue; 294 if (exclude_surrogates && !scalar_is_value(lo)) continue; 295 int active = 0; 296 for (size_t st = 0; st < nfa->nstates && !active; st++) { 297 for (size_t ei = 0; ei < nfa->states[st].nedges; ei++) { 298 if (scalar_set_intersects_range(&nfa->states[st].edges[ei].chars, lo, 299 hi)) { 300 active = 1; 301 break; 302 } 303 } 304 } 305 if (!active) continue; 306 if (natoms >= 65535) 307 kit_gram_error(ctx, loc, "too many lexer scalar classes"); 308 scalar_range_append(ctx, &atoms, &natoms, &cap_atoms, lo, hi); 309 } 310 if (!natoms) 311 kit_gram_error(ctx, loc, "generated lexer has no scalar transitions"); 312 *natoms_out = (uint16_t)natoms; 313 return atoms; 314 } 315 316 /* Refine a partition of `natoms` atoms by a boolean predicate. color[] is kept 317 * dense in [0, *ncolors). lo/hi (scratch, each sized >= current ncolors) map 318 * (oldcolor, bit) -> new dense color, assigned in ascending atom order so the 319 * color set stays dense. Heap-sized analog of byte_color_refine. */ 320 static void scalar_color_refine(uint16_t* color, uint16_t natoms, int* ncolors, 321 const uint8_t* pred, int* lo, int* hi) { 322 for (int c = 0; c < *ncolors; c++) { 323 lo[c] = -1; 324 hi[c] = -1; 325 } 326 int n = 0; 327 for (uint16_t a = 0; a < natoms; a++) { 328 int oc = color[a]; 329 int* slot = pred[a] ? &hi[oc] : &lo[oc]; 330 if (*slot < 0) *slot = n++; 331 color[a] = (uint16_t)*slot; 332 } 333 *ncolors = n; 334 } 335 336 /* Partition the atoms into symbol classes (see ScalarClasses). Mirrors 337 * nfa_byte_classes: start with one class, then refine once per DISTINCT edge 338 * ScalarSet across the whole NFA by the predicate "this edge's set intersects 339 * the atom". Two atoms end in the same class iff every edge set contains both 340 * or neither. */ 341 static ScalarClasses scalar_atom_classes(GramgenContext* ctx, 342 ScalarNfaBuilder* nfa, 343 const ScalarRange* atoms, 344 uint16_t natoms) { 345 uint16_t* color = xmalloc(ctx, (size_t)natoms * sizeof *color); 346 for (uint16_t a = 0; a < natoms; a++) color[a] = 0; 347 int ncolors = 1; 348 int* lo = xmalloc(ctx, (size_t)natoms * sizeof *lo); 349 int* hi = xmalloc(ctx, (size_t)natoms * sizeof *hi); 350 uint8_t* pred = xmalloc(ctx, (size_t)natoms * sizeof *pred); 351 352 ScalarSet* seen = NULL; 353 size_t nseen = 0, cap_seen = 0; 354 for (size_t st = 0; st < nfa->nstates; st++) { 355 ScalarNfaState* s = &nfa->states[st]; 356 for (size_t ei = 0; ei < s->nedges; ei++) { 357 ScalarSet* cs = &s->edges[ei].chars; 358 int dup = 0; 359 for (size_t i = 0; i < nseen; i++) 360 if (scalar_set_equal(&seen[i], cs)) { 361 dup = 1; 362 break; 363 } 364 if (dup) continue; /* same set refines to the same (idempotent) split */ 365 if (nseen == cap_seen) { 366 cap_seen = cap_seen ? cap_seen * 2 : 16; 367 seen = xrealloc(ctx, seen, cap_seen * sizeof *seen); 368 } 369 seen[nseen++] = 370 *cs; /* shallow: borrowed ranges, never freed/mutated here */ 371 for (uint16_t a = 0; a < natoms; a++) 372 pred[a] = 373 (uint8_t)scalar_set_intersects_range(cs, atoms[a].lo, atoms[a].hi); 374 scalar_color_refine(color, natoms, &ncolors, pred, lo, hi); 375 } 376 } 377 xfree(ctx, seen); 378 xfree(ctx, pred); 379 380 /* Canonicalize colors by ascending first-atom index (mirrors 381 * byte_color_finish); reuse color[] as the final atom -> class map. */ 382 int* remap = xmalloc(ctx, (size_t)ncolors * sizeof *remap); 383 for (int c = 0; c < ncolors; c++) remap[c] = -1; 384 int nclasses = 0; 385 for (uint16_t a = 0; a < natoms; a++) { 386 int oc = color[a]; 387 if (remap[oc] < 0) remap[oc] = nclasses++; 388 color[a] = (uint16_t)remap[oc]; 389 } 390 xfree(ctx, remap); 391 xfree(ctx, lo); 392 xfree(ctx, hi); 393 394 /* Flat union: atoms grouped by class (counting sort), ascending within a 395 * class so ranges[off[c]] is the class's representative atom. */ 396 ScalarClasses sc = {.nclasses = (uint16_t)nclasses}; 397 sc.off = xmalloc(ctx, ((size_t)nclasses + 1) * sizeof *sc.off); 398 sc.ranges = xmalloc(ctx, (size_t)(natoms ? natoms : 1) * sizeof *sc.ranges); 399 for (int c = 0; c <= nclasses; c++) sc.off[c] = 0; 400 for (uint16_t a = 0; a < natoms; a++) sc.off[color[a] + 1]++; 401 for (int c = 0; c < nclasses; c++) sc.off[c + 1] += sc.off[c]; 402 uint32_t* cursor = 403 xmalloc(ctx, (size_t)(nclasses ? nclasses : 1) * sizeof *cursor); 404 for (int c = 0; c < nclasses; c++) cursor[c] = sc.off[c]; 405 for (uint16_t a = 0; a < natoms; a++) 406 sc.ranges[cursor[color[a]]++] = atoms[a]; 407 xfree(ctx, cursor); 408 xfree(ctx, color); 409 return sc; 410 } 411 412 /* Per-(state, class) NFA destination closures. A class's representative atom 413 * (its first, smallest range) shares edge membership with every atom in the 414 * class, so testing it gives the destination set common to the whole class. */ 415 static IntSet* scalar_nfa_class_dests(GramgenContext* ctx, 416 ScalarNfaBuilder* nfa, 417 const IntSet* state_closures, 418 IntSetScratch* scratch, 419 const ScalarClasses* sc) { 420 IntSet* dests = 421 xcalloc(ctx, nfa->nstates * (size_t)sc->nclasses, sizeof *dests); 422 for (size_t st_idx = 0; st_idx < nfa->nstates; st_idx++) { 423 ScalarNfaState* st = &nfa->states[st_idx]; 424 for (uint16_t cls = 0; cls < sc->nclasses; cls++) { 425 ScalarRange rep = sc->ranges[sc->off[cls]]; 426 IntSet direct = {0}; 427 for (size_t ei = 0; ei < st->nedges; ei++) { 428 if (scalar_set_intersects_range(&st->edges[ei].chars, rep.lo, rep.hi)) 429 intset_add(ctx, &direct, st->edges[ei].dst); 430 } 431 if (direct.n) 432 dests[st_idx * (size_t)sc->nclasses + cls] = 433 cached_closure(ctx, state_closures, scratch, &direct); 434 } 435 } 436 return dests; 437 } 438 439 /* Accept triple for a DFA subset: priority-winning recognizer reachable 440 * directly (no end anchor), via a `\z` (ET) zero-width edge, and via a `$` (EL) 441 * edge. Mirrors byte_subset_accepts on the range NFA. */ 442 static void scalar_subset_accepts(const ScalarNfaBuilder* nfa, 443 const IntSet* state_closures, 444 const IntSet* subset, uint16_t* plain, 445 uint16_t* text, uint16_t* line) { 446 int p = 65535, t = 65535, l = 65535; 447 for (size_t i = 0; i < subset->n; i++) { 448 const ScalarNfaState* st = &nfa->states[subset->v[i]]; 449 if (st->accept >= 0 && st->accept < p) p = st->accept; 450 for (size_t e = 0; e < st->nbnd; e++) { 451 int kind = st->bnd[e].kind; 452 if (kind != NFA_BND_ET && kind != NFA_BND_EL) continue; 453 const IntSet* clo = &state_closures[st->bnd[e].dst]; 454 for (size_t k = 0; k < clo->n; k++) { 455 int a = nfa->states[clo->v[k]].accept; 456 if (a < 0) continue; 457 if (kind == NFA_BND_ET) { 458 if (a < t) t = a; 459 } else { 460 if (a < l) l = a; 461 } 462 } 463 } 464 } 465 *plain = (uint16_t)p; 466 *text = (uint16_t)t; 467 *line = (uint16_t)l; 468 } 469 470 void scalar_nfa_to_dfa(GramgenContext* ctx, Loc loc, ScalarNfaBuilder* nfa, 471 int start, int exclude_surrogates, 472 ScalarClasses* classes_out, uint16_t** trans_out, 473 uint16_t** accept_out, uint16_t* nstates_out, 474 AcceptSigMap* sigmap, uint16_t* start_text_out, 475 uint16_t* start_line_out) { 476 uint16_t natoms = 0; 477 ScalarRange* atoms = 478 scalar_atom_ranges(ctx, loc, nfa, exclude_surrogates, &natoms); 479 ScalarClasses sc = scalar_atom_classes(ctx, nfa, atoms, natoms); 480 xfree(ctx, atoms); /* sc.ranges now carries the per-class ranges */ 481 uint16_t nclasses = sc.nclasses; 482 IntSet* state_closures = scalar_nfa_state_closures(nfa); 483 IntSetScratch scratch; 484 intset_scratch_init(ctx, &scratch, nfa->nstates); 485 IntSet* class_dests = 486 scalar_nfa_class_dests(ctx, nfa, state_closures, &scratch, &sc); 487 488 IntSet* dfa_sets = NULL; 489 size_t nsets = 0, cap_sets = 0; 490 DfaSubsetMap subset_map = {0}; 491 dfa_subset_map_init(ctx, &subset_map); 492 493 /* Three start subsets selected by start-of-match context (see the byte 494 * pipeline): interior interns as state 0; line/text dedup to 0 when there 495 * are no start anchors. */ 496 IntSet interior_set = {0}, line_seed = {0}, text_seed = {0}; 497 intset_add(ctx, &interior_set, start); 498 intset_add(ctx, &line_seed, start); 499 intset_add(ctx, &text_seed, start); 500 { 501 ScalarNfaState* s0 = &nfa->states[start]; 502 for (size_t e = 0; e < s0->nbnd; e++) { 503 if (s0->bnd[e].kind == NFA_BND_BL) { 504 intset_add(ctx, &line_seed, s0->bnd[e].dst); 505 intset_add(ctx, &text_seed, s0->bnd[e].dst); 506 } else if (s0->bnd[e].kind == NFA_BND_BT) { 507 intset_add(ctx, &text_seed, s0->bnd[e].dst); 508 } 509 } 510 } 511 IntSet interior_clo = 512 cached_closure(ctx, state_closures, &scratch, &interior_set); 513 IntSet line_clo = cached_closure(ctx, state_closures, &scratch, &line_seed); 514 IntSet text_clo = cached_closure(ctx, state_closures, &scratch, &text_seed); 515 dfa_intern_subset(ctx, &subset_map, &dfa_sets, &nsets, &cap_sets, 516 &interior_clo, loc); 517 *start_line_out = (uint16_t)dfa_intern_subset( 518 ctx, &subset_map, &dfa_sets, &nsets, &cap_sets, &line_clo, loc); 519 *start_text_out = (uint16_t)dfa_intern_subset( 520 ctx, &subset_map, &dfa_sets, &nsets, &cap_sets, &text_clo, loc); 521 xfree(ctx, interior_clo.v); 522 xfree(ctx, line_clo.v); 523 xfree(ctx, text_clo.v); 524 xfree(ctx, interior_set.v); 525 xfree(ctx, line_seed.v); 526 xfree(ctx, text_seed.v); 527 528 uint16_t* trans = NULL; 529 uint16_t* accept = NULL; 530 size_t row_cap = 0, accept_cap = 0; 531 size_t qpos = 0; 532 IntSet dest = {0}; /* reused across all cells */ 533 while (qpos < nsets) { 534 IntSet subset = dfa_sets[qpos++]; 535 if (qpos > accept_cap) { 536 accept_cap = accept_cap ? accept_cap * 2 : 16; 537 while (accept_cap < qpos) accept_cap *= 2; 538 accept = xrealloc(ctx, accept, accept_cap * sizeof *accept); 539 } 540 uint16_t ap, at, al; 541 scalar_subset_accepts(nfa, state_closures, &subset, &ap, &at, &al); 542 accept[qpos - 1] = accept_sig_intern(ctx, sigmap, ap, at, al); 543 if (qpos > row_cap) { 544 row_cap = row_cap ? row_cap * 2 : 16; 545 while (row_cap < qpos) row_cap *= 2; 546 trans = xrealloc(ctx, trans, row_cap * (size_t)nclasses * sizeof *trans); 547 } 548 uint16_t* row = &trans[(qpos - 1) * (size_t)nclasses]; 549 for (uint16_t cls = 0; cls < nclasses; cls++) { 550 dest.n = 0; 551 intset_scratch_reset(&scratch); 552 for (size_t si = 0; si < subset.n; si++) { 553 const IntSet* st_dest = 554 &class_dests[subset.v[si] * (size_t)nclasses + cls]; 555 intset_scratch_union(ctx, &scratch, &dest, st_dest); 556 } 557 if (dest.n) { 558 intset_sort_in_place(&dest); 559 row[cls] = (uint16_t)dfa_intern_subset(ctx, &subset_map, &dfa_sets, 560 &nsets, &cap_sets, &dest, loc); 561 } else { 562 row[cls] = UINT16_MAX; 563 } 564 } 565 } 566 xfree(ctx, dest.v); 567 568 *classes_out = sc; 569 *trans_out = trans; 570 *accept_out = accept; 571 *nstates_out = (uint16_t)nsets; 572 }