extra reductions

Finished the function of performing extra reductions.

Still untested though.

4 files changed, 248 insertions, 224 deletions

diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 22069d2..3903162 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -628,7 +628,7 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
     /// case we clone it only when its degree is larger than one.
     ///
     /// Return either the original node or the cloned node at the end.
-    pub(crate) fn plant_if_needed(
+    pub(crate) fn plant_at_start(
         &mut self,
         node: usize,
         mut fragment: Self,
@@ -691,6 +691,34 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
 
         Ok(node)
     }
+
+    /// Extract the node from `pavi`.
+    ///
+    /// If pavi is a parent, this returns the child pointed to by the
+    /// represented edge.
+    ///
+    /// If pavi is a virtual node, this simply returns the virtual
+    /// node.
+    ///
+    /// If pavi is empty, this returns the root, unless the forest is
+    /// empty.
+    ///
+    /// # Guarantee
+    ///
+    /// The returned node is guaranteed to be a valid node.
+    pub(crate) fn node_from_pavi(&self, pavi: PaVi) -> Result<usize, Error> {
+        match pavi {
+            PaVi::Parent(node, edge) => Ok(self.nth_child(node, edge)?),
+            PaVi::Virtual(_, _, node) => {
+                if node >= self.nodes_len() {
+                    return Err(Error::IndexOutOfBounds(node, self.nodes_len()));
+                }
+
+                Ok(node)
+            }
+            PaVi::Empty => Ok(self.root().ok_or(Error::IndexOutOfBounds(0, 0))?),
+        }
+    }
 }
 
 pub mod splone;
@@ -831,6 +859,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// `child` is the index of the child node in question, and
     /// `index` means that the child is the `index`-th child of the
     /// node.
+    #[allow(dead_code)]
     pub(crate) fn position_search(
         &self,
         node: usize,
@@ -1052,7 +1081,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     // }
 
     /// Set the position of every node.
-    pub(crate) fn set_pos(&mut self, pos: usize) -> Result<(), Error> {
+    pub(crate) fn set_pos(&mut self, pos: usize, allp: bool) -> Result<(), Error> {
         let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
         for node in 0..builder.nodes_len() {
@@ -1064,7 +1093,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             label_label.set_start(pos);
 
-            if matches!(label_label.label().tnt(), Some(TNT::Ter(_))) {
+            if allp || matches!(label_label.label().tnt(), Some(TNT::Ter(_))) {
                 label_label.set_end(pos + 1);
             } else if builder.degree(node)? == 1 && label_label.label().rule().is_some() {
                 let child = builder.children_of(node)?.next().unwrap();
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index 237b92a..4cd11b9 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -142,7 +142,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
         // 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)?;
@@ -176,27 +175,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             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(node)
     }
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index f48c8a8..0c3f616 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -9,15 +9,17 @@
 use super::*;
 use crate::{
     atom::{Atom, DefaultAtom},
-    default::Error,
+    default::{BoTop, Error, Reducer},
     item::default::DefaultForest,
     Edge,
 };
 use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT};
-use graph::{builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, RedirectGraph};
+use graph::Graph;
 
 use core::borrow::Borrow;
 
+use std::collections::HashSet;
+
 /// Convert an error telling us that an index is out of bounds.
 ///
 /// # Panics
@@ -151,8 +153,35 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// # Steps
     ///
     /// This function performs the following steps.
+    ///
+    /// # Extra reductions
+    ///
+    /// If the label's true_source is different from its
+    /// forest_source, first splone the node of true_source, then
+    /// query the reducer by the key botop, whose bottom is
+    /// `true_source` and top is `forest_source`.  The result is an
+    /// optional set of tuples (nt, rule) of unsigned integers.  For
+    /// each tuple, find a parent which is labelled by `nt` and whose
+    /// parent is labelled by `rule`.  Then proceed similarly.
+    ///
+    /// # Reductions
+    ///
+    /// Perform splone on the node of forest_source.  Then query atom
+    /// for the reduction information by the key (label, atom_child),
+    /// where atom_child runs through every element of
+    /// atom_child_iter.  The result is a list of unsigned integers.
+    /// For each unsigned integer `nt`, we find a parent which is
+    /// labelled by `nt`.  The last parents found will be the parents
+    /// used in the next step.
+    ///
+    /// # Plant
+    ///
+    /// For parents as found in the previous step, for each node in
+    /// parents, perform splone with an open end, and then plant the
+    /// fragment under the result splone.
     pub(crate) fn insert_item(
         &mut self,
+        reducer: &Reducer,
         label: Edge,
         fragment: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>,
         atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator + Clone,
@@ -182,181 +211,12 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
         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()
-                    {
-                        self.splone(nth_child, Some(pos), nth_child_last, false)?
-                    } 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);
-
-                                builder.redirect(sploned, last_index, closed_label_id)?;
-                            }
-                        }
-
-                        first_time = false;
-                    }
-                }
-            }
-        }
+        self.extra_reductions(
+            BoTop::new(pavi, true_source),
+            pos,
+            reducer.borrow(),
+            atom.borrow(),
+        )?;
 
         // Ensure the last node in the PaVi is a terminal or a
         // non-terminal node, as an extra safety guard during
