From 1a3d346f413325ed37848a6b2526e8e729269833 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Wed, 11 Jan 2023 23:47:26 +0800 Subject: Record left-linear expansion and forest format Now the grammar will record the left-linear expansions when generating the nondeterministic finite automaton frmo its rules, and will record whether an edge in the nondeterministic finite automaton comes from a left-linear expansion. The latter is needed because while performing a chain-rule derivation, we do not need the left-linear expanded derivations in the "first layer". This might well have been the root cause of the bad performance of the previous version of this package. Also I have figured out how to properly generate and handle parse forests while manipulating the "chain-rule machine". --- forest/src/lib.rs | 116 +++++++++++++++++++++++------------------------------- 1 file changed, 49 insertions(+), 67 deletions(-) (limited to 'forest/src/lib.rs') diff --git a/forest/src/lib.rs b/forest/src/lib.rs index 3925bd5..c2f4988 100644 --- a/forest/src/lib.rs +++ b/forest/src/lib.rs @@ -1,3 +1,4 @@ +#![warn(missing_docs)] //! This file defines the expected behaviours of forests, and provides //! a default implementation for forests. //! @@ -10,12 +11,16 @@ //! out-coming and in-coming plugs. These plugs are used to join //! different fragments of forests together. -use graph::{Graph, GraphLabel}; +use graph::{GraphLabel, LabelGraph, ParentsGraph}; use core::fmt::Display; +// TODO: move this to default + +/// The type of errors for forest operations. #[derive(Debug)] pub enum Error { + /// An index is out of bounds. IndexOutOfBounds(usize, usize), } @@ -31,75 +36,52 @@ impl Display for Error { impl std::error::Error for Error {} -/// A builder of a forest. -pub trait ForestBuilder { - /// The type of the resulting forest. - type Output: Forest; - - /// Construct a new builder with only one node with the given - /// label. - fn new_leaf(label: NodeLabel) -> Self; - - /// Add a child to the builder the given labels for the new node - /// and the added edge. - /// - /// All plug-out nodes within the builder should have a new child - /// with the specified labels, and hence multiple children might - /// be added, and the plug-out nodes should be modified - /// accordingly. - fn add_children(&mut self, vertex_label: NodeLabel, edge_labe: EdgeLabel); - - /// Build the forest. - fn build(self) -> Self::Output; - - /// Build the forest from a reference. - fn build_ref(&self) -> Self::Output; -} +// /// A builder of a forest. +// pub trait ForestBuilder { +// /// The type of the resulting forest. +// type Output: Forest; + +// /// Construct a new builder with only one node with the given +// /// label. +// fn new_leaf(label: NodeLabel) -> Self; + +// /// Add a child to the builder the given labels for the new node +// /// and the added edge. +// /// +// /// All plug-out nodes within the builder should have a new child +// /// with the specified labels, and hence multiple children might +// /// be added, and the plug-out nodes should be modified +// /// accordingly. +// fn add_children(&mut self, vertex_label: NodeLabel, edge_labe: EdgeLabel); + +// /// Build the forest. +// fn build(self) -> Self::Output; + +// /// Build the forest from a reference. +// fn build_ref(&self) -> Self::Output; +// } + +// FIXME: The trait should be re-designed. /// The expected behaviours of a forest. /// -/// Note that it contains a "striped down" version of the labelled -/// graphs. -pub trait Forest: Graph { - /// Type of iterator of plug-in nodes. - type PluginIter<'a>: Iterator + 'a - where - Self: 'a; - - /// Type of iterator of plug-out nodes. - type PlugoutIter<'a>: Iterator + 'a - where - Self: 'a; - - /// Return the plug-in nodes - fn plugins(&self) -> Self::PluginIter<'_>; - - /// Return the plug-out nodes - fn plugouts(&self) -> Self::PlugoutIter<'_>; - - /// Plug another forest onto this forest. - /// - /// The plug-out nodes of this forest will be joined onto the - /// plug-in nodes of the joining forest. - /// - /// # Performance warning - /// - /// It is recommended to only call this function with a "small" - /// `other`, as this function might copy the whole graph - /// individually, node by node and edge by edge. - fn plug(&mut self, other: &Self) -> Result<(), Error>; - - /// Return the vertex label. - /// - /// A vertex may not have labels. - fn vertex_label(&self, node_id: usize) -> Result, Error>; - - /// Return the edge label. - /// - /// An edge may have no labels. If there is no edge from the - /// given source to the given target, then `Ok(None)` is returned - /// as well. - fn edge_label(&self, source: usize, target: usize) -> Result, Error>; +/// 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; + + /// 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; + + /// Extend the forest by adjoining another forest at a given node. + fn plant>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error>; + + /// 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. + fn clone(&mut self, node_id: usize) -> Result<(), Self::Error>; } pub mod default; -- cgit v1.2.3-18-g5258