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/item/mod.rs | 252 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 252 insertions(+) create mode 100644 chain/src/item/mod.rs (limited to 'chain/src/item/mod.rs') 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 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 { + 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 { + label: T, + status: ForestLabelType, +} + +impl core::fmt::Display for ForestLabel { + 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 ForestLabel { + /// 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 { + match self.status { + ForestLabelType::Cloned(index) => Some(index), + _ => None, + } + } + + /// Try to clone a node. + pub fn clone(self, forest: &F) -> Result + where + F: Forest, + { + 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 { + if self.clone_index().is_some() { + Err(ForestLabelError::PackClone) + } else { + let new_label = Self { + status: ForestLabelType::Packed, + ..self + }; + + Ok(new_label) + } + } +} + +impl From for ForestLabel { + 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: ParentsGraph + LabelGraph> { + /// The type of errors for operations on the forest. + type Error: std::error::Error + From + From; + + /// Return the root of the forest. + /// + /// A forest without a root is regarded as empty. + fn root(&self) -> Option; + + /// 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(&self, node_id: usize, fragment: F) -> Result + where + F: Borrow; + + /// Extend the forest by adjoining another forest at a given node. + fn plant(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error> + where + F: Borrow; + + /// 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; +} + +pub mod default; + +pub mod genins; + +pub use genins::generate_fragment; -- cgit v1.2.3-18-g5258