Fix the bug of testing prefixes and planting

Previously the functions `is_prefix` and `plant` did not take the
situation of packed nodes into considerations.  That was because I
only dealt with non-packed nodes in the past: the fragment to test for
prefixes and for planting did not intersect the packed nodes in the
forest, and the grammar is so simple that the fragments do not contain
packed nodes.

Then a test revealed this situation, so I have to fix this lack of
considerations now.  This commit attempts to fix this issue.

From the newly added unit-tests, it seems that this fix works.  :)

3 files changed, 759 insertions, 133 deletions

diff --git a/chain/src/archive.txt b/chain/src/archive.txt
index 7bd6f31..79fe6d8 100644
--- a/chain/src/archive.txt
+++ b/chain/src/archive.txt
@@ -540,3 +540,101 @@
 // 
 //     Ok(None)
 // }
+
+// let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+// // Just a dummy label for use in adding edges.
+// //
+// // REVIEW: I probably should refactor the API for builder_mut.
+// let root_label = fragment
+//     .vertex_label(root)?
+//     .ok_or(Error::NodeNoLabel(root))?;
+
+// let nodes_len = fragment.nodes_len();
+
+// /// If the fragment root has a duplicate label, the forest
+// /// will not grow, so we use the label to find the adjoined
+// /// node index.
+// ///
+// /// The nodes hava already been added to the forest, so it is
+// /// safe to call unwrap.
+// macro_rules! conversion (
+//     ($node:expr) => {
+//         {
+//             builder
+//                 .query_label(
+//                     fragment
+//                         .vertex_label($node)?
+//                         .ok_or(Error::NodeNoLabel($node))?
+//                 ).unwrap()
+//         }
+//     }
+// );
+
+// // If the fragment has been planted before, we just add an
+// // edge.
+
+// if planted {
+//     builder.add_edge(node_id, conversion!(root), root_label)?;
+
+//     return Ok(());
+// }
+
+// // First adjoin the relevant nodes and join the edges later.
+
+// let mut used_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();
+
+// let mut stack = vec![root];
+
+// while let Some(top) = stack.pop() {
+//     if used_nodes.get(top).copied() == Some(true) {
+//         continue;
+//     }
+
+//     *used_nodes
+//         .get_mut(top)
+//         .ok_or(Error::IndexOutOfBounds(top, nodes_len))? = true;
+
+//     stack.extend(fragment.children_of(top)?);
+// }
+
+// let used_nodes = used_nodes;
+
+// for node in (0..nodes_len).filter(|node| used_nodes.get(*node).copied() == Some(true)) {
+//     let label = fragment
+//         .vertex_label(node)?
+//         .ok_or(Error::NodeNoLabel(node))?;
+
+//     builder.add_vertex(label);
+// }
+
+// // Don't forget to join the new sub-forest to the original
+// // forest, at the specified position.
+
+// builder.add_edge(node_id, conversion!(root), root_label)?;
+
+// // We can try to calculate the depth of fragments, if we need
+// // to lower the memory usage.  But in our use cases, we
+// // usually deal with fragments where each node has at most one
+// // child, so the depth is supposed to be equal to the length
+// // in this case.
+// let mut stack = Vec::with_capacity(fragment.nodes_len());
+
+// stack.push(root);
+
+// let mut seen_nodes = std::collections::HashSet::<usize>::new();
+
+// while let Some(top) = stack.pop() {
+//     seen_nodes.insert(top);
+
+//     for child in fragment.children_of(top)? {
+//         builder.add_edge(conversion!(top), conversion!(child), root_label)?;
+
+//         if !seen_nodes.contains(&child) {
+//             seen_nodes.insert(child);
+//             stack.push(child);
+//         }
+//     }
+// }
+
+// Ok(())
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 28bdbee..7b0a843 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -10,8 +10,6 @@ use graph::{
 
 use graph_macro::Graph;
 
-use std::collections::HashSet;
-
 use std::fmt::Display;
 
 /// The type of errors for forest operations.
@@ -216,29 +214,9 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
             return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
         }
 
