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 ++++ tests/CLAUDE-PROGRESS-ARCHIVE.md | 856 ++++++++++++++++++ tests/CLAUDE-PROGRESS.md | 32 + tests/DESIGN-forest-from-spans.md | 413 +++++++++ tests/DESIGN-leading-chains.md | 153 ++++ tests/oracle.rs | 1803 +++++++++++++++++++++++++++++++++++++ tests/spike.rs | 279 ++++++ 7 files changed, 3715 insertions(+) create mode 100644 tests/CLAUDE SUGGESTIONS.org create mode 100644 tests/CLAUDE-PROGRESS-ARCHIVE.md create mode 100644 tests/CLAUDE-PROGRESS.md create mode 100644 tests/DESIGN-forest-from-spans.md create mode 100644 tests/DESIGN-leading-chains.md create mode 100644 tests/oracle.rs create mode 100644 tests/spike.rs (limited to 'tests') 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=. diff --git a/tests/CLAUDE-PROGRESS-ARCHIVE.md b/tests/CLAUDE-PROGRESS-ARCHIVE.md new file mode 100644 index 0000000..d14365a --- /dev/null +++ b/tests/CLAUDE-PROGRESS-ARCHIVE.md @@ -0,0 +1,856 @@ +# Progress summary (for a new Claude session) + +Written by Claude Code at the user's request, 2026-10-14. Read this first, +then `CLAUDE.md` (project rules) and `forest-examples.md` (reference cases). +Longer notes from earlier in the work: `tests/CLAUDE SUGGESTIONS.org`. + +## START HERE (state at the end of session 2, 2026-10-14) + +**Reading order for a new session:** `CLAUDE.md` -> this section -> +`tests/DESIGN-leading-chains.md` (design + status, section 7). The rest of this +file is chronological notes of session 1 and 2; parts are SUPERSEDED (see +"Superseded claims" below). `forest-examples.md` holds the reference cases; +the memory notes (auto-loaded) hold the working style. + +### Where the work stands (one paragraph) +Recognition works. Forest construction is fixed for: root-level left recursion +(`S -> S a | a` up to 4 tokens, several variants), non-root left recursion +(`T -> x S`, `T -> S x`), an ambiguous left-recursive root +(`S -> x S | S a | a` on `x a a`), a simple indirect case (`S -> A b; A -> S c | d` +on `d b`). All of this is a PROTOTYPE in a scratch copy; NOTHING is applied to +the user's tree (the user writes all source by hand). The task now is: finish +the failing cases below, then hand the user a consolidated, ordered change list +(file, function, what, why; NO diff unless asked) plus regression tests. + +### Scratch copy (the ONLY place the prototype exists; no diff was saved) +- MOVED INTO THE REPO at the user's request (end of session 2): + `/claude scratch/ws` (the prototype, a full copy of the workspace with + its own `[workspace]`, so it is a separate cargo workspace root) and + `/claude scratch/target` (its own, independent build directory, ~420 MB). + `` = `/Users/durand/Desktop/Centre/A propos de programmes/Rust/rep`. + The paths contain spaces: always quote them. +- Run (verified from the new location; identical probe results): + `cd "/claude scratch/ws" && CARGO_TARGET_DIR="/claude scratch/target" cargo test --test oracle -- --test-threads=1` + This is the ONE exception to "write only inside `tests/`" and was explicitly + requested by the user; the user's real sources are still untouched. Do NOT + copy it anywhere (move/edit in place); do not touch the repo's own `target/`. +- Notes: `claude scratch/` is untracked and NOT covered by `.gitignore` + (`/target` only matches the root one); rust-analyzer may index the nested + workspace. Whether to ignore it is the user's decision (not done). +- Safe to delete (ask the user first), still in the old per-session scratchpads + under `/private/tmp/claude-501/-Users-durand-Desktop-Centre-A-propos-de-programmes-Rust-rep/`: + `2f4b067a-.../scratchpad/ws` (old, ~29 MB) and `8010540b-.../scratchpad/` + `{base,target_base,*.txt}` (`base` = pristine copy of the user's tree, used to + show that `test_from_grammar` fails without my changes; `target_base` 121 MB). +- Risk reduced: the prototype no longer lives under `/private/tmp`. Still no + diff of it exists in `tests/`; ask before writing one. +- macOS: `sed -i ''`, BSD sed has no `\b` (use python for edits). zsh: avoid + `for g in $'...'` loops with newlines in the grammar (spurious `.Trash` errors). + +### The prototype = these edits to the user's tree (in dependency order) +(S) = scratch only; status: NEEDED / UNVERIFIED / DEBUG. +1. NEEDED `chain/src/item/reduction.rs` leaf branch (childless Non node closed by + `close_pavi(Virtual)`): after `correct_ends.insert(top, correctness.into())` + add `if correctness && accept_root { order_of_correct_ends.push(top); }` + (FIX-A; the `accept_root` gate is required). +2. NEEDED `graph/src/lib.rs` new module `det` (aliases `HashMap`/`HashSet` over + `BuildHasherDefault`), used in graph (`adset`, + `labelled/double`, `labelled/binary`), grammar (`lib`, `first_set`, `abnf`), + chain (`atom/default`, `reducer`, `default`, `item/reduction`); `new()` -> + `default()`, `with_capacity(n)` -> `with_capacity_and_hasher(n, Default::default())`. + Reason: results of failing cases FLIPPED between runs with random hash order + (measured), so nothing could be diagnosed. Same SipHash speed (inferred). +3. NEEDED `chain/src/default.rs` `derive` (~674): remove the dummy wrapper node 1 + as soon as it exists: `nodes_len() >= 2` instead of `> 2`. +4. NEEDED `chain/src/item/default/mod.rs` `plant_at_start`: `clone_threshold` + always 0 (no dummy child of the root). (S) also `remove_prefix_cut_cycles` + (DFS back-edge cut) replaced `remove_prefix(1)`; with the leading chains + (edit 7) there are no cycles, so it is probably a no-op: UNVERIFIED whether + it can be dropped; try `remove_prefix(1)` again. +5. NEEDED `chain/src/item/default/splone.rs`: + a. `open_ancestors`: add `new_top` as a child of the new open ancestor AFTER + the preserved children, in BOTH branches (clone branch never added it; + plain branch added it first, wrong order when `parent_edge > 0`). + b. `create_new_label`: a parentless existing node is legitimate (not stale) + when `node` is top-level (no parents, or its only parent is a packed node + that is the root or parentless); apply to both the packed and plain + lookups. Fixes two packed clones of the root closing to the same label + (children of both merged into one node). Reproduced without left + recursion: `S -> a A | A b; A -> a | b` on `a b`. + c. New `splone_left(node, pos, edge, wrapper) -> (closed, open)`: if `node` + is open, force the split path (closed copy `C`, `split_parents` + duplicates parents) and keep `node` as the open continuation `O`; if + `node` is already closed at `pos`, `C = node` and `O` is an open copy via + `create_new_label(node, None, ..)` + `split_node`. Then remove all + children of `O` and give it the single child `Rule(wrapper)[p,pos] -> C` + (packed node above `C` if `C` is a clone). +6. NEEDED `chain/src/item/genins.rs` `insert_item`: + a. climb hook before the `splone` of a reduction level: `r` = fragment root + rule, `h = atom.get_rule_num(r)`, `w = atom.left_wrapper(h, reduction_nt, r)`; + if `Some(w)`, the node has no wrapper-parent labelled `Non(h)` with the + SAME START, is plain and (open or closed at `pos`): call `splone_left`, + push `Parent(O, 0)` on `second_stack`, `continue`. + b. virtual branch: loop over ALL fragments from `generate_virtual_frags` + (was `frag.first().unwrap()`), deduplicating pushed parents. + c. UNVERIFIED (no measured effect): `is_last_level` restriction of the hook, + and a final filter keeping only stack nodes labelled `get_rule_num(r)`. + Theory says the filter is correct; drop the level restriction. +7. NEEDED `chain/src/atom/default.rs` (design in `DESIGN-leading-chains.md`): + `first_literals`, `lead`, `chains`, `left_wrappers` computed from the NFA + before `nfa.closure(..)`; `virtual_frags: Map>>` + built from `chains`; `generate_virtual_frags` returns all alternatives; + accessors `left_wrapper(h, y, r)` and `chains_of(nt, t)` (tests). + `expansion_map` is no longer read by the parser. +8. DEBUG (S): `eprintln`/`dbg_dump` under env `DBG`, `DBGLEAD`, `DBGEXP`; + `generate_virtual_frags` made `pub` (the user's tree has it `pub(crate)`); + scratch-only tests in `tests/oracle.rs`: `diag_left` (env `DIAG_GRAMMAR`, + `DIAG_INPUT`, `DIAG_END`), `probe_cases`, `probe_one`. `probe_cases` and + `probe_one` were copied into the user's `tests/oracle.rs` as `#[ignore]`. + +### Results now (deterministic; heights 1..5 against the oracle) +PASS: layer 1 (incl. right recursion n=1), `layer4_left_recursion` (n=1..4), +`S -> S a | b`, `S -> S a b | c`, `S -> S a | a | b`, `T -> x S; S -> S a | a` +(`x a`, `x a a`, `x a a a`), `T -> S x; S -> S a | a` (`a a x`), +`S -> x S | S a | a` (`x a a`), `S -> S S | a` (`a a`), +`S -> A b; A -> S c | d` (`d b`), `S -> a A | A b; A -> a | b` (`a b`). +FAIL (not yet analysed unless noted): +- `S -> x S | S a | a` on `x x a a a`: panic "attempt to subtract with overflow". +- `S -> A b | d; A -> S c` on `d c b`, `d c b c b`: CannotPlant at token 1. +- `S -> S S | a` on `a a a` (layer 2, blocks Case 1 and 2): EXTRA + `(S (S a) (S a) (S a))` (an `S` with three `S` children) and MISSING + `(S (S (S a) (S a)) (S a))`. Smallest layer-2 failure: START HERE. +- layer 3 (epsilon): epsilon nodes missing. layer 5 (cycles): cyclic + derivations missing (chains drop back edges, nothing creates `S -> R -> S`); + case 5d CannotPlant at token 1. +- chain crate unit test `atom::default::test_default_atom::test_from_grammar` + fails 8/8 on a pristine copy of the user's tree too (hard-coded virtual node + numbers 166..=173 and an absolute path): NOT caused by the prototype. + +### Next steps (suggested order) +1. Trace `S -> S S | a` on `a a a` with `DBG=1 DIAG_END=1 DIAG_GRAMMAR=... DIAG_INPUT=... + cargo test --test oracle diag_left -- --nocapture --test-threads=1`. +2. The overflow panic on `x x a a a`; then `d c b` (indirect: the chain for + `[A]^d` exists, check the climb with `h != nt`). +3. Design layer 5 (who creates the cycle `S -> R -> S` for unit/cyclic + productions) and layer 3 (epsilon nodes; nullable leading symbols in chains). +4. `reduction_map` is built by the same iterative closure with the same + "longer wins" guard as `expansion_map` was: possible analogous defect, not + measured. +5. When the probe set and `layer2_*` pass: write the consolidated change list + for the user; every fix gets a regression test that fails before it. + +### Superseded claims (older sections of this file) +- "OPEN DESIGN QUESTION" / "Suggested next steps" / "Scratch state at the time of + writing": superseded by this section. +- "Nondeterminism ... HARMLESS": wrong for the failing cases; they flipped + between runs. The user allowed restoring order (deterministic hasher, edit 2). +- "junk expansion is the cause" (finding 1): partly right. Measured later: + `(0,13)` is first written correctly, then overwritten by a longer entry from + another composition; now bypassed by the leading chains. +- The "last level only" restriction of the continuation fork was a guess with + no measured effect (see edit 6c). +- User preferences confirmed this session: deterministic hashing is fine; a + redesign of how information is recorded is fine (the user confirms first); + the paper is NOT to be consulted (their forest construction differs from + Herman's). + +## How the user wants to work (keep following this) + +- The user writes all source by hand. Claude plans, explains, and writes files + ONLY inside `tests/`. Do NOT write diffs unless the user asks for one. +- Run experiments ONLY on a scratch copy of the repo, never in the user's tree + (the user said so; cargo in the real tree would also write to its `target/`). + Keep scratch space small and delete it when debugging is done. + Copy: `chain grammar graph graph_macro forest nfa receme semiring tokens viz + src tests examples Cargo.toml Cargo.lock`, and build with + `CARGO_TARGET_DIR=/target cargo test ...`. +- Say what is MEASURED, what is INFERRED, what is a guess. Do not claim + more. Ask before opening any paper PDF (see `CLAUDE.md`). +- macOS: use `sed -i ''`. The parser prints a lot; the tests capture it. +- The parser's debug dumps write to a relative `output/` directory; the + test harness `chdir`s into `$TMPDIR/rep-tests` (with `output/`) first. + +## Project in one paragraph + +Rust implementation of Herman's relational parsing (chain-rule machine over an +NFA of "atomic languages"). Recognition works; the FOREST (shared packed +parse forest) is wrong. Goal: the forest represents exactly the derivation +trees of the input, shared properly. Construction is in `chain/` +(`chain/src/default.rs` `derive` / `end_of_input`; `chain/src/item/genins.rs` +`insert_item`; `item/default/{mod,splone,extract}.rs`; `item/reduction.rs`). + +## The test tooling (DONE): `tests/oracle.rs` + +- Brute-force oracle `oracle_trees(grammar, tokens, h)`, validated against all + of `forest-examples.md` (10 checks pass). Case 1 in that file says "5 + packed alternatives"; the real count is 7 (user confirmed it is a typo). +- `parser_side` module: builds the parser from the same grammar text, runs it + (per-case timeout, default 20 s, `REP_TIMEOUT`; panics and errors are caught), + `unpack(forest, names, h, limit)`, `classify` (missing / extra / duplicate), + `validate_forest` (span coverage, unique nodes, terminals, productions, + cycles within one span, size bound), and the test layers of `CLAUDE.md` + (layers 1-5, plus layer 6 random grammars, `#[ignore]`, `REP_SEED`, + `REP_CASES`). Run: `cargo test --test oracle -- --test-threads=1`. +- Grammar syntax in tests: `"S -> S S | a"`, several lines for several + nonterminals, `eps` for an empty alternative. Names are mapped to letters + because `scan_tnt` only accepts letters in `T` / `N`. +- `tests/spike.rs`: early probes (partly obsolete). `tests/exp.diff`, + `tests/fix-experiments.diff`: old probe/experiment diffs (obsolete; the + experiments below supersede them). +- Empty input is NOT supported by the API: `end_of_input(pos, ter)` needs the + last token, and `ter` selects virtual fragments (atom/default.rs:489-549, + genins.rs:730), so an arbitrary terminal is not safe. Deferred to the + epsilon layer. The "END_OF_INPUT token" is NOT a convention of this project. + +## Forest convention (verified on forests of passing grammars) + +- A nonterminal node's children are "position wrappers" `Rule(pos)`, one per + right-hand-side symbol, in order; each wrapper has exactly one child, the + symbol. Wrapper span = its child's span. Example for `S -> a a` on `aa`: + `S[0,2] -> [Rule(2)[0,1] -> a, Rule(3)[1,2] -> a]`. +- Ambiguity: a `Packed` node (labelled like the nonterminal) whose children are + `Cloned(i)` nodes, one per alternative. +- Nodes are unique by label = (symbol, start, end) (`forest/src/design.org`, + axiom 1). `plant` identifies fragment nodes with forest nodes BY LABEL. +- `extract(pos)` takes the node labelled `Non(0)[0,pos]` (closed copy of the + root) as the answer root; any node without an end infects its relatives. + So a closed `S[0,pos]` MUST exist at the end. +- Unverified assumption in `unpack`: an epsilon production is a childless + nonterminal node. Observed instead: epsilon nodes are MISSING (layer 3). +- The dummy root: `unit()` makes root `S[0,None]`; the first step plants + `[Rule(6), Non(0)]` under it, which merges back onto the root: a cycle + `S -> Rule(6) -> S`. Per the user it only exists so the code can work on an + almost empty forest and SHOULD be removed early (`derive`, default.rs:673-683, + and `end_of_input`). Do not keep it alive (experiment E5 did; it was wrong). + +## Results on the ORIGINAL code (baseline, as in the user's tree) + +| layer / case | result | +|---|---| +| 1 fixed length, nested nonterminals | pass | +| 1 right recursion `S -> a S \| a` | n >= 2 pass; **n = 1: empty forest** | +| 2 Case 1 `S -> S S \| a`, Case 2 | n = 1 empty forest; n >= 2 `CannotPlant` at token 1 | +| 3 epsilon (Case 3, 4, nullable middle) | epsilon nodes missing / empty forest | +| 4 left recursion, hidden left recursion | `CannotPlant` at token 1 (n=1 empty) | +| 5 cyclic: 5a, 5c, highly ambiguous with eps | TIMEOUT: the parser never terminates | +| 5 Case 5d | `CannotPlant` at token 1 | + +## Findings + +### Verified fix FIX-A (not applied to the user's tree) +`item/reduction.rs` ~line 357, in the leaf branch (childless Non node closed via +`close_pavi(Virtual)`): after `correct_ends.insert(top, correctness.into());` +add `if correctness && accept_root { order_of_correct_ends.push(top); }`. +Without it no closed `S[0,pos]` is made and `extract` returns nothing. The +`&& accept_root` gate is REQUIRED: without it two layer-1 tests regress +(`reduction` is also called mid-parse from `insert_item`). Regression test: +`layer1_right_recursion` (now starts at n = 1) fails before, passes after. +It does not fix left-recursive one-token inputs. + +### Root cause of `CannotPlant` on left recursion (MEASURED) +1. `grammar/src/lib.rs:722-781` (`transform_label_null_epsilon`): the + left-linear `expansion_map` is keyed by (source, target), so the direct edge + and the left-recursion composite edge share one entry, and every closure + pass re-extends it. The recorded expansion is junk for left recursion + (length 4-10 depending on order and iteration count). Right recursion gives + a correct length-1 expansion. +2. `generate_fragment` (genins.rs:79-88) merges nodes by label, so the repeated + pairs collapse into a CYCLE: `S -> R2 -> S` plus `S -> R5 -> a`. +3. `plant_at_start` (item/default/mod.rs:963) calls `fragment.remove_prefix(1)` + (deletes node 0 and all its edges; assumes a chain): the cycle and the + second root child are dropped, leaving `R4` (childless, planted) and a + floating `R2 -> a`. `insert_item` then finds that floating rule node by + `query_label` (no parents), the lift in step 4 gives `[]`, empty stack, + `CannotPlant`. +4. The `trace`/`virtual_frags` tables DO agree (trace value == fragment key); + my earlier "key mismatch" claim was wrong. + +### Nondeterminism +Hash iteration order made atom numbering vary between runs (graph/labelled/ +double.rs, grammar/lib.rs, first_set.rs, atom/default.rs). Measured +HARMLESS for the results above (identical over repeated runs with the original +hashing); the user deliberately keeps hash order for speed. If a result is +flaky, repeat the run before suspecting anything else. + +### Left-recursion fragment experiments (scratch only) +| shape | root `S -> S a \| a` | non-root `T -> x S` | +|---|---|---| +| E3 base only `S -> R5 -> a` (cut expansion at first pair with nt = the nonterminal) | 1 token ok; continuation lost: 2nd `a` attaches to T's rule | same | +| E4 one wrapper level + explicit closed flags (`generate_fragment_with_closing`) | correct up to 2 tokens | spurious unit layer `(T x (S (S a)))` | +| E6 keep the cycle, graft root children, `set_pos` does not close past root | `splone` assertions ("a rule node should not have more than one child"); closed copy keeps the cycle wrapper | same | +Beyond 2 tokens with the dummy removed early: closing `S[0,2]` leaves no +parent to climb to (the wrapper `Rule(2)[0,2] -> S[0,2]` is never created). + +## DESIGN DECISION (session 2, 2026-10-14): the climb creates the continuation + +Decided with the user: when a left-recursive `S` closes (e.g. `S[0,1]`), the +CLIMB in `insert_item` (through `splone`-like closing) creates the wrapper +`R4[0,1] -> S[0,1]` and the new open `S[0,None]` above it. The fragment does +NOT carry the continuation. The user thinks their forest construction differs +from Herman's, so the paper is not to be consulted. + +Evidence (MEASURED on `S -> S a | a`, input `a a`, scratch copy with a +diagnostic test `diag_left`, not in the repo): +- NFA (state numbers): `0 -a(moved 2)-> 5`, `0 -S(moved 4, left_p)-> 9`, + `5 -a(moved 5)-> 11` (reduction [0]), `11 -a(moved 5)-> 11` (reduction [0], + expansion only [(0,5)]), virtual node `[S]^a` = 14 with + `14 -a(moved 5)-> 11` (reduction [0], accepting). +- `expansion(0,5) = [(0,2),(0,4),(0,4),(0,4),(0,4)]` (junk repeat of (0,4)). + Harmless for the stored virtual fragment: merging by label collapses it. +- Stored virtual fragment of `[S]^a` (rule 2) is + `S[0,None] -> {R4[0,None] -> S (back edge: CYCLE), R2[0,1] -> a[0,1]}`. + `trace(0,0,11) = [2]`; `trace(0,0,5)` and `trace(0,0,9)` are empty. +- After token 0 the forest holds only the dummy root (`S -> Rule(6) -> S`): + the virtual fragment is materialized LAZILY at token 1 (`PaVi::Virtual` + branch of `insert_item`, `plant_at_start` + `remove_prefix(1)`), which drops + the cycle: result `R4[0,1]` childless + floating `R2[0,1] -> a`, then + `CannotPlant` (parents = []). + +Why the climb (INFERRED from the above): +1. Axiom 1: outer and inner `S` both start at 0 and are open, so they get the + same label; a fragment can only express the pair as a cycle. +2. The loop `11 -a-> 11` repeats the continuation at EVERY further token, but + its expansion is just [(0,5)]: nothing in a fragment supplies `R4` for the + 2nd, 3rd... iteration. Only the climb runs every time. +3. Commit `a80db17` says reductions are meant to close nodes at every step. +4. The wrapper rule number is available: it is the `moved` of the left-linear + `Non` edge (here 4), and the second component of the `(nt, rule)` pairs of + the expansion. + +Sketch for the user's implementation (not written, to be checked): +(a) plant only the acyclic base `S[p,None] -> R2[p,q] -> a[p,q]` (cut the back +edge instead of `remove_prefix`); (b) on reduction [S] splone/close `S[p,q]`; +(c) if `S` is left-recursively continued, add `R4[p,q] -> S[p,q]` as the first +child of a fresh open `S[p,None]`; (d) the next terminal's wrapper `R5` goes +after `R4`. OPEN: indirect left recursion (`S -> A b`, `A -> S c`), and +non-root nonterminals (`T -> x S`, E4 gave a spurious unit layer there). + +### PROTOTYPE RESULT (session 2, scratch copy only; MEASURED) + +Scratch copy: `/ws` (original code + the edits below + debug +`eprintln` under env `DBG` + a `diag_left`/`probe_cases` test in its +`tests/oracle.rs`). Edits, described in words (no diff written): +1. FIX-A (gated on `accept_root`), as before. +2. `derive` (default.rs ~line 674): remove the dummy wrapper node 1 as soon as + it exists (`nodes_len() >= 2` instead of `> 2`). +3. `plant_at_start` (item/default/mod.rs ~963): new `remove_prefix_cut_cycles` + instead of `remove_prefix(1)`: also drops the wrapper nodes that are parents + of the fragment root (the cycle back edges) and the nodes they leave + isolated; and `clone_threshold` is always 0 (no dummy child of the root). +4. New `left_continue(closed, wrapper_rule)` (item/default/mod.rs, next to + `remove_node`): adds `wrapper[p,q] -> closed` and an open `cont[p,None] -> + wrapper` (reusing existing nodes by label), and makes `cont` the forest root + if `closed` was the root. +5. Climb hook (genins.rs, just before `let parents_iter = self.parents_of( + node.node())` after the `splone` in step 1). FIRST VERSION (superseded): + "closed node has no parents" + wrapper = fragment slot - 1 (arithmetic + hack, wrong in general: slot numbers are regex NODE ids, not a sequence). + CURRENT VERSION = condition (1), using only existing accessors: + `r` = fragment root's `Rule(r)`; `h = atom.get_rule_num(r)` (head of the + slot; `accumulators` are in regex-node units, same unit as `moved`); + `w = left_wrapper(atom, h, nt, r)`: look in `atom.labels_of(2 * + atom.nth_accumulator(h))` for an edge with `is_left_p()` and value + `Non(nt)` (nt = the reduced nonterminal), whose target state has an + outgoing edge with `get_moved() == r`; `w` is that left-linear edge's + `get_moved()` (e.g. 4 for `S -> S a`). Then, unless the closed node + already has a rule-wrapper parent whose parent is labelled `Non(h)`, call + `left_continue(closed, w, h)` (continuation labelled `Non(h)`, so it also + covers indirect left recursion, modulo the longer cycle, see below). + `regexp` in `DefaultAtom` is private and has no accessor; none is needed. + +Results (heights 1..5 vs the oracle, `validate_forest` included): +- PASS: `S -> S a | a` for n = 1..4 (stable over 8 repeated runs, so hash + order is not an issue here); `S -> S a | b`; `S -> S a b | c`; + `S -> S a | a | b`; `S -> S S | a` on `a a`; `T -> x S; S -> S a | a` on `x a`. + Layer 1 still passes (fixed length, nested, right recursion). + With condition (1) the root-level results are identical (same passes). +- FAIL, non-root left recursion: `T -> x S; S -> S a | a`: `x a a` gives EXTRA + `(T x (S a) a)` and MISSING `(T x (S (S a) a))`; `x a a a` MISSING one tree; + `T -> S x` with `a a x`: CannotPlant at token 1. MEASURED: condition (1) + DOES fire here (`r=7 h=S nt=S w=6`) and builds `S'[1,None] -> R6 -> S[1,2]`, + so the condition is not the problem. The problem (measured on the forest + dump): the closed `S[1,2]` has two wrapper parents, T's `R3[1,2]` and the new + `R6`; the existing lift goes through BOTH, so the fragment is planted under + T as well as under `S'` (spurious), and `S'` has no open wrapper under an + open copy of T. Needed (design, not yet tried): in the continuation case + lift ONLY through the new wrapper, and give `S'` an open wrapper + `R3'[1,None]` under an open alternative of T (split: closed T alternative + with `R3[1,2]`, open one with `R3'`); `split_node`/`split_parents` already + do the closed/open duplication for ordinary closings. Alternative worth + trying: force the SPLIT path of `splone` (closed copy C, parents duplicated + by `split_parents`) and rewrite the surviving open node O to have the single + child `R_w[p,q] -> C`, so root and non-root cases are handled uniformly. +- FAIL, ambiguity: `S -> S S | a` on `a a a` (2 trees missing). +- FAIL, indirect left recursion (`S -> A b; A -> S c | d`, and + `S -> A b | d; A -> S c`): "assumption fails" panic / CannotPlant. Inferred: + the virtual fragment has a cycle of length 2 (`S -> R -> A -> R' -> S`); + `remove_prefix_cut_cycles` only drops the wrapper `R'` that points to the + root, leaving `A` and its wrapper planted childless. A general cut must drop + the whole cycle path through the root. +- Layers 2-5 other cases still fail as in the baseline table (not re-examined). + +### OPTION B RESULT (session 2, last scratch run; MEASURED) + +Implemented in the scratch copy (now unavailable, see below): in the climb, BEFORE +the `splone` of a reduction, if condition (1) holds for (fragment root slot +`r`, head `h = get_rule_num(r)`, reduced `nt`) and the open node has no wrapper +parent labelled `Non(h)` with the SAME START (the start check is new) and is a +plain open node, then call a new method `splone_left(node, pos, edge, w)` +(splone.rs): `create_new_label(node, Some(pos), edge, None)` + `split_node` to +get the closed copy `C` (parents duplicated by `split_parents`), then remove +all children of the surviving open node `O` and give it the single child +`Rule(w)[p,pos] -> C` (the packed node above `C` if `C` is a clone). The lift +then pushes only `Parent(O, 0)` (skips the generic lift through `C`'s +parents). The forest root is NOT reassigned any more (`O` is the root). + +- Now PASS: `T -> x S; S -> S a | a` on `x a`, `x a a`, `x a a a` (fixed by + option B; before: extra/missing trees); `S -> S a | a` n = 1..4 (no regression); + all other earlier passes unchanged. +- Still FAIL: + - `T -> S x; S -> S a | a` on `a a x`: CannotPlant at token 1 (not analysed). + - `S -> x S | S a | a` on `x a a`: MISSING `(S (S x (S a)) a)`, EXTRA + `(S x (S (S (S a)) a))` at h = 4; on `x x a a a`: panic "attempt to subtract + with overflow" at genins.rs:646 (not analysed; line numbers refer to the + scratch file). + - `S -> S S | a` on `a a a`: now 1 missing + 1 extra tree (was 2 missing). + - Indirect left recursion: unchanged (assumption-fails panic / CannotPlant). +- Layers 2-5 of the oracle test file: not re-run after option B. + +### SESSION 2, LATER (MEASURED unless marked) + +**Scratch location.** The scratchpad path of the session changed +(`2f4b067a-...` -> `8010540b-...`); the old copy was NOT deleted. It was copied to +`.../8010540b-.../scratchpad/ws` (build dir `.../scratchpad/target`). The old +directory `.../2f4b067a-.../scratchpad/{ws,target}` (~250 MB) is untouched and +can be deleted by the user. Still no diff saved: the edits are described here. + +**Determinism (new scratch edit, E0).** Results of the failing probe cases +FLIPPED between runs (CannotPlant / "assumption fails" / missing / extra), so +nothing could be diagnosed. Measured: 6 runs, passing cases identical, 4 of the +failing cases varied. Fix tried in scratch: a `graph::det` module with +`HashMap`/`HashSet` aliases over `BuildHasherDefault` (fixed +SipHash keys), used in graph (adset, labelled/double, labelled/binary), +grammar (lib, first_set, abnf), chain (atom/default, reducer, default, +item/reduction); constructors `new()` -> `default()`, +`with_capacity(n)` -> `with_capacity_and_hasher(n, Default::default())`. +After that, 6 runs of the probe set gave byte-identical results. Speed: same +SipHash as the default hasher, only a constant key, so lookups stay O(1) +(INFERRED, not benchmarked). A BTree container would be O(log n) and needs +`Ord` keys. + +**Reduction levels (E7, option B refinement).** The continuation fork is only +done at the LAST level of `reduction_info` (the level at which the fragment is +planted); earlier levels use the normal `splone`. (Hypothesis from reading; +it changed no probe result by itself, but it is the logical rule.) + +**Two calls per token (measured on `S -> x S | S a | a`, `x a a`).** At the +token after `x a`, `derive` makes TWO `insert_item` calls (edges 17 and 20) +sharing `true_source = Virtual(0,1,5)`. Call A closes the virtual node 5 +(`S[1,..]`) IN PLACE through `close_pavi`, so in call B the node is already +`S[1,2]`. Hence `splone_left` now has a second case: node already closed at +`pos` -> make the open continuation `O` by the standard re-open path +(`create_new_label(node, None, ..)` + `split_node`, which calls +`open_ancestors`), then rewrite `O` to `R_w[p,pos] -> C`. The hook's condition +accepts `end == None` or `end == Some(pos)`. `splone_left` returns `(C, O)` and +the climb pushes `Parent(O, 0)`. + +**Bug found in `open_ancestors` (splone.rs ~ line 590; measured on the forest +dump).** (1) In the clone branch the new open ancestor never receives the +reopened child `new_top` (orphan wrapper, e.g. `R8[1,None]` without parent); +(2) in the plain branch `new_top` is added BEFORE the preserved children, so +the child order is wrong whenever `parent_edge > 0`. Scratch fix: add +`new_top` after the preserved children in both branches (remove the edge from +the plain `else`). With it the forest of `x a a` after token 2 is exactly +right: root packed with clone0 `[R4[0,2]->S[0,2], R5->a]` and clone1 +`[R7->x, R8'[1,None]->S[1,None]->[R4[1,2]->S[1,2], R5->a]]`. + +**Results now (deterministic):** +- PASS (unchanged): all earlier passes, incl. `T -> x S; S -> S a | a` on + `x a`, `x a a`, `x a a a`; `S -> S a | a` n = 1..4. Layer 1 and + `layer4_left_recursion` pass; no regression in the full run. +- FAIL, now a DIFFERENT bug class (ambiguity at closing, NOT left recursion): + `S -> x S | S a | a` on `x a a` fails only when `end_of_input` closes the two + packed clones of the root: both close to the label `S[0,3]` and the node + ends up with the children of BOTH (`S -> [S, a, x, S]`, not a production). + Reproduced WITHOUT left recursion: `S -> a A | A b; A -> a | b` on `a b` + gives EXTRA `(S (A a) b a (A b))` and MISSING `(S (A a) b)`, `(S a (A b))`; + also `S -> a b | A b; A -> a | a b`. Suspect: `reduction()` + + `splone` on cloned nodes / `create_new_label` returning `Cloned` and then + `split_node` (INFERRED, not yet traced). This is the baseline "layer 2" + failure. +- FAIL, unchanged class: `T -> S x` (`a a x`) CannotPlant at token 1; + `S -> x S | S a | a` on `x x a a a` overflow panic; `S -> S S | a` on + `a a a` (EXTRA); indirect left recursion (panic "this should be a rule + parent" / CannotPlant). + +### SESSION 2, LEADING CHAINS PROTOTYPE (design: `tests/DESIGN-leading-chains.md`) + +User confirmed: multiple virtual fragments per (virtual node, final slot) are +fine and must each be inspected by the consumers; the leading edges are read +from the NFA (in `DefaultAtom::from_grammar`, where it exists). + +Implemented in the scratch copy (prose, no diff): +- `first_literals(nfa, starts, state)`: literal edges reachable from `state` by + epsilon edges WITHOUT entering another nonterminal's start state. Note: in + the pre-closure NFA the first epsilon edge out of a start state has NO label + entry (`children_of(0) = [2]` but `labels_of(0)` is empty); unlabelled edges + must be treated as epsilon. The edge `4 -eps-> 8` into `S`'s start state is + the left-linear link and must not be followed. +- Before the closure: `lead[N]` = `first_literals(start(N))`; + `chains[(N,t)]` = simple paths in the leading graph (no repeated nonterminal; + repeats only stop the search); `left_wrappers[(h, Y, r)] = w`. +- `virtual_frags` is now `Map>>`, filled from + `chains` (a chain is used for the closure edge whose `moved` equals its last + slot; duplicates skipped). `generate_virtual_frags` returns ALL alternatives. +- `insert_item` virtual branch loops over all fragments (parents deduplicated); + `left_wrapper` is now `atom.left_wrapper(h, nt, r)`, a table lookup. +- `expansion_map` is no longer read by the parser (still written). + +MEASURED chains (slots vary with the encoding): `S -> A b; A -> a`: +`chains(S,a) = [[(S,2),(A,6)]]`; `S -> S a | a`: `[[(S,2)]]`, left wrapper +`(S,S,5) -> 4`; `T -> S x; S -> S a | a`: `chains(T,a) = [[(T,2),(S,6)]]` +(the previously missing fragment); indirect `S -> A b | d; A -> S c`: +`chains(A,d) = [[(A,8),(S,2)]]`. + +Probe results now (deterministic, heights 1..5): PASS: all earlier passes plus +`T -> S x; S -> S a | a` on `a a x`, `S -> x S | S a | a` on `x a a` (after the +`create_new_label` top-level fix), `S -> A b; A -> S c | d` on `d b`. +FAIL: `S -> x S | S a | a` on `x x a a a` (panic "attempt to subtract with +overflow", not analysed); `S -> S S | a` on `a a a`; `S -> A b | d; A -> S c` +on `d c b` and `d c b c b` (CannotPlant at token 1). Layer 1 and +`layer4_left_recursion` still pass. The full oracle run now takes 0.16 s (the +cyclic layer-5 cases used to time out; they now fail fast). + +Layer 2-5 symptoms now: +- layer 2 (`S -> S S | a`, `E -> E + E | n`), 3 inputs: EXTRA + `(S (S a) (S a) (S a))` = an `S` node with THREE `S` children (not a + production) and MISSING `(S (S (S a) (S a)) (S a))`. Looks like the + continuation/wrapper order for a left-recursive rule whose leading symbol + is followed by the SAME nonterminal (INFERRED, not traced). +- layer 3 (epsilon): epsilon nodes missing (as in the baseline). +- layer 5 (`S -> S | a`, `S -> A | a; A -> S`): MISSING the cyclic derivations. + The chains drop back edges, so nothing creates the cycle `S -> R -> S`. + Expected: the completer must create it when `S[0,1]` closes (to be designed). + Case 5d: CannotPlant at token 1. + +Not a regression: the chain crate unit test `atom::default::test_default_atom:: +test_from_grammar` fails 8/8 on a pristine copy of the user's tree (it asserts +fixed virtual-node numbers 166..=173 for an absolute-path grammar file). + +Extra scratch dirs now: `/base` (pristine copy of the user's tree) +and `/target_base`; delete when no longer needed. + +## Understanding of `insert_item` (genins.rs:178) +Steps: close `true_source` if virtual; choose initial `parents` per `PaVi` +(`Parent` / `Virtual` -> materialize via `trace` + `generate_virtual_frags` +then `plant_at_start` / `Empty` -> root); `reduction()` on the child for +`Parent` sources; lift parents from rule nodes to Non nodes; per `atom_child` +climb through the nonterminals in `query_reduction` (`splone` each); empty stack += `CannotPlant`; `splant` the fragment; return a new `PaVi`. A redesign was +discussed (split into named phases; move the "virtual marker" call at +default.rs:807 out of `insert_item`) but nothing depends on it yet. + +## Suggested next steps (SUPERSEDED, see START HERE) +1. (Design settled, see above.) Trace what `splone` and `reduction` do when + `S[0,1]` closes, and where step (c) would go. +2. Apply FIX-A (user's hands) and re-run `--test oracle`. +3. Fix left recursion per the answer; the expansion junk (finding 1) must be + handled either way. +4. Then Case 1 / Case 2 cycles (E4 gave "depth bound exceeded"; unanalysed), + epsilon nodes (layer 3), and the TIMEOUT on cyclic grammars (layer 5). +5. Memoization (step 5 of `CLAUDE.md`) is skipped; none exists. + +## Scratch state at the time of writing (SUPERSEDED, see START HERE) +Scratch copy `.../scratchpad/wsb` (original code + gated FIX-A + oracle tests) +and `.../scratchpad/targetb` (~240 MB) under +`/private/tmp/claude-501/-Users-durand-Desktop-Centre-A-propos-de-programmes-Rust-rep/`. +They are session-specific; delete them when no longer needed. + +## Session rep-3 (2026-10-14/15): Case 1 (S -> S S | a) fixed up to 7 tokens in scratch + +All edits are in `claude scratch/ws` only (nothing in the user's tree). Result: `layer2_case_1` +passes; every previously-passing test still passes; layer3/4-hidden/5 and the probes +`x x a a a`, `d c b`, `d c b c b` still fail (unchanged). + +Root causes found this session (MEASURED via DBG traces, fixes verified by the oracle): +1. `genins.rs` hook condition required `clone_index().is_none()`; clones are the normal case in + ambiguous grammars. Removed. +2. `graph/src/labelled/binary.rs` `PLChildren::remove` never removed the key from `indices` + (HEAD bug): `has_edge` stayed true after `remove_edge`, so re-adding an edge was skipped. +3. `splone_left` was not idempotent (several `insert_item` calls per position): early return when + the open node's first child is already the wrapper. +4. `open_ancestors`, `Eon::Ex` branch: do not add an edge blindly; push a (parent, new_top) pair. +5. Hook "already hooked" check (closed node under wrapper `w` of an open non-packed `h` node). +6. NEW cascade: after hooking `closed`, the open `h` ancestors whose LAST child is a rule wrapper + (closed at pos, rule == fragment root rule) over `closed` complete at `pos` too; push them on + `stack`. (Without it S[0,4] / S[0,5] lose the split-at-2 alternative.) +7. NEW `splone_left` dedupe: two alternatives of one span produce the same continuation; reuse + the existing open sibling (closed-node branch: before reopening; open-node branch: `bury` the + duplicate clone). `bury` (splone.rs) drops edges and relabels with a unique dummy label so + label lookups never find an orphan (orphans broke `has_same_children`/`clone_node` asserts). +8. NEW `close_pavi(Virtual)`: do not replant the virtual alternative into a node that was already + turned into a left-recursive continuation (first child is a closed left-wrapper rule node; + `atom.is_left_wrapper_rule`). It created a bogus open clone `S[2,None] -> [a]`. +9. NEW `reduction.rs` `repair_stale_last_children` (called in `end_of_input`): top-down `splone` + in `reduction` leaves closed copies whose last child is still the open rule node although a + closed twin exists (the `Eon::Ex` path never rewires). Point the edge at the twin, or `bury` + the copy if a sibling alternative already equals the repaired one. +Debug-only: `dbg_dump` calls in `end_of_input`, `SL ...`, `CASCADE`, `HOOKED_ALREADY`, `REPAIR`. +Not yet: regression tests in tests/ for 2 (graph unit test), 6-9 (Case 1 at 4,5,6 tokens already +covered by `layer2_case_1`), mid-parse application of the repair (only EOI so far). + +### Regression tests added (tests/oracle.rs, module parser_side; also in the scratch copy) +Verified fail-before with scratch-only `NOFIX_` env switches (each fix off, others on): +- `regression_graph_remove_edge_clears_index` <- GRAPH (`PLChildren::remove` indices) +- `regression_case1_three_tokens_idempotent_hook` <- IDEMP (`splone_left` early return) +- `regression_case1_four_tokens_clone_hook` <- CLONE (hook on clones), HOOKED (already-hooked reuse), IDEMP +- `regression_case1_five_tokens_cascade` <- CASCADE, DEDUPE, REPAIR (and the three above) +- `regression_case1_seven_tokens_virtual_and_ex` <- VIRT (`close_pavi` replant), EX (`open_ancestors` Ex), and all above +Caveat: CLONE/HOOKED, CASCADE/DEDUPE/REPAIR and VIRT/EX are not isolated from each other by any +input I found; the test names the group. Still-open failures found by the matrix (not fixed): +`S -> S S | S a | a` on `a a a a` (panic), `E -> E + E | n` on 5 operands, `S -> S S S | a` on 5 tokens. + +## Archived from CLAUDE-PROGRESS.md on 2026-10-16 (prototype edits, regression tests, Updates 1-14) + +The prototype edits 13-24 below are OBSOLETE (see `tests/DESIGN-forest-from-spans.md`). +Headings are demoted one level. + +### Current results (scratch, deterministic, heights 1..5 vs the oracle) +PASS: layer 1, `layer2_case_1` (`S -> S S | a`, up to 7 tokens), `layer2_case_2`, +`layer4_left_recursion`, `validate_oracle::*`, the 10 regression tests, and probes: +`S -> S a | b`, `S -> S a b | c`, `S -> S a | a | b`, `T -> x S; S -> S a | a`, `T -> S x; ...`, +`S -> x S | S a | a` (`x a a`, `x x a a a`, `x x x a a a`), `S -> A b; A -> S c | d` (`d b`), +`S -> S S | S a | a` on 1..6 tokens, `E -> E + E | n` on 3 and 4 operands, `S -> S S S | a` on 3 tokens. +FAIL (open): +- `S -> S S | S a | a` on 7 and 8 tokens: MISSING trees only (no extras, no duplicates, invariants OK). + MEASURED (`DIAG_ALTS`): `S[0,6]` has only the splits k=1 and k=5; the splits k=2,3,4 are lost. + Cause (MEASURED in the dumps): `reduction()` at the entry of an `insert_item` closes the frame named by the + item's forest_source; `split_parents` then makes OPEN clones of the ancestors whose last child is the new + CLOSED wrapper (e.g. node 177 `S[0,None] -> [R7[0,2], R8[2,6]]`). Nothing completes them: the cascade + (edit 6) only follows wrappers whose rule equals the item's fragment-root rule (here 8 vs 5), and the item's + `stack` only holds the parents of ONE reduced node. INFERRED: the frames of S[2,*] need an item of their own + at that position, and the obsolete (stale) items that used to serve them were dropped by edit 13. + Tried and rejected: letting the cascade follow every wrapper that is the last position of its production + (`atom.is_accepting(rule*2+1)`): 6 tokens then lose `S[0,5]` splits. Not kept. +- `E -> E + E | n` on 5 operands: 1 MISSING tree (`(E (E (E (E n) + (E n)) + (E (E n) + (E n))) + (E n))`). +- `S -> S S S | a` on 4 tokens (NOT derivable: the forest must be empty) is ACCEPTED with trees like + `(S (S (S a) (S a) (S a)) (S a))`, i.e. a node with 2 children for a 3-symbol rule: an incomplete + continuation closed (same family as edit 12). On 5 tokens: 3 missing, 5 extra, 5 duplicates. +- `S -> A b | d; A -> S c` on `d c b`, `d c b c b`: CannotPlant at token 1 (indirect left recursion). +- layer 3 (epsilon), `layer4_hidden_left_recursion`, layer 5 (cyclic): not started. +- `test_from_grammar` fails on the PRISTINE tree too (not caused by the prototype). + +### The prototype = edits to the user's tree (dependency order; all scratch only) +Old items 1-8 (details in the archive, "The prototype = these edits"): FIX-A in +`item/reduction.rs` leaf branch; deterministic hasher `graph::det` (random hash order flipped +results); dummy root removal in `derive`; `plant_at_start` threshold 0; `open_ancestors` child +order; `create_new_label` top-level fix; `splone_left`; climb hook in `genins.rs insert_item` +(+ all virtual fragments); leading-chains tables in `atom/default.rs` (design in +`DESIGN-leading-chains.md`). Added in session rep-3: +1. `graph/src/labelled/binary.rs` `PLChildren::remove`: also `self.indices.remove(&key)`. + BUG IN THE USER'S TREE (HEAD too): `has_edge` stayed true after `remove_edge`, later + `add_edge` to the same child was skipped. `remove_edge` has one caller in the user's tree, + `chain/src/item/default/mod.rs:1213`. +2. `genins.rs` hook condition: drop `clone_index().is_none()` (clones are normal when ambiguous). +3. `splone.rs splone_left`: early return if the open node's first child is already the wrapper + `Rule(w)[start,pos]` (several `insert_item` calls visit one reduction per position). +4. `splone.rs open_ancestors`, `Eon::Ex` branch: if the existing node already has a child at + `parent_edge`, push `(Parent(ex, parent_edge), new_top)` instead of `add_edge`. +5. `genins.rs` hook: "already hooked" reuse: closed node under wrapper `w` of an open non-packed + `h` node with the same start -> push that open node on `second_stack`, `continue`. +6. `genins.rs` cascade: after `splone_left`, open `h` ancestors whose LAST child is the rule + wrapper (rule == fragment root rule, closed at `pos`) over `closed` complete at `pos` too: + push them on `stack` (not `second_stack`). +7. `splone.rs splone_left` dedupe: two alternatives of one span give the same continuation; + closed-node branch reuses the existing open sibling before reopening, open-node branch + buries the duplicate clone. New helper `bury` (drop edges, unique dummy label), because a + detached clone with a registered label broke `has_same_children`/`clone_node` asserts + (also two `assert_eq!(parentsa.len(), 1)` made tolerant of zero parents). +8. `genins.rs close_pavi(Virtual)`: do not replant the virtual alternative into a node already + turned into a continuation (first child is a closed left-wrapper rule node; + new `atom.is_left_wrapper_rule`). +9. `item/reduction.rs`: new `repair_stale_last_children(only)`; in `reduction` step 3 the nodes + returned by `splone` are collected and repaired right after the loop: a closed node whose + last child is still the open rule node although the closed twin exists gets its last edge + repointed (or is buried if a sibling alternative already equals the repaired one). The + `splone` `Eon::Ex` path never rewires; this is a patch around that. MEASURED: no stale + edge exists mid-parse, so the end-of-input call was dropped. +10. `genins.rs` hook, `has_h_parent`: only count a wrapper whose rule == `w` (a node hooked for + the OTHER left-recursive rule of the same head must not block this rule's hook). + Switch `NOFIX_HASHP`. Smallest failing input: `S -> S S | S a | a` on `a a`. +11. `DefaultForest` field `buried: HashMap` (buried node -> replacement), filled by + `bury(node, replacement)`; `resolve_buried` follows the map until a node that is not buried; + `insert_item` resolves `forest_source`/`true_source` through it at entry (`resolve_pavi`). + Reason: pending chain edges keep the old node number in their `PaVi`; without it the + debug assertion at `genins.rs` ~293 panicked (`a a a`). Alternative considered: rewrite + the chain edges when burying (needs patching `derive`'s pending items too; not done). +12. `splone.rs splone_left(.., atom)`: if the open node's first child is a closed wrapper of + ANOTHER left rule (`atom.is_left_wrapper_rule`), the node is already a continuation with + incomplete children and must not be closed again (it gave `S[1,2] -> [R7]`, i.e. `(S (S a))` + extras). Continue from its existing closed counterpart instead (`NOFIX_OTHERW`). +13. `genins.rs insert_item`, stack loop: a stack frame whose label is closed at a position `q < pos` is + DROPPED (`stale_frame = true`), but only when the item's own forest_source child is closed before `pos` + too (`DROP_ALL=1` drops every such frame; same results so far). An item left with an empty stack plants + nothing (no `CannotPlant`), and when its fragment root was not planted by another item the function + returns the item's own `pavi` instead of panicking on `query_label(root_label)`. Switch `NOFIX_STALE`. + Why (MEASURED, 5 tokens): the lineage whose forest_source is `Parent(25,0,26)` (frame `S[2,*]` under the + 2nd symbol of `S S`) keeps that pavi after the hook closed node 26 in place at pos 3 and moved the live + frame into the continuations (nodes 44/46/53). At pos 4 the item still climbs from the closed wrapper 25, + finds `S[0,3]`, `S[1,3]` (closed at 3 < 4) in its stack and `splone` re-ends them at 4 while keeping the + old last child `R8[2,3]`: nodes whose children end before the node does (89, 90, 92). The live + continuations are served by the lineage with forest_source = true_source = the freshly planted + `Parent(48,0,43)` (its stack was `[44,53,46]`, correct). The same test exists in + `chain/src/default.rs:758` for the `Non` branch (`Some(end) if end != pos => continue`), which is why + I believe the item is obsolete, not needed. Side effect: also fixes `S -> x S | S a | a` on `x x a a a`. + OPEN QUESTION for the user: the right cure may be to give the hooked frame a new forest_source + (remap `Parent(25,0,26)` to the continuation) instead of dropping; dropping loses the k=2..4 splits + from 7 tokens on (see FAIL above). +Debug-only (do not copy): `dbg_dump`, `SL`/`CASCADE`/`REPAIR`/`HOOKED_ALREADY`/`STALE_FRAME`/`OA create`/ +`CLONE_NODE` traces, probes, NOFIX switches, `DROP_ALL`. + +### Regression tests (tests/oracle.rs, module parser_side; all fail without their fix) +`regression_graph_remove_edge_clears_index` (GRAPH); `..._three_tokens_idempotent_hook` (IDEMP); +`..._four_tokens_clone_hook` (CLONE, HOOKED); `..._five_tokens_cascade` (CASCADE, DEDUPE, +REPAIR); `..._seven_tokens_virtual_and_ex` (VIRT, EX). New: `regression_two_left_rules_two_tokens_hook_per_rule` +(HASHP); `..._three_tokens` (HASHP, OTHERW; no longer isolates BURIED); `..._four_tokens_other_wrapper` +(HASHP, OTHERW); `..._five_tokens_stale_frame` (STALE, BURIED, HASHP, OTHERW; 5 and 6 tokens); +`regression_nested_left_recursion_stale_frame` (STALE; `x x a a a`). MEASURED with the switches. +No input separates fixes inside the older groups. + +### Still to do +1. `S -> S S | S a | a` on 7+ tokens (lost splits, see FAIL); decide drop vs remap for edit 13. +2. `S -> S S S | a` (incomplete continuation accepted on 4 tokens), `E -> E + E | n` with 5 operands, + indirect `d c b` (CannotPlant), then layer 3 (epsilon) and layer 5 (cyclic): the reference Cases 3-5 + of `forest-examples.md` are still untouched and matter more than the exotic grammars above. +3. Final deliverable: a consolidated, ordered change list for the user (file, function, + what, why; no diff unless asked) plus the regression tests. Mention that + `repair_stale_last_children` and edit 13 are patches around the `splone` `Eon::Ex` path and the stale + forest_source, and that the scratch-only debug code and `NOFIX_*` switches must not be copied. + +### Update (rep-3, after edit 13): stale-frame criterion and 7-token loss + +Scratch-only experiments (`claude scratch/ws`), all MEASURED unless marked. + +- New scratch field `hooked: HashMap>` (closed copy C -> open continuations O), filled at the end of `splone_left`. +- All 39 frames dropped by edit 13 on `S -> S S | S a | a`, 7 tokens, are recorded hook-closed copies (`hooked` has an entry). So `q < pos` coincides with "closed by the hook" here; not shown for other grammars. +- Only 18/39 have a continuation O in some item's stack at the same pos; 21 do not (some O were closed and re-hooked, so the live node is further along the chain; not separated). +- `REMAP=1` (replace a dropped frame by its live continuations, following the chain, pushed into the same item): WORSE than the drop. 5 tokens ok; 6 tokens 24 missing; 7: 128 missing (drop: 104); 8: 272 (drop: 200). Kept behind `REMAP`, off by default. +- 7-token loss, cause located: node 177 (`S[0,None] -> [R7[0,2], R8[2,6]]`, clone of 55 made by `reduction()` at `insert_item` entry) has no closed twin `S[0,6]`, so the splits k=2..4 of `S[0,6]` are missing. At pos 5 the analogous twin (node 122) is made by the cascade (`CASCADE closed=116 -> [118,119]`); at pos 6 the cascade skips it because the wrapper rule (8) differs from the item's fragment-root rule (5). +- `CASC_ACC=1` (cascade also for wrappers with `atom.is_accepting(rule*2+1)`): 7 tokens 104 -> 48 missing, but 6 tokens now 48 missing (`S[0,5]` loses splits k=2,3). At pos 4 it fires 5 nonempty cascades instead of 3, changing the `SL dedupe` / `bury` outcomes. Cause of the 6-token regression NOT identified (guess: `SL dedupe` buries an open clone whose pending content differs). +- Next: understand why extra cascades at pos 4 change pos-5 structure (compare `SL dedupe` decisions), before deciding on a cascade rule. + +### Update 2: 7 tokens of `S -> S S | S a | a` now pass (edits 14, 15; scratch) + +MEASURED. Both are on by default in scratch; off switches `NOFIX_REMAP`, `NOFIX_CASCACC`. Both are needed. + +- Root cause of the 7-token loss: an open node `S[0,None] -> [R7[0,j], R8[j,pos]]` with a complete last child never got its closed twin `S[0,pos]`. + - Cause (a): the cascade after `splone_left` only followed wrappers of the item's own fragment-root rule. + - Cause (b): when `CASC_ACC` was tried alone, the cascade-pushed node was processed with the item's rule (wrong hook wrapper `w`), and its open continuation was pushed into the item's `second_stack`, so the item planted its own fragment under a foreign-rule continuation (node `[R7[0,2], R5[2,3]]`, an extra/duplicate). +- Edit 14 (`genins.rs`, `insert_item`, cascade): also cascade over wrappers `Rule(r)` with `atom.is_accepting(r*2+1)`, remember `(node, r)` in the local `casc_rule`, use that rule instead of the fragment-root rule in the COND1 hook logic, and do not push the continuation of a foreign-rule cascade node into `second_stack`. Skip a node whose identical closed twin already exists (`NOFIX_CASCTWIN`; did not change results by itself). +- Edit 15 (`genins.rs`, stale-frame drop): instead of only dropping a stale frame, replace it by its live continuations: follow `DefaultForest::hooked` (closed copy -> open continuations, filled at the end of `splone_left`, `pub(crate)` field in `item/default/mod.rs`) until nodes that are open or end >= pos, and push `Parent(o, edge)`. +- Alone, neither works: remap without the cascade fix gives 24 missing at 6 tokens; the cascade fix without remap gives 104 missing at 7. +- New regression test `regression_two_left_rules_seven_tokens_cascade` (repo and scratch `tests/oracle.rs`). Fails with `NOFIX_REMAP` and with `NOFIX_CASCACC`. +- Suite in scratch: 30/39 pass (was 29/38 plus the new test), same failing set as before. +- Still failing: `S -> S S | S a | a` at 8 tokens (nodes `S -> ["S"]`, an incomplete continuation closed); `E -> E + E | n` at 5 operands is WORSE than before (4 missing + extras, was 1 missing); `S -> S S S | a` 4 tokens still accepted (extras), 5 tokens slightly better (1 missing, 3 extra, 1 dup, was 3/5/5); indirect `S -> A b | d; A -> S c`; layers 3, hidden left recursion, 5. + +### Update 3: 8+ tokens of `S -> S S | S a | a` pass (edit 16; scratch) + +MEASURED. `S -> S S | S a | a` now passes 3..10 tokens (heights 1..5). Suite in scratch: 30/39 (same failing set: layer 3 x3, hidden left recursion, layer 5 x4, layer6_random_grammars). + +- Symptom at 8 tokens: invariant violations `S[1..3,7] -> ["S"]` (nodes `S[k,7] -> [R7[k,7]]`, one child). +- Root cause: `reduction()` step 2 (`chain/src/item/reduction.rs`, the `if let Some(end) = top_label.label().end()` branch) marks every closed node ending at `pos` as Correct. A closed hook wrapper `Rule(w)` (first symbol of a left-recursive rule) is not a complete rule instance, so the open continuation `S[k,None] -> [R7[k,7]]` (one child) looked complete and step 3 closed it with that single child. RED3 trace (`DBG`): nodes 295, 316, 280 with `deg=1`. +- Edit 16: in that branch, a closed node whose rule satisfies `atom.is_left_wrapper_rule(r)` is Incorrect (switch `NOFIX_WRAPLAST`). +- Regression test `regression_two_left_rules_eight_tokens_wrapper_last_child` (repo + scratch `tests/oracle.rs`); fails with `NOFIX_WRAPLAST` (11/12 regression tests pass). +- Other probes (unchanged by edit 16): `E -> E + E | n` at 5 operands still worse than before edit 14 (4 missing + extras); `S -> S S S | a` 4/5 tokens still wrong. + +### Update 4: `E -> E + E | n` fixed (edits 17-20; scratch) + +MEASURED. `E -> E + E | n` passes 3..7 operands; `E -> E + E | E * E | n` (4 operands) and `E -> E + T | T; T -> T * n | n` (5 operands) pass; `S -> S S | S a | a` still passes 3..10 tokens. Suite in scratch: 32/44 pass; failing: layer 3 x3, hidden left recursion, layer 5 x4, and the open tests (indirect left recursion, `S -> S S S | a` 4 and 5 tokens). `layer6_random_grammars` is `#[ignore]`d. + +New known-open tests added to `tests/oracle.rs` (repo and scratch), named `open_*`: `open_three_symbol_rule_four_tokens`, `open_three_symbol_rule_five_tokens`, `open_indirect_left_recursion`. They fail on purpose until fixed. + +Causes (E at 5 operands; 3 missing + extras + invariants `E -> [E + E + E]`, children ending later than the node): +- Edit 17 (`genins.rs`, cascade): `left_wrapper` is keyed by the slot AFTER the wrapper (`R5` for `E -> E + E`), which coincides with the last slot only for two-symbol rules. A cascade node of another rule was hooked with the rule of its last slot (`R6`): `left_wrapper(0, E, 6) = None`, so it was never hooked. Now the hook slot is `first_child_rule + 1` when the first child is a left wrapper (`NOFIX_CASCWRAP`). +- Edit 18 (`genins.rs`, `insert_item` entry): `repair_stale_last_children(None)` sweep at every entry (`NOFIX_REPAIRALL`). The remapped continuation closed at pos 7 had an open last child; the correct closed twin appeared later, so the clone must be repointed (and dropped if it duplicates a sibling). +- Edit 19 (`reduction.rs`, `repair_stale_last_children`): also repair a last child that is closed but ends elsewhere than the node (was: open only) (`NOFIX_REPAIRANY`); and (`default.rs`) run the sweep at the end of input by default (was `EOI_REPAIR`, now `NOFIX_EOIREPAIR`). +- Edit 20 (`splone.rs`, `splone_left`, open-node branch): when the node is in progress (more than one child, last child open) the hook continuation is a separate open clone (made with edge 0, since edge `edge_index` resolves to the node itself) instead of repurposing the node, which lost `E[0,None] -> [R4[0,5], R5[5,6], R6[6,None]]` and with it the split `E[0,5] + E[6,9]` (`NOFIX_INPROG`). +- Interactions (MEASURED with the switches): `NOFIX_CASCWRAP` and `NOFIX_INPROG` fail the new E test; `NOFIX_REPAIRALL`, `NOFIX_REPAIRANY`, `NOFIX_EOIREPAIR` fail the 7- and 8-token S tests (edit 20 leaves more stale last children for the sweeps to fix). An earlier experiment, skipping remapped in-progress continuations (`REMAP_SKIP_INPROG`), fixed E but lost 48 trees at 8 tokens of S; kept off. +- Regression test: `regression_three_symbol_left_rule_five_operands` (repo and scratch `tests/oracle.rs`). 13/13 regression tests pass. +- Still wrong: `S -> S S S | a` at 4 tokens (extras, accepted though not derivable), 5 and 7 tokens; the indirect grammar; layers 3, hidden left recursion, 5. + +### Update 5: edit 17 without arithmetic + +The `first_child_rule + 1` of edit 17 was an unproven assumption. `atom/default.rs` fills `left_wrappers[(h, y, r)] = slot` with `r` ranging over the FIRST LITERALS reachable after the leading symbol (`first_literals`), not "the next slot", so `w+1` is not guaranteed. `r` is only used to look up `w`; a cascade node's own first child already is its wrapper. Now `casc_rule` entries carry `Some(w)` (the first child's rule, when `atom.is_left_wrapper_rule`), COND1 uses `known_w.or_else(|| left_wrapper(...))`, and the head comes from `get_rule_num(w)`. Suite unchanged (32/44, same failing set). Added `coverage_longer_left_recursive_rules` (4-symbol rule, shared leading symbol with different lengths, `S x S y S`); passes. Not covered: leading nonterminal that is not the head (indirect), regexp rules with alternatives after the leading symbol. + +### Update 6: `S -> S S S | a` (edits 21-23; scratch) + +MEASURED. Passes 3..6 and 8 tokens (4, 6, 8 are not derivable: the forest must be empty). 7 and 9 tokens: no invalid node left, 1 tree missing at h=3 (`(S (S a a a) (S a a a) a)`) and more at larger heights. Suite in scratch: 35/46 (failing: layer 3 x3, hidden left recursion, layer 5 x4, `open_indirect_left_recursion`, and the new `open_three_symbol_rule_seven_tokens`). + +- Harness fix (tests only): `check_case` returned the invariant "the forest is empty (no root)" even for inputs the oracle says are not derivable. Now no root is correct iff the oracle finds no tree at any height. +- Edit 21 (`genins.rs`, cascade after `splone_left`): every cascade node needs an ACCEPTING wrapper (`atom.is_accepting(rule*2+1)`), also in the same-rule case (edit 6 assumed the item's slot is the last slot of its rule, true only for two-symbol rules). Closed `S[0,2] -> [R4, R5]` of `S -> S S S`. Switch `NOFIX_CASCACCEPT`. Test `regression_three_symbol_rule_incomplete_cascade` (4, 5, 6 tokens). +- Edit 22 (`genins.rs` + `atom/default.rs`): new `DefaultAtom::follows` / `can_follow(prev, next)`: slot `next` may directly follow slot `prev` (through the target of each literal edge, `first_literals`). In the `HFILTER` loop a frame `(node, edge)` is kept only if `can_follow(rule of child at edge, fragment root rule)`. Fixes planting `R6` after `R4` (frame `edge=0` on `[R4, R5]`). Switch `NOFIX_FOLLOW`. No passing test needs it; at 7 and 9 tokens it removes 10 / 17 invalid nodes. +- Edit 23 (`genins.rs`, stack loop): a frame whose node is the reduced nonterminal completes it only if the child at `edge` has an accepting slot; hook wrapper slots (`is_left_wrapper_rule`) are exempt (they are legitimately non-accepting and are pushed with edge 0). Closed `S -> [R4, R5]` made by the hook with `edge=1`. Switch `NOFIX_ACCFRAME`. Test `regression_three_symbol_rule_eight_tokens_frame_filters`. Without the exemption the 7- and 8-token tests of `S -> S S | S a | a` fail. +- Open: 7 tokens. The open node `S[0,None] -> [R4[0,3], R5[3,6]]` (node 95, made during the pos-6 items) is in no item's stack, so the last symbol is never planted under it. Test `open_three_symbol_rule_seven_tokens`. + +### Update 7: what a stack frame is (investigation; no behaviour change kept) + +- `accepting_vec` (`atom/default.rs` ~499-555) is a fixpoint: a state is accepting if it ends a rule OR a nullable edge leads to an accepting state. So a wrapper followed only by nullable symbols IS accepting (read from code, not measured; the `2*slot+1` indexing is the original author's convention). Edit 23's wrapper exemption is only about non-nullable remainders. +- Convention (MEASURED, `DBGF`): a frame `(node, edge)` means "the child at `edge` is the one before the planting point" (`splant` keeps `edge+1` children). The planting filter (`HFILTER`) runs AFTER the reduction loop, so an invalid frame is hooked/closed before it is ever checked (cause of closed `S -> [R4, R5]`). +- Scratch diagnostics (off by default): `origin` side table in `insert_item` (init / remap / hooked_already / hook_open / casc / climb), `DBG_ORIGIN=1` prints `FRM origin lvl r childrule nt_match follow_would_drop`; `FOLLOW_ENTRY=1` applies `can_follow(child rule at edge, fragment root slot)` at the entry of reduction level 0. +- Result: `FOLLOW_ENTRY` breaks `regression_two_left_rules_{seven,eight}_tokens_*` (S S | S a | a): `S[0,6]` loses the splits k=2,3 (`[R7[0,j], R8[j,6]]`). Init frames whose child at `edge` is the OTHER production's wrapper (e.g. child slot 7, item slot 5) are needed: the item completes an inner `S` (via `S a`) which is then planted as the second child of the `S S` continuation. So there are at least two roles: (P) plant the item's fragment root under the node (needs `can_follow(child slot, r)`), (C) receive the CLOSED reduced nonterminal as the next child (needs a following slot whose symbol is `Non(reduction_nt)`; independent of `r`). Edit 23 (accepting child at `edge`) and edit 22 (`can_follow`) mix the two, hence the wrapper exemption. +- `can_follow` is too permissive at rule ends: `(8, 5)` is reported as allowed (`first_literals` crosses epsilon edges at the end of a rule into other rules' starts); fine for the filters that use it only in role P but should be restricted. +- Next: tag frames with role (P or C) at creation (from the relation above), apply the P check only to P frames and a C check ("next slot after child at `edge` has symbol `Non(nt)`") to C frames, and see whether edit 23 and the wrapper exemption can go. Open question for the user: read the paper's definition of the stack (ask first). + +### Update 8 (roles of the stack, MEASURED) +- At reduction level 0 every surviving input frame has nt_match=true (8-token S S S test: 34 frames, 7 of them would be dropped by `can_follow`, and are needed). + So the two roles are two phases: input frames (C, they close their node) and the output stack after the levels (P, where the fragment root is planted). + `can_follow` (edit 22) belongs only to P, where it already runs (HFILTER). +- Full suite with and without `NOFIX_FOLLOW`: identical (35 passed, 10 failed). `can_follow`, strict or coarse, does not decide any remaining failure. +- Next: the open 7-token `S -> S S S | a` case (open node 95 in no item's stack). + +### Update 9 (7-token `S -> S S S | a`, traced) +- MEASURED: the hook (`splone_left` of node 81, closed copy 91 = S[3,6]) clones three containers: 94 = S[1,None]->[R4,R5,R6[3,6]] (gets a cascade frame, last slot accepting), 95 = S[0,None]->[R4[0,3],R5[3,6]] and 96 = S[2,None]->[R4[2,3],R5[3,6]] (need one more sibling, get NO frame). +- INFERRED: the hook branch `continue`s before the climb into `second_stack` that the non-hook branch does, so open containers with a non-last slot never become planting frames. +- Experiment (opt-in `HOOKCLIMB=1`, off): push `(gp, idx)` for open NT parents of each parent of `closed` ending at pos. Result: breaks 4+ passing tests (extra and missing trees), 7-token tree still missing, also when restricted to the last level. Not a fix; frames of the wanted kind (`edge=1, crules=[4,5]`) do appear, so more is wrong (maybe which clones exist, or the cascade twin check). + +### Update 10 (7-token `S -> S S S | a` FIXED) +- MEASURED: the `r=6` item's start stack contained the closed cascade node 91 (`S[3,6]`, edge 2 = its last child). The planting filter (HFILTER) dropped it (a closed node takes no child) and nothing replaced it, so containers 94/95/96 (open, waiting for a third child) got no frame. +- Fix (`genins.rs`, just before the HFILTER loop, switch `NOFIX_CLOSEDCLIMB`): a frame whose node is closed at `pos`, not packed, with `edge` = last child, is replaced by `(gp, edge)` for every open non-packed NT grandparent through its wrapper parents. The normal head and `can_follow` filters then apply (e.g. `(81,0)` after R4 is dropped for `r=6`, `(95,1)` after R5 is kept). +- Needed: `NOFIX_CLOSEDCLIMB=1` fails the test `regression_three_symbol_rule_seven_tokens_closed_frame_climb` (formerly `open_three_symbol_rule_seven_tokens`). Suite: 36 passed, 9 failed, 1 ignored. +- Earlier `HOOKCLIMB` experiment (frames added at the hook, off by default) is superseded: it put the frames at the `r=5` item where they are invalid. +- `S S S|a`: 7 passes; 9 and 11 tokens still lose trees (3 at h=4 for 9); 10 is non-derivable (correct, empty). + +### PLAN for next session (agreed with the user; Update 10's fix is NOT yet considered sound) +The closed-frame climb (`NOFIX_CLOSEDCLIMB`, genins.rs before the HFILTER loop) works on the tests but has unjustified choices: +1. Packed nodes: treat a packed node as the base (the "closed node"), its parent as the wrapper, and that parent's parent as `gp`, instead of rejecting them (a packed parent currently makes `gp` a rule node and the case is dropped). +2. Last-ness (`edge + 1 == degree`): the user thinks it is wrong, middle nodes can grow new follow-ups. Measure on other grammars whether last-ness always holds, or derive it from the definitions; otherwise remove it (mind that `splant` keeps only `edge+1` children). +3. One level only: the user thinks it is wrong too. Measure or infer the stopping condition of the climb (what makes a container final: open + non-packed? closed copies served by other items? cascade completion?). +Also check what else the fix drops: closed `gp`, containers whose wrapper is not last. Add a regression test for each case found, and keep NOFIX switches until justified. + +### Update 11 (plan steps 1-3 done; MEASURED) +- Closed-frame climb now uses packed nodes as bases too (`NOFIX_CCPACKED` disables): 8 occurrences in the suite; S S S at 11 tokens: missing 21->19 (h=4), 74->62 (h=5). Suite unchanged: 36 passed, 9 failed. +- Last-ness of the closed frame (`edge+1==degree`): never violated (0 events in suite, 9 and 11 token S S S). `CC_NOLAST=1` disables it, no change. Containers whose wrapper is not their last child: 10 events, already handled (the code never required last-ness for `gp`). +- Stopping condition: closed `gp` skipped 5 times, all with end == pos. Recursive climb from them (`CC_REC=1`, off) changes nothing. +- 9 tokens `S S S`, the missing tree: open `170 = S[0,None] -> [R4[0,3], R5[3,8]]` (wrapper 168 over packed 195, alternatives incl. closed 199) never gets its third child. The closed frame `(199,2)` is in the stack of the `r=5` item only (pavi child 116 = S[7,8]) and is consumed there by the hook (SPLONE_LEFT 199, open=158), so the climb never sees it. The `r=6` items have frames from another source (R5 node 148). OPEN: how should the `r=6` item receive containers found when the `r=5` item consumed a closed frame? (design question for the user) +- Diagnostics added (no behaviour change): `DBG_ANC=1`, `ANC_TARGETS=a,b,c` (path from the pavi child to targets), `DBG_CC=1`. + +### Update 12 (9/11/13-token `S -> S S S | a` FIXED) +- MEASURED cause: two items at pos 8 share the pavi child 116 (S[7,8]) but start from different rule nodes (r=5 item: R6[7,8] 115; r=6 item: R5[7,8] 148). In the 7-token case the r=6 item's pavi child was still OPEN, so the init `reduction` produced a closed copy and the item took `parents_of(reduced)`, i.e. the parents of ALL wrappers of the shared closed node (R5 and R6), reaching the closed S[3,6] frame. At 9 tokens the pavi child was already closed at `pos` (closed by an earlier item), `reduced == nth_child`, so only the parents of the planted R5 node were used and the wrapper R6[7,8] -> closed S[3,8] (199) -> packed 195 -> R5[3,8] 168 -> container 170 was never reached. +- Fix (`genins.rs`, the `reduced != nth_child` test after `reduction` in `insert_item`, switch `NOFIX_CLOSEDPARENTS`): treat a pavi child already closed at `pos` like a freshly reduced one (take all its parents). +- Needed: `NOFIX_CLOSEDPARENTS=1` fails the new test `regression_three_symbol_rule_nine_and_eleven_tokens_closed_pavi_child`. Suite: 37 passed, 9 failed, 1 ignored. S S S passes for 3,5,7,9,12,13 tokens (even counts that are non-derivable give an empty forest). +- With this fix on: `NOFIX_CLOSEDCLIMB=1` fails the 7-token regression test, and `NOFIX_CCPACKED=1` fails the 9/11 test (the packed-base part is needed, 9 tokens: 3 missing at h=4 again). `CC_REC=1` (recursive climb) and `CC_NOLAST=1` still change nothing: still no evidence for them. +- Separate, pre-existing gap (same with and without this fix): `S -> S S | a` at 8, 9, 10, 12 tokens misses trees at h=5 (2, 2, 4, 12); 7 tokens is fine. + +### Update 13 (2026-10-15): change of approach — READ `tests/DESIGN-forest-from-spans.md` FIRST +- MEASURED: the current forest construction depends on the item processing order. Adding a constant field to `Edge`'s hash (scratch `HASH_START=1`) changes `labels_of` order and breaks 3 regression tests (37 -> 32 passed). +- MEASURED: with frame starts carried on edges, the recognizer's completion events give spans covering every nonterminal span of the oracle trees in 20/21 cases (scratch test `probe_spans`, `PROBE_START=1`), independent of hash order. The 21st is a recognition bug. +- New failing test (both copies): `open_recognition_nullable_rest_of_virtual_node` (`S -> A A; A -> a | eps` rejects `a`; virtual node `[S]^a` not accepting). This is why `layer3_case_3` fails. +- Decision proposed: record spans in the recognizer, build the forest after the input from spans + grammar (productive fixpoint, keyed nodes). Plan in the design doc, section 5. Prototype edits 13-24 become obsolete. +- Scratch-only probe code (default behaviour unchanged): `Edge.start` + `with_start` (no-op unless `PROBE_START`), manual `Hash for Edge` (start hashed only with `HASH_START`), `DefaultChain.{spans,marks,tail_links}`, `node_pos`, `probe_spans`, `probe_pos`; env `PROBE_OFF`, `PROBE_TR`, `PROBE_CASE`, `NO_TAIL`. Scratch suite: 38 passed (incl. the print-only `probe_spans`), 10 failed (the 10th is the new recognition test), 1 ignored. + +### Update 14 (2026-10-15): facts with nonterminals verified; recognizer bugs — see `tests/DESIGN-forest-from-spans.md` (rewritten) +- Edges carry `start` and `frame_nt`; facts `(X, i, j)` recorded (E1-E4 + closures). MEASURED: no missing fact on 27 hand cases and 597 random grammars; "derivable from facts == exactly derivable" on 398 random grammars (needs the virtual-node fix). +- Recognizer bugs (design doc section 6): 6.1 virtual-node acceptance ignores left-linear edges (needed; scratch `FIX_VACC`); 6.2 `extend` acceptance order-dependent (scratch `FIX_EXTEND`); 6.3 reduction lists lose nonterminals (scratch `FIX_REDSET`, union sets); 6.4 false acceptances (acceptance not relative to the frame nonterminal; harmless for the facts approach). +- New failing test (both copies): `open_recognition_unreachable_rule_accepts_too_much`. +- CORRECTION: an earlier round used `env $v` with several switches in zsh, which sets only the first; the claims "FIX_SECOND needed?", "FIX_EXTEND has no effect" and the first hash-order check were invalid. Redone with `env ${=v}`; the design doc has the corrected results. +- Scratch suite (probes skipped): 35 passed, 11 failed (9 old + 2 recognition tests), 1 ignored. diff --git a/tests/CLAUDE-PROGRESS.md b/tests/CLAUDE-PROGRESS.md new file mode 100644 index 0000000..9bd9c51 --- /dev/null +++ b/tests/CLAUDE-PROGRESS.md @@ -0,0 +1,32 @@ +# Progress (for a new Claude session) + +Reading order: `CLAUDE.md` -> this file -> `tests/DESIGN-forest-from-spans.md` (the plan). +Reference cases: `forest-examples.md`. Older notes, only if something points there: +`tests/CLAUDE-PROGRESS-ARCHIVE.md`. + +## Rules that matter +- The user writes ALL source by hand. Claude plans, explains, and writes files ONLY in `tests/` + and in the scratch workspace. No diffs unless asked. +- Do not weaken reference cases or tests. Minimal targeted changes. Every fixed bug gets a + regression test that failed before the fix. Label claims MEASURED / INFERRED / guess. +- Do not open the paper PDFs without asking; the forest construction is the user's own design. +- macOS: BSD sed, so edit files with python. Paths contain spaces: quote them. +- zsh: `env $v cmd` with `v="A=1 B=1"` sets only `A`; write switches literally. + +## Scratch workspace +`` = `/Users/durand/Desktop/Centre/A propos de programmes/Rust/rep`. +`/claude scratch/ws` (full copy), build dir `/claude scratch/target`. Run: +`cd "/claude scratch/ws" && CARGO_TARGET_DIR="/claude scratch/target" cargo test --test oracle -- --test-threads=1` +Prototypes and their switches: design doc section 9. + +## Current state +- **Design settled and verified in scratch** (design doc section 7). What remains is to follow + the plan in design doc section 5: Part A (recognizer fixes, section 3), then Part B (forest + from facts, section 4). No research is left. +- **The user's tree has none of the fixes yet.** They exist only in scratch, behind switches. +- **Tests** (design doc section 6): four open recognition tests fail today and pass with the + fixes; one guard test passes and must keep passing. +- **Suite today (scratch, default, probes skipped):** 36 passed, 13 failed (the 4 open + recognition tests and 9 old forest tests), 1 ignored. The 9 forest tests are expected to pass + after plan step 11: the top-down prototype gives exactly the oracle's trees on all of them. +- **Next:** the user implements the plan, Part A first. diff --git a/tests/DESIGN-forest-from-spans.md b/tests/DESIGN-forest-from-spans.md new file mode 100644 index 0000000..8ff81d4 --- /dev/null +++ b/tests/DESIGN-forest-from-spans.md @@ -0,0 +1,413 @@ +# Design: exact recognizer and forest from facts + +Written by Claude Code (Opus). This is the plan to follow; the source +changes are for the user to write by hand. Claims are marked MEASURED +(shown by a run in the scratch copy), READ (read from the code) or +INFERRED. + +## 1. Goal and approach + +The parser's forest must represent exactly the derivation trees of the +input. The approach: + +- **Part A, an exact recognizer.** Fix five recognizer bugs (section 3). + Recognition alone must be right and fast; it is also the base of Part + B. +- **Part B, the forest from facts.** While recognizing, record facts + `(X, i, j)` ("the nonterminal `X` derives `input[i..j]`"). After the + input, build the forest top-down from `(S, 0, n)` using only the facts, + the grammar and the input (section 4). The forest is then a function + of a set of facts: it does not depend on the order in which edges are + processed. Extra facts are harmless, because every forest node is + checked down to terminals and ε, so correctness reduces to "no fact is + missing", which the tests check against the oracle. + +The current incremental forest code (`insert_item` and everything under +it) is replaced, not repaired. MEASURED: its result depends on the hash +order of `Edge` (`labels_of` iterates a hash map, +`graph/src/labelled/double.rs:20`). + +Everything in this document is prototyped and verified in the scratch +copy (section 7). No step needs further research. + +## 2. How the recognizer works (READ, partly INFERRED) + +From `chain/src/default.rs` (`derive`, `generate_edges`, `extend`), +`chain/src/lib.rs` (`Collapsed`, `chain`) and +`chain/src/atom/default.rs` (`from_grammar`). + +- **Chain graph.** A graph-structured stack. An edge `(label, target)` + out of a node means: "inside a nonterminal invocation (a *frame*), the + atom NFA is in state `label`; when the frame completes, continue with + the edges of `target`". +- **Nodes never change.** `DLGraph::extend` + (`graph/src/labelled/double.rs:395`) builds a node whole from edges + whose targets are older nodes. Nothing adds edges to a node later. +- **NFA states.** NFA nodes `2·pos` and `2·pos+1` belong to rule + position `pos`; `get_rule_num(pos)` is the nonterminal owning it. + **These states are shared by all nonterminals** (MEASURED): for + `S -> X d; X -> Y c; Y -> a`, the state `Y -> a ·` has the edge + `c -> X -> Y c ·` in every frame. Virtual nodes `[nt]^t` come after + all positions. Within one frame the NFA runs through left-corner + chains, so every nonterminal completed inside a frame starts at the + frame's start. +- **Calls.** A nonterminal in a non-leading position starts a new frame + at the current position `p`. `derive` groups all callers of one + virtual node (`add_second_layer`); `Collapsed` then creates one + *second-layer* node `M` with their continuations, and the edge + `(v, M)`. +- **Pops.** A transition to an accepting state "pulls in" the target's + edges: the frame completes and the caller continues. Reaching the end + of a rule with nothing after it (an *empty node*) gives no real edge, + only an *imaginary* edge `Im(target)` that carries acceptance. +- **Tail calls.** If the caller has nothing left after the call, no node + is kept for it. So the target of an edge does not tell where its frame + started (for `S -> a S | a` every edge points to the root). + +## 3. Part A: recognizer bugs and fixes + +Each bug has a test in `tests/oracle.rs` (section 6). + +### 3.1 Add `Edge::frame_nt` + +The nonterminal of the edge's frame, part of `Eq` and `Hash`. Needed by +3.4 and 3.5. + +| Edge | `frame_nt` | +|---|---| +| Continuing edge made by `generate_edges` (`Edge::new(atom_child, …)`) | the `frame_nt` of the edge it comes from | +| Edge into a new frame: `Collapsed`, label = virtual node `[nt]^t` | `nt` | +| Edge into a new frame: the tail-call edge `Edge::new(virtual_node, …)` in `derive` | `non` | +| Pulled-in edge | its own | +| Initial edge from `unit` | the start symbol | + +### 3.2 `DefaultChain::extend` decides acceptance from the first label + +- **Bug:** the loop over the new node's labels (hash order) stops at the + first label: "not accepting" if none of its targets accepts, + "accepting" if the label accepts. The result depends on the order. +- **Fix:** the node accepts iff some accepting label has an accepting + target. +- Latent today; it shows once edges with the same label are not merged + (3.1). + +### 3.3 Moves into rules outside the frame + +- **Bug:** because states are shared, inside a frame of `T` the end of + `T` continues into `E -> E + · T` (`T` is a left corner of `E`). + - `S -> b | a; A -> A S A | eps` accepts `a b b b`. + - `E -> E + T | T; T -> T * n | n` on `n + n + … + n`: every `+` + leaves a phantom `E` inside a `T` frame; maximum node degree 21 at 41 + tokens, total edges quadratic (MEASURED). +- **Fix:** inside a frame of `X`, allow a transition `label -> a` only if + `a` is not a rule position, or the nonterminal owning `a` + (`get_rule_num(a/2)`) is in `LC*(X)`. + - `LC*(X)`: `X` itself, and for every rule `X -> Y1 … Ym` and every `k` + such that `Y1 … Y(k-1)` are nullable and `Yk` is a nonterminal, + everything in `LC*(Yk)`. Compute it once from the grammar (a boolean + matrix in the grammar or the atom). + - Apply it to the atom children in the main loop of `derive`, and in + the fact recording (4.3). Checking the target state is enough + (INFERRED): a composed edge climbs only through left corners of the + target's nonterminal, which are then in `LC*(X)` too. +- With the fix the expression grammar has maximum degree 2 and linear + edges (MEASURED). + +### 3.4 Acceptance is one flag per state + +- **Bugs:** + - `S -> X d; X -> Y c; Y -> a` accepts `a c`: `X -> Y c ·` accepts + because `X` ends there, and that flag also ends the frame of `S`. + - `S -> A A; A -> a | eps` rejects `a`: the virtual node `[S]^a` + ignores its left-linearly expanded children ("should not affect the + nullability" block in `chain/src/atom/default.rs`). Also + `S -> Y; Y -> A | B; A -> x; B -> x` on `x`, and + `S -> A; A -> B C; B -> x | eps; C -> y | eps` on `x`. +- **Fix:** acceptance relative to the frame's nonterminal. + - In `DefaultAtom::from_grammar`, before the closure, compute for every + nonterminal `x` the NFA nodes that reach the end of `x` (node + `accumulators[x] + 1`) through nullable edges: the same propagation + loop as `accepting_vec`, seeded with that one node. Store it as + `acc_by_nt[x][node]`. + - `is_accepting_in(x, node)`: `acc_by_nt[x][node]` for a node of a rule + position; `accepting_vec[node]` for other nodes (end of rules, + virtual nodes). + - `generate_edges` takes `frame_nt` and uses + `is_accepting_in(frame_nt, atom_child)` for the edge's `accepting` + flag and for pulling in the target's edges. + - The virtual node `[nt]^t` accepts iff some child, left-linear or not, + has `acc_by_nt[nt][child]`. + +### 3.5 Imaginary edges are ignored next to real edges + +- **Bug:** `Chain::chain` calls `update_epsilon` only when the new node + has no real edges, and `Collapsed` keeps only the real edges of a + second-layer group. So a completion exactly at the end of a rule + (`Im(target)`) is lost when other edges exist. Hidden today by the + global acceptance of 3.4: with 3.4 alone, `S -> B a; B -> a B | eps` + rejects `a a`. +- **Fix:** in `chain`, always call `update_epsilon` (it only ever sets + acceptance to true); in `Collapsed`, after creating `M`, call + `update_epsilon(M, …)` with the group's imaginary edges. Do 3.4 and + 3.5 in the same change. + +### 3.6 Reduction lists lose nonterminals (needed by Part B) + +- **Bug:** `transform_label_null_epsilon` (`grammar/src/lib.rs`) keeps + one list per pair of states: the longest, and on composition only the + second edge's list plus the end crossed in the middle. + `S -> Y c; Y -> A | B; A -> x; B -> x` on `x c` loses `B[0,1]`. +- **Fix:** keep, per pair of NFA states, the *union* of all nonterminals + ended on any path (a reduction set): during the closure, union the + sets of both composed edges and the end crossed in the middle; when the + atom builds a virtual node, copy the union onto the virtual node's + edges. Keep the lists while the old forest code still uses them. + +## 4. Part B: the forest + +### 4.1 Start sets (only when a forest is requested) + +Edges do not carry their start. A side table maps each chain edge +`(node, label, target, frame_nt)` to the set of starts of its frame, +filled when the node is created, from edges of older nodes: + +| New edge | Its start set | +|---|---| +| continuing edge `(a, target)` from the edge `e` | `starts(e)` | +| pulled-in edge copied from node `c` | the set of that edge in `c` | +| edge into a new frame (`(v, M)`, tail-call edge `(v, target)`) | `{p}` | +| edges of a second-layer node `M` | by the same rules | +| initial edge from `unit` | `{0}` | + +Edges that merge in `extend` take the union of their sets. + +**Why this is exact (READ, MEASURED).** A node is built whole from +older nodes and never changes, and all callers of one call are grouped +before `M` is created. So no start can reach an edge after the edge's +successors exist. Keep the check "every real edge has a non-empty set" +as a debug assertion. If nodes are ever shared across positions +(memoization), this argument must be redone. + +### 4.2 Facts recorded while reading token `t` at position `p` + +For every edge `e = (label, children)` of the current node, and every +transition `label -> a` on `t` or on a call `Non(non)` with `t` in +FIRST(non), after the left-corner filter (3.3): + +- **E1, inner completions.** For every `X` in the reduction set of + `(label, a)` (3.6) and every `s` in `starts(e)`: `(X, s, p)`. +- **E2, frame completion after a terminal.** If `t` is read and + `is_accepting_in(e.frame_nt, a)`: + - for every `s` in `starts(e)`: `(e.frame_nt, s, p+1)`, and the *head + event* `(H, s, p+1)` with `H = get_rule_num(a / 2)`; + - walk down the stack: for every child node of `e`, every edge `l` of + it with `is_accepting_in(l.frame_nt, l.label)` completes too; record + the same for `l` with its start set, and continue from `l`'s targets. +- **E3, calls.** + - Every call: the single-token event `(t, p)`, standing for + `(X, p, p+1)` for every `X` that derives exactly `t` (precompute per + terminal from the grammar). + - If the virtual node `v` accepts: `(non, p, p+1)`. + - If `a` also accepts for the caller's frame: as E2 with `e`. +- **E4, tail calls.** If `a` is an empty node: for every `s` in + `starts(e)`, the link `(p → s, e.frame_nt, H = get_rule_num(a/2))`. + +Facts with `i == j` are not recorded: nullability comes from the +grammar. Facts are not closed during the parse (4.3). + +### 4.3 Building the forest top-down + +- **`closed(j)`**: the facts ending at `j` (E1-E3, single-token events + expanded), closed + - *upward*: a head event `(H, i, j)` also gives `(Y, i, j)` for every + `Y` reachable from `H` through rules `Y -> α H β` with `α`, `β` + nullable; + - *through tail links*: if a fact in `closed(j)` has start `p` and a + link starts at `p`, add `(caller_nt, caller_start, j)` and the upward + closure of `H` at `(caller_start, j)`; repeat. + + Compute `closed(j)` once per `j`, on the first demand. Closing all + facts eagerly would be quadratic on right recursion (`S -> a S | eps`: + 3240 facts at 80 tokens, against 80 needed; MEASURED). +- **Allowed keys.** `(Y, k, l)` is allowed if `k < l` and `(Y, k)` is in + `closed(l)`, or `k == l` and `Y` is nullable. +- **Alternatives of `(X, i, j)`.** For each production `X -> Y1 … Ym`, + find split points from right to left: `Ym` ends at `j` (a terminal + equal to `input[j-1]`, or an allowed key `(Ym, k, j)`), then `Y(m-1)` + ends at `k`, and so on; `Y1` must start at `i`. An ε production is the + alternative with `m = 0` and `i == j`. Right to left makes every query + "facts ending at `k`", the unit of the lazy closure. +- **Visit** from `(S, 0, n)`, computing the alternatives of each key + reached. This gives a finite graph of keys and alternatives. +- **Productive keys**: least fixpoint on that graph (a key is productive + if one of its alternatives has only productive key children). Cycles + over equal spans (Case 5) are kept; keys with no finite derivation are + dropped. +- **The forest**: the productive keys reachable from `(S, 0, n)` through + productive alternatives. If `(S, 0, n)` is not productive there is no + root. After Part A this agrees with `chain.epsilon()`; keep a debug + assertion. + +### 4.4 Output format + +The format `unpack` in `tests/oracle.rs` reads: + +- one nonterminal node per key, `start = i`, `end = Some(j)`; +- one alternative: a plain node whose children are, in order, one + `Rule(slot)` wrapper per symbol of the production, each wrapper with + exactly one child; +- several alternatives: a packed node with one cloned node per + alternative; +- an ε alternative: a nonterminal node with no children; +- terminal leaves shared per position, wrappers per `(slot, start, end)`; +- `slot` is the atom's position number (`print_rule_positions`); +- check with `validate_forest`. + +### 4.5 Why this is exact (INFERRED from the construction) + +- **No extra trees:** every node is checked down to terminals and ε. +- **No missing trees:** if the facts cover the oracle, every node of + every tree is a productive key with that alternative, reached from the + root. +- **No duplicates:** alternatives are unique per (production, splits), + nodes per key. + +### 4.6 Cost + +- **Recognition alone:** no side table, no facts. The fixes of Part A + make the chain smaller where states leaked between frames. +- **Recording:** O(edges + start-set entries + facts E1-E3). +- **Forest:** about the facts in the visited `closed(j)` plus the + alternatives built. +- **Measured sizes** (scratch, all fixes): + + | Grammar | tokens | chain edges | max degree | start-set entries | facts needed | keys visited | + |---|---|---|---|---|---|---| + | `S -> a S \| eps` | 80 | 81 | 1 | 80 | 80 | 81 | + | `S -> S a \| a` | 80 | 81 | 1 | 80 | 79 | 80 | + | `S -> a S b \| eps` | 80 | 119 | 1 | 119 | 78 | 41 | + | `E -> E + T \| T; T -> T * n \| n` | 79 | 158 | 2 | 155 | 119 | 80 | + | `S -> S S \| a` | 80 | 6401 | 80 | 6242 | 3240 | 3240 | + + Linear for the first four (also at 20 and 40 tokens); quadratic for + `S -> S S | a`, whose forest has n²/2 keys anyway. +- **Flat output:** a node may have O(n^(m-1)) alternatives for a + production of length m. Binarised nodes `(slot, i, k)` would give + O(n³) but need `unpack` changes; later. + +## 5. Plan + +Each step has a test that fails before it and passes after it. + +### Part A: exact recognizer + +1. **Recognition gate**: port the scratch recognition check into + `tests/oracle.rs`. On the hand cases and the random grammars, "the + recognizer accepts" must equal exact derivability (no height bound). + It fails today. +2. **`extend` acceptance** (3.2). +3. **`Edge::frame_nt`** (3.1). +4. **Left-corner filter** (3.3). +5. **Frame-relative acceptance and imaginary edges** (3.4 and 3.5, one + change). +6. **Gate passes** with zero mismatches; all recognition tests pass. + Time the recognizer on long inputs before and after Part A (only + chain size has been measured so far). + +### Part B: forest + +7. **Reduction sets** (3.6). +8. **Start-set side table** (4.1), only when a forest is requested. +9. **Record facts E1-E4** (4.2). +10. **Facts gate**: port `probe_facts` from scratch into + `tests/oracle.rs` as real tests on the hand cases and random + grammars. A test-only eager closure of the recorded facts must + satisfy "no missing fact" and "derivable from facts == exactly + derivable". This checks the recording alone. +11. **Top-down forest in `end_of_input`** (4.3, 4.4), with the chain run + with `no_item = true`. Compare the forest with the oracle on the + same cases. Delete `insert_item` and the old forest code once the + suite passes. +12. **Full suite**, including layers 3 to 6 and every regression test + (they compare derivation sets, so they stay valid). +13. **Later:** binarised nodes, memoization (redo 4.1's argument), + incremental reparsing from the saved chain node at an edit point + (facts and start sets before it stay valid). + +## 6. Tests + +In `tests/oracle.rs` (and the scratch copy): + +| Test | Today | After | +|---|---|---| +| `open_recognition_nullable_rest_of_virtual_node` | fails | passes after step 5 | +| `open_recognition_inner_rule_end_is_not_frame_end` | fails | passes after step 5 | +| `open_recognition_unreachable_rule_accepts_too_much` | fails | passes after step 5 | +| `open_recognition_expression_grammar_node_degree_stays_bounded` | fails (degree 21) | passes after step 4 | +| `guard_recognition_rule_end_completion_next_to_other_edges` | passes | must keep passing; fails if 3.4 is done without 3.5 | + +**The 9 forest tests that fail today** (`layer3_case_3`, +`layer3_case_4`, `layer3_nullable_in_the_middle`, +`layer4_hidden_left_recursion`, `layer5_case_5a`, `layer5_case_5c`, +`layer5_case_5d`, `layer5_highly_ambiguous_with_epsilon`, +`open_indirect_left_recursion`) fail in the old forest code. Part A +does not change them (MEASURED). The top-down prototype gives exactly +the oracle's trees on every grammar and input of those tests (MEASURED, +height 5), so they are expected to pass after step 11. If one does not, +the step 10 tests tell whether the recording or the construction is +wrong. + +## 7. Evidence (MEASURED in scratch, recognizer run with `no_item = true`) + +With all fixes, start sets in a side table and `frame_nt` on edges: + +- **27 hand cases** (right, left, hidden, indirect and nested left + recursion; `S S`, `S S S`, `S S | S a`, `E + E`, `E + T / T * n`; + nullable rules; the cyclic grammars of Case 5; unit chains through two + nonterminals; 8-11-token ambiguous inputs) and **1194 random grammars** + (the layer-6 generator, six seeds, height 4): + - recognition equals exact derivability (no false acceptance or + rejection); + - no fact missing; "derivable from facts" equals exact derivability; + - every real edge has a non-empty start set; + - the top-down construction's trees equal the oracle's. +- With the fixes on, the old forest code's suite results do not change. +- Tree sets were compared at oracle height 4 to 6; recognition and + derivability exactly. + +## 8. Open points + +- That a pulled-in edge keeps the start set and frame nonterminal of its + own frame is INFERRED from the code and supported by the measurements, + not proven; the step 10 tests guard it. +- The empty input is not supported by the test harness yet; `(S, 0, 0)` + must be allowed when `S` is nullable. + +## 9. Scratch reference + +The scratch copy `/claude scratch/ws` (build dir +`/claude scratch/target`) holds the prototypes. It is not the +user's tree: it also contains obsolete forest edits and `NOFIX_*` +switches, which must not be ported. The prototypes are probes that +mirror `derive` in a separate pass; the real code should record inside +the actual edge generation. + +| What | Where (scratch) | Switch | +|---|---|---| +| `Edge::frame_nt` | `chain/src/lib.rs` | `PROBE_START=1 NO_START=1` | +| 3.2 `extend` | `chain/src/default.rs` | `FIX_EXTEND=1` | +| 3.3 left-corner filter (`lc_ok`) | `chain/src/default.rs`; table from the test via `LC_TABLE` | `FIX_LC=1` | +| 3.4 `acc_by_nt`, `is_accepting_in` | `chain/src/atom/default.rs` | `FIX_FACC=1` | +| 3.5 imaginary edges | `chain/src/lib.rs` (`Collapsed`, `chain`) | `FIX_IMAG=1` | +| 3.6 reduction sets | `grammar/src/lib.rs` (`reduction_sets`) | `FIX_REDSET=1` | +| 4.1 start sets (`resolve_origins`, `orig`) and 4.2 facts | `chain/src/default.rs` | `ORIGINS=1` | +| 4.3 top-down prototype | `tests/oracle.rs`, test `probe_facts` | `PF_TOPDOWN=1` | + +Full configuration: +`env PROBE_START=1 NO_START=1 ORIGINS=1 FIX_REDSET=1 FIX_EXTEND=1 FIX_LC=1 FIX_FACC=1 FIX_IMAG=1 PF_TOPDOWN=1` +(write the switches literally; zsh does not split `env $v`). +`probe_facts` options: `PF_GRAMMAR`/`PF_INPUT` (one case), +`PF_RANDOM=n` with `REP_SEED`, `PF_NOORACLE=1` (sizes only). +`probe_atom` prints the atom NFA of `PF_GRAMMAR`. Recognition tests run +with `FIX_LC` need `LC_TABLE` by hand (`"0,1;1"` for the expression +grammar). diff --git a/tests/DESIGN-leading-chains.md b/tests/DESIGN-leading-chains.md new file mode 100644 index 0000000..72421ad --- /dev/null +++ b/tests/DESIGN-leading-chains.md @@ -0,0 +1,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 { symbol: TNT, slot: usize, target: usize /* NFA state after it */ } +``` + +From `lead` compute two tables, once, at construction: + +### 3.1 `chains[(N, t)] : Vec` (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): + 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` 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. diff --git a/tests/oracle.rs b/tests/oracle.rs new file mode 100644 index 0000000..cab790f --- /dev/null +++ b/tests/oracle.rs @@ -0,0 +1,1803 @@ +//! Brute-force derivation-tree oracle. +//! +//! WRITTEN BY CLAUDE CODE (an AI assistant), at the user's request, as +//! step 1 of the debugging workflow in `CLAUDE.md`. It is deliberately +//! naive and independent of the parser: it knows nothing about the +//! `chain`, `forest` or `grammar` crates. +//! +//! Input: a context-free grammar, a token sequence and a height bound +//! `h`. Output: the set of ALL derivation trees of the whole token +//! sequence whose height is at most `h`, as canonical S-expression +//! strings in the notation of `forest-examples.md`: +//! +//! - a nonterminal node is `(Symbol child child ...)`; +//! - a terminal is the bare token; +//! - an empty production is `eps`, so `A -> eps` gives `(A eps)`. +//! +//! The height of a tree is the maximum number of nonterminal nodes on +//! any root-to-leaf path. Cyclic derivations (such as `S -> S`) are not +//! pruned: the height bound is what makes the search terminate. +//! +//! Method: top-down. For a nonterminal over a span, try every +//! production, and for every production try every way of cutting the +//! span into consecutive pieces for its symbols. Nothing is memoized. +//! +//! Every case of `forest-examples.md` is checked against this oracle +//! at the bottom of this file, before the oracle is trusted. + +use std::collections::BTreeSet; + +/// A grammar: rules per nonterminal; the first rule's left-hand side +/// is the start symbol. An empty alternative is an epsilon production. +#[derive(Debug, Clone)] +pub struct Grammar { + start: String, + rules: Vec<(String, Vec>)>, +} + +impl Grammar { + /// Parse a grammar from lines such as `S -> S S | a`. Symbols are + /// separated by whitespace. A symbol is a nonterminal iff it is the + /// left-hand side of some line. An alternative that is empty or is + /// the single word `eps` is an epsilon production. Several lines + /// with the same left-hand side are merged. + pub fn parse(text: &str) -> Grammar { + let mut rules: Vec<(String, Vec>)> = Vec::new(); + + for line in text.lines().map(str::trim).filter(|l| !l.is_empty()) { + let (lhs, rhs) = line + .split_once("->") + .unwrap_or_else(|| panic!("bad grammar line: {line}")); + let lhs = lhs.trim().to_string(); + + let alternatives: Vec> = rhs + .split('|') + .map(|alt| { + let symbols: Vec = + alt.split_whitespace().map(str::to_string).collect(); + + if symbols == ["eps"] { + Vec::new() + } else { + symbols + } + }) + .collect(); + + match rules.iter_mut().find(|(name, _)| *name == lhs) { + Some((_, existing)) => existing.extend(alternatives), + None => rules.push((lhs, alternatives)), + } + } + + let start = rules.first().expect("empty grammar").0.clone(); + + Grammar { start, rules } + } + + fn is_nonterminal(&self, symbol: &str) -> bool { + self.rules.iter().any(|(name, _)| name == symbol) + } + + fn alternatives(&self, nonterminal: &str) -> &[Vec] { + self.rules + .iter() + .find(|(name, _)| name == nonterminal) + .map(|(_, alts)| alts.as_slice()) + .unwrap_or(&[]) + } +} + +/// Split a whitespace-separated token string. `""` is the empty input. +pub fn tokens(text: &str) -> Vec { + text.split_whitespace().map(str::to_string).collect() +} + +/// All derivation trees of `tokens` from the start symbol of `grammar` +/// whose height is at most `h`. +pub fn oracle_trees(grammar: &Grammar, tokens: &[String], h: usize) -> BTreeSet { + nonterminal_trees(grammar, &grammar.start, tokens, 0, tokens.len(), h) +} + +/// Trees for `nonterminal` deriving `tokens[i..j]` with height <= `h`. +fn nonterminal_trees( + grammar: &Grammar, + nonterminal: &str, + tokens: &[String], + i: usize, + j: usize, + h: usize, +) -> BTreeSet { + let mut out = BTreeSet::new(); + + // A nonterminal node itself counts one towards the height. + if h == 0 { + return out; + } + + for alternative in grammar.alternatives(nonterminal) { + if alternative.is_empty() { + if i == j { + out.insert(format!("({nonterminal} eps)")); + } + + continue; + } + + for children in sequence_trees(grammar, alternative, tokens, i, j, h - 1) { + out.insert(format!("({nonterminal} {})", children.join(" "))); + } + } + + out +} + +/// Every way to derive `tokens[i..j]` from the sequence of `symbols`, +/// each child having height at most `child_h`. Each result is the +/// list of the children's trees, in order. +fn sequence_trees( + grammar: &Grammar, + symbols: &[String], + tokens: &[String], + i: usize, + j: usize, + child_h: usize, +) -> Vec> { + let Some((first, rest)) = symbols.split_first() else { + return if i == j { vec![Vec::new()] } else { Vec::new() }; + }; + + let mut out = Vec::new(); + + // Try every cut point for the first symbol. + for k in i..=j { + let first_trees: BTreeSet = if grammar.is_nonterminal(first) { + nonterminal_trees(grammar, first, tokens, i, k, child_h) + } else if k == i + 1 && tokens[i] == *first { + BTreeSet::from([first.clone()]) + } else { + BTreeSet::new() + }; + + if first_trees.is_empty() { + continue; + } + + let rest_trees = sequence_trees(grammar, rest, tokens, k, j, child_h); + + for first_tree in &first_trees { + for tail in &rest_trees { + let mut children = Vec::with_capacity(1 + tail.len()); + children.push(first_tree.clone()); + children.extend(tail.iter().cloned()); + out.push(children); + } + } + } + + out +} + +// --------------------------------------------------------------------- +// Validation of the oracle against `forest-examples.md`. +// --------------------------------------------------------------------- + +#[cfg(test)] +mod validate_oracle { + use super::*; + + fn set(items: &[&str]) -> BTreeSet { + items.iter().map(|s| s.to_string()).collect() + } + + fn trees(grammar: &str, input: &str, h: usize) -> BTreeSet { + oracle_trees(&Grammar::parse(grammar), &tokens(input), h) + } + + /// Case 1: `S -> S S | a` on `aaa`: exactly two trees. + #[test] + fn case_1_trees() { + assert_eq!( + trees("S -> S S | a", "a a a", 4), + set(&[ + "(S (S a) (S (S a) (S a)))", + "(S (S (S a) (S a)) (S a))" + ]) + ); + } + + /// Case 1: tree counts by input length are Catalan(n - 1). + #[test] + fn case_1_counts() { + for (n, expected) in [(1usize, 1usize), (2, 1), (3, 2), (4, 5), (5, 14)] { + let input = vec!["a"; n].join(" "); + + // Height n is enough for any binary tree with n leaves. + assert_eq!(trees("S -> S S | a", &input, n).len(), expected, "n = {n}"); + } + } + + /// Case 2: `E -> E + E | n` on `n + n + n`: exactly two trees. + #[test] + fn case_2() { + assert_eq!( + trees("E -> E + E | n", "n + n + n", 4), + set(&[ + "(E (E n) + (E (E n) + (E n)))", + "(E (E (E n) + (E n)) + (E n))" + ]) + ); + } + + /// Case 3: `S -> A A ; A -> a | eps`. + #[test] + fn case_3() { + let grammar = "S -> A A\nA -> a | eps"; + + assert_eq!( + trees(grammar, "a", 4), + set(&["(S (A a) (A eps))", "(S (A eps) (A a))"]) + ); + + // The empty input gives exactly ONE tree. + assert_eq!(trees(grammar, "", 4), set(&["(S (A eps) (A eps))"])); + } + + /// Case 4: `S -> a S | eps` on `a a`: exactly one tree. + #[test] + fn case_4() { + assert_eq!( + trees("S -> a S | eps", "a a", 6), + set(&["(S a (S a (S eps)))"]) + ); + } + + /// Case 5a: `S -> S | a` on `a`: exactly h trees for height h. + #[test] + fn case_5a() { + let g = "S -> S | a"; + + assert_eq!(trees(g, "a", 1), set(&["(S a)"])); + assert_eq!(trees(g, "a", 2), set(&["(S a)", "(S (S a))"])); + assert_eq!( + trees(g, "a", 3), + set(&["(S a)", "(S (S a))", "(S (S (S a)))"]) + ); + assert_eq!( + trees(g, "a", 4), + set(&["(S a)", "(S (S a))", "(S (S (S a)))", "(S (S (S (S a))))"]) + ); + } + + /// Case 5b: `A -> A | eps` on the empty input. + #[test] + fn case_5b() { + let g = "A -> A | eps"; + + assert_eq!(trees(g, "", 1), set(&["(A eps)"])); + assert_eq!(trees(g, "", 2), set(&["(A eps)", "(A (A eps))"])); + assert_eq!( + trees(g, "", 3), + set(&["(A eps)", "(A (A eps))", "(A (A (A eps)))"]) + ); + } + + /// Case 5c: `S -> A | a ; A -> S` on `a`; each trip adds 2 to the height. + #[test] + fn case_5c() { + let g = "S -> A | a\nA -> S"; + + assert_eq!(trees(g, "a", 1), set(&["(S a)"])); + assert_eq!(trees(g, "a", 2), set(&["(S a)"])); + assert_eq!(trees(g, "a", 3), set(&["(S a)", "(S (A (S a)))"])); + assert_eq!(trees(g, "a", 4), set(&["(S a)", "(S (A (S a)))"])); + assert_eq!( + trees(g, "a", 5), + set(&["(S a)", "(S (A (S a)))", "(S (A (S (A (S a)))))"]) + ); + } + + /// Case 5d: `S -> S S | S | a` on `a a`. `forest-examples.md` gives + /// no expected forest for this case. The counts below were derived + /// by hand by Claude Code, not taken from that file: + /// + /// - h = 1: none (`S -> S S` already needs height 2); + /// - h = 2: only `(S (S a) (S a))`; + /// - h = 3: the 4 trees `(S X Y)` with `X`, `Y` in `{(S a), (S (S a))}`, + /// and `(S (S (S a) (S a)))`: 5 trees. + #[test] + fn case_5d() { + let g = "S -> S S | S | a"; + + assert_eq!(trees(g, "a a", 1), set(&[])); + assert_eq!(trees(g, "a a", 2), set(&["(S (S a) (S a))"])); + + let h3 = trees(g, "a a", 3); + + assert_eq!(h3.len(), 5); + assert!(h3.contains("(S (S a) (S a))")); + assert!(h3.contains("(S (S (S a)) (S (S a)))")); + assert!(h3.contains("(S (S (S a) (S a)))")); + } + + /// Larger bounds only add trees. + #[test] + fn monotone_in_height() { + for (g, input) in [ + ("S -> S S | a", "a a a"), + ("S -> S | a", "a"), + ("S -> S S | S | a | eps", "a a"), + ] { + let mut previous = BTreeSet::new(); + + for h in 1..=4 { + let current = trees(g, input, h); + + assert!(previous.is_subset(¤t), "{g} on {input:?}, h = {h}"); + + previous = current; + } + } + } +} + +// --------------------------------------------------------------------- +// The parser side: build the parser, unpack its forest, compare it with +// the oracle, and check structural invariants. +// +// Also written by Claude Code. Everything below is TEST CODE ONLY; it +// reads the parser's forest through the public traits of `graph` and +// `forest` and never changes the parser. +// --------------------------------------------------------------------- + +#[cfg(test)] +mod parser_side { + use super::*; + + use chain::atom::DefaultAtom; + use chain::default::DefaultChain; + use chain::Chain; + use forest::Forest as ForestTrait; + use grammar::test_grammar_helper::scan_tnt; + use grammar::{GrammarLabelType, Nonterminal, Rule, Terminal, TNT}; + use graph::{Graph, LabelGraph}; + use nfa::default::regex::DefaultRegParser; + use nfa::DesRec; + use std::collections::{BTreeMap, HashMap}; + + type Forest = chain::item::default::DefaultForest>; + + // ------------------------------------------------------------ + // Running the parser. + // ------------------------------------------------------------ + + /// The parser prints debug dumps to `output/...` relative to the + /// current directory. Run from a temporary directory so that they + /// neither fail nor litter the source tree. + fn init() { + static INIT: std::sync::Once = std::sync::Once::new(); + + INIT.call_once(|| { + let dir = std::env::temp_dir().join("rep-tests"); + std::fs::create_dir_all(dir.join("output")).unwrap(); + std::env::set_current_dir(dir).unwrap(); + }); + } + + /// Names for the symbols of a grammar, in the order of the parser's + /// numbering: nonterminal 0 is the start symbol. + #[derive(Debug, Clone)] + struct Names { + nons: Vec, + ters: Vec, + } + + /// A grammar together with its terminal alphabet. The alphabet is + /// explicit so that terminal numbers are stable between the grammar + /// and the input, even if some terminal is not used by any rule. + #[derive(Debug, Clone)] + struct Setup { + grammar: Grammar, + names: Names, + } + + impl Setup { + fn new(grammar_text: &str, input: &[String]) -> Setup { + let grammar = Grammar::parse(grammar_text); + + let nons: Vec = grammar.rules.iter().map(|(n, _)| n.clone()).collect(); + + let mut ters: Vec = Vec::new(); + + for (_, alternatives) in &grammar.rules { + for symbol in alternatives.iter().flatten() { + if !grammar.is_nonterminal(symbol) && !ters.contains(symbol) { + ters.push(symbol.clone()); + } + } + } + + for token in input { + if !ters.contains(token) { + ters.push(token.clone()); + } + } + + Setup { + grammar, + names: Names { nons, ters }, + } + } + } + + /// Letters only: `scan_tnt` accepts nothing else in a name. + fn letters(mut i: usize) -> String { + let mut out = String::new(); + + loop { + out.insert(0, (b'a' + (i % 26) as u8) as char); + + if i < 26 { + break; + } + + i = i / 26 - 1; + } + + out + } + + fn parser_grammar(setup: &Setup) -> grammar::Grammar { + let names = &setup.names; + + // `scan_tnt` reads `T` / `N` and looks `` up + // among terminals / nonterminals respectively, so the two + // namespaces may reuse the same letters. + let ter_name = |i: usize| letters(i); + let non_name = |i: usize| letters(i); + + let mut parser: DefaultRegParser = Default::default(); + + for i in 0..names.ters.len() { + parser.add_tnt(&ter_name(i), true); + } + for i in 0..names.nons.len() { + parser.add_tnt(&non_name(i), false); + } + + let rules: Vec = names + .nons + .iter() + .map(|nt| { + let alternatives = setup.grammar.alternatives(nt); + + // Epsilon alternatives go last: `scan_tnt` handles a + // trailing empty alternative (as in `new_paren_grammar`). + let mut texts: Vec = alternatives + .iter() + .filter(|alt| !alt.is_empty()) + .map(|alt| { + alt.iter() + .map(|symbol| match names.nons.iter().position(|n| n == symbol) { + Some(i) => format!("N{}", non_name(i)), + None => { + let i = names.ters.iter().position(|t| t == symbol).unwrap(); + format!("T{}", ter_name(i)) + } + }) + .collect::>() + .join(" ") + }) + .collect(); + + if alternatives.iter().any(|alt| alt.is_empty()) { + texts.push(String::new()); + } + + let text = texts.join(" | "); + + Rule::new( + parser + .parse(&text, Box::new(scan_tnt), true) + .unwrap_or_else(|e| panic!("cannot parse rule {text:?}: {e:?}")) + .unwrap_or_else(|| panic!("rule {text:?} parsed to nothing")) + .0, + ) + }) + .collect(); + + grammar::Grammar::new( + (0..names.ters.len()) + .map(|i| Terminal::new(ter_name(i))) + .collect(), + (0..names.nons.len()) + .map(|i| Nonterminal::new(non_name(i))) + .collect(), + rules, + ) + } + + /// Run the parser on `input`, giving up after a timeout (default 20 + /// seconds, `REP_TIMEOUT` seconds to override). A parser that does + /// not terminate is reported as an error like any other failure, + /// instead of blocking the whole test run. The abandoned thread + /// keeps running until the test process exits. + fn run_parser(setup: &Setup, input: &[String]) -> Result { + init(); + + if input.is_empty() { + return Err("empty input is not supported yet (see CLAUDE SUGGESTIONS.org)".into()); + } + + let seconds: u64 = std::env::var("REP_TIMEOUT") + .ok() + .and_then(|s| s.parse().ok()) + .unwrap_or(20); + + let (sender, receiver) = std::sync::mpsc::channel(); + let (setup, input) = (setup.clone(), input.to_vec()); + + std::thread::spawn(move || { + let _ = sender.send(run_parser_unguarded(&setup, &input)); + }); + + match receiver.recv_timeout(std::time::Duration::from_secs(seconds)) { + Ok(result) => result, + Err(_) => Err(format!( + "TIMEOUT after {seconds}s: the parser does not terminate on this input" + )), + } + } + + fn run_parser_unguarded(setup: &Setup, input: &[String]) -> Result { + let outcome = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| { + let atom = DefaultAtom::from_grammar(parser_grammar(setup)) + .map_err(|e| format!("from_grammar: {e:?}"))?; + + let mut chain = DefaultChain::unit(atom).map_err(|e| format!("unit: {e:?}"))?; + + let ids: Vec = input + .iter() + .map(|token| setup.names.ters.iter().position(|t| t == token).unwrap()) + .collect(); + + for (pos, id) in ids.iter().copied().enumerate() { + chain + .chain(id, pos, false) + .map_err(|e| format!("chain() failed at token {pos}: {e:?}"))?; + } + + chain + .end_of_input(ids.len(), *ids.last().unwrap()) + .map_err(|e| format!("end_of_input: {e:?}")) + })); + + match outcome { + Ok(result) => result, + Err(payload) => { + let message = payload + .downcast_ref::() + .cloned() + .or_else(|| payload.downcast_ref::<&str>().map(|s| s.to_string())) + .unwrap_or_else(|| "unknown panic".into()); + + Err(format!("parser panicked: {message}")) + } + } + } + + // ------------------------------------------------------------ + // Reading the forest. + // + // Convention (observed on forests of passing grammars, see + // `tests/CLAUDE SUGGESTIONS.org`): + // + // - a nonterminal node's children are "position wrappers", + // nodes labelled `Rule(_)`, one per right-hand-side symbol, in + // order; each wrapper has exactly one child, the symbol; + // - an ambiguous node is labelled like a nonterminal but is + // `Packed`; its children are `Cloned` nodes, one per + // alternative, each decoded like a plain nonterminal node. + // + // ASSUMPTION, NOT YET VERIFIED: an epsilon production appears as a + // nonterminal node with no children at all. + // ------------------------------------------------------------ + + #[derive(Debug)] + pub enum UnpackError { + TooMany(usize), + Decode(String), + } + + struct NodeInfo { + status: forest::ForestLabelType, + label: GrammarLabelType, + start: usize, + end: Option, + children: Vec, + } + + fn info(forest: &Forest, node: usize) -> Result { + let decode = |e: &dyn std::fmt::Debug| UnpackError::Decode(format!("{e:?}")); + + let label = forest + .vertex_label(node) + .map_err(|e| decode(&e))? + .ok_or_else(|| UnpackError::Decode(format!("node {node} has no label")))?; + + Ok(NodeInfo { + status: label.status(), + label: label.label().label(), + start: label.label().start(), + end: label.label().end(), + children: forest + .children_of(node) + .map_err(|e| decode(&e))? + .collect(), + }) + } + + /// Expand the forest into the set of trees of height at most `h`, + /// as a sorted list WITH multiplicity (so that duplicates can be + /// reported). Alternatives are chosen per occurrence of a node. + /// Cycles are cut by the height bound. More than `limit` trees at + /// any node is an error. + pub fn unpack( + forest: &Forest, + names: &Names, + h: usize, + limit: usize, + ) -> Result, UnpackError> { + let Some(root) = forest.root() else { + return Ok(Vec::new()); + }; + + let mut memo: HashMap<(usize, usize), Vec> = HashMap::new(); + + let mut trees = go(forest, names, root, h, limit, &mut memo)?; + + trees.sort(); + + Ok(trees) + } + + fn go( + forest: &Forest, + names: &Names, + node: usize, + h: usize, + limit: usize, + memo: &mut HashMap<(usize, usize), Vec>, + ) -> Result, UnpackError> { + if let Some(done) = memo.get(&(node, h)) { + return Ok(done.clone()); + } + + let me = info(forest, node)?; + + let result = match me.label { + GrammarLabelType::TNT(TNT::Ter(t)) => vec![names.ters[t].clone()], + GrammarLabelType::TNT(TNT::Non(n)) if me.status == forest::ForestLabelType::Packed => { + // A packed node costs no height: it only chooses. + let mut all = Vec::new(); + + for alternative in me.children { + all.extend(go(forest, names, alternative, h, limit, memo)?); + } + + let _ = n; + + all + } + GrammarLabelType::TNT(TNT::Non(n)) => { + if h == 0 { + Vec::new() + } else if me.children.is_empty() { + vec![format!("({} eps)", names.nons[n])] + } else { + let mut partial: Vec> = vec![Vec::new()]; + + for wrapper in me.children { + let w = info(forest, wrapper)?; + + if w.label.rule().is_none() || w.children.len() != 1 { + return Err(UnpackError::Decode(format!( + "child {wrapper} of {node} is not a one-child position wrapper" + ))); + } + + let options = go(forest, names, w.children[0], h - 1, limit, memo)?; + + let mut next = Vec::new(); + + for prefix in &partial { + for option in &options { + let mut extended = prefix.clone(); + extended.push(option.clone()); + next.push(extended); + } + } + + if next.len() > limit { + return Err(UnpackError::TooMany(next.len())); + } + + partial = next; + } + + partial + .into_iter() + .map(|children| format!("({} {})", names.nons[n], children.join(" "))) + .collect() + } + } + GrammarLabelType::Rule(_) => { + return Err(UnpackError::Decode(format!( + "node {node} is a position wrapper where a symbol was expected" + ))); + } + }; + + if result.len() > limit { + return Err(UnpackError::TooMany(result.len())); + } + + memo.insert((node, h), result.clone()); + + Ok(result) + } + + // ------------------------------------------------------------ + // Structural invariants. + // ------------------------------------------------------------ + + /// Check the invariants of `CLAUDE.md` step 4 on a finished forest. + /// Returns the list of violations (empty if the forest is valid). + fn validate_forest(forest: &Forest, setup: &Setup, input: &[String]) -> Vec { + let mut bad: Vec = Vec::new(); + + let Some(root) = forest.root() else { + return vec!["the forest is empty (no root)".into()]; + }; + + let n = input.len(); + let names = &setup.names; + + let mut infos: Vec> = Vec::new(); + + for node in forest.nodes() { + match info(forest, node) { + Ok(i) => infos.push(Some(i)), + Err(e) => { + bad.push(format!("node {node} unreadable: {e:?}")); + infos.push(None); + } + } + } + + // Which nodes are reachable from the root? Unreachable nodes + // are reported, not checked further. + let mut reachable = vec![false; infos.len()]; + let mut stack = vec![root]; + + while let Some(node) = stack.pop() { + if node >= infos.len() || reachable[node] { + continue; + } + + reachable[node] = true; + + if let Some(i) = &infos[node] { + stack.extend(i.children.iter().copied()); + } + } + + let describe = |node: usize| -> String { + match &infos[node] { + Some(i) => { + let name = match i.label { + GrammarLabelType::TNT(TNT::Non(k)) => names.nons[k].clone(), + GrammarLabelType::TNT(TNT::Ter(k)) => names.ters[k].clone(), + GrammarLabelType::Rule(r) => format!("rule@{r}"), + }; + + format!("{name}[{},{:?}]#{node}", i.start, i.end) + } + None => format!("#{node}"), + } + }; + + let unreachable: Vec = (0..infos.len()).filter(|k| !reachable[*k]).collect(); + + if !unreachable.is_empty() { + bad.push(format!( + "{} node(s) not reachable from the root: {}", + unreachable.len(), + unreachable + .iter() + .map(|k| describe(*k)) + .collect::>() + .join(", ") + )); + } + + // Nodes are unique per (symbol, start, end); clones are exempt. + let mut seen: BTreeMap<(String, usize, Option), usize> = BTreeMap::new(); + + for node in 0..infos.len() { + if !reachable[node] { + continue; + } + + let Some(i) = &infos[node] else { continue }; + + // All nodes must be closed in a finished forest. + if i.end.is_none() { + bad.push(format!("{} is not closed (no end position)", describe(node))); + } + + if matches!(i.status, forest::ForestLabelType::Cloned(_)) { + continue; + } + + if let GrammarLabelType::TNT(tnt) = i.label { + let key = (format!("{tnt:?}"), i.start, i.end); + + if let Some(other) = seen.insert(key, node) { + bad.push(format!( + "duplicate node for (symbol, start, end): {} and {}", + describe(other), + describe(node) + )); + } + } + } + + // Per-node structure. + let signature = |wrappers: &[usize]| -> Option> { + let mut out = Vec::new(); + + for w in wrappers { + let wi = infos[*w].as_ref()?; + let child = infos[*wi.children.first()?].as_ref()?; + + out.push(match child.label { + GrammarLabelType::TNT(TNT::Non(k)) => names.nons[k].clone(), + GrammarLabelType::TNT(TNT::Ter(k)) => names.ters[k].clone(), + GrammarLabelType::Rule(_) => return None, + }); + } + + Some(out) + }; + + for node in 0..infos.len() { + if !reachable[node] { + continue; + } + + let Some(i) = &infos[node] else { continue }; + + match i.label { + GrammarLabelType::TNT(TNT::Ter(t)) => { + // Terminal children match the input. + if i.end != Some(i.start + 1) || i.start >= n || input[i.start] != names.ters[t] + { + bad.push(format!( + "terminal {} does not match the input {:?}", + describe(node), + input + )); + } + } + GrammarLabelType::TNT(TNT::Non(k)) if i.status == forest::ForestLabelType::Packed => { + let mut signatures: Vec<(Vec, Vec<(usize, Option)>)> = + Vec::new(); + + for clone in &i.children { + let Some(c) = &infos[*clone] else { continue }; + + if !matches!(c.status, forest::ForestLabelType::Cloned(_)) + || c.label != i.label + || c.start != i.start + || c.end != i.end + { + bad.push(format!( + "{}: child {} is not a clone with the same label and span", + describe(node), + describe(*clone) + )); + } + + let spans: Vec<(usize, Option)> = c + .children + .iter() + .filter_map(|w| infos[*w].as_ref().map(|wi| (wi.start, wi.end))) + .collect(); + + if let Some(sig) = signature(&c.children) { + if signatures.iter().any(|(s, sp)| *s == sig && *sp == spans) { + bad.push(format!( + "{}: two packed alternatives are identical ({} {:?})", + describe(node), + names.nons[k], + sig + )); + } + + signatures.push((sig, spans)); + } + } + } + GrammarLabelType::TNT(TNT::Non(k)) => { + // Children cover exactly [start, end], in order. + let mut at = i.start; + + for w in &i.children { + let Some(wi) = &infos[*w] else { continue }; + + if wi.label.rule().is_none() || wi.children.len() != 1 { + bad.push(format!( + "{}: child {} is not a one-child position wrapper", + describe(node), + describe(*w) + )); + + continue; + } + + if wi.start != at { + bad.push(format!( + "{}: gap or overlap before {} (expected start {at})", + describe(node), + describe(*w) + )); + } + + if let Some(sym) = &infos[wi.children[0]] { + if (sym.start, sym.end) != (wi.start, wi.end) { + bad.push(format!( + "{}: wrapper {} and its symbol {} disagree on the span", + describe(node), + describe(*w), + describe(wi.children[0]) + )); + } + } + + at = wi.end.unwrap_or(at); + } + + if i.end.is_some() && Some(at) != i.end { + bad.push(format!( + "{}: children end at {at}, not at the node's end", + describe(node) + )); + } + + // The alternative is a real production. + if let Some(sig) = signature(&i.children) { + let ok = setup + .grammar + .alternatives(&names.nons[k]) + .iter() + .any(|alt| *alt == sig); + + if !ok { + bad.push(format!( + "{}: {} -> {:?} is not a production of the grammar", + describe(node), + names.nons[k], + sig + )); + } + } + } + GrammarLabelType::Rule(_) => {} + } + } + + // Cycles: every node on a cycle has the same span. Tarjan. + let count = infos.len(); + let edges: Vec> = infos + .iter() + .map(|i| i.as_ref().map(|i| i.children.clone()).unwrap_or_default()) + .collect(); + + let mut index = vec![usize::MAX; count]; + let mut low = vec![0usize; count]; + let mut on_stack = vec![false; count]; + let mut scc_stack: Vec = Vec::new(); + let mut counter = 0usize; + let mut sccs: Vec> = Vec::new(); + + // Iterative Tarjan: (node, next child index). + for start in 0..count { + if index[start] != usize::MAX || !reachable[start] { + continue; + } + + let mut call: Vec<(usize, usize)> = vec![(start, 0)]; + + index[start] = counter; + low[start] = counter; + counter += 1; + scc_stack.push(start); + on_stack[start] = true; + + while let Some(&(v, next)) = call.last() { + if next < edges[v].len() { + call.last_mut().unwrap().1 += 1; + + let w = edges[v][next]; + + if w >= count { + continue; + } + + if index[w] == usize::MAX { + index[w] = counter; + low[w] = counter; + counter += 1; + scc_stack.push(w); + on_stack[w] = true; + call.push((w, 0)); + } else if on_stack[w] { + low[v] = low[v].min(index[w]); + } + } else { + call.pop(); + + if let Some(&(parent, _)) = call.last() { + low[parent] = low[parent].min(low[v]); + } + + if low[v] == index[v] { + let mut component = Vec::new(); + + while let Some(w) = scc_stack.pop() { + on_stack[w] = false; + component.push(w); + + if w == v { + break; + } + } + + sccs.push(component); + } + } + } + } + + for component in sccs { + let cyclic = component.len() > 1 || edges[component[0]].contains(&component[0]); + + if !cyclic { + continue; + } + + let spans: std::collections::BTreeSet<(usize, Option)> = component + .iter() + .filter_map(|k| infos[*k].as_ref().map(|i| (i.start, i.end))) + .collect(); + + if spans.len() > 1 { + bad.push(format!( + "a cycle passes through nodes of different spans: {}", + component + .iter() + .map(|k| describe(*k)) + .collect::>() + .join(", ") + )); + } + } + + // The forest is polynomial in the input length. + let symbols: usize = setup + .grammar + .rules + .iter() + .flat_map(|(_, alts)| alts.iter()) + .map(|alt| alt.len() + 1) + .sum(); + let bound = (symbols + names.ters.len() + names.nons.len() + 1) * (n + 1).pow(3); + + if infos.len() > bound { + bad.push(format!( + "the forest has {} nodes, above the polynomial bound {bound}", + infos.len() + )); + } + + bad + } + + // ------------------------------------------------------------ + // Comparison and classification. + // ------------------------------------------------------------ + + /// Compare the parser's trees (with multiplicity) with the oracle's. + /// Each kind of difference points to a different bug class. + fn classify(oracle: &BTreeSet, parser: &[String]) -> Vec { + let mut report = Vec::new(); + + let parser_set: BTreeSet = parser.iter().cloned().collect(); + + let missing: Vec<&String> = oracle.difference(&parser_set).collect(); + let extra: Vec<&String> = parser_set.difference(oracle).collect(); + + if !missing.is_empty() { + report.push(format!( + "MISSING trees (lost derivations): {} e.g. {:?}", + missing.len(), + missing.iter().take(3).collect::>() + )); + } + + if !extra.is_empty() { + report.push(format!( + "EXTRA trees (spurious derivations): {} e.g. {:?}", + extra.len(), + extra.iter().take(3).collect::>() + )); + } + + if parser.len() != parser_set.len() { + let mut duplicated: Vec<&String> = Vec::new(); + + for pair in parser.windows(2) { + if pair[0] == pair[1] && !duplicated.contains(&&pair[0]) { + duplicated.push(&pair[0]); + } + } + + report.push(format!( + "DUPLICATE trees (wrong multiplicity): {} extra copies, e.g. {:?}", + parser.len() - parser_set.len(), + duplicated.iter().take(3).collect::>() + )); + } + + report + } + + /// Run one case end to end. `Err` carries a full report: the + /// grammar, the input, and the classified differences. + pub fn check_case(grammar_text: &str, input: &str, heights: &[usize]) -> Result<(), String> { + let input = tokens(input); + let setup = Setup::new(grammar_text, &input); + + let header = format!( + "grammar:\n{}\ninput: {:?}", + grammar_text.trim(), + input.join(" ") + ); + + let forest = run_parser(&setup, &input).map_err(|e| format!("{header}\nPARSER: {e}"))?; + + // No root: correct exactly when the input has no derivation at + // all (the oracle finds no tree at any of the heights). + if forest.root().is_none() { + let total: usize = heights.iter().map(|&h| oracle_trees(&setup.grammar, &input, h).len()).sum(); + return if total == 0 { + Ok(()) + } else { + Err(format!("{header}\nthe forest is empty but the oracle finds {total} tree(s)")) + }; + } + + let mut problems: Vec = Vec::new(); + + for &h in heights { + let expected = oracle_trees(&setup.grammar, &input, h); + + match unpack(&forest, &setup.names, h, 100_000) { + Ok(parsed) => { + for line in classify(&expected, &parsed) { + problems.push(format!("h = {h}: {line}")); + } + } + Err(e) => problems.push(format!("h = {h}: cannot unpack: {e:?}")), + } + } + + for violation in validate_forest(&forest, &setup, &input) { + problems.push(format!("INVARIANT: {violation}")); + } + + if problems.is_empty() { + Ok(()) + } else { + Err(format!("{header}\n{}", problems.join("\n"))) + } + } + + fn assert_case(grammar_text: &str, input: &str, heights: &[usize]) { + if let Err(report) = check_case(grammar_text, input, heights) { + panic!("\n{report}\n"); + } + } + + // ------------------------------------------------------------ + // The test layers, in the order of CLAUDE.md. Stop at the first + // failing layer and fix it before moving on. + // ------------------------------------------------------------ + + const H: [usize; 4] = [1, 2, 3, 4]; + + // Layer 1: unambiguous, no epsilon. + // Probes (added in session 2): run with + // `cargo test --test oracle -- --ignored probe --nocapture --test-threads=1`. + // They print one line per case instead of stopping at the first failure. + #[test] + #[ignore] + fn probe_cases() { + let cases: Vec<(&str, &str)> = vec![ + ("S -> S a | b", "b a a"), + ("S -> S a b | c", "c a b a b"), + ("S -> S a | a | b", "b a a"), + ("T -> x S\nS -> S a | a", "x a"), + ("T -> x S\nS -> S a | a", "x a a"), + ("T -> x S\nS -> S a | a", "x a a a"), + ("T -> S x\nS -> S a | a", "a a x"), + ("S -> x S | S a | a", "x a a"), + ("S -> x S | S a | a", "x x a a a"), + ("S -> S a | a", "a a a a"), + ("S -> S S | a", "a a"), + ("S -> S S | a", "a a a"), + ("S -> A b\nA -> S c | d", "d b"), + ("S -> A b | d\nA -> S c", "d c b"), + ("S -> A b | d\nA -> S c", "d c b c b"), + ("S -> a A | A b\nA -> a | b", "a b"), + ]; + + for (g, i) in cases { + let r = check_case(g, i, &[1, 2, 3, 4, 5]); + println!( + "PROBE {:?} {:?} => {}", + g, + i, + match r { + Ok(()) => "OK".to_string(), + Err(e) => format!("FAIL {}", e.replace('\n', " | ")), + } + ); + } + } + + // One probe: env `DIAG_GRAMMAR` (default `S -> S a | a`) and `DIAG_INPUT` + // (default `a a`). + #[test] + #[ignore] + fn probe_one() { + let g = std::env::var("DIAG_GRAMMAR").unwrap_or("S -> S a | a".into()); + let i = std::env::var("DIAG_INPUT").unwrap_or("a a".into()); + + match check_case(&g, &i, &[1, 2, 3, 4, 5]) { + Ok(()) => println!("ONE OK"), + Err(e) => println!("ONE FAIL\n{e}"), + } + } + + // ------------------------------------------------------------ + // Regression tests for left-recursive forest construction + // (session rep-3). Written by Claude Code. Each one failed + // before the fix named in its comment; see tests/CLAUDE-PROGRESS.md. + // Heights are capped at 5 to keep the oracle fast. + // ------------------------------------------------------------ + + const H5: [usize; 5] = [1, 2, 3, 4, 5]; + + /// `graph/src/labelled/binary.rs`, `PLChildren::remove` did not + /// remove the key from `indices`: `has_edge` stayed true after + /// `remove_edge`, so a later `add_edge` to the same child was + /// silently skipped. + #[test] + fn regression_graph_remove_edge_clears_index() { + use graph::builder::BuilderMut; + use graph::labelled::binary::{PLGBuilderMut, PLGraph}; + + let mut g = PLGraph::::default(); + let mut b = PLGBuilderMut::from_graph_mut(&mut g); + b.add_vertex(0); + b.add_vertex(1); + b.add_edge(0, 1, 0).unwrap(); + b.remove_edge(0, 1, |_| true).unwrap(); + assert!(!b.has_edge(0, 1).unwrap(), "edge still reported after removal"); + b.add_edge(0, 1, 0).unwrap(); + assert!(b.has_edge(0, 1).unwrap()); + assert_eq!(b.degree(0).unwrap(), 1, "re-added edge was skipped"); + } + + /// `splone_left` must be idempotent: several `insert_item` calls + /// visit the same reduction in one step (early return when the open + /// node's first child is already the wrapper). + #[test] + fn regression_case1_three_tokens_idempotent_hook() { + assert_case("S -> S S | a", "a a a", &H5); + } + + /// The hook in `insert_item` must also fire for cloned nodes + /// (ambiguous grammars), and a node already hooked under its wrapper + /// must be reused rather than climbed (`HOOKED_ALREADY`). Both + /// fixes are needed from 4 tokens on. + #[test] + fn regression_case1_four_tokens_clone_hook() { + assert_case("S -> S S | a", "a a a a", &H5); + } + + /// Right-spine cascade (open `h` ancestors whose last child is the + /// wrapper over the node just closed complete too), the dedupe of + /// identical continuations (`bury`), and the stale-last-child + /// repair in `reduction`. `S[0,5]` loses its split-at-2 + /// alternative without them. + #[test] + fn regression_case1_five_tokens_cascade() { + assert_case("S -> S S | a", "a a a a a", &H5); + } + + /// `close_pavi(Virtual)` must not replant the virtual alternative + /// into a node that is already a left-recursive continuation, and + /// `open_ancestors` must not append to an existing open node that + /// already has a child at the edge (`Eon::Ex`). Seen from 7 tokens. + #[test] + fn regression_case1_seven_tokens_virtual_and_ex() { + assert_case("S -> S S | a", "a a a a a a a", &H5); + } + + /// Two left-recursive rules for one head (`S -> S S | S a | a`). + /// `insert_item`, hook: only a wrapper of the SAME rule counts as + /// "already hooked" (`has_h_parent`); a node hooked for the other + /// rule used to block this rule's hook, and the climb planted the + /// wrong continuation (the mixed alternative `[R4[0,1], R8[1,2]]`). + #[test] + fn regression_two_left_rules_two_tokens_hook_per_rule() { + assert_case("S -> S S | S a | a", "a a", &H5); + } + + /// Same grammar. Fails without the per-rule `has_h_parent` and + /// without the other-wrapper check in `splone_left` (MEASURED with + /// the scratch switches NOFIX_HASHP / NOFIX_OTHERW). It no longer + /// isolates the `buried` map: that panic (assertion in `insert_item` + /// on `a a a`) was removed by the other-wrapper check. + #[test] + fn regression_two_left_rules_three_tokens() { + assert_case("S -> S S | S a | a", "a a a", &H5); + } + + /// Same grammar. `splone_left` must not close again a node whose + /// first child is a closed wrapper of ANOTHER left rule: it is + /// already a continuation with incomplete children (it gave + /// `S[1,2] -> [R7[1,2]]`, i.e. the extra trees `(S (S a))`). + #[test] + fn regression_two_left_rules_four_tokens_other_wrapper() { + assert_case("S -> S S | S a | a", "a a a a", &H5); + } + + /// Same grammar. A frame closed at an earlier position was already + /// turned into open continuations by the hook; the obsolete item + /// that still names it must drop it from the stack instead of + /// splitting a closed node (it gave nodes whose children end + /// before the node does). Seen from 5 tokens. Also fails without + /// the `buried` map (`DefaultForest::buried`, `resolve_buried`): + /// MEASURED with NOFIX_BURIED, the only test of the suite that does. + #[test] + fn regression_two_left_rules_five_tokens_stale_frame() { + assert_case("S -> S S | S a | a", "a a a a a", &H5); + assert_case("S -> S S | S a | a", "a a a a a a", &H5); + } + + /// Same grammar, 7 tokens. An open continuation + /// `S[0,None] -> [R7[0,j], R8[j,6]]` whose last child (the second + /// `S` of `S S`) is complete never got its closed twin `S[0,6]`: + /// the cascade after a hook only followed wrappers of the item's + /// own fragment-root rule, and the stale frames dropped for the + /// item were not replaced by their live continuations. Lost the + /// splits k=2..4 of `S[0,6]` (104 trees at h = 5). Needs both + /// the frame remap (`hooked`) and the generalised cascade + /// (`casc_rule`); see tests/CLAUDE-PROGRESS.md. + #[test] + fn regression_two_left_rules_seven_tokens_cascade() { + assert_case("S -> S S | S a | a", "a a a a a a a", &H5); + } + + /// Same grammar, 8 tokens. `reduction()` (step 2) treated a closed + /// hook wrapper (`Rule(w)`, the first symbol of a left-recursive + /// rule) ending at `pos` as a complete child, so an open + /// continuation `S[k,None] -> [R7[k,pos]]` was closed with that + /// single child: nodes `S -> ["S"]`, not a production. Fix in + /// `chain/src/item/reduction.rs`: a closed left-wrapper rule node + /// does not count as correct (`NOFIX_WRAPLAST` in scratch). + #[test] + fn regression_two_left_rules_eight_tokens_wrapper_last_child() { + assert_case("S -> S S | S a | a", "a a a a a a a a", &H5); + } + + /// `E -> E + E | n`, 5 operands (a three-symbol left-recursive + /// rule). Four causes, all needed (MEASURED with the switches): + /// (1) cascade nodes of another rule were hooked with the rule of + /// their LAST slot (`R6`), for which no wrapper exists + /// (`left_wrapper` is keyed by the first literal after the + /// wrapper): the wrapper is the rule of the node's own first + /// child and is now passed through directly (`NOFIX_CASCWRAP`); (2) a stale last child (open, or closed at a + /// later position) of a closed node must be repointed to the closed + /// twin by a sweep at every `insert_item` entry + /// (`NOFIX_REPAIRALL`), widened to any mismatching end + /// (`NOFIX_REPAIRANY`) and run once more at the end of input + /// (`NOFIX_EOIREPAIR`); (3) `splone_left` on an in-progress open + /// node repurposed it as the hook continuation, losing the + /// in-progress node (`NOFIX_INPROG`). + #[test] + fn regression_three_symbol_left_rule_five_operands() { + assert_case("E -> E + E | n", "n + n + n + n + n", &H5); + } + + /// Coverage (they passed when written; not tied to a fix): longer + /// left-recursive rules and productions of different lengths that + /// share the leading symbol. + #[test] + fn coverage_longer_left_recursive_rules() { + assert_case("S -> S a b c | d", "d a b c a b c a b c", &H5); + assert_case("S -> S a | S b c | d", "d a b c a", &H5); + assert_case("S -> S S a b | S c | d", "d d a b c d a b", &H5); + assert_case("S -> S x S y S | a", "a x a y a x a y a", &H5); + } + + // ------------------------------------------------------------ + // Known-open cases (session rep-3). These FAIL at the time of + // writing; each names the symptom measured. They are not + // regression tests: they become regression tests once fixed. + // Written by Claude Code. + // ------------------------------------------------------------ + + + /// `S -> S S S | a`, 4 and 5 tokens (derivable lengths are odd, so + /// 4 must give NO forest). The cascade after a hook (edit 6, + /// `insert_item`) followed any wrapper whose rule equals the + /// item's rule, assuming it is the last slot of its rule (true + /// for two-symbol rules); for a three-symbol rule the middle slot + /// closed the node after two children (`S -> [R4, R5]`). Fix: the + /// wrapper must be accepting, `atom.is_accepting(r*2+1)` + /// (`NOFIX_CASCACCEPT`). + #[test] + fn regression_three_symbol_rule_incomplete_cascade() { + assert_case("S -> S S S | a", "a a a a", &H5); + assert_case("S -> S S S | a", "a a a a a", &H5); + assert_case("S -> S S S | a", "a a a a a a", &H5); + } + + /// `S -> S S S | a`, 8 tokens (not derivable: must give no + /// forest). A frame completes its node only if the child at + /// `edge` fills the last slot of its rule (hook wrapper slots + /// exempt); the hook closed `S -> [R4, R5]` after two of three + /// children (`NOFIX_ACCFRAME` in scratch). The companion filter + /// `atom.can_follow` (`NOFIX_FOLLOW`) only shows at 7 and 9 tokens + /// (invalid nodes and extras without it); see the open 7-token test. + #[test] + fn regression_three_symbol_rule_eight_tokens_frame_filters() { + assert_case("S -> S S S | a", "a a a a a a a a", &H5); + } + + /// `S -> S S S | a`, 7 tokens: the tree `(S (S a a a) (S a a a) a)` + /// was missing, because the open node + /// `S[0,None] -> [R4[0,3], R5[3,6]]` never got its third child: + /// a frame whose node is already closed at `pos` (here the cascade + /// frame for `S[3,6]`) was dropped by the planting filter instead of + /// being replaced by the open containers of its wrapper. + #[test] + fn regression_three_symbol_rule_seven_tokens_closed_frame_climb() { + assert_case("S -> S S S | a", "a a a a a a a", &H5); + } + + /// `S -> S S S | a`, 9 and 11 tokens: trees were missing (3 at h=4 + /// for 9 tokens), e.g. `(S (S a a a) (S (S a a a) a a) a)`. The item + /// that plants the third child started from the rule node of the + /// slot-5 occurrence of a pavi child that was already closed at `pos`, + /// so it only saw the parents of that rule node and not those of the + /// other wrappers of the same (shared) closed node, which lead to the + /// open container waiting for its third child. + #[test] + fn regression_three_symbol_rule_nine_and_eleven_tokens_closed_pavi_child() { + assert_case("S -> S S S | a", "a a a a a a a a a", &H5); + assert_case("S -> S S S | a", "a a a a a a a a a a a", &H5); + } + + /// Recognition bug (not forest): `S -> A A; A -> a | eps` must accept + /// `a` (`S => A A => a eps`, or `eps a`), but after the input + /// `chain.epsilon()` is false. Measured: the virtual node `[S]^a` + /// is not accepting although the rest of `S` (one `A`) is nullable. + /// Run with the forest disabled (`no_item = true`), so only the + /// recognizer is involved. + #[test] + fn open_recognition_nullable_rest_of_virtual_node() { + init(); + let toks = tokens("a"); + let setup = Setup::new("S -> A A\nA -> a | eps", &toks); + let atom = DefaultAtom::from_grammar(parser_grammar(&setup)).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + for (pos, token) in toks.iter().enumerate() { + let id = setup.names.ters.iter().position(|t| t == token).unwrap(); + chain.chain(id, pos, true).unwrap(); + } + assert!(chain.epsilon().unwrap(), "the recognizer rejects a derivable input"); + } + + /// Recognition bug (not forest): `S -> b | a` derives only one-token + /// strings, but with the unreachable rule `A -> A S A | eps` the + /// recognizer accepts `a b b b`. Without that rule, or with + /// `A -> S A | eps` instead, it rejects correctly. Traced in scratch + /// (2026-10-16): NFA states belong to rule positions and are shared by + /// all nonterminals, so inside a frame of `S` the end of `S` continues + /// into `A -> A S . A` (`S` is a left corner of `A`). Fixed in scratch + /// by allowing, inside a frame of `X`, only states of rules whose + /// nonterminal is a left corner of `X` (design doc 6.4). + #[test] + fn open_recognition_unreachable_rule_accepts_too_much() { + init(); + let toks = tokens("a b b b"); + let setup = Setup::new("S -> b | a\nA -> A S A | eps", &toks); + let atom = DefaultAtom::from_grammar(parser_grammar(&setup)).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + let mut rejected_early = false; + for (pos, token) in toks.iter().enumerate() { + let id = setup.names.ters.iter().position(|t| t == token).unwrap(); + if chain.chain(id, pos, true).is_err() { rejected_early = true; break; } + } + assert!(rejected_early || !chain.epsilon().unwrap(), "the recognizer accepts a non-derivable input"); + } + + /// Recognition bug (not forest), written by Claude Code 2026-10-16: + /// `S -> X d; X -> Y c; Y -> a` derives only `a c d`, but the + /// recognizer accepts `a c`. The state `X -> Y c .` is accepting + /// because `X` ends there, and acceptance is one flag per NFA state, so + /// it also counts as the end of the frame of `S`. Acceptance must be + /// relative to the frame's nonterminal (design doc 6.4). + #[test] + fn open_recognition_inner_rule_end_is_not_frame_end() { + init(); + let toks = tokens("a c"); + let setup = Setup::new("S -> X d\nX -> Y c\nY -> a", &toks); + let atom = DefaultAtom::from_grammar(parser_grammar(&setup)).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + let mut rejected_early = false; + for (pos, token) in toks.iter().enumerate() { + let id = setup.names.ters.iter().position(|t| t == token).unwrap(); + if chain.chain(id, pos, true).is_err() { rejected_early = true; break; } + } + assert!(rejected_early || !chain.epsilon().unwrap(), "the recognizer accepts a non-derivable input"); + } + + /// Guard for the recognizer (passes today), written by Claude Code + /// 2026-10-16: `S -> B a; B -> a B | eps` accepts `a a`. The accepting + /// path ends exactly at the end of `S -> B a`, so it is an imaginary + /// edge `Im(target)`, and the new node also has real edges. Today the + /// node is accepting only by accident (the global acceptance of + /// `B -> a B .`). With frame-relative acceptance (6.4) alone this test + /// fails, because `chain()` applies imaginary edges only to nodes + /// without real edges and `Collapsed` drops them (design doc 6.5). + #[test] + fn guard_recognition_rule_end_completion_next_to_other_edges() { + init(); + let toks = tokens("a a"); + let setup = Setup::new("S -> B a\nB -> a B | eps", &toks); + let atom = DefaultAtom::from_grammar(parser_grammar(&setup)).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + for (pos, token) in toks.iter().enumerate() { + let id = setup.names.ters.iter().position(|t| t == token).unwrap(); + chain.chain(id, pos, true).unwrap(); + } + assert!(chain.epsilon().unwrap(), "the recognizer rejects a derivable input"); + } + + /// Recognition speed (not forest), written by Claude Code 2026-10-16: + /// on `E -> E + T | T; T -> T * n | n` with `n + n + ... + n` (41 + /// tokens) the chain nodes keep growing: measured maximum degree 20 at + /// 39 tokens, total edges quadratic in the input. Every `+` leaves a + /// phantom `E -> E + . T` inside a frame of `T` (shared NFA states, + /// the same cause as `open_recognition_unreachable_rule_accepts_too_much`). + /// With the left-corner filter the maximum degree is 2 (measured in + /// scratch); the bound 4 leaves room. + #[test] + fn open_recognition_expression_grammar_node_degree_stays_bounded() { + init(); + let input = vec!["n"; 21].join(" + "); + let toks = tokens(&input); + let setup = Setup::new("E -> E + T | T\nT -> T * n | n", &toks); + let atom = DefaultAtom::from_grammar(parser_grammar(&setup)).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + for (pos, token) in toks.iter().enumerate() { + let id = setup.names.ters.iter().position(|t| t == token).unwrap(); + chain.chain(id, pos, true).unwrap(); + } + assert!(chain.epsilon().unwrap()); + let max = (0..chain.nodes_len()).map(|v| chain.degree(v).unwrap_or(0)).max().unwrap_or(0); + assert!(max <= 4, "maximum node degree {max} grows with the input"); + } + + /// Indirect left recursion: `CannotPlant` at token 1. + #[test] + fn open_indirect_left_recursion() { + assert_case("S -> A b | d\nA -> S c", "d c b", &H5); + assert_case("S -> A b | d\nA -> S c", "d c b c b", &H5); + } + + /// Nested left recursion (`S -> x S | S a | a`): the same stale + /// frame, reached through the `x S` rule. + #[test] + fn regression_nested_left_recursion_stale_frame() { + assert_case("S -> x S | S a | a", "x x a a a", &H5); + } + + #[test] + fn layer1_fixed_length() { + assert_case("S -> a a", "a a", &H); + assert_case("S -> a b c", "a b c", &H); + } + + #[test] + fn layer1_right_recursion() { + // n = 1 is the one-token case: the forest used to come out empty. + for n in 1..=4 { + assert_case("S -> a S | a", &vec!["a"; n].join(" "), &H); + } + } + + #[test] + fn layer1_nested_nonterminals() { + assert_case("S -> A b\nA -> a", "a b", &H); + assert_case("S -> A B\nA -> a\nB -> b", "a b", &H); + } + + // Layer 2: ambiguous, no epsilon (Cases 1 and 2). + #[test] + fn layer2_case_1() { + for n in 1..=5 { + assert_case("S -> S S | a", &vec!["a"; n].join(" "), &[1, 2, 3, 4, 5]); + } + } + + #[test] + fn layer2_case_2() { + assert_case("E -> E + E | n", "n + n + n", &H); + } + + // Layer 3: epsilon rules and nullable nonterminals (Cases 3 and 4). + // The empty-input halves of these cases are not supported by the + // parser's API yet, so only the non-empty inputs are run. + #[test] + fn layer3_case_3() { + assert_case("S -> A A\nA -> a | eps", "a", &H); + } + + #[test] + fn layer3_case_4() { + assert_case("S -> a S | eps", "a a", &[1, 2, 3, 4, 5]); + } + + #[test] + fn layer3_nullable_in_the_middle() { + assert_case("S -> a A b\nA -> eps | A c", "a b", &H); + assert_case("S -> a A b\nA -> eps | A c", "a c c b", &[1, 2, 3, 4, 5]); + } + + // Layer 4: left, right and hidden left recursion. + #[test] + fn layer4_left_recursion() { + for n in 1..=4 { + assert_case("S -> S a | a", &vec!["a"; n].join(" "), &[1, 2, 3, 4, 5]); + } + } + + #[test] + fn layer4_hidden_left_recursion() { + assert_case("S -> A S a | a\nA -> eps", "a a a", &H); + } + + // Layer 5: cyclic grammars (Case 5). + #[test] + fn layer5_case_5a() { + assert_case("S -> S | a", "a", &H); + } + + #[test] + fn layer5_case_5c() { + assert_case("S -> A | a\nA -> S", "a", &[1, 2, 3, 4, 5]); + } + + #[test] + fn layer5_case_5d() { + assert_case("S -> S S | S | a", "a a", &H); + } + + #[test] + fn layer5_highly_ambiguous_with_epsilon() { + assert_case("S -> S S | a | eps", "a a", &H); + } + + // Layer 6: random small grammars. Slow and noisy while earlier + // layers fail, so it is ignored by default: run it with + // `cargo test --test oracle -- --ignored`. Reproducible: the seed + // is printed, and can be set with `REP_SEED`; `REP_CASES` sets the + // number of cases. + struct Rng(u64); + + impl Rng { + fn next(&mut self) -> u64 { + // xorshift64* + self.0 ^= self.0 >> 12; + self.0 ^= self.0 << 25; + self.0 ^= self.0 >> 27; + self.0.wrapping_mul(0x2545F4914F6CDD1D) + } + + fn below(&mut self, n: usize) -> usize { + (self.next() % n as u64) as usize + } + } + + fn random_grammar(rng: &mut Rng) -> String { + let nons = ["S", "A", "B"]; + let count = 1 + rng.below(3); + let symbols: Vec<&str> = ["a", "b"].into_iter().chain(nons[..count].iter().copied()).collect(); + + let mut lines = Vec::new(); + + for nt in &nons[..count] { + let alternatives: Vec = (0..1 + rng.below(3)) + .map(|_| { + let len = rng.below(4); + + if len == 0 { + "eps".to_string() + } else { + (0..len) + .map(|_| symbols[rng.below(symbols.len())]) + .collect::>() + .join(" ") + } + }) + .collect(); + + lines.push(format!("{nt} -> {}", alternatives.join(" | "))); + } + + lines.join("\n") + } + + #[test] + #[ignore] + fn layer6_random_grammars() { + let seed: u64 = std::env::var("REP_SEED") + .ok() + .and_then(|s| s.parse().ok()) + .unwrap_or(0x5EED); + let cases: usize = std::env::var("REP_CASES") + .ok() + .and_then(|s| s.parse().ok()) + .unwrap_or(50); + + eprintln!("layer 6: seed = {seed}, cases = {cases}"); + + let mut rng = Rng(seed | 1); + let mut failures = Vec::new(); + + for case in 0..cases { + let grammar_text = random_grammar(&mut rng); + let len = 1 + rng.below(6); + let input: Vec<&str> = (0..len).map(|_| ["a", "b"][rng.below(2)]).collect(); + + if let Err(report) = check_case(&grammar_text, &input.join(" "), &[1, 2, 3, 4]) { + failures.push(format!("case {case} (seed {seed}):\n{report}")); + } + } + + assert!( + failures.is_empty(), + "\n{} of {cases} random cases failed; first:\n{}\n", + failures.len(), + failures[0] + ); + } +} diff --git a/tests/spike.rs b/tests/spike.rs new file mode 100644 index 0000000..69fbf38 --- /dev/null +++ b/tests/spike.rs @@ -0,0 +1,279 @@ +//! Step 1 spike (written by Claude Code): dump the raw forest layout +//! for `S -> S S | a` on `aaa`, to learn how nodes, packed nodes, +//! clones and rule nodes are laid out. This is exploratory; it only +//! prints, and asserts nothing about the forest's shape. + +use chain::atom::DefaultAtom; +use chain::default::DefaultChain; +use chain::Chain; +use forest::Forest; +use graph::{Graph, LabelGraph, ParentsGraph}; +use grammar::test_grammar_helper::scan_tnt; +use grammar::{Grammar, Nonterminal, Rule, Terminal, TNT}; +use nfa::default::regex::DefaultRegParser; +use nfa::DesRec; + +/// The parser's debug dumps (`print_viz`) write to `output/...` +/// relative to the current directory. Run from a temp directory so +/// that they neither fail nor litter the source tree. +fn init() { + static INIT: std::sync::Once = std::sync::Once::new(); + + INIT.call_once(|| { + let dir = std::env::temp_dir().join("rep-tests"); + std::fs::create_dir_all(dir.join("output")).unwrap(); + std::env::set_current_dir(dir).unwrap(); + }); +} + +/// Build a grammar from terminal names, nonterminal names (the first +/// one is the start symbol) and one rule string per nonterminal, in +/// the `T` / `N` notation of `scan_tnt`. +fn make_grammar(ters: &[&str], nons: &[&str], rules: &[&str]) -> Grammar { + let mut parser: DefaultRegParser = Default::default(); + + for t in ters { + parser.add_tnt(t, true); + } + for n in nons { + parser.add_tnt(n, false); + } + + let rules = rules + .iter() + .map(|r| { + Rule::new( + parser + .parse(r, Box::new(scan_tnt), true) + .unwrap() + .unwrap() + .0, + ) + }) + .collect(); + + Grammar::new( + ters.iter().map(|t| Terminal::new((*t).to_owned())).collect(), + nons.iter().map(|n| Nonterminal::new((*n).to_owned())).collect(), + rules, + ) +} + +/// Find at which token the chain first fails, for `S -> S S | a` on +/// `a^n`. +#[test] +fn locate_failure_case1() { + init(); + + for n in 1..=4usize { + let grammar = make_grammar(&["a"], &["S"], &["NS NS | Ta"]); + let atom = DefaultAtom::from_grammar(grammar).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + + let mut outcome = String::from("all tokens consumed"); + + for pos in 0..n { + if let Err(e) = chain.chain(0, pos, false) { + outcome = format!("chain() failed at pos {pos}: {e:?}"); + break; + } + } + + eprintln!("RESULT n={n}: {outcome}"); + } +} + +/// Sanity check of the harness: unambiguous grammars (layer 1) should +/// get through `chain()` for every prefix of `a^4`. +#[test] +fn layer1_sanity() { + init(); + + let cases: [(&str, &str); 3] = [ + ("S -> a S | a", "Ta NS | Ta"), + ("S -> S a | a", "NS Ta | Ta"), + ("S -> a a", "Ta Ta"), + ]; + + for (name, rule) in cases { + for n in 1..=4usize { + let grammar = make_grammar(&["a"], &["S"], &[rule]); + let atom = DefaultAtom::from_grammar(grammar).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + + let mut outcome = String::from("ok"); + + for pos in 0..n { + if let Err(e) = chain.chain(0, pos, false) { + outcome = format!("chain() failed at pos {pos}: {e:?}"); + break; + } + } + + eprintln!("LAYER1 {name}, n={n}: {outcome}"); + } + } +} + +/// Same failing inputs, but with forest building off (`no_item = +/// true`): does recognition alone get through? +#[test] +fn recognition_only() { + init(); + + for (name, rule) in [("S -> S S | a", "NS NS | Ta"), ("S -> S a | a", "NS Ta | Ta")] { + for n in 1..=4usize { + let grammar = make_grammar(&["a"], &["S"], &[rule]); + let atom = DefaultAtom::from_grammar(grammar).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + + let mut outcome = String::from("ok"); + + for pos in 0..n { + if let Err(e) = chain.chain(0, pos, true) { + outcome = format!("chain() failed at pos {pos}: {e:?}"); + break; + } + } + + let accepted = chain.epsilon().unwrap(); + + eprintln!("RECOG {name}, n={n}: {outcome}, accepted={accepted}"); + } + } +} + +/// Probe the atom of `S -> S a | a`: which (nt=0, t=0, target) have +/// virtual traces, and what the NFA looks like. +#[test] +fn probe_atom_left_recursion() { + use chain::atom::Atom; + + init(); + + let grammar = make_grammar(&["a"], &["S"], &["NS Ta | Ta"]); + let atom = DefaultAtom::from_grammar(grammar).unwrap(); + + eprintln!("PROBE grammar:\n{}", &*atom); + eprintln!("PROBE virtual node (S, a) = {:?}", atom.atom(0, 0)); + eprintln!("PROBE accepting_len = {}", atom.accepting_len()); + atom.print_virtual(); + + { + use graph::LabelGraph; + + let non_start = atom.nth_accumulator(0).unwrap() * 2; + + eprintln!("PROBE non_start = {non_start}"); + + for (label, children) in atom.labels_of(non_start).unwrap() { + for child in children { + eprintln!( + "PROBE edge from non_start labelled {label:?} to {child}: \ + query_expansion = {:?}", + atom.query_expansion(non_start, child) + ); + } + } + } + + { + use graph::LabelGraph; + + for node in [5usize, 7, 9, 14] { + for (label, children) in atom.labels_of(node).unwrap() { + eprintln!( + "PROBE edges of node {node}: {label:?} -> {:?}, reduction to first = {:?}", + children.clone().collect::>(), + children + .clone() + .map(|c| atom.query_reduction(node, c).ok().flatten().map(|s| s.to_vec())) + .collect::>() + ); + } + } + } + + for pos in 0..8 { + eprintln!("PROBE rule_pos {pos}: {:?}", atom.rule_pos_to_string(pos)); + } + + for target in 0..atom.accepting_len() { + let rules: Option> = atom.trace(0, 0, target).map(|i| i.collect()); + eprintln!("PROBE trace(S, a, target {target}) = {rules:?}"); + } +} + +/// Dump the working forest after each token, for `S -> S a | a`. +#[test] +fn forest_after_each_token() { + init(); + + let grammar = make_grammar(&["a"], &["S"], &["NS Ta | Ta"]); + let atom = DefaultAtom::from_grammar(grammar).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + + let dump = |chain: &DefaultChain, title: &str| { + let forest = chain.forest(); + + eprintln!("FOREST {title}: root={:?}", forest.root()); + + for node in forest.nodes() { + let l = forest.vertex_label(node).unwrap(); + eprintln!( + "FOREST node {node}: {:?} parents={:?} children={:?}", + l.map(|l| (l.status(), l.label().label(), l.label().start(), l.label().end())), + forest.parents_of(node).map(|i| i.collect::>()), + forest.children_of(node).map(|i| i.collect::>()) + ); + } + }; + + dump(&chain, "initial"); + + for pos in 0..2usize { + let r = chain.chain(0, pos, false); + dump(&chain, &format!("after token {pos}, result {r:?}")); + } +} + +#[test] +fn dump_case1() { + init(); + + let grammar = make_grammar(&["a"], &["S"], &["NS NS | Ta"]); + + let atom = DefaultAtom::from_grammar(grammar).unwrap(); + let mut chain = DefaultChain::unit(atom).unwrap(); + + let toks = [0usize, 0, 0]; + + for (pos, t) in toks.iter().copied().enumerate() { + chain.chain(t, pos, false).unwrap(); + } + + assert!(chain.epsilon().unwrap()); + + let forest = chain + .end_of_input(toks.len(), *toks.last().unwrap()) + .unwrap(); + + println!("=== FOREST DUMP ==="); + println!("root = {:?}", forest.root()); + + for node in forest.nodes() { + let label = forest.vertex_label(node).unwrap(); + let children: Vec = forest.children_of(node).unwrap().collect(); + + match label { + Some(l) => println!( + "node {node}: status={:?} label={:?} start={} end={:?} children={children:?}", + l.status(), + l.label().label(), + l.label().start(), + l.label().end(), + ), + None => println!("node {node}: no label, children={children:?}"), + } + } +} -- cgit v1.2.3-18-g5258