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/src/iter/query.rs | 372 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 372 insertions(+) create mode 100644 forest/src/iter/query.rs (limited to 'forest/src/iter/query.rs') 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(); + } +} -- cgit v1.2.3-18-g5258