-        // FIXME: We should take the presence of packed nodes into
-        // consideration.  That is, the fragment might have already
-        // been planted and packed, and we need to account for such
-        // possibilities.
-        //
-        // Moreover, the fragments might also contain packed nodes, in
-        // which case we need to check these multiple possibilities
-        // are properly contained.
-
-        // We do a depth-first traversal to determine if every node
-        // encountered has the same set of children (labels taken into
-        // the consideration).
-
         let fragment = fragment.borrow();
         let fragment_nodes_len = fragment.nodes_len();
 
-        let mut frag_stack = Vec::with_capacity(fragment_nodes_len);
-
-        let mut self_stack = Vec::with_capacity(fragment_nodes_len);
-
-        let mut frag_seen: HashSet<usize> = HashSet::with_capacity(fragment_nodes_len);
-        let mut self_seen: HashSet<usize> = HashSet::with_capacity(fragment_nodes_len);
-
         let frag_root = if let Some(root) = fragment.root() {
             root
         } else {
@@ -246,72 +224,181 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
             return Ok(true);
         };
 
-        frag_stack.push(frag_root);
-        self_stack.push(node_id);
+        // We assign to each node in the fragment the node id in the
+        // forest that has a label that corresponds to the label of
+        // the node.  One thing to note is that a plain node can also
+        // correspond to a packed node, but a packed node cannot
+        // correspond to a plain node.  Denote this correspondence as
+        // A -> f(A).
+        //
+        // After this, we need to check, for each edge from A to B, if
+        // f(A) has an edge to f(B).  But there are some caveats: if A
+        // is a packed node and B is a cloned node, we check nothing.
+        // And if f(A) is a packed node, we check every of its cloned
+        // children to see if it has an edge to f(B).  Finally, we
+        // evaluate the fragment as a boolean expression, where the
+        // only operation is multiplication and the final value is the
+        // return value of the function.
+        //
+        // I have a marvelous proof that this algorithm works, but my
+        // computer does not have enough memory to contain this proof.
+        // See
+        // <https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem#Fermat's_conjecture>.
 
