From fba9a90cfc6aca2a26cce72f55fb261789139781 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 16 Oct 2026 14:01:01 +0800 Subject: new start Now I tested and discussed with claude, and had a working version of this project. The rest is to port the claude version to my own writings. So this serves as the starting point before that attempt. In the new attempt the design is better, and a number of bugs were found and supposedly fixed, so let us see how this goes at the end. --- tests/DESIGN-leading-chains.md | 153 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+) create mode 100644 tests/DESIGN-leading-chains.md (limited to 'tests/DESIGN-leading-chains.md') 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 { symbol: TNT, slot: usize, target: usize /* NFA state after it */ } +``` + +From `lead` compute two tables, once, at construction: + +### 3.1 `chains[(N, t)] : Vec` (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): + 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` 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. -- cgit v1.2.3-18-g5258