Add a type Reducer for recording extra reductions

In the chain-rule machine, we need to skip through edges whose labels
are "accepting", otherwise the time complexity will be high even for
simple grammars.  This implies that we will skip some "jumping up" in
the item derivation forest.  So we need to record these extra jumping
up, in order to jump up at a later point.

This Reducer type plays this role.  But I still need more experiments
to see if this approach works out as I intended.

1 files changed, 140 insertions, 27 deletions

diff --git a/chain/src/default.rs b/chain/src/default.rs
index da665bf..6e935fe 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -17,10 +17,7 @@ use graph::{
     labelled::DLGBuilder, Builder, DLGraph, Graph, LabelExtGraph, LabelGraph, ParentsGraph,
 };
 
-use std::{
-    borrow::Borrow,
-    collections::{HashMap as Map, HashSet, TryReserveError},
-};
+use std::collections::{HashMap as Map, HashSet, TryReserveError};
 
 /// The errors related to taking derivatives by chain rule.
 #[non_exhaustive]
@@ -207,6 +204,47 @@ impl Iterator for DerIter {
 // we just query again with the new bottom and top.  This means we do
 // not need to clear the map.
 
+/// This represents a tuple of bottom and top forest positions.
+///
+/// It is supposed to be used as keys to query the reduction
+/// information.  See the type [`Reducer`] for more details.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
+pub(crate) struct BoTop {
+    bottom: PaVi,
+    top: PaVi,
+}
+
+#[allow(dead_code)]
+impl BoTop {
+    fn new(bottom: PaVi, top: PaVi) -> Self {
+        Self { bottom, top }
+    }
+
+    fn top(&self) -> PaVi {
+        self.top
+    }
+
+    fn bottom(&self) -> PaVi {
+        self.bottom
+    }
+}
+
+/// This hashmap records information for performing extra reductions
+/// when we insert items.
+///
+/// When we want to *jump* from the bottom to the top positions in the
+/// forest, we need to perform a set of reductions, in order to jump
+/// one layer upwards.  After one step, we query again for the next
+/// step of reductions to perform.
+///
+/// # Reduction format
+///
+/// The value records a set of tuples of the form `(non-terminal,
+/// rule_position)`.  Such a tuple means we want to reduce from the
+/// expansion of the given `non-terminal`, where the last rule
+/// position we have seen in this branch is the given `rule_position`.
+type Reducer = Map<BoTop, HashSet<(usize, usize)>>;
+
 /// A default implementation for the [`Chain`] trait.
 #[derive(Debug, Clone, Default)]
 pub struct DefaultChain {
@@ -217,6 +255,7 @@ pub struct DefaultChain {
     forest: DefaultForest<ForestLabel<GrammarLabel>>,
     accepting_vec: Vec<bool>,
     accepting_sources: Vec<PaVi>,
+    reducer: Reducer,
 }
 
 impl DefaultChain {
@@ -433,6 +472,8 @@ impl Chain for DefaultChain {
 
         let accepting_sources = Vec::new();
 
+        let reducer = Default::default();
+
         Ok(Self {
             graph,
             atom,
@@ -441,6 +482,7 @@ impl Chain for DefaultChain {
             forest,
             accepting_vec,
             accepting_sources,
+            reducer,
         })
     }
 
@@ -506,6 +548,14 @@ impl Chain for DefaultChain {
     ) -> Result<Self::DerIter, Self::Error> {
         use TNT::*;
 
+        /// The function `generate_edges` takes too many arguments, so
+        /// a type is used to group them together.
+        ///
+        /// The format is as follows:
+        ///
+        /// `(graph, atom, accepting_vec, forest_source, new_source)`
+        type GeneratorInput<'a> = (&'a DLGraph<Edge>, &'a DefaultAtom, &'a [bool], PaVi, PaVi);
+
         /// A helper function to generate edges to join.
         ///
         /// It first checks if the base edge is accepting.  If yes,
@@ -517,27 +567,28 @@ impl Chain for DefaultChain {
         /// The generated edges will be pushed to `output` directly,
         /// to save some allocations.
         fn generate_edges(
-            chain: &DefaultChain,
+            input: GeneratorInput<'_>,
             mut child_iter: impl Iterator<Item = usize> + ExactSizeIterator + Clone,
             atom_child_iter: impl Iterator<Item = usize> + Clone,
-            pavi: PaVi,
-            true_pavi: PaVi,
+            reducer: &mut Reducer,
             mut output: impl AsMut<Vec<(Roi, usize)>>,
         ) -> Result<bool, Error> {
             let mut accepting = false;
 
+            let (graph, atom, accepting_vec, pavi, true_pavi) = input;
+
             // First check the values from iterators are all valid.
-            let graph_len = chain.graph.nodes_len();
-            let atom_len = chain.atom.nodes_len();
+            let graph_len = graph.nodes_len();
+            let atom_len = atom.nodes_len();
 
             for child in child_iter.clone() {
-                if !chain.graph.has_node(child) {
+                if !graph.has_node(child) {
                     return Err(Error::IndexOutOfBounds(child, graph_len));
                 }
             }
 
             for atom_child in atom_child_iter.clone() {
-                if !chain.atom.has_node(atom_child) {
+                if !atom.has_node(atom_child) {
                     return Err(Error::IndexOutOfBounds(atom_child, atom_len));
                 }
             }
@@ -551,11 +602,11 @@ impl Chain for DefaultChain {
 
             let child_iter_total_degree = child_iter
                 .clone()
-                .map(|child| chain.graph.degree(child).unwrap())
+                .map(|child| graph.degree(child).unwrap())
                 .sum::<usize>();
 
             for atom_child in atom_child_iter.clone() {
-                let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap();
+                let atom_child_accepting = atom.is_accepting(atom_child).unwrap();
 
                 num += child_iter.len();
 
@@ -574,8 +625,8 @@ impl Chain for DefaultChain {
             // now push into output
 
             for atom_child in atom_child_iter {
-                let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap();
-                let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap();
+                let atom_child_accepting = atom.is_accepting(atom_child).unwrap();
+                let atom_child_empty_node = atom.is_empty_node(atom_child).unwrap();
 
                 let roi = Edge::new(atom_child, pavi, atom_child_accepting).into();
 
@@ -587,11 +638,28 @@ impl Chain for DefaultChain {
 
                 if atom_child_accepting {
                     for child in child_iter.clone() {
-                        for (child_label, child_child) in chain.graph.labels_of(child).unwrap() {
-                            // use the new `pavi` as `true_source`
+                        for (child_label, child_child) in graph.labels_of(child).unwrap() {
                             let mut new_label = *child_label;
                             new_label.set_true_source(true_pavi);
 
+                            let botop = BoTop::new(true_pavi, new_label.forest_source());
+
+                            let rule_pos = child_label.label().div_euclid(2);
+
+                            let rule_nt = atom
+                                .get_rule_num(rule_pos)
+                                .map_err(index_out_of_bounds_conversion)?;
+
+                            let rule_pos = rule_pos
+                                - atom
+                                    .nth_accumulator(rule_nt)
+                                    .map_err(index_out_of_bounds_conversion)?;
+
+                            reducer
+                                .entry(botop)
+                                .or_insert_with(Default::default)
+                                .insert((rule_nt, rule_pos));
+
                             output.extend(
                                 std::iter::repeat(new_label.into())
                                     .take(child_child.len())
@@ -602,8 +670,7 @@ impl Chain for DefaultChain {
                 }
             }
 
-            accepting =
-                accepting && child_iter.any(|child| *chain.accepting_vec.get(child).unwrap());
+            accepting = accepting && child_iter.any(|child| *accepting_vec.get(child).unwrap());
 
             Ok(accepting)
         }
@@ -665,12 +732,19 @@ impl Chain for DefaultChain {
                             new_pavi = PaVi::default();
                         }
 
+                        let generator_input = (
+                            &self.graph,
+                            &self.atom,
+                            self.accepting_vec.as_slice(),
+                            new_pavi,
+                            new_pavi,
+                        );
+
                         let accepting = generate_edges(
-                            self,
+                            generator_input,
                             child_iter.clone(),
                             atom_child_iter.clone(),
-                            new_pavi,
-                            new_pavi,
+                            &mut self.reducer,
                             &mut der_iter.singles,
                         )?;
 
@@ -751,12 +825,19 @@ impl Chain for DefaultChain {
 
                             let mut new_edges = Vec::new();
 
+                            let generator_input = (
+                                &self.graph,
+                                &self.atom,
+                                self.accepting_vec.as_slice(),
+                                first_segment_pavi,
+                                virtual_pavi,
+                            );
+
                             let virtual_accepting = generate_edges(
-                                self.borrow(),
+                                generator_input,
                                 child_iter.clone(),
                                 atom_child_iter.clone(),
-                                first_segment_pavi,
-                                virtual_pavi,
+                                &mut self.reducer,
                                 &mut new_edges,
                             )?;
 
@@ -766,8 +847,38 @@ impl Chain for DefaultChain {
 
                             if accepting {
                                 accepting_pavi.insert(virtual_pavi);
-                                // FIXME: set true_source here
-                                der_iter.singles.extend(new_edges.clone());
+
+                                for (roi, target) in new_edges.iter() {
+                                    match roi {
+                                        Roi::Re(edge) => {
+                                            let mut edge = *edge;
+                                            edge.set_true_source(virtual_pavi);
+
+                                            // FIXME: Modify reducer after first experiments.
+
+                                            // let botop = BoTop::new(virtual_pavi, edge.forest_source());
+
+                                            // let rule_pos = atom_child.div_euclid(2);
+
+                                            // let rule_nt = atom
+                                            //     .get_rule_num(rule_pos)
+                                            //     .map_err(index_out_of_bounds_conversion)?;
+
+                                            // let rule_pos = rule_pos
+                                            //     - atom
+                                            //     .nth_accumulator(rule_nt)
+                                            //     .map_err(index_out_of_bounds_conversion)?;
+
+                                            // reducer
+                                            //     .entry(botop)
+                                            //     .or_insert_with(Default::default)
+                                            //     .insert((rule_nt, rule_pos));
+
+                                            der_iter.singles.push((Roi::Re(edge), *target));
+                                        }
+                                        Roi::Im(_) => der_iter.singles.push((*roi, *target)),
+                                    }
+                                }
                             }
 
                             if !self.atom.is_empty_node(virtual_node).unwrap() {
@@ -803,6 +914,8 @@ impl Chain for DefaultChain {
                                         // hmm...
 
                                         // FIXME: Set true_source as well.
+
+                                        // FIXME: Modify two layers of reducer.
                                         der_iter.singles.extend(child_iter.clone().flat_map(
                                             |child| {
                                                 self.graph.labels_of(child).unwrap().flat_map(