@@ -399,6 +259,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             }
         }
 
+        // TODO: Refactor this.
+
         let is_empty_segment = pavi.is_empty();
 
         let mut parents: Vec<Parent> = {
@@ -418,7 +280,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                             if let Some(frag) = virtual_frag {
                                 let mut frag = (*frag.get(0).unwrap()).clone();
 
-                                frag.set_pos(node_label.label().start())?;
+                                frag.set_pos(node_label.label().start(), false)?;
 
                                 let frag_nodes_len = frag.nodes_len();
 
@@ -435,7 +297,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                                 // assumption holds in this case, but
                                 // not in general.
 
-                                self.plant_if_needed(node, frag)?;
+                                self.plant_at_start(node, frag)?;
 
                                 let rule_label_pos = self
                                     .query_label(last_but_one_label)
@@ -685,6 +547,181 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
         Ok(result)
     }
+
+    /// Perform extra reductions.
+    ///
+    /// To be precise, this functions first splones the bottom node,
+    /// and then queries the reducer to find the next nodes to splone,
+    /// and repeats this process until either we find the top node, or
+    /// the reducer says to stop.
+    ///
+    /// One nuance to note is that after we splone a node, if we split
+    /// that node, then the splitted node will have a cloned parent,
+    /// see
+    /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node]
+    /// for details.  So for each parent pointed out by the reducer,
+    /// we need to find its clone that has the splitted node as a
+    /// child.
+    fn extra_reductions(
+        &mut self,
+        botop: BoTop,
+        pos: usize,
+        reducer: &Reducer,
+        atom: &DefaultAtom,
+    ) -> Result<Vec<usize>, Error> {
+        if botop.bottom() == botop.top() {
+            return Ok(vec![self.node_from_pavi(botop.top())?]);
+        }
+
+        let top = botop.top();
+        let bottom = botop.bottom();
+
+        let bottom_closed = self.close_pavi(atom.borrow(), bottom, pos)?;
+
+        let top_node = self.node_from_pavi(top)?;
+        let bottom_node = self.node_from_pavi(bottom)?;
+
+        let mut stack = vec![bottom_node];
+
+        let mut seen_nodes: HashSet<usize> = Default::default();
+
+        let mut result = Vec::new();
+
+        while let Some(bottom) = stack.pop() {
+            if seen_nodes.contains(&bottom) {
+                continue;
+            }
+
+            seen_nodes.insert(bottom);
+
+            if let Some(set) = reducer.get(&(top_node, bottom)) {
+                // First splone the bottom, except for the bottom one.
+
+                let mut sploned = if bottom == bottom_node {
+                    bottom_closed
+                } else {
+                    let degree = self.degree(bottom)?;
+                    let last_index = core::cmp::max(degree, 1) - 1;
+
+                    self.splone(bottom, Some(pos), last_index, false)?
+                };
+
+                // Then add parents whose labels are what we want into
+                // the stack.
+
+                let mut label_set: HashSet<GrammarLabel> = HashSet::with_capacity(set.len());
+
+                for node in set.iter().copied() {
+                    label_set.insert(
+                        self.vertex_label(node)?
+                            .ok_or(Error::NodeNoLabel(node))?
+                            .label(),
+                    );
+                }
+
+                let sploned_label = self
+                    .vertex_label(sploned)?
+                    .ok_or(Error::NodeNoLabel(sploned))?;
+
+                if sploned_label.clone_index().is_some() {
+                    let mut parents = self.parents_of(sploned)?;
+
+                    #[cfg(debug_assertions)]
+                    if parents.len() != 1 {
+                        panic!("assumption fails");
+                    }
+
+                    sploned = parents.next().unwrap().node();
+                }
+
+                for rule_parent in self.parents_of(sploned)? {
+                    if self.degree(rule_parent.node())? != 1 {
+                        panic!("assumption fails");
+                    }
+
+                    for parent in self.parents_of(rule_parent.node())? {
+                        let parent_node = parent.node();
+
+                        let parent_label = self
+                            .vertex_label(parent_node)?
+                            .ok_or(Error::NodeNoLabel(parent_node))?
+                            .label();
+
+                        if label_set.contains(&parent_label) {
+                            stack.push(parent_node);
+                        }
+                    }
+                }
+            } else {
+                result.push(bottom);
+            }
+        }
+
+        Ok(result)
+    }
+
+    /// Set the end position of the node associated with `pavi` to be `pos`.
+    ///
+    /// The parameter `atom` is used to query the reduction fragment
+    /// if `pavi` is a virtual node.
+    fn close_pavi(&mut self, atom: &DefaultAtom, pavi: PaVi, pos: usize) -> Result<usize, Error> {
+        match pavi {
+            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 = core::cmp::max(nth_child_degree, 1) - 1;
+
+                if matches!(nth_child_label.label().label().tnt(), Some(TNT::Non(_)))
+                    && !nth_child_label.is_packed()
+                {
+                    Ok(self.splone(nth_child, Some(pos), nth_child_last, false)?)
+                } else if nth_child_label.is_packed() {
+                    // REVIEW: is this really correct?
+                    dbg!("this should not really happen?");
+
+                    let mut result: usize = nth_child;
+
+                    for node in self.children_of(nth_child)?.collect::<Vec<_>>() {
+                        let node_label =
+                            self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
+                        let degree = self.degree(node)?;
+                        let last_index = core::cmp::max(degree, 1) - 1;
+
+                        if matches!(node_label.label().label().tnt(), Some(TNT::Non(_))) {
+                            result = self.splone(node, Some(pos), last_index, false)?;
+                        }
+                    }
+
+                    Ok(result)
+                } else {
+                    Ok(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);
+
+                for frag in reduction_fragment.into_iter().flatten() {
+                    let mut frag = frag.clone();
+                    frag.set_pos(node_label_start, true)?;
+
+                    node = self.plant_at_start(node, frag)?;
+                }
+
+                Ok(node)
+            }
+            _ => self.root().ok_or(Error::IndexOutOfBounds(0, 0)),
+        }
+    }
 }
 
 #[cfg(test)]
diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs
index 39d04c7..f8e0aa0 100644
--- a/chain/src/item/mod.rs
+++ b/chain/src/item/mod.rs
@@ -75,26 +75,6 @@ impl PaVi {
         }
     }
 
-    // /// Get the "Virtual" variant.
-    // ///
-    // /// # Name
-    // ///
-    // /// We cannot use the name "virtual" since it is a reserved
-    // /// keyword in Rust, so we use its French name.
-    // ///
-    // /// # Tuple elements
-    // ///
-    // /// The returned tuple is of the form (nt, t, node), which means a
-    // /// virtually added node at the `node` representing the expansion
-    // /// from the non-terminal `nt` by the terminal `t`.
-    // fn virtuel(self) -> Option<(usize, usize, usize)> {
-    //     if let Self::Virtual(nt, t, node) = self {
-    //         Some((nt, t, node))
-    //     } else {
-    //         None
-    //     }
-    // }
-
     /// Is this an empty segment?
     fn is_empty(self) -> bool {
         self == Self::Empty