1 files changed, 338 insertions, 0 deletions
diff --git a/forest/src/iter/query/matching.rs b/forest/src/iter/query/matching.rs
new file mode 100644
index 0000000..7ff47bb
--- /dev/null
+++ b/forest/src/iter/query/matching.rs
@@ -0,0 +1,338 @@
+//! This file defines some traits and basic implementations for
+//! matching pattern vertices against target vertices.
+
+use crate::{bytes::BytesForest, ForestLabel};
+
+#[allow(unused_imports)]
+use graph::{
+    error::Error as GError, ELabelGraph, Graph, GraphLabel, LabelGraph, PLGraph, SLGBuilder,
+    SLGraph, VLabelGraph,
+};
+
+use graph_macro::Graph;
+
+use grammar::GrammarLabel;
+
+/// An aggregate struct that holds information about a parent as well
+/// as its vertex label and the corresponding edge label.
+#[derive(Debug, Clone, Copy)]
+pub struct EVLabelParent<T: GraphLabel> {
+    parent: usize,
+    // edge_index: usize,
+    parent_label: T,
+    edge_label: EdgeType,
+}
+
+impl<T: GraphLabel> EVLabelParent<T> {
+    /// Construct a new instance.
+    pub fn new(parent: usize, parent_label: T, edge_label: EdgeType) -> Self {
+        Self {
+            parent,
+            parent_label,
+            edge_label,
+        }
+    }
+
+    /// Retrieve the `parent` field.
+    pub fn parent(&self) -> usize {
+        self.parent
+    }
+
+    // /// Retrieve the `edge_index` field.
+    // pub fn edge_index(&self) -> usize {
+    //     self.edge_index
+    // }
+
+    /// Retrieve the `parent_label` field.
+    pub fn parent_label(&self) -> T {
+        self.parent_label
+    }
+
+    /// Retrieve the `edge_label` field.
+    pub fn edge_label(&self) -> EdgeType {
+        self.edge_label
+    }
+}
+
+/// A trait for pattern graphs.
+pub trait Pattern<T: GraphLabel>: VLabelGraph<T> + ELabelGraph<EdgeType> {
+    /// An iterator delegation for parents and vertex and edge labels.
+    type ParentIter<'a>: Iterator<Item = EVLabelParent<T>> + 'a
+    where
+        Self: 'a,
+        T: 'a;
+
+    /// Return an iterator that goes through the parents and edge
+    /// labels.
+    fn parents(&self, node: usize) -> Result<Self::ParentIter<'_>, GError>;
+}
+
+/// A trait for target graphs.
+pub trait Target<T: GraphLabel>: VLabelGraph<T> {
+    /// Return an array of node indices whose labels match the given
+    /// label.
+    fn filter_label(&self, label: T) -> Box<[usize]> {
+        let _label = label;
+
+        (0..self.nodes_len()).collect::<Vec<_>>().into_boxed_slice()
+    }
+}
+
+/// A custom pattern type with a fixed edge label and a generic vertex
+/// label.
+///
+/// This type contains two graphs, with the extra one containing
+/// parentship information.
+#[derive(Debug, Clone, Graph)]
+pub struct SimplePattern<T: GraphLabel> {
+    graph: SLGBuilder<T, EdgeType>,
+    parents_graph: SLGBuilder<T, EdgeType>,
+}
+
+impl<T: GraphLabel> Default for SimplePattern<T> {
+    fn default() -> Self {
+        let graph = SLGBuilder::default();
+        let parents_graph = SLGBuilder::default();
+        Self {
+            graph,
+            parents_graph,
+        }
+    }
+}
+
+impl<T: GraphLabel> SimplePattern<T> {
+    /// Return a new pattern from an underlying graph builder.
+    pub fn new(graph: SLGBuilder<T, EdgeType>) -> Result<Self, GError> {
+        let nodes_len = graph.nodes_len();
+
+        let mut parents_graph: SLGBuilder<T, EdgeType> = SLGBuilder::with_capacity(nodes_len);
+
+        for node in 0..nodes_len {
+            // Nodes must have labels.
+            let label = VLabelGraph::vertex_label(&graph, node)?.unwrap();
+
+            parents_graph.add_vertex(label);
+        }
+
+        for node in 0..nodes_len {
+            for (label, child) in ELabelGraph::edlabren_of(&graph, node)? {
+                parents_graph.add_edge(node, child, label)?;
+            }
+        }
+
+        Ok(Self {
+            graph,
+            parents_graph,
+        })
+    }
+}
+
+impl<T: GraphLabel> VLabelGraph<T> for SimplePattern<T> {
+    type TupleIter<'a> = <SLGBuilder::<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>
+    where
+        Self: 'a,
+        T: 'a;
+
+    fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
+        self.graph.verlabren_of(node_id)
+    }
+}
+
+impl<T: GraphLabel> LabelGraph<EdgeType> for SimplePattern<T> {
+    type Iter<'a> = std::iter::Empty<usize>
+    where
+        Self: 'a;
+
+    type TupleIter<'a> = <SLGBuilder::<T, EdgeType> as LabelGraph<EdgeType>>::TupleIter<'a>
+    where
+        Self: 'a,
+        T: 'a;
+
+    type LabelIter<'a>  = std::iter::Empty<(&'a EdgeType, std::iter::Empty<usize>)>
+    where
+        Self: 'a,
+        T: 'a;
+
+    type EdgeLabelIter<'a> = std::option::IntoIter<EdgeType>
+    where
+        Self: 'a,
+        T: 'a;
+
+    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> {
+        LabelGraph::edge_label(&self.graph, source, target)
+    }
+
+    fn find_children_with_label(
+        &self,
+        node_id: usize,
+        label: &EdgeType,
+    ) -> Result<<Self as LabelGraph<EdgeType>>::Iter<'_>, GError> {
+        self.graph.find_children_with_label(node_id, label)
+    }
+
+    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
+        unimplemented!("Unsupported operation!")
+    }
+
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
+        self.graph.tuples_of(node_id)
+    }
+
+    fn has_edge_label(
+        &self,
+        node_id: usize,
+        label: &EdgeType,
+        target: usize,
+    ) -> Result<bool, GError> {
+        self.graph.has_edge_label(node_id, label, target)
+    }
+}
+
+/// Iterator delegator for parents.
+#[derive(Debug, Clone)]
+pub struct PatternParents<'a, T>
+where
+    T: GraphLabel + 'a,
+{
+    vertex_iter: <SLGBuilder<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>,
+    edge_iter: <SLGBuilder<T, EdgeType> as ELabelGraph<EdgeType>>::TupleIter<'a>,
+}
+
+impl<'a, T> PatternParents<'a, T>
+where
+    T: GraphLabel + 'a,
+{
+    /// Construct a new iterator.
+    pub fn new(
+        vertex_iter: <SLGBuilder<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>,
+        edge_iter: <SLGBuilder<T, EdgeType> as ELabelGraph<EdgeType>>::TupleIter<'a>,
+    ) -> Self {
+        Self {
+            vertex_iter,
+            edge_iter,
+        }
+    }
+}
+
+impl<'a, T: 'a + GraphLabel> Iterator for PatternParents<'a, T> {
+    type Item = EVLabelParent<T>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.vertex_iter.next().and_then(|(vlabel, target)| {
+            self.edge_iter
+                .next()
+                .map(|(elabel, _)| EVLabelParent::new(target, vlabel, elabel))
+        })
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.vertex_iter.size_hint()
+    }
+}
+
+impl<'a, T: 'a + GraphLabel> ExactSizeIterator for PatternParents<'a, T> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.vertex_iter.len()
+    }
+}
+
+impl<T: GraphLabel> Pattern<T> for SimplePattern<T> {
+    type ParentIter<'a> = PatternParents<'a, T> where T:'a;
+
+    fn parents(&self, node: usize) -> Result<Self::ParentIter<'_>, GError> {
+        let vertex_iter = self.parents_graph.verlabren_of(node)?;
+        let edge_iter = self.parents_graph.edlabren_of(node)?;
+
+        Ok(PatternParents::new(vertex_iter, edge_iter))
+    }
+}
+
+// Implement Target for three types.  Another type "DefaultForest"
+// should implement this trait on its own when the need arises.
+//
+// Note that SimplePattern also implements the Target trait.
+
+impl<T: GraphLabel> Target<T> for SimplePattern<T> {
+    fn filter_label(&self, label: T) -> Box<[usize]> {
+        (0..self.nodes_len())
+            .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label)))
+            .collect::<Vec<_>>()
+            .into_boxed_slice()
+    }
+}
+
+impl<T: GraphLabel> Target<T> for PLGraph<T> {
+    fn filter_label(&self, label: T) -> Box<[usize]> {
+        (0..self.nodes_len())
+            .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label)))
+            .collect::<Vec<_>>()
+            .into_boxed_slice()
+    }
+}
+
+impl Target<ForestLabel<GrammarLabel>> for BytesForest {
+    fn filter_label(&self, label: ForestLabel<GrammarLabel>) -> Box<[usize]> {
+        (0..self.nodes_len())
+            .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label)))
+            .collect::<Vec<_>>()
+            .into_boxed_slice()
+    }
+}
+
+// Edge-filtering types
+
+/// The type of edges that this edge can match against.
+///
+/// For the time being, we can only match either a direct child
+/// (i.e. no extra condition) or a sibling of another node.
+///
+/// In the future, we shall be able to use supplemental graphs to
+/// match edges.
+///
+/// This can be used as [`Graphlabel`][graph::GraphLabel].
+#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Hash, Ord, PartialOrd)]
+pub enum EdgeType {
+    /// Matches a direct child.
+    #[default]
+    Direct,
+    /// Match a sibling of another node.
+    Sibling(usize),
+}
+
+impl std::fmt::Display for EdgeType {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            EdgeType::Direct => write!(f, "direct edge"),
+            EdgeType::Sibling(node) => write!(f, "sibling of {node}"),
+        }
+    }
+}
+
+impl EdgeType {
+    /// Return a Sibling-type edge.
+    pub fn sibling(node: usize) -> Self {
+        Self::Sibling(node)
+    }
+
+    /// Return whether this edge matches.
+    pub fn matches<G: Graph>(&self, g: &G, from: usize, to: usize) -> Result<bool, GError> {
+        match self {
+            EdgeType::Direct => g.has_edge(from, to),
+            EdgeType::Sibling(sibling) => {
+                let mut iter = g.children_of(from)?;
+
+                while let Some(child) = iter.next() {
+                    if child == *sibling {
+                        return Ok(iter.next() == Some(to));
+                    }
+                }
+
+                // sibling not found
+
+                Ok(false)
+            }
+        }
+    }
+}