before a major refactor

I decide to adopt a new approach of recording and updating item
derivation forests.  Since this affects a lot of things, I decide to
commit before the refactor, so that I can create a branch for that
refactor.

1 files changed, 370 insertions, 124 deletions

diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index 4c51d9a..feb45c6 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -7,19 +7,24 @@
 //! semirings later on.
 
 use super::*;
-use crate::{atom::DefaultAtom, default::Error, item::default::DefaultForest, Edge};
+use crate::{
+    atom::{Atom, DefaultAtom},
+    default::Error,
+    item::default::DefaultForest,
+    Edge,
+};
 use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT};
-use graph::Graph;
+#[allow(unused_imports)]
+use graph::{builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, RedirectGraph};
 
 use core::borrow::Borrow;
-use std::collections::HashSet as Set;
 
 /// Convert an error telling us that an index is out of bounds.
 ///
 /// # Panics
 ///
 /// The function panics if the error is not of the expected kind.
-fn index_out_of_bounds_conversion(ge: GrammarError) -> Error {
+pub(crate) fn index_out_of_bounds_conversion(ge: GrammarError) -> Error {
     match ge {
         GrammarError::IndexOutOfBounds(index, bound) => Error::IndexOutOfBounds(index, bound),
         _ => Error::Invalid,
@@ -105,11 +110,6 @@ pub fn virtual_generate_fragment(
                     Some(TNT::Ter(ter)) if ter == t)
         {
             for child in child_iter {
-                // #[allow(unused_must_use)]
-                // {
-                //     dbg!(non_start, child, atom.query_expansion(non_start, child));
-                // }
-
                 let line: Vec<GrammarLabelType> = atom
                     .query_expansion(non_start, child)
                     .map_err(index_out_of_bounds_conversion)?
@@ -124,7 +124,15 @@ pub fn virtual_generate_fragment(
                 if result.is_empty() {
                     result = generate_fragment(line, pos)?;
                 } else {
-                    result.plant(0, generate_fragment(line, pos)?, false)?;
+                    let mut new_fragment = generate_fragment(line, pos)?;
+
+                    new_fragment.remove_node(0)?;
+
+                    new_fragment.set_root(1)?;
+
+                    let cloned = result.clone_node(0, 0, false)?;
+
+                    result.plant(cloned, new_fragment, false)?;
                 }
             }
         }
@@ -133,90 +141,313 @@ pub fn virtual_generate_fragment(
     Ok(result)
 }
 
+// TODO: Examine `insert_item` again.
+
 impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// Insert an item derivation forest into a recording forest.
     ///
     /// We need the help of other things just for finding the correct
     /// places to insert these item fragments.
-    pub fn insert_item(
+    pub(crate) fn insert_item(
         &mut self,
         label: Edge,
         fragment: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>,
-        atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator,
+        atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator + Clone,
         atom: &DefaultAtom,
-    ) -> Result<PaSe, Error> {
-        let fragment = fragment.borrow();
+    ) -> Result<PaVi, Error> {
+        let root = if let Some(root) = self.root() {
+            root
+        } else {
+            panic!("the forest must be non-empty when we insert items");
+        };
+
+        let pavi = label.forest_source();
 
-        let pase = label.forest_source();
+        let true_source = label.true_source();
+
+        let fragment = fragment.borrow();
 
         let fragment_root = if let Some(root) = fragment.root() {
             root
         } else {
-            return Err(Error::EmptyItem);
+            unreachable!("empty item");
         };
 
-        let pos = fragment
+        let fragment_root_label = fragment
             .vertex_label(fragment_root)?
-            .ok_or(Error::NodeNoLabel(fragment_root))?
-            .label()
-            .start();
+            .ok_or(Error::NodeNoLabel(fragment_root))?;
+
+        let pos = fragment_root_label.label().start();
+
+        if pavi != true_source {
+            dbg!(label, pos);
+
+            // Completing from true_source up to the pavi
+            let true_source_node = match true_source {
+                PaVi::Parent(node, edge) => {
+                    let nth_child = self.nth_child(node, edge)?;
+                    let nth_child_label = self
+                        .vertex_label(nth_child)?
+                        .ok_or(Error::NodeNoLabel(nth_child))?;
+
+                    let nth_child_degree = self.degree(nth_child)?;
+                    let nth_child_last = if nth_child_degree > 0 {
+                        nth_child_degree - 1
+                    } else {
+                        0
+                    };
+
+                    if matches!(nth_child_label.label().label().tnt(), Some(TNT::Non(_)))
+                        && !nth_child_label.is_packed()
+                    {
+                        let sploned = self.splone(nth_child, Some(pos), nth_child_last, false)?;
+
+                        sploned
+                    } else {
+                        nth_child
+                    }
+                }
+                PaVi::Virtual(nt, t, mut node) => {
+                    let node_label_start = self
+                        .vertex_label(node)?
+                        .ok_or(Error::NodeNoLabel(node))?
+                        .label()
+                        .start();
+
+                    let reduction_fragment = atom.generate_virtual_frags(nt, t, None);
+
+                    // FIXME: We shall "close" this fragment as well.
+
+                    for frag in reduction_fragment.into_iter().flatten() {
+                        let mut frag = frag.clone();
+                        frag.set_pos(node_label_start)?;
+
+                        // NOTE: The function `plant_if_needed`
+                        // assumes that we want to plant the fragment
+                        // as the first child of the node.  This
+                        // assumption holds in this case, but not in
+                        // general.
+
+                        node = self.plant_if_needed(node, frag)?;
+                    }
+
+                    node
+                }
+                PaVi::Empty => {
+                    dbg!();
+                    root
+                }
+            };
+
+            let true_source_pos = self
+                .vertex_label(true_source_node)?
+                .ok_or(Error::NodeNoLabel(true_source_node))?
+                .label()
+                .start();
+
+            let top_node = match pavi {
+                PaVi::Parent(node, edge) => self.nth_child(node, edge)?,
+                PaVi::Virtual(_nt, _t, _node) => {
+                    dbg!(label);
+
+                    self.print_viz("dbg forest.gv").unwrap();
+                    fragment.print_viz("dbg fragment.gv").unwrap();
+
+                    unreachable!("I do not think this is possible")
+                }
+                PaVi::Empty => {
+                    unreachable!("The empty segment should not need to be reduced")
+                }
+            };
+
+            let mut stack = vec![vec![(top_node, 0)]];
+            let mut result_stack = Vec::new();
+
+            while let Some(mut top_stack) = stack.pop() {
+                let (node, _) = top_stack.pop().unwrap();
+
+                let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
+
+                if node_label.is_packed() {
+                    for node in self.children_of(node)? {
+                        let search_child = self.position_search(node, true_source_pos)?;
+
+                        if let Some((child, index)) = search_child {
+                            let mut top_stack = top_stack.clone();
+                            // Fix the previous element
+                            top_stack.push((node, index));
+
+                            if child == true_source_node {
+                                result_stack.push(top_stack);
+                            } else {
+                                top_stack.push((child, 0));
+
+                                stack.push(top_stack);
+                            }
+                        }
+                    }
+                } else {
+                    let search_child = self.position_search(node, true_source_pos)?;
+
+                    if let Some((child, index)) = search_child {
+                        top_stack.push((node, index));
+
+                        if child == true_source_node {
+                            result_stack.push(top_stack);
+                        } else {
+                            top_stack.push((child, 0));
+
+                            stack.push(top_stack);
+                        }
+                    }
+                }
+            }
+
+            // FIXME: We have to change the pavi as well, otherwise we
+            // are going to use the wrong branch for planting later.
+
+            for stack in result_stack {
+                // dbg!(&stack);
+                // self.print_viz("dbg forest.gv").unwrap();
+                // panic!("test");
+
+                let mut first_time = true;
+
+                for (node, index) in stack.into_iter().rev() {
+                    if matches!(
+                        self.vertex_label(node)?
+                            .ok_or(Error::NodeNoLabel(node))?
+                            .label()
+                            .label()
+                            .tnt(),
+                        Some(TNT::Non(_))
+                    ) {
+                        let sploned = self.splone(node, Some(pos), index, false)?;
+
+                        if !first_time {
+                            let last_index = self.degree(sploned)? - 1;
+
+                            let last_child = self.nth_child(sploned, last_index)?;
+
+                            let last_child_label = self
+                                .vertex_label(last_child)?
+                                .ok_or(Error::NodeNoLabel(last_child))?
+                                .label();
+
+                            if last_child_label.end() != Some(pos) {
+                                let closed_label = GrammarLabel::new_closed(
+                                    last_child_label.label(),
+                                    last_child_label.start(),
+                                    pos,
+                                );
+
+                                let closed_label_id = self
+                                    .query_label(closed_label.into())
+                                    .expect("last child closed label not found");
+
+                                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
-        // Ensure the last node in the PaSe is a terminal or a
+                                builder.redirect(sploned, last_index, closed_label_id)?;
+                            }
+                        }
+
+                        first_time = false;
+                    }
+                }
+            }
+        }
+
+        // Ensure the last node in the PaVi is a terminal or a
         // non-terminal node, as an extra safety guard during
         // development.
         #[cfg(debug_assertions)]
         {
-            if let Some(parent) = pase.parent() {
-                assert!(matches!(
-                    self.vertex_label(self.nth_child(parent.node(), parent.edge())?),
-                    Ok(Some(label))
-                        if label.label().label().tnt().is_some()));
-            } else if let Some((_, leaf)) = pase.segment() {
-                assert!(matches!(
-                    self.vertex_label(leaf),
-                    Ok(Some(label))
-                        if label.label().label().tnt().is_some()));
-            } else {
-                unreachable!("a pase is neither a parent nor a segment");
+            match pavi {
+                PaVi::Parent(node, edge) => {
+                    assert!(matches!(
+                        self.vertex_label(self.nth_child(node, edge)?),
+                        Ok(Some(label))
+                            if label.label().label().tnt().is_some()));
+                }
+                PaVi::Virtual(nt, t, node) => {
+                    if !matches!(
+                        self.vertex_label(node),
+                        Ok(Some(label))
+                            if matches!(
+                                label.label().label().tnt(),
+                                Some(TNT::Non(_))))
+                    {
+                        dbg!(node, self.vertex_label(node)?, pavi);
+
+                        self.print_viz("dbg forest.gv").unwrap();
+
+                        panic!("assumption fails");
+                    }
+
+                    if nt >= atom.non_num() {
+                        dbg!();
+                        return Err(Error::IndexOutOfBounds(nt, atom.non_num()));
+                    }
+
+                    if t >= atom.ter_num() {
+                        dbg!();
+                        return Err(Error::IndexOutOfBounds(t, atom.ter_num()));
+                    }
+                }
+                PaVi::Empty => {}
             }
         }
 
-        let mut is_empty_segment = false;
+        let is_empty_segment = pavi.is_empty();
 
         let mut parents: Vec<Parent> = {
             let mut result = Vec::new();
 
-            if let Some(parent) = pase.parent() {
-                result.push(parent);
-            } else {
-                let (root, leaf) = pase.segment().unwrap();
-                let mut seen_nodes = Set::new();
+            match pavi {
+                PaVi::Parent(node, edge) => {
+                    result.push(Parent::new(node, edge));
+                }
+                PaVi::Virtual(nt, t, node) => {
+                    let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
 
-                let mut stack = if root == leaf {
-                    // an empty segment means the root
-                    is_empty_segment = true;
+                    for atom_child in atom_child_iter.clone() {
+                        for rule in atom.trace(nt, t, atom_child).into_iter().flatten() {
+                            let virtual_frag = atom.generate_virtual_frags(nt, t, Some(rule));
 
-                    result.push(Parent::new(root, 0));
-                    vec![]
-                } else {
-                    vec![root]
-                };
+                            if let Some(frag) = virtual_frag {
+                                let mut frag = (*frag.get(0).unwrap()).clone();
 
-                while let Some(top) = stack.pop() {
-                    if seen_nodes.contains(&top) {
-                        continue;
-                    }
+                                frag.set_pos(node_label.label().start())?;
 
-                    seen_nodes.insert(top);
+                                let frag_nodes_len = frag.nodes_len();
 
-                    for (index, child) in self.children_of(top)?.enumerate() {
-                        if child == leaf {
-                            result.push(Parent::new(top, index));
-                        } else {
-                            stack.push(child);
+                                assert!(frag_nodes_len > 1);
+
+                                let last_but_one_label = frag
+                                    .vertex_label(frag_nodes_len - 2)?
+                                    .ok_or(Error::NodeNoLabel(frag_nodes_len - 2))?;
+
+                                // NOTE: The function
+                                // `plant_if_needed` assumes that we
+                                // want to plant the fragment as the
+                                // first child of the node.  This
+                                // assumption holds in this case, but
+                                // not in general.
+
+                                self.plant_if_needed(node, frag)?;
+
+                                let rule_label_pos = self
+                                    .query_label(last_but_one_label)
+                                    .expect("the forest was wrongly planted");
+
+                                result.push(Parent::new(rule_label_pos, 0));
+                            }
                         }
                     }
                 }
+                PaVi::Empty => {
+                    result.push(Parent::new(root, 0));
+                }
             }
 
             result
@@ -251,6 +482,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
         for atom_child in atom_child_iter {
             // dbg!(label.label(), atom_child);
+
             // Find reduction information.
             let reduction_info = atom
                 .query_reduction(label.label(), atom_child)
@@ -272,7 +504,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                             .label(),
                         GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt
                     ) {
-                        let sploned_node = self.splone(node.node(), Some(pos), node.edge())?;
+                        let sploned_node =
+                            self.splone(node.node(), Some(pos), node.edge(), false)?;
 
                         node_label = self
                             .vertex_label(sploned_node)?
@@ -282,16 +515,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                             let mut parent_iter = self.parents_of(sploned_node)?;
 
                             #[cfg(debug_assertions)]
-                            {
-                                assert_eq!(parent_iter.len(), 1);
-
-                                assert!(self
-                                    .vertex_label(sploned_node)?
-                                    .ok_or(Error::NodeNoLabel(sploned_node))?
-                                    .is_packed());
-                            }
+                            assert_eq!(parent_iter.len(), 1);
 
                             node = parent_iter.next().unwrap();
+
+                            #[cfg(debug_assertions)]
+                            assert!(self
+                                .vertex_label(node.node())?
+                                .ok_or(Error::NodeNoLabel(node.node()))?
+                                .is_packed());
                         } else {
                             node = Parent::new(sploned_node, node.edge());
                         }
@@ -337,19 +569,29 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                     atom_child,
                     parents,
                     reduction_info,
-                    atom.query_reduction(label.label(), atom_child).unwrap()
+                    atom.query_reduction(label.label(), atom_child).unwrap(),
+                    is_empty_segment,
+                    atom.trace(0, 3, atom_child)
+                        .into_iter()
+                        .flatten()
+                        .collect::<Vec<_>>(),
                 );
 
                 self.print_viz("dbg forest.gv").unwrap();
 
                 #[cfg(test)]
-                genins_test::print_labels(atom, self.borrow()).unwrap();
+                crate::item::default::print_labels(atom, self.borrow()).unwrap();
 
                 return Err(Error::CannotPlant);
             }
 
-            for parent in stack.into_iter() {
-                let sploned_node = self.splone(parent.node(), None, parent.edge())?;
+            if pos == 4 && matches!(true_source, PaVi::Virtual(_, _, _)) {
+                dbg!(&stack, reduction_info, true_source, pavi);
+                self.print_viz(&format!("pos4ib.gv")).unwrap();
+            }
+
+            for parent in stack {
+                let sploned_node = self.splone(parent.node(), None, parent.edge(), false)?;
 
                 self.plant(sploned_node, fragment, non_empty)?;
 
@@ -357,24 +599,22 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             }
         }
 
-        // If the iterator is empty, just plant at the specified
-        // child.
+        // If the iterator is empty, assert the fragment has length
+        // one, and do not plant anything.
         if !non_empty {
-            for parent in parents.into_iter() {
-                let nth_child = self.nth_child(parent.node(), parent.edge())?;
-
-                self.plant(nth_child, fragment, non_empty)?;
-
-                non_empty = true;
-            }
+            assert_eq!(fragment.nodes_len(), 1);
         }
 
         let result = if fragment.nodes_len() == 2 {
-            let root_label = fragment.vertex_label(0)?.unwrap();
-            let leaf_label = fragment.vertex_label(1)?.unwrap();
+            let root_label = fragment_root_label;
+            let leaf_label = fragment
+                .vertex_label(1 - fragment_root)?
+                .ok_or(Error::NodeNoLabel(1 - fragment_root))?;
 
             // it has been planted, so should be safe.
-            let node = self.query_label(root_label).unwrap();
+            let node = self
+                .query_label(root_label)
+                .expect("root label was not found");
 
             let edge = {
                 let mut result = None;
@@ -394,16 +634,52 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 }
             };
             // dbg!(node, edge, root_label, leaf_label);
-            PaSe::Parent(node, edge)
+            PaVi::Parent(node, edge)
         } else {
-            let root_label = fragment.vertex_label(0)?.unwrap();
-            let leaf_label = fragment.vertex_label(fragment.nodes_len() - 1)?.unwrap();
-            // dbg!(root_label, leaf_label);
-
-            PaSe::Segment(
-                self.query_label(root_label).unwrap(),
-                self.query_label(leaf_label).unwrap(),
-            )
+            assert_eq!(
+                fragment.nodes_len(),
+                1,
+                "a virtual fragment should consist of a single terminal node."
+            );
+
+            let root_label = fragment_root_label;
+
+            let pavi_parent = pavi.parent().expect(
+                "When we insert a virtual fragment, the forest_source of
+            the label must be a parent.",
+            );
+
+            let nth_child = self.nth_child(pavi_parent.node(), pavi_parent.edge())?;
+
+            let nth_child_label = self
+                .vertex_label(nth_child)?
+                .ok_or(Error::NodeNoLabel(nth_child))?
+                .label()
+                .label();
+
+            let error_str = "When we insert a virtual fragment, the \
+                             forest source of the label must point to \
+                             a non-terminal node";
+
+            let nt = match nth_child_label.tnt().expect(error_str) {
+                TNT::Non(nt) => nt,
+                _ => {
+                    dbg!(nth_child, nth_child_label);
+
+                    panic!("{error_str}");
+                }
+            };
+
+            let t = match root_label.label().label().tnt().unwrap() {
+                TNT::Ter(t) => t,
+                _ => {
+                    dbg!(root_label);
+
+                    panic!("a virtual fragment should consist of a single terminal node")
+                }
+            };
+
+            PaVi::Virtual(nt, t, nth_child)
         };
 
         Ok(result)
@@ -413,40 +689,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 #[cfg(test)]
 mod genins_test {
     use super::*;
-    #[allow(unused_imports)]
-    use crate::{default::DefaultChain, item::default::leaf, Chain};
+    use crate::item::default::leaf;
 
     use grammar::test_grammar_helper::*;
 
-    pub fn print_labels(
-        atom: impl Borrow<DefaultAtom>,
-        forest: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>,
-    ) -> Result<(), Box<dyn std::error::Error>> {
-        let forest = forest.borrow();
-        let atom = atom.borrow();
-
-        for node in forest.nodes() {
-            let label = forest.vertex_label(node)?;
-
-            if let Some(label) = label {
-                let label = label.label.label();
-
-                match label {
-                    GrammarLabelType::TNT(tnt) => {
-                        println!("{tnt} = {}", atom.name_of_tnt(tnt)?);
-                    }
-                    GrammarLabelType::Rule(pos) => {
-                        println!("pos {pos} = {}", atom.rule_pos_string(pos)?);
-                    }
-                }
-            } else {
-                return Err(Error::NodeNoLabel(node).into());
-            }
-        }
-
-        Ok(())
-    }
-
     #[test]
     fn test_generate_fragment() -> Result<(), Box<dyn std::error::Error>> {
         let grammar = new_notes_grammar()?;
@@ -497,7 +743,7 @@ mod genins_test {
             0,
         )?;
 
-        print_labels(&atom, &virtual_fragment)?;
+        crate::item::default::print_labels(&atom, &virtual_fragment)?;
 
         assert_eq!(virtual_fragment, test_fragment);
 
@@ -511,7 +757,7 @@ mod genins_test {
         let test_fragment =
             generate_fragment([TNT::Non(3).into(), 38.into(), TNT::Ter(2).into()], 1)?;
 
-        print_labels(&atom, &virtual_fragment)?;
+        crate::item::default::print_labels(&atom, &virtual_fragment)?;
 
         assert_eq!(virtual_fragment, test_fragment);