new startHEADmaster

Now I tested and discussed with claude, and had a working version of
this project.  The rest is to port the claude version to my own
writings.  So this serves as the starting point before that attempt.

In the new attempt the design is better, and a number of bugs were
found and supposedly fixed, so let us see how this goes at the end.

1 files changed, 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:?}"),
+        }
+    }
+}