path: root/tests/oracle.rs

//! 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]
        );
    }
}