lex_byte.c (72650B)
1 /* kit_gram_lex_byte.c - byte lexer pipeline (byte NFA -> byte DFA) plus the 2 * mode-independent lexer driver (compile_lexer / kit_gram_prepare_lexer). */ 3 #include "internal.h" 4 typedef struct { 5 uint64_t bits[4]; 6 } CharSet; 7 8 static void charset_add(CharSet* cs, unsigned b) { 9 cs->bits[b / 64] |= (uint64_t)1 << (b % 64); 10 } 11 12 static int charset_has(const CharSet* cs, unsigned b) { 13 return (cs->bits[b / 64] & ((uint64_t)1 << (b % 64))) != 0; 14 } 15 16 static int charset_equal(const CharSet* a, const CharSet* b) { 17 return a->bits[0] == b->bits[0] && a->bits[1] == b->bits[1] && 18 a->bits[2] == b->bits[2] && a->bits[3] == b->bits[3]; 19 } 20 21 static int charset_empty(const CharSet* cs) { 22 return cs->bits[0] == 0 && cs->bits[1] == 0 && cs->bits[2] == 0 && 23 cs->bits[3] == 0; 24 } 25 26 static CharSet charset_all(void) { 27 CharSet cs = {{UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX}}; 28 return cs; 29 } 30 31 static CharSet charset_not(CharSet in) { 32 CharSet out; 33 for (int i = 0; i < 4; i++) out.bits[i] = ~in.bits[i]; 34 return out; 35 } 36 37 static unsigned char class_escape_value2(unsigned char c) { 38 switch (c) { 39 case 'n': 40 return '\n'; 41 case 'r': 42 return '\r'; 43 case 't': 44 return '\t'; 45 case '0': 46 return '\0'; 47 default: 48 return c; 49 } 50 } 51 52 /* ASCII shorthand class set for \d \w \s (and their uppercase complements). 53 * Defined identically in byte and utf8 mode; sh is one of d D w W s S. */ 54 static CharSet class_shorthand_bytes(unsigned char sh) { 55 CharSet cs = {{0}}; 56 unsigned char lower = 57 (sh >= 'A' && sh <= 'Z') ? (unsigned char)(sh + 32) : sh; 58 if (lower == 'd') { 59 for (int b = '0'; b <= '9'; b++) charset_add(&cs, (unsigned)b); 60 } else if (lower == 'w') { 61 for (int b = '0'; b <= '9'; b++) charset_add(&cs, (unsigned)b); 62 for (int b = 'A'; b <= 'Z'; b++) charset_add(&cs, (unsigned)b); 63 for (int b = 'a'; b <= 'z'; b++) charset_add(&cs, (unsigned)b); 64 charset_add(&cs, (unsigned)'_'); 65 } else { /* 's' */ 66 charset_add(&cs, (unsigned)' '); 67 charset_add(&cs, (unsigned)'\t'); 68 charset_add(&cs, (unsigned)'\n'); 69 charset_add(&cs, (unsigned)'\r'); 70 charset_add(&cs, (unsigned)'\f'); 71 charset_add(&cs, (unsigned)'\v'); 72 } 73 if (sh >= 'A' && sh <= 'Z') cs = charset_not(cs); 74 return cs; 75 } 76 77 static int class_is_shorthand(Str raw, size_t end, size_t i) { 78 if (raw.s[i] != '\\' || i + 1 >= end) return 0; 79 unsigned char n = (unsigned char)raw.s[i + 1]; 80 return n == 'd' || n == 'D' || n == 'w' || n == 'W' || n == 's' || n == 'S'; 81 } 82 83 static int class_atom_value(GramgenContext* ctx, Str raw, size_t end, size_t* i, 84 Loc loc) { 85 unsigned char c = (unsigned char)raw.s[*i]; 86 if (c == '\\') { 87 (*i)++; 88 if (*i >= end) kit_gram_error(ctx, loc, "unterminated character class"); 89 if ((unsigned char)raw.s[*i] == 'x') { 90 if (*i + 2 >= end) kit_gram_error(ctx, loc, "short hex escape"); 91 int hi = hex_val((unsigned char)raw.s[*i + 1]); 92 int lo = hex_val((unsigned char)raw.s[*i + 2]); 93 if (hi < 0 || lo < 0) kit_gram_error(ctx, loc, "bad hex escape"); 94 *i += 3; 95 return (hi << 4) | lo; 96 } 97 if ((unsigned char)raw.s[*i] == 'u' || (unsigned char)raw.s[*i] == 'U') 98 kit_gram_error( 99 ctx, loc, 100 "Unicode escapes are not supported in byte character classes"); 101 if (((unsigned char)raw.s[*i] == 'p' || (unsigned char)raw.s[*i] == 'P') && 102 *i + 1 < end && raw.s[*i + 1] == '{') 103 kit_gram_error(ctx, loc, 104 "Unicode property escapes are not supported in byte " 105 "character classes"); 106 c = class_escape_value2((unsigned char)raw.s[*i]); 107 (*i)++; 108 return c; 109 } 110 if (c == '-' || c == '^' || c == ']') 111 kit_gram_error(ctx, loc, "literal '%c' must be escaped in character class", 112 c); 113 (*i)++; 114 return c; 115 } 116 117 static CharSet char_class_bytes(GramgenContext* ctx, Str raw, Loc loc) { 118 if (raw.len < 2 || raw.s[0] != '[' || raw.s[raw.len - 1] != ']') 119 kit_gram_error(ctx, loc, "malformed character class"); 120 size_t i = 1, end = raw.len - 1; 121 int negate = 0; 122 if (i < end && raw.s[i] == '^') { 123 negate = 1; 124 i++; 125 } 126 CharSet out = {{0}}; 127 size_t nitems = 0; 128 while (i < end) { 129 if (class_is_shorthand(raw, end, i)) { 130 CharSet sh = class_shorthand_bytes((unsigned char)raw.s[i + 1]); 131 for (int k = 0; k < 4; k++) out.bits[k] |= sh.bits[k]; 132 i += 2; 133 nitems++; 134 continue; 135 } 136 int lo = class_atom_value(ctx, raw, end, &i, loc); 137 if (i < end && raw.s[i] == '-') { 138 i++; 139 if (i >= end) 140 kit_gram_error(ctx, loc, 141 "literal '-' must be escaped in character class"); 142 int hi = class_atom_value(ctx, raw, end, &i, loc); 143 if (lo > hi) kit_gram_error(ctx, loc, "reversed range in character class"); 144 for (int b = lo; b <= hi; b++) charset_add(&out, (unsigned)b); 145 } else { 146 charset_add(&out, (unsigned)lo); 147 } 148 nitems++; 149 } 150 if (!nitems) kit_gram_error(ctx, loc, "empty character class"); 151 if (negate) out = charset_not(out); 152 if (charset_empty(&out)) kit_gram_error(ctx, loc, "empty character class"); 153 return out; 154 } 155 156 static int lex_node_nullable(AstLexNode* node); 157 158 static int lex_seq_nullable(AstLexSeq* seq) { 159 for (size_t i = 0; i < seq->nitems; i++) 160 if (!lex_node_nullable(seq->items[i])) return 0; 161 return 1; 162 } 163 164 static int lex_alt_nullable(AstLexAlt* alt) { 165 for (size_t i = 0; i < alt->nseqs; i++) 166 if (lex_seq_nullable(alt->seqs[i])) return 1; 167 return 0; 168 } 169 170 static int lex_node_nullable(AstLexNode* node) { 171 switch (node->kind) { 172 case LEX_LITERAL: 173 return node->value.len == 0; 174 case LEX_CLASS: 175 case LEX_PROP: 176 case LEX_ANY: 177 return 0; 178 case LEX_GROUP: 179 return lex_alt_nullable(node->alts); 180 case LEX_OPT: 181 case LEX_REP: 182 return 1; 183 case LEX_ANCHOR: 184 return 1; /* zero-width; stripped before this runs */ 185 case LEX_REPEAT: 186 case LEX_NAME: 187 /* Removed by kit_gram_desugar_lex before this runs; nfa_from_lex_node is 188 * the loud guard if one ever leaks. Return a safe value (LEX_NAME has no 189 * alts to recurse into). */ 190 return 0; 191 } 192 return 0; 193 } 194 195 typedef struct { 196 CharSet chars; 197 int dst; 198 } NfaEdge; 199 200 typedef struct { 201 IntSet eps; 202 NfaEdge* edges; 203 size_t nedges, cap_edges; 204 NfaBndEdge* bnd; /* zero-width edge-anchor edges (not in eps-closure) */ 205 size_t nbnd, cap_bnd; 206 int accept; 207 } NfaState; 208 209 typedef struct { 210 GramgenContext* ctx; 211 NfaState* states; 212 size_t nstates, cap_states; 213 } NfaBuilder; 214 215 static int nfa_new_state(NfaBuilder* nfa) { 216 if (nfa->nstates == nfa->cap_states) { 217 nfa->cap_states = GROW_CAP(nfa->cap_states, 32); 218 nfa->states = 219 xrealloc(nfa->ctx, nfa->states, nfa->cap_states * sizeof *nfa->states); 220 } 221 NfaState st; 222 memset(&st, 0, sizeof st); 223 st.accept = -1; 224 nfa->states[nfa->nstates] = st; 225 return (int)nfa->nstates++; 226 } 227 228 static void nfa_eps(NfaBuilder* nfa, int src, int dst) { 229 intset_add(nfa->ctx, &nfa->states[src].eps, dst); 230 } 231 232 static void nfa_bnd(NfaBuilder* nfa, int src, NfaBndKind kind, int dst) { 233 NfaState* st = &nfa->states[src]; 234 if (st->nbnd == st->cap_bnd) { 235 st->cap_bnd = GROW_CAP(st->cap_bnd, 4); 236 st->bnd = xrealloc(nfa->ctx, st->bnd, st->cap_bnd * sizeof *st->bnd); 237 } 238 st->bnd[st->nbnd++] = (NfaBndEdge){.kind = (int)kind, .dst = dst}; 239 } 240 241 static void nfa_edge(NfaBuilder* nfa, int src, CharSet chars, int dst) { 242 if (charset_empty(&chars)) return; 243 NfaState* st = &nfa->states[src]; 244 if (st->nedges == st->cap_edges) { 245 st->cap_edges = GROW_CAP(st->cap_edges, 4); 246 st->edges = 247 xrealloc(nfa->ctx, st->edges, st->cap_edges * sizeof *st->edges); 248 } 249 st->edges[st->nedges++] = (NfaEdge){.chars = chars, .dst = dst}; 250 } 251 252 static NfaFrag nfa_empty(NfaBuilder* nfa) { 253 int start = nfa_new_state(nfa); 254 int end = nfa_new_state(nfa); 255 nfa_eps(nfa, start, end); 256 return (NfaFrag){start, end}; 257 } 258 259 static NfaFrag nfa_chars(NfaBuilder* nfa, CharSet chars) { 260 int start = nfa_new_state(nfa); 261 int end = nfa_new_state(nfa); 262 nfa_edge(nfa, start, chars, end); 263 return (NfaFrag){start, end}; 264 } 265 266 static NfaFrag nfa_literal(NfaBuilder* nfa, Str s) { 267 if (!s.len) return nfa_empty(nfa); 268 int start = nfa_new_state(nfa); 269 int cur = start; 270 for (size_t i = 0; i < s.len; i++) { 271 int nxt = nfa_new_state(nfa); 272 CharSet cs = {{0}}; 273 charset_add(&cs, (unsigned char)s.s[i]); 274 nfa_edge(nfa, cur, cs, nxt); 275 cur = nxt; 276 } 277 return (NfaFrag){start, cur}; 278 } 279 280 static NfaFrag nfa_concat(NfaBuilder* nfa, NfaFrag* parts, size_t n) { 281 if (!n) return nfa_empty(nfa); 282 NfaFrag cur = parts[0]; 283 for (size_t i = 1; i < n; i++) { 284 nfa_eps(nfa, cur.end, parts[i].start); 285 cur.end = parts[i].end; 286 } 287 return cur; 288 } 289 290 static NfaFrag nfa_alt(NfaBuilder* nfa, NfaFrag* parts, size_t n) { 291 int start = nfa_new_state(nfa); 292 int end = nfa_new_state(nfa); 293 for (size_t i = 0; i < n; i++) { 294 nfa_eps(nfa, start, parts[i].start); 295 nfa_eps(nfa, parts[i].end, end); 296 } 297 return (NfaFrag){start, end}; 298 } 299 300 static NfaFrag nfa_opt(NfaBuilder* nfa, NfaFrag part) { 301 int start = nfa_new_state(nfa); 302 int end = nfa_new_state(nfa); 303 nfa_eps(nfa, start, part.start); 304 nfa_eps(nfa, start, end); 305 nfa_eps(nfa, part.end, end); 306 return (NfaFrag){start, end}; 307 } 308 309 static NfaFrag nfa_rep(NfaBuilder* nfa, NfaFrag part) { 310 int start = nfa_new_state(nfa); 311 int end = nfa_new_state(nfa); 312 nfa_eps(nfa, start, part.start); 313 nfa_eps(nfa, start, end); 314 nfa_eps(nfa, part.end, part.start); 315 nfa_eps(nfa, part.end, end); 316 return (NfaFrag){start, end}; 317 } 318 319 static NfaFrag nfa_from_lex_alt(NfaBuilder* nfa, AstLexAlt* alt); 320 321 static NfaFrag nfa_from_lex_node(NfaBuilder* nfa, AstLexNode* node) { 322 switch (node->kind) { 323 case LEX_LITERAL: 324 return nfa_literal(nfa, node->value); 325 case LEX_CLASS: 326 return nfa_chars(nfa, char_class_bytes(nfa->ctx, node->value, node->loc)); 327 case LEX_PROP: 328 kit_gram_error( 329 nfa->ctx, node->loc, 330 "Unicode property escapes are not supported in byte lexer mode"); 331 break; 332 case LEX_ANY: 333 return nfa_chars(nfa, charset_all()); 334 case LEX_ANCHOR: 335 /* Anchors are lowered to per-recognizer flags before NFA construction; 336 * reaching here means an anchor survived extraction (generator bug). */ 337 kit_gram_error(nfa->ctx, node->loc, 338 "mid-pattern assertions are not supported (Tier 2)"); 339 break; 340 case LEX_GROUP: 341 return nfa_from_lex_alt(nfa, node->alts); 342 case LEX_OPT: 343 return nfa_opt(nfa, nfa_from_lex_alt(nfa, node->alts)); 344 case LEX_REP: 345 return nfa_rep(nfa, nfa_from_lex_alt(nfa, node->alts)); 346 case LEX_REPEAT: 347 case LEX_NAME: 348 kit_gram_error(nfa->ctx, node->loc, "internal: lex node not desugared"); 349 break; 350 } 351 return nfa_empty(nfa); 352 } 353 354 static NfaFrag nfa_from_lex_seq(NfaBuilder* nfa, AstLexSeq* seq) { 355 NfaFrag* parts = NULL; 356 if (seq->nitems) parts = xmalloc(nfa->ctx, seq->nitems * sizeof *parts); 357 for (size_t i = 0; i < seq->nitems; i++) 358 parts[i] = nfa_from_lex_node(nfa, seq->items[i]); 359 NfaFrag out = nfa_concat(nfa, parts, seq->nitems); 360 xfree(nfa->ctx, parts); 361 return out; 362 } 363 364 static NfaFrag nfa_from_lex_alt(NfaBuilder* nfa, AstLexAlt* alt) { 365 NfaFrag* parts = NULL; 366 if (alt->nseqs) parts = xmalloc(nfa->ctx, alt->nseqs * sizeof *parts); 367 for (size_t i = 0; i < alt->nseqs; i++) 368 parts[i] = nfa_from_lex_seq(nfa, alt->seqs[i]); 369 NfaFrag out = nfa_alt(nfa, parts, alt->nseqs); 370 xfree(nfa->ctx, parts); 371 return out; 372 } 373 374 static IntSet nfa_closure(NfaBuilder* nfa, IntSetScratch* scratch, 375 const IntSet* states) { 376 IntSet out = {0}; 377 intset_scratch_reset(scratch); 378 intset_scratch_union(nfa->ctx, scratch, &out, states); 379 size_t pos = 0; 380 while (pos < out.n) { 381 int st = out.v[pos++]; 382 for (size_t i = 0; i < nfa->states[st].eps.n; i++) { 383 int dst = nfa->states[st].eps.v[i]; 384 intset_scratch_add(nfa->ctx, scratch, &out, dst); 385 } 386 } 387 intset_sort_in_place(&out); 388 return out; 389 } 390 391 static IntSet* nfa_state_closures(NfaBuilder* nfa) { 392 IntSet* closures = xcalloc(nfa->ctx, nfa->nstates, sizeof *closures); 393 IntSetScratch scratch; 394 intset_scratch_init(nfa->ctx, &scratch, nfa->nstates); 395 for (size_t st = 0; st < nfa->nstates; st++) { 396 IntSet one = {0}; 397 intset_add(nfa->ctx, &one, (int)st); 398 closures[st] = nfa_closure(nfa, &scratch, &one); 399 } 400 return closures; 401 } 402 403 /* Interval/coloring byte equivalence-class partition (re2 ByteMapBuilder 404 * style). 405 * 406 * The partition over bytes 0..255 is represented by a per-byte color array. 407 * Each refinement "batch" splits the current partition by a boolean predicate: 408 * two bytes remain in the same class iff they shared a class before AND have 409 * the same predicate value in the batch. This is the common refinement of the 410 * prior partition with the predicate's two-way partition -- exactly the 411 * semantics needed for both byte-class call sites: 412 * - NFA edges: predicate = "byte appears in this edge's CharSet" 413 * - DFA columns: predicate = "byte's transition equals value v" 414 * 415 * Refining once per distinct edge CharSet (NFA) or once per distinct transition 416 * value per state (DFA) yields bytes equivalent iff their full signatures 417 * match, matching the original signature-comparison output. Class numbering is 418 * then canonicalized by minimum member byte to reproduce byte-identical tables. 419 */ 420 typedef struct { 421 /* color[b] is the current class color of byte b, always kept dense in 422 * [0, ncolors). Colors are arbitrary during refinement; canonical 423 * relabeling by minimum member byte happens in byte_color_finish. */ 424 uint16_t color[256]; 425 int ncolors; 426 } ByteColoring; 427 428 static void byte_color_init(ByteColoring* bc) { 429 for (int b = 0; b < 256; b++) bc->color[b] = 0; 430 bc->ncolors = 1; 431 } 432 433 /* Refine the partition by the boolean predicate pred[0..255]. Two bytes stay 434 * together iff they shared a class before AND have equal predicate value. */ 435 static void byte_color_refine(ByteColoring* bc, const uint8_t pred[256]) { 436 /* Fresh (oldcolor, bit) -> dense new color, assigned in ascending byte 437 * order so the color set stays dense and bounded by 256. */ 438 int lo[256], hi[256]; 439 for (int c = 0; c < bc->ncolors; c++) { 440 lo[c] = -1; 441 hi[c] = -1; 442 } 443 int n = 0; 444 for (int b = 0; b < 256; b++) { 445 int oc = bc->color[b]; 446 int* slot = pred[b] ? &hi[oc] : &lo[oc]; 447 if (*slot < 0) *slot = n++; 448 bc->color[b] = (uint16_t)*slot; 449 } 450 bc->ncolors = n; 451 } 452 453 /* Refine the partition by an arbitrary per-byte value (one batch). Two bytes 454 * stay together iff they shared a class before AND have equal value here. Uses 455 * a small open-addressed table keyed by (oldcolor, value) for the batch; new 456 * color ids are assigned in ascending byte order to keep the color set dense. 457 */ 458 static void byte_color_refine_u16(ByteColoring* bc, const uint16_t value[256]) { 459 enum { TCAP = 1024 }; /* power of two, > 256 distinct (color,value) pairs */ 460 uint32_t keys[TCAP]; 461 int vals[TCAP]; 462 uint8_t used[TCAP]; 463 memset(used, 0, sizeof used); 464 int n = 0; 465 for (int b = 0; b < 256; b++) { 466 uint32_t key = ((uint32_t)bc->color[b] << 16) | value[b]; 467 uint64_t h = (uint64_t)key * KIT_GRAM_HASH_PRIME; 468 size_t idx = (size_t)(h >> 40) & (TCAP - 1); 469 for (;;) { 470 if (!used[idx]) { 471 used[idx] = 1; 472 keys[idx] = key; 473 vals[idx] = n++; 474 bc->color[b] = (uint16_t)vals[idx]; 475 break; 476 } 477 if (keys[idx] == key) { 478 bc->color[b] = (uint16_t)vals[idx]; 479 break; 480 } 481 idx = (idx + 1) & (TCAP - 1); 482 } 483 } 484 bc->ncolors = n; 485 } 486 487 /* Canonicalize: relabel classes 0,1,2,... in ascending order of minimum member 488 * byte, exactly as the original first-byte scan numbered them. */ 489 static void byte_color_finish(GramgenContext* ctx, Loc loc, ByteColoring* bc, 490 uint8_t class_of[256], int* class_first, 491 uint16_t* nclasses_out) { 492 int remap[256]; 493 for (int i = 0; i < 256; i++) remap[i] = -1; 494 int nclasses = 0; 495 for (int b = 0; b < 256; b++) { 496 int oc = bc->color[b]; 497 int cls = remap[oc]; 498 if (cls < 0) { 499 if (nclasses >= 256) 500 kit_gram_error(ctx, loc, "too many lexer byte classes"); 501 cls = nclasses; 502 remap[oc] = cls; 503 class_first[nclasses++] = b; 504 } 505 class_of[b] = (uint8_t)cls; 506 } 507 *nclasses_out = (uint16_t)nclasses; 508 } 509 510 static void nfa_byte_classes(GramgenContext* ctx, Loc loc, 511 const NfaBuilder* nfa, uint8_t class_of[256], 512 unsigned char class_first[256], 513 uint16_t* nclasses_out) { 514 ByteColoring bc; 515 byte_color_init(&bc); 516 uint8_t pred[256]; 517 /* Refine once per distinct edge CharSet across the whole NFA. Two bytes end 518 * in the same class iff every CharSet contains both or neither, matching the 519 * original per-state signature comparison. */ 520 CharSet* seen_sets = NULL; 521 size_t nseen = 0, cap_seen = 0; 522 for (size_t st = 0; st < nfa->nstates; st++) { 523 const NfaState* s = &nfa->states[st]; 524 for (size_t ei = 0; ei < s->nedges; ei++) { 525 const CharSet* cs = &s->edges[ei].chars; 526 int dup = 0; 527 for (size_t i = 0; i < nseen; i++) { 528 if (charset_equal(&seen_sets[i], cs)) { 529 dup = 1; 530 break; 531 } 532 } 533 if (dup) continue; 534 if (nseen == cap_seen) { 535 cap_seen = GROW_CAP(cap_seen, 16); 536 seen_sets = xrealloc(ctx, seen_sets, cap_seen * sizeof *seen_sets); 537 } 538 seen_sets[nseen++] = *cs; 539 for (int b = 0; b < 256; b++) 540 pred[b] = (uint8_t)charset_has(cs, (unsigned)b); 541 byte_color_refine(&bc, pred); 542 } 543 } 544 xfree(ctx, seen_sets); 545 546 int first_tmp[256]; 547 byte_color_finish(ctx, loc, &bc, class_of, first_tmp, nclasses_out); 548 for (uint16_t c = 0; c < *nclasses_out; c++) 549 class_first[c] = (unsigned char)first_tmp[c]; 550 } 551 552 /* Per-(state,class) NFA destination closures, stored as a compressed sparse 553 * representation: data[off[k] .. off[k+1]) holds the sorted closure for cell 554 * k = state*nclasses + class. This replaces an array of nstates*nclasses IntSet 555 * structs (most empty) with two flat arrays, eliminating the dominant tiny 556 * allocation / free churn in UTF-8 lexer generation. Output is unchanged: the 557 * subset construction reads the same destination sets. */ 558 typedef struct { 559 size_t* off; /* (nstates*nclasses + 1) offsets into data */ 560 int* data; 561 size_t ncells; 562 } ByteClassDests; 563 564 static void byte_class_dests_free(GramgenContext* ctx, ByteClassDests* d) { 565 xfree(ctx, d->off); 566 xfree(ctx, d->data); 567 } 568 569 static ByteClassDests nfa_byte_class_dests( 570 GramgenContext* ctx, NfaBuilder* nfa, const IntSet* state_closures, 571 IntSetScratch* scratch, uint16_t nclasses, 572 const unsigned char class_first[256]) { 573 ByteClassDests d = {0}; 574 d.ncells = nfa->nstates * (size_t)nclasses; 575 d.off = xmalloc(ctx, (d.ncells + 1) * sizeof *d.off); 576 int* data = NULL; 577 size_t ndata = 0, cap_data = 0; 578 /* Per-state byte->class map computed once from class_first lets us route 579 * each edge to its covered classes in a single edge pass instead of 580 * rescanning all edges per class. */ 581 IntSet acc = {0}; 582 for (size_t st_idx = 0; st_idx < nfa->nstates; st_idx++) { 583 NfaState* st = &nfa->states[st_idx]; 584 for (uint16_t cls = 0; cls < nclasses; cls++) { 585 size_t cell = st_idx * (size_t)nclasses + cls; 586 d.off[cell] = ndata; 587 unsigned b = class_first[cls]; 588 acc.n = 0; 589 intset_scratch_reset(scratch); 590 for (size_t ei = 0; ei < st->nedges; ei++) { 591 if (!charset_has(&st->edges[ei].chars, b)) continue; 592 intset_scratch_union(ctx, scratch, &acc, 593 &state_closures[st->edges[ei].dst]); 594 } 595 if (acc.n) { 596 intset_sort_in_place(&acc); 597 if (ndata + acc.n > cap_data) { 598 cap_data = GROW_CAP(cap_data, 1024); 599 while (cap_data < ndata + acc.n) cap_data *= 2; 600 data = xrealloc(ctx, data, cap_data * sizeof *data); 601 } 602 memcpy(data + ndata, acc.v, acc.n * sizeof *acc.v); 603 ndata += acc.n; 604 } 605 } 606 } 607 d.off[d.ncells] = ndata; 608 xfree(ctx, acc.v); 609 d.data = data; 610 return d; 611 } 612 613 static uint16_t* dfa_compact_byte_classes(GramgenContext* ctx, Loc loc, 614 const uint16_t* trans_bytes, 615 size_t nstates, uint8_t class_of[256], 616 uint16_t* nclasses_out) { 617 /* Refine the byte partition by each state's transition column: two bytes 618 * end in the same class iff every state maps them to the same destination, 619 * matching the original column-signature comparison. */ 620 ByteColoring bc; 621 byte_color_init(&bc); 622 for (size_t st = 0; st < nstates; st++) 623 byte_color_refine_u16(&bc, &trans_bytes[st * 256]); 624 625 int class_first[256]; 626 uint16_t nclasses = 0; 627 byte_color_finish(ctx, loc, &bc, class_of, class_first, &nclasses); 628 629 uint16_t* trans = xmalloc(ctx, nstates * (size_t)nclasses * sizeof *trans); 630 for (size_t st = 0; st < nstates; st++) 631 for (uint16_t c = 0; c < nclasses; c++) 632 trans[st * (size_t)nclasses + (size_t)c] = 633 trans_bytes[st * 256 + (size_t)class_first[c]]; 634 *nclasses_out = nclasses; 635 return trans; 636 } 637 638 static uint16_t* dfa_expand_byte_classes(GramgenContext* ctx, 639 const uint8_t class_of[256], 640 const uint16_t* trans, size_t nstates, 641 uint16_t nclasses) { 642 uint16_t* out = xmalloc(ctx, nstates * 256 * sizeof *out); 643 for (size_t st = 0; st < nstates; st++) 644 for (int b = 0; b < 256; b++) 645 out[st * 256 + (size_t)b] = trans[st * (size_t)nclasses + class_of[b]]; 646 return out; 647 } 648 649 /* Accept triple for a DFA subset: the priority-winning recognizer reachable 650 * directly (no end anchor), via a `\z` (ET) zero-width edge, and via a `$` (EL) 651 * edge. UINT16_MAX = none of that kind. The end-anchor accept node sits behind 652 * a boundary edge (never in any byte subset), so its accept surfaces only here. 653 */ 654 static void byte_subset_accepts(const NfaBuilder* nfa, 655 const IntSet* state_closures, 656 const IntSet* subset, uint16_t* plain, 657 uint16_t* text, uint16_t* line) { 658 int p = 65535, t = 65535, l = 65535; 659 for (size_t i = 0; i < subset->n; i++) { 660 const NfaState* st = &nfa->states[subset->v[i]]; 661 if (st->accept >= 0 && st->accept < p) p = st->accept; 662 for (size_t e = 0; e < st->nbnd; e++) { 663 int kind = st->bnd[e].kind; 664 if (kind != NFA_BND_ET && kind != NFA_BND_EL) continue; 665 const IntSet* clo = &state_closures[st->bnd[e].dst]; 666 for (size_t k = 0; k < clo->n; k++) { 667 int a = nfa->states[clo->v[k]].accept; 668 if (a < 0) continue; 669 if (kind == NFA_BND_ET) { 670 if (a < t) t = a; 671 } else { 672 if (a < l) l = a; 673 } 674 } 675 } 676 } 677 *plain = (uint16_t)p; 678 *text = (uint16_t)t; 679 *line = (uint16_t)l; 680 } 681 682 static void byte_nfa_to_tables(GramgenContext* ctx, Loc loc, NfaBuilder* nfa, 683 int start, uint8_t class_of[256], 684 uint16_t* nclasses_out, uint16_t** trans_out, 685 uint16_t** accept_out, 686 uint16_t** accept_text_out, 687 uint16_t** accept_line_out, 688 uint16_t* nstates_out, uint16_t* start_text_out, 689 uint16_t* start_line_out) { 690 unsigned char class_first[256]; 691 uint16_t nclasses = 0; 692 nfa_byte_classes(ctx, loc, nfa, class_of, class_first, &nclasses); 693 IntSet* state_closures = nfa_state_closures(nfa); 694 IntSetScratch scratch; 695 intset_scratch_init(ctx, &scratch, nfa->nstates); 696 ByteClassDests class_dests = nfa_byte_class_dests( 697 ctx, nfa, state_closures, &scratch, nclasses, class_first); 698 699 IntSet* dfa_sets = NULL; 700 size_t nsets = 0, cap_sets = 0; 701 DfaSubsetMap subset_map = {0}; 702 dfa_subset_map_init(ctx, &subset_map); 703 704 /* Three start subsets, selected at scan time by the start-of-match context. 705 * Start anchors hang off the global start as zero-width edges; eps-closure 706 * does not cross them, so they only contribute through these seeds: 707 * interior = closure({start}) (no \A/^ satisfied) 708 * line = closure({start} ∪ ^-targets) (^ satisfied) 709 * text = closure({start} ∪ ^- and \A-targets) (text start: both fire) 710 * interior interns as state 0; the others dedup to 0 when no start anchors. 711 */ 712 IntSet interior_set = {0}, line_seed = {0}, text_seed = {0}; 713 intset_add(ctx, &interior_set, start); 714 intset_add(ctx, &line_seed, start); 715 intset_add(ctx, &text_seed, start); 716 { 717 NfaState* s0 = &nfa->states[start]; 718 for (size_t e = 0; e < s0->nbnd; e++) { 719 if (s0->bnd[e].kind == NFA_BND_BL) { 720 intset_add(ctx, &line_seed, s0->bnd[e].dst); 721 intset_add(ctx, &text_seed, s0->bnd[e].dst); 722 } else if (s0->bnd[e].kind == NFA_BND_BT) { 723 intset_add(ctx, &text_seed, s0->bnd[e].dst); 724 } 725 } 726 } 727 IntSet interior_clo = 728 cached_closure(ctx, state_closures, &scratch, &interior_set); 729 IntSet line_clo = cached_closure(ctx, state_closures, &scratch, &line_seed); 730 IntSet text_clo = cached_closure(ctx, state_closures, &scratch, &text_seed); 731 dfa_intern_subset(ctx, &subset_map, &dfa_sets, &nsets, &cap_sets, 732 &interior_clo, loc); 733 uint16_t start_line = (uint16_t)dfa_intern_subset( 734 ctx, &subset_map, &dfa_sets, &nsets, &cap_sets, &line_clo, loc); 735 uint16_t start_text = (uint16_t)dfa_intern_subset( 736 ctx, &subset_map, &dfa_sets, &nsets, &cap_sets, &text_clo, loc); 737 xfree(ctx, interior_clo.v); 738 xfree(ctx, line_clo.v); 739 xfree(ctx, text_clo.v); 740 xfree(ctx, interior_set.v); 741 xfree(ctx, line_seed.v); 742 xfree(ctx, text_seed.v); 743 744 AcceptSigMap sigmap = {0}; 745 uint16_t* trans = NULL; 746 uint16_t* accept = NULL; 747 size_t row_cap = 0, accept_cap = 0; 748 size_t qpos = 0; 749 IntSet dest = {0}; /* reused across all cells */ 750 while (qpos < nsets) { 751 IntSet subset = dfa_sets[qpos++]; 752 if (qpos > accept_cap) { 753 accept_cap = GROW_CAP(accept_cap, 16); 754 while (accept_cap < qpos) accept_cap *= 2; 755 accept = xrealloc(ctx, accept, accept_cap * sizeof *accept); 756 } 757 uint16_t ap, at, al; 758 byte_subset_accepts(nfa, state_closures, &subset, &ap, &at, &al); 759 accept[qpos - 1] = accept_sig_intern(ctx, &sigmap, ap, at, al); 760 if (qpos > row_cap) { 761 row_cap = GROW_CAP(row_cap, 16); 762 while (row_cap < qpos) row_cap *= 2; 763 trans = xrealloc(ctx, trans, row_cap * (size_t)nclasses * sizeof *trans); 764 } 765 uint16_t* row = &trans[(qpos - 1) * (size_t)nclasses]; 766 for (uint16_t cls = 0; cls < nclasses; cls++) { 767 dest.n = 0; 768 intset_scratch_reset(&scratch); 769 for (size_t si = 0; si < subset.n; si++) { 770 size_t cell = (size_t)subset.v[si] * (size_t)nclasses + cls; 771 size_t lo = class_dests.off[cell], hi = class_dests.off[cell + 1]; 772 intset_scratch_union_slice(ctx, &scratch, &dest, class_dests.data + lo, 773 hi - lo); 774 } 775 if (dest.n) { 776 intset_sort_in_place(&dest); 777 row[cls] = (uint16_t)dfa_intern_subset(ctx, &subset_map, &dfa_sets, 778 &nsets, &cap_sets, &dest, loc); 779 } else { 780 row[cls] = UINT16_MAX; 781 } 782 } 783 } 784 xfree(ctx, dest.v); 785 786 byte_class_dests_free(ctx, &class_dests); 787 788 uint16_t nstates = (uint16_t)nsets; 789 uint16_t starts[2] = {start_line, start_text}; 790 dfa_minimize(ctx, loc, &trans, &accept, &nstates, nclasses, starts, 2); 791 792 uint16_t* min_trans_bytes = 793 dfa_expand_byte_classes(ctx, class_of, trans, nstates, nclasses); 794 trans = dfa_compact_byte_classes(ctx, loc, min_trans_bytes, nstates, class_of, 795 &nclasses); 796 uint16_t roots[3] = {0, starts[0], starts[1]}; 797 dfa_canonical_relabel(ctx, trans, accept, nstates, nclasses, roots, 3, starts, 798 2); 799 800 /* Expand the per-state accept signature ids back into the three accept 801 * tables consumed by the runtime. Collapse an all-none end-context table to 802 * NULL so grammars without that anchor kind emit byte-identically. */ 803 uint16_t* accept_text = 804 xmalloc(ctx, (nstates ? nstates : 1) * sizeof *accept_text); 805 uint16_t* accept_line = 806 xmalloc(ctx, (nstates ? nstates : 1) * sizeof *accept_line); 807 int any_text = 0, any_line = 0; 808 for (uint16_t s = 0; s < nstates; s++) { 809 uint16_t sig = accept[s]; 810 if (sig == UINT16_MAX) { 811 accept[s] = UINT16_MAX; 812 accept_text[s] = UINT16_MAX; 813 accept_line[s] = UINT16_MAX; 814 } else { 815 AcceptTriple tr = sigmap.triples[sig]; 816 accept[s] = tr.plain; 817 accept_text[s] = tr.text; 818 accept_line[s] = tr.line; 819 if (tr.text != UINT16_MAX) any_text = 1; 820 if (tr.line != UINT16_MAX) any_line = 1; 821 } 822 } 823 accept_sig_map_free(ctx, &sigmap); 824 if (!any_text) { 825 xfree(ctx, accept_text); 826 accept_text = NULL; 827 } 828 if (!any_line) { 829 xfree(ctx, accept_line); 830 accept_line = NULL; 831 } 832 833 *nclasses_out = nclasses; 834 *trans_out = trans; 835 *accept_out = accept; 836 *accept_text_out = accept_text; 837 *accept_line_out = accept_line; 838 *nstates_out = nstates; 839 *start_text_out = starts[1]; /* remapped through minimize + relabel */ 840 *start_line_out = starts[0]; 841 } 842 843 static uint64_t lex_hash_mix(uint64_t h, uint64_t value) { 844 h ^= value; 845 h *= KIT_GRAM_HASH_PRIME; 846 return h; 847 } 848 849 static uint64_t lex_hash_str(uint64_t h, Str s) { 850 h = lex_hash_mix(h, (uint64_t)s.len); 851 for (size_t i = 0; i < s.len; i++) h = lex_hash_mix(h, (unsigned char)s.s[i]); 852 return h; 853 } 854 855 static uint64_t lex_alt_hash(AstLexAlt* alt); 856 857 static uint64_t lex_node_hash(AstLexNode* node) { 858 uint64_t h = lex_hash_mix(KIT_GRAM_HASH_OFFSET_BASIS, (uint64_t)node->kind); 859 switch (node->kind) { 860 case LEX_LITERAL: 861 h = lex_hash_str(h, node->value); 862 return lex_hash_str(h, node->scalar_value); 863 case LEX_CLASS: 864 case LEX_PROP: 865 case LEX_ANCHOR: 866 return lex_hash_str(h, node->value); 867 case LEX_ANY: 868 return h; 869 case LEX_GROUP: 870 case LEX_OPT: 871 case LEX_REP: 872 case LEX_REPEAT: 873 return lex_hash_mix(h, lex_alt_hash(node->alts)); 874 case LEX_NAME: 875 return lex_hash_str(h, node->value); 876 } 877 return h; 878 } 879 880 static uint64_t lex_seq_hash(AstLexSeq* seq) { 881 uint64_t h = lex_hash_mix(KIT_GRAM_HASH_OFFSET_BASIS, seq->nitems); 882 for (size_t i = 0; i < seq->nitems; i++) 883 h = lex_hash_mix(h, lex_node_hash(seq->items[i])); 884 return h; 885 } 886 887 static uint64_t lex_alt_hash(AstLexAlt* alt) { 888 uint64_t h = lex_hash_mix(KIT_GRAM_HASH_OFFSET_BASIS, alt->nseqs); 889 for (size_t i = 0; i < alt->nseqs; i++) 890 h = lex_hash_mix(h, lex_seq_hash(alt->seqs[i])); 891 return h; 892 } 893 894 static int lex_alt_equal(AstLexAlt* a, AstLexAlt* b); 895 896 static int lex_node_equal(AstLexNode* a, AstLexNode* b) { 897 if (a->kind != b->kind) return 0; 898 switch (a->kind) { 899 case LEX_LITERAL: 900 return str_eq(a->value, b->value) && 901 str_eq(a->scalar_value, b->scalar_value); 902 case LEX_CLASS: 903 case LEX_PROP: 904 case LEX_ANCHOR: 905 return str_eq(a->value, b->value); 906 case LEX_ANY: 907 return 1; 908 case LEX_GROUP: 909 case LEX_OPT: 910 case LEX_REP: 911 case LEX_REPEAT: 912 return lex_alt_equal(a->alts, b->alts); 913 case LEX_NAME: 914 return str_eq(a->value, b->value); 915 } 916 return 0; 917 } 918 919 static int lex_seq_equal(AstLexSeq* a, AstLexSeq* b) { 920 if (a->nitems != b->nitems) return 0; 921 for (size_t i = 0; i < a->nitems; i++) 922 if (!lex_node_equal(a->items[i], b->items[i])) return 0; 923 return 1; 924 } 925 926 static int lex_alt_equal(AstLexAlt* a, AstLexAlt* b) { 927 if (a->nseqs != b->nseqs) return 0; 928 for (size_t i = 0; i < a->nseqs; i++) 929 if (!lex_seq_equal(a->seqs[i], b->seqs[i])) return 0; 930 return 1; 931 } 932 933 static size_t* unique_recognizer_indices(GramgenContext* ctx, 934 LexRecognizer* recognizers, 935 size_t nrecognizers, 936 size_t* nunique_out) { 937 size_t* indices = xmalloc(ctx, nrecognizers * sizeof *indices); 938 uint64_t* hashes = xmalloc(ctx, nrecognizers * sizeof *hashes); 939 int* next = xmalloc(ctx, nrecognizers * sizeof *next); 940 size_t nbuckets = 1024; 941 while (nbuckets < nrecognizers * 2) nbuckets *= 2; 942 int* buckets = xmalloc(ctx, nbuckets * sizeof *buckets); 943 for (size_t i = 0; i < nbuckets; i++) buckets[i] = -1; 944 945 size_t nunique = 0; 946 for (size_t i = 0; i < nrecognizers; i++) { 947 /* Anchors are stripped from `alts` into flags before this runs, so they 948 * must join the key: `\A "if"` and `"if"` share a body but are distinct 949 * recognizers (different zero-width edges) and must not be merged. */ 950 uint64_t hash = lex_alt_hash(recognizers[i].alts); 951 hash = lex_hash_mix(hash, (uint64_t)recognizers[i].start_anchor); 952 hash = lex_hash_mix(hash, (uint64_t)recognizers[i].end_anchor); 953 size_t bucket = (size_t)(hash & (uint64_t)(nbuckets - 1)); 954 int found = 0; 955 for (int pos = buckets[bucket]; pos >= 0; pos = next[pos]) { 956 size_t old = indices[pos]; 957 if (hashes[pos] == hash && 958 recognizers[i].start_anchor == recognizers[old].start_anchor && 959 recognizers[i].end_anchor == recognizers[old].end_anchor && 960 lex_alt_equal(recognizers[i].alts, recognizers[old].alts)) { 961 found = 1; 962 break; 963 } 964 } 965 if (found) continue; 966 indices[nunique] = i; 967 hashes[nunique] = hash; 968 next[nunique] = buckets[bucket]; 969 buckets[bucket] = (int)nunique; 970 nunique++; 971 } 972 973 *nunique_out = nunique; 974 return indices; 975 } 976 977 static int recognizer_cmp(const void* a, const void* b) { 978 const LexRecognizer* x = a; 979 const LexRecognizer* y = b; 980 if (x->loc.line != y->loc.line) return x->loc.line < y->loc.line ? -1 : 1; 981 if (x->loc.col != y->loc.col) return x->loc.col < y->loc.col ? -1 : 1; 982 return (x->seq > y->seq) - (x->seq < y->seq); 983 } 984 985 /* ---- Explicit keyword extraction (%keywords) ---------------------------- 986 * Keywords are declared, not discovered: each %keywords entry contributes a 987 * (lexeme -> token) pair under a host kind and is kept out of the DFA. The 988 * "shadow check" is replaced by running each keyword's bytes through the final 989 * generated DFA and requiring the host to win the whole span; lookup uses a 990 * minimal perfect hash (CHD). See doc/DESIGN.md "Keyword extraction". */ 991 992 /* Longest-match over the built byte DFA. Returns the winning recognizer index 993 * (or -1) and the matched length, mirroring the runtime scan. */ 994 static int keyword_dfa_match(const LexDFA* dfa, const unsigned char* s, 995 size_t len, size_t* match_len) { 996 uint16_t state = 0; 997 int best_acc = -1; 998 size_t best_len = 0; 999 for (size_t i = 0; i < len; i++) { 1000 uint16_t cls = dfa->class_of[s[i]]; 1001 uint16_t next = dfa->trans[(size_t)state * dfa->nclasses + cls]; 1002 if (next == UINT16_MAX) break; 1003 state = next; 1004 uint16_t acc = dfa->accept[state]; 1005 if (acc != UINT16_MAX) { 1006 best_acc = (int)acc; 1007 best_len = i + 1; 1008 } 1009 } 1010 *match_len = best_len; 1011 return best_acc; 1012 } 1013 1014 /* Shadowed string-literal check. A string-literal token (`%token IF = "if"`, an 1015 * `"if"` parser literal, etc.) only reaches the token stream if the finished 1016 * DFA actually returns it for its own bytes. A broader recognizer declared at 1017 * lower (earlier) source priority — classically an IDENT rule placed before the 1018 * keyword — wins the same-length tie, so the literal token is never produced 1019 * and the grammar is silently miscompiled. We catch that by running every 1020 * literal recognizer's bytes back through the built DFA and requiring it (or a 1021 * recognizer with the same token kind) to win the whole span. Literals 1022 * extracted into a %keywords block carry no DFA recognizer (the host recovers 1023 * them by lexeme lookup, validated in build_group_keyword_tables), so they are 1024 * not iterated here and never false-positive. */ 1025 static void check_literal_shadowing(GramgenContext* ctx, const LexDFA* dfa) { 1026 for (size_t i = 0; i < dfa->nrecognizers; i++) { 1027 const LexRecognizer* rec = &dfa->recognizers[i]; 1028 if (rec->skip || !rec->has_literal_key) continue; 1029 size_t mlen = 0; 1030 int acc = keyword_dfa_match(dfa, (const unsigned char*)rec->literal_key.s, 1031 rec->literal_key.len, &mlen); 1032 if (acc >= 0 && mlen == rec->literal_key.len && 1033 dfa->recognizers[acc].tok == rec->tok) 1034 continue; /* the literal wins its own span: fine */ 1035 if (acc >= 0 && mlen == rec->literal_key.len) 1036 kit_gram_error( 1037 ctx, rec->loc, 1038 "string literal token %s (\"%.*s\") is shadowed by %s and can " 1039 "never be produced; declare it before the broader rule, or list " 1040 "it in a %%keywords block", 1041 rec->name, (int)rec->literal_key.len, rec->literal_key.s, 1042 dfa->recognizers[acc].name); 1043 else 1044 kit_gram_error( 1045 ctx, rec->loc, 1046 "string literal token %s (\"%.*s\") is not recognized by its own " 1047 "lexer and can never be produced; declare it before the broader " 1048 "rule, or list it in a %%keywords block", 1049 rec->name, (int)rec->literal_key.len, rec->literal_key.s); 1050 } 1051 } 1052 1053 /* Round up to a power of two (>= 1) so the runtime indexes seed buckets and MPH 1054 * slots with a mask instead of a modulo on every keyword lookup. */ 1055 static size_t kw_pow2_ceil(size_t x) { 1056 size_t p = 1; 1057 while (p < x) p <<= 1; 1058 return p; 1059 } 1060 1061 /* Build a perfect hash (CHD) over n keywords for one host. seeds[r] are bucket 1062 * displacements; slots[m] place each keyword at its perfect position. r 1063 * (nseeds) and m (nslots) are powers of two so the runtime masks rather than 1064 * divides; m may exceed n, leaving empty (literal.s == NULL) slots. The 1065 * construction is deterministic (bucket order, seed search) so C and Python 1066 * emit identical tables. */ 1067 static void build_keyword_mph(GramgenContext* ctx, Loc loc, int host, 1068 const LexKeyword* kws, size_t n, 1069 LexKeywordTable* out) { 1070 size_t r_nat = (n + 1) / 2; 1071 if (r_nat < 1) r_nat = 1; 1072 size_t r = kw_pow2_ceil(r_nat); /* nseeds: power of two (bucket mask) */ 1073 size_t m = 1074 kw_pow2_ceil(n ? n : 1); /* nslots: power of two >= n (slot mask) */ 1075 size_t* bucket_of = xmalloc(ctx, n * sizeof *bucket_of); 1076 size_t* bsize = xcalloc(ctx, r, sizeof *bsize); 1077 for (size_t i = 0; i < n; i++) { 1078 uint64_t h = kit_gram_lex_kw_hash64(0, (const unsigned char*)kws[i].literal.s, 1079 kws[i].literal.len); 1080 bucket_of[i] = (size_t)(h & (uint64_t)(r - 1)); 1081 bsize[bucket_of[i]]++; 1082 } 1083 /* Process buckets largest-first (ties by ascending index) via insertion sort. 1084 */ 1085 size_t* order = xmalloc(ctx, r * sizeof *order); 1086 for (size_t i = 0; i < r; i++) order[i] = i; 1087 for (size_t i = 1; i < r; i++) { 1088 size_t key = order[i], j = i; 1089 while (j > 0 && 1090 (bsize[order[j - 1]] < bsize[key] || 1091 (bsize[order[j - 1]] == bsize[key] && order[j - 1] > key))) { 1092 order[j] = order[j - 1]; 1093 j--; 1094 } 1095 order[j] = key; 1096 } 1097 1098 LexKeyword* slots = 1099 xcalloc(ctx, m, sizeof *slots); /* literal.s == NULL means empty */ 1100 uint8_t* taken = xcalloc(ctx, m, 1); 1101 uint32_t* seeds = xcalloc(ctx, r, sizeof *seeds); 1102 size_t* cand = xmalloc( 1103 ctx, (n ? n : 1) * sizeof *cand); /* candidate slots within a bucket */ 1104 1105 for (size_t oi = 0; oi < r; oi++) { 1106 size_t b = order[oi]; 1107 if (bsize[b] == 0) continue; /* unused bucket: seed stays 0 */ 1108 for (uint32_t d = 0;; d++) { 1109 if (d > (1u << 20)) 1110 kit_gram_error(ctx, loc, "could not build keyword hash table"); 1111 int ok = 1; 1112 size_t cnt = 0; 1113 for (size_t i = 0; i < n && ok; i++) { 1114 if (bucket_of[i] != b) continue; 1115 uint64_t h = kit_gram_lex_kw_hash64( 1116 d, (const unsigned char*)kws[i].literal.s, kws[i].literal.len); 1117 size_t slot = (size_t)(h & (uint64_t)(m - 1)); 1118 if (taken[slot]) { 1119 ok = 0; 1120 break; 1121 } 1122 for (size_t t = 0; t < cnt; t++) 1123 if (cand[t] == slot) { 1124 ok = 0; 1125 break; 1126 } 1127 if (ok) cand[cnt++] = slot; 1128 } 1129 if (ok) { 1130 seeds[b] = d; 1131 size_t ci = 0; 1132 for (size_t i = 0; i < n; i++) { 1133 if (bucket_of[i] != b) continue; 1134 slots[cand[ci++]] = kws[i]; 1135 } 1136 for (size_t t = 0; t < cnt; t++) taken[cand[t]] = 1; 1137 break; 1138 } 1139 } 1140 } 1141 1142 out->host = host; 1143 out->slots = slots; 1144 out->nslots = m; 1145 out->seeds = seeds; 1146 out->nseeds = r; 1147 out->min_len = n ? kws[0].literal.len : 0; 1148 out->max_len = out->min_len; 1149 for (size_t i = 1; i < n; i++) { 1150 if (kws[i].literal.len < out->min_len) out->min_len = kws[i].literal.len; 1151 if (kws[i].literal.len > out->max_len) out->max_len = kws[i].literal.len; 1152 } 1153 1154 xfree(ctx, cand); 1155 xfree(ctx, taken); 1156 xfree(ctx, order); 1157 xfree(ctx, bsize); 1158 xfree(ctx, bucket_of); 1159 } 1160 1161 static int kw_host_cmp(const void* pa, const void* pb) { 1162 int a = ((const LexKeywordTable*)pa)->host; 1163 int b = ((const LexKeywordTable*)pb)->host; 1164 return (a > b) - (a < b); 1165 } 1166 1167 /* For one lexer group, resolve each %keywords host to a recognizer in the built 1168 * DFA, validate every keyword tokenizes to that host over its whole span, and 1169 * build one MPH table per host (sorted by host kind). */ 1170 static void build_group_keyword_tables(Builder* b, LexDFA* dfa, 1171 const char* group_name) { 1172 GramgenContext* ctx = b->ctx; 1173 /* Distinct hosts in this group, in first-seen order. */ 1174 char** hosts = NULL; 1175 size_t nhosts = 0, cap = 0; 1176 for (size_t i = 0; i < b->nkw_bindings; i++) { 1177 KeywordBinding* kb = &b->kw_bindings[i]; 1178 if (strcmp(kb->group, group_name) != 0) continue; 1179 int seen = 0; 1180 for (size_t h = 0; h < nhosts; h++) 1181 if (strcmp(hosts[h], kb->host) == 0) { 1182 seen = 1; 1183 break; 1184 } 1185 if (seen) continue; 1186 if (nhosts == cap) { 1187 cap = GROW_CAP(cap, 4); 1188 hosts = xrealloc(ctx, hosts, cap * sizeof *hosts); 1189 } 1190 hosts[nhosts++] = kb->host; 1191 } 1192 if (!nhosts) { 1193 xfree(ctx, hosts); 1194 return; 1195 } 1196 1197 LexKeywordTable* tables = xcalloc(ctx, nhosts, sizeof *tables); 1198 for (size_t h = 0; h < nhosts; h++) { 1199 const char* host_name = hosts[h]; 1200 int host_kind = -1; 1201 Loc host_loc = dfa->loc; 1202 for (size_t ri = 0; ri < dfa->nrecognizers; ri++) { 1203 LexRecognizer* rec = &dfa->recognizers[ri]; 1204 if (!rec->skip && strcmp(rec->name, host_name) == 0) { 1205 host_kind = rec->tok; 1206 break; 1207 } 1208 } 1209 LexKeyword* kws = NULL; 1210 size_t n = 0, kcap = 0; 1211 for (size_t i = 0; i < b->nkw_bindings; i++) { 1212 KeywordBinding* kb = &b->kw_bindings[i]; 1213 if (strcmp(kb->group, group_name) != 0 || 1214 strcmp(kb->host, host_name) != 0) 1215 continue; 1216 if (host_kind < 0 && n == 0) host_loc = kb->loc; 1217 if (host_kind >= 0) { 1218 size_t mlen = 0; 1219 int acc = keyword_dfa_match(dfa, (const unsigned char*)kb->literal.s, 1220 kb->literal.len, &mlen); 1221 if (acc < 0 || mlen != kb->literal.len) 1222 kit_gram_error(ctx, kb->loc, 1223 "keyword \"%.*s\" is not matched by host %s", 1224 (int)kb->literal.len, kb->literal.s, host_name); 1225 if (dfa->recognizers[acc].tok != host_kind) 1226 kit_gram_error( 1227 ctx, kb->loc, 1228 "keyword \"%.*s\" is matched by %s, not declared host %s", 1229 (int)kb->literal.len, kb->literal.s, dfa->recognizers[acc].name, 1230 host_name); 1231 } 1232 if (n == kcap) { 1233 kcap = GROW_CAP(kcap, 8); 1234 kws = xrealloc(ctx, kws, kcap * sizeof *kws); 1235 } 1236 kws[n].literal = kb->literal; 1237 kws[n].tok = kb->tok; 1238 n++; 1239 } 1240 if (host_kind < 0) 1241 kit_gram_error(ctx, host_loc, "unknown %%keywords host %s in lexer %s", 1242 host_name, group_name); 1243 build_keyword_mph(ctx, host_loc, host_kind, kws, n, &tables[h]); 1244 xfree(ctx, kws); 1245 } 1246 qsort(tables, nhosts, sizeof *tables, kw_host_cmp); 1247 dfa->keyword_tables = tables; 1248 dfa->nkeyword_tables = nhosts; 1249 xfree(ctx, hosts); 1250 } 1251 1252 static LexDFA* compile_lexer(GramgenContext* ctx, const char* name, 1253 LexRecognizer* recognizers, size_t nrecognizers, 1254 KitGramLexInputMode input, Loc loc) { 1255 if (!nrecognizers) 1256 kit_gram_error(ctx, loc, "generated lexer has no recognizers"); 1257 if (nrecognizers >= 65535) 1258 kit_gram_error(ctx, loc, "too many lexer recognizers"); 1259 1260 uint8_t class_of[256]; 1261 uint16_t nclasses = 0; 1262 uint16_t nstates = 0; 1263 uint16_t* trans = NULL; 1264 uint16_t* accept = NULL; 1265 uint16_t* accept_text = NULL; 1266 uint16_t* accept_line = NULL; 1267 uint16_t start_text = 0, start_line = 0; 1268 1269 for (size_t i = 0; i < nrecognizers; i++) { 1270 if (lex_alt_nullable(recognizers[i].alts)) 1271 kit_gram_error(ctx, recognizers[i].loc, 1272 "lexer rule %s can match empty input", recognizers[i].name); 1273 } 1274 size_t ncompile = 0; 1275 size_t* compile_indices = 1276 unique_recognizer_indices(ctx, recognizers, nrecognizers, &ncompile); 1277 1278 if (input == KIT_GRAM_LEX_INPUT_UTF8) { 1279 #ifndef KIT_GRAM_NO_UNICODE 1280 kit_gram_compile_lexer_utf8(ctx, loc, recognizers, compile_indices, ncompile, 1281 class_of, &nclasses, &trans, &nstates, &accept, 1282 &accept_text, &accept_line, &start_text, 1283 &start_line); 1284 #else 1285 /* Unreachable: kit_gram_prepare_lexer rejects %lex :utf8 in this build. */ 1286 kit_gram_error(ctx, loc, 1287 "utf8 mode is disabled in this build (KIT_GRAM_NO_UNICODE)"); 1288 #endif 1289 } else { 1290 NfaBuilder nfa = {.ctx = ctx}; 1291 int start = nfa_new_state(&nfa); 1292 for (size_t i = 0; i < ncompile; i++) { 1293 size_t rec_idx = compile_indices[i]; 1294 LexRecognizer* rec = &recognizers[rec_idx]; 1295 NfaFrag frag = nfa_from_lex_alt(&nfa, rec->alts); 1296 /* Start anchor: zero-width edge from the global start (selects an 1297 * alternate start state); otherwise a plain eps edge. */ 1298 if (rec->start_anchor == KIT_GRAM_LEX_ANCHOR_TEXT) 1299 nfa_bnd(&nfa, start, NFA_BND_BT, frag.start); 1300 else if (rec->start_anchor == KIT_GRAM_LEX_ANCHOR_LINE) 1301 nfa_bnd(&nfa, start, NFA_BND_BL, frag.start); 1302 else 1303 nfa_eps(&nfa, start, frag.start); 1304 /* End anchor: zero-width edge from the body end to a terminal accept 1305 * node (surfaced via the end-context accept tables); otherwise the 1306 * body end is itself the accept. */ 1307 if (rec->end_anchor == KIT_GRAM_LEX_ANCHOR_TEXT) { 1308 int acc = nfa_new_state(&nfa); 1309 nfa.states[acc].accept = (int)rec_idx; 1310 nfa_bnd(&nfa, frag.end, NFA_BND_ET, acc); 1311 } else if (rec->end_anchor == KIT_GRAM_LEX_ANCHOR_LINE) { 1312 int acc = nfa_new_state(&nfa); 1313 nfa.states[acc].accept = (int)rec_idx; 1314 nfa_bnd(&nfa, frag.end, NFA_BND_EL, acc); 1315 } else { 1316 nfa.states[frag.end].accept = (int)rec_idx; 1317 } 1318 } 1319 byte_nfa_to_tables(ctx, loc, &nfa, start, class_of, &nclasses, &trans, 1320 &accept, &accept_text, &accept_line, &nstates, 1321 &start_text, &start_line); 1322 } 1323 1324 LexDFA* dfa = xcalloc(ctx, 1, sizeof *dfa); 1325 if (!dfa) die_oom(ctx); 1326 dfa->name = (char*)name; 1327 dfa->loc = loc; 1328 dfa->recognizers = recognizers; 1329 dfa->nrecognizers = nrecognizers; 1330 dfa->input = input; 1331 memcpy(dfa->class_of, class_of, sizeof dfa->class_of); 1332 dfa->nclasses = nclasses; 1333 dfa->trans = trans; 1334 dfa->nstates = nstates; 1335 dfa->accept = accept; 1336 dfa->accept_text = accept_text; 1337 dfa->accept_line = accept_line; 1338 dfa->start_text = start_text; 1339 dfa->start_line = start_line; 1340 return dfa; 1341 } 1342 1343 static void append_recognizer(GramgenContext* ctx, LexRecognizer** recs, 1344 size_t* n, size_t* cap, LexRecognizer rec) { 1345 if (*n == *cap) { 1346 *cap = GROW_CAP(*cap, 16); 1347 *recs = xrealloc(ctx, *recs, *cap * sizeof **recs); 1348 } 1349 (*recs)[(*n)++] = rec; 1350 } 1351 1352 typedef struct { 1353 char* name; 1354 Loc loc; 1355 KitGramLexInputMode mode; 1356 LexRecognizer* recs; 1357 size_t nrecs, cap_recs; 1358 NameIndexMap names; 1359 /* %machine only: the block's %def lines (LEX_LINE_DEF), kept so a `[ … ]` 1360 * symbol set can reference a set-valued %def by lowercase name. */ 1361 AstLexLine** sets; 1362 size_t nsets, cap_sets; 1363 } LexGroup; 1364 1365 static int lex_name_is_main(const char* name) { 1366 return strcmp(name, "main") == 0; 1367 } 1368 1369 static LexGroup* find_lex_group(LexGroup* groups, size_t ngroups, 1370 const char* name) { 1371 for (size_t i = 0; i < ngroups; i++) 1372 if (strcmp(groups[i].name, name) == 0) return &groups[i]; 1373 return NULL; 1374 } 1375 1376 static LexGroup* append_lex_group(Builder* b, LexGroup** groups, 1377 size_t* ngroups, size_t* cap_groups, 1378 AstLexBlock* block) { 1379 if (*ngroups == *cap_groups) { 1380 *cap_groups = GROW_CAP(*cap_groups, 4); 1381 *groups = xrealloc(b->ctx, *groups, *cap_groups * sizeof **groups); 1382 } 1383 LexGroup* group = &(*groups)[(*ngroups)++]; 1384 memset(group, 0, sizeof *group); 1385 group->name = block->name; 1386 group->loc = block->loc; 1387 group->mode = block->mode; 1388 /* Parser-literal exact-match recognizers (the TOK_* punctuation/keywords the 1389 * grammar spells inline) feed the parser, and only the main lexer feeds the 1390 * parser. Named sub-lexers re-scan a token's payload bytes and never produce 1391 * these kinds, so injecting the literals there is both pointless and harmful: 1392 * a catch-all sub-lexer rule (e.g. [^"\\]+) would shadow every shared 1393 * literal. So the literals go into the main lexer only. Token machines 1394 * (abstract alphabet) never carry these either. */ 1395 if (block->mode != KIT_GRAM_LEX_INPUT_TOKENS && lex_name_is_main(block->name)) 1396 for (size_t i = 0; i < b->nliteral_recs; i++) 1397 append_recognizer(b->ctx, &group->recs, &group->nrecs, &group->cap_recs, 1398 b->literal_recs[i]); 1399 return group; 1400 } 1401 1402 /* A one-literal lex alternative (mirrors single_literal_lex_alt in 1403 * kit_gram_ll1.c). `value` carries the literal bytes for the byte NFA; 1404 * `scalar_value` the same bytes for the UTF-8 scalar NFA (it decodes them as 1405 * UTF-8), so a multi-byte keyword like "café" or "λ" folds correctly in both 1406 * modes. */ 1407 static AstLexAlt* single_literal_alt(GramgenContext* ctx, Str lit, Loc loc) { 1408 AstLexNode* node = ast_lex_node_new(ctx, LEX_LITERAL, loc); 1409 node->value = str_dup_len(ctx, lit.s, lit.len); 1410 node->scalar_value = str_dup_len(ctx, lit.s, lit.len); 1411 AstLexSeq* seq = ast_lex_seq_new(ctx, loc); 1412 ast_lex_seq_append(seq, node); 1413 AstLexAlt* alt = ast_lex_alt_new(ctx, loc); 1414 ast_lex_alt_append(alt, seq); 1415 return alt; 1416 } 1417 1418 /* Standalone mode folds %keywords straight into the DFA instead of extracting 1419 * them into an MPH table: synthesize one literal recognizer per keyword binding 1420 * in this group, at top priority (loc {0,0}, which sorts before every real 1421 * recognizer at line >= 1) so it out-ranks its host on the same-length tie that 1422 * decides `if` vs an IDENT host. byte_subset_accepts then stamps the keyword's 1423 * own (lower) accept index onto the DFA state reached by its bytes, so `if` 1424 * reaches an accepting state emitting TOK_IF with no second hash pass; longest 1425 * match still gives `iffy` -> IDENT (the length-4 IDENT accept beats length-2). 1426 */ 1427 static void synthesize_group_keywords(Builder* b, LexGroup* group) { 1428 GramgenContext* ctx = b->ctx; 1429 for (size_t i = 0; i < b->nkw_bindings; i++) { 1430 KeywordBinding* kb = &b->kw_bindings[i]; 1431 if (strcmp(kb->group, group->name) != 0) continue; 1432 LexRecognizer rec; 1433 memset(&rec, 0, sizeof rec); 1434 rec.name = b->tokens[kb->tok].name; 1435 rec.loc = (Loc){.path = kb->loc.path, .line = 0, .col = 0}; 1436 rec.alts = single_literal_alt(ctx, kb->literal, kb->loc); 1437 rec.tok = kb->tok; 1438 rec.skip = 0; 1439 rec.seq = kit_gram_next_rec_seq(b); 1440 rec.has_literal_key = 1; 1441 rec.literal_key = str_dup_len(ctx, kb->literal.s, kb->literal.len); 1442 append_recognizer(ctx, &group->recs, &group->nrecs, &group->cap_recs, rec); 1443 } 1444 } 1445 1446 static void append_lex_dfa(Builder* b, LexDFA* dfa) { 1447 if (b->nlex_dfas == b->cap_lex_dfas) { 1448 b->cap_lex_dfas = GROW_CAP(b->cap_lex_dfas, 2); 1449 b->lex_dfas = 1450 xrealloc(b->ctx, b->lex_dfas, b->cap_lex_dfas * sizeof *b->lex_dfas); 1451 } 1452 b->lex_dfas[b->nlex_dfas++] = *dfa; 1453 } 1454 1455 static void append_machine(Builder* b, LexDFA* dfa) { 1456 if (b->nmachines == b->cap_machines) { 1457 b->cap_machines = GROW_CAP(b->cap_machines, 2); 1458 b->machines = 1459 xrealloc(b->ctx, b->machines, b->cap_machines * sizeof *b->machines); 1460 } 1461 b->machines[b->nmachines++] = *dfa; 1462 } 1463 1464 /* ---- Tier-1 edge anchor extraction -------------------------------------- 1465 * Peel a leading start anchor (\A/^) and trailing end anchor (\z/$) off a 1466 * recognizer's single top-level sequence into per-recognizer flags, then reject 1467 * any anchor that survives (it was mid-pattern or in a multi-alternative top 1468 * level). Shared by the byte and utf8 pipelines since it runs on the AST. */ 1469 static int anchor_tag(const AstLexNode* n) { 1470 return n->kind == LEX_ANCHOR && n->value.len ? (unsigned char)n->value.s[0] 1471 : 0; 1472 } 1473 1474 static int anchor_is_start(const AstLexNode* n) { 1475 int t = anchor_tag(n); 1476 return t == 'A' || t == '^'; 1477 } 1478 1479 static int anchor_is_end(const AstLexNode* n) { 1480 int t = anchor_tag(n); 1481 return t == 'z' || t == '$'; 1482 } 1483 1484 static int anchor_value(const AstLexNode* n) { 1485 int t = anchor_tag(n); 1486 return t == '^' || t == '$' ? KIT_GRAM_LEX_ANCHOR_LINE : KIT_GRAM_LEX_ANCHOR_TEXT; 1487 } 1488 1489 static int lex_alt_has_anchor(AstLexAlt* alt); 1490 1491 static int lex_seq_has_anchor(AstLexSeq* seq) { 1492 for (size_t i = 0; i < seq->nitems; i++) { 1493 AstLexNode* n = seq->items[i]; 1494 if (n->kind == LEX_ANCHOR) return 1; 1495 if ((n->kind == LEX_GROUP || n->kind == LEX_OPT || n->kind == LEX_REP) && 1496 lex_alt_has_anchor(n->alts)) 1497 return 1; 1498 } 1499 return 0; 1500 } 1501 1502 static int lex_alt_has_anchor(AstLexAlt* alt) { 1503 for (size_t i = 0; i < alt->nseqs; i++) 1504 if (lex_seq_has_anchor(alt->seqs[i])) return 1; 1505 return 0; 1506 } 1507 1508 static void extract_recognizer_anchors(GramgenContext* ctx, 1509 LexRecognizer* rec) { 1510 AstLexAlt* alt = rec->alts; 1511 if (alt->nseqs == 1) { 1512 AstLexSeq* seq = alt->seqs[0]; 1513 if (seq->nitems && anchor_is_start(seq->items[0])) { 1514 rec->start_anchor = anchor_value(seq->items[0]); 1515 memmove(&seq->items[0], &seq->items[1], 1516 (seq->nitems - 1) * sizeof seq->items[0]); 1517 seq->nitems--; 1518 } 1519 if (seq->nitems && anchor_is_end(seq->items[seq->nitems - 1])) { 1520 rec->end_anchor = anchor_value(seq->items[seq->nitems - 1]); 1521 seq->nitems--; 1522 } 1523 } 1524 if (lex_alt_has_anchor(alt)) 1525 kit_gram_error(ctx, rec->loc, 1526 "mid-pattern assertions are not supported (Tier 2)"); 1527 } 1528 1529 /* ---------------- front-end desugaring on the lex AST ---------------- 1530 * A single pass, run before NFA construction and shared by the byte and scalar 1531 * pipelines, that (1) inlines `%def` fragment references and (2) expands 1532 * counted / `+` repetitions. After it runs, no LEX_REPEAT or LEX_NAME nodes 1533 * remain and 1534 * `%def` lines are skipped when building recognizers. Shorthand classes (\d 1535 * etc.) are lowered earlier (to `[\d]`) and expanded by the class machinery, so 1536 * they need no work here. */ 1537 1538 static AstLexAlt* lex_alt_clone(GramgenContext* ctx, const AstLexAlt* src); 1539 1540 static AstLexNode* lex_node_clone(GramgenContext* ctx, const AstLexNode* src) { 1541 AstLexNode* n = ast_lex_node_new(ctx, src->kind, src->loc); 1542 n->value = src->value; /* immutable interned/arena strings: shared */ 1543 n->scalar_value = src->scalar_value; 1544 if (src->alts) n->alts = lex_alt_clone(ctx, src->alts); 1545 return n; 1546 } 1547 1548 static AstLexSeq* lex_seq_clone(GramgenContext* ctx, const AstLexSeq* src) { 1549 AstLexSeq* seq = ast_lex_seq_new(ctx, src->loc); 1550 for (size_t i = 0; i < src->nitems; i++) 1551 ast_lex_seq_append(seq, lex_node_clone(ctx, src->items[i])); 1552 return seq; 1553 } 1554 1555 static AstLexAlt* lex_alt_clone(GramgenContext* ctx, const AstLexAlt* src) { 1556 AstLexAlt* alt = ast_lex_alt_new(ctx, src->loc); 1557 for (size_t i = 0; i < src->nseqs; i++) 1558 ast_lex_alt_append(alt, lex_seq_clone(ctx, src->seqs[i])); 1559 return alt; 1560 } 1561 1562 static AstLexNode* lex_wrap_group(GramgenContext* ctx, AstLexAlt* alts, 1563 Loc loc) { 1564 AstLexNode* n = ast_lex_node_new(ctx, LEX_GROUP, loc); 1565 n->alts = alts; 1566 return n; 1567 } 1568 1569 static int parse_count_uint(GramgenContext* ctx, const char* s, size_t lo, 1570 size_t hi, Loc loc) { 1571 if (lo >= hi) kit_gram_error(ctx, loc, "invalid repetition count"); 1572 long v = 0; 1573 for (size_t i = lo; i < hi; i++) { 1574 if (s[i] < '0' || s[i] > '9') 1575 kit_gram_error(ctx, loc, "invalid repetition count"); 1576 v = v * 10 + (s[i] - '0'); 1577 if (v > KIT_GRAM_MAX_REPEAT + 1) 1578 v = KIT_GRAM_MAX_REPEAT + 1; /* clamp; cap check rejects */ 1579 } 1580 return (int)v; 1581 } 1582 1583 /* Parse a `{n,m}` count body ("n", "n,", "n,m", ",m"; or "1," from `+`). 1584 * hi = -1 means unbounded. Validates the cap and bound ordering. */ 1585 static void parse_repeat_count(GramgenContext* ctx, Str s, Loc loc, int* lo_out, 1586 int* hi_out) { 1587 size_t comma = 0, ncomma = 0; 1588 for (size_t i = 0; i < s.len; i++) 1589 if (s.s[i] == ',') { 1590 comma = i; 1591 ncomma++; 1592 } 1593 if (ncomma > 1) kit_gram_error(ctx, loc, "invalid repetition count"); 1594 int lo, hi; 1595 if (ncomma == 0) { 1596 lo = parse_count_uint(ctx, s.s, 0, s.len, loc); 1597 hi = lo; 1598 } else { 1599 int have_left = comma > 0; 1600 int have_right = comma + 1 < s.len; 1601 if (!have_left && !have_right) 1602 kit_gram_error(ctx, loc, "invalid repetition count"); 1603 lo = have_left ? parse_count_uint(ctx, s.s, 0, comma, loc) : 0; 1604 hi = have_right ? parse_count_uint(ctx, s.s, comma + 1, s.len, loc) : -1; 1605 } 1606 if (lo > KIT_GRAM_MAX_REPEAT || hi > KIT_GRAM_MAX_REPEAT) 1607 kit_gram_error(ctx, loc, "repetition count exceeds maximum of %d", 1608 KIT_GRAM_MAX_REPEAT); 1609 if (hi >= 0 && hi < lo) 1610 kit_gram_error(ctx, loc, 1611 "repetition count: maximum %d is less than minimum %d", hi, 1612 lo); 1613 *lo_out = lo; 1614 *hi_out = hi; 1615 } 1616 1617 typedef struct { 1618 const char* name; 1619 Loc loc; 1620 AstLexAlt* 1621 alts; /* fragment body; desugared (mutated) in place once resolved */ 1622 int state; /* 0 unseen, 1 in-progress (cycle guard), 2 resolved */ 1623 int token_mode; /* declared inside a %machine (token-alphabet) block */ 1624 } Fragment; 1625 1626 typedef struct { 1627 GramgenContext* ctx; 1628 Fragment* frags; 1629 size_t nfrags; 1630 int token_mode; /* desugaring a token-alphabet (%machine) body */ 1631 } Desugar; 1632 1633 static AstLexAlt* desugar_alt(Desugar* D, AstLexAlt* alt); 1634 1635 static AstLexAlt* resolve_fragment(Desugar* D, size_t idx) { 1636 Fragment* f = &D->frags[idx]; 1637 if (f->state == 2) return f->alts; 1638 if (f->state == 1) 1639 kit_gram_error(D->ctx, f->loc, "fragment '%s' is recursive", f->name); 1640 f->state = 1; 1641 /* A fragment body is desugared in the mode of the block that declared it, so 1642 * an UPPERCASE name inside a %machine %def survives as a symbol. */ 1643 int saved = D->token_mode; 1644 D->token_mode = f->token_mode; 1645 f->alts = desugar_alt(D, f->alts); 1646 D->token_mode = saved; 1647 f->state = 2; 1648 return f->alts; 1649 } 1650 1651 static AstLexNode* inline_name(Desugar* D, AstLexNode* node) { 1652 const char* name = node->value.s; 1653 /* In token mode an UPPERCASE NAME is an alphabet symbol: it survives to the 1654 * token NFA leaf rather than being inlined as a %def reference. */ 1655 if (is_token_name(name)) { 1656 if (D->token_mode) return node; 1657 kit_gram_error(D->ctx, node->loc, 1658 "lexer pattern cannot reference token '%s' (only lowercase " 1659 "%%def fragments)", 1660 name); 1661 } 1662 for (size_t i = 0; i < D->nfrags; i++) { 1663 if (strcmp(D->frags[i].name, name) == 0) { 1664 AstLexAlt* body = resolve_fragment(D, i); 1665 return lex_wrap_group(D->ctx, lex_alt_clone(D->ctx, body), node->loc); 1666 } 1667 } 1668 kit_gram_error(D->ctx, node->loc, "unknown fragment '%s'", name); 1669 return node; /* unreachable */ 1670 } 1671 1672 static AstLexNode* expand_repeat(Desugar* D, AstLexNode* node) { 1673 GramgenContext* ctx = D->ctx; 1674 int lo, hi; 1675 parse_repeat_count(ctx, node->value, node->loc, &lo, &hi); 1676 AstLexSeq* seq = ast_lex_seq_new(ctx, node->loc); 1677 for (int i = 0; i < lo; i++) 1678 ast_lex_seq_append( 1679 seq, lex_wrap_group(ctx, lex_alt_clone(ctx, node->alts), node->loc)); 1680 if (hi < 0) { 1681 AstLexNode* rep = ast_lex_node_new(ctx, LEX_REP, node->loc); 1682 rep->alts = lex_alt_clone(ctx, node->alts); 1683 ast_lex_seq_append(seq, rep); 1684 } else { 1685 for (int i = lo; i < hi; i++) { 1686 AstLexNode* opt = ast_lex_node_new(ctx, LEX_OPT, node->loc); 1687 opt->alts = lex_alt_clone(ctx, node->alts); 1688 ast_lex_seq_append(seq, opt); 1689 } 1690 } 1691 AstLexAlt* alt = ast_lex_alt_new(ctx, node->loc); 1692 ast_lex_alt_append(alt, seq); 1693 return lex_wrap_group(ctx, alt, node->loc); 1694 } 1695 1696 static AstLexNode* desugar_node(Desugar* D, AstLexNode* node) { 1697 switch (node->kind) { 1698 case LEX_LITERAL: 1699 case LEX_CLASS: 1700 case LEX_PROP: 1701 case LEX_ANY: 1702 case LEX_ANCHOR: /* passed through; edge anchors are extracted afterward */ 1703 return node; 1704 case LEX_GROUP: 1705 case LEX_OPT: 1706 case LEX_REP: 1707 node->alts = desugar_alt(D, node->alts); 1708 return node; 1709 case LEX_REPEAT: 1710 node->alts = desugar_alt(D, node->alts); 1711 return expand_repeat(D, node); 1712 case LEX_NAME: 1713 return inline_name(D, node); 1714 } 1715 return node; 1716 } 1717 1718 static AstLexAlt* desugar_alt(Desugar* D, AstLexAlt* alt) { 1719 for (size_t i = 0; i < alt->nseqs; i++) { 1720 AstLexSeq* seq = alt->seqs[i]; 1721 for (size_t j = 0; j < seq->nitems; j++) 1722 seq->items[j] = desugar_node(D, seq->items[j]); 1723 } 1724 return alt; 1725 } 1726 1727 static void kit_gram_desugar_lex(Builder* b) { 1728 GramgenContext* ctx = b->ctx; 1729 if (!b->pg->nlex_blocks) return; 1730 1731 /* %def fragments are scoped to their lexer/machine block: each block resolves 1732 * and inlines only its own fragments (declared-before-use not required, but a 1733 * reference to another block's %def is an "unknown fragment"). */ 1734 for (size_t bi = 0; bi < b->pg->nlex_blocks; bi++) { 1735 AstLexBlock* block = b->pg->lex_blocks[bi]; 1736 int token_mode = (block->mode == KIT_GRAM_LEX_INPUT_TOKENS); 1737 1738 Fragment* frags = NULL; 1739 size_t nfrags = 0, cap = 0; 1740 for (size_t li = 0; li < block->nlines; li++) { 1741 AstLexLine* line = block->lines[li]; 1742 if (line->kind != LEX_LINE_DEF) continue; 1743 if (!is_rule_name(line->name)) 1744 kit_gram_error(ctx, line->loc, "fragment name '%s' must be lowercase", 1745 line->name); 1746 for (size_t k = 0; k < nfrags; k++) 1747 if (strcmp(frags[k].name, line->name) == 0) 1748 kit_gram_error(ctx, line->loc, "duplicate fragment '%s'", line->name); 1749 if (nfrags == cap) { 1750 cap = GROW_CAP(cap, 8); 1751 frags = xrealloc(ctx, frags, cap * sizeof *frags); 1752 } 1753 frags[nfrags].name = line->name; 1754 frags[nfrags].loc = line->loc; 1755 frags[nfrags].alts = line->alts; 1756 frags[nfrags].state = 0; 1757 frags[nfrags].token_mode = token_mode; 1758 nfrags++; 1759 } 1760 1761 Desugar D = { 1762 .ctx = ctx, .frags = frags, .nfrags = nfrags, .token_mode = token_mode}; 1763 /* Resolve every fragment (catches cycles even when unused). */ 1764 for (size_t i = 0; i < nfrags; i++) resolve_fragment(&D, i); 1765 /* Inline references and expand repetitions in this block's token/skip 1766 * bodies, in the block's alphabet mode. */ 1767 for (size_t li = 0; li < block->nlines; li++) { 1768 AstLexLine* line = block->lines[li]; 1769 if (line->kind == LEX_LINE_DEF || line->kind == LEX_LINE_KEYWORDS) 1770 continue; 1771 line->alts = desugar_alt(&D, line->alts); 1772 } 1773 xfree(ctx, frags); 1774 } 1775 } 1776 1777 void kit_gram_prepare_lexer(Builder* b) { 1778 if (!b->pg->nlex_blocks) return; 1779 /* Lower fragments and counted repetitions on the lex AST before any NFA is 1780 * built, so the byte and scalar pipelines see only primitive nodes. */ 1781 kit_gram_desugar_lex(b); 1782 LexGroup* groups = NULL; 1783 size_t ngroups = 0, cap_groups = 0; 1784 1785 for (size_t bi = 0; bi < b->pg->nlex_blocks; bi++) { 1786 AstLexBlock* block = b->pg->lex_blocks[bi]; 1787 #ifdef KIT_GRAM_NO_UNICODE 1788 if (block->mode == KIT_GRAM_LEX_INPUT_UTF8) 1789 kit_gram_error( 1790 b->ctx, block->loc, 1791 "%%lex :utf8 mode is disabled in this build (KIT_GRAM_NO_UNICODE)"); 1792 #endif 1793 int token_mode = (block->mode == KIT_GRAM_LEX_INPUT_TOKENS); 1794 /* A lexer/machine must be fully specified in one block: a repeated name is 1795 * an error, not a merge. (Two unnamed %lex blocks both default to "main".) 1796 */ 1797 if (find_lex_group(groups, ngroups, block->name)) 1798 kit_gram_error( 1799 b->ctx, block->loc, 1800 token_mode ? "%%machine '%s' already defined; a %%machine must be a " 1801 "single block" 1802 : "lexer '%s' already defined; a lexer must be a single " 1803 "block", 1804 block->name); 1805 LexGroup* group = 1806 append_lex_group(b, &groups, &ngroups, &cap_groups, block); 1807 for (size_t li = 0; li < block->nlines; li++) { 1808 AstLexLine* line = block->lines[li]; 1809 if (line->kind == LEX_LINE_DEF) { 1810 /* %def: inlined, never a recognizer. In %machine, also catalog them as 1811 * candidate symbol sets so a `[ … ]` can reference one by name. */ 1812 if (token_mode) { 1813 if (group->nsets == group->cap_sets) { 1814 group->cap_sets = GROW_CAP(group->cap_sets, 8); 1815 group->sets = xrealloc(b->ctx, group->sets, 1816 group->cap_sets * sizeof *group->sets); 1817 } 1818 group->sets[group->nsets++] = line; 1819 } 1820 continue; 1821 } 1822 if (line->kind == LEX_LINE_KEYWORDS) { 1823 if (token_mode) 1824 kit_gram_error(b->ctx, line->loc, 1825 "%%keywords is not supported in %%machine"); 1826 continue; /* handled separately below (Phase 2) */ 1827 } 1828 if (token_mode) { 1829 /* A %machine rule is a named recognizer over the symbol alphabet; 1830 * names are lowercase (like parser rules / the kind enum), there is 1831 * no %skip, and there are no edge anchors. */ 1832 if (line->kind == LEX_LINE_SKIP) 1833 kit_gram_error(b->ctx, line->loc, 1834 "%%skip is not supported in %%machine"); 1835 if (!is_rule_name(line->name)) 1836 kit_gram_error(b->ctx, line->loc, 1837 "%%machine rule name '%s' must be lowercase", 1838 line->name); 1839 if (name_index_find(&group->names, line->name, NULL)) 1840 kit_gram_error(b->ctx, line->loc, 1841 "duplicate %%machine rule %s in machine %s", line->name, 1842 block->name); 1843 name_index_put(b->ctx, &group->names, line->name, 1); 1844 LexRecognizer rec; 1845 memset(&rec, 0, sizeof rec); 1846 rec.name = line->name; 1847 rec.loc = line->loc; 1848 rec.alts = line->alts; 1849 rec.seq = kit_gram_next_rec_seq(b); 1850 rec.tok = -1; 1851 rec.skip = 0; 1852 append_recognizer(b->ctx, &group->recs, &group->nrecs, &group->cap_recs, 1853 rec); 1854 continue; 1855 } 1856 const char* what = line->kind == LEX_LINE_SKIP ? "skip" : "token"; 1857 if (!is_token_name(line->name)) 1858 kit_gram_error(b->ctx, line->loc, 1859 "invalid %s name '%s'; names must be all uppercase", what, 1860 line->name); 1861 if (name_index_find(&group->names, line->name, NULL)) 1862 kit_gram_error(b->ctx, line->loc, "duplicate lexer rule %s in lexer %s", 1863 line->name, block->name); 1864 name_index_put(b->ctx, &group->names, line->name, 1); 1865 LexRecognizer rec; 1866 memset(&rec, 0, sizeof rec); 1867 rec.name = line->name; 1868 rec.loc = line->loc; 1869 rec.alts = line->alts; 1870 rec.seq = kit_gram_next_rec_seq(b); 1871 extract_recognizer_anchors(b->ctx, &rec); 1872 if (line->kind == LEX_LINE_TOKEN) { 1873 rec.tok = kit_gram_token_for_ident(b, line->name, line->loc); 1874 rec.skip = 0; 1875 } else { 1876 rec.tok = -1; 1877 rec.skip = 1; 1878 } 1879 append_recognizer(b->ctx, &group->recs, &group->nrecs, &group->cap_recs, 1880 rec); 1881 } 1882 } 1883 1884 /* `recs` lives in the permanent arena (it backs LexDFA.recognizers, which 1885 * codegen reads later). The NFA / subset / scalar intermediates built inside 1886 * compile_lexer are transient, so build them in the scratch arena, copy the 1887 * finished tables back to permanent, and release the scratch. */ 1888 for (size_t gi = 0; gi < ngroups; gi++) { 1889 LexGroup* group = &groups[gi]; 1890 1891 /* Token machines (%machine): codegen-only over an abstract alphabet. They 1892 * reuse the source-priority sort (recognizer_cmp) so the lowest-source- 1893 * order rule wins a same-length accept tie, then compile to a token DFA 1894 * stored apart from the byte/scalar lexers (no KitGramLexGrammar, no 1895 * keyword/shadow machinery). */ 1896 if (group->mode == KIT_GRAM_LEX_INPUT_TOKENS) { 1897 qsort(group->recs, group->nrecs, sizeof *group->recs, recognizer_cmp); 1898 LexDFA* m = kit_gram_compile_machine(b->ctx, group->name, group->recs, 1899 group->nrecs, group->sets, 1900 group->nsets, group->loc); 1901 append_machine(b, m); 1902 continue; 1903 } 1904 1905 /* Standalone + --fold-keywords: fold keywords into the DFA (must run before 1906 * the sort so the synthesized recognizers take their top-priority slots). 1907 * Otherwise keywords are extracted into a minimal perfect hash below, as in 1908 * the table path. */ 1909 int fold_kw = b->lexer_standalone && b->fold_keywords; 1910 if (fold_kw) synthesize_group_keywords(b, group); 1911 qsort(group->recs, group->nrecs, sizeof *group->recs, recognizer_cmp); 1912 1913 GramgenContext* ctx = b->ctx; 1914 scratch_enter(ctx); 1915 LexDFA* tmp = compile_lexer(ctx, group->name, group->recs, group->nrecs, 1916 group->mode, group->loc); 1917 scratch_leave(ctx); 1918 1919 LexDFA* dfa = xcalloc(ctx, 1, sizeof *dfa); /* permanent */ 1920 *dfa = *tmp; /* scalars + class_of + recognizers ptr */ 1921 size_t ncells = (size_t)tmp->nstates * tmp->nclasses; 1922 dfa->trans = xmalloc(ctx, (ncells ? ncells : 1) * sizeof *dfa->trans); 1923 memcpy(dfa->trans, tmp->trans, ncells * sizeof *dfa->trans); 1924 dfa->accept = 1925 xmalloc(ctx, (tmp->nstates ? tmp->nstates : 1) * sizeof *dfa->accept); 1926 memcpy(dfa->accept, tmp->accept, tmp->nstates * sizeof *dfa->accept); 1927 /* End-context accept tables (NULL unless the grammar has that end anchor). 1928 */ 1929 if (tmp->accept_text) { 1930 dfa->accept_text = xmalloc( 1931 ctx, (tmp->nstates ? tmp->nstates : 1) * sizeof *dfa->accept_text); 1932 memcpy(dfa->accept_text, tmp->accept_text, 1933 tmp->nstates * sizeof *dfa->accept_text); 1934 } 1935 if (tmp->accept_line) { 1936 dfa->accept_line = xmalloc( 1937 ctx, (tmp->nstates ? tmp->nstates : 1) * sizeof *dfa->accept_line); 1938 memcpy(dfa->accept_line, tmp->accept_line, 1939 tmp->nstates * sizeof *dfa->accept_line); 1940 } 1941 1942 /* %keywords tables are built against the finished DFA (validation runs 1943 * each keyword through it) in the permanent arena; the literal bytes 1944 * point into the permanent lex AST. The folded path above synthesized the 1945 * keywords into the DFA, so it emits no table (keyword_tables stays NULL); 1946 * every other configuration (table path and standalone MPH) builds them. */ 1947 if (!fold_kw) build_group_keyword_tables(b, dfa, group->name); 1948 check_literal_shadowing(ctx, dfa); 1949 1950 /* The scalar-property memo cache's entries were allocated in the scratch 1951 * arena (utf8/scalar path) and are gone now; drop the dangling head. */ 1952 ctx->scalar_set_cache = NULL; 1953 scratch_release(ctx); 1954 append_lex_dfa(b, dfa); 1955 } 1956 for (size_t i = 0; i < b->nlex_dfas; i++) { 1957 if (lex_name_is_main(b->lex_dfas[i].name)) { 1958 b->lex_dfa = &b->lex_dfas[i]; 1959 break; 1960 } 1961 } 1962 }