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, 137 insertions, 18 deletions

diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index 9ed3b74..43807f8 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -68,7 +68,7 @@ pub fn generate_fragment(
 }
 
 /// Generate a virtual fragment representing the left-linear null
-/// closure [nt]^t.
+/// closure \[nt\]^t.
 pub fn virtual_generate_fragment(
     atom: impl Borrow<DefaultAtom>,
     nt: usize,
@@ -130,12 +130,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
         let pase = label.forest_source();
 
-        let _fragment_root = if let Some(root) = fragment.root() {
+        let fragment_root = if let Some(root) = fragment.root() {
             root
         } else {
             return Err(Error::EmptyItem);
         };
 
+        let pos = fragment
+            .vertex_label(fragment_root)?
+            .ok_or(Error::NodeNoLabel(fragment_root))?
+            .label()
+            .start();
+
         // Ensure the last node in the PaSe is a terminal or a
         // non-terminal node, as an extra safety guard during
         // development.
@@ -236,26 +242,83 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             // locate the nodes
             for reduction_nt in reduction_info.iter().copied().flatten().rev() {
-                while let Some(node) = stack.pop() {
+                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()))?;
+
                     if matches!(
-                        self
-                            .vertex_label(node.node())?
-                            .ok_or_else(|| Error::NodeNoLabel(node.node()))?
+                        node_label
                             .label()
                             .label(),
                         GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt
                     ) {
-                        for parent in self.parents_of(node.node())? {
-                            debug_assert!(matches!(
-                                self.vertex_label(parent.node()),
-                                Ok(Some(label)) if
-                                    label
-                                    .label()
-                                    .label()
-                                    .rule()
-                                    .is_some()));
+                        // 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
+                            })?;
+                        }
+
+                        if node_label.clone_index().is_some() {
+                            let mut parent_iter = self.parents_of(node.node())?;
+
+                            #[cfg(debug_assertions)]
+                            assert_eq!(parent_iter.len(), 1);
+
+                            node = parent_iter.next().unwrap();
+
+                            #[cfg(debug_assertions)]
+                            assert!(self
+                                .vertex_label(node.node())?
+                                .ok_or_else(|| Error::NodeNoLabel(node.node()))?
+                                .is_packed());
+                        }
+
+                        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())?
+                                .ok_or_else(|| Error::NodeNoLabel(parent.node()))?
+                                .label();
+
+                            if parent_label.label().rule().is_none() {
+                                crate::item::default::print_labels(atom, self.borrow()).unwrap();
+                                self.print_viz("dbg forest.gv").unwrap();
+
+                                dbg!(parent, parent_label, label, 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()),
@@ -265,6 +328,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                                              Some(TNT::Non(_))))
                             }));
                         }
+
+                        for node in to_update {
+                            self.transform_label(node, |mut label| {
+                                label.set_end(pos + 1);
+                                label
+                            })?;
+                        }
                     }
                 }
 
@@ -293,7 +363,29 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             }
 
             for parent in stack.into_iter() {
-                if parent.edge() + 1 >= self.degree(parent.node())? {
+                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
+                    }
+                };
+
+                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 {
@@ -303,9 +395,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                         // do nothing
                         continue;
                     }
-                    dbg!("clone?");
 
-                    let cloned_node = self.clone_node(nth_child)?;
+                    // 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)?;
                 }
@@ -484,4 +585,22 @@ mod genins_test {
 
         Ok(())
     }
+
+    #[test]
+    fn test_reduction() -> Result<(), Box<dyn std::error::Error>> {
+        let grammar = new_paren_grammar()?;
+
+        let atom = DefaultAtom::from_grammar(grammar)?;
+
+        #[cfg(feature = "test-print-viz")]
+        atom.print_nfa("genins nfa.gv")?;
+
+        // querying reductions
+
+        println!("{:?}", atom.query_reduction(32, 17)?);
+
+        // assert!(matches!(atom.query_reduction(35, 25), Ok(Some(&[2]))));
+
+        Ok(())
+    }
 }