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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
#+TITLE: Claude's suggestions on forest construction
#+DATE: 2026-10-12
#+STARTUP: overview
Written by Claude Code at the user's request, for later reference.
Nothing here has been applied to the source. The only code written is
=tests/spike.rs=, which holds exploratory probes.
Status labels used below:
- MEASURED: observed by running the probes in =tests/spike.rs=.
- INFERRED: concluded from reading code, not directly observed.
- OPINION: a judgement about design, not verified.
* Where we are
** Harness facts
- A root-crate test can use =chain=, =grammar=, =graph=, =forest=, =nfa=.
(=nfa= and the =test-helper= feature were added to the root
=[dev-dependencies]= by the user.)
- Grammars are built with =Terminal::new=, =Nonterminal::new=,
=Rule::new= and =DefaultRegParser= + =scan_tnt=. Names in the rule
strings are letters only, e.g. =Ta=, =NS=. An empty alternative
(="... | "=) is epsilon.
- The parser's debug dumps write to a relative =output/= directory.
The tests change into =$TMPDIR/rep-tests= (with =output/= inside) once,
so nothing is written to the source tree.
- Call sequence: =DefaultAtom::from_grammar= -> =DefaultChain::unit= ->
=chain(tok, pos, false)= per token -> =end_of_input(n, last_tok)=.
- The END_OF_INPUT token is NOT a convention of this project.
- Empty input is deferred to the epsilon layer: the =ter= argument of
=end_of_input= selects virtual fragments keyed by (nt, ter)
(=chain/src/atom/default.rs:489-549=, =chain/src/item/genins.rs:730=), so
an arbitrary terminal is not safe for an empty input.
** First failure found (MEASURED)
Smallest failing case: =S -> S a | a= on =aa=. =chain()= returns
=Err(CannotPlant)= at the second token (pos 1). Case 1
(=S -> S S | a=) fails the same way on =aa=.
| Grammar | Forest building on | Recognition only |
|------------------------------------+-----------------------------+------------------|
| =S -> a S \| a= (right recursion) | n = 1..4 pass | accepted |
| =S -> a a= | n = 1..4 pass | accepted |
| =S -> S a \| a= (left recursion) | n >= 2 fails at pos 1 | accepted, n=1..4 |
| =S -> S S \| a= (Case 1) | n >= 2 fails at pos 1 | accepted, n=1..4 |
So recognition is fine; the failure is in forest construction.
Left recursion is listed in layer 4 of CLAUDE.md, but it already fails
at two tokens without ambiguity or epsilon. Suggestion: stop at this
failure instead of building the oracle first.
** Where the failure surfaces
=insert_item= in =chain/src/item/genins.rs=. The walk up the parents
ends with an empty =stack= and returns =Error::CannotPlant= (line 551).
The dump at the failure shows =parents = []= and
=forest_source = true_source = Virtual(0, 0, 0)=.
* How =insert_item= works
Inputs: an NFA =Edge= (with =forest_source= and =true_source=), a small
=fragment= (a chain of nodes from a nonterminal through a rule node
down to a terminal leaf), and =atom_child_iter= (the NFA nodes the step
moves to). A =PaVi= says where the edge's source sits in the forest:
- =Parent(node, edge, child)=: under a real forest node;
- =Virtual(nt, t, node)=: the nonterminal =node= is only implied by the
collapsed left-closure edge, its expansion down to =t= is not built;
- =Empty=: at the root.
Steps (line numbers in =genins.rs=):
1. 306-316: if =true_source= is virtual, close it by planting the stored
virtual fragment for (nt, t) (=close_pavi=, line 686).
2. 318-375: choose the initial =parents= (rule nodes to hang from).
- =Parent= gives that node; =Empty= gives the root.
- =Virtual=: for each =atom_child=, =atom.trace(nt, t, atom_child)=
gives rule numbers; for each rule fetch
=generate_virtual_frags(nt, t, Some(rule))=, plant it at the start of
=node= and add its second-to-last node as a parent.
=parents= is only ever filled here.
3. 377-395: for a =Parent= source run =reduction()= on the child; if it
produced a different node, replace =parents= by its parents.
4. 403-420: lift each parent from a rule node to the nonterminal nodes
above it.
5. 428-552: for each =atom_child=, =query_reduction= gives the
nonterminals this step completes, innermost first. For each, find a
stack node with that label, close it (=splone= sets its end to =pos=,
splits off clones) and move to the grandparent nonterminals. An
empty stack here means "nowhere to plant": =CannotPlant=.
6. 558-673: =splant= (splone with an open end, then plant the fragment)
under each remaining node, and return the =PaVi= of the planted
terminal (or a =Virtual= one for a single-terminal fragment).
* Why =parents= is empty (partly INFERRED)
- MEASURED: =atom.trace(S, a, 7)= is =[5]= for =S -> S a | a=; node 7 is
the only target with a trace. Rule positions: 5 is
"(NSTa|Ta . )", the end of the second alternative.
- MEASURED: =query_expansion(0, 5)= for the terminal edge from the
nonterminal start is =[(0,2), (0,4), (0,4), (0,4), (0,4)]=.
- INFERRED: virtual fragments are stored under =line[len-2]=, the first
rule of that expansion, which is 2 (=chain/src/atom/default.rs:502,546-549=).
Then =generate_virtual_frags(0, 0, Some(5))= finds nothing, nothing is
planted, =parents= stays empty and the walk has nothing to pop.
- To confirm: print the key set of =virtual_frags.get(&VirtualNode(0,0))=
just after line 549 of =atom/default.rs=, or make
=generate_virtual_frags= temporarily =pub= and call it from the test.
- The =dbg!= at =genins.rs:538= calls =atom.trace(0, 3, ...)= with
hard-coded arguments, so its empty =[]= is meaningless.
* Algorithmic assessment (OPINION; the paper has not been consulted)
The outline (expand / push / reduce, walk up completed nonterminals,
plant) is the standard completer and is a reasonable shape. The
weak points:
1. The machine discards what the forest needs. =chain/src/item/reduction.rs=
header: after the nullable closure a reduction edge looks like a
normal push. The left closure collapses =S => S a => ...= into one
edge in the same way.
2. The three fixes tried: complete at the end (failed), record skipped
nodes (failed because nodes are split and cloned), "guided
brute-force" (perform all possible reductions and rely on =extract=
to prune). The third makes correctness depend on exact pruning,
with no stated invariant. This could explain missing and extra trees.
3. =Edge= carries =forest_source= / =true_source= as =PaVi::Parent(node, ...)=
node numbers, while nodes are split and cloned. Not checked how these
are updated. =query_label(...).expect("the forest was wrongly
planted")= (e.g. =genins.rs:361=) finds nodes by label, assuming labels
are unique.
4. Three tables must agree: =virtual_traces=, =virtual_frags=, reduction
info. They use different notions of "rule" (trace 5 against key 2).
Nothing checks this.
5. Virtual fragments have a fixed depth, but left recursion is
unbounded. The four-times repeated =(0,4)= looks unrolled. The
fragment for (S, a) should arguably be just the base step =S -> a=,
with each later token adding one =S -> S a= level through reduction.
6. =insert_item= places virtual expansions, reduces, walks up and
plants in one function on a live mutable graph where =None= ends mean
"in progress". Failures are hard to localise.
7. Two different lookups serve the same virtual source: =close_pavi=
asks for the accepting fragments (=None= rule) at step 1, while step 2
asks by trace rule. Whether they plant twice or collide is unchecked.
8. The code flags its own doubts: =REVIEW: is this really correct?=
(=genins.rs:707=), =NOTE: ... holds in this case, but not in general=
(=:345=), =panic!("assumption fails")= (=:287=, =:509=).
9. Possible nondeterminism: the edges from a nonterminal start are
collected into a =HashMap= (=atom/default.rs:448-452=). The
=S -> S S | a= dump showed =atom_child = 11= in one run and =7= in
another. Not investigated.
* Suggested next steps
Ordered; the user decides.
1. Confirm the trace/key mismatch (see "Why =parents= is empty").
2. Unit test in the atom: for every (nt, t, target) with a trace,
every traced rule has a matching fragment key. Cheap, and it would
flag mismatches directly, for left recursion and for other grammars.
3. Define a mid-parse invariant and assert it in debug builds after each
token. For example: every =forest_source= / =true_source= points at a
node of the expected kind, and every pending forest node has
start <= pos. This is =validate_forest= applied per token.
4. Check determinism: run =S -> S S | a= on =aa= many times and compare
which =atom_child= fails.
5. Once left recursion and Case 1 get through =chain()=, resume the
original plan from CLAUDE.md: oracle, =unpack=, diff harness,
=validate_forest=, then the layers in order.
6. Ask before consulting the paper. Possible question: how does the
paper build the forest without splitting nodes destructively? Read
only the forest-construction section.
* Known typo in the reference file
=forest-examples.md= Case 1 says "5 packed alternatives in total".
The forest listed has 7 (2 + 1 + 1 + 1 + 1 + 1). The user has
confirmed this is a typo. The file is untouched.
* Probes in =tests/spike.rs=
| Test | Purpose |
|--------------------------------+-------------------------------------------------|
| =locate_failure_case1= | at which token =chain()= first fails, Case 1 |
| =layer1_sanity= | right recursion, left recursion, fixed length |
| =recognition_only= | same inputs with forest building off |
| =probe_atom_left_recursion= | prints traces, expansions and NFA edges |
| =dump_case1= | planned forest dump; currently fails in =chain()= |
Run, for example: =cargo test --test spike probe -- --nocapture=.
Probe output is prefixed with =PROBE=, =RESULT=, =LAYER1= or =RECOG=.
|
