diff options
| -rw-r--r-- | chain/src/atom/default.rs | 10 | ||||
| -rw-r--r-- | chain/src/default.rs | 10 | ||||
| -rw-r--r-- | chain/src/item/default/mod.rs | 9 | ||||
| -rw-r--r-- | forest/Cargo.toml | 1 | ||||
| -rw-r--r-- | forest/src/bytes.rs | 280 | ||||
| -rw-r--r-- | forest/src/iter/mod.rs | 91 | ||||
| -rw-r--r-- | forest/src/iter/query.rs | 372 | ||||
| -rw-r--r-- | forest/src/lib.rs | 2 | ||||
| -rw-r--r-- | graph/src/labelled/binary.rs | 9 | ||||
| -rw-r--r-- | graph/src/labelled/double.rs | 10 | ||||
| -rw-r--r-- | graph/src/labelled/mod.rs | 3 | ||||
| -rw-r--r-- | graph/src/labelled/simple.rs | 579 | ||||
| -rw-r--r-- | graph/src/lib.rs | 65 | ||||
| -rw-r--r-- | graph_macro/src/lib.rs | 2 | ||||
| -rw-r--r-- | nfa/src/default/nfa.rs | 10 | ||||
| -rw-r--r-- | nfa/src/default/regex.rs | 6 | ||||
| -rw-r--r-- | semiring/Cargo.toml | 6 |
17 files changed, 1457 insertions, 8 deletions
diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs index df61b6f..c6289f1 100644 --- a/chain/src/atom/default.rs +++ b/chain/src/atom/default.rs @@ -213,6 +213,11 @@ impl LabelGraph<LabelType<TNT>> for DefaultAtom { where Self: 'b; + type TupleIter<'b> = <DefaultNFA<LabelType<TNT>> as LabelGraph<LabelType<TNT>>>::TupleIter<'b> + where + Self: 'b, + DOption<TNT>: 'b; + type LabelIter<'b> = <DefaultNFA<LabelType<TNT>> as LabelGraph<LabelType<TNT>>>::LabelIter<'b> where Self: 'b, @@ -247,6 +252,11 @@ impl LabelGraph<LabelType<TNT>> for DefaultAtom { } #[inline] + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GraphError> { + self.nfa.tuples_of(node_id) + } + + #[inline] fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, GraphError> { self.nfa.labels_of(node_id) } diff --git a/chain/src/default.rs b/chain/src/default.rs index 85e3c8f..042f84e 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -324,6 +324,11 @@ impl LabelGraph<Edge> for DefaultChain { where Self: 'a; + type TupleIter<'a> = <DLGraph<Edge> as LabelGraph<Edge>>::TupleIter<'a> + where + Self: 'a, + Edge: 'a; + type LabelIter<'a> = <DLGraph<Edge> as LabelGraph<Edge>>::LabelIter<'a> where Self: 'a, @@ -349,6 +354,11 @@ impl LabelGraph<Edge> for DefaultChain { } #[inline] + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + self.graph.tuples_of(node_id) + } + + #[inline] fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, GError> { self.graph.labels_of(node_id) } diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs index 01e463e..f532805 100644 --- a/chain/src/item/default/mod.rs +++ b/chain/src/item/default/mod.rs @@ -127,6 +127,11 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> { where Self: 'a; + type TupleIter<'a> = std::iter::Empty<(T, usize)> + where + Self: 'a, + T: 'a; + type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)> where Self: 'a, @@ -163,6 +168,10 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> { unimplemented!("edges have no labels") } + fn tuples_of(&self, _node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + unimplemented!("edges have no labels") + } + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> { unimplemented!("edges have no labels") } diff --git a/forest/Cargo.toml b/forest/Cargo.toml index 5702265..7944bc4 100644 --- a/forest/Cargo.toml +++ b/forest/Cargo.toml @@ -13,6 +13,7 @@ test-print-viz = [] [dependencies] graph = { path = "../graph" } +graph_macro = { path = "../graph_macro" } grammar = { path = "../grammar" } # This should be integrated in the package, but it is not yet done.
\ No newline at end of file diff --git a/forest/src/bytes.rs b/forest/src/bytes.rs index 951abad..d0d7e1e 100644 --- a/forest/src/bytes.rs +++ b/forest/src/bytes.rs @@ -78,6 +78,9 @@ use super::Forest; use grammar::{GrammarLabel, GrammarLabelType, TNT}; +use graph::error::Error as GError; + +use std::array::TryFromSliceError; /// Convert any type that implements the `Forest` trait into a /// sequence of bytes. @@ -174,3 +177,280 @@ pub fn forest_to_bytes<F: Forest<GrammarLabel>>(forest: &F) -> Vec<u8> { bytes } + +/// The type of a forest that is represented as a sequence of bytes. +#[derive(Debug, Clone, Default)] +pub struct BytesForest { + /// The sequence of bytes. + bytes: Vec<u8>, + /// The number of nodes. + nodes_len: usize, + /// The offset of labels + offset: usize, +} + +/// The errors encountered when parsing a sequence of bytes into a +/// forest. +#[derive(Debug)] +pub enum BytesError { + /// File size and forest length do not match. + LengthNotMatched(usize, usize), + /// The underlying sequence has the wrong length. + WrongBytesLen(usize, usize), + /// The file is too small. + TooSmall(usize, usize), + /// The special mark at the beginning is corrupted. + SpecialCorrupted(u8, u8, u8), + /// An error occurs during conversion of slices. + WrongSliceConversion(TryFromSliceError), + /// The data indicates a wrong offset. + InvalidOffset(usize, usize), + /// Wrong node index. + WrongNodeIndex(usize, usize), +} + +impl std::fmt::Display for BytesError { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::WrongBytesLen(wrong, correct) => write!( + f, + "the sequence has length {wrong} but should have length {correct}" + ), + Self::LengthNotMatched(file, forest) => write!( + f, + "the file size is {file}, but the file indicates that the size should be {forest}" + ), + Self::TooSmall(len, threshold) => { + write!(f, "the file size {len} is less than {threshold} bytes") + } + Self::SpecialCorrupted(a, b, c) => { + write!(f, "the special mark is [{a}, {b}, {c}] which is wrong") + } + Self::WrongSliceConversion(e) => { + write!(f, "error during slice conversion: {e}") + } + Self::InvalidOffset(offset, len) => write!( + f, + "Data says offset = {offset} but the total length is {len}" + ), + Self::WrongNodeIndex(index, len) => write!( + f, + "node index {index} is greater than or equal to the length {len} of nodes" + ), + } + } +} + +impl From<TryFromSliceError> for BytesError { + fn from(value: TryFromSliceError) -> Self { + Self::WrongSliceConversion(value) + } +} + +impl std::error::Error for BytesError {} + +impl TryFrom<Vec<u8>> for BytesForest { + type Error = BytesError; + + fn try_from(bytes: Vec<u8>) -> Result<Self, Self::Error> { + let forest_len = bytes.len(); + + if forest_len < 27 { + return Err(BytesError::TooSmall(forest_len, 27)); + } + + let indicated_len = usize::from_be_bytes((&bytes[..8]).try_into()?); + + if forest_len != indicated_len { + return Err(BytesError::LengthNotMatched(forest_len, indicated_len)); + } + + let nodes_len = usize::from_be_bytes((&bytes[11..19]).try_into()?); + + let special_marks = &bytes[8..11]; + + if special_marks != [114, 101, 112] { + return Err(BytesError::SpecialCorrupted( + special_marks[0], + special_marks[1], + special_marks[2], + )); + } + + let offset = usize::from_be_bytes((&bytes[19..27]).try_into()?); + + let threshold = std::cmp::max(offset + 34 * nodes_len, 27 + 16 * nodes_len); + + if forest_len < threshold { + return Err(BytesError::TooSmall(forest_len, threshold)); + } + + let mut total_degree = 0usize; + + for node in 0..nodes_len { + let degree = + usize::from_be_bytes((&bytes[(27 + 16 * node)..(35 + 16 * node)]).try_into()?); + + total_degree += degree; + } + + let total_degree = total_degree; + + let correct_len: usize = 27 + 50 * nodes_len + 8 * total_degree; + + if forest_len != correct_len { + return Err(BytesError::WrongBytesLen(forest_len, correct_len)); + } + + for node in 0..nodes_len { + let degree = + usize::from_be_bytes((&bytes[(27 + 16 * node)..(35 + 16 * node)]).try_into()?); + + let node_offset = + usize::from_be_bytes((&bytes[(35 + 16 * node)..(43 + 16 * node)]).try_into()?); + + if forest_len <= node_offset + 8 * degree { + return Err(BytesError::InvalidOffset(node_offset, forest_len)); + } + + for n in 0..degree { + let target = usize::from_be_bytes( + (&bytes[(node_offset + 8 * n)..(node_offset + 8 * n + 8)]).try_into()?, + ); + + if nodes_len <= target { + return Err(BytesError::WrongNodeIndex(target, nodes_len)); + } + } + } + + Ok(Self { + bytes, + nodes_len, + offset, + }) + } +} + +/// The delegation of iterators for children of nodes. +#[derive(Debug, Clone)] +pub struct BytesChildrenIter<'a> { + vec: &'a [u8], + offset: usize, + degree: usize, + current: usize, +} + +impl<'a> Iterator for BytesChildrenIter<'a> { + type Item = usize; + + fn next(&mut self) -> Option<Self::Item> { + if self.current + 1 >= self.degree { + return None; + } + + let len = self.vec.len(); + + if self.offset + 8 * self.degree > len { + dbg!(); + return None; + } + + Some(usize::from_be_bytes( + (&self.vec[(self.offset + 8 * self.current)..(self.offset + 8 * self.current + 8)]) + .try_into() + .ok()?, + )) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (self.degree, Some(self.degree)) + } +} + +impl<'a> ExactSizeIterator for BytesChildrenIter<'a> { + fn len(&self) -> usize { + self.degree + } +} + +impl graph::Graph for BytesForest { + type Iter<'a> = BytesChildrenIter<'a> + where + Self: 'a; + + fn is_empty(&self) -> bool { + self.bytes.is_empty() + } + + fn nodes_len(&self) -> usize { + self.nodes_len + } + + fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> { + if node_id >= self.nodes_len { + return Err(GError::IndexOutOfBounds(node_id, self.nodes_len)); + } + + let degree = usize::from_be_bytes( + (&self.bytes[(27 + 16 * node_id)..(35 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + let offset = usize::from_be_bytes( + (&self.bytes[(35 + 16 * node_id)..(43 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + let current = 0; + + let vec = &self.bytes; + + Ok(BytesChildrenIter { + vec, + offset, + degree, + current, + }) + } + + fn degree(&self, node_id: usize) -> Result<usize, GError> { + if node_id >= self.nodes_len { + return Err(GError::IndexOutOfBounds(node_id, self.nodes_len)); + } + + let degree = usize::from_be_bytes( + (&self.bytes[(27 + 16 * node_id)..(35 + 16 * node_id)]) + .try_into() + .unwrap(), + ); + + Ok(degree) + } + + fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> { + Ok(self.degree(node_id)? == 0) + } + + fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> { + for child in self.children_of(source)? { + if child == target { + return Ok(true); + } + } + + Ok(false) + } + + fn replace_by_builder(&mut self, builder: impl graph::Builder<Result = Self>) { + let result = builder.build(); + + self.nodes_len = result.nodes_len; + self.offset = result.offset; + self.bytes = result.bytes; + } +} + +// TODO: Implement labelgraph diff --git a/forest/src/iter/mod.rs b/forest/src/iter/mod.rs new file mode 100644 index 0000000..49aa4f1 --- /dev/null +++ b/forest/src/iter/mod.rs @@ -0,0 +1,91 @@ +//! This module defines the expected behaviours of "iterators of +//! forests", or "walkers of forests". Moreover, an implementation +//! that provides querying capabilities is provided. + +use super::*; + +/// The state of the iterator. +#[derive(Debug, Copy, Clone, Eq, PartialEq)] +pub enum State { + /// The iterator goes to the next state. + Continue, + /// The iterator cannot proceed anymore. + Finish, + /// The iterator finishes for this tree, but there are trees not + /// visited yet. + ChangeBranch, +} + +impl std::fmt::Display for State { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> { + use State::*; + match self { + Continue => write!(f, "next"), + Finish => write!(f, "finished"), + ChangeBranch => write!( + f, + "this branch is finished, but there are unvisited branches" + ), + } + } +} + +/// An iterator is able to walk any forest, so no forest type is +/// associated with iterators. Essentially speaking, an iterator just +/// provides the abilities to iterate through nodes of forests which +/// meet certain conditions, in certain orders. +pub trait ForestIter: Default { + /// Return the currenty visited node. + /// + /// If the iterator is not visiting any node, return `None`. + /// + /// The default implementation always returns `None`. + fn current(&self) -> Option<usize> { + None + } + + /// The type of labels that can be iterated by this iterator. + type ForestLabel: GraphLabel; + + /// The type of objects of iteration. + type Item<'a>: Default + where + Self: 'a; + + /// The type of iteration errors. + type Error: std::error::Error + From<graph::error::Error>; + + /// Walk to the next node according to this iterator. + /// + /// `forest` is any type that implements the `Forest` trait. + /// Theoretically, the forest can be different in two calls of + /// this method. This makes it somehow more flexible. + /// + /// `root` specifies the root of the sub-forest to iterate. + /// + /// Of course this flexibility is not the main reason for the + /// design. My purpose is to decouple the iterator from the + /// forest, so that the iterator can be as simple as a wrapper of + /// a vector of unsigned integers. + /// + /// The default implementation is lazy and always returns + /// "finished". + fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error> + where + F: LabelGraph<ForestLabel<Self::ForestLabel>>, + { + // just to silence the compiler + let _f = forest; + let _r = root; + + Ok(State::Finish) + } + + /// Reset the progress of this iterator so that it can be used to + /// iterate any forest again. + /// + /// The default implementation does nothing. + fn clear(&mut self) {} +} + +pub mod query; diff --git a/forest/src/iter/query.rs b/forest/src/iter/query.rs new file mode 100644 index 0000000..aff8eef --- /dev/null +++ b/forest/src/iter/query.rs @@ -0,0 +1,372 @@ +//! This module implements an iterator of forests, which provides +//! querying capabilities. + +use super::*; + +use graph::{error::Error as GError, labelled::SLGraph, Graph}; + +use graph_macro::Graph; + +/// The label of a query graph. +/// +/// Such a label is responsible for matching forest labels. +pub trait QueryLabel: GraphLabel { + /// The type of labels this matches against. + type Obj: GraphLabel; + + /// Determine whether or not a label matches this query label. + fn matches(&self, label: Self::Obj, status: ForestLabelType) -> bool { + let _ = label; + let _ = status; + + false + } + + /// Perform the query for one single query label. + fn run<F>( + &self, + forest: &F, + node: usize, + packs: &mut Vec<(usize, usize)>, + ) -> Result<Option<usize>, QRError> + where + F: LabelGraph<ForestLabel<<Self as QueryLabel>::Obj>>, + { + let mut dfs_stack: Vec<usize> = vec![node]; + + let nodes_len = forest.nodes_len(); + + while let Some(node) = dfs_stack.pop() { + let label = match forest.vertex_label(node) { + Ok(None) => return Err(QRError::NodeNoLabel(node)), + Err(_) => return Err(QRError::IndexOutOfBounds(node, nodes_len)), + Ok(Some(label)) => label, + }; + + let status = label.status(); + let label = label.label(); + + if status == ForestLabelType::Packed { + packs.push((node, 0)); + + dfs_stack.extend(forest.children_of(node).unwrap().take(1)); + + continue; + } + + if self.matches(label, status) { + return Ok(Some(node)); + } + + dfs_stack.extend( + forest + .children_of(node) + .unwrap() + .collect::<Vec<_>>() + .into_iter() + .rev(), + ); + } + + Ok(None) + } +} + +/// How should the current query skip nodes +#[derive(Debug, Clone, Copy, Default, Ord, PartialOrd, Hash, Eq, PartialEq)] +pub enum SkipState { + /// Skip anything in the depth-first search + Any, + /// Skip siblings + Sibling, + /// Do not skip + #[default] + None, +} + +impl std::fmt::Display for SkipState { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::Any => write!(f, "skip anything"), + Self::Sibling => write!(f, "skip siblings"), + Self::None => write!(f, "no skipping"), + } + } +} + +impl From<bool> for SkipState { + fn from(value: bool) -> Self { + if value { + Self::Sibling + } else { + Self::None + } + } +} + +/// The type that represents queries as dependency graphs of query +/// labels. +/// +/// The labels of vertices are query labels that match against forest +/// labels, whereas the labels of graphs indicate whether or not the +/// edge should allow skipping siblings before matching. +#[derive(Debug, Clone, Graph)] +pub struct Query<T: QueryLabel> { + graph: SLGraph<SkipState>, + vertex_labels: Vec<T>, + root: Option<usize>, +} + +impl<T: QueryLabel> Query<T> { + /// Construct a new query from raw fields. + pub fn new(graph: SLGraph<SkipState>, vertex_labels: Vec<T>, root: Option<usize>) -> Self { + Self { + graph, + vertex_labels, + root, + } + } + + /// Return the root of this query. + /// + /// This returns `None` if and only if the graph is empty. + pub fn root(&self) -> Option<usize> { + self.root + } + + /// Return the label of the given node. + /// + /// This cannot be implemented as a method of the `LabelGraph` + /// trait as the type differs from that of the labels. + #[inline] + pub fn label_of_vertex(&self, node: usize) -> Result<T, GError> { + self.vertex_labels + .get(node) + .copied() + .ok_or(GError::IndexOutOfBounds(node, self.vertex_labels.len())) + } +} + +impl<T: QueryLabel> Default for Query<T> { + fn default() -> Self { + let graph = Default::default(); + let vertex_labels = Vec::new(); + let root = None; + + Self { + graph, + vertex_labels, + root, + } + } +} + +// delegation of labelgraph + +impl<T: QueryLabel> LabelGraph<SkipState> for Query<T> { + type Iter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::Iter<'a> + where + Self: 'a; + + type TupleIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::TupleIter<'a> + where + Self: 'a; + + type LabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::LabelIter<'a> + where + Self: 'a; + + type EdgeLabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::EdgeLabelIter<'a> + where + Self: 'a; + + #[inline] + fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> { + self.graph.edge_label(source, target) + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &SkipState, + ) -> Result<<Self as LabelGraph<SkipState>>::Iter<'_>, GError> { + unimplemented!("Unsupported operation") + } + + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> { + unimplemented!("Unsupported operation") + } + + #[inline] + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + self.graph.tuples_of(node_id) + } + + #[inline] + fn has_edge_label( + &self, + node_id: usize, + label: &SkipState, + target: usize, + ) -> Result<bool, GError> { + self.graph.has_edge_label(node_id, label, target) + } +} + +#[derive(Debug, Clone)] +/// The type of errors that can occur when querying forests. +pub enum QRError { + /// AN index is out of bounds. + IndexOutOfBounds(usize, usize), + /// A node has no labels while it is required to have one. + NodeNoLabel(usize), + /// Encounter an invalid error in converting from an error of + /// graphs. + InvalidGraphError(GError), +} + +impl std::fmt::Display for QRError { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + QRError::IndexOutOfBounds(n, b) => { + write!(f, "index {n} out of bound {b}") + } + QRError::NodeNoLabel(n) => write!(f, "the node {n} has no label but should have one"), + QRError::InvalidGraphError(g) => { + write!(f, "an invalid error for forest iterators: {g}") + } + } + } +} + +impl std::error::Error for QRError {} + +impl From<GError> for QRError { + fn from(value: GError) -> Self { + match value { + GError::IndexOutOfBounds(n, b) => Self::IndexOutOfBounds(n, b), + _ => Self::InvalidGraphError(value), + } + } +} + +/// An implementation of the forest iterator for querying purposes. +#[derive(Debug, Clone)] +pub struct QRun<T: QueryLabel> { + /// The currently visited node. + current: Option<usize>, + /// The queries dependency graph. + query: Query<T>, + /// The packed nodes that can be used to change to another branch + /// if needed. + packs: Vec<usize>, +} + +impl<T: QueryLabel> Default for QRun<T> { + fn default() -> Self { + let current = Default::default(); + let query = Default::default(); + let packs = Default::default(); + + Self { + current, + query, + packs, + } + } +} + +impl<T: QueryLabel> ForestIter for QRun<T> { + #[inline] + fn current(&self) -> Option<usize> { + self.current + } + + type ForestLabel = <T as QueryLabel>::Obj; + + type Item<'a> = Option<&'a [usize]> + where + Self: 'a; + + type Error = QRError; + + #[allow(unused)] + #[allow(clippy::collapsible_if)] + fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error> + where + F: LabelGraph<ForestLabel<Self::ForestLabel>>, + { + let query_root = if let Some(r) = self.query.root() { + r + } else { + return Ok(State::Finish); + }; + + #[derive(Debug, Clone, Copy)] + enum Item<T: Copy + Clone + std::fmt::Debug> { + Seen(T), + Unseen(T), + } + + use Item::*; + + impl<T: Copy + Clone + std::fmt::Debug> Item<T> { + fn is_seen(self) -> bool { + matches!(self, Self::Seen(_)) + } + + fn value(&self) -> T { + match self { + Seen(v) => *v, + Unseen(v) => *v, + } + } + } + + let query_len = self.query.nodes_len(); + + let mut stack: Vec<Item<(SkipState, usize, usize)>> = Vec::with_capacity(query_len); + + stack.push(Unseen((SkipState::Any, root, query_root))); + + let mut parents_stack: Vec<usize> = Vec::with_capacity(query_len); + + let mut match_result = false; + + while let Some(item) = stack.pop() { + if item.is_seen() { + if match_result { + continue; + } + + // fallback + } + + let (state, top, qtop) = item.value(); + + let top_label = forest.vertex_label(top)?.ok_or(QRError::NodeNoLabel(top))?; + + let query_label = self.query.label_of_vertex(qtop)?; + + if query_label.matches(top_label.label(), top_label.status()) { + // Success branch + + match_result = true; + + // TODO: Deal with captures later + } else { + // Failure branch + + match_result = false; + } + } + + todo!() + } + + #[inline] + fn clear(&mut self) { + self.current.take(); + self.packs.clear(); + } +} diff --git a/forest/src/lib.rs b/forest/src/lib.rs index a888fae..c3ee706 100644 --- a/forest/src/lib.rs +++ b/forest/src/lib.rs @@ -220,3 +220,5 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> { pub mod bytes; pub use bytes::forest_to_bytes; + +pub mod iter; diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs index 5120522..862f25b 100644 --- a/graph/src/labelled/binary.rs +++ b/graph/src/labelled/binary.rs @@ -420,6 +420,11 @@ impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> { Self: 'a, T: 'a; + type TupleIter<'a> = std::iter::Empty<(T, usize)> + where + Self: 'a, + T: 'a; + #[inline] fn query_label(&self, label: T) -> Option<usize> { self.label_index_map.get(&label).copied() @@ -446,6 +451,10 @@ impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> { unimplemented!("Edges have no labels") } + fn tuples_of(&self, _node_id: usize) -> Result<Self::TupleIter<'_>, Error> { + unimplemented!("Edges have no labels") + } + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> { unimplemented!("Edges have no labels") } diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs index a641c74..b01a13b 100644 --- a/graph/src/labelled/double.rs +++ b/graph/src/labelled/double.rs @@ -319,6 +319,8 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> { Self: 'a, T: 'a; + type TupleIter<'a> = std::iter::Copied<std::slice::Iter<'a, (T, usize)>> where Self: 'a, T:'a; + fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> { if self.has_edge(source, target)? { Ok(EdgeLabelIter::new( @@ -353,6 +355,14 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> { } #[inline] + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(node.flat.iter().copied()), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())), + } + } + + #[inline] fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error> { match self.nodes.get(node_id) { Some(node) => Ok(Self::LabelIter::new(node.by_label.iter())), diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs index fb7b405..13fd8c1 100644 --- a/graph/src/labelled/mod.rs +++ b/graph/src/labelled/mod.rs @@ -17,3 +17,6 @@ pub use double::{DLGBuilder, DLGraph}; pub mod binary; pub use binary::{PLGBuilderMut, PLGraph}; + +pub mod simple; +pub use simple::{SLGBuilder, SLGraph}; diff --git a/graph/src/labelled/simple.rs b/graph/src/labelled/simple.rs new file mode 100644 index 0000000..b5388a9 --- /dev/null +++ b/graph/src/labelled/simple.rs @@ -0,0 +1,579 @@ +//! This file implements a simple labelled graph without extra +//! functionalities. +//! +//! Neither the method +//! [`find_children_with_label`][crate::LabelGraph::find_children_with_label] +//! nor the method [`labels_of`][crate::LabelGraph::labels_of] are +//! implemented efficiently. + +use super::*; + +#[derive(Debug, Clone)] +struct SLNode<T: GraphLabel> { + children: Vec<(T, usize)>, +} + +impl<T: GraphLabel> Default for SLNode<T> { + fn default() -> Self { + Self { + children: Vec::new(), + } + } +} + +impl<T: GraphLabel> SLNode<T> { + fn new(children: Vec<(T, usize)>) -> Self { + Self { children } + } +} + +/// Simple Labelled Graph. +#[derive(Debug, Clone)] +pub struct SLGraph<T: GraphLabel> { + nodes: Vec<SLNode<T>>, +} + +impl<T: GraphLabel> SLGraph<T> { + /// Return a builder. + #[inline] + pub fn builder(self) -> SLGBuilder<T> { + SLGBuilder(self) + } + + /// Return a builder from a reference. + #[inline] + pub fn builder_ref(&self) -> SLGBuilder<T> { + SLGBuilder(self.clone()) + } +} + +impl<T: GraphLabel> Default for SLGraph<T> { + #[inline] + fn default() -> Self { + let nodes = Vec::new(); + + Self { nodes } + } +} + +/// An iterator delegation for children of nodes of `SLGraph`. +#[derive(Debug, Clone)] +pub struct ChildrenIter<'a, T: GraphLabel> { + iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>, +} + +impl<'a, T: GraphLabel> ChildrenIter<'a, T> { + fn new(iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>) -> Self { + Self { iter } + } +} + +impl<'a, T: GraphLabel> Iterator for ChildrenIter<'a, T> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + self.iter.next().map(|(_, to)| to) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, T: GraphLabel> ExactSizeIterator for ChildrenIter<'a, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T: GraphLabel> Graph for SLGraph<T> { + // Not using a boxed pointer is supposed to save some allocations. + type Iter<'a> = ChildrenIter<'a, T> where T: 'a; + + #[inline] + fn is_empty(&self) -> bool { + self.nodes.is_empty() + } + + #[inline] + fn nodes_len(&self) -> usize { + self.nodes.len() + } + + #[inline] + fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(ChildrenIter::new(node.children.iter().copied())), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())), + } + } + + #[inline] + /// Return the number of "children" of a node, or an error if the + /// node is not a member of the graph. + /// + /// This counts edges with different labels as different edges. + fn degree(&self, node_id: usize) -> Result<usize, Error> { + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) + .map(|node| node.children.len()) + } + + #[inline] + fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> { + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) + .map(|node| node.children.is_empty()) + } + + fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> { + match self.nodes.get(source) { + Some(source_node) => { + if self.nodes.get(target).is_none() { + Err(Error::IndexOutOfBounds(target, self.nodes.len())) + } else { + for (_, to) in source_node.children.iter() { + if *to == target { + return Ok(true); + } + } + + Ok(false) + } + } + None => Err(Error::IndexOutOfBounds(source, self.nodes.len())), + } + } + + fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> { + let filename = format!("output/{filename}"); + + let preamble = "digraph nfa { + fontname=\"Helvetica,Arial,sans-serif\" + node [fontname=\"Helvetica,Arial,sans-serif\", ordering=out] + edge [fontname=\"Helvetica,Arial,sans-serif\"] + rankdir=LR;\n"; + + let mut post = String::new(); + + for (source, target) in self.edges() { + for label in self.edge_label(source, target).unwrap() { + post.push_str(&format!(" {source} -> {target} [label = \"{label}\"]\n")); + } + } + + post.push_str("}\n"); + + let result = format!("{preamble}{post}"); + + if std::fs::metadata(&filename).is_ok() { + std::fs::remove_file(&filename)?; + } + + let mut file = std::fs::File::options() + .write(true) + .create(true) + .open(&filename)?; + + use std::io::Write; + + file.write_all(result.as_bytes()) + } + + #[inline] + fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) { + let new_graph = builder.build(); + + self.nodes = new_graph.nodes; + } +} + +impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> { + type Iter<'a> = std::iter::Empty<usize> + where + Self:'a, + T:'a; + + type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + where + Self: 'a, + T: 'a; + + type TupleIter<'a> = std::iter::Copied<std::slice::Iter<'a, (T, usize)>> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::option::IntoIter<T> + where + Self: 'a, + T: 'a; + + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> { + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) + .map(|node| node.children.iter().copied()) + } + + fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> { + let nodes_len = self.nodes.len(); + + if let Some(source_node) = self.nodes.get(source) { + if !(0..nodes_len).contains(&target) { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + for (label, end) in source_node.children.iter() { + if *end == target { + return Ok(Some(*label).into_iter()); + } + } + + Ok(None.into_iter()) + } else { + Err(Error::IndexOutOfBounds(source, nodes_len)) + } + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &T, + ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error> { + unimplemented!("Unsupported operation") + } + + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> { + unimplemented!("Unsupported operation") + } + + #[inline] + fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error> { + let nodes_len = self.nodes.len(); + + match self.nodes.get(node_id) { + Some(node) => { + if target >= nodes_len { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + for (edge_label, end) in node.children.iter() { + if *edge_label == *label && *end == target { + return Ok(true); + } + } + + Ok(false) + } + None => Err(Error::IndexOutOfBounds(node_id, nodes_len)), + } + } +} + +impl<T: GraphLabel> LabelExtGraph<T> for SLGraph<T> { + #[inline] + fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error> { + let mut children = Vec::new(); + + for (label, to) in edges { + if !self.has_node(to) { + return Err(Error::IndexOutOfBounds(to, self.nodes.len())); + } + + children.push((label, to)); + } + + let new_node = SLNode::new(children); + let new_index = self.nodes_len(); + + self.nodes.push(new_node); + + Ok(new_index) + } +} + +// Builder for this implementation of graph + +/// A builder for simple labelled graphs. +#[derive(Debug, Clone)] +pub struct SLGBuilder<T: GraphLabel>(SLGraph<T>); + +impl<T: GraphLabel> Default for SLGBuilder<T> { + fn default() -> Self { + Self(Default::default()) + } +} + +impl<T: GraphLabel> Deref for SLGBuilder<T> { + type Target = SLGraph<T>; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl<T: GraphLabel> DerefMut for SLGBuilder<T> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl<T: GraphLabel> Builder for SLGBuilder<T> { + type Label = T; + + type Result = SLGraph<T>; + + #[inline] + fn with_capacity(size: usize) -> Self { + Self(SLGraph { + nodes: Vec::with_capacity(size), + }) + } + + #[inline] + fn add_vertex(&mut self) -> usize { + self.nodes.push(SLNode::default()); + self.nodes.len() - 1 + } + + #[inline] + fn add_vertices(&mut self, n: usize) { + self.nodes + .extend(std::iter::repeat_with(Default::default).take(n)); + } + + fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> { + let nodes_len = self.nodes.len(); + + let source_node = self + .nodes + .get_mut(source) + .ok_or(Error::IndexOutOfBounds(source, nodes_len))?; + + if !(0..nodes_len).contains(&target) { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + source_node.children.push((label, target)); + + Ok(()) + } + + fn remove_edge<F>( + &mut self, + source: usize, + target: usize, + mut predicate: F, + ) -> Result<(), Error> + where + F: FnMut(Self::Label) -> bool, + { + let nodes_len = self.nodes.len(); + + let source_node = self + .nodes + .get_mut(source) + .ok_or(Error::IndexOutOfBounds(source, nodes_len))?; + + if !(0..nodes_len).contains(&target) { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + source_node + .children + .retain(|(label, end)| !(*end == target && predicate(*label))); + + Ok(()) + } + + fn build_ref(&self) -> Self::Result { + self.0.clone() + } + + fn build(self) -> Self::Result { + self.0 + } +} + +#[cfg(test)] +mod simple_test { + use super::*; + + use std::collections::BTreeSet as Set; + + macro_rules! set { + () => { Set::<usize>::default() }; + ($($num:literal),*) => { + { + let mut set: Set<usize> = Set::default(); + $(set.insert($num);)* + set + } + }; + } + + // macro_rules! map { + // () => { Map::<usize, Set<usize>>::default() }; + // ($(($key:literal, $value:expr)),*) => { + // { + // let mut map: Map<usize, Set<usize>> = Map::default(); + // $(map.insert($key, $value);)* + // map + // } + // }; + // } + + #[test] + fn test_graph_apis() -> Result<(), Error> { + let mut graph: SLGraph<usize> = Default::default(); + + // testing empty graph + assert!(graph.is_empty()); + + // testing adding an empty node + assert_eq!(graph.extend(std::iter::empty())?, 0); + + // testing nodes_len + assert_eq!(graph.nodes_len(), 1); + + // testing extension + + assert_eq!(graph.extend([(0, 0)].iter().copied())?, 1); + assert_eq!(graph.extend([(1, 0), (1, 1)].iter().copied())?, 2); + assert_eq!(graph.extend([(3, 0), (3, 2)].iter().copied())?, 3); + assert_eq!(graph.extend([(1, 1), (1, 2)].iter().copied())?, 4); + assert_eq!(graph.extend([(2, 1), (3, 2), (2, 3)].iter().copied())?, 5); + + // testing adding a duplicated edge set + assert_eq!(graph.extend([(2, 1), (2, 3), (3, 2)].iter().copied())?, 6); + assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 7); + + let graph = graph; + + // ensuring the correct length + assert_eq!(graph.nodes_len(), 8); + + // testing children_of + assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2)); + + // testing find_children_with_label + assert!(std::panic::catch_unwind(|| { graph.find_children_with_label(5, &2) }).is_err()); + + // testing edge_label + assert_eq!(graph.edge_label(5, 2)?.collect::<Set<_>>(), set!(3)); + assert!(matches!( + graph.edge_label(8, 2), + Err(Error::IndexOutOfBounds(8, 8)) + )); + + // testing degree + assert_eq!(graph.degree(4)?, 2); + + // testing is_empty_node + assert!(graph.is_empty_node(0)?); + assert!(!graph.is_empty_node(1)?); + + // testing has_edge + assert!(graph.has_edge(3, 2)?); + assert!(!graph.has_edge(3, 1)?); + assert!(matches!( + graph.has_edge(3, 8), + Err(Error::IndexOutOfBounds(8, 8)) + )); + + // testing labels_of + assert!(std::panic::catch_unwind(|| { graph.labels_of(5) }).is_err()); + + Ok(()) + } +} + +#[cfg(test)] +mod test_slgraph_builder { + use super::*; + + #[test] + fn test_builder() -> Result<(), Box<dyn std::error::Error>> { + let mut builder = SLGBuilder::<usize>::default(); + + // Add five nodes + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + + // Link each node to its successor and link the last node with + // the first one to form a cycle. + for i in 0..5 { + builder.add_edge(i, if i < 4 { i + 1 } else { 0 }, i)?; + } + + // Remove the link from the last node to the first node. + builder.remove_edge(4, 0, |_| true)?; + + // build a graph + + let graph = builder.build(); + + println!("final graph: {graph:?}"); + + Ok(()) + } + + #[test] + fn test_errors() -> Result<(), Box<dyn std::error::Error>> { + let mut builder = SLGBuilder::default(); + + // Add five nodes + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + + // Errors in add_edge + + assert!(matches!( + builder.add_edge(0, 5, 0), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + assert!(matches!( + builder.add_edge(10, 5, 0), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + assert!(matches!( + builder.add_edge(10, 50, 0), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + // Errors in remove_edge + + assert!(matches!( + builder.remove_edge(0, 5, |_| true), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + assert!(matches!( + builder.remove_edge(10, 5, |_| true), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + assert!(matches!( + builder.remove_edge(10, 50, |_| true), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),)); + + Ok(()) + } +} diff --git a/graph/src/lib.rs b/graph/src/lib.rs index e27ace0..058d62c 100644 --- a/graph/src/lib.rs +++ b/graph/src/lib.rs @@ -276,6 +276,58 @@ pub trait RedirectGraph: Graph { ) -> Result<(), Error>; } +// TODO: Design traits for vertex-labelled, edge-labelled, and +// both-labelled graphs separately. +// +// This is needed because we need better iterators to return labels +// simultaneously with children nodes. This can then reduce the +// number of checking bounds when iterating. I think this is the +// right way of doing things, and can help with the performance as +// well. + +/// A graph whose vertices are associated with labels. +/// +/// This trait defines some convenient methods for accessing the +/// labels of vertices. +pub trait VLabelGraph<T: GraphLabel>: Graph { + /// A type that iterates through tuples of labels and targets of + /// edges. + type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a + where + Self: 'a, + T: 'a; + + /// Query the graph for a label, and return the node index if + /// this operation is supported. + /// + /// The default implementation always returns `None`. + #[inline] + fn query_label(&self, _label: T) -> Option<usize> { + None + } + + #[inline] + /// Return the label of a vertex or an error if the node is + /// invalid. + /// + /// The default implementation always returns `None` after + /// checking the validity of `node_id`. + fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> { + if self.has_node(node_id) { + Ok(None) + } else { + Err(Error::IndexOutOfBounds(node_id, self.nodes_len())) + } + } + + /// Return an iterator of tuples of vertex labels and indices of + /// targets edges out of a node. + /// + /// The name is a weird new word created to stand as a + /// simplification of the phrase "vertex label and children of". + fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error>; +} + /// A labelled graph is just a graph with labels associated to /// vertices and / or edges. /// @@ -289,9 +341,12 @@ pub trait LabelGraph<T: GraphLabel>: Graph { where Self: 'a; - // TODO: Add a type that iterates through children and labels of - // children simultaneously. This can reduce the number of bounds - // checking. + /// A type that iterates through tuples of labels and targets of + /// edges. + type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a + where + Self: 'a, + T: 'a; /// A type that iterates through labels. type LabelIter<'a>: Iterator<Item = (&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + 'a @@ -347,6 +402,10 @@ pub trait LabelGraph<T: GraphLabel>: Graph { /// The efficiency of this method matters in implementations. fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error>; + /// Return an iterator of tuples of edge labels and targets of + /// edges out of a node. + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error>; + /// Return true if and only if the node has an edge with the given /// label and target. fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error>; diff --git a/graph_macro/src/lib.rs b/graph_macro/src/lib.rs index 3b7742a..409e6db 100644 --- a/graph_macro/src/lib.rs +++ b/graph_macro/src/lib.rs @@ -137,6 +137,8 @@ macro_rules! myerror { }; } +/// Derive macro generating an implementation of the trait `Graph` +/// inheriting a field. #[proc_macro_derive(Graph, attributes(graph))] pub fn graph_derive(input: TokenStream) -> TokenStream { let mut input = input.into_iter().peekable(); diff --git a/nfa/src/default/nfa.rs b/nfa/src/default/nfa.rs index e38a1a9..42f7fd8 100644 --- a/nfa/src/default/nfa.rs +++ b/nfa/src/default/nfa.rs @@ -43,6 +43,11 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultNFA<T> { Self: 'a, T: 'a; + type TupleIter<'a> = <DLGraph<T> as LabelGraph<T>>::TupleIter<'a> + where + Self: 'a, + T: 'a; + #[inline] fn vertex_label(&self, node_id: usize) -> Result<Option<T>, GError> { if self.has_node(node_id) { @@ -67,6 +72,11 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultNFA<T> { } #[inline] + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + self.graph.tuples_of(node_id) + } + + #[inline] fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, GError> { self.graph.labels_of(node_id) } diff --git a/nfa/src/default/regex.rs b/nfa/src/default/regex.rs index 8185ca5..261b10c 100644 --- a/nfa/src/default/regex.rs +++ b/nfa/src/default/regex.rs @@ -211,6 +211,12 @@ where .take(self.len()) .collect(); + // FIXME: This seems wrong: we shall perform a depth-first + // search to find nodes without children and collect their + // results first. However this function is not actually used + // elsewhere, so it is left unfixed until it is needed in the + // future. + for index in 0..=self.len() { let algebra_result = { let results_of_children: Vec<T> = self diff --git a/semiring/Cargo.toml b/semiring/Cargo.toml index d62eea6..8c03308 100644 --- a/semiring/Cargo.toml +++ b/semiring/Cargo.toml @@ -7,8 +7,4 @@ edition = "2021" [dependencies] grammar = { path = "../grammar" } - -[dev-dependencies] -grammar = { path = "../grammar", features = ["test-helper"] } - -# TODO +forest = { path = "../forest" } |