-        // defer popping
-        while let (Some(frag_top), Some(self_top)) =
-            (frag_stack.last().copied(), self_stack.last().copied())
-        {
-            frag_seen.insert(frag_top);
-            self_seen.insert(self_top);
+        // The vector of correspondance `f`.
+        let mut correspondance: Vec<usize> =
+            std::iter::repeat(0).take(fragment_nodes_len).collect();
 
-            frag_stack.pop();
-            self_stack.pop();
+        for (node, cor_mut) in (0..fragment_nodes_len).zip(correspondance.iter_mut()) {
+            let frag_label = fragment
+                .vertex_label(node)?
+                .ok_or(Error::NodeNoLabel(node))?
+                .label();
 
-            // NOTE: The labels might defer by the status.  We test
-            // for the equalities of inner labels only.
+            let packed_label = ForestLabel::new(frag_label, ForestLabelType::Packed);
+            let plain_label = ForestLabel::new(frag_label, ForestLabelType::Plain);
 
-            if fragment.vertex_label(frag_top)?.map(|label| label.label())
-                != self.vertex_label(self_top)?.map(|label| label.label())
-            {
-                // not a prefix
-                // dbg!(
-                //     frag_top,
-                //     self_top,
-                //     fragment.vertex_label(frag_top)?,
-                //     self.vertex_label(self_top)?
-                // );
+            if let Some(packed_pos) = self.query_label(packed_label) {
+                *cor_mut = packed_pos;
+            } else if let Some(plain_pos) = self.query_label(plain_label) {
+                *cor_mut = plain_pos;
+            } else {
                 return Ok(false);
             }
+        }
 
-            let self_children = self.children_of(self_top)?;
-            let frag_children = fragment.children_of(frag_top)?;
+        let correspondance = correspondance;
 
-            if frag_children.len() > self_children.len() {
-                // dbg!(
-                //     frag_top,
-                //     self_top,
-                //     fragment.vertex_label(frag_top)?,
-                //     self.vertex_label(self_top)?
-                // );
-                return Ok(false);
+        let f_root = correspondance
+            .get(frag_root)
+            .copied()
+            .ok_or(Error::IndexOutOfBounds(frag_root, correspondance.len()))?;
+
+        if f_root != node_id {
+            return Ok(false);
+        }
+
+        'node_loop: for (node, f_node) in
+            (0..fragment_nodes_len).zip(correspondance.iter().copied())
+        {
+            let node_label = fragment
+                .vertex_label(node)?
+                .ok_or(Error::NodeNoLabel(node))?;
+            let node_degree = fragment.degree(node)?;
+
+            let f_label = self
+                .vertex_label(f_node)?
+                .ok_or(Error::NodeNoLabel(f_node))?;
+
+            if node_label.is_packed() {
+                let value = f_label.is_packed() && self.degree(f_node)? >= node_degree;
+
+                if !value {
+                    return Ok(false);
+                }
+
+                continue 'node_loop;
             }
 
-            for (frag_child, self_child) in frag_children.zip(self_children) {
-                if frag_seen.contains(&frag_child) && self_seen.contains(&self_child) {
-                    continue;
-                } else if frag_seen.contains(&frag_child) || self_seen.contains(&self_child) {
-                    // dbg!();
+            if f_label.is_packed() {
+                let mut value = false;
+
+                'f_children_loop: for f_node_child in self.children_of(f_node)? {
+                    if self.degree(f_node_child)? < node_degree {
+                        continue 'f_children_loop;
+                    }
+
+                    for (child, f_node_child_child) in fragment
+                        .children_of(node)?
+                        .zip(self.children_of(f_node_child)?)
+                    {
+                        let f_child = correspondance
+                            .get(child)
+                            .copied()
+                            .ok_or(Error::IndexOutOfBounds(child, correspondance.len()))?;
+
+                        if f_node_child_child != f_child {
+                            continue 'f_children_loop;
+                        }
+                    }
+
+                    value = true;
+
+                    break 'f_children_loop;
+                }
+
+                if !value {
                     return Ok(false);
                 }
 
-                frag_stack.push(frag_child);
-                self_stack.push(self_child);
+                continue 'node_loop;
+            }
+
+            if self.degree(f_node)? < node_degree {
+                return Ok(false);
+            }
+
+            for (child, f_node_child) in fragment.children_of(node)?.zip(self.children_of(f_node)?)
+            {
+                let f_child = correspondance
+                    .get(child)
+                    .copied()
+                    .ok_or(Error::IndexOutOfBounds(child, correspondance.len()))?;
+
+                if f_node_child != f_child {
+                    return Ok(false);
+                }
             }
         }
 
-        // Check both stacks are empty at the end.
-        Ok(frag_stack.is_empty() && self_stack.is_empty())
+        Ok(true)
     }
 
     fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
     where
         F: Borrow<Self>,
     {
-        // Convert self to a builder_mut, and traverse fragment in a
-        // depth-first manner and adjoin corresponding nodes along the
-        // way.
+        // As in the method `is_prefix`, we assign a node id of self
+        // to a node in the fragment.  Here a plain node can
+        // correspond to a packed node, and a packed node can also
+        // correspond to a plain node.  The only restriction is that
+        // if there is a packed node in the self forest, then it must
+        // be corresponded, rather than the plain node with the same
+        // inner label.  One thing to note is that this correspondance
+        // is not fixed during the execution of the function.
+        // Instead, the planting of the function will change the
+        // status of nodes.  And if the fragment contains nodes that
+        // share children, then the status of nodes need to be
+        // synchronized after each change.
+        //
+        // Another way is to give up calculating the status
+        // beforehand.  Rather, we calculate the correspondance
+        // exactly when we need it.  This might turn out to be much
+        // simpler and more efficient.
+        //
+        // After this, consider a correspondence pair (node, f(node)),
+        // there are five situations to consider:
+        //
+        // 1. f(node) is non-existent: in this case we just add a new
+        // node f(node) and add edges from f(node) to f(child) for
+        // every child of node.
+        //
+        // 2. node and f(node) are not packed: We need to decide
+        // whether f(node) should be cloned.
+        //
+        // 3. node is packed but f(node) is not: in this case we need
+        // to clone f(node), and for each cloned child of node, we
+        // need to decide whether it needs to be added as a new node.
+        //
+        // 4. node is not packed but f(node) is: in this case we check
+        // if there is a cloned child of f(node) that possesses the
+        // same set of children as node, as a prefix.  If, and only
+        // if, this is not the case, we add a new clone with the given
+        // children.
+        //
+        // 5. both node and f(node) are packed: in this case we repeat
+        // the same process as the previous situation, for each cloned
+        // child of node.
 
         if !self.has_node(node_id) {
             return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
@@ -319,7 +406,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
 
         let fragment = fragment.borrow();
 
-        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+        let fragment_nodes_len = fragment.nodes_len();
 
         let root = if let Some(root) = fragment.root() {
             root
@@ -328,96 +415,388 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
             return Ok(());
         };
 
-        // Just a dummy label for use in adding edges.
-        //
-        // REVIEW: I probably should refactor the API for builder_mut.
-        let root_label = fragment
-            .vertex_label(root)?
-            .ok_or(Error::NodeNoLabel(root))?;
+        // A convenient function to calculate the correspondance.
+        fn builder_query<T: GraphLabel>(
+            builder: &PLGBuilderMut<ForestLabel<T>>,
+            label: T,
+        ) -> Option<(usize, ForestLabel<T>, bool)> {
+            let packed_label = ForestLabel::new(label, ForestLabelType::Packed);
+            let plain_label = ForestLabel::new(label, ForestLabelType::Plain);
+
+            if let Some(packed_node) = builder.query_label(packed_label) {
+                Some((packed_node, packed_label, true))
+            } else {
+                builder
+                    .query_label(plain_label)
+                    .map(|plain_node| (plain_node, plain_label, false))
+            }
+        }
 
-        let nodes_len = fragment.nodes_len();
-
-        /// If the fragment root has a duplicate label, the forest
-        /// will not grow, so we use the label to find the adjoined
-        /// node index.
-        ///
-        /// The nodes hava already been added to the forest, so it is
-        /// safe to call unwrap.
-        macro_rules! conversion (
-            ($node:expr) => {
-                {
-                    builder
-                        .query_label(
-                            fragment
-                                .vertex_label($node)?
-                                .ok_or(Error::NodeNoLabel($node))?
-                        ).unwrap()
+        // A convenient function to decide whether a node in the
+        // fragment matches the corresponding node in the builder.
+        fn children_match_p<T: GraphLabel>(
+            builder: &PLGBuilderMut<ForestLabel<T>>,
+            nodea: usize,
+            fragment: &DefaultForest<ForestLabel<T>>,
+            nodeb: usize,
+        ) -> Result<bool, Error> {
+            if builder.degree(nodea)? < fragment.degree(nodeb)? {
+                return Ok(false);
+            }
+
+            for (frag_child, builder_child) in fragment
+                .children_of(nodeb)?
+                .zip(builder.children_of(nodea)?)
+            {
+                let frag_label = fragment
+                    .vertex_label(frag_child)?
+                    .ok_or(Error::NodeNoLabel(frag_child))?
+                    .label();
+                let builder_label = builder
+                    .vertex_label(builder_child)?
+                    .ok_or(Error::NodeNoLabel(builder_child))?
+                    .label();
+
+                if frag_label != builder_label {
+                    return Ok(false);
                 }
             }
-        );
+
+            Ok(true)
+        }
 
         // If the fragment has been planted before, we just add an
         // edge.
 
-        if planted {
-            builder.add_edge(node_id, conversion!(root), root_label)?;
-
-            return Ok(());
-        }
-
-        // First adjoin the relevant nodes and join the edges later.
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
-        let mut used_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();
+        let root_label = fragment
+            .vertex_label(root)?
+            .ok_or(Error::NodeNoLabel(root))?;
 
-        let mut stack = vec![root];
+        let f_root_label_packed = builder_query(&builder, root_label.label());
 
-        while let Some(top) = stack.pop() {
-            if used_nodes.get(top).copied() == Some(true) {
-                continue;
+        if let Some((f_root, f_label, _)) = f_root_label_packed {
+            if f_root != node_id {
+                builder.add_edge(node_id, f_root, f_label)?;
             }
+        } else {
+            let f_root =
+                builder.add_vertex(ForestLabel::new(root_label.label(), ForestLabelType::Plain));
 
-            *used_nodes
-                .get_mut(top)
-                .ok_or(Error::IndexOutOfBounds(top, nodes_len))? = true;
-
-            stack.extend(fragment.children_of(top)?);
+            builder.add_edge(node_id, f_root, root_label)?;
         }
 
-        let used_nodes = used_nodes;
+        if planted {
+            return Ok(());
+        }
 
-        for node in (0..nodes_len).filter(|node| used_nodes.get(*node).copied() == Some(true)) {
-            let label = fragment
+        'node_loop: for node in 0..fragment_nodes_len {
+            let node_label = fragment
                 .vertex_label(node)?
                 .ok_or(Error::NodeNoLabel(node))?;
 
-            builder.add_vertex(label);
-        }
+            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
-        // Don't forget to join the new sub-forest to the original
-        // forest, at the specified position.
+            let f_node_label_packed = builder_query(builder.borrow(), node_label.label());
+
+            if let Some((f_node, _f_label, f_packed)) = f_node_label_packed {
+                match (node_label.is_packed(), f_packed) {
+                    (false, false) => {
+                        // case 2
+
+                        if builder.is_empty_node(f_node)? {
+                            for child in fragment.children_of(node)? {
+                                let child_label = fragment
+                                    .vertex_label(child)?
+                                    .ok_or(Error::NodeNoLabel(child))?
+                                    .label();
+
+                                if let Some((f_child, _, _)) =
+                                    builder_query(builder.borrow(), child_label)
+                                {
+                                    builder.add_edge(f_node, f_child, node_label)?;
+                                } else {
+                                    let f_child = builder.add_vertex(ForestLabel::new(
+                                        child_label,
+                                        ForestLabelType::Plain,
+                                    ));
+                                    builder.add_edge(f_node, f_child, node_label)?;
+                                }
+                            }
+                        } else if !children_match_p(
+                            builder.borrow(),
+                            f_node,
+                            fragment.borrow(),
+                            node,
+                        )? {
+                            let cloned = self.clone_node(f_node, 0, false)?;
+
+                            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                            for child in fragment.children_of(node)? {
+                                let child_label = fragment
+                                    .vertex_label(child)?
+                                    .ok_or(Error::NodeNoLabel(child))?
+                                    .label();
+
+                                if let Some((f_child, _, _)) =
+                                    builder_query(builder.borrow(), child_label)
+                                {
+                                    builder.add_edge(cloned, f_child, node_label)?;
+                                } else {
+                                    let f_child = builder.add_vertex(ForestLabel::new(
+                                        child_label,
+                                        ForestLabelType::Plain,
+                                    ));
+                                    builder.add_edge(cloned, f_child, node_label)?;
+                                }
+                            }
+                        }
+                    }
+                    (true, false) => {
+                        // case 3
+
+                        if builder.is_empty_node(f_node)? {
+                            for cloned_child in fragment.children_of(node)? {
+                                let cloned = self.clone_node(f_node, 0, false)?;
+
+                                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                                for child in fragment.children_of(cloned_child)? {
+                                    let child_label = fragment
+                                        .vertex_label(child)?
+                                        .ok_or(Error::NodeNoLabel(child))?;
+
+                                    let f_child =
+                                        builder_query(builder.borrow(), child_label.label());
+
+                                    if let Some((f_child, _, _)) = f_child {
+                                        builder.add_edge(cloned, f_child, child_label)?;
+                                    } else {
+                                        let f_child = builder.add_vertex(ForestLabel::new(
+                                            child_label.label(),
+                                            ForestLabelType::Plain,
+                                        ));
+
+                                        builder.add_edge(cloned, f_child, child_label)?;
+                                    }
+                                }
+                            }
+
+                            continue 'node_loop;
+                        }
+
+                        for cloned_child in fragment.children_of(node)? {
+                            let builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                            if !children_match_p(
+                                builder.borrow(),
+                                f_node,
+                                fragment.borrow(),
+                                cloned_child,
+                            )? {
+                                let cloned = self.clone_node(f_node, 0, false)?;
+
+                                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                                for child in fragment.children_of(cloned_child)? {
+                                    let child_label = fragment
+                                        .vertex_label(child)?
+                                        .ok_or(Error::NodeNoLabel(child))?;
+
+                                    let f_child =
+                                        builder_query(builder.borrow(), child_label.label());
+
+                                    if let Some((f_child, _, _)) = f_child {
+                                        builder.add_edge(cloned, f_child, child_label)?;
+                                    } else {
+                                        let f_child = builder.add_vertex(ForestLabel::new(
+                                            child_label.label(),
+                                            ForestLabelType::Plain,
+                                        ));
+
+                                        builder.add_edge(cloned, f_child, child_label)?;
+                                    }
+                                }
+                            }
+                        }
+                    }
+                    (false, true) => {
+                        // case 4
+
+                        let mut f_node_cloned_child = None;
+
+                        for f_node_clone in builder.children_of(f_node)? {
+                            f_node_cloned_child = Some(f_node_clone);
+
+                            if builder.is_empty_node(f_node_clone)? {
+                                for child in fragment.children_of(node)? {
+                                    let child_label = fragment
+                                        .vertex_label(child)?
+                                        .ok_or(Error::NodeNoLabel(child))?;
+
+                                    let f_child =
+                                        builder_query(builder.borrow(), child_label.label());
+
+                                    if let Some((f_child, _, _)) = f_child {
+                                        builder.add_edge(f_node_clone, f_child, child_label)?;
+                                    } else {
+                                        let f_child = builder.add_vertex(ForestLabel::new(
+                                            child_label.label(),
+                                            ForestLabelType::Plain,
+                                        ));
+
+                                        builder.add_edge(f_node_clone, f_child, child_label)?;
+                                    }
+                                }
+
+                                continue 'node_loop;
+                            }
+
+                            if children_match_p(
+                                builder.borrow(),
+                                f_node_clone,
+                                fragment.borrow(),
+                                node,
+                            )? {
+                                continue 'node_loop;
+                            }
+                        }
+
+                        let f_node_cloned_child = if let Some(clone) = f_node_cloned_child {
+                            clone
+                        } else {
+                            continue 'node_loop;
+                        };
+
+                        let cloned = self.clone_node(f_node_cloned_child, 0, false)?;
+
+                        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                        for child in fragment.children_of(node)? {
+                            let child_label = fragment
+                                .vertex_label(child)?
+                                .ok_or(Error::NodeNoLabel(child))?;
+
+                            let f_child = builder_query(builder.borrow(), child_label.label());
+
+                            if let Some((f_child, _, _)) = f_child {
+                                builder.add_edge(cloned, f_child, child_label)?;
+                            } else {
+                                let f_child = builder.add_vertex(ForestLabel::new(
+                                    child_label.label(),
+                                    ForestLabelType::Plain,
+                                ));
+
+                                builder.add_edge(cloned, f_child, child_label)?;
+                            }
+                        }
+                    }
+                    (true, true) => {
+                        // case 5
+
+                        'cloned_loop: for cloned_child in fragment.children_of(node)? {
+                            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                            let mut f_node_cloned_child = None;
+
+                            for f_node_clone in builder.children_of(f_node)? {
+                                f_node_cloned_child = Some(f_node_clone);
+
+                                if builder.is_empty_node(f_node_clone)? {
+                                    for child in fragment.children_of(cloned_child)? {
+                                        let child_label = fragment
+                                            .vertex_label(child)?
+                                            .ok_or(Error::NodeNoLabel(child))?;
+
+                                        let f_child =
+                                            builder_query(builder.borrow(), child_label.label());
+
+                                        if let Some((f_child, _, _)) = f_child {
+                                            builder.add_edge(f_node_clone, f_child, child_label)?;
+                                        } else {
+                                            let f_child = builder.add_vertex(ForestLabel::new(
+                                                child_label.label(),
+                                                ForestLabelType::Plain,
+                                            ));
+
+                                            builder.add_edge(f_node_clone, f_child, child_label)?;
+                                        }
+                                    }
+
+                                    continue 'node_loop;
+                                }
+
+                                if children_match_p(
+                                    builder.borrow(),
+                                    f_node_clone,
+                                    fragment.borrow(),
+                                    cloned_child,
+                                )? {
+                                    continue 'cloned_loop;
+                                }
+                            }
+
+                            let f_node_cloned_child = if let Some(clone) = f_node_cloned_child {
+                                clone
+                            } else {
+                                continue 'cloned_loop;
+                            };
+
+                            let cloned = self.clone_node(f_node_cloned_child, 0, false)?;
+
+                            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                            for child in fragment.children_of(cloned_child)? {
+                                let child_label = fragment
+                                    .vertex_label(child)?
+                                    .ok_or(Error::NodeNoLabel(child))?;
+
+                                let f_child = builder_query(builder.borrow(), child_label.label());
+
+                                if let Some((f_child, _, _)) = f_child {
+                                    builder.add_edge(cloned, f_child, child_label)?;
+                                } else {
+                                    let f_child = builder.add_vertex(ForestLabel::new(
+                                        child_label.label(),
+                                        ForestLabelType::Plain,
+                                    ));
+
+                                    builder.add_edge(cloned, f_child, child_label)?;
+                                }
+                            }
+                        }
+                    }
+                }
+            } else {
+                // case 1
 
-        builder.add_edge(node_id, conversion!(root), root_label)?;
+                let f_node = builder
+                    .add_vertex(ForestLabel::new(node_label.label(), ForestLabelType::Plain));
 
-        // We can try to calculate the depth of fragments, if we need
-        // to lower the memory usage.  But in our use cases, we
-        // usually deal with fragments where each node has at most one
-        // child, so the depth is supposed to be equal to the length
-        // in this case.
-        let mut stack = Vec::with_capacity(fragment.nodes_len());
+                for child in fragment.children_of(node)? {
+                    if child == node {
+                        continue;
+                    }
 
-        stack.push(root);
+                    let child_label_label = fragment
+                        .vertex_label(child)?
+                        .ok_or(Error::NodeNoLabel(child))?
+                        .label();
 
-        let mut seen_nodes = std::collections::HashSet::<usize>::new();
+                    let f_child_label_packed = builder_query(builder.borrow(), child_label_label);
 
-        while let Some(top) = stack.pop() {
-            seen_nodes.insert(top);
+                    if let Some((f_child, _, _)) = f_child_label_packed {
+                        builder.add_edge(f_node, f_child, node_label)?;
+                    } else {
+                        let plain_label =
+                            ForestLabel::new(child_label_label, ForestLabelType::Plain);
 
-            for child in fragment.children_of(top)? {
-                builder.add_edge(conversion!(top), conversion!(child), root_label)?;
+                        let f_child = builder.add_vertex(plain_label);
 
-                if !seen_nodes.contains(&child) {
-                    seen_nodes.insert(child);
-                    stack.push(child);
+                        builder.add_edge(f_node, f_child, node_label)?;
+                    }
                 }
             }
         }
@@ -459,7 +838,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
 
             // Make sure it only has one parent, which is the
             // representative node.
-            // assert_eq!(parents.len(), 1);
+            assert_eq!(parents.len(), 1);
 
             // We checked its length is 1, so it is safe to unwrap
             // here.
@@ -899,6 +1278,28 @@ pub(crate) use leaf;
 #[cfg(test)]
 mod item_test {
     use super::*;
+    use graph::Graph;
+
+    fn make_forest_1() -> Result<DefaultForest<ForestLabel<usize>>, Box<dyn std::error::Error>> {
+        let mut result = leaf!(0);
+
+        for i in 1..5 {
+            result.plant(0, leaf!(i), false)?;
+        }
+
+        for i in 5..10 {
+            result.plant(2, leaf!(i), false)?;
+        }
+
+        result.plant(4, leaf!(10), false)?;
+        result.plant(4, leaf!(11), false)?;
+
+        let clone = result.clone_node(4, 1, false)?;
+
+        result.plant(clone, leaf!(12), false)?;
+
+        Ok(result)
+    }
 
     #[test]
     fn test_forest_api() -> Result<(), Box<dyn std::error::Error>> {
@@ -963,6 +1364,7 @@ mod item_test {
         test_forest.plant(0, leaf!(5), false)?;
 
         assert!(forest.is_prefix(2, &test_forest)?);
+        assert!(!forest.is_prefix(0, &test_forest)?);
 
         // now test cloning
 
@@ -991,6 +1393,132 @@ mod item_test {
     }
 
     #[test]
+    fn test_case_1() -> Result<(), Box<dyn std::error::Error>> {
+        let mut forest = make_forest_1()?;
+
+        let mut test_forest = leaf!(0);
+        test_forest.plant(0, leaf!(13), false)?;
+
+        assert_eq!(forest.is_prefix(0, &test_forest), Ok(false));
+
+        forest.plant(0, leaf!(13), false)?;
+
+        assert_eq!(forest.degree(0), Ok(5));
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_case_2() -> Result<(), Box<dyn std::error::Error>> {
+        let mut forest = make_forest_1()?;
+
+        let mut test_forest = leaf!(0);
+        test_forest.plant(0, leaf!(9), false)?;
+
+        assert_eq!(forest.is_prefix(0, test_forest), Ok(false));
+
+        forest.plant(0, leaf!(9), false)?;
+
+        assert_eq!(forest.degree(0), Ok(5));
+
+        assert_eq!(forest.children_of(0)?.nth(4), Some(9));
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_case_3() -> Result<(), Box<dyn std::error::Error>> {
+        let mut forest = make_forest_1()?;
+
+        let mut test_forest = leaf!(2);
+
+        test_forest.plant(0, leaf!(5), false)?;
+
+        let clone = test_forest.clone_node(0, 0, false)?;
+
+        test_forest.plant(clone, leaf!(6), false)?;
+
+        assert_eq!(forest.is_prefix(0, &test_forest), Ok(false));
+
+        let mut answer = forest.clone();
+
+        forest.plant(0, test_forest, false)?;
+
+        let clone = answer.clone_node(2, 0, false)?;
+
+        answer.plant(clone, leaf!(6), false)?;
+
+        assert_eq!(forest, answer);
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_case_4() -> Result<(), Box<dyn std::error::Error>> {
+        let mut forest = make_forest_1()?;
+
+        let mut test_forest = leaf!(4);
+
+        test_forest.plant(0, leaf!(10), false)?;
+        test_forest.plant(0, leaf!(12), false)?;
+
+        assert_eq!(forest.is_prefix(12, &test_forest), Ok(true));
+
+        let answer = forest.clone();
+
+        forest.plant(0, test_forest, false)?;
+
+        assert_eq!(forest, answer);
+
+        let mut test_forest = leaf!(4);
+
+        test_forest.plant(0, leaf!(10), false)?;
+        test_forest.plant(0, leaf!(9), false)?;
+
+        assert_eq!(forest.is_prefix(12, &test_forest), Ok(false));
+
+        let mut answer = forest.clone();
+
+        forest.plant(0, test_forest, false)?;
+
+        let clone = answer.clone_node(4, 1, false)?;
+
+        answer.plant(clone, leaf!(9), false)?;
+
+        assert_eq!(forest, answer);
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_case_5() -> Result<(), Box<dyn std::error::Error>> {
+        let mut forest = make_forest_1()?;
+
+        let mut test_forest = leaf!(4);
+
+        test_forest.plant(0, leaf!(10), false)?;
+        test_forest.plant(0, leaf!(12), false)?;
+
+        let clone = test_forest.clone_node(0, 1, false)?;
+
+        test_forest.plant(clone, leaf!(9), false)?;
+
+        assert_eq!(forest.is_prefix(12, &test_forest), Ok(false));
+
+        let mut answer = forest.clone();
+
+        forest.plant(0, test_forest, false)?;
+
+        let clone = answer.clone_node(4, 1, false)?;
+
+        answer.plant(clone, leaf!(9), false)?;
+
+        assert_eq!(forest, answer);
+
+        Ok(())
+    }
+
+    #[test]
     fn test_eq() -> Result<(), Box<dyn std::error::Error>> {
         let mut forest = leaf!(0, usize);
 
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index da13c56..c9d9c5a 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -657,7 +657,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         } else if labela.clone_index().is_some() {
             let mut parentsa = self.parents_of(nodea)?;
 
-            // assert_eq!(parentsa.len(), 1);
+            assert_eq!(parentsa.len(), 1);
 
             let parenta = parentsa.next().unwrap().node();