aboutsummaryrefslogtreecommitdiff
path: root/tests/spike.rs
diff options
context:
space:
mode:
Diffstat (limited to 'tests/spike.rs')
-rw-r--r--tests/spike.rs279
1 files changed, 279 insertions, 0 deletions
diff --git a/tests/spike.rs b/tests/spike.rs
new file mode 100644
index 0000000..69fbf38
--- /dev/null
+++ b/tests/spike.rs
@@ -0,0 +1,279 @@
+//! Step 1 spike (written by Claude Code): dump the raw forest layout
+//! for `S -> S S | a` on `aaa`, to learn how nodes, packed nodes,
+//! clones and rule nodes are laid out. This is exploratory; it only
+//! prints, and asserts nothing about the forest's shape.
+
+use chain::atom::DefaultAtom;
+use chain::default::DefaultChain;
+use chain::Chain;
+use forest::Forest;
+use graph::{Graph, LabelGraph, ParentsGraph};
+use grammar::test_grammar_helper::scan_tnt;
+use grammar::{Grammar, Nonterminal, Rule, Terminal, TNT};
+use nfa::default::regex::DefaultRegParser;
+use nfa::DesRec;
+
+/// The parser's debug dumps (`print_viz`) write to `output/...`
+/// relative to the current directory. Run from a temp directory so
+/// that they neither fail nor litter the source tree.
+fn init() {
+ static INIT: std::sync::Once = std::sync::Once::new();
+
+ INIT.call_once(|| {
+ let dir = std::env::temp_dir().join("rep-tests");
+ std::fs::create_dir_all(dir.join("output")).unwrap();
+ std::env::set_current_dir(dir).unwrap();
+ });
+}
+
+/// Build a grammar from terminal names, nonterminal names (the first
+/// one is the start symbol) and one rule string per nonterminal, in
+/// the `T<name>` / `N<name>` notation of `scan_tnt`.
+fn make_grammar(ters: &[&str], nons: &[&str], rules: &[&str]) -> Grammar {
+ let mut parser: DefaultRegParser<TNT> = Default::default();
+
+ for t in ters {
+ parser.add_tnt(t, true);
+ }
+ for n in nons {
+ parser.add_tnt(n, false);
+ }
+
+ let rules = rules
+ .iter()
+ .map(|r| {
+ Rule::new(
+ parser
+ .parse(r, Box::new(scan_tnt), true)
+ .unwrap()
+ .unwrap()
+ .0,
+ )
+ })
+ .collect();
+
+ Grammar::new(
+ ters.iter().map(|t| Terminal::new((*t).to_owned())).collect(),
+ nons.iter().map(|n| Nonterminal::new((*n).to_owned())).collect(),
+ rules,
+ )
+}
+
+/// Find at which token the chain first fails, for `S -> S S | a` on
+/// `a^n`.
+#[test]
+fn locate_failure_case1() {
+ init();
+
+ for n in 1..=4usize {
+ let grammar = make_grammar(&["a"], &["S"], &["NS NS | Ta"]);
+ let atom = DefaultAtom::from_grammar(grammar).unwrap();
+ let mut chain = DefaultChain::unit(atom).unwrap();
+
+ let mut outcome = String::from("all tokens consumed");
+
+ for pos in 0..n {
+ if let Err(e) = chain.chain(0, pos, false) {
+ outcome = format!("chain() failed at pos {pos}: {e:?}");
+ break;
+ }
+ }
+
+ eprintln!("RESULT n={n}: {outcome}");
+ }
+}
+
+/// Sanity check of the harness: unambiguous grammars (layer 1) should
+/// get through `chain()` for every prefix of `a^4`.
+#[test]
+fn layer1_sanity() {
+ init();
+
+ let cases: [(&str, &str); 3] = [
+ ("S -> a S | a", "Ta NS | Ta"),
+ ("S -> S a | a", "NS Ta | Ta"),
+ ("S -> a a", "Ta Ta"),
+ ];
+
+ for (name, rule) in cases {
+ for n in 1..=4usize {
+ let grammar = make_grammar(&["a"], &["S"], &[rule]);
+ let atom = DefaultAtom::from_grammar(grammar).unwrap();
+ let mut chain = DefaultChain::unit(atom).unwrap();
+
+ let mut outcome = String::from("ok");
+
+ for pos in 0..n {
+ if let Err(e) = chain.chain(0, pos, false) {
+ outcome = format!("chain() failed at pos {pos}: {e:?}");
+ break;
+ }
+ }
+
+ eprintln!("LAYER1 {name}, n={n}: {outcome}");
+ }
+ }
+}
+
+/// Same failing inputs, but with forest building off (`no_item =
+/// true`): does recognition alone get through?
+#[test]
+fn recognition_only() {
+ init();
+
+ for (name, rule) in [("S -> S S | a", "NS NS | Ta"), ("S -> S a | a", "NS Ta | Ta")] {
+ for n in 1..=4usize {
+ let grammar = make_grammar(&["a"], &["S"], &[rule]);
+ let atom = DefaultAtom::from_grammar(grammar).unwrap();
+ let mut chain = DefaultChain::unit(atom).unwrap();
+
+ let mut outcome = String::from("ok");
+
+ for pos in 0..n {
+ if let Err(e) = chain.chain(0, pos, true) {
+ outcome = format!("chain() failed at pos {pos}: {e:?}");
+ break;
+ }
+ }
+
+ let accepted = chain.epsilon().unwrap();
+
+ eprintln!("RECOG {name}, n={n}: {outcome}, accepted={accepted}");
+ }
+ }
+}
+
+/// Probe the atom of `S -> S a | a`: which (nt=0, t=0, target) have
+/// virtual traces, and what the NFA looks like.
+#[test]
+fn probe_atom_left_recursion() {
+ use chain::atom::Atom;
+
+ init();
+
+ let grammar = make_grammar(&["a"], &["S"], &["NS Ta | Ta"]);
+ let atom = DefaultAtom::from_grammar(grammar).unwrap();
+
+ eprintln!("PROBE grammar:\n{}", &*atom);
+ eprintln!("PROBE virtual node (S, a) = {:?}", atom.atom(0, 0));
+ eprintln!("PROBE accepting_len = {}", atom.accepting_len());
+ atom.print_virtual();
+
+ {
+ use graph::LabelGraph;
+
+ let non_start = atom.nth_accumulator(0).unwrap() * 2;
+
+ eprintln!("PROBE non_start = {non_start}");
+
+ for (label, children) in atom.labels_of(non_start).unwrap() {
+ for child in children {
+ eprintln!(
+ "PROBE edge from non_start labelled {label:?} to {child}: \
+ query_expansion = {:?}",
+ atom.query_expansion(non_start, child)
+ );
+ }
+ }
+ }
+
+ {
+ use graph::LabelGraph;
+
+ for node in [5usize, 7, 9, 14] {
+ for (label, children) in atom.labels_of(node).unwrap() {
+ eprintln!(
+ "PROBE edges of node {node}: {label:?} -> {:?}, reduction to first = {:?}",
+ children.clone().collect::<Vec<_>>(),
+ children
+ .clone()
+ .map(|c| atom.query_reduction(node, c).ok().flatten().map(|s| s.to_vec()))
+ .collect::<Vec<_>>()
+ );
+ }
+ }
+ }
+
+ for pos in 0..8 {
+ eprintln!("PROBE rule_pos {pos}: {:?}", atom.rule_pos_to_string(pos));
+ }
+
+ for target in 0..atom.accepting_len() {
+ let rules: Option<Vec<usize>> = atom.trace(0, 0, target).map(|i| i.collect());
+ eprintln!("PROBE trace(S, a, target {target}) = {rules:?}");
+ }
+}
+
+/// Dump the working forest after each token, for `S -> S a | a`.
+#[test]
+fn forest_after_each_token() {
+ init();
+
+ let grammar = make_grammar(&["a"], &["S"], &["NS Ta | Ta"]);
+ let atom = DefaultAtom::from_grammar(grammar).unwrap();
+ let mut chain = DefaultChain::unit(atom).unwrap();
+
+ let dump = |chain: &DefaultChain, title: &str| {
+ let forest = chain.forest();
+
+ eprintln!("FOREST {title}: root={:?}", forest.root());
+
+ for node in forest.nodes() {
+ let l = forest.vertex_label(node).unwrap();
+ eprintln!(
+ "FOREST node {node}: {:?} parents={:?} children={:?}",
+ l.map(|l| (l.status(), l.label().label(), l.label().start(), l.label().end())),
+ forest.parents_of(node).map(|i| i.collect::<Vec<_>>()),
+ forest.children_of(node).map(|i| i.collect::<Vec<_>>())
+ );
+ }
+ };
+
+ dump(&chain, "initial");
+
+ for pos in 0..2usize {
+ let r = chain.chain(0, pos, false);
+ dump(&chain, &format!("after token {pos}, result {r:?}"));
+ }
+}
+
+#[test]
+fn dump_case1() {
+ init();
+
+ let grammar = make_grammar(&["a"], &["S"], &["NS NS | Ta"]);
+
+ let atom = DefaultAtom::from_grammar(grammar).unwrap();
+ let mut chain = DefaultChain::unit(atom).unwrap();
+
+ let toks = [0usize, 0, 0];
+
+ for (pos, t) in toks.iter().copied().enumerate() {
+ chain.chain(t, pos, false).unwrap();
+ }
+
+ assert!(chain.epsilon().unwrap());
+
+ let forest = chain
+ .end_of_input(toks.len(), *toks.last().unwrap())
+ .unwrap();
+
+ println!("=== FOREST DUMP ===");
+ println!("root = {:?}", forest.root());
+
+ for node in forest.nodes() {
+ let label = forest.vertex_label(node).unwrap();
+ let children: Vec<usize> = forest.children_of(node).unwrap().collect();
+
+ match label {
+ Some(l) => println!(
+ "node {node}: status={:?} label={:?} start={} end={:?} children={children:?}",
+ l.status(),
+ l.label().label(),
+ l.label().start(),
+ l.label().end(),
+ ),
+ None => println!("node {node}: no label, children={children:?}"),
+ }
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2026-10-21 10:44:08 +0000