1 files changed, 156 insertions, 31 deletions

diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index 851968c..237b92a 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -1,4 +1,3 @@
-#![allow(dead_code)]
 //! This module implements a function for "closing" and "splitting" a
 //! node in a forest, and hence the name.
 
@@ -20,6 +19,7 @@ fn get_rule_label(label: GrammarLabel) -> Option<usize> {
 }
 
 /// Existing or non-existing label.
+#[derive(Debug, Copy, Clone)]
 enum Eon {
     Ex(usize),
     Nex(ForestLabel<GrammarLabel>),
@@ -62,6 +62,12 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node]
     /// for details.
     ///
+    /// # `completingp`
+    ///
+    /// When we are completing the forest at the end, we do not wish
+    /// to keep the nodes at the end, so we pass a flag to inform the
+    /// function of this intention.
+    ///
     /// # Return
     ///
     /// The function returns the new, splitted or cloned node, or the
@@ -90,6 +96,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         node: usize,
         end: Option<usize>,
         edge_index: usize,
+        completingp: bool,
     ) -> Result<usize, Error> {
         let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
 
@@ -130,7 +137,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             || node_label.clone_index().is_some()
             || new_label.clone_index().is_some()
         {
-            return self.split_node(new_label, node, edge_index);
+            return self.split_node(new_label, node, edge_index, completingp);
         }
 
         // replace the label directly
@@ -151,6 +158,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 .ok_or(Error::NodeNoLabel(parent))?
                 .label();
 
+            if get_rule_label(parent_label).is_none() {
+                self.print_viz("dbg forest.gv").unwrap();
+                panic!("assumption fails");
+            }
+
             assert!(get_rule_label(parent_label).is_some());
             assert_eq!(builder.degree(parent)?, 1);
 
@@ -207,12 +219,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         new_label: ForestLabel<GrammarLabel>,
         mut node: usize,
         edge_index: usize,
+        completingp: bool,
     ) -> Result<usize, Error> {
         let end = new_label.label().end();
 
         let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
-        let mut new_node = builder.add_vertex(new_label);
+        let new_node = builder.add_vertex(new_label);
 
         let new_packed = if new_label.clone_index().is_some() {
             let packed = builder
@@ -261,7 +274,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                     .label();
 
                 assert!(get_rule_label(parent_label).is_some());
-                assert_eq!(self.degree(parent.node())?, 1);
+
+                if self.degree(parent.node())? != 1 {
+                    dbg!(parent);
+                    self.print_viz("dbg forest.gv").unwrap();
+
+                    panic!("assumption fails");
+                }
 
                 if let Some(pos) = end {
                     parent_label.set_end(pos);
@@ -276,11 +295,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 let new_parent = builder.add_vertex(parent_label);
 
                 if let Some(packed) = new_packed {
-                    new_node = packed;
+                    builder.add_edge(new_parent, packed, new_label)?;
+                } else {
+                    builder.add_edge(new_parent, new_node, new_label)?;
                 }
 
-                builder.add_edge(new_parent, new_node, new_label)?;
-
                 result.extend(
                     self.parents_of(parent.node())?
                         .map(|parent_parent| (parent_parent, new_parent)),
@@ -291,21 +310,48 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         };
 
         for (parent, new_child) in parents {
-            if self.has_same_children_until(
-                parent.node(),
-                parent.node(),
-                parent.edge(),
-                new_child,
-            )? {
-                continue;
-            }
+            if !completingp {
+                if self.has_same_children_until(
+                    parent.node(),
+                    parent.node(),
+                    parent.edge(),
+                    new_child,
+                )? {
+                    continue;
+                }
 
-            // we don't add a child to parent.edge() here.
-            let cloned = self.clone_node(parent.node(), parent.edge(), false)?;
+                // we don't add a child to parent.edge() here.
+                let cloned = self.clone_node(parent.node(), parent.edge(), false)?;
 
-            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
-            builder.add_edge(cloned, new_child, new_label)?;
+                builder.add_edge(cloned, new_child, new_label)?;
+            } else {
+                if self.has_same_children_except(
+                    parent.node(),
+                    parent.node(),
+                    parent.edge(),
+                    new_child,
+                )? {
+                    continue;
+                }
+
+                // we don't add a child to parent.edge() here.
+                let cloned = self.clone_node(parent.node(), parent.edge(), false)?;
+
+                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(new_node)
@@ -486,6 +532,85 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             unreachable!("should not examine children of a packed node")
         }
     }
+
+    /// Detect if a node has a branch that has the same children as
+    /// another node, except for 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_except(
+        &self,
+        nodea: usize,
+        nodeb: usize,
+        edge_index: usize,
+        alternative: usize,
+    ) -> Result<bool, Error> {
+        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() {
+                return Ok(false);
+            }
+
+            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);
+                    }
+                } else if childa != alternative {
+                    return Ok(false);
+                }
+            }
+
+            Ok(true)
+        } else if labela.clone_index().is_some() {
+            let mut parentsa = self.parents_of(nodea)?;
+
+            assert_eq!(parentsa.len(), 1);
+
+            let parenta = parentsa.next().unwrap().node();
+
+            'branch_loop: for branch in self.children_of(parenta)? {
+                let children_a = self.children_of(branch)?;
+                let children_b = children_b.clone();
+
+                if children_a.len() < children_b.len() {
+                    continue 'branch_loop;
+                }
+
+                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;
+                        }
+                    } else if childa != alternative {
+                        continue 'branch_loop;
+                    }
+                }
+
+                return Ok(true);
+            }
+
+            Ok(false)
+        } else {
+            // a packed node; this should not happen
+            unreachable!("should not examine children of a packed node")
+        }
+    }
 }
 
 #[cfg(test)]
@@ -688,7 +813,7 @@ mod test_splone {
     fn test() -> Result<(), Box<dyn std::error::Error>> {
         let mut test_forest = create_test_forest()?;
 
-        test_forest.splone(6, Some(3), 1)?;
+        test_forest.splone(6, Some(3), 1, false)?;
 
         let answer = splone_6_3_1()?;
 
@@ -698,7 +823,7 @@ mod test_splone {
             panic!("splone(6, Some(3), 1) produced wrong forest");
         }
 
-        test_forest.splone(6, Some(3), 1)?;
+        test_forest.splone(6, Some(3), 1, false)?;
 
         if test_forest != answer {
             test_forest.print_viz("sploned forest.gv")?;
@@ -706,7 +831,7 @@ mod test_splone {
             panic!("repeated splone(6, Some(3), 1) produced wrong forest");
         }
 
-        test_forest.splone(6, Some(2), 0)?;
+        test_forest.splone(6, Some(2), 0, false)?;
 
         let answer = splone_6_2_0()?;
 
@@ -716,7 +841,7 @@ mod test_splone {
             panic!("splone(6, Some(2), 0) produced wrong forest");
         }
 
-        test_forest.splone(6, Some(2), 0)?;
+        test_forest.splone(6, Some(2), 0, false)?;
 
         if test_forest != answer {
             test_forest.print_viz("sploned forest.gv")?;
@@ -724,7 +849,7 @@ mod test_splone {
             panic!("repeated splone(6, Some(2), 0) produced wrong forest");
         }
 
-        test_forest.splone(6, None, 0)?;
+        test_forest.splone(6, None, 0, false)?;
 
         let answer = splone_6_n_0()?;
 
@@ -734,7 +859,7 @@ mod test_splone {
             panic!("splone(6, None, 0) produced wrong forest");
         }
 
-        test_forest.splone(14, None, 0)?;
+        test_forest.splone(14, None, 0, false)?;
 
         if test_forest != answer {
             test_forest.print_viz("sploned forest.gv")?;
@@ -742,7 +867,7 @@ mod test_splone {
             panic!("repeated splone(6, None, 0) produced wrong forest");
         }
 
-        test_forest.splone(4, Some(3), 0)?;
+        test_forest.splone(4, Some(3), 0, false)?;
 
         let answer = splone_4_3_0()?;
 
@@ -752,7 +877,7 @@ mod test_splone {
             panic!("splone(4, Some(3), 0) produced wrong forest");
         }
 
-        test_forest.splone(4, Some(3), 0)?;
+        test_forest.splone(4, Some(3), 0, false)?;
 
         if test_forest != answer {
             test_forest.print_viz("sploned forest.gv")?;
@@ -760,8 +885,8 @@ mod test_splone {
             panic!("repeated splone(4, Some(3), 0) produced wrong forest");
         }
 
-        test_forest.splone(17, Some(3), 0)?;
-        test_forest.splone(15, Some(3), 0)?;
+        test_forest.splone(17, Some(3), 0, false)?;
+        test_forest.splone(15, Some(3), 0, false)?;
 
         let answer = splone_17_3_0_15_3_0()?;
 
@@ -771,8 +896,8 @@ mod test_splone {
             panic!("splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest");
         }
 
-        test_forest.splone(17, Some(3), 0)?;
-        test_forest.splone(15, Some(3), 0)?;
+        test_forest.splone(17, Some(3), 0, false)?;
+        test_forest.splone(15, Some(3), 0, false)?;
 
         if test_forest != answer {
             test_forest.print_viz("sploned forest.gv")?;