diff options
Diffstat (limited to 'forest/src')
| -rw-r--r-- | forest/src/default.rs | 144 | ||||
| -rw-r--r-- | forest/src/design.org | 95 | ||||
| -rw-r--r-- | forest/src/lib.rs | 116 |
3 files changed, 146 insertions, 209 deletions
diff --git a/forest/src/default.rs b/forest/src/default.rs index 5e438d4..d3970e9 100644 --- a/forest/src/default.rs +++ b/forest/src/default.rs @@ -1,141 +1,21 @@ //! This file provides a default implementation for the //! [`Forest`][crate::Forest] trait. +#[allow(unused_imports)] use super::*; +#[allow(unused_imports)] use graph::{error::Error as GraphError, ALGraph, Graph}; +#[allow(unused_imports)] use std::collections::{hash_set::Iter, HashMap, HashSet}; -#[derive(Debug, Clone)] -pub struct DefaultForest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> { - graph: ALGraph, - vertex_labels: HashMap<usize, NodeLabel>, - edge_labels: HashMap<(usize, usize), EdgeLabel>, - plugins: HashSet<usize>, - plugouts: HashSet<usize>, -} +// TODO: Use PLGraph instead. -impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Default for DefaultForest<NodeLabel, EdgeLabel> { - fn default() -> Self { - Self { - graph: Default::default(), - vertex_labels: Default::default(), - edge_labels: Default::default(), - plugins: Default::default(), - plugouts: Default::default(), - } - } -} - -impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Graph for DefaultForest<NodeLabel, EdgeLabel> { - type Iter<'a> = <ALGraph as Graph>::Iter<'a> - where - Self: 'a; - - fn is_empty(&self) -> bool { - self.graph.is_empty() - } - - fn nodes_len(&self) -> usize { - self.graph.nodes_len() - } - - fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GraphError> { - self.graph.children_of(node_id) - } - - fn degree(&self, node_id: usize) -> Result<usize, GraphError> { - self.graph.degree(node_id) - } - - fn is_empty_node(&self, node_id: usize) -> Result<bool, GraphError> { - self.graph.is_empty_node(node_id) - } - - fn has_edge(&self, source: usize, target: usize) -> Result<bool, GraphError> { - self.graph.has_edge(source, target) - } - - fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) { - unimplemented!() - } -} - -#[derive(Debug)] -pub struct LabelIter<'a> { - set_iter: Iter<'a, usize>, -} - -impl<'a> Iterator for LabelIter<'a> { - type Item = usize; - - fn next(&mut self) -> Option<Self::Item> { - self.set_iter.next().copied() - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.set_iter.size_hint() - } -} - -impl<'a> ExactSizeIterator for LabelIter<'a> { - fn len(&self) -> usize { - self.set_iter.len() - } -} - -impl<'a> From<Iter<'a, usize>> for LabelIter<'a> { - fn from(set_iter: Iter<'a, usize>) -> Self { - Self { set_iter } - } -} - -impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Forest<NodeLabel, EdgeLabel> - for DefaultForest<NodeLabel, EdgeLabel> -{ - type PluginIter<'a> = LabelIter<'a> - where - Self: 'a; - - type PlugoutIter<'a> = LabelIter<'a> - where - Self: 'a; - - fn plugins(&self) -> Self::PluginIter<'_> { - self.plugins.iter().into() - } - - fn plugouts(&self) -> Self::PlugoutIter<'_> { - self.plugouts.iter().into() - } - - fn plug(&mut self, other: &Self) -> Result<(), Error> { - // PLAN: Produce a BuilderMut, adjust the indices for edges, - // and then add edges between plugs. - // - // Since I cannot touch the underlying nodes directly, I have - // to add the nodes and edges individually. - - todo!() - } - - fn vertex_label(&self, node_id: usize) -> Result<Option<NodeLabel>, Error> { - if node_id >= self.nodes_len() { - return Err(Error::IndexOutOfBounds(node_id, self.nodes_len())); - } - - Ok(self.vertex_labels.get(&node_id).copied()) - } - - fn edge_label(&self, source: usize, target: usize) -> Result<Option<EdgeLabel>, Error> { - if source >= self.nodes_len() { - return Err(Error::IndexOutOfBounds(source, self.nodes_len())); - } - - if target >= self.nodes_len() { - return Err(Error::IndexOutOfBounds(target, self.nodes_len())); - } - - Ok(self.edge_labels.get(&(source, target)).copied()) - } -} +// #[derive(Debug, Clone)] +// pub struct DefaultForest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> { +// graph: ALGraph, +// vertex_labels: HashMap<usize, NodeLabel>, +// edge_labels: HashMap<(usize, usize), EdgeLabel>, +// plugins: HashSet<usize>, +// plugouts: HashSet<usize>, +// } diff --git a/forest/src/design.org b/forest/src/design.org index 771ca4b..09db113 100644 --- a/forest/src/design.org +++ b/forest/src/design.org @@ -28,7 +28,7 @@ topic sooner or later, why not deal with it now? ;P represent this alternation. Packed nodes are not labelled. They just serve the role of putting nodes together. -* Some thoughts [1/3] +* Some thoughts We do not need to attach forest fragments to nodes of nondeterministic finite automata: we just attach to them lists of grammar slots, which @@ -44,23 +44,98 @@ non-terminals. Some caveats: -- [X] Every node in the forest needs to know its parents. This is - needed for "reductions". That is, after we have parsed the entire +- Every node in the forest needs to know its parents. This is needed + for "reductions". That is, after we have parsed the entire expansion for a non-terminal, we need to go back to where that non-terminal was and continue from there. -- [ ] We need to record the expansions of those "virtual nodes". That - is, the virtual nodes represent atomic languages such as [s]^{(t)} - where s is a non-terminal and t is a terminal. To be more specific, - it represents the derivative of the left-linear closure of the +- We need to record the expansions of those "virtual nodes". That is, + the virtual nodes represent atomic languages such as [s]^{(t)} where s + is a non-terminal and t is a terminal. To be more specific, it + represents the derivative of the left-linear closure of the non-terminal s with respect to the terminal t. The left-linear closure of s is the set of all strings (consisting of terminals and non-terminals alike) that are derivable from s alone, without consuming any inputs, by expanding according to the grammar rules. This means that we need to know if which non-terminals were expanded in order to get to a state in [s]^{(t)}. -- [ ] Each edge in the chain-rule machine needs to be labelled also - with a position in the forest. This perfectly solves the problem of - those "plugs"! +- Each edge in the chain-rule machine needs to be labelled also with a + position in the forest. This perfectly solves the problem of those + "plugs"! +* Formal Definition +We need to figure out the definition of the forest. That it to say, +what will the resulting forest look like for a grammar. +Moreover, we need to know how to correspond each step in the +chain-rule machine with the definition of the forest. + +After these two steps, we can easily proceed with the construction of +the chain-rule machine. + +** Axioms + +There are two *axioms* from which the definition of the forests +follows. + +1. Each node has a unique label, given (principally) by three + components: + 1) input range start + 2) input range end + 3) grammar label +2. If different subtrees share the same node label as the root, a + "clone" of the root should be made, and there should be a + "representative" of all clones, which is treated as a normal node + with that label, and all clones are its children. + +The first axiom ensures that the size of the forest is bounded by the +cube of \(n\), \(n\) is the length of the input sequence. And the +second axiom specifies what to do when subtrees share a parent. + +Since the clones are introduced only when subtrees share a parent, +their number cannot exceed the number of nodes of a forest without +clones. This shows that adding clones does not affect the growth rate +of the size of forests. + +A remark: the /clones/ are called /packed nodes/ in the traditional +terminology, but the terminology of a clone makes more sense to me. + +** Correspondence with chain-rule machine + +Every edge in the chain-rule machine corresponds to an edge in the +forest; denote this correspondence by \(f\). + +The chain-rule operation can be described as follows: + +1. Start with an edge \(e\) with children \(d_1, \ldots, d_n\) in the + chain-rule machine. +2. Prepare a new forest fragment as follows. + 1) For every child \(g\) of \(e\) in the atomic language, if \(g\) + is the terminal that appears as the current input \(t\), let the + new fragment be defined as the node moved by \(g\), alone. + 2) If \(g\) is a non-terminal and its first-set contains \(t\), + then for every left-linearly closed child of \(g\) that is + labelled \(t\), denoted as \(h\), then let the fragment be + defined as the node moved by \(g\), with the pre-recorded + left-linear expansion information from \(g\) to \(h\) appended + as children. +3. For \(i=1,\ldots,n\), consider the edge \(f(d_i)\) in the forest. + There are three cases: + 1) If the next edge is empty, that means we have found something + totally new to add to the forest, so we just add that. + 2) If the next edge after \(f(e)\) contains the new fragment as a + sub-tree already, this means the current branch has already been + explored before, and we have nothing else to do. + 3) If the next edge is non-empty and does not match the new + fragment, this means we have a conflict with a previously found + branch. We solve it simply by following the second axiom above: + we make the node that is the source of \(f(e)\) a clone, and add + the new fragment under a new clone. Note that if the node is + already a clone, we just make a clone under the parent of that + clone. +4. Update the correspondence \(f\) by updating \(f(g)\) and \(f(h)\) + accordingly. + +In this process we always follow the first axiom by ensuring that the +labels of the forest are unique to each node, except for those clones, +which are only created by following the second axiom. 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<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> { - /// The type of the resulting forest. - type Output: Forest<NodeLabel, EdgeLabel>; - - /// 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<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> { +// /// The type of the resulting forest. +// type Output: Forest<NodeLabel, EdgeLabel>; + +// /// 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<NodeLabel: GraphLabel, EdgeLabel: GraphLabel>: Graph { - /// Type of iterator of plug-in nodes. - type PluginIter<'a>: Iterator<Item = usize> + 'a - where - Self: 'a; - - /// Type of iterator of plug-out nodes. - type PlugoutIter<'a>: Iterator<Item = usize> + '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<Option<NodeLabel>, 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<Option<EdgeLabel>, Error>; +/// Note that it requires only a subset of the functionalities of +/// labelled graphs. +pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<T> { + /// The type of errors for operations on the forest. + type Error: std::error::Error + From<graph::error::Error>; + + /// Detect if the fragment is a prefix of the sub-forest rooted at + /// `node_id`. + fn is_prefix<F: AsRef<Self>>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>; + + /// Extend the forest by adjoining another forest at a given node. + fn plant<F: AsRef<Self>>(&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; |