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.

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));