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, 252 insertions, 0 deletions

diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs
new file mode 100644
index 0000000..7fafcc8
--- /dev/null
+++ b/chain/src/item/mod.rs
@@ -0,0 +1,252 @@
+#![warn(missing_docs)]
+//! This module implements the type of items for the chain-rule
+//! machine.
+//!
+//! More specifically, it implements the iten derivation forests for
+//! the machine.
+
+// TODO: Implement an enumeration for Parent or Segment, perhaps
+// called PaSe.
+
+// TODO: Move functions for handling forests, currently contained
+// within the method derive to this module, and make them aware of the
+// enumeration PaSe.
+
+// TODO: Implement the Item trait from semirings for the item
+// derivation forest, and then we can easily execute items later on.
+
+use graph::{error::Error as GError, GraphLabel, LabelGraph, Parent, ParentsGraph};
+
+use core::borrow::Borrow;
+
+/// A parent or a segment.
+///
+/// A parent is a node with an edge index, which represents a certain
+/// edge.
+///
+/// A segment represents every edge from the root node to the single
+/// terminating node.
+#[allow(unused)]
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+pub enum PaSe {
+    /// An edge from a node, as the n-th child.
+    Parent(usize, usize),
+    /// A segment from a root to the single terminating node.
+    Segment(usize, usize),
+}
+
+impl From<Parent> for PaSe {
+    fn from(value: Parent) -> Self {
+        Self::Parent(value.node(), value.edge())
+    }
+}
+
+impl Default for PaSe {
+    fn default() -> Self {
+        Self::Segment(0, 0)
+    }
+}
+
+impl core::fmt::Display for PaSe {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Self::Parent(node, edge) => write!(f, "the {edge}-th edge from {node}"),
+            Self::Segment(root, leaf) => write!(f, "a segment from {root} to {leaf}"),
+        }
+    }
+}
+
+impl PaSe {
+    fn parent(self) -> Option<Parent> {
+        if let Self::Parent(node, edge) = self {
+            Some(Parent::new(node, edge))
+        } else {
+            None
+        }
+    }
+
+    fn segment(self) -> Option<(usize, usize)> {
+        if let Self::Segment(root, leaf) = self {
+            Some((root, leaf))
+        } else {
+            None
+        }
+    }
+}
+
+/// An internal type that indicates the status of a node as either a
+/// packed, cloned, or plain node.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
+enum ForestLabelType {
+    Packed,
+    #[default]
+    Plain,
+    Cloned(usize),
+}
+
+impl core::fmt::Display for ForestLabelType {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        match self {
+            Self::Packed => write!(f, "packed"),
+            Self::Plain => write!(f, "plain"),
+            Self::Cloned(index) => write!(f, "the {index}-th clone"),
+        }
+    }
+}
+
+/// A type that encodes the properties demanded by a forest.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+pub struct ForestLabel<T: GraphLabel> {
+    label: T,
+    status: ForestLabelType,
+}
+
+impl<T: GraphLabel> core::fmt::Display for ForestLabel<T> {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        writeln!(f, "label: {}, status: {}", self.label, self.status)
+    }
+}
+
+/// The type of erros for converting forest labels.
+#[non_exhaustive]
+#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
+pub enum ForestLabelError {
+    /// Try to pack a cloned node.
+    PackClone,
+    /// Try to clone a packed node.
+    ClonePack,
+}
+
+impl core::fmt::Display for ForestLabelError {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        match self {
+            Self::PackClone => write!(f, "cannot pack a cloned node"),
+            Self::ClonePack => write!(f, "cannot clone a packed node"),
+        }
+    }
+}
+
+impl std::error::Error for ForestLabelError {}
+
+impl<T: GraphLabel> ForestLabel<T> {
+    /// Retrieve the label.
+    pub fn label(&self) -> T {
+        self.label
+    }
+
+    /// Return true if and only if this node is packed.
+    pub fn is_packed(&self) -> bool {
+        matches!(self.status, ForestLabelType::Packed)
+    }
+
+    /// Retrieve the optional clone index.
+    pub fn clone_index(&self) -> Option<usize> {
+        match self.status {
+            ForestLabelType::Cloned(index) => Some(index),
+            _ => None,
+        }
+    }
+
+    /// Try to clone a node.
+    pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
+    where
+        F: Forest<T>,
+    {
+        if self.is_packed() {
+            Err(ForestLabelError::ClonePack)
+        } else {
+            let clone_index = if let Some(old_index) = self.clone_index() {
+                let mut new_index: usize = old_index + 1;
+
+                let mut new_label = Self {
+                    status: ForestLabelType::Cloned(new_index),
+                    ..self
+                };
+
+                while forest.query_label(new_label).is_some() {
+                    new_index += 1;
+                    new_label = Self {
+                        status: ForestLabelType::Cloned(new_index),
+                        ..self
+                    };
+                }
+
+                new_index
+            } else {
+                0
+            };
+
+            Ok(Self {
+                status: ForestLabelType::Cloned(clone_index),
+                ..self
+            })
+        }
+    }
+
+    /// Try to pack a node.
+    pub fn pack(self) -> Result<Self, ForestLabelError> {
+        if self.clone_index().is_some() {
+            Err(ForestLabelError::PackClone)
+        } else {
+            let new_label = Self {
+                status: ForestLabelType::Packed,
+                ..self
+            };
+
+            Ok(new_label)
+        }
+    }
+}
+
+impl<T: GraphLabel> From<T> for ForestLabel<T> {
+    fn from(label: T) -> Self {
+        let status = ForestLabelType::default();
+        Self { label, status }
+    }
+}
+
+/// The expected behaviours of an item derivation forest.
+///
+/// Note that it requires only a subset of the functionalities of
+/// labelled graphs.
+pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
+    /// The type of errors for operations on the forest.
+    type Error: std::error::Error + From<GError> + From<ForestLabelError>;
+
+    /// Return the root of the forest.
+    ///
+    /// A forest without a root is regarded as empty.
+    fn root(&self) -> Option<usize>;
+
+    /// Construct a forest consisting of one leaf node with the given
+    /// label.
+    fn new_leaf(label: T) -> Self;
+
+    /// Detect if the fragment is a prefix of the sub-forest rooted at
+    /// `node_id`.
+    fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
+    where
+        F: Borrow<Self>;
+
+    /// Extend the forest by adjoining another forest at a given node.
+    fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
+    where
+        F: Borrow<Self>;
+
+    /// Clone a node by making a new node and making all the nodes
+    /// that previously pointed to the old node now point to the new
+    /// node, and the new node points to the old node.  Return the
+    /// index of the new node.  In addition, if the old node had
+    /// already been cloned, just return the index of its
+    /// representative.
+    ///
+    /// The labels of the representing node and of the cloned node
+    /// will be handled automatically.
+    fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error>;
+}
+
+pub mod default;
+
+pub mod genins;
+
+pub use genins::generate_fragment;