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.

2 files changed, 145 insertions, 14 deletions

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)]