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.

2 files changed, 126 insertions, 158 deletions

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;
             }