1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
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.
|
