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/CLAUDE SUGGESTIONS.org | 179 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 179 insertions(+) create mode 100644 tests/CLAUDE SUGGESTIONS.org (limited to 'tests/CLAUDE SUGGESTIONS.org') 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=. -- cgit v1.2.3-18-g5258