diff options
Diffstat (limited to 'chain/src/default.rs')
| -rw-r--r-- | chain/src/default.rs | 167 |
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( |