From f28155105134b90fd86049c65478d307e0d8dbbc Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sat, 28 Jan 2023 10:17:24 +0800 Subject: a prototype of an item derivation forest It seems to be complete now, but still awaits more tests to see where the errors are, which should be plenty, haha. --- chain/src/default.rs | 128 +++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 110 insertions(+), 18 deletions(-) (limited to 'chain/src/default.rs') diff --git a/chain/src/default.rs b/chain/src/default.rs index 22befff..77a64ca 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -7,8 +7,10 @@ use super::*; use crate::atom::{Atom, DefaultAtom}; +use crate::item::{ + default::DefaultForest, generate_fragment, Forest, ForestLabel, ForestLabelError, +}; use core::fmt::Display; -use forest::{default::DefaultForest, Forest}; use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT}; use graph::{labelled::DLGBuilder, Builder, DLGraph, Graph, LabelExtGraph, LabelGraph}; @@ -29,6 +31,10 @@ pub enum Error { NodeNoLabel(usize), /// Reserving memory fails. CannotReserve(TryReserveError), + /// Cannot create label for cloning nodes. + CannotClone(ForestLabelError), + /// Cannot find a suitable node to plant the new forest fragment. + CannotPlant, /// An invalid situation happens. Invalid, } @@ -44,6 +50,8 @@ impl Display for Error { ), Self::NodeNoLabel(n) => write!(f, "node {n} has no labels while it should have one"), Self::CannotReserve(e) => write!(f, "cannot reserve memory: {e}"), + Self::CannotClone(fe) => write!(f, "cannot clone due to {fe}"), + Self::CannotPlant => write!(f, "cannot plant a new forest fragment"), Self::Invalid => write!(f, "invalid"), } } @@ -69,6 +77,7 @@ impl From for Error { ForestError::DuplicatedNode(n) => Error::DuplicateNode(n), ForestError::InvalidGraphError(ge) => ge.into(), ForestError::NodeNoLabel(n) => Error::NodeNoLabel(n), + ForestError::LabelConversion(ce) => Error::CannotClone(ce), } } } @@ -93,7 +102,7 @@ impl Default for DerIterIndex { } /// A complex type used for storing values of edges with two layers. -type SecondTypeValue = (Parent, bool, Vec<(Edge, usize)>); +type SecondTypeValue = (PaSe, bool, Vec<(Edge, usize)>); /// An iterator of TwoLayers. #[derive(Debug, Default)] @@ -120,7 +129,7 @@ impl DerIter { fn add_second_layer( &mut self, label: usize, - forest_source: Parent, + forest_source: PaSe, accepting: bool, edges: Vec<(Edge, usize)>, ) { @@ -186,7 +195,7 @@ pub struct DefaultChain { atom: DefaultAtom, current: usize, history: Vec, - forest: DefaultForest, + forest: DefaultForest>, accepting_vec: Vec, } @@ -205,7 +214,7 @@ impl DefaultChain { /// Return a reference to the associated forest. #[inline] - pub fn forest(&self) -> &DefaultForest { + pub fn forest(&self) -> &DefaultForest> { &self.forest } @@ -316,6 +325,7 @@ impl LabelExtGraph for DefaultChain { let new = self.graph.extend(edges)?; let accepting_len = self.accepting_vec.len(); + // Update the acceptace of the new node, if any. if self.accepting_vec.get(new).is_none() { // assert it can only grow by one node at a time. #[cfg(debug_assertions)] @@ -377,14 +387,17 @@ impl Chain for DefaultChain { let empty_state = atom.empty(); + // The zero-th non-terminal is assumed to be the starting + // non-terminal, by convention. let initial_nullable = atom .is_nullable(0) .map_err(|_| Error::IndexOutOfBounds(0, atom.non_num()))?; + // NOTE: Is it really correct to use `Parent::new(0, 0)` here? builder.add_edge( first, root, - Edge::new(empty_state, Parent::new(0, 0), initial_nullable), + Edge::new(empty_state, Default::default(), initial_nullable), )?; let graph = builder.build(); @@ -431,7 +444,7 @@ impl Chain for DefaultChain { type DerIter = DerIter; - fn derive(&mut self, t: usize, _pos: usize) -> Result { + fn derive(&mut self, t: usize, pos: usize) -> Result { use TNT::*; /// Convert an error telling us that an index is out of bounds. @@ -445,7 +458,7 @@ impl Chain for DefaultChain { GrammarError::IndexOutOfBounds(index, bound) => { Error::IndexOutOfBounds(index, bound) } - _ => panic!("wrong error kind"), + _ => Error::Invalid, } } @@ -459,11 +472,11 @@ impl Chain for DefaultChain { /// /// The generated edges will be pushed to `output` directly, /// to save some allocations. - // TODO: Handle forests as well. fn generate_edges( chain: &DefaultChain, child_iter: impl Iterator + ExactSizeIterator + Clone, atom_child_iter: impl Iterator + Clone, + pase: PaSe, mut output: impl AsMut>, ) -> Result<(), Error> { // First check the values from iterators are all valid. @@ -515,13 +528,11 @@ impl Chain for DefaultChain { // now push into output - let parent = Parent::new(0, 0); - 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 edge = Edge::new(atom_child, parent, atom_child_accepting); + let edge = Edge::new(atom_child, pase, atom_child_accepting); if !atom_child_empty_node { output.extend(child_iter.clone().map(|child| (edge, child))); @@ -549,16 +560,41 @@ impl Chain for DefaultChain { continue; } + let atom_moved = atom_label.get_moved(); + match *atom_label.get_value() { Some(Ter(ter)) if ter == t => { + // prepare forest fragment + + let fragment = + generate_fragment([atom_moved.into(), Ter(ter).into()], pos)?; + + let new_pase = self.forest.insert_item( + *label, + fragment, + atom_child_iter.clone(), + &self.atom, + )?; + generate_edges( self, child_iter.clone(), atom_child_iter.clone(), + new_pase, &mut der_iter.singles, )?; } Some(Non(non)) => { + let first_fragment = + generate_fragment([atom_moved.into(), Non(non).into()], pos)?; + + let first_segment_pase = self.forest.insert_item( + *label, + first_fragment, + atom_child_iter.clone(), + &self.atom, + )?; + let virtual_node = self .atom .atom(non, t) @@ -570,12 +606,66 @@ impl Chain for DefaultChain { .is_accepting(virtual_node) .map_err(index_out_of_bounds_conversion)?; + let virtual_fragment = { + // `non` is valid, as checked above + let non_start = self.atom.nth_accumulator(non).unwrap() * 2; + + let mut result = DefaultForest::default(); + + for (label, child_iter) in self.atom.labels_of(non_start)? { + if matches!(*label.get_value(), + Some(Ter(ter)) if ter == t) + { + for child in child_iter { + let mut line: Vec<_> = self + .atom + .query_expansion(non_start, child) + .map_err(index_out_of_bounds_conversion)? + .iter() + .copied() + .flatten() + .map(|(nt, rule)| [(*rule).into(), Non(*nt).into()]) + .collect(); + + line.push([label.get_moved().into(), Ter(t).into()]); + + let line: Vec = + line.into_iter().flatten().collect(); + + if result.is_empty() { + result = generate_fragment(line, pos)?; + } else { + result.plant( + 0, + generate_fragment(line, pos)?, + false, + )?; + } + } + } + } + + result + }; + + // NOTE: We only need the PaSe from the + // first segment, so we pass an empty + // iterator, in which case the passed + // label is only used for the PaSe. + let virtual_pase = self.forest.insert_item( + Edge::new(0, first_segment_pase, true), + virtual_fragment, + std::iter::empty(), + &self.atom, + )?; + let mut new_edges = Vec::new(); generate_edges( self, child_iter.clone(), atom_child_iter.clone(), + first_segment_pase, &mut new_edges, )?; @@ -583,12 +673,10 @@ impl Chain for DefaultChain { der_iter.singles.extend(new_edges.clone()); } - let parent = Parent::new(0, 0); - if !self.atom.is_empty_node(virtual_node).unwrap() { der_iter.add_second_layer( virtual_node, - parent, + virtual_pase, accepting, new_edges, ); @@ -601,7 +689,10 @@ impl Chain for DefaultChain { // `generate_edges` if self.atom.is_empty_node(atom_child).unwrap() { der_iter.singles.extend(child_iter.clone().map(|child| { - (Edge::new(virtual_node, parent, accepting), child) + ( + Edge::new(virtual_node, virtual_pase, accepting), + child, + ) })); } } @@ -610,7 +701,8 @@ impl Chain for DefaultChain { // this has been checked in // `generate_edges` if self.atom.is_empty_node(atom_child).unwrap() { - // flat flat map, hmm... + // REVIEW: flat flat map, + // hmm... der_iter.singles.extend(child_iter.clone().flat_map( |child| { self.graph.labels_of(child).unwrap().flat_map( @@ -646,7 +738,7 @@ mod test_der_iter { fn test() -> Result<(), Box> { let mut der_iter = DerIter::default(); - let parent = Parent::new(0, 0); + let parent = Default::default(); der_iter.singles.push((Edge::new(0, parent, true), 0)); -- cgit v1.2.3-18-g5258