diff options
Diffstat (limited to 'forest')
| -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 |
5 files changed, 746 insertions, 0 deletions
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; |