Fix phantom edges

Previously there was a minor bug: if the chain-rule machine ended in a
node without children, which node should be accepting because of edges
that have no children and hence were ignored, then since the node has
no children, it would be regarded as not accepting.  Now this issue is
fixed by introducting real or imaginary edges, where an imaginary edge
is used to determine the acceptance of nodes without chidlren.

4 files changed, 307 insertions, 201 deletions

diff --git a/chain/src/default.rs b/chain/src/default.rs
index 31c1002..c873de7 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -110,13 +110,13 @@ impl Default for DerIterIndex {
 }
 
 /// A complex type used for storing values of edges with two layers.
-type SecondTypeValue = (PaSe, bool, Vec<(Edge, usize)>);
+type SecondTypeValue = (PaSe, bool, Vec<(Roi, usize)>);
 
 /// An iterator of TwoLayers.
 #[derive(Debug, Default)]
 pub struct DerIter {
     /// Stores edges of only one layer.
-    singles: Vec<(Edge, usize)>,
+    singles: Vec<(Roi, usize)>,
     /// Stores edges with two layers.  They are grouped by their
     /// labels of the second layer.
     ///
@@ -139,7 +139,7 @@ impl DerIter {
         label: usize,
         forest_source: PaSe,
         accepting: bool,
-        edges: Vec<(Edge, usize)>,
+        edges: Vec<(Roi, usize)>,
     ) {
         if let Some((_, _, vec)) = self.seconds.get_mut(&label) {
             vec.extend(edges);
@@ -449,6 +449,30 @@ impl Chain for DefaultChain {
         self.current = new;
     }
 
+    fn update_epsilon(
+        &mut self,
+        node_id: usize,
+        edges: impl Iterator<Item = (Roi, usize)>,
+    ) -> Result<(), Self::Error> {
+        for (roi, _) in edges {
+            match roi.imaginary_part() {
+                Some(target) => {
+                    if matches!(self.accepting_vec.get(target).copied(), Some(true)) {
+                        let accepting_vec_len = self.accepting_vec.len();
+
+                        *self
+                            .accepting_vec
+                            .get_mut(node_id)
+                            .ok_or(Error::IndexOutOfBounds(node_id, accepting_vec_len))? = true;
+                    }
+                }
+                None => {}
+            }
+        }
+
+        Ok(())
+    }
+
     type DerIter = DerIter;
 
     fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error> {
@@ -484,7 +508,7 @@ impl Chain for DefaultChain {
             child_iter: impl Iterator<Item = usize> + ExactSizeIterator + Clone,
             atom_child_iter: impl Iterator<Item = usize> + Clone,
             pase: PaSe,
-            mut output: impl AsMut<Vec<(Edge, usize)>>,
+            mut output: impl AsMut<Vec<(Roi, usize)>>,
         ) -> Result<(), Error> {
             // First check the values from iterators are all valid.
             let graph_len = chain.graph.nodes_len();
@@ -516,11 +540,9 @@ impl Chain for DefaultChain {
 
             for atom_child in atom_child_iter.clone() {
                 let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap();
-                let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap();
+                // let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap();
 
-                if !atom_child_empty_node {
-                    num += child_iter.len();
-                }
+                num += child_iter.len();
 
                 if atom_child_accepting {
                     num += child_iter_total_degree;
@@ -539,16 +561,19 @@ impl Chain for DefaultChain {
                 let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap();
                 let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap();
 
-                let edge = Edge::new(atom_child, pase, atom_child_accepting);
+                let roi = Edge::new(atom_child, pase, atom_child_accepting).into();
 
-                if !atom_child_empty_node {
-                    output.extend(child_iter.clone().map(|child| (edge, child)));
-                }
+                if atom_child_empty_node {
+                    output.extend(child_iter.clone().map(|child| (child.into(), child)));
+                } else {
+                    output.extend(child_iter.clone().map(|child| (roi, child)));
+                };
 
                 if atom_child_accepting {
                     for child in child_iter.clone() {
                         for (child_label, child_child) in chain.graph.labels_of(child).unwrap() {
-                            output.extend(child_child.map(|target| (*child_label, target)));
+                            output
+                                .extend(child_child.map(|target| ((*child_label).into(), target)));
                         }
                     }
                 }
@@ -666,7 +691,8 @@ impl Chain for DefaultChain {
                                     if self.atom.is_empty_node(atom_child).unwrap() {
                                         der_iter.singles.extend(child_iter.clone().map(|child| {
                                             (
-                                                Edge::new(virtual_node, virtual_pase, accepting),
+                                                Edge::new(virtual_node, virtual_pase, accepting)
+                                                    .into(),
                                                 child,
                                             )
                                         }));
@@ -684,7 +710,7 @@ impl Chain for DefaultChain {
                                                 self.graph.labels_of(child).unwrap().flat_map(
                                                     |(child_label, child_child_iter)| {
                                                         child_child_iter.map(|child_child| {
-                                                            (*child_label, child_child)
+                                                            ((*child_label).into(), child_child)
                                                         })
                                                     },
                                                 )
@@ -716,18 +742,39 @@ mod test_der_iter {
 
         let parent = Default::default();
 
-        der_iter.singles.push((Edge::new(0, parent, true), 0));
+        der_iter
+            .singles
+            .push((Edge::new(0, parent, true).into(), 0));
 
-        der_iter.singles.push((Edge::new(1, parent, true), 0));
+        der_iter
+            .singles
+            .push((Edge::new(1, parent, true).into(), 0));
 
-        der_iter.singles.push((Edge::new(2, parent, true), 0));
+        der_iter
+            .singles
+            .push((Edge::new(2, parent, true).into(), 0));
 
-        der_iter.add_second_layer(3, parent, true, vec![(Edge::new(4, parent, true), 1)]);
+        der_iter.add_second_layer(
+            3,
+            parent,
+            true,
+            vec![(Edge::new(4, parent, true).into(), 1)],
+        );
 
-        der_iter.add_second_layer(6, parent, true, vec![(Edge::new(5, parent, true), 1)]);
+        der_iter.add_second_layer(
+            6,
+            parent,
+            true,
+            vec![(Edge::new(5, parent, true).into(), 1)],
+        );
 
         // add an entry with a repeated label
-        der_iter.add_second_layer(3, parent, true, vec![(Edge::new(7, parent, true), 2)]);
+        der_iter.add_second_layer(
+            3,
+            parent,
+            true,
+            vec![(Edge::new(7, parent, true).into(), 2)],
+        );
 
         assert_eq!(
             der_iter.next(),
@@ -736,8 +783,8 @@ mod test_der_iter {
                 parent,
                 true,
                 vec![
-                    (Edge::new(4, parent, true), 1),
-                    (Edge::new(7, parent, true), 2)
+                    (Edge::new(4, parent, true).into(), 1),
+                    (Edge::new(7, parent, true).into(), 2)
                 ]
             ))
         );
@@ -748,23 +795,23 @@ mod test_der_iter {
                 6,
                 parent,
                 true,
-                vec![(Edge::new(5, parent, true), 1)]
+                vec![(Edge::new(5, parent, true).into(), 1)]
             ))
         );
 
         assert_eq!(
             der_iter.next(),
-            Some(TwoLayers::One(Edge::new(0, parent, true), 0))
+            Some(TwoLayers::One(Edge::new(0, parent, true).into(), 0))
         );
 
         assert_eq!(
             der_iter.next(),
-            Some(TwoLayers::One(Edge::new(1, parent, true), 0))
+            Some(TwoLayers::One(Edge::new(1, parent, true).into(), 0))
         );
 
         assert_eq!(
             der_iter.next(),
-            Some(TwoLayers::One(Edge::new(2, parent, true), 0))
+            Some(TwoLayers::One(Edge::new(2, parent, true).into(), 0))
         );
 
         assert_eq!(der_iter.next(), None);
@@ -800,6 +847,24 @@ mod test_chain {
         chain.chain(0, 11)?;
         chain.chain(0, 12)?;
 
+        let forest = &mut chain.forest;
+
+        let node = forest
+            .query_label(ForestLabel::from(GrammarLabel::new(TNT::Non(6), 6)))
+            .unwrap();
+
+        forest.splone(node, Some(13), forest.degree(node)?)?;
+
+        let node = forest
+            .query_label(ForestLabel::from(GrammarLabel::new(TNT::Non(1), 0)))
+            .unwrap();
+
+        forest.splone(node, Some(13), forest.degree(node)?)?;
+
+        forest.splone(0, Some(13), forest.degree(0)?)?;
+
+        forest.print_viz("forest.gv")?;
+
         assert!(matches!(chain.epsilon(), Ok(true)));
 
         #[cfg(feature = "test-print-viz")]
@@ -823,10 +888,13 @@ mod test_chain {
         chain.chain(0, 0)?;
         chain.chain(2, 1)?;
         chain.chain(2, 2)?;
-        // chain.chain(2, 3)?;
-        chain.chain(1, 3)?;
+        chain.chain(2, 3)?;
+        chain.chain(1, 4)?;
+
+        chain.forest.print_viz("forest.gv")?;
 
         dbg!(chain.current(), chain.history());
+        item::default::print_labels(&chain.atom, &chain.forest)?;
 
         #[cfg(feature = "test-print-viz")]
         {
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index 4f4835b..851968c 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -19,6 +19,12 @@ fn get_rule_label(label: GrammarLabel) -> Option<usize> {
     }
 }
 
+/// Existing or non-existing label.
+enum Eon {
+    Ex(usize),
+    Nex(ForestLabel<GrammarLabel>),
+}
+
 impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// Either "open split" or "closed split".
     ///
@@ -56,6 +62,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node]
     /// for details.
     ///
+    /// # Return
+    ///
+    /// The function returns the new, splitted or cloned node, or the
+    /// old node, if nothing is performed.
+    ///
     /// # Name
     ///
     /// The name is a mixture of *split* and *clone*.
@@ -74,12 +85,19 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// descriptions of procedures below, we actually refer to the
     /// parents of the rule parents, which should again be checked to
     /// be labelled by non-terminals.
-    fn splone(&mut self, node: usize, end: Option<usize>, edge_index: usize) -> Result<(), Error> {
+    pub(crate) fn splone(
+        &mut self,
+        node: usize,
+        end: Option<usize>,
+        edge_index: usize,
+    ) -> Result<usize, Error> {
         let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
 
         assert!(get_nt_label(node_label.label()).is_some());
 
         if node_label.is_packed() {
+            self.print_viz("dbg forest.gv").unwrap();
+            dbg!(self.vertex_label(node)?, end);
             return Err(Error::SplitPack(node));
         }
 
@@ -89,26 +107,26 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         // We can check the end to know whether the new label is equal
         // to the old label.
         if node_end == end {
-            if node_degree == edge_index + 1 {
-                return Ok(());
+            if node_degree <= edge_index + 1 {
+                return Ok(node);
             }
 
-            dbg!();
-            self.clone_node(node, edge_index + 1, false)?;
+            let cloned = self.clone_node(node, edge_index + 1, false)?;
 
-            return Ok(());
+            return Ok(cloned);
         }
 
         let new_label = self.create_new_label(node, end, edge_index)?;
 
-        let new_label = if let Some(label) = new_label {
-            label
-        } else {
-            return Ok(());
+        let new_label = match new_label {
+            Eon::Nex(label) => label,
+            Eon::Ex(existing) => {
+                return Ok(existing);
+            }
         };
 
         if node_end.is_some()
-            || edge_index + 1 != node_degree
+            || edge_index + 1 < node_degree
             || node_label.clone_index().is_some()
             || new_label.clone_index().is_some()
         {
@@ -168,7 +186,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         //     builder.add_edge(packed, node, new_label)?;
         // }
 
-        Ok(())
+        Ok(node)
     }
 
     /// Procedure to split the node:
@@ -180,12 +198,16 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// 3. For each parent, clone the parent.  Replace the original
     /// child of the parent, which pointed to the old node, by this
     /// new node.  Other children are inherited from the old parent.
+    ///
+    /// # Return
+    ///
+    /// The function returns the new node index.
     fn split_node(
         &mut self,
         new_label: ForestLabel<GrammarLabel>,
         mut node: usize,
         edge_index: usize,
-    ) -> Result<(), Error> {
+    ) -> Result<usize, Error> {
         let end = new_label.label().end();
 
         let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
@@ -269,7 +291,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         };
 
         for (parent, new_child) in parents {
-            if self.has_same_children_but_one(
+            if self.has_same_children_until(
                 parent.node(),
                 parent.node(),
                 parent.edge(),
@@ -284,18 +306,9 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
             builder.add_edge(cloned, new_child, new_label)?;
-
-            let children_to_add: Vec<_> = builder
-                .children_of(parent.node())?
-                .skip(parent.edge() + 1)
-                .collect();
-
-            for child in children_to_add {
-                builder.add_edge(cloned, child, new_label)?;
-            }
         }
 
-        Ok(())
+        Ok(new_node)
     }
 
     /// Procedure for the new label:
@@ -320,7 +333,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         node: usize,
         end: Option<usize>,
         edge_index: usize,
-    ) -> Result<Option<ForestLabel<GrammarLabel>>, Error> {
+    ) -> Result<Eon, Error> {
         let mut copied_label = self
             .vertex_label(node)?
             .ok_or(Error::NodeNoLabel(node))?
@@ -337,7 +350,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         if let Some(packed) = self.query_label(label) {
             for child in self.children_of(packed)? {
                 if self.has_same_children(child, node, self.degree(child)?, edge_index + 1)? {
-                    return Ok(None);
+                    return Ok(Eon::Ex(child));
                 }
             }
 
@@ -347,7 +360,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             let clone_index = self.clone_node(first_child, 0, true)?;
 
-            Ok(Some(ForestLabel::new(
+            Ok(Eon::Nex(ForestLabel::new(
                 copied_label,
                 ForestLabelType::Cloned(clone_index),
             )))
@@ -356,17 +369,17 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             if let Some(existing) = self.query_label(plain_label) {
                 if self.has_same_children(existing, node, self.degree(existing)?, edge_index + 1)? {
-                    return Ok(None);
+                    return Ok(Eon::Ex(existing));
                 }
 
                 let clone_index = self.clone_node(existing, 0, true)?;
 
-                Ok(Some(ForestLabel::new(
+                Ok(Eon::Nex(ForestLabel::new(
                     copied_label,
                     ForestLabelType::Cloned(clone_index),
                 )))
             } else {
-                Ok(Some(plain_label))
+                Ok(Eon::Nex(plain_label))
             }
         }
     }
@@ -396,9 +409,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     }
 
     /// Detect if a node has a branch that has the same children as
-    /// another node, except at a given index, where it points to
-    /// another given node.
-    fn has_same_children_but_one(
+    /// another node, until a given index, where it points to another
+    /// given node.
+    ///
+    /// # Clones
+    ///
+    /// If `nodea` is a clone, it checks every clone to see if the
+    /// condition is satisfied for some clone.
+    fn has_same_children_until(
         &self,
         nodea: usize,
         nodeb: usize,
@@ -408,14 +426,20 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         let labela = self.vertex_label(nodea)?.ok_or(Error::NodeNoLabel(nodea))?;
         let children_b = self.children_of(nodeb)?;
 
+        if children_b.len() < edge_index + 1 {
+            return Err(Error::IndexOutOfBounds(edge_index, children_b.len() - 1));
+        }
+
         if labela.is_plain() {
             let children_a = self.children_of(nodea)?;
 
-            if children_a.len() != children_b.len() {
+            if children_a.len() < edge_index + 1 {
                 return Ok(false);
             }
 
-            for (index, (childa, childb)) in children_a.zip(children_b).enumerate() {
+            for (index, (childa, childb)) in
+                children_a.zip(children_b).take(edge_index + 1).enumerate()
+            {
                 if index != edge_index {
                     if childa != childb {
                         return Ok(false);
@@ -437,11 +461,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 let children_a = self.children_of(branch)?;
                 let children_b = children_b.clone();
 
-                if children_a.len() != children_b.len() {
+                if children_a.len() < edge_index + 1 {
                     continue 'branch_loop;
                 }
 
-                for (index, (childa, childb)) in children_a.zip(children_b).enumerate() {
+                for (index, (childa, childb)) in
+                    children_a.zip(children_b).take(edge_index + 1).enumerate()
+                {
                     if index != edge_index {
                         if childa != childb {
                             continue 'branch_loop;
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index 43807f8..4c51d9a 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -25,6 +25,12 @@ fn index_out_of_bounds_conversion(ge: GrammarError) -> Error {
         _ => Error::Invalid,
     }
 }
+
+/// Determine if a label is labelled by a terminal.
+fn is_labelled_by_terminal(label: GrammarLabelType) -> bool {
+    matches!(label.tnt(), Some(t) if matches!(t, TNT::Ter(_)))
+}
+
 /// A helper function to generate a fragment of forest.
 ///
 /// It simply constructs a root node and then appends
@@ -38,30 +44,43 @@ pub fn generate_fragment(
     labels: impl AsRef<[GrammarLabelType]>,
     pos: usize,
 ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, crate::default::Error> {
-    let mut labels_iter = labels.as_ref().iter();
-    let mut result: DefaultForest<ForestLabel<GrammarLabel>>;
-
-    if let Some(first_label) = labels_iter.next() {
-        result = DefaultForest::new_leaf(GrammarLabel::new(*first_label, pos));
-
-        let mut index = 0;
-
-        for label in labels_iter {
-            result.plant(
-                index,
-                DefaultForest::new_leaf(GrammarLabel::new(*label, pos)),
-                false,
-            )?;
-
-            // To prevent duplication of labels causing
-            // panics, we query the index of the new node.
-            index = result
-                .query_label(GrammarLabel::new(*label, pos).into())
-                // REVIEW: Perhaps a LabelNoNode error?
-                .ok_or(Error::Invalid)?;
-        }
+    let labels_slice = labels.as_ref();
+
+    let labels_len = labels_slice.len();
+
+    let last_label = if labels_len > 0 {
+        labels_slice.get(labels_len - 1).copied().unwrap()
     } else {
-        result = Default::default();
+        return Ok(Default::default());
+    };
+
+    let labels_iter = labels_slice.iter();
+
+    let labels_iter_zipped = labels_iter
+        .clone()
+        .zip(labels_iter.skip(1).chain(std::iter::once(&last_label)));
+
+    let mut mapped_iter = labels_iter_zipped.map(|(label, next_label)| {
+        if is_labelled_by_terminal(*next_label) {
+            GrammarLabel::new_closed(*label, pos, pos + 1)
+        } else {
+            GrammarLabel::new(*label, pos)
+        }
+    });
+
+    let first_label = mapped_iter.next().unwrap();
+
+    let mut result = DefaultForest::new_leaf(first_label);
+
+    let mut index = 0;
+
+    for label in mapped_iter {
+        result.plant(index, DefaultForest::new_leaf(label), false)?;
+
+        index = result
+            .query_label(label.into())
+            // REVIEW: Perhaps a LabelNoNode error?
+            .ok_or(Error::Invalid)?;
     }
 
     Ok(result)
@@ -123,7 +142,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         &mut self,
         label: Edge,
         fragment: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>,
-        atom_child_iter: impl Iterator<Item = usize>,
+        atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator,
         atom: &DefaultAtom,
     ) -> Result<PaSe, Error> {
         let fragment = fragment.borrow();
@@ -243,8 +262,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             // locate the nodes
             for reduction_nt in reduction_info.iter().copied().flatten().rev() {
                 while let Some(mut node) = stack.pop() {
-                    // REVIEW: A lot of labels appear here.
-                    // Perhaps I need to refactor something?
                     let mut node_label = self
                         .vertex_label(node.node())?
                         .ok_or_else(|| Error::NodeNoLabel(node.node()))?;
@@ -255,53 +272,32 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                             .label(),
                         GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt
                     ) {
-                        // TODO: Try to update the end index of the
-                        // node; if the node already has an ending
-                        // index, clone the node, and update the
-                        // ending index of the cloned node; otherwise,
-                        // just set the ending index.
-
-                        if node_label.label().end().is_some() {
-                            let cloned_node =
-                                self.clone_node(node.node(), node.edge() + 1, false)?;
-
-                            self.transform_label(cloned_node, |mut label| {
-                                label.set_end(pos + 1);
-                                label
-                            })?;
-
-                            node_label = self
-                                .vertex_label(node.node())?
-                                .ok_or_else(|| Error::NodeNoLabel(node.node()))?;
-                        } else {
-                            self.transform_label(node.node(), |mut label| {
-                                label.set_end(pos + 1);
-                                label
-                            })?;
-                        }
+                        let sploned_node = self.splone(node.node(), Some(pos), node.edge())?;
+
+                        node_label = self
+                            .vertex_label(sploned_node)?
+                            .ok_or(Error::NodeNoLabel(sploned_node))?;
 
                         if node_label.clone_index().is_some() {
-                            let mut parent_iter = self.parents_of(node.node())?;
+                            let mut parent_iter = self.parents_of(sploned_node)?;
 
                             #[cfg(debug_assertions)]
-                            assert_eq!(parent_iter.len(), 1);
+                            {
+                                assert_eq!(parent_iter.len(), 1);
 
-                            node = parent_iter.next().unwrap();
+                                assert!(self
+                                    .vertex_label(sploned_node)?
+                                    .ok_or(Error::NodeNoLabel(sploned_node))?
+                                    .is_packed());
+                            }
 
-                            #[cfg(debug_assertions)]
-                            assert!(self
-                                .vertex_label(node.node())?
-                                .ok_or_else(|| Error::NodeNoLabel(node.node()))?
-                                .is_packed());
+                            node = parent_iter.next().unwrap();
+                        } else {
+                            node = Parent::new(sploned_node, node.edge());
                         }
 
                         let parents_iter = self.parents_of(node.node())?;
 
-                        let to_update = parents_iter
-                            .clone()
-                            .map(|parent| parent.node())
-                            .collect::<Vec<_>>();
-
                         for parent in parents_iter {
                             let parent_label = self
                                 .vertex_label(parent.node())?
@@ -312,14 +308,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                                 crate::item::default::print_labels(atom, self.borrow()).unwrap();
                                 self.print_viz("dbg forest.gv").unwrap();
 
-                                dbg!(parent, parent_label, label, node);
+                                dbg!(parent, parent_label, label, node, sploned_node);
 
                                 panic!("assumption fails");
                             }
 
-                            // debug_assert!(parent_label.label().rule().is_some());
-                            // debug_assert!(parent_label.end().is_none());
-
                             second_stack.extend(self.parents_of(parent.node())?.filter(|n| {
                                 matches!(self.vertex_label(n.node()),
                                          Ok(Some(label))
@@ -328,13 +321,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                                              Some(TNT::Non(_))))
                             }));
                         }
-
-                        for node in to_update {
-                            self.transform_label(node, |mut label| {
-                                label.set_end(pos + 1);
-                                label
-                            })?;
-                        }
                     }
                 }
 
@@ -357,59 +343,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 self.print_viz("dbg forest.gv").unwrap();
 
                 #[cfg(test)]
-                genins_test::print_labels(atom, self).unwrap();
+                genins_test::print_labels(atom, self.borrow()).unwrap();
 
                 return Err(Error::CannotPlant);
             }
 
             for parent in stack.into_iter() {
-                let was_last_child = parent.edge() + 1 >= self.degree(parent.node())?;
-
-                let overlap = {
-                    if let Ok(child) = self.nth_child(parent.node(), parent.edge()) {
-                        let edge_th_child = child;
-                        let child_label = self
-                            .vertex_label(edge_th_child)?
-                            .ok_or(Error::NodeNoLabel(edge_th_child))?;
-                        let child_start = child_label.label().start();
-                        let child_end = child_label.label().end();
-
-                        child_start >= pos || matches!(child_end, Some(end) if end > pos)
-                    } else {
-                        // the root case
-                        false
-                    }
-                };
+                let sploned_node = self.splone(parent.node(), None, parent.edge())?;
 
-                if overlap {
-                    let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?;
-
-                    self.plant(cloned_node, fragment, non_empty)?;
-                } else if was_last_child {
-                    // dbg!(&fragment);
-                    self.plant(parent.node(), fragment, non_empty)?;
-                } else {
-                    let nth_child = self.nth_child(parent.node(), parent.edge() + 1)?;
-
-                    if self.is_prefix(nth_child, fragment)? {
-                        // do nothing
-                        continue;
-                    }
-
-                    // dbg!(
-                    //     label,
-                    //     atom_child,
-                    //     &parents,
-                    //     reduction_info,
-                    //     atom.query_reduction(label.label(), atom_child).unwrap()
-                    // );
-
-                    // self.print_viz("dbg forest.gv").unwrap();
-
-                    let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?;
-
-                    self.plant(cloned_node, fragment, non_empty)?;
-                }
+                self.plant(sploned_node, fragment, non_empty)?;
 
                 non_empty = true;
             }
diff --git a/chain/src/lib.rs b/chain/src/lib.rs
index 745ad5a..a7740c2 100644
--- a/chain/src/lib.rs
+++ b/chain/src/lib.rs
@@ -64,12 +64,59 @@ impl core::fmt::Display for Edge {
     }
 }
 
-// TODO: Define an enumeration that stands for either an edge or a
-// "phantom" edge.
-//
-// A phantom edge will be ignored when adding edges.  The phantom
-// edges will be used to determine the acceptance of a node, when and
-// only when that new node turns out to have no children.
+/// A Real Or Imaginary edge.
+///
+/// An imaginary edge will be ignored when adding edges.  The
+/// imaginary edges will be used to determine the acceptance of a
+/// node, when and only when that new node turns out to have no
+/// children.
+///
+/// # Note
+///
+/// Non, je ne suis pas un roi.  Je ne sais pas qu'est-ce que vous
+/// parlez.
+#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
+pub enum Roi {
+    /// A real edge is an ordinary edge.
+    Re(Edge),
+    /// The label of an imaginary edge is not important, so we only
+    /// record its target.
+    Im(usize),
+}
+
+// Some convenient conversions
+
+impl From<Edge> for Roi {
+    fn from(edge: Edge) -> Self {
+        Self::Re(edge)
+    }
+}
+
+impl From<usize> for Roi {
+    fn from(target: usize) -> Self {
+        Self::Im(target)
+    }
+}
+
+impl Roi {
+    /// Return the real part if it is a real edge.
+    fn real_part(self) -> Option<Edge> {
+        if let Self::Re(edge) = self {
+            Some(edge)
+        } else {
+            None
+        }
+    }
+
+    /// Return the imaginary part if it is an imaginary edge.
+    fn imaginary_part(self) -> Option<usize> {
+        if let Self::Im(target) = self {
+            Some(target)
+        } else {
+            None
+        }
+    }
+}
 
 /// Each derivation is a concatenation of two items, so there are two
 /// layers.  But some items have no children and are accepting, in
@@ -81,7 +128,7 @@ impl core::fmt::Display for Edge {
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub enum TwoLayers {
     /// One layer has no children.
-    One(Edge, usize),
+    One(Roi, usize),
     // REVIEW: Maybe we do not need to store an edge in the forest: we
     // only need the source of the edge?
     /// Both layers have children.
@@ -90,7 +137,7 @@ pub enum TwoLayers {
     /// the source of the associated forest edge of the second layer,
     /// and the third is a list of edges, which are the common first
     /// layers.
-    Two(usize, PaSe, bool, Vec<(Edge, usize)>),
+    Two(usize, PaSe, bool, Vec<(Roi, usize)>),
 }
 
 /// The type of a collapsed iterator.
@@ -122,7 +169,7 @@ where
     I: Iterator<Item = TwoLayers>,
     C: Chain<DerIter = I>,
 {
-    type Item = Result<(Edge, usize), <C as Chain>::Error>;
+    type Item = Result<(Roi, usize), <C as Chain>::Error>;
 
     fn next(&mut self) -> Option<Self::Item> {
         if self.stop {
@@ -133,7 +180,11 @@ where
             match two_layer {
                 TwoLayers::One(edge, to) => Some(Ok((edge, to))),
                 TwoLayers::Two(label, forest_source, accepting, edges) => {
-                    let new_index = match self.chain.extend(edges.into_iter()) {
+                    let new_index = match self.chain.extend(
+                        edges
+                            .into_iter()
+                            .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, target))),
+                    ) {
                         Ok(new) => new,
                         Err(error) => {
                             // Prevent further iterations.
@@ -143,7 +194,10 @@ where
                         }
                     };
 
-                    Some(Ok((Edge::new(label, forest_source, accepting), new_index)))
+                    Some(Ok((
+                        Edge::new(label, forest_source, accepting).into(),
+                        new_index,
+                    )))
                 }
             }
         } else {
@@ -174,6 +228,14 @@ pub trait Chain: LabelExtGraph<Edge> {
     /// Update the history
     fn update_history(&mut self, new: usize);
 
+    /// Update the acceptance of a node, when and only when that node
+    /// turns out to have no children.
+    fn update_epsilon(
+        &mut self,
+        node_id: usize,
+        edges: impl Iterator<Item = (Roi, usize)>,
+    ) -> Result<(), Self::Error>;
+
     /// An iterator that iterates all layers that need to be merged.
     type DerIter: Iterator<Item = TwoLayers>;
 
@@ -181,10 +243,10 @@ pub trait Chain: LabelExtGraph<Edge> {
     fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error>;
 
     /// Take the union of all derivatives.
-    fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Edge, usize)>, Self::Error> {
+    fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Roi, usize)>, Self::Error> {
         // REVIEW: Find a way to avoid allocations.
         Collapsed::<_, Self>::collapse(der_iter, self)
-            .collect::<Result<Vec<(Edge, usize)>, Self::Error>>()
+            .collect::<Result<Vec<(Roi, usize)>, Self::Error>>()
             .map(|mut v| {
                 v.retain(|(_, target)| {
                     *target == 0 || matches!(self.degree(*target), Ok(deg) if deg != 0)
@@ -200,7 +262,15 @@ pub trait Chain: LabelExtGraph<Edge> {
 
         let edges = self.union(der_iter)?;
 
-        let new_index = self.extend(edges)?;
+        let new_index = self.extend(
+            edges
+                .iter()
+                .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, *target))),
+        )?;
+
+        if self.is_empty_node(new_index)? {
+            self.update_epsilon(new_index, edges.into_iter())?;
+        }
 
         self.update_history(new_index);