Fix some bugs

Some bugs are fixed:

1. If a non-terminal expansion can be reduced immediately, previously
an extra node would be created that had no parents.  Now this strange
behaviour is corrected.

2. When performing reductions, a leaf non-terminal node would
previously be regarded as completed.  Now we will first try to
complete that node, and then determine if the completion is
successful, and finally determine the completedness according to the
result.

Of course some more tests are still pending, before I can confirm that
no more bugs lurk around.

6 files changed, 186 insertions, 30 deletions

diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs
index e156178..6ae924f 100644
--- a/chain/src/atom/default.rs
+++ b/chain/src/atom/default.rs
@@ -123,7 +123,7 @@ impl DefaultAtom {
             .accepting_vec
             .iter()
             .enumerate()
-            .filter_map(|(index, pred)| (*pred).then(|| index))
+            .filter_map(|(index, pred)| (*pred).then_some(index))
         {
             print!("{nullable}, ");
         }
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 5f83115..618e560 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -594,13 +594,10 @@ impl Chain for DefaultChain {
             && 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)?;
-                    }
+            if let Ok(Some(label)) = self.forest.vertex_label(1) {
+                if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) {
+                    self.forest.remove_node(1)?;
                 }
-                _ => {}
             }
         }
 
@@ -1189,7 +1186,7 @@ mod test_chain {
 
         let no_item = false;
 
-        let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 0, 1, 4, 2, 2, 1];
+        let input: &[usize] = &[3, 0, 2, 1, 1, 0, 1, 4, 0, 2, 1];
 
         let input_len = input.len();
 
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index b84d4ea..de43f37 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -965,7 +965,8 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
             return Ok(node);
         }
 
-        fragment.set_root(1)?;
+        // fragment.set_root(1)?;
+        fragment.remove_prefix(1)?;
 
         let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
 
@@ -1056,6 +1057,45 @@ impl<T: GraphLabel> DefaultForest<T> {
         Self { graph, root }
     }
 
+    /// Remove a prefix of the fragment.
+    ///
+    /// The new forest will have root set to 0, unless the entire
+    /// forest is removed.
+    pub fn remove_prefix(&mut self, prefix_len: usize) -> Result<(), Error> {
+        let nodes_len = self.nodes_len();
+
+        if prefix_len >= nodes_len {
+            self.graph = Default::default();
+            self.root = None;
+
+            return Ok(());
+        }
+
+        let mut new_graph = Default::default();
+        let mut new_builder = PLGBuilderMut::from_graph_mut(&mut new_graph);
+
+        let dummy_label = self.vertex_label(0)?.ok_or(Error::NodeNoLabel(0))?;
+
+        for i in prefix_len..nodes_len {
+            let label = self.vertex_label(i)?.ok_or(Error::NodeNoLabel(i))?;
+
+            new_builder.add_vertex(label);
+        }
+
+        for (i, j) in self.edges() {
+            if i < prefix_len || j < prefix_len {
+                continue;
+            }
+
+            new_builder.add_edge(i - prefix_len, j - prefix_len, dummy_label)?;
+        }
+
+        self.graph = new_graph;
+        self.root = Some(0);
+
+        Ok(())
+    }
+
     /// Set the root to the given node.
     pub fn set_root(&mut self, root: usize) -> Result<(), Error> {
         if root >= self.nodes_len() {
@@ -1173,14 +1213,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
     /// Set the position of every node.
     ///
-    /// If ALLP is non-nil or if the node is a terminal node, also set
+    /// If ALLP is `true` or if the node is a terminal node, also set
     /// the ending position whereever reasonable.
+    ///
+    /// If ALLP is `false` , always return `true`.  Otherwise return
+    /// `true` if and only if the root is set to closed.  If the
+    /// forest is empty, this returns `false`.
     pub(crate) fn set_pos(
         &mut self,
         atom: &DefaultAtom,
         pos: usize,
         allp: bool,
-    ) -> Result<(), Error> {
+    ) -> Result<bool, Error> {
         let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
         let nodes_len = builder.nodes_len();
@@ -1200,7 +1244,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 builder.set_label(node, new_label)?;
             }
 
-            return Ok(());
+            return Ok(true);
         }
 
         // We assign every node to be open first, and then start from
@@ -1267,7 +1311,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             builder.set_label(node, new_label)?;
         }
 
-        Ok(())
+        let root = if let Some(root) = self.root() {
+            root
+        } else {
+            return Ok(false);
+        };
+
+        let result = closed_nodes
+            .get(root)
+            .copied()
+            .ok_or(Error::IndexOutOfBounds(root, nodes_len))?;
+
+        Ok(result)
     }
 }
 
