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, 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)
+    }
+}