Fix the bug of forgetting to check cloned nodes.

In the process of splitting, cloning, and planting the forest, I
forgot to check whether some cloned node of the node inquestion
satisfy the condition.  This used to cause forests that violate some
fundamental assumptions.  Now this is supposed to be fixed, but more
tests await us.

1 files changed, 93 insertions, 20 deletions

diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index c9d9c5a..09fca0b 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -209,30 +209,17 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         }
 
         let node_end = node_label.label().end();
-        let node_degree = self.degree(node)?;
 
         // We can check the end to know whether the new label is equal
         // to the old label.
         if node_end.is_none() {
-            if node_degree == edge_index + 2 {
-                let last_child = self.nth_child(node, node_degree - 1)?;
-
-                if self.is_prefix(last_child, fragment.borrow())? {
-                    return Ok(node);
-                }
-            }
-
-            if node_degree <= edge_index + 1 {
-                self.plant(node, fragment, planted)?;
+            if let Some(node_to_plant) = self.find_node_to_plant(fragment, node, edge_index)? {
+                self.plant(node_to_plant, fragment, planted)?;
 
+                return Ok(node_to_plant);
+            } else {
                 return Ok(node);
             }
-
-            let cloned = self.clone_node(node, edge_index + 1, false)?;
-
-            self.plant(cloned, fragment, planted)?;
-
-            return Ok(cloned);
         }
 
         let new_label = self.create_new_label(node, None, edge_index, Some((fragment, planted)))?;
@@ -516,11 +503,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 if let Some((fragment, _planted)) = fragment {
                     let modified_degree = std::cmp::max(child_degree, 1) - 1;
 
-                    dbg!(node, end, edge_index, modified_degree);
+                    // dbg!(node, end, edge_index, modified_degree);
 
-                    dbg!(child, child_degree);
+                    // dbg!(child, child_degree);
 
-                    dbg!(&fragment);
+                    // dbg!(&fragment);
 
                     if self.has_same_children(child, node, modified_degree, edge_index + 1)?
                         && child_degree != 0
@@ -588,6 +575,92 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         }
     }
 
+    /// Determine if the `fragment` should be planted anew.  If so, return
+    /// a node to plant.
+    ///
+    /// Precisely speaking, if `node` has the fragment planted at the
+    /// position `edge_index` + 1, then there is no need to plant.  If
+    /// not, but if `edge_index` + 1 is equal to the degree of `node`,
+    /// then we can directly plant under `node`.
+    ///
+    /// Moreover, if `node` is cloned, then do the same check for each of
+    /// its clones.
+    ///
+    /// # Assumption
+    ///
+    /// This function assumes the node is open-ended.
+    fn find_node_to_plant(
+        &mut self,
+        fragment: &DefaultForest<ForestLabel<GrammarLabel>>,
+        node: usize,
+        edge_index: usize,
+    ) -> Result<Option<usize>, Error> {
+        let mut node = node;
+
+        let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
+
+        if node_label.is_packed() {
+            dbg!("split pack: {node}");
+
+            return Err(Error::SplitPack(node));
+        }
+
+        if node_label.clone_index().is_some() {
+            let mut parents = self.parents_of(node)?;
+
+            #[cfg(debug_assertions)]
+            assert_eq!(parents.len(), 1, "Assumption fails");
+
+            let packed = parents.next().unwrap().node();
+
+            for clone in self.children_of(packed)? {
+                let degree = self.degree(clone)?;
+
+                if degree == 0 {
+                    return Ok(Some(clone));
+                }
+
+                if degree >= edge_index + 2 {
+                    let index_child = self.nth_child(clone, edge_index + 1)?;
+
+                    if self.is_prefix(index_child, fragment.borrow())? {
+                        return Ok(None);
+                    }
+                }
+
+                if degree == edge_index + 1 {
+                    return Ok(Some(clone));
+                }
+            }
+
+            node = self.clone_node(node, edge_index + 1, false)?;
+
+            return Ok(Some(node));
+        }
+
+        let degree = self.degree(node)?;
+
+        if degree == 0 {
+            return Ok(Some(node));
+        }
+
+        if degree >= edge_index + 2 {
+            let index_child = self.nth_child(node, edge_index + 1)?;
+
+            if self.is_prefix(index_child, fragment.borrow())? {
+                return Ok(None);
+            }
+        }
+
+        if degree == edge_index + 1 {
+            return Ok(Some(node));
+        }
+
+        node = self.clone_node(node, edge_index + 1, false)?;
+
+        Ok(Some(node))
+    }
+
     /// Compare if two nodes have the same children in the same order.
     fn has_same_children(
         &self,