new startHEADmaster

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.

1 files changed, 1803 insertions, 0 deletions

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<Vec<String>>)>,
+}
+
+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<String>>)> = 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<Vec<String>> = rhs
+                .split('|')
+                .map(|alt| {
+                    let symbols: Vec<String> =
+                        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<String>] {
+        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<String> {
+    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<String> {
+    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<String> {
+    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<Vec<String>> {
+    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<String> = 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<String> {
+        items.iter().map(|s| s.to_string()).collect()
+    }
+
+    fn trees(grammar: &str, input: &str, h: usize) -> BTreeSet<String> {
+        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(&current), "{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<forest::ForestLabel<grammar::GrammarLabel>>;
+
+    // ------------------------------------------------------------
+    // 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<String>,
+        ters: Vec<String>,
+    }
+
+    /// 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<String> = grammar.rules.iter().map(|(n, _)| n.clone()).collect();
+
+            let mut ters: Vec<String> = 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<name>` / `N<name>` and looks `<name>` 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<TNT> = 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<Rule> = 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<String> = 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::<Vec<_>>()
+                            .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<Forest, String> {
+        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<Forest, String> {
+        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<usize> = 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::<String>()
+                    .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<usize>,
+        children: Vec<usize>,
+    }
+
+    fn info(forest: &Forest, node: usize) -> Result<NodeInfo, UnpackError> {
+        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<Vec<String>, UnpackError> {
+        let Some(root) = forest.root() else {
+            return Ok(Vec::new());
+        };
+
+        let mut memo: HashMap<(usize, usize), Vec<String>> = 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<String>>,
+    ) -> Result<Vec<String>, 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<String>> = 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<String> {
+        let mut bad: Vec<String> = 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<Option<NodeInfo>> = 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<usize> = (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::<Vec<_>>()
+                    .join(", ")
+            ));
+        }
+
+        // Nodes are unique per (symbol, start, end); clones are exempt.
+        let mut seen: BTreeMap<(String, usize, Option<usize>), 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<Vec<String>> {
+            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<String>, Vec<(usize, Option<usize>)>)> =
+                        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<usize>)> = 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<Vec<usize>> = 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<usize> = Vec::new();
+        let mut counter = 0usize;
+        let mut sccs: Vec<Vec<usize>> = 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<usize>)> = 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::<Vec<_>>()
+                        .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<String>, parser: &[String]) -> Vec<String> {
+        let mut report = Vec::new();
+
+        let parser_set: BTreeSet<String> = 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::<Vec<_>>()
+            ));
+        }
+
+        if !extra.is_empty() {
+            report.push(format!(
+                "EXTRA trees (spurious derivations): {} e.g. {:?}",
+                extra.len(),
+                extra.iter().take(3).collect::<Vec<_>>()
+            ));
+        }
+
+        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::<Vec<_>>()
+            ));
+        }
+
+        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<String> = 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::<usize>::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<String> = (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::<Vec<_>>()
+                            .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]
+        );
+    }
+}