summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--chain/src/default.rs55
-rw-r--r--chain/src/item/default/mod.rs35
-rw-r--r--chain/src/item/default/splone.rs22
-rw-r--r--chain/src/item/genins.rs395
-rw-r--r--chain/src/item/mod.rs20
5 files changed, 278 insertions, 249 deletions
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 6e935fe..1df68b5 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -214,17 +214,16 @@ pub(crate) struct BoTop {
top: PaVi,
}
-#[allow(dead_code)]
impl BoTop {
- fn new(bottom: PaVi, top: PaVi) -> Self {
+ pub(crate) fn new(bottom: PaVi, top: PaVi) -> Self {
Self { bottom, top }
}
- fn top(&self) -> PaVi {
+ pub(crate) fn top(&self) -> PaVi {
self.top
}
- fn bottom(&self) -> PaVi {
+ pub(crate) fn bottom(&self) -> PaVi {
self.bottom
}
}
@@ -240,10 +239,10 @@ impl BoTop {
/// # 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)>>;
+/// starting_position)`. Such a tuple means we want to reduce from
+/// the expansion of the given `non-terminal`, which expands from the
+/// given starting position. We need to restrict the
+pub(crate) type Reducer = Map<(usize, usize), HashSet<usize>>;
/// A default implementation for the [`Chain`] trait.
#[derive(Debug, Clone, Default)]
@@ -553,8 +552,15 @@ impl Chain for DefaultChain {
///
/// 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);
+ /// `(graph, atom, forest, accepting_vec, forest_source, new_source)`
+ type GeneratorInput<'a> = (
+ &'a DLGraph<Edge>,
+ &'a DefaultAtom,
+ &'a DefaultForest<ForestLabel<GrammarLabel>>,
+ &'a [bool],
+ PaVi,
+ PaVi,
+ );
/// A helper function to generate edges to join.
///
@@ -575,7 +581,7 @@ impl Chain for DefaultChain {
) -> Result<bool, Error> {
let mut accepting = false;
- let (graph, atom, accepting_vec, pavi, true_pavi) = input;
+ let (graph, atom, forest, accepting_vec, pavi, true_pavi) = input;
// First check the values from iterators are all valid.
let graph_len = graph.nodes_len();
@@ -644,21 +650,15 @@ impl Chain for DefaultChain {
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)?;
+ let key = (
+ forest.node_from_pavi(botop.top())?,
+ forest.node_from_pavi(botop.bottom)?,
+ );
reducer
- .entry(botop)
+ .entry(key)
.or_insert_with(Default::default)
- .insert((rule_nt, rule_pos));
+ .insert(forest.node_from_pavi(new_label.true_source())?);
output.extend(
std::iter::repeat(new_label.into())
@@ -714,6 +714,7 @@ impl Chain for DefaultChain {
}
new_pavi = self.forest.insert_item(
+ &self.reducer,
*label,
fragment,
atom_child_iter.clone(),
@@ -735,6 +736,7 @@ impl Chain for DefaultChain {
let generator_input = (
&self.graph,
&self.atom,
+ &self.forest,
self.accepting_vec.as_slice(),
new_pavi,
new_pavi,
@@ -787,6 +789,7 @@ impl Chain for DefaultChain {
}
first_segment_pavi = self.forest.insert_item(
+ &self.reducer,
*label,
first_fragment,
atom_child_iter.clone(),
@@ -807,6 +810,7 @@ impl Chain for DefaultChain {
// iterator, in which case the passed
// label is only used for the PaVi.
virtual_pavi = self.forest.insert_item(
+ &self.reducer,
Edge::new(0, first_segment_pavi, accepting),
virtual_fragment,
std::iter::empty(),
@@ -828,6 +832,7 @@ impl Chain for DefaultChain {
let generator_input = (
&self.graph,
&self.atom,
+ &self.forest,
self.accepting_vec.as_slice(),
first_segment_pavi,
virtual_pavi,
@@ -980,9 +985,9 @@ impl Chain for DefaultChain {
for frag in reduction_fragment.into_iter().flatten() {
let mut frag = frag.clone();
- frag.set_pos(node_label.label().start())?;
+ frag.set_pos(node_label.label().start(), true)?;
- stack.push(self.forest.plant_if_needed(*node, frag)?);
+ stack.push(self.forest.plant_at_start(*node, frag)?);
}
}
}
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