lex_dfa.c (17692B)
1 /* kit_gram_lex_dfa.c - shared NFA->DFA core (subset construction, Moore 2 * minimization, canonical relabeling) used by both lexer back ends. */ 3 #include "internal.h" 4 5 int lex_int_cmp(const void* a, const void* b) { 6 int x = *(const int*)a; 7 int y = *(const int*)b; 8 return (x > y) - (x < y); 9 } 10 11 void intset_sort_in_place(IntSet* s) { 12 if (s->n > 1) qsort(s->v, s->n, sizeof *s->v, lex_int_cmp); 13 } 14 15 int intset_equal_sorted(const IntSet* a, const IntSet* b) { 16 if (a->n != b->n) return 0; 17 for (size_t i = 0; i < a->n; i++) 18 if (a->v[i] != b->v[i]) return 0; 19 return 1; 20 } 21 22 uint64_t intset_hash_sorted(const IntSet* s) { 23 uint64_t h = 1469598103934665603ull; 24 for (size_t i = 0; i < s->n; i++) { 25 uint64_t x = (uint64_t)(uint32_t)s->v[i]; 26 h ^= x; 27 h *= 1099511628211ull; 28 } 29 h ^= (uint64_t)s->n; 30 h *= 1099511628211ull; 31 return h; 32 } 33 34 void intset_scratch_init(GramgenContext* ctx, IntSetScratch* scratch, 35 size_t limit) { 36 scratch->limit = limit; 37 scratch->stamp = 0; 38 scratch->seen = xcalloc(ctx, limit ? limit : 1, sizeof *scratch->seen); 39 } 40 41 void intset_scratch_reset(IntSetScratch* scratch) { 42 scratch->stamp++; 43 if (!scratch->stamp) { 44 memset(scratch->seen, 0, scratch->limit * sizeof *scratch->seen); 45 scratch->stamp = 1; 46 } 47 } 48 49 void intset_scratch_append(GramgenContext* ctx, IntSet* dst, int value) { 50 if (dst->n == dst->cap) { 51 dst->cap = dst->cap ? dst->cap * 2 : 8; 52 dst->v = xrealloc(ctx, dst->v, dst->cap * sizeof *dst->v); 53 } 54 dst->v[dst->n++] = value; 55 } 56 57 void intset_scratch_add(GramgenContext* ctx, IntSetScratch* scratch, 58 IntSet* dst, int value) { 59 if (value < 0 || (size_t)value >= scratch->limit) { 60 intset_add(ctx, dst, value); 61 return; 62 } 63 size_t idx = (size_t)value; 64 if (scratch->seen[idx] == scratch->stamp) return; 65 scratch->seen[idx] = scratch->stamp; 66 intset_scratch_append(ctx, dst, value); 67 } 68 69 void intset_scratch_union(GramgenContext* ctx, IntSetScratch* scratch, 70 IntSet* dst, const IntSet* src) { 71 for (size_t i = 0; i < src->n; i++) 72 intset_scratch_add(ctx, scratch, dst, src->v[i]); 73 } 74 75 void intset_scratch_union_slice(GramgenContext* ctx, IntSetScratch* scratch, 76 IntSet* dst, const int* src, size_t n) { 77 for (size_t i = 0; i < n; i++) intset_scratch_add(ctx, scratch, dst, src[i]); 78 } 79 80 void dfa_subset_map_init(GramgenContext* ctx, DfaSubsetMap* map) { 81 map->nbuckets = 1024; 82 map->buckets = xmalloc(ctx, map->nbuckets * sizeof *map->buckets); 83 for (size_t i = 0; i < map->nbuckets; i++) map->buckets[i] = -1; 84 map->next = NULL; 85 map->cap_next = 0; 86 } 87 88 void dfa_subset_map_reserve_next(GramgenContext* ctx, DfaSubsetMap* map, 89 size_t cap) { 90 if (cap <= map->cap_next) return; 91 size_t old = map->cap_next; 92 map->cap_next = map->cap_next ? map->cap_next * 2 : 16; 93 while (map->cap_next < cap) map->cap_next *= 2; 94 map->next = xrealloc(ctx, map->next, map->cap_next * sizeof *map->next); 95 for (size_t i = old; i < map->cap_next; i++) map->next[i] = -1; 96 } 97 98 void dfa_subset_map_rehash(GramgenContext* ctx, DfaSubsetMap* map, 99 const IntSet* sets, size_t nsets) { 100 size_t nbuckets = map->nbuckets * 2; 101 int* buckets = xmalloc(ctx, nbuckets * sizeof *buckets); 102 for (size_t i = 0; i < nbuckets; i++) buckets[i] = -1; 103 for (size_t i = 0; i < nsets; i++) { 104 size_t bucket = 105 (size_t)(intset_hash_sorted(&sets[i]) & (uint64_t)(nbuckets - 1)); 106 map->next[i] = buckets[bucket]; 107 buckets[bucket] = (int)i; 108 } 109 map->buckets = buckets; 110 map->nbuckets = nbuckets; 111 } 112 113 IntSet cached_closure(GramgenContext* ctx, const IntSet* state_closures, 114 IntSetScratch* scratch, const IntSet* states) { 115 IntSet out = {0}; 116 intset_scratch_reset(scratch); 117 for (size_t i = 0; i < states->n; i++) 118 intset_scratch_union(ctx, scratch, &out, &state_closures[states->v[i]]); 119 intset_sort_in_place(&out); 120 return out; 121 } 122 123 void dfa_append_subset(GramgenContext* ctx, IntSet** sets, size_t* nsets, 124 size_t* cap, IntSet subset) { 125 if (*nsets == *cap) { 126 *cap = *cap ? *cap * 2 : 16; 127 *sets = xrealloc(ctx, *sets, *cap * sizeof **sets); 128 } 129 (*sets)[(*nsets)++] = subset; 130 } 131 132 /* Intern a subset, copying it into an owned IntSet only when it is genuinely 133 * new. The caller may pass a reusable scratch buffer (reset and refilled each 134 * call) instead of allocating a fresh IntSet per cell, which avoids the 135 * dominant per-(state,class) allocation churn during subset construction. */ 136 int dfa_intern_subset(GramgenContext* ctx, DfaSubsetMap* map, IntSet** sets, 137 size_t* nsets, size_t* cap, const IntSet* subset, 138 Loc loc) { 139 uint64_t hash = intset_hash_sorted(subset); 140 size_t bucket = (size_t)(hash & (uint64_t)(map->nbuckets - 1)); 141 for (int idx = map->buckets[bucket]; idx >= 0; idx = map->next[idx]) { 142 if (intset_equal_sorted(&(*sets)[idx], subset)) return idx; 143 } 144 if (*nsets >= 65535) kit_gram_error(ctx, loc, "too many lexer DFA states"); 145 if ((*nsets + 1) * 2 > map->nbuckets) { 146 dfa_subset_map_rehash(ctx, map, *sets, *nsets); 147 bucket = (size_t)(hash & (uint64_t)(map->nbuckets - 1)); 148 } 149 dfa_subset_map_reserve_next(ctx, map, *nsets + 1); 150 IntSet owned = {0}; 151 if (subset->n) { 152 owned.v = xmalloc(ctx, subset->n * sizeof *owned.v); 153 memcpy(owned.v, subset->v, subset->n * sizeof *owned.v); 154 owned.n = subset->n; 155 owned.cap = subset->n; 156 } 157 dfa_append_subset(ctx, sets, nsets, cap, owned); 158 map->next[*nsets - 1] = map->buckets[bucket]; 159 map->buckets[bucket] = (int)(*nsets - 1); 160 return (int)(*nsets - 1); 161 } 162 163 uint16_t accept_sig_intern(GramgenContext* ctx, AcceptSigMap* m, uint16_t plain, 164 uint16_t text, uint16_t line) { 165 if (plain == UINT16_MAX && text == UINT16_MAX && line == UINT16_MAX) 166 return UINT16_MAX; 167 if (!m->nbuckets) { 168 m->nbuckets = 1024; 169 m->buckets = xmalloc(ctx, m->nbuckets * sizeof *m->buckets); 170 for (size_t i = 0; i < m->nbuckets; i++) m->buckets[i] = -1; 171 } 172 uint64_t key = ((uint64_t)plain << 32) | ((uint64_t)text << 16) | line; 173 uint64_t h = key * 1099511628211ull; 174 size_t bucket = (size_t)(h & (uint64_t)(m->nbuckets - 1)); 175 for (int idx = m->buckets[bucket]; idx >= 0; idx = m->next[idx]) { 176 AcceptTriple* t = &m->triples[idx]; 177 if (t->plain == plain && t->text == text && t->line == line) 178 return (uint16_t)idx; 179 } 180 if (m->n >= UINT16_MAX) 181 kit_gram_error(ctx, (Loc){0}, "too many lexer accept signatures"); 182 if (m->n == m->cap) { 183 m->cap = m->cap ? m->cap * 2 : 16; 184 m->triples = xrealloc(ctx, m->triples, m->cap * sizeof *m->triples); 185 m->next = xrealloc(ctx, m->next, m->cap * sizeof *m->next); 186 } 187 if ((m->n + 1) * 2 > m->nbuckets) { 188 size_t nb = m->nbuckets * 2; 189 int* b = xmalloc(ctx, nb * sizeof *b); 190 for (size_t i = 0; i < nb; i++) b[i] = -1; 191 for (size_t i = 0; i < m->n; i++) { 192 AcceptTriple* t = &m->triples[i]; 193 uint64_t k = 194 ((uint64_t)t->plain << 32) | ((uint64_t)t->text << 16) | t->line; 195 size_t bk = (size_t)((k * 1099511628211ull) & (uint64_t)(nb - 1)); 196 m->next[i] = b[bk]; 197 b[bk] = (int)i; 198 } 199 xfree(ctx, m->buckets); 200 m->buckets = b; 201 m->nbuckets = nb; 202 bucket = (size_t)(h & (uint64_t)(nb - 1)); 203 } 204 int id = (int)m->n++; 205 m->triples[id] = (AcceptTriple){plain, text, line}; 206 m->next[id] = m->buckets[bucket]; 207 m->buckets[bucket] = id; 208 return (uint16_t)id; 209 } 210 211 void accept_sig_map_free(GramgenContext* ctx, AcceptSigMap* m) { 212 xfree(ctx, m->triples); 213 xfree(ctx, m->buckets); 214 xfree(ctx, m->next); 215 *m = (AcceptSigMap){0}; 216 } 217 218 typedef struct { 219 const uint16_t* trans; 220 const uint16_t* accept; 221 const int* block_of; 222 size_t nclasses; 223 } DfaMinSortCtx; 224 225 /* Signature hash of a state: its block, accept value, and the blocks of all its 226 * transition targets. Two states are Moore-equivalent within a refinement round 227 * iff their signatures match. */ 228 static uint64_t dfa_min_sig_hash(const DfaMinSortCtx* ctx, int x) { 229 uint64_t h = 1469598103934665603ull; 230 h = (h ^ (uint64_t)(uint32_t)ctx->block_of[x]) * 1099511628211ull; 231 h = (h ^ (uint64_t)ctx->accept[x]) * 1099511628211ull; 232 const uint16_t* rx = &ctx->trans[(size_t)x * ctx->nclasses]; 233 for (size_t c = 0; c < ctx->nclasses; c++) 234 h = (h ^ (uint64_t)(uint32_t)ctx->block_of[rx[c]]) * 1099511628211ull; 235 return h; 236 } 237 238 static int dfa_min_same_sig(const DfaMinSortCtx* ctx, int x, int y) { 239 if (ctx->block_of[x] != ctx->block_of[y]) return 0; 240 if (ctx->accept[x] != ctx->accept[y]) return 0; 241 const uint16_t* rx = &ctx->trans[(size_t)x * ctx->nclasses]; 242 const uint16_t* ry = &ctx->trans[(size_t)y * ctx->nclasses]; 243 for (size_t c = 0; c < ctx->nclasses; c++) 244 if (ctx->block_of[rx[c]] != ctx->block_of[ry[c]]) return 0; 245 return 1; 246 } 247 248 void dfa_minimize(GramgenContext* ctx, Loc loc, uint16_t** trans_io, 249 uint16_t** accept_io, uint16_t* nstates_io, uint16_t nclasses, 250 uint16_t* remap_ids, size_t nremap_ids) { 251 size_t nstates = *nstates_io; 252 if (!nstates) return; 253 size_t total = nstates + 1; 254 uint16_t sink = (uint16_t)nstates; 255 uint16_t* old_trans = *trans_io; 256 uint16_t* old_accept = *accept_io; 257 uint16_t* full_trans = 258 xmalloc(ctx, total * (size_t)nclasses * sizeof *full_trans); 259 uint16_t* full_accept = xmalloc(ctx, total * sizeof *full_accept); 260 261 for (size_t st = 0; st < nstates; st++) { 262 for (uint16_t c = 0; c < nclasses; c++) { 263 uint16_t dst = old_trans[st * (size_t)nclasses + c]; 264 full_trans[st * (size_t)nclasses + c] = 265 dst == UINT16_MAX || dst >= nstates ? sink : dst; 266 } 267 full_accept[st] = old_accept[st]; 268 } 269 for (uint16_t c = 0; c < nclasses; c++) 270 full_trans[nstates * (size_t)nclasses + c] = sink; 271 full_accept[nstates] = UINT16_MAX; 272 273 int* block_of = xmalloc(ctx, total * sizeof *block_of); 274 int* next_block = xmalloc(ctx, total * sizeof *next_block); 275 int* accept_block = xmalloc(ctx, 65536 * sizeof *accept_block); 276 for (size_t i = 0; i < 65536; i++) accept_block[i] = -1; 277 int nblocks = 0; 278 for (size_t st = 0; st < total; st++) { 279 uint16_t acc = full_accept[st]; 280 if (accept_block[acc] < 0) accept_block[acc] = nblocks++; 281 block_of[st] = accept_block[acc]; 282 } 283 284 /* Hash table for grouping states by signature within each refinement round. 285 * Two states land in the same new block iff they are Moore-equivalent under 286 * the current partition. Numbering is assigned in ascending state order on 287 * first appearance; the final emitted table depends only on the converged 288 * partition (not these intermediate numbers), so output is byte-identical. */ 289 size_t nbuckets = 1024; 290 while (nbuckets < total * 2) nbuckets *= 2; 291 int* buckets = xmalloc(ctx, nbuckets * sizeof *buckets); 292 int* group_head = xmalloc(ctx, total * sizeof *group_head); 293 int* group_next = xmalloc(ctx, total * sizeof *group_next); 294 295 for (;;) { 296 DfaMinSortCtx sort_ctx = { 297 .trans = full_trans, 298 .accept = full_accept, 299 .block_of = block_of, 300 .nclasses = nclasses, 301 }; 302 303 for (size_t i = 0; i < nbuckets; i++) buckets[i] = -1; 304 int new_nblocks = 0; 305 for (size_t st = 0; st < total; st++) { 306 uint64_t h = dfa_min_sig_hash(&sort_ctx, (int)st); 307 size_t bucket = (size_t)(h & (uint64_t)(nbuckets - 1)); 308 int blk = -1; 309 for (int g = buckets[bucket]; g >= 0; g = group_next[g]) { 310 if (dfa_min_same_sig(&sort_ctx, group_head[g], (int)st)) { 311 blk = g; 312 break; 313 } 314 } 315 if (blk < 0) { 316 blk = new_nblocks++; 317 group_head[blk] = (int)st; 318 group_next[blk] = buckets[bucket]; 319 buckets[bucket] = blk; 320 } 321 next_block[st] = blk; 322 } 323 324 int changed = new_nblocks != nblocks; 325 int* tmp = block_of; 326 block_of = next_block; 327 next_block = tmp; 328 nblocks = new_nblocks; 329 if (!changed) break; 330 } 331 332 int start_block = block_of[0]; 333 int sink_block = block_of[sink]; 334 int emit_sink = start_block == sink_block; 335 int* min_real = xmalloc(ctx, (size_t)nblocks * sizeof *min_real); 336 int* used = xcalloc(ctx, (size_t)nblocks, sizeof *used); 337 int* ordered = xmalloc(ctx, (size_t)nblocks * sizeof *ordered); 338 int* block_to_new = xmalloc(ctx, (size_t)nblocks * sizeof *block_to_new); 339 for (int b = 0; b < nblocks; b++) { 340 min_real[b] = INT_MAX; 341 block_to_new[b] = -1; 342 } 343 for (size_t st = 0; st < nstates; st++) { 344 int block = block_of[st]; 345 if ((int)st < min_real[block]) min_real[block] = (int)st; 346 } 347 348 int out_blocks = 0; 349 ordered[out_blocks++] = start_block; 350 used[start_block] = 1; 351 for (;;) { 352 int best = -1; 353 for (int b = 0; b < nblocks; b++) { 354 if (used[b]) continue; 355 if (!emit_sink && b == sink_block) continue; 356 if (min_real[b] == INT_MAX) continue; 357 if (best < 0 || min_real[b] < min_real[best]) best = b; 358 } 359 if (best < 0) break; 360 ordered[out_blocks++] = best; 361 used[best] = 1; 362 } 363 if (out_blocks > 65535) kit_gram_error(ctx, loc, "too many lexer DFA states"); 364 for (int i = 0; i < out_blocks; i++) block_to_new[ordered[i]] = i; 365 366 uint16_t* new_trans = 367 xmalloc(ctx, (size_t)out_blocks * nclasses * sizeof *new_trans); 368 uint16_t* new_accept = xmalloc(ctx, (size_t)out_blocks * sizeof *new_accept); 369 for (int i = 0; i < out_blocks; i++) { 370 int block = ordered[i]; 371 int rep = sink; 372 for (size_t st = 0; st < nstates; st++) { 373 if (block_of[st] == block) { 374 rep = (int)st; 375 break; 376 } 377 } 378 new_accept[i] = full_accept[rep]; 379 for (uint16_t c = 0; c < nclasses; c++) { 380 int dst_block = block_of[full_trans[(size_t)rep * nclasses + c]]; 381 if (dst_block == sink_block && !emit_sink) 382 new_trans[(size_t)i * nclasses + c] = UINT16_MAX; 383 else 384 new_trans[(size_t)i * nclasses + c] = (uint16_t)block_to_new[dst_block]; 385 } 386 } 387 388 for (size_t i = 0; i < nremap_ids; i++) { 389 uint16_t old = remap_ids[i]; 390 if (old < nstates) remap_ids[i] = (uint16_t)block_to_new[block_of[old]]; 391 } 392 393 *trans_io = new_trans; 394 *accept_io = new_accept; 395 *nstates_io = (uint16_t)out_blocks; 396 } 397 398 /* Canonically renumber DFA states by breadth-first traversal from the start 399 * state (state 0), visiting byte classes in ascending order and numbering each 400 * newly reached state in discovery order. This makes the emitted numbering a 401 * function only of the (minimized) automaton and the canonical byte-class 402 * order, not of the order in which states happened to be constructed. 403 * 404 * For the byte-NFA subset-construction pipeline this reproduces the previous 405 * min_real numbering exactly: subset states were interned in BFS order, so a 406 * block's minimum pre-min index equals its BFS first-discovery time, and BFS 407 * first-discovery order is invariant under byte-class refinement. Making the 408 * numbering explicit lets the direct scalar->byte lowering, whose intermediate 409 * state-construction order differs entirely, emit byte-identical tables. */ 410 void dfa_canonical_relabel(GramgenContext* ctx, uint16_t* trans, 411 uint16_t* accept, uint16_t nstates, 412 uint16_t nclasses, const uint16_t* roots, 413 size_t nroots, uint16_t* remap_ids, 414 size_t nremap_ids) { 415 if (!nstates) return; 416 uint16_t* new_of = xmalloc(ctx, (size_t)nstates * sizeof *new_of); 417 uint16_t* order = 418 xmalloc(ctx, (size_t)nstates * sizeof *order); /* new id -> old id */ 419 for (uint16_t i = 0; i < nstates; i++) new_of[i] = UINT16_MAX; 420 size_t head = 0, count = 0; 421 /* Seed the BFS with the start roots in order (default: the single state 0). 422 * Numbering newly-reached states in discovery order makes the result a 423 * function only of the automaton, the byte-class order, and the root order. 424 */ 425 static const uint16_t default_root = 0; 426 if (!roots || !nroots) { 427 roots = &default_root; 428 nroots = 1; 429 } 430 for (size_t r = 0; r < nroots; r++) { 431 uint16_t root = roots[r]; 432 if (root >= nstates || new_of[root] != UINT16_MAX) continue; 433 new_of[root] = (uint16_t)count; 434 order[count++] = root; 435 } 436 while (head < count) { 437 uint16_t s = order[head++]; 438 const uint16_t* row = &trans[(size_t)s * nclasses]; 439 for (uint16_t c = 0; c < nclasses; c++) { 440 uint16_t t = row[c]; 441 if (t == UINT16_MAX || t >= nstates) continue; 442 if (new_of[t] == UINT16_MAX) { 443 new_of[t] = (uint16_t)count; 444 order[count++] = t; 445 } 446 } 447 } 448 /* Unreachable states (none in a reachable-by-construction DFA) keep their 449 * relative order after the reachable ones, for total determinism. */ 450 for (uint16_t s = 0; s < nstates; s++) { 451 if (new_of[s] == UINT16_MAX) { 452 new_of[s] = (uint16_t)count; 453 order[count++] = s; 454 } 455 } 456 uint16_t* nt = xmalloc(ctx, (size_t)nstates * (size_t)nclasses * sizeof *nt); 457 uint16_t* na = xmalloc(ctx, (size_t)nstates * sizeof *na); 458 for (uint16_t ni = 0; ni < nstates; ni++) { 459 uint16_t old = order[ni]; 460 na[ni] = accept[old]; 461 const uint16_t* row = &trans[(size_t)old * nclasses]; 462 uint16_t* dst = &nt[(size_t)ni * nclasses]; 463 for (uint16_t c = 0; c < nclasses; c++) { 464 uint16_t t = row[c]; 465 dst[c] = (t == UINT16_MAX || t >= nstates) ? UINT16_MAX : new_of[t]; 466 } 467 } 468 memcpy(trans, nt, (size_t)nstates * (size_t)nclasses * sizeof *nt); 469 memcpy(accept, na, (size_t)nstates * sizeof *na); 470 for (size_t i = 0; i < nremap_ids; i++) 471 if (remap_ids[i] < nstates) remap_ids[i] = new_of[remap_ids[i]]; 472 xfree(ctx, nt); 473 xfree(ctx, na); 474 xfree(ctx, new_of); 475 xfree(ctx, order); 476 }