lex_dfa.h (6302B)
1 /* kit_gram_lex_dfa.h - shared NFA->DFA infrastructure for the lexer compiler. 2 * 3 * Both lexer back ends share this core: the byte pipeline 4 * (gen/kit_gram_lex_byte.c) and the utf8 scalar pipeline 5 * (gen/kit_gram_lex_scalar.c) each build an NFA, then determinize, minimize, and 6 * canonically relabel it with the routines declared here. Keeping the core in 7 * its own TU lets the scalar pipeline be dropped entirely (KIT_GRAM_NO_UNICODE) 8 * without disturbing the byte path. 9 * 10 * Included from kit_gram_internal.h after the IntSet / GramgenContext / Loc 11 * types it depends on. Cross-TU symbols follow the kit_gram_internal.h 12 * macro-alias convention: a short name in source, an gramgen_-prefixed external 13 * symbol. 14 */ 15 #ifndef KIT_GRAM_LEX_DFA_H 16 #define KIT_GRAM_LEX_DFA_H 17 18 typedef struct { 19 int start, end; 20 } NfaFrag; 21 22 /* Zero-width boundary edge kinds for Tier-1 edge anchors. Both lexer NFA back 23 * ends carry these as a separate edge list (not traversed by eps-closure): 24 * start anchors (BT=`\A`, BL=`^`) hang off the global start state and select 25 * alternate DFA start states; end anchors (ET=`\z`, EL=`$`) hang off a body-end 26 * state and lead to a terminal accept node surfaced through the per-state 27 * end-context accept tables. See doc/DESIGN.md "Edge anchors". */ 28 typedef enum { NFA_BND_BT, NFA_BND_BL, NFA_BND_ET, NFA_BND_EL } NfaBndKind; 29 typedef struct { 30 int kind; 31 int dst; 32 } NfaBndEdge; 33 34 typedef struct { 35 uint32_t* seen; 36 uint32_t stamp; 37 size_t limit; 38 } IntSetScratch; 39 40 typedef struct { 41 int* buckets; 42 int* next; 43 size_t nbuckets; 44 size_t cap_next; 45 } DfaSubsetMap; 46 47 /* A per-DFA-state accept triple: the priority-winning accept reachable directly 48 * (plain, no end anchor), via a `\z` zero-width edge (text), and via a `$` edge 49 * (line). UINT16_MAX in a slot means "no accept of that kind". */ 50 typedef struct { 51 uint16_t plain, text, line; 52 } AcceptTriple; 53 54 /* Interns accept triples to dense signature ids so the shared minimizer can use 55 * a single opaque uint16 equality key. The all-none triple maps to UINT16_MAX 56 * (matching the non-accepting sentinel); other triples map to 0,1,2,... in 57 * first-seen order. `triples[id]` recovers a non-sentinel triple. */ 58 typedef struct { 59 AcceptTriple* triples; 60 size_t n, cap; 61 int* buckets; 62 size_t nbuckets; 63 int* next; 64 } AcceptSigMap; 65 66 #define lex_int_cmp kit_gram_lex_int_cmp 67 #define intset_sort_in_place kit_gram_intset_sort_in_place 68 #define intset_equal_sorted kit_gram_intset_equal_sorted 69 #define intset_hash_sorted kit_gram_intset_hash_sorted 70 #define intset_scratch_init kit_gram_intset_scratch_init 71 #define intset_scratch_reset kit_gram_intset_scratch_reset 72 #define intset_scratch_append kit_gram_intset_scratch_append 73 #define intset_scratch_add kit_gram_intset_scratch_add 74 #define intset_scratch_union kit_gram_intset_scratch_union 75 #define intset_scratch_union_slice kit_gram_intset_scratch_union_slice 76 #define dfa_subset_map_init kit_gram_dfa_subset_map_init 77 #define dfa_subset_map_reserve_next kit_gram_dfa_subset_map_reserve_next 78 #define dfa_subset_map_rehash kit_gram_dfa_subset_map_rehash 79 #define cached_closure kit_gram_cached_closure 80 #define dfa_append_subset kit_gram_dfa_append_subset 81 #define dfa_intern_subset kit_gram_dfa_intern_subset 82 #define dfa_minimize kit_gram_dfa_minimize 83 #define dfa_canonical_relabel kit_gram_dfa_canonical_relabel 84 #define accept_sig_intern kit_gram_accept_sig_intern 85 #define accept_sig_map_free kit_gram_accept_sig_map_free 86 87 int lex_int_cmp(const void* a, const void* b); 88 void intset_sort_in_place(IntSet* s); 89 int intset_equal_sorted(const IntSet* a, const IntSet* b); 90 uint64_t intset_hash_sorted(const IntSet* s); 91 void intset_scratch_init(GramgenContext* ctx, IntSetScratch* scratch, 92 size_t limit); 93 void intset_scratch_reset(IntSetScratch* scratch); 94 void intset_scratch_append(GramgenContext* ctx, IntSet* dst, int value); 95 void intset_scratch_add(GramgenContext* ctx, IntSetScratch* scratch, 96 IntSet* dst, int value); 97 void intset_scratch_union(GramgenContext* ctx, IntSetScratch* scratch, 98 IntSet* dst, const IntSet* src); 99 void intset_scratch_union_slice(GramgenContext* ctx, IntSetScratch* scratch, 100 IntSet* dst, const int* src, size_t n); 101 void dfa_subset_map_init(GramgenContext* ctx, DfaSubsetMap* map); 102 void dfa_subset_map_reserve_next(GramgenContext* ctx, DfaSubsetMap* map, 103 size_t cap); 104 void dfa_subset_map_rehash(GramgenContext* ctx, DfaSubsetMap* map, 105 const IntSet* sets, size_t nsets); 106 IntSet cached_closure(GramgenContext* ctx, const IntSet* state_closures, 107 IntSetScratch* scratch, const IntSet* states); 108 void dfa_append_subset(GramgenContext* ctx, IntSet** sets, size_t* nsets, 109 size_t* cap, IntSet subset); 110 int dfa_intern_subset(GramgenContext* ctx, DfaSubsetMap* map, IntSet** sets, 111 size_t* nsets, size_t* cap, const IntSet* subset, 112 Loc loc); 113 /* Hash-grouped Moore minimization. `accept` is treated as an opaque per-state 114 * equality key. Any ids in `remap_ids` (e.g. alternate start states) are 115 * rewritten in place to their post-minimization numbering. Pass NULL/0 when 116 * there are none. */ 117 void dfa_minimize(GramgenContext* ctx, Loc loc, uint16_t** trans_io, 118 uint16_t** accept_io, uint16_t* nstates_io, uint16_t nclasses, 119 uint16_t* remap_ids, size_t nremap_ids); 120 /* Canonically renumber by BFS. `roots` lists the start states to traverse from, 121 * in order (pass NULL/0 to default to the single root state 0). Any ids in 122 * `remap_ids` (e.g. alternate start states) are rewritten in place to their new 123 * numbering. */ 124 void dfa_canonical_relabel(GramgenContext* ctx, uint16_t* trans, 125 uint16_t* accept, uint16_t nstates, 126 uint16_t nclasses, const uint16_t* roots, 127 size_t nroots, uint16_t* remap_ids, 128 size_t nremap_ids); 129 uint16_t accept_sig_intern(GramgenContext* ctx, AcceptSigMap* m, uint16_t plain, 130 uint16_t text, uint16_t line); 131 void accept_sig_map_free(GramgenContext* ctx, AcceptSigMap* m); 132 133 #endif /* KIT_GRAM_LEX_DFA_H */