diff options
Diffstat (limited to 'tests/CLAUDE SUGGESTIONS.org')
| -rw-r--r-- | tests/CLAUDE SUGGESTIONS.org | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/tests/CLAUDE SUGGESTIONS.org b/tests/CLAUDE SUGGESTIONS.org new file mode 100644 index 0000000..f37c7f9 --- /dev/null +++ b/tests/CLAUDE SUGGESTIONS.org @@ -0,0 +1,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=. |