Added the functionality of split or clone.

I need more than the ability to clone nodes: I also need to split the
nodes.  Now this seems to be correctly added.

1 files changed, 760 insertions, 0 deletions

diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
new file mode 100644
index 0000000..1168539
--- /dev/null
+++ b/chain/src/item/default/splone.rs
@@ -0,0 +1,760 @@
+//! This module implements a function for "closing" and "splitting" a
+//! node in a forest, and hence the name.
+
+use super::*;
+use grammar::TNT;
+
+fn get_nt_label(label: GrammarLabel) -> Option<usize> {
+    match label.label() {
+        GrammarLabelType::TNT(TNT::Non(nt)) => Some(nt),
+        _ => None,
+    }
+}
+
+fn get_rule_label(label: GrammarLabel) -> Option<usize> {
+    match label.label() {
+        GrammarLabelType::Rule(rule) => Some(rule),
+        _ => None,
+    }
+}
+
+impl DefaultForest<ForestLabel<GrammarLabel>> {
+    /// Either "open split" or "closed split".
+    ///
+    /// An open split is an attempt to set the end of the node to
+    /// `None`, and a closed split is an attempt to set the end to a
+    /// specific position.
+    ///
+    /// Also this function preserves `edge_index + 1` many children
+    /// when splitting or cloning.
+    ///
+    /// To be more precise, this function performs the following
+    /// actions:
+    ///
+    /// 1. Make sure it is labelled by a nonterminal.
+    ///
+    /// 2. Check the status of the node.  If it is packed, return an
+    /// error.
+    ///
+    /// 3. Make a new label according to the given `end`.  See the
+    /// function
+    /// [`create_new_label`][DefaultForest::<ForestLabel<GrammarLabel>>::create_new_label]
+    /// for the process of making new labels.
+    ///
+    /// 4. If the new label is equal to the old label, and if
+    /// `edge_index + 1` is equal to the degree of the node, then do
+    /// nothing.
+    ///
+    /// 5. If the new label is equal to the old label but
+    /// `edge_index+1` is not equal to the degree of the node, then
+    /// clone the node while preserving `edge_index + 1` many
+    /// children.
+    ///
+    /// 6. If the new label is not equal to the old label, then split
+    /// the node. See the function
+    /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node]
+    /// for details.
+    ///
+    /// # Name
+    ///
+    /// The name is a mixture of *split* and *clone*.
+    ///
+    /// # NOTE
+    ///
+    /// We want to "do the same thing" to each parent of the node,
+    /// that should be checked to be labelled by a rule position.
+    ///
+    /// That is to say, if we replace the label of the node, we also
+    /// replace the label of the "rule parent".  If we split the node,
+    /// the rule parents are also splitted in a parallel manner with
+    /// the splitted node.
+    ///
+    /// Also, when we refer to the parents of the node in the
+    /// 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> {
+        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() {
+            return Err(Error::SplitPack(node));
+        }
+
+        let node_end = node_label.label().end();
+        let node_degree = self.degree(node)?;
+
+        // 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(());
+            }
+
+            dbg!();
+            self.clone_node(node, edge_index + 1, false)?;
+
+            return Ok(());
+        }
+
+        let new_label = self.create_new_label(node, end, edge_index)?;
+
+        let new_label = if let Some(label) = new_label {
+            label
+        } else {
+            return Ok(());
+        };
+
+        if node_end.is_some()
+            || edge_index + 1 != node_degree
+            || node_label.clone_index().is_some()
+            || new_label.clone_index().is_some()
+        {
+            return self.split_node(new_label, node, edge_index);
+        }
+
+        // replace the label directly
+
+        // if new_label.clone_index().is_none() {
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+        builder.set_label(node, new_label)?;
+
+        let parents: Vec<_> = builder
+            .parents_of(node)?
+            .map(|parent| parent.node())
+            .collect();
+
+        for parent in parents {
+            let mut parent_label = builder
+                .vertex_label(parent)?
+                .ok_or(Error::NodeNoLabel(parent))?
+                .label();
+
+            assert!(get_rule_label(parent_label).is_some());
+            assert_eq!(builder.degree(parent)?, 1);
+
+            if let Some(pos) = end {
+                parent_label.set_end(pos);
+            } else {
+                parent_label.open_end();
+            }
+
+            let parent_label = ForestLabel::from(parent_label);
+
+            builder.set_label(parent, parent_label)?;
+        }
+        // } else {
+        //     // REVIEW: Call `split_node` in this situation as well?
+
+        //     // If we are here, the new label should have a packed
+        //     // parent.
+        //     let packed = self
+        //         .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed))
+        //         .unwrap();
+
+        //     let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+        //     builder.set_label(node, new_label)?;
+
+        //     let parents: Vec<_> = builder.parents_of(node)?.collect();
+
+        //     for parent in parents.iter() {
+        //         builder.redirect(parent.node(), parent.edge(), packed)?;
+        //     }
+
+        //     builder.add_edge(packed, node, new_label)?;
+        // }
+
+        Ok(())
+    }
+
+    /// Procedure to split the node:
+    ///
+    /// 1. Create a new node with the new label.
+    ///
+    /// 2. Preserve the old children as specified by `edge_index + 1`.
+    ///
+    /// 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.
+    fn split_node(
+        &mut self,
+        new_label: ForestLabel<GrammarLabel>,
+        mut node: usize,
+        edge_index: usize,
+    ) -> Result<(), 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_packed = if new_label.clone_index().is_some() {
+            let packed = builder
+                .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed))
+                .unwrap();
+
+            builder.add_edge(packed, new_node, new_label)?;
+
+            Some(packed)
+        } else {
+            None
+        };
+
+        let preserve_children: Vec<_> = builder.children_of(node)?.take(edge_index + 1).collect();
+
+        for child in preserve_children {
+            builder.add_edge(new_node, child, new_label)?;
+        }
+
+        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());
+                assert_eq!(self.degree(parent.node())?, 1);
+
+                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 {
+                    new_node = packed;
+                }
+
+                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 self.has_same_children_but_one(
+                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(())
+    }
+
+    /// Procedure for the new label:
+    ///
+    /// 1. Copy the old label.
+    ///
+    /// 2. Set the end to `pos`.
+    ///
+    /// 3. Pack the label.
+    ///
+    /// 4. Check if this label already exists.  If so, clone the label and
+    /// return it.
+    ///
+    /// 5. Else set the label to be a plain label.
+    ///
+    /// 6. Check if this plain label already exists.  If so, clone the
+    /// existing label, and return the clone of the cloned label.
+    ///
+    /// 7. Else return the plain label.
+    fn create_new_label(
+        &mut self,
+        node: usize,
+        end: Option<usize>,
+        edge_index: usize,
+    ) -> Result<Option<ForestLabel<GrammarLabel>>, Error> {
+        let mut copied_label = self
+            .vertex_label(node)?
+            .ok_or(Error::NodeNoLabel(node))?
+            .label();
+
+        if let Some(pos) = end {
+            copied_label.set_end(pos);
+        } else {
+            copied_label.open_end();
+        }
+
+        let label = ForestLabel::new(copied_label, ForestLabelType::Packed);
+
+        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);
+                }
+            }
+
+            let mut packed_children = self.children_of(packed)?;
+
+            let first_child = packed_children.next().unwrap();
+
+            let clone_index = self.clone_node(first_child, 0, true)?;
+
+            Ok(Some(ForestLabel::new(
+                copied_label,
+                ForestLabelType::Cloned(clone_index),
+            )))
+        } else {
+            let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);
+
+            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);
+                }
+
+                let clone_index = self.clone_node(existing, 0, true)?;
+
+                Ok(Some(ForestLabel::new(
+                    copied_label,
+                    ForestLabelType::Cloned(clone_index),
+                )))
+            } else {
+                Ok(Some(plain_label))
+            }
+        }
+    }
+
+    /// Compare if two nodes have the same children in the same order.
+    fn has_same_children(
+        &self,
+        nodea: usize,
+        nodeb: usize,
+        edge_num_a: usize,
+        edge_num_b: usize,
+    ) -> Result<bool, Error> {
+        let children_a = self.children_of(nodea)?.take(edge_num_a);
+        let children_b = self.children_of(nodeb)?.take(edge_num_b);
+
+        if children_a.len() != children_b.len() {
+            return Ok(false);
+        }
+
+        for (childa, childb) in children_a.zip(children_b) {
+            if childa != childb {
+                return Ok(false);
+            }
+        }
+
+        Ok(true)
+    }
+
+    /// 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(
+        &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 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).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).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)]
+mod test_splone {
+    use super::*;
+
+    use grammar::TNT::*;
+
+    fn create_test_forest(
+    ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> {
+        let mut forest = leaf!(GrammarLabel::new(Non(0), 0), GrammarLabel);
+
+        forest.plant(
+            0,
+            leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel),
+            false,
+        )?;
+        forest.plant(
+            1,
+            leaf!(GrammarLabel::new_closed(Ter(0), 0, 1), GrammarLabel),
+            false,
+        )?;
+
+        forest.plant(0, leaf!(GrammarLabel::new(7, 1), GrammarLabel), false)?;
+        forest.plant(3, leaf!(GrammarLabel::new(Non(0), 1), GrammarLabel), false)?;
+
+        forest.plant(4, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?;
+        forest.plant(5, leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel), false)?;
+
+        forest.plant(
+            6,
+            leaf!(GrammarLabel::new_closed(11, 1, 2), GrammarLabel),
+            false,
+        )?;
+        forest.plant(
+            7,
+            leaf!(GrammarLabel::new_closed(Ter(2), 1, 2), GrammarLabel),
+            false,
+        )?;
+
+        forest.plant(
+            6,
+            leaf!(GrammarLabel::new_closed(13, 2, 3), GrammarLabel),
+            false,
+        )?;
+        forest.plant(
+            9,
+            leaf!(GrammarLabel::new_closed(Ter(2), 2, 3), GrammarLabel),
+            false,
+        )?;
+
+        forest.print_viz("test forest.gv")?;
+
+        Ok(forest)
+    }
+
+    fn splone_6_3_1() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+    {
+        let mut forest = create_test_forest()?;
+
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);
+
+        builder.set_label(
+            5,
+            ForestLabel::new(GrammarLabel::new_closed(3, 1, 3), ForestLabelType::Plain),
+        )?;
+
+        builder.set_label(
+            6,
+            ForestLabel::new(
+                GrammarLabel::new_closed(Non(1), 1, 3),
+                ForestLabelType::Plain,
+            ),
+        )?;
+
+        Ok(forest)
+    }
+
+    fn splone_6_2_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+    {
+        let mut forest = splone_6_3_1()?;
+
+        let cloned = forest.clone_node(4, 0, false)?;
+
+        forest.plant(
+            cloned,
+            leaf!(GrammarLabel::new_closed(3, 1, 2), GrammarLabel),
+            false,
+        )?;
+
+        forest.plant(
+            cloned + 1,
+            leaf!(GrammarLabel::new_closed(Non(1), 1, 2), GrammarLabel),
+            false,
+        )?;
+
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);
+
+        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));
+
+        builder.add_edge(cloned + 2, 7, dummy_label)?;
+
+        Ok(forest)
+    }
+
+    fn splone_6_n_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+    {
+        let mut forest = splone_6_2_0()?;
+
+        let cloned = forest.clone_node(4, 0, false)?;
+
+        forest.plant(cloned, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?;
+
+        forest.plant(
+            cloned + 1,
+            leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel),
+            false,
+        )?;
+
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);
+
+        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));
+
+        builder.add_edge(cloned + 2, 7, dummy_label)?;
+
+        Ok(forest)
+    }
+
+    fn splone_4_3_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+    {
+        let mut forest = splone_6_n_0()?;
+
+        let cloned = forest.clone_node(0, 0, false)?;
+
+        forest.plant(
+            cloned,
+            leaf!(GrammarLabel::new_closed(7, 1, 3), GrammarLabel),
+            false,
+        )?;
+
+        forest.plant(
+            cloned + 1,
+            leaf!(GrammarLabel::new_closed(Non(0), 1, 3), GrammarLabel),
+            false,
+        )?;
+
+        forest.plant(
+            cloned,
+            leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel),
+            true,
+        )?;
+
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);
+
+        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));
+
+        builder.add_edge(cloned + 2, 5, dummy_label)?;
+
+        Ok(forest)
+    }
+
+    fn splone_17_3_0_15_3_0(
+    ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> {
+        let mut forest = splone_4_3_0()?;
+
+        let to_clone = forest
+            .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(1), 1, 3)))
+            .unwrap();
+
+        let cloned = forest.clone_node(to_clone, 0, false)?;
+
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);
+
+        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));
+
+        let child = builder
+            .query_label(ForestLabel::from(GrammarLabel::new_closed(11, 1, 2)))
+            .unwrap();
+
+        builder.add_edge(cloned, child, dummy_label)?;
+
+        let to_clone = forest
+            .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(0), 1, 3)))
+            .unwrap();
+
+        let cloned = forest.clone_node(to_clone, 0, false)?;
+
+        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);
+
+        let child = builder
+            .query_label(ForestLabel::from(GrammarLabel::new(3, 1)))
+            .unwrap();
+
+        builder.add_edge(cloned, child, dummy_label)?;
+
+        Ok(forest)
+    }
+
+    #[test]
+    fn test() -> Result<(), Box<dyn std::error::Error>> {
+        let mut test_forest = create_test_forest()?;
+
+        test_forest.splone(6, Some(3), 1)?;
+
+        let answer = splone_6_3_1()?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 6 3 1.gv")?;
+            panic!("splone(6, Some(3), 1) produced wrong forest");
+        }
+
+        test_forest.splone(6, Some(3), 1)?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 6 3 1.gv")?;
+            panic!("repeated splone(6, Some(3), 1) produced wrong forest");
+        }
+
+        test_forest.splone(6, Some(2), 0)?;
+
+        let answer = splone_6_2_0()?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 6 2 0.gv")?;
+            panic!("splone(6, Some(2), 0) produced wrong forest");
+        }
+
+        test_forest.splone(6, Some(2), 0)?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 6 2 0.gv")?;
+            panic!("repeated splone(6, Some(2), 0) produced wrong forest");
+        }
+
+        test_forest.splone(6, None, 0)?;
+
+        let answer = splone_6_n_0()?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 6 None 0.gv")?;
+            panic!("splone(6, None, 0) produced wrong forest");
+        }
+
+        test_forest.splone(14, None, 0)?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 6 None 0.gv")?;
+            panic!("repeated splone(6, None, 0) produced wrong forest");
+        }
+
+        test_forest.splone(4, Some(3), 0)?;
+
+        let answer = splone_4_3_0()?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 4 3 0.gv")?;
+            panic!("splone(4, Some(3), 0) produced wrong forest");
+        }
+
+        test_forest.splone(4, Some(3), 0)?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 4 3 0.gv")?;
+            panic!("repeated splone(4, Some(3), 0) produced wrong forest");
+        }
+
+        test_forest.splone(17, Some(3), 0)?;
+        test_forest.splone(15, Some(3), 0)?;
+
+        let answer = splone_17_3_0_15_3_0()?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 17 3 0 15 3 0.gv")?;
+            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)?;
+
+        if test_forest != answer {
+            test_forest.print_viz("sploned forest.gv")?;
+            answer.print_viz("splone 17 3 0 15 3 0.gv")?;
+            panic!(
+                "repeated splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest"
+            );
+        }
+
+        Ok(())
+    }
+}