summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--chain/src/default.rs167
-rw-r--r--chain/src/item/genins.rs7
-rw-r--r--grammar/src/lib.rs6
3 files changed, 148 insertions, 32 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(
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index 41972c1..f48c8a8 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -14,7 +14,6 @@ use crate::{
Edge,
};
use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT};
-#[allow(unused_imports)]
use graph::{builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, RedirectGraph};
use core::borrow::Borrow;
@@ -141,13 +140,17 @@ pub fn virtual_generate_fragment(
Ok(result)
}
-// TODO: Examine `insert_item` again.
+// TODO: Refactor `insert_item`.
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.
+ ///
+ /// # Steps
+ ///
+ /// This function performs the following steps.
pub(crate) fn insert_item(
&mut self,
label: Edge,
diff --git a/grammar/src/lib.rs b/grammar/src/lib.rs
index 21ce2b4..54d9ebc 100644
--- a/grammar/src/lib.rs
+++ b/grammar/src/lib.rs
@@ -374,9 +374,9 @@ impl Grammar {
for (index, accumulator) in self.accumulators.iter().copied().enumerate() {
let shifted_accumulator = accumulator << 1;
- // NOTE: Clippy suggests to call `cmp`, but it seems
- // compiler might not yet be smart enough to inline that
- // call, so I just silence clippy here.
+ // NOTE: Clippy suggests to call `cmp`, but it seems that
+ // the compiler might not yet be smart enough to inline
+ // that call, so I just silence clippy here.
#[allow(clippy::comparison_chain)]
if pos == shifted_accumulator {
return Some(index);