diff options
| -rw-r--r-- | chain/src/default.rs | 55 | ||||
| -rw-r--r-- | chain/src/item/default/mod.rs | 35 | ||||
| -rw-r--r-- | chain/src/item/default/splone.rs | 22 | ||||
| -rw-r--r-- | chain/src/item/genins.rs | 395 | ||||
| -rw-r--r-- | chain/src/item/mod.rs | 20 |
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 |