diff options
Diffstat (limited to 'chain/src/item/genins.rs')
| -rw-r--r-- | chain/src/item/genins.rs | 231 |
1 files changed, 231 insertions, 0 deletions
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs new file mode 100644 index 0000000..99d9202 --- /dev/null +++ b/chain/src/item/genins.rs @@ -0,0 +1,231 @@ +//! This module implements the generation and insertion of item +//! derivation forests. +//! +//! This is used for the chain-rule machine to conveniently produce +//! item derivations into a forest. This forest can serve as a rough +//! approximation of the parse forests, and can be executed in other +//! semirings later on. + +use super::*; +use crate::{atom::DefaultAtom, default::Error, item::default::DefaultForest, Edge}; +use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT}; +use graph::Graph; + +use core::borrow::Borrow; +use std::collections::HashSet as Set; + +/// A helper function to generate a fragment of forest. +/// +/// It simply constructs a root node and then appends +/// successive nodes as successive children of the previous +/// node. Also the starting positions will all be set to the +/// same position. +/// +/// If the input is empty, this returns an empty forest; +/// otherwise the result is not empty. +pub fn generate_fragment( + labels: impl AsRef<[GrammarLabelType]>, + pos: usize, +) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, crate::default::Error> { + let mut labels_iter = labels.as_ref().iter(); + let mut result: DefaultForest<ForestLabel<GrammarLabel>>; + + if let Some(first_label) = labels_iter.next() { + result = DefaultForest::new_leaf(GrammarLabel::new(*first_label, pos)); + + let mut index = 0; + + for label in labels_iter { + result.plant( + index, + DefaultForest::new_leaf(GrammarLabel::new(*label, pos)), + false, + )?; + + // To prevent duplication of labels causing + // panics, we query the index of the new node. + index = result + .query_label(GrammarLabel::new(*label, pos).into()) + // REVIEW: Perhaps a LabelNoNode error? + .ok_or(Error::Invalid)?; + } + } else { + result = Default::default(); + } + + Ok(result) +} + +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. + pub fn insert_item( + &mut self, + label: Edge, + fragment: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>, + atom_child_iter: impl Iterator<Item = usize>, + atom: &DefaultAtom, + ) -> Result<PaSe, Error> { + /// Convert an error telling us that an index is out of bounds. + /// + /// # Panics + /// + /// The function panics if the error is not of the expected + /// kind. + fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { + match ge { + GrammarError::IndexOutOfBounds(index, bound) => { + Error::IndexOutOfBounds(index, bound) + } + _ => Error::Invalid, + } + } + + let fragment = fragment.borrow(); + + let pase = label.forest_source(); + + let parents: Vec<Parent> = { + let mut result = Vec::new(); + + if let Some(parent) = pase.parent() { + result.push(parent); + } else { + let (root, leaf) = pase.segment().unwrap(); + let mut seen_nodes = Set::new(); + + let mut stack = vec![root]; + + while let Some(top) = stack.pop() { + if seen_nodes.contains(&top) { + continue; + } + + seen_nodes.insert(top); + + for (index, child) in self.children_of(top)?.enumerate() { + if child == leaf { + result.push(Parent::new(top, index)); + } else { + stack.push(child); + } + } + } + } + + result + }; + + for atom_child in atom_child_iter { + // Find reduction information. + let reduction_info = atom + .query_reduction(label.label(), atom_child) + .map_err(index_out_of_bounds_conversion)?; + + let mut stack = parents.clone(); + let mut second_stack = Vec::new(); + + // locate the nodes + for reduction_nt in reduction_info.iter().copied().flatten().rev() { + while let Some(node) = stack.pop() { + // REVIEW: A lot of labels appear here. + // Perhaps I need to refactor something? + if matches!( + self + .vertex_label(node.node())? + .ok_or_else(|| Error::NodeNoLabel(node.node()))? + .label() + .label(), + GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt + ) { + for parent in self.parents_of(node.node())? { + debug_assert!(matches!( + self.vertex_label(parent.node()), + Ok(Some(label)) if + label + .label() + .label() + .rule() + .is_some())); + + second_stack.extend(self.parents_of(parent.node())?.filter(|n| { + matches!(self.vertex_label(n.node()), + Ok(Some(label)) + if matches!( + label.label().label().tnt(), + Some(TNT::Non(_)))) + })); + } + } + } + + std::mem::swap(&mut stack, &mut second_stack); + + if stack.is_empty() { + break; + } + } + + if stack.is_empty() { + return Err(Error::CannotPlant); + } + + for parent in stack.into_iter() { + if parent.edge() + 1 >= self.degree(parent.node())? { + self.plant(parent.node(), fragment, false)?; + } else { + let nth_child = self.nth_child(parent.node(), parent.edge() + 1)?; + + if self.is_prefix(nth_child, fragment)? { + // do nothing + continue; + } + + let cloned_node = self.clone_node(nth_child)?; + + self.plant(cloned_node, fragment, false)?; + } + } + } + + let result = if fragment.nodes_len() == 2 { + let root_label = fragment.vertex_label(0)?.unwrap(); + let leaf_label = fragment.vertex_label(1)?.unwrap(); + + // it has been planted, so should be safe. + let node = self.query_label(root_label).unwrap(); + + let edge = { + let mut result = None; + + for (index, child) in self.children_of(node)?.enumerate() { + if matches!(self.vertex_label(child)?, Some(child_label) if child_label == leaf_label) + { + result = Some(index); + break; + } + } + + if let Some(result) = result { + result + } else { + unreachable!("the forest is wrongly planted"); + } + }; + + PaSe::Parent(node, edge) + } else { + let root_label = fragment.vertex_label(0)?.unwrap(); + let leaf_label = fragment.vertex_label(fragment.nodes_len() - 1)?.unwrap(); + + PaSe::Segment( + self.query_label(root_label).unwrap(), + self.query_label(leaf_label).unwrap(), + ) + }; + + Ok(result) + } +} |