From b8a2d05a3c0d835556d5ddbd44e4a1e201302af5 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Thu, 10 Aug 2023 11:14:04 +0800 Subject: Move the trait `Forest` to the crate "forest". The purpose of this change is to share this trait with other crates, such as the forth-coming "semiring" crate that will be responsible for handling some simple semiring operations as well as the querying, in my plans. --- forest/src/lib.rs | 102 +++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 70 insertions(+), 32 deletions(-) (limited to 'forest/src/lib.rs') diff --git a/forest/src/lib.rs b/forest/src/lib.rs index 0b1092f..a888fae 100644 --- a/forest/src/lib.rs +++ b/forest/src/lib.rs @@ -1,26 +1,27 @@ #![warn(missing_docs)] -//! This file defines the expected behaviours of forests, and provides -//! a default implementation for forests. +//! This file defines the expected behaviours of forests. //! -//! The default forest actually implements the so-called shared packed -//! parse forest, or SPPF. It packs sub-trees with the same parents -//! under the same branch, and lets nodes from different branches -//! share the same children, and hence the name. +//! The forests are the basis of the `semiring` crate. use graph::{error::Error as GError, GraphLabel, LabelGraph, ParentsGraph}; +use std::borrow::Borrow; + /// 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 { +pub enum ForestLabelType { + /// A packed node Packed, + /// A plain node #[default] Plain, + /// A cloned node Cloned(usize), } -impl core::fmt::Display for ForestLabelType { - fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { +impl std::fmt::Display for ForestLabelType { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { Self::Packed => write!(f, "packed"), Self::Plain => write!(f, "plain"), @@ -36,14 +37,17 @@ pub struct ForestLabel { 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) +impl std::fmt::Display for ForestLabel { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + if !matches!(self.status, ForestLabelType::Plain) { + write!(f, "{}, {}", self.label, self.status) + } else { + write!(f, "{}", self.label) + } } } /// 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. @@ -52,8 +56,8 @@ pub enum ForestLabelError { ClonePack, } -impl core::fmt::Display for ForestLabelError { - fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { +impl std::fmt::Display for ForestLabelError { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { Self::PackClone => write!(f, "cannot pack a cloned node"), Self::ClonePack => write!(f, "cannot clone a packed node"), @@ -64,33 +68,50 @@ impl core::fmt::Display for ForestLabelError { impl std::error::Error for ForestLabelError {} impl ForestLabel { + /// Construct a new label with the inner `label` and `status`. + pub fn new(label: T, status: ForestLabelType) -> Self { + Self { label, status } + } + /// Retrieve the label. pub fn label(&self) -> T { self.label } + /// Retrieve the status. + pub fn status(&self) -> ForestLabelType { + self.status + } + /// Return true if and only if this node is packed. pub fn is_packed(&self) -> bool { - matches!(self.status, ForestLabelType::Packed) + self.status == ForestLabelType::Packed } /// Retrieve the optional clone index. - pub fn is_cloned(&self) -> Option { - match self.status { - ForestLabelType::Cloned(index) => Some(index), - _ => None, + pub fn clone_index(&self) -> Option { + if let ForestLabelType::Cloned(index) = self.status { + Some(index) + } else { + None } } + /// Return true if and only if this node is a plain node. + pub fn is_plain(&self) -> bool { + self.status == ForestLabelType::Plain + } + /// Try to clone a node. pub fn clone(self, forest: &F) -> Result where - F: Forest, + F: LabelGraph>, { if self.is_packed() { + dbg!(); Err(ForestLabelError::ClonePack) } else { - let clone_index = if let Some(old_index) = self.is_cloned() { + let clone_index = if let Some(old_index) = self.clone_index() { let mut new_index: usize = old_index + 1; let mut new_label = Self { @@ -120,7 +141,7 @@ impl ForestLabel { /// Try to pack a node. pub fn pack(self) -> Result { - if self.is_cloned().is_some() { + if self.clone_index().is_some() { Err(ForestLabelError::PackClone) } else { let new_label = Self { @@ -140,7 +161,7 @@ impl From for ForestLabel { } } -/// The expected behaviours of a forest. +/// The expected behaviours of an item derivation forest. /// /// Note that it requires only a subset of the functionalities of /// labelled graphs. @@ -157,28 +178,45 @@ pub trait Forest: ParentsGraph + LabelGraph> { /// label. fn new_leaf(label: T) -> Self; + /// Transform the label at the given node. + fn transform_label( + &mut self, + node_id: usize, + transform: impl FnOnce(T) -> T, + ) -> Result<(), Self::Error>; + /// 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: AsRef; + 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: AsRef; + 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 - /// representitave. + /// index of the new node. However, if, and only if, + /// `no_new_clone` is `true`, do not make a new clone; instead + /// return the clone index that would be used if a new clone was + /// made. + /// + /// Also, `preserved_edges_num` many edges out of the old node + /// will be copied to be the children of the new node. /// /// The labels of the representing node and of the cloned node /// will be handled automatically. - fn clone_node(&mut self, node_id: usize) -> Result; + fn clone_node( + &mut self, + node_id: usize, + preserved_edges_num: usize, + no_new_clone: bool, + ) -> Result; } -pub mod default; -pub use default::Error; +pub mod bytes; + +pub use bytes::forest_to_bytes; -- cgit v1.2.3-18-g5258