From 3ae0cf9898485a2ec35df7d23cd274e7dea5796d Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 8 Jan 2024 16:13:19 +0800 Subject: a commit before the forst query I think the main functionalities are already there, but the lack of querying capabilities makes this not very useful at the moment. This commit is right before an attempt to add this missing piece. --- forest/Cargo.toml | 1 + forest/src/bytes.rs | 280 +++++++++++++++++++++++++++++++++++ forest/src/iter/mod.rs | 91 ++++++++++++ forest/src/iter/query.rs | 372 +++++++++++++++++++++++++++++++++++++++++++++++ forest/src/lib.rs | 2 + 5 files changed, 746 insertions(+) create mode 100644 forest/src/iter/mod.rs create mode 100644 forest/src/iter/query.rs (limited to 'forest') 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>(forest: &F) -> Vec { 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, + /// 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 for BytesError { + fn from(value: TryFromSliceError) -> Self { + Self::WrongSliceConversion(value) + } +} + +impl std::error::Error for BytesError {} + +impl TryFrom> for BytesForest { + type Error = BytesError; + + fn try_from(bytes: Vec) -> Result { + 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 { + 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) { + (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, 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 { + 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 { + Ok(self.degree(node_id)? == 0) + } + + fn has_edge(&self, source: usize, target: usize) -> Result { + 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) { + 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 { + 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; + + /// 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(&mut self, forest: &F, root: usize) -> Result + where + F: LabelGraph>, + { + // 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( + &self, + forest: &F, + node: usize, + packs: &mut Vec<(usize, usize)>, + ) -> Result, QRError> + where + F: LabelGraph::Obj>>, + { + let mut dfs_stack: Vec = 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::>() + .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 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 { + graph: SLGraph, + vertex_labels: Vec, + root: Option, +} + +impl Query { + /// Construct a new query from raw fields. + pub fn new(graph: SLGraph, vertex_labels: Vec, root: Option) -> 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 { + 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 { + self.vertex_labels + .get(node) + .copied() + .ok_or(GError::IndexOutOfBounds(node, self.vertex_labels.len())) + } +} + +impl Default for Query { + fn default() -> Self { + let graph = Default::default(); + let vertex_labels = Vec::new(); + let root = None; + + Self { + graph, + vertex_labels, + root, + } + } +} + +// delegation of labelgraph + +impl LabelGraph for Query { + type Iter<'a> = as LabelGraph>::Iter<'a> + where + Self: 'a; + + type TupleIter<'a> = as LabelGraph>::TupleIter<'a> + where + Self: 'a; + + type LabelIter<'a> = as LabelGraph>::LabelIter<'a> + where + Self: 'a; + + type EdgeLabelIter<'a> = as LabelGraph>::EdgeLabelIter<'a> + where + Self: 'a; + + #[inline] + fn edge_label(&self, source: usize, target: usize) -> Result, GError> { + self.graph.edge_label(source, target) + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &SkipState, + ) -> Result<>::Iter<'_>, GError> { + unimplemented!("Unsupported operation") + } + + fn labels_of(&self, _node_id: usize) -> Result, GError> { + unimplemented!("Unsupported operation") + } + + #[inline] + fn tuples_of(&self, node_id: usize) -> Result, GError> { + self.graph.tuples_of(node_id) + } + + #[inline] + fn has_edge_label( + &self, + node_id: usize, + label: &SkipState, + target: usize, + ) -> Result { + 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 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 { + /// The currently visited node. + current: Option, + /// The queries dependency graph. + query: Query, + /// The packed nodes that can be used to change to another branch + /// if needed. + packs: Vec, +} + +impl Default for QRun { + fn default() -> Self { + let current = Default::default(); + let query = Default::default(); + let packs = Default::default(); + + Self { + current, + query, + packs, + } + } +} + +impl ForestIter for QRun { + #[inline] + fn current(&self) -> Option { + self.current + } + + type ForestLabel = ::Obj; + + type Item<'a> = Option<&'a [usize]> + where + Self: 'a; + + type Error = QRError; + + #[allow(unused)] + #[allow(clippy::collapsible_if)] + fn next(&mut self, forest: &F, root: usize) -> Result + where + F: LabelGraph>, + { + let query_root = if let Some(r) = self.query.root() { + r + } else { + return Ok(State::Finish); + }; + + #[derive(Debug, Clone, Copy)] + enum Item { + Seen(T), + Unseen(T), + } + + use Item::*; + + impl Item { + 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> = Vec::with_capacity(query_len); + + stack.push(Unseen((SkipState::Any, root, query_root))); + + let mut parents_stack: Vec = 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: ParentsGraph + LabelGraph> { pub mod bytes; pub use bytes::forest_to_bytes; + +pub mod iter; -- cgit v1.2.3-18-g5258