#+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=.