new startHEADmaster

Now I tested and discussed with claude, and had a working version of
this project.  The rest is to port the claude version to my own
writings.  So this serves as the starting point before that attempt.

In the new attempt the design is better, and a number of bugs were
found and supposedly fixed, so let us see how this goes at the end.

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)
+            }
+        }
+    }
+}