aboutsummaryrefslogtreecommitdiff
path: root/tests/oracle.rs
diff options
context:
space:
mode:
Diffstat (limited to 'tests/oracle.rs')
-rw-r--r--tests/oracle.rs1803
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]
+ );
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2026-10-21 11:50:22 +0000