@@ -1559,6 +1614,40 @@ mod item_test {
     }
 
     #[test]
+    fn test_remove_prefix() -> Result<(), Box<dyn std::error::Error>> {
+        let mut forest = leaf!(0, usize);
+
+        forest.plant(0, leaf!(1), false)?;
+        forest.plant(1, leaf!(2), false)?;
+        forest.plant(2, leaf!(3), false)?;
+        forest.plant(3, leaf!(4), false)?;
+        forest.plant(4, leaf!(5), false)?;
+
+        forest.remove_prefix(2)?;
+
+        dbg!(&forest);
+
+        assert_eq!(forest.nodes_len(), 4);
+        assert_eq!(forest.root(), Some(0));
+
+        for i in 0..4 {
+            assert!(matches!(forest.vertex_label(i),
+                             Ok(Some(label)) if
+                             label == ForestLabel::new(i + 2, ForestLabelType::Plain)));
+
+            for j in 0..4 {
+                if i + 1 == j {
+                    assert!(matches!(forest.has_edge(i, j), Ok(true)));
+                } else {
+                    assert!(matches!(forest.has_edge(i, j), Ok(false)));
+                }
+            }
+        }
+
+        Ok(())
+    }
+
+    #[test]
     fn test_eq() -> Result<(), Box<dyn std::error::Error>> {
         let mut forest = leaf!(0, usize);
 
@@ -1598,6 +1687,25 @@ mod item_test {
 
         atom.print_nullables();
 
+        let non_nullable: usize = {
+            let mut result = 0usize;
+
+            for i in 0..(atom.total()) {
+                if !atom.is_accepting(2 * i + 1)? {
+                    result = i;
+                    break;
+                }
+            }
+
+            if result != 0 {
+                result
+            } else {
+                panic!("grammar has no non-nullable position?");
+            }
+        };
+
+        println!("the chosen non-nullable is {non_nullable}");
+
         let mut forest: DefaultForest<ForestLabel<GrammarLabel>> = DefaultForest::new_leaf_raw(
             ForestLabel::new(GrammarLabel::new(TNT::Non(0), 0), ForestLabelType::Plain),
         );
@@ -1623,7 +1731,7 @@ mod item_test {
         forest.plant(
             2,
             DefaultForest::new_leaf_raw(ForestLabel::new(
-                GrammarLabel::new(104, 0),
+                GrammarLabel::new(non_nullable, 0),
                 ForestLabelType::Plain,
             )),
             false,
@@ -1658,7 +1766,7 @@ mod item_test {
 
         // forest.print_viz("test.gv")?;
 
-        forest.set_pos(&atom, 1, true)?;
+        assert!(!forest.set_pos(&atom, 1, true)?);
 
         // forest.print_viz("test set.gv")?;
 
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index 2ac3d73..9da156a 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -125,6 +125,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
         let new_label = self.create_new_label(node, end, edge_index, None)?;
 
+        // if node == 15 {
+        //     dbg!(end, new_label, node_label);
+        // }
+
         let new_label = match new_label {
             Eon::Nex(label) => label,
             Eon::Ex(existing) => {
@@ -374,7 +378,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     ///
     /// 1. Copy the old label.
     ///
-    /// 2. Set the end to `pos`.
+    /// 2. Set the end to `end`.
     ///
     /// 3. Pack the label.
     ///
@@ -412,9 +416,24 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
         copied_label.set_end_option(end);
 
-        let label = ForestLabel::new(copied_label, ForestLabelType::Packed);
+        let packed_label = ForestLabel::new(copied_label, ForestLabelType::Packed);
+        let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);
+
+        let root = if let Some(root) = self.root() {
+            root
+        } else {
+            return Ok(Eon::Nex(plain_label));
+        };
+
+        let packed_query = self.query_label(packed_label);
+
+        // We ignore nodes without parents which are not roots.
+        if matches!(packed_query, Some(packed) if packed == root ||
+                    self.parents_of(packed)?.len() > 0)
+        {
+            // this is safe because of the 'if' guard
+            let packed = packed_query.unwrap();
 
-        if let Some(packed) = self.query_label(label) {
             for child in self.children_of(packed)? {
                 let child_degree = self.degree(child)?;
 
@@ -457,9 +476,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             Ok(Eon::Nex(cloned_label))
         } else {
-            let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);
+            let plain_query = self.query_label(plain_label);
+
+            if matches!(plain_query, Some(plain) if plain == root ||
+                        self.parents_of(plain)?.len() > 0)
+            {
+                let existing = plain_query.unwrap();
 
-            if let Some(existing) = self.query_label(plain_label) {
                 let existing_degree = self.degree(existing)?;
 
                 if self.has_same_children(existing, node, existing_degree, edge_index + 1)? {
@@ -622,7 +645,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         for parent in parents {
             let mut parent_label = self
                 .vertex_label(parent)?
-                .ok_or_else(|| Error::NodeNoLabel(parent))?
+                .ok_or(Error::NodeNoLabel(parent))?
                 .label();
 
             #[cfg(debug_assertions)]
@@ -803,7 +826,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                     for rule_parent in rule_parents {
                         let mut rule_parent_label = self
                             .vertex_label(rule_parent)?
-                            .ok_or_else(|| Error::NodeNoLabel(rule_parent))?
+                            .ok_or(Error::NodeNoLabel(rule_parent))?
                             .label();
 
                         #[cfg(debug_assertions)]
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index bad0cfd..d5fb678 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -378,6 +378,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             let reduced = self.reduction(nth_child, pos, ter, atom.borrow(), false)?;
 
+            // dbg!(reduced, nth_child, self.is_empty_node(reduced)?);
+
             if reduced != nth_child && !self.is_empty_node(reduced)? {
                 parents.clear();
                 parents.extend(self.parents_of(reduced)?);
@@ -514,6 +516,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             if stack.is_empty() {
                 dbg!(
+                    is_empty_segment,
                     label,
                     atom_child,
                     parents,
@@ -698,12 +701,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                     Ok(nth_child)
                 }
             }
-            PaVi::Virtual(nt, t, mut node) => {
-                let node_label_start = self
+            PaVi::Virtual(nt, t, node) => {
+                let node_label = self
                     .vertex_label(node)?
                     .ok_or(Error::NodeNoLabel(node))?
-                    .label()
-                    .start();
+                    .label();
+
+                let node_label_start = node_label.start();
 
                 let reduction_fragment = atom.generate_virtual_frags(nt, t, None);
 
@@ -719,9 +723,16 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 for frag in reduction_fragment.into_iter().flatten() {
                     let mut frag = frag.clone();
 
-                    frag.set_pos(atom, node_label_start, true)?;
+                    let _root_closed_p = frag.set_pos(atom, node_label_start, true)?;
+
+                    // NOTE: If the root is closed, planting it might
+                    // affect the original node, but we shall not deal
+                    // with this phenomenon here.
+                    //
+                    // Instead, we will ignore the extra node at later
+                    // stages.
 
-                    node = self.plant_at_start(node, frag)?;
+                    self.plant_at_start(node, frag)?;
                 }
 
                 Ok(node)
diff --git a/chain/src/item/reduction.rs b/chain/src/item/reduction.rs
index 3c76c1e..512862a 100644
--- a/chain/src/item/reduction.rs
+++ b/chain/src/item/reduction.rs
@@ -139,6 +139,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     ) -> Result<usize, Error> {
         let mut result = node;
 
+        // if node == 15 && pos == 2 {
+        //     let _ = self.print_viz("pos really before splone.gv");
+        // }
+
         // step 1: Determine if this needs reductions.
 
         if !accept_root && self.root() == Some(node) {
@@ -346,10 +350,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                             panic!("a terminal node {top} has no ending position?");
                         }
                         Some(TNT::Non(nt)) => {
-                            correct_ends.insert(top, Correct);
-
                             self.close_pavi(atom.borrow(), PaVi::Virtual(nt, ter, top), pos)?;
 
+                            // dbg!(top, nt, ter, pos, self.degree(top)?, degree);
+
+                            let correctness = self.degree(top)? > 0;
+
+                            correct_ends.insert(top, correctness.into());
+
                             continue 'stack_loop;
                         }
                         None => {
@@ -404,6 +412,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         // NOTE: We must fix the order from top to bottom: this is the
         // reverse order of `order_of_correct_ends` .
 
+        // if node == 15 && pos == 2 {
+        //     dbg!(&order_of_correct_ends);
+        //     let _ = self.print_viz("pos before splone.gv");
+        // }
+
         for node in order_of_correct_ends.into_iter().rev() {
             let label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
             let degree = self.degree(node)?;
@@ -421,6 +434,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             let last_index = degree - 1;
 
+            // if node == 15 && pos == 2 {
+            //     let _ = self.print_viz("before splone.gv");
+            // }
+
             self.splone(node, Some(pos), last_index, false)?;
         }