splone: splitting parents properly.

* chain/src/item/default/splone.rs: Previouslt the function
  `split_node` used to split the parents of splitted nodes by an ugly
  logic.  Now that is moved into a dedicated function, which properly
  handles the splitting of parents, including the case when the new
  node is open whereas the old node is closed, in which situation we
  ought to put the new node under the opened node only, as a closed
  node cannot contain an open node as a child by definition.

1 files changed, 283 insertions, 118 deletions

diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index c73bd9f..2ac3d73 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -137,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, completingp);
+            return self.split_node(new_label, node_label, node, edge_index, completingp);
         }
 
         self.replace_label(node, new_label)?;
@@ -231,7 +231,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             }
         };
 
-        let splitted = self.split_node(new_label, node, edge_index, false)?;
+        let splitted = self.split_node(new_label, node_label, node, edge_index, false)?;
 
         self.plant(splitted, fragment, planted)?;
 
@@ -270,11 +270,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             assert_eq!(builder.degree(parent)?, 1);
 
-            if let Some(pos) = end {
-                parent_label.set_end(pos);
-            } else {
-                parent_label.open_end();
-            }
+            parent_label.set_end_option(end);
 
             let parent_label = ForestLabel::from(parent_label);
 
@@ -301,6 +297,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     fn split_node(
         &mut self,
         new_label: ForestLabel<GrammarLabel>,
+        old_label: ForestLabel<GrammarLabel>,
         mut node: usize,
         edge_index: usize,
         completingp: bool,
@@ -348,115 +345,28 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             return Ok(new_node);
         }
 
-        let parents: Vec<_> = {
-            if let Some(label) = self.vertex_label(node)? {
-                if label.clone_index().is_some() {
-                    let mut parents = self.parents_of(node)?;
-                    assert_eq!(parents.len(), 1);
-                    node = parents.next().unwrap().node();
-                }
-            }
-
-            let parents: Vec<_> = self.parents_of(node)?.collect();
-
-            let mut result: Vec<(Parent, usize)> = Vec::with_capacity(
-                parents
-                    .iter()
-                    .map(|parent| {
-                        self.parents_of(parent.node())
-                            .map(|iter| iter.len())
-                            .unwrap_or(0)
-                    })
-                    .sum(),
-            );
-
-            for parent in parents {
-                let mut parent_label = self
-                    .vertex_label(parent.node())?
-                    .ok_or_else(|| Error::NodeNoLabel(parent.node()))?
-                    .label();
-
-                assert!(get_rule_label(parent_label).is_some());
-
-                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);
-                } else {
-                    parent_label.open_end();
-                }
-
-                let parent_label = ForestLabel::from(parent_label);
-
-                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
-
-                let new_parent = builder.add_vertex(parent_label);
-
-                if let Some(packed) = new_packed {
-                    builder.add_edge(new_parent, packed, new_label)?;
-                } else {
-                    builder.add_edge(new_parent, new_node, new_label)?;
-                }
-
-                result.extend(
-                    self.parents_of(parent.node())?
-                        .map(|parent_parent| (parent_parent, new_parent)),
-                );
-            }
-
-            result
-        };
-
-        for (parent, new_child) in parents {
-            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)?;
-
-                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
-
-                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();
+        // We actually have to consider two cases here: one when the
+        // new end is closed, and the other when the new end is open
+        // and the new node is a plain node.
+        //
+        // The former case can be dealt with by cloning the parent,
+        // whereas the latter needs to open the parents recursively
+        // until it meets an open node.
 
-                for child in children_to_add {
-                    builder.add_edge(cloned, child, new_label)?;
-                }
-            }
+        if old_label.clone_index().is_some() {
+            let mut parents = self.parents_of(node)?;
+            assert_eq!(parents.len(), 1);
+            node = parents.next().unwrap().node();
         }
 
+        self.split_parents(
+            node,
+            old_label,
+            end,
+            new_packed.unwrap_or(new_node),
+            completingp,
+        )?;
+
         Ok(new_node)
     }
 
@@ -500,11 +410,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             .ok_or(Error::NodeNoLabel(node))?
             .label();
 
-        if let Some(pos) = end {
-            copied_label.set_end(pos);
-        } else {
-            copied_label.open_end();
-        }
+        copied_label.set_end_option(end);
 
         let label = ForestLabel::new(copied_label, ForestLabelType::Packed);
 
@@ -681,6 +587,265 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         Ok(Some(node))
     }
 
+    /// Split the parents of `node`.
+    ///
+    /// We have created a new node `new_node`, and now we want to
+    /// adjoin it to /proper/ parents so that the labels of parents
+    /// match.
+    ///
+    /// In particular, the rule parents of the old node should have
+    /// the new counter-parts and should be parents of the new node.
+    ///
+    /// Moreover, if the new label is open, we demand that every
+    /// ancestor of the new node be open as well, as a closed node
+    /// cannot contain an open node by definition.
+    fn split_parents(
+        &mut self,
+        node: usize,
+        label: ForestLabel<GrammarLabel>,
+        end: Option<usize>,
+        new_node: usize,
+        completingp: bool,
+    ) -> Result<(), Error> {
+        // First handle the rule parents.
+
+        let parents: Vec<usize> = self.parents_of(node)?.map(|parent| parent.node()).collect();
+
+        let mut ancestors: Vec<(Parent, usize)> = Vec::with_capacity(
+            parents
+                .iter()
+                .copied()
+                .map(|parent| self.parents_of(parent).map_or(0, |iter| iter.len()))
+                .sum(),
+        );
+
+        for parent in parents {
+            let mut parent_label = self
+                .vertex_label(parent)?
+                .ok_or_else(|| Error::NodeNoLabel(parent))?
+                .label();
+
+            #[cfg(debug_assertions)]
+            {
+                assert!(
+                    matches!(parent_label.label(), GrammarLabelType::Rule(_)),
+                    "this should be a rule parent"
+                );
+
+                if self.degree(parent)? != 1 {
+                    dbg!(parent);
+                    let _ = self.print_viz("dbg forest.gv");
+
+                    panic!("a rule node should not have more than one child");
+                }
+            }
+
+            parent_label.set_end_option(end);
+
+            let parent_label = ForestLabel::from(parent_label);
+
+            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+            let new_parent = builder.add_vertex(parent_label);
+
+            builder.add_edge(new_parent, new_node, label)?;
+
+            // Open all closed parents if necessary.
+            // dbg!(new_node, label, parent, new_parent, end);
+
+            if end.is_none() {
+                let opened = self.open_ancestors(parent, new_parent)?;
+
+                // dbg!(&opened);
+
+                ancestors.extend(opened);
+            } else {
+                ancestors.extend(
+                    self.parents_of(parent)?
+                        .map(|parent_parent| (parent_parent, new_parent)),
+                );
+            }
+        }
+
+        // Now clone and add edges, if necessary.
+
+        for (parent, new_child) in ancestors {
+            if !completingp {
+                if self.has_same_children_until(
+                    parent.node(),
+                    parent.node(),
+                    parent.edge(),
+                    new_child,
+                )? {
+                    continue;
+                }
+
+                // we add no child to parent.edge()-th child here.
+                let cloned = self.clone_node(parent.node(), parent.edge(), false)?;
+
+                dbg!(cloned, parent, new_child);
+
+                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                builder.add_edge(cloned, new_child, label)?;
+            } else {
+                if self.has_same_children_except(
+                    parent.node(),
+                    parent.node(),
+                    parent.edge(),
+                    new_child,
+                )? {
+                    continue;
+                }
+
+                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, 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, label)?;
+                }
+            }
+        }
+
+        Ok(())
+    }
+
+    /// Open all closed ancestors.
+    fn open_ancestors(
+        &mut self,
+        parent: usize,
+        new_parent: usize,
+    ) -> Result<Vec<(Parent, usize)>, Error> {
+        let mut result = Vec::new();
+
+        let mut stack: Vec<_> = vec![(parent, new_parent)];
+
+        while let Some((top, new_top)) = stack.pop() {
+            // dbg!(top, new_top);
+            let parents: Vec<_> = self.parents_of(top)?.collect();
+
+            'parent_loop: for parent in parents {
+                // dbg!(parent);
+
+                let parent_node = parent.node();
+                let parent_edge = parent.edge();
+                let parent_label = self
+                    .vertex_label(parent_node)?
+                    .ok_or(Error::NodeNoLabel(parent_node))?
+                    .label();
+
+                if parent_label.end().is_some() {
+                    let new_label = self.create_new_label(parent_node, None, parent_edge, None)?;
+
+                    let new_label = match new_label {
+                        Eon::Nex(label) => label,
+                        Eon::Ex(ex_node) => {
+                            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                            builder.add_edge(ex_node, new_top, parent_label.into())?;
+
+                            continue 'parent_loop;
+                        }
+                    };
+
+                    let new_node_is_clone = new_label.clone_index().is_some();
+
+                    let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                    let new_node = builder.add_vertex(new_label);
+
+                    let new_packed = if new_node_is_clone {
+                        let packed = builder
+                            .query_label(ForestLabel::new(
+                                new_label.label(),
+                                ForestLabelType::Packed,
+                            ))
+                            .unwrap_or_else(|| {
+                                panic!("A cloned node {new_node} without packed nodes")
+                            });
+
+                        builder.add_edge(packed, new_node, new_label)?;
+
+                        Some(packed)
+                    } else {
+                        builder.add_edge(new_node, new_top, new_label)?;
+                        None
+                    };
+
+                    let preserve_children: Vec<_> = builder
+                        .children_of(parent_node)?
+                        .take(parent_edge)
+                        .collect();
+
+                    for child in preserve_children {
+                        builder.add_edge(new_node, child, new_label)?;
+                    }
+
+                    if new_node_is_clone {
+                        continue 'parent_loop;
+                    }
+
+                    // Now deal with new rule parents.
+
+                    let rule_parents: Vec<_> = builder
+                        .parents_of(parent_node)?
+                        .map(|parent| parent.node())
+                        .collect();
+
+                    for rule_parent in rule_parents {
+                        let mut rule_parent_label = self
+                            .vertex_label(rule_parent)?
+                            .ok_or_else(|| Error::NodeNoLabel(rule_parent))?
+                            .label();
+
+                        #[cfg(debug_assertions)]
+                        {
+                            assert!(
+                                matches!(rule_parent_label.label(), GrammarLabelType::Rule(_)),
+                                "this should be a rule parent"
+                            );
+
+                            if self.degree(rule_parent)? != 1 {
+                                dbg!(rule_parent);
+                                let _ = self.print_viz("dbg forest.gv");
+
+                                panic!("a rule node should not have more than one child");
+                            }
+                        }
+
+                        rule_parent_label.set_end_option(None);
+
+                        let parent_label = ForestLabel::from(rule_parent_label);
+
+                        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+                        let new_rule_parent = builder.add_vertex(parent_label);
+
+                        builder.add_edge(
+                            new_rule_parent,
+                            new_packed.unwrap_or(new_node),
+                            parent_label,
+                        )?;
+
+                        stack.push((rule_parent, new_rule_parent));
+                    }
+                } else {
+                    result.push((parent, new_top));
+                }
+            }
+        }
+
+        Ok(result)
+    }
+
     /// Compare if two nodes have the same children in the same order.
     fn has_same_children(
         &self,