summaryrefslogtreecommitdiff
path: root/chain/src/default.rs
diff options
context:
space:
mode:
Diffstat (limited to 'chain/src/default.rs')
-rw-r--r--chain/src/default.rs128
1 files changed, 110 insertions, 18 deletions
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<ForestError> 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<usize>,
- forest: DefaultForest<GrammarLabel>,
+ forest: DefaultForest<ForestLabel<GrammarLabel>>,
accepting_vec: Vec<bool>,
}
@@ -205,7 +214,7 @@ impl DefaultChain {
/// Return a reference to the associated forest.
#[inline]
- pub fn forest(&self) -> &DefaultForest<GrammarLabel> {
+ pub fn forest(&self) -> &DefaultForest<ForestLabel<GrammarLabel>> {
&self.forest
}
@@ -316,6 +325,7 @@ impl LabelExtGraph<Edge> 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<Self::DerIter, Self::Error> {
+ fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error> {
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<Item = usize> + ExactSizeIterator + Clone,
atom_child_iter: impl Iterator<Item = usize> + Clone,
+ pase: PaSe,
mut output: impl AsMut<Vec<(Edge, usize)>>,
) -> 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<GrammarLabelType> =
+ 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<dyn std::error::Error>> {
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));
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-09-19 22:44:11 +0000