aboutsummaryrefslogtreecommitdiff
path: root/forest/src/iter
diff options
context:
space:
mode:
Diffstat (limited to 'forest/src/iter')
-rw-r--r--forest/src/iter/mod.rs91
-rw-r--r--forest/src/iter/query.rs372
2 files changed, 463 insertions, 0 deletions
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();
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2026-10-21 15:25:12 +0000