diff options
Diffstat (limited to 'forest/src/iter/query.rs')
| -rw-r--r-- | forest/src/iter/query.rs | 372 |
1 files changed, 0 insertions, 372 deletions
diff --git a/forest/src/iter/query.rs b/forest/src/iter/query.rs deleted file mode 100644 index aff8eef..0000000 --- a/forest/src/iter/query.rs +++ /dev/null @@ -1,372 +0,0 @@ -//! 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(); - } -} |