diff options
Diffstat (limited to 'tests/DESIGN-leading-chains.md')
| -rw-r--r-- | tests/DESIGN-leading-chains.md | 153 |
1 files changed, 153 insertions, 0 deletions
diff --git a/tests/DESIGN-leading-chains.md b/tests/DESIGN-leading-chains.md new file mode 100644 index 0000000..72421ad --- /dev/null +++ b/tests/DESIGN-leading-chains.md @@ -0,0 +1,153 @@ +# Design proposal: record leading chains directly (replaces `expansion_map`) + +Written by Claude Code (session 2, 2026-10-14) at the user's request, as a +PROPOSAL for the user to confirm and implement by hand. Nothing here has been +applied to the repository. Items marked MEASURED come from runs on a scratch +copy; INFERRED means read from code; OPEN means a decision for the user. + +## 1. Problem (MEASURED) + +For `T -> S x ; S -> S a | a` the stored virtual fragment of `[T]^a` is +`S -> {R8 -> S (back edge), R6 -> a}`: it has no `T` node and no `T -> R2 -> S` +link, whereas for the non-recursive `S -> A b ; A -> a` the fragment of `[S]^a` +is `S -> R2 -> A -> R6 -> a`. Tracing the writes to `expansion_map` (debug +prints, key `(0,13)` = start state of `T` to the `a`-edge target): + +1. The composition through `second_source = 8` (S's start state) writes the + correct `[(1,6),(0,2)]`. +2. A later composition through `second_source = 16` takes the branch + `!second_nt_start`, and since the existing entry (2 pairs) is shorter than + `(16,13)`'s `[(1,6),(1,8),(1,8)]` (3 pairs), the guard "longer wins" + overwrites the correct entry. The copy has no `(0,2)`. + +INFERRED root cause: the entries are written as a side effect of the iterative +null-closure; with a left-recursive nonterminal the lists grow with repeated +`(S, R8)` pairs, so "longer" no longer means "more complete", and the branch +that copies `(second_source, second_target)` forgets what the first edge added. + +## 2. What is actually consumed (INFERRED, by grep) + +- `query_expansion` is called from `atom/default.rs` (`from_grammar`, the loop + that fills `virtual_frags`) always as `(nt_start, child)`, and from + `genins.rs::virtual_generate_fragment`, which only the unit tests use. + So only entries whose first component is the START STATE of a nonterminal + are ever read. +- The consumer wants, for each virtual node `[N]^t` and each final slot `r` (the + slot of the terminal `t`): a forest fragment + `N -> Rule(w1) -> X1 -> Rule(w2) -> X2 ... -> Rule(r) -> t`. + `virtual_frags[VirtualNode(N,t)][r]` stores it, `trace(N,t,target)` gives `r`. +- The climb needs, for condition (1): given the closed nonterminal `Y`, the + fragment slot `r` and the head `h = get_rule_num(r)`, the wrapper slot `w` of + `Y` as leading symbol of `h`'s rule. Today `left_wrapper` (my scratch code) + scans the closure NFA's `left_p` edges for this on every call. + +## 3. Proposed record: the leading graph, read from the NFA BEFORE the closure + +In `DefaultAtom::from_grammar`, right after `grammar.left_closure_to_nfa(®exp)` +and before `nfa.closure(...)`, the NFA of each nonterminal `N` has at its start +state `start(N)` exactly one edge per possible first literal of `N` +(`first_nodes_of`), labelled with the symbol (`Ter(t)` or `Non(Y)`) and carrying +the slot `w` (`get_moved()`). Read these once: + +```text +lead[N] : Vec<LeadEdge> +LeadEdge { symbol: TNT, slot: usize, target: usize /* NFA state after it */ } +``` + +From `lead` compute two tables, once, at construction: + +### 3.1 `chains[(N, t)] : Vec<Chain>` (replaces the use of `expansion_map`) + +`Chain = Vec<(nt, slot)>`, outermost first: `nt` is a nonterminal node and `slot` +is the wrapper that is its child; the last slot is the one of the terminal. + +```text +fn collect(N, t, path: Vec<(nt,slot)>, on_path: Set<nt>): + for e in lead[N]: + match e.symbol: + Ter(t') if t' == t => emit path ++ [(N, e.slot)] + Non(Y) if Y not in on_path => collect(Y, t, path ++ [(N, e.slot)], on_path + {N}) + Non(Y) (Y on the path) => record back edge (N, e.slot, Y); do not recurse +``` + +Chains are SIMPLE paths: no nonterminal repeats, so no cycle, and the fragment +needs no cut (`remove_prefix_cut_cycles` and the cycle problem disappear). +The fragment is `generate_fragment(chain flattened, 0)` as today; the key +`r` is the last slot, as today. For `T -> S x; S -> S a | a` this yields +`[(T,2),(S,6)]` = `T -> R2 -> S -> R6 -> a`, which is the missing fragment. +Left recursion (`S -> S a`) shows up only as a back edge, not as a chain. + +### 3.2 `left_wrapper[(h, Y, r)] -> w` (replaces my scan in `left_wrapper`) + +```text +for each head h, each e in lead[h] with e.symbol = Non(Y): + for each out-edge (moved = r) of NFA state e.target: + left_wrapper[(h, Y, r)] = e.slot +``` + +Meaning: in a rule of `h`, `Y` is a leading symbol with wrapper slot `w = +e.slot`, and slot `r` is what may follow it. The climb's condition (1) becomes +a single lookup. This also covers the back edges of 3.1. + +## 4. What changes in the existing code (for the user to decide) + +1. `grammar/src/lib.rs::transform_label_null_epsilon`: stop writing + `expansion_map` (keep the `left_p` computation and the reduction recording). + `query_expansion` / the field can go once `virtual_generate_fragment` (test + only) is rewritten on top of `chains`. +2. `chain/src/atom/default.rs` (~487): build `virtual_frags` from `chains` + instead of `grammar.query_expansion(nt_start, child)`. +3. `chain/src/item/genins.rs`: `left_wrapper` becomes a lookup in 3.2 (an + accessor on `DefaultAtom`). +4. `plant_at_start`: `remove_prefix(1)` stays as it was; no cycle cut needed. + NOTE the existing assumption "the fragment root is the owner of the virtual + node": with `chains` the root is `N` itself, so it is true again also for + `T -> S x` (today the root is `S`, which is wrong). + +## 5. OPEN questions for the user + +1. Several chains with the same final slot `r` (e.g. `N -> A -> X`, + `N -> B -> X`): `virtual_frags.insert(rule, frag)` today keeps only the last. + They are different derivations, so they should become alternatives (clones + of the root, as `virtual_generate_fragment` in genins.rs already does). + Should `virtual_frags` store `Vec<frag>` per `(node, r)`? +2. Nullable leading symbols (a nullable `A` before `x`): `first_nodes_of` + already lists the literal after it as a first literal, but the forest needs + the epsilon derivation of `A` in the chain. Defer to layer 3? +3. Is it acceptable to read `lead` from the NFA before the closure, or do you + prefer to compute it in the `grammar` crate (`left_closure.rs`)? +4. `reduction_map` is built by the same iterative closure with the same + "longer wins" guard. It may have an analogous defect (not measured). A + similar direct computation would be: for an edge `q -> q'` the list of + nonterminals whose exit state is crossed on the null path. Out of scope + until the expansion part is settled. + +## 6. Test plan (before any change to the climb) + +- Unit test on the atom: `chains` for + `S -> A b; A -> a` = `[[(S,2),(A,6)]]`, + `T -> S x; S -> S a | a` = `[[(T,2),(S,6)]]` with back edge `(S, 8, S)`, + `S -> S a | a` = `[[(S,2)]]` with back edge `(S, 4, S)`, + indirect `S -> A b | d; A -> S c` for `(S, d)` = `[[(S,slot of d)]]` and + for `(A, d)` = `[[(A,w),(S,slot of d)]]`. + (Slot numbers vary with the grammar encoding; assert structure, not numbers.) +- Then in the scratch copy: swap the source of `virtual_frags`, rerun the oracle + probe set (`T -> S x`, indirect cases first), and compare with the current + table of results. + +## 7. Status (end of session 2) + +Prototyped in a scratch copy as described in `tests/CLAUDE-PROGRESS.md` +("LEADING CHAINS PROTOTYPE"). Findings that refine this design: + +- The leading edges must be read through epsilon edges, and unlabelled edges + count as epsilon (see 3. above); do not follow an epsilon edge that enters + another nonterminal's start state. +- `chains[(T,a)]` for `T -> S x; S -> S a | a` is `[(T,2),(S,6)]`, which + fixes `T -> S x` and the indirect case `S -> A b; A -> S c | d` on `d b`. +- Consumers of fragments: `insert_item` (virtual branch) now loops over all + alternatives; `close_pavi` already iterated. Parents pushed by several + alternatives with the same final wrapper must be deduplicated. +- Back edges are dropped by `chains`. For cyclic grammars (`S -> S | a`) the + cycle then has to be created by the completer; this is the remaining design + question of layer 5. |