aboutsummaryrefslogtreecommitdiff
path: root/tests/oracle.rs
diff options
context:
space:
mode:
Diffstat (limited to 'tests/oracle.rs')
-rw-r--r--tests/oracle.rs579
1 files changed, 579 insertions, 0 deletions
diff --git a/tests/oracle.rs b/tests/oracle.rs
index cab790f..1390511 100644
--- a/tests/oracle.rs
+++ b/tests/oracle.rs
@@ -1800,4 +1800,583 @@ mod parser_side {
failures[0]
);
}
+
+ // ------------------------------------------------------------
+ // Recognition gate (plan step 1), written by Claude Code.
+ //
+ // The recognizer (run with `no_item = true`, so no forest is built)
+ // must accept an input if and only if the input is derivable.
+ // Derivability is computed exactly, without a height bound, by a
+ // fixpoint over the facts `(X, i, j)`.
+ // ------------------------------------------------------------
+
+ /// Exact derivability of `tokens` from the start symbol.
+ fn exact_derivable(grammar: &Grammar, tokens: &[String]) -> bool {
+ let n = tokens.len();
+ let mut facts: std::collections::BTreeSet<(String, usize, usize)> = Default::default();
+
+ loop {
+ let before = facts.len();
+
+ for (nt, alternatives) in &grammar.rules {
+ for alt in alternatives {
+ for i in 0..=n {
+ // Positions reachable after matching a prefix of `alt`.
+ let mut ends = std::collections::BTreeSet::from([i]);
+
+ for symbol in alt {
+ let mut next = std::collections::BTreeSet::new();
+
+ for &k in &ends {
+ if grammar.is_nonterminal(symbol) {
+ for l in k..=n {
+ if facts.contains(&(symbol.clone(), k, l)) {
+ next.insert(l);
+ }
+ }
+ } else if k < n && tokens[k] == *symbol {
+ next.insert(k + 1);
+ }
+ }
+
+ ends = next;
+ }
+
+ for j in ends {
+ facts.insert((nt.clone(), i, j));
+ }
+ }
+ }
+ }
+
+ if facts.len() == before {
+ break;
+ }
+ }
+
+ facts.contains(&(grammar.start.clone(), 0, n))
+ }
+
+ /// Run only the recognizer, with the same timeout and panic guard as
+ /// `run_parser`. An error from `chain` counts as a rejection.
+ fn recognizes(setup: &Setup, input: &[String]) -> Result<bool, String> {
+ init();
+
+ let (setup, input) = (setup.clone(), input.to_vec());
+ let (sender, receiver) = std::sync::mpsc::channel();
+
+ std::thread::spawn(move || {
+ 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:?}"))?;
+
+ for (pos, token) in input.iter().enumerate() {
+ let id = setup.names.ters.iter().position(|t| t == token).unwrap();
+
+ if chain.chain(id, pos, true).is_err() {
+ return Ok(false);
+ }
+ }
+
+ chain.epsilon().map_err(|e| format!("epsilon: {e:?}"))
+ }));
+
+ let _ = sender.send(match outcome {
+ Ok(result) => result,
+ Err(_) => Err("parser panicked".to_string()),
+ });
+ });
+
+ receiver
+ .recv_timeout(std::time::Duration::from_secs(20))
+ .unwrap_or_else(|_| Err("TIMEOUT".to_string()))
+ }
+
+ /// Compare the recognizer with exact derivability on one input.
+ fn check_recognition(grammar_text: &str, input: &str) -> Result<(), String> {
+ let input = tokens(input);
+ let setup = Setup::new(grammar_text, &input);
+ let expected = exact_derivable(&setup.grammar, &input);
+
+ match recognizes(&setup, &input) {
+ Ok(got) if got == expected => Ok(()),
+ Ok(got) => Err(format!(
+ "grammar:\n{}\ninput: {:?}\nrecognizer says {got}, exact derivability is {expected}",
+ grammar_text.trim(),
+ input.join(" ")
+ )),
+ Err(e) => Err(format!(
+ "grammar:\n{}\ninput: {:?}\n{e}",
+ grammar_text.trim(),
+ input.join(" ")
+ )),
+ }
+ }
+
+ /// Every input of length 1 to `max_len` over `alphabet`.
+ fn all_inputs(alphabet: &[&str], max_len: usize) -> Vec<String> {
+ let mut result = Vec::new();
+ let mut layer: Vec<Vec<&str>> = vec![Vec::new()];
+
+ for _ in 0..max_len {
+ layer = layer
+ .iter()
+ .flat_map(|prefix| {
+ alphabet.iter().map(move |t| {
+ let mut v = prefix.clone();
+ v.push(t);
+ v
+ })
+ })
+ .collect();
+
+ result.extend(layer.iter().map(|v| v.join(" ")));
+ }
+
+ result
+ }
+
+ #[test]
+ fn gate_recognition_hand_cases() {
+ let cases: &[(&str, &[&str], usize)] = &[
+ ("S -> a a", &["a"], 4),
+ ("S -> a S | a", &["a"], 5),
+ ("S -> S a | a", &["a"], 5),
+ ("S -> S S | a", &["a"], 5),
+ ("S -> S S | S | a", &["a"], 4),
+ ("S -> S S | a | eps", &["a"], 4),
+ ("S -> S | a", &["a"], 3),
+ ("S -> A | a\nA -> S", &["a"], 3),
+ ("S -> A A\nA -> a | eps", &["a"], 4),
+ ("S -> a S | eps", &["a"], 4),
+ ("S -> a A b\nA -> eps | A c", &["a", "b", "c"], 5),
+ ("S -> A S a | a\nA -> eps", &["a"], 5),
+ ("S -> B a\nB -> a B | eps", &["a"], 5),
+ ("S -> b | a\nA -> A S A | eps", &["a", "b"], 5),
+ ("S -> X d\nX -> Y c\nY -> a", &["a", "c", "d"], 4),
+ ("S -> Y\nY -> A | B\nA -> x\nB -> x", &["x"], 3),
+ ("S -> A\nA -> B C\nB -> x | eps\nC -> y | eps", &["x", "y"], 4),
+ ("S -> A b | d\nA -> S c", &["b", "c", "d"], 5),
+ ("S -> x S | S a | a", &["x", "a"], 5),
+ ("S -> a S b | eps", &["a", "b"], 6),
+ ("E -> E + T | T\nT -> T * n | n", &["n", "+", "*"], 5),
+ ("E -> E + E | n", &["n", "+"], 5),
+ ];
+
+ let mut failures = Vec::new();
+
+ for (grammar, alphabet, max_len) in cases {
+ for input in all_inputs(alphabet, *max_len) {
+ if let Err(report) = check_recognition(grammar, &input) {
+ failures.push(report);
+ }
+ }
+ }
+
+ assert!(
+ failures.is_empty(),
+ "\n{} mismatches; first:\n{}\n",
+ failures.len(),
+ failures.join("\n--\n")
+ );
+ }
+
+ #[test]
+ fn gate_recognition_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(200);
+
+ eprintln!("recognition gate: seed = {seed}, cases = {cases}");
+
+ let mut rng = Rng(seed | 1);
+ let mut failures = Vec::new();
+
+ for _ 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_recognition(&grammar_text, &input.join(" ")) {
+ failures.push(report);
+ }
+ }
+
+ assert!(
+ failures.is_empty(),
+ "\n{} of {cases} mismatches (seed {seed}); first:\n{}\n",
+ failures.len(),
+ failures[0]
+ );
+ }
+
+ /// Print the chain after every token (recognizer only), for
+ /// `DIAG_GRAMMAR` and `DIAG_INPUT`. Written by Claude Code.
+ #[test]
+ #[ignore]
+ fn probe_chain() {
+ init();
+ let g = std::env::var("DIAG_GRAMMAR").unwrap_or("S -> A A\nA -> a | eps".into());
+ let i = std::env::var("DIAG_INPUT").unwrap_or("a a a".into());
+ let toks = tokens(&i);
+ let setup = Setup::new(&g, &toks);
+ let atom = DefaultAtom::from_grammar(parser_grammar(&setup)).unwrap();
+ if std::env::var("DIAG_ATOM").is_ok() {
+ use chain::atom::Atom;
+ for node in 0..atom.nodes_len() {
+ let name = atom.rule_pos_string(node / 2).map(|n| format!("{n} ({})", node % 2)).unwrap_or_default();
+ for (label, targets) in atom.labels_of(node).unwrap() {
+ println!("ATOM {node} [{name}] --{label}--> {:?} (acc={})", targets.collect::<Vec<_>>(), atom.is_accepting(node).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();
+ let result = chain.chain(id, pos, true);
+ println!("after token {pos} ({token}): {result:?}; current = {}, accepting = {:?}",
+ chain.current(), chain.epsilon());
+
+ for (label, targets) in chain.labels_of(chain.current()).unwrap() {
+ let name = chain.atom().rule_pos_string(label.label()).unwrap_or_else(|_| format!("#{}", label.label()));
+ println!(" {name} [state {}] frame={} acc={} -> {:?}",
+ label.label(), label.frame_nt(), label.is_accepting(), targets.collect::<Vec<_>>());
+ }
+ }
+ }
+
+ // ------------------------------------------------------------
+ // Facts gate (plan step 10), written by Claude Code.
+ //
+ // While the parser reads the input it records facts `(X, i, j)`.
+ // The recording alone is checked here, without the forest: after
+ // an eager closure of the recorded facts,
+ //
+ // - no fact is missing: every nonterminal node of every oracle
+ // tree (of height at most `h`) with a non-empty span is a fact;
+ // - the input is derivable from the facts (plus the empty spans,
+ // which come from nullability) if and only if it is derivable.
+ // ------------------------------------------------------------
+
+ /// The facts `(X, i, j)` with `i < j` of a tree in the notation of
+ /// the oracle.
+ fn tree_facts(tree: &str, nons: &[String]) -> BTreeSet<(usize, usize, usize)> {
+ let padded = tree.replace('(', " ( ").replace(')', " ) ");
+ let words: Vec<&str> = padded.split_whitespace().collect();
+
+ let mut result = BTreeSet::new();
+ let mut stack: Vec<(usize, usize)> = Vec::new();
+ let mut at = 0usize;
+ let mut k = 0usize;
+
+ while k < words.len() {
+ match words[k] {
+ "(" => {
+ let name = words[k + 1];
+ stack.push((nons.iter().position(|n| n == name).unwrap(), at));
+ k += 1;
+ }
+ ")" => {
+ let (nt, start) = stack.pop().unwrap();
+
+ if at > start {
+ result.insert((nt, start, at));
+ }
+ }
+ "eps" => {}
+ _ => at += 1,
+ }
+
+ k += 1;
+ }
+
+ result
+ }
+
+ /// Derivability when a nonterminal may derive a non-empty span
+ /// only if that is a recorded fact.
+ fn derivable_from_facts(
+ grammar: &Grammar,
+ nons: &[String],
+ tokens: &[String],
+ facts: &BTreeSet<(usize, usize, usize)>,
+ ) -> bool {
+ let n = tokens.len();
+ let id = |name: &str| nons.iter().position(|x| x == name).unwrap();
+ let mut known: BTreeSet<(usize, usize, usize)> = BTreeSet::new();
+
+ loop {
+ let before = known.len();
+
+ for (nt, alternatives) in &grammar.rules {
+ for alt in alternatives {
+ for i in 0..=n {
+ let mut ends = BTreeSet::from([i]);
+
+ for symbol in alt {
+ let mut next = BTreeSet::new();
+
+ for &k in &ends {
+ if grammar.is_nonterminal(symbol) {
+ for l in k..=n {
+ if known.contains(&(id(symbol), k, l)) {
+ next.insert(l);
+ }
+ }
+ } else if k < n && tokens[k] == *symbol {
+ next.insert(k + 1);
+ }
+ }
+
+ ends = next;
+ }
+
+ for j in ends {
+ if i == j || facts.contains(&(id(nt), i, j)) {
+ known.insert((id(nt), i, j));
+ }
+ }
+ }
+ }
+ }
+
+ if known.len() == before {
+ break;
+ }
+ }
+
+ known.contains(&(0, 0, n))
+ }
+
+ /// Run the parser with the forest requested and return the chain.
+ fn run_chain(setup: &Setup, input: &[String]) -> Result<DefaultChain, String> {
+ init();
+
+ 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:?}"))?;
+
+ for (pos, token) in input.iter().enumerate() {
+ let id = setup.names.ters.iter().position(|t| t == token).unwrap();
+
+ chain
+ .chain(id, pos, false)
+ .map_err(|e| format!("chain() failed at token {pos}: {e:?}"))?;
+ }
+
+ Ok(chain)
+ }))
+ .unwrap_or_else(|_| Err("parser panicked".to_string()))
+ }
+
+ fn check_facts(grammar_text: &str, input: &str, h: 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 chain = run_chain(&setup, &input).map_err(|e| format!("{header}\n{e}"))?;
+
+ let facts = chain
+ .facts()
+ .eager_closure(chain.tokens(), chain.atom())
+ .map_err(|e| format!("{header}\neager closure: {e:?}"))?;
+
+ let mut problems = Vec::new();
+
+ let mut wanted = BTreeSet::new();
+
+ for tree in oracle_trees(&setup.grammar, &input, h) {
+ wanted.extend(tree_facts(&tree, &setup.names.nons));
+ }
+
+ let name = |f: &(usize, usize, usize)| format!("{}[{},{}]", setup.names.nons[f.0], f.1, f.2);
+
+ let missing: Vec<String> = wanted.difference(&facts).map(name).collect();
+
+ if !missing.is_empty() {
+ problems.push(format!("missing facts: {missing:?}"));
+ }
+
+ let exact = exact_derivable(&setup.grammar, &input);
+ let from_facts = derivable_from_facts(&setup.grammar, &setup.names.nons, &input, &facts);
+
+ if exact != from_facts {
+ problems.push(format!("derivable from facts is {from_facts}, exact derivability is {exact}"));
+ }
+
+ if problems.is_empty() {
+ Ok(())
+ } else {
+ Err(format!("{header}\n{}", problems.join("\n")))
+ }
+ }
+
+ #[test]
+ fn gate_facts_hand_cases() {
+ let cases: &[(&str, &str, usize)] = &[
+ ("S -> a a", "a a", 3),
+ ("S -> a S | a", "a a a a", 6),
+ ("S -> A b\nA -> a", "a b", 3),
+ ("S -> A B\nA -> a\nB -> b", "a b", 3),
+ ("S -> S S | a", "a a a a a a", 6),
+ ("E -> E + E | n", "n + n + n", 5),
+ ("S -> A A\nA -> a | eps", "a", 4),
+ ("S -> a S | eps", "a a", 5),
+ ("S -> a A b\nA -> eps | A c", "a c c b", 5),
+ ("S -> S a | a", "a a a a", 5),
+ ("S -> A S a | a\nA -> eps", "a a a", 5),
+ ("S -> S | a", "a", 4),
+ ("S -> A | a\nA -> S", "a", 5),
+ ("S -> S S | S | a", "a a", 4),
+ ("S -> S S | a | eps", "a a", 4),
+ ("S -> S S S | a", "a a a a a a a a a", 5),
+ ("S -> S S | S a | a", "a a a a a a a", 5),
+ ("S -> A b | d\nA -> S c", "d c b c b", 6),
+ ("S -> x S | S a | a", "x x a a a", 6),
+ ("E -> E + T | T\nT -> T * n | n", "n + n * n + n", 6),
+ ("S -> Y c\nY -> A | B\nA -> x\nB -> x", "x c", 5),
+ ("S -> Y\nY -> A | B\nA -> x\nB -> x", "x", 5),
+ ("S -> Y c | Y\nY -> A d | B\nA -> B\nB -> x", "x d c", 6),
+ ("S -> A c | B c\nA -> x\nB -> x", "x c", 4),
+ ("S -> A\nA -> B C\nB -> x | eps\nC -> y | eps", "x", 5),
+ ("S -> A B c\nA -> x | eps\nB -> A | eps", "x c", 5),
+ ];
+
+ let mut failures = Vec::new();
+
+ for (grammar, input, h) in cases {
+ if let Err(report) = check_facts(grammar, input, *h) {
+ failures.push(report);
+ }
+ }
+
+ assert!(
+ failures.is_empty(),
+ "\n{} failing cases; first:\n{}\n",
+ failures.len(),
+ failures[0]
+ );
+ }
+
+ #[test]
+ fn gate_facts_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(150);
+
+ eprintln!("facts gate: seed = {seed}, cases = {cases}");
+
+ let mut rng = Rng(seed | 1);
+ let mut failures = Vec::new();
+
+ for _ 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_facts(&grammar_text, &input.join(" "), 4) {
+ failures.push(report);
+ }
+ }
+
+ assert!(
+ failures.is_empty(),
+ "\n{} of {cases} failing (seed {seed}); first:\n{}\n",
+ failures.len(),
+ failures[0]
+ );
+ }
+
+ // ------------------------------------------------------------
+ // Sizes (plan section 4.6): the forest must be polynomial, and
+ // for the linear grammars below, linear in the input.
+ // ------------------------------------------------------------
+
+ fn forest_size(grammar_text: &str, input: &str) -> (usize, usize) {
+ let input = tokens(input);
+ let setup = Setup::new(grammar_text, &input);
+ let start = std::time::Instant::now();
+ let forest = run_parser(&setup, &input).expect("the parser fails");
+ let _ = start.elapsed();
+
+ (forest.nodes_len(), forest.edges().count())
+ }
+
+ #[test]
+ fn size_linear_grammars_have_linear_forests() {
+ for (grammar, token) in [
+ ("S -> a S | eps", "a"),
+ ("S -> S a | a", "a"),
+ ("S -> a S b | eps", "a b"),
+ ] {
+ let make = |n: usize| {
+ if grammar.contains('b') {
+ format!("{} {}", vec!["a"; n].join(" "), vec!["b"; n].join(" "))
+ } else {
+ vec![token; n].join(" ")
+ }
+ };
+
+ let (small, _) = forest_size(grammar, &make(20));
+ let (large, _) = forest_size(grammar, &make(40));
+
+ assert!(
+ large <= 2 * small + 8,
+ "{grammar}: {small} nodes at 20 and {large} nodes at 40 are not linear"
+ );
+ }
+ }
+
+ #[test]
+ fn size_ambiguous_grammar_is_cubic_at_most() {
+ let (small, _) = forest_size("S -> S S | a", &vec!["a"; 10].join(" "));
+ let (large, _) = forest_size("S -> S S | a", &vec!["a"; 20].join(" "));
+
+ // O(n^2) nodes with O(n) alternatives each; doubling the input
+ // multiplies the nodes by about 4 to 8.
+ assert!(large <= 10 * small, "{small} nodes at 10 and {large} nodes at 20");
+ }
+
+ /// Recognition of long inputs (plan step 6): no quadratic behaviour
+ /// for left and right recursion and for the expression grammar.
+ #[test]
+ fn recognition_time_on_long_inputs() {
+ init();
+
+ for (grammar, input) in [
+ ("S -> a S | a", vec!["a"; 400].join(" ")),
+ ("S -> S a | a", vec!["a"; 400].join(" ")),
+ ("E -> E + T | T\nT -> T * n | n", vec!["n"; 200].join(" + ")),
+ ] {
+ let toks = tokens(&input);
+ let setup = Setup::new(grammar, &toks);
+ let atom = DefaultAtom::from_grammar(parser_grammar(&setup)).unwrap();
+ let mut chain = DefaultChain::unit(atom).unwrap();
+ let start = std::time::Instant::now();
+
+ for (pos, token) in toks.iter().enumerate() {
+ let id = setup.names.ters.iter().position(|t| t == token).unwrap();
+ chain.chain(id, pos, true).unwrap();
+ }
+
+ let elapsed = start.elapsed();
+
+ assert!(chain.epsilon().unwrap());
+ eprintln!("{} tokens, {grammar:?}: {elapsed:?}", toks.len());
+ assert!(elapsed < std::time::Duration::from_secs(10), "{grammar}: {elapsed:?}");
+ }
+ }
}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2026-10-21 11:52:15 +0000