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.

1 files changed, 115 insertions, 7 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")?;