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.

1 files changed, 63 insertions, 37 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;