chain/default: Remove the annoying node whenever plausible.

The chain-rule machine needs a place-holder node at the beginning.
But afterwards that node is pure annoyance and disturbs the
functioning of the machine.  Consequently I removed that node whenever
the right time comes.

This seems to fix some other bugs.  It is reasonable: the presence of
that bogus node is just noise to the machine and error-prone.

1 files changed, 119 insertions, 9 deletions

diff --git a/chain/src/default.rs b/chain/src/default.rs
index 2f6311c..97dbfa3 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -365,7 +365,7 @@ impl Chain for DefaultChain {
 
         let initial_nullable = atom
             .is_nullable(START_NONTERMINAL)
-            .map_err(|_| Error::IndexOutOfBounds(0, atom.non_num()))?;
+            .map_err(|_| Error::IndexOutOfBounds(START_NONTERMINAL, atom.non_num()))?;
 
         builder.add_edge(
             first,
@@ -569,6 +569,21 @@ impl Chain for DefaultChain {
             Ok(accepting)
         }
 
+        if !no_item
+            && self.forest.nodes_len() > 2
+            && matches!(self.forest.degree(1), Ok(d) if d > 0)
+        {
+            // dbg!(self.forest.vertex_label(1)?, self.atom.empty());
+            match self.forest.vertex_label(1) {
+                Ok(Some(label)) => {
+                    if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) {
+                        self.forest.remove_node(1)?;
+                    }
+                }
+                _ => {}
+            }
+        }
+
         let mut der_iter = DerIter::default();
 
         let mut accepting_pavi: HashSet<PaVi> = HashSet::new();
@@ -813,9 +828,91 @@ impl Chain for DefaultChain {
 
         dbg!(root_degree, root_label);
 
+        // First perform reduction.
+
+        let _ = self.forest.print_viz("forest before reduction.gv");
+
+        // self.forest.reduction(root, pos, ter, &self.atom, true)?;
+
         // REVIEW: Why nodes?
         let mut nodes = Vec::with_capacity(root_degree);
 
+        // let nodes_len = self.forest.nodes_len();
+
+        // let mut stack: Vec<(usize, ForestLabel<GrammarLabel>)> = Vec::with_capacity(nodes_len);
+        // let mut visited: Vec<_> = std::iter::repeat(false).take(nodes_len).collect();
+
+        // macro_rules! visited {
+        //     ($node: expr) => {
+        //         visited.get($node).copied() == Some(true)
+        //     };
+        // }
+
+        // macro_rules! visit {
+        //     ($node: expr) => {
+        //         *visited
+        //             .get_mut($node)
+        //             .ok_or(Error::IndexOutOfBounds($node, nodes_len))? = true;
+        //     };
+        // }
+
+        // stack.push((root, root_label));
+
+        // while let Some((top, top_label)) = stack.pop() {
+        //     if top_label.is_packed() {
+        //         visit!(top);
+
+        //         for clone in self.forest.children_of(top)? {
+        //             let cloned_label = self
+        //                 .forest
+        //                 .vertex_label(clone)?
+        //                 .ok_or(Error::NodeNoLabel(clone))?;
+        //             stack.push((clone, cloned_label));
+        //         }
+        //     } else if top_label.clone_index().is_some() {
+        //         let visited = visited!(top);
+
+        //         if visited {
+        //             // every child should have been processed
+
+        //             if top_label.label().end().is_some() {
+        //                 continue;
+        //             }
+
+        //             for child in self.forest.children_of(top)? {
+        //                 let child_label = self
+        //                     .forest
+        //                     .vertex_label(child)?
+        //                     .ok_or(Error::NodeNoLabel(child))?;
+
+        //                 if child_label.label().end().is_none() {
+        //                     continue;
+        //                 }
+        //             }
+
+        //         } else {
+        //             visit!(top);
+
+        //             stack.push((top, top_label));
+
+        //             for child in self.forest.children_of(top)? {
+        //                 if visited!(child) {
+        //                     continue;
+        //                 }
+
+        //                 let child_label = self
+        //                     .forest
+        //                     .vertex_label(child)?
+        //                     .ok_or(Error::NodeNoLabel(child))?;
+
+        //                 stack.push((child, child_label));
+        //             }
+        //         }
+        //     } else {
+        //         //
+        //     }
+        // }
+
         if root_label.is_packed() {
             let mut all_completed_clones = Vec::with_capacity(root_degree);
 
@@ -884,11 +981,15 @@ impl Chain for DefaultChain {
             nodes.push(self.forest.reduction(root, pos, ter, &self.atom, true)?);
         }
 
-        dbg!(&nodes);
+        // dbg!(&nodes);
 
-        // self.forest
-        //     .print_viz("forest before extraction.gv")
-        //     .unwrap();
+        println!("printing grammar");
+        println!("{}", &(*self.atom));
+        self.atom.print_nullables();
+        self.atom.print_virtual();
+        let _ = item::default::print_labels(&self.atom, &self.forest);
+
+        let _ = self.forest.print_viz("forest before extraction.gv");
 
         result = self.forest.extract(pos)?;
 
@@ -1066,11 +1167,14 @@ mod test_chain {
 
         let no_item = false;
 
-        let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 1, 0, 1];
+        let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 0, 1, 4, 2, 2, 1];
+
+        let input_len = input.len();
 
-        let to_print = std::fs::metadata("output/").is_ok();
+        // let to_print = std::fs::metadata("output/").is_ok();
+        let to_print = false;
 
-        for (pos, t) in input.iter().copied().enumerate().take(2) {
+        for (pos, t) in input.iter().copied().enumerate().take(input_len) {
             chain.chain(t, pos, no_item)?;
             if to_print {
                 chain.forest().print_viz(&format!("forest {pos}.gv"))?;
@@ -1078,7 +1182,13 @@ mod test_chain {
             dbg!(pos, t);
         }
 
-        item::default::print_labels(&chain.atom, &chain.forest)?;
+        // let _ = chain.forest.print_viz("forest before extraction.gv");
+
+        let extracted = chain.end_of_input(input_len, input[input_len - 1])?;
+
+        let _ = extracted.print_viz("extracted forest.gv");
+
+        // item::default::print_labels(&chain.atom, &chain.forest)?;
 
         Ok(())
     }