From fba9a90cfc6aca2a26cce72f55fb261789139781 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 16 Oct 2026 14:01:01 +0800 Subject: new start 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. --- forest/src/iter/query/matching.rs | 338 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 338 insertions(+) create mode 100644 forest/src/iter/query/matching.rs (limited to 'forest/src/iter/query/matching.rs') 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 { + parent: usize, + // edge_index: usize, + parent_label: T, + edge_label: EdgeType, +} + +impl EVLabelParent { + /// 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: VLabelGraph + ELabelGraph { + /// An iterator delegation for parents and vertex and edge labels. + type ParentIter<'a>: Iterator> + 'a + where + Self: 'a, + T: 'a; + + /// Return an iterator that goes through the parents and edge + /// labels. + fn parents(&self, node: usize) -> Result, GError>; +} + +/// A trait for target graphs. +pub trait Target: VLabelGraph { + /// 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::>().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 { + graph: SLGBuilder, + parents_graph: SLGBuilder, +} + +impl Default for SimplePattern { + fn default() -> Self { + let graph = SLGBuilder::default(); + let parents_graph = SLGBuilder::default(); + Self { + graph, + parents_graph, + } + } +} + +impl SimplePattern { + /// Return a new pattern from an underlying graph builder. + pub fn new(graph: SLGBuilder) -> Result { + let nodes_len = graph.nodes_len(); + + let mut parents_graph: SLGBuilder = 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 VLabelGraph for SimplePattern { + type TupleIter<'a> = as VLabelGraph>::TupleIter<'a> + where + Self: 'a, + T: 'a; + + fn verlabren_of(&self, node_id: usize) -> Result, GError> { + self.graph.verlabren_of(node_id) + } +} + +impl LabelGraph for SimplePattern { + type Iter<'a> = std::iter::Empty + where + Self: 'a; + + type TupleIter<'a> = as LabelGraph>::TupleIter<'a> + where + Self: 'a, + T: 'a; + + type LabelIter<'a> = std::iter::Empty<(&'a EdgeType, std::iter::Empty)> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::option::IntoIter + where + Self: 'a, + T: 'a; + + fn edge_label(&self, source: usize, target: usize) -> Result, GError> { + LabelGraph::edge_label(&self.graph, source, target) + } + + fn find_children_with_label( + &self, + node_id: usize, + label: &EdgeType, + ) -> Result<>::Iter<'_>, GError> { + self.graph.find_children_with_label(node_id, label) + } + + fn labels_of(&self, _node_id: usize) -> Result, GError> { + unimplemented!("Unsupported operation!") + } + + fn tuples_of(&self, node_id: usize) -> Result, GError> { + self.graph.tuples_of(node_id) + } + + fn has_edge_label( + &self, + node_id: usize, + label: &EdgeType, + target: usize, + ) -> Result { + 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: as VLabelGraph>::TupleIter<'a>, + edge_iter: as ELabelGraph>::TupleIter<'a>, +} + +impl<'a, T> PatternParents<'a, T> +where + T: GraphLabel + 'a, +{ + /// Construct a new iterator. + pub fn new( + vertex_iter: as VLabelGraph>::TupleIter<'a>, + edge_iter: as ELabelGraph>::TupleIter<'a>, + ) -> Self { + Self { + vertex_iter, + edge_iter, + } + } +} + +impl<'a, T: 'a + GraphLabel> Iterator for PatternParents<'a, T> { + type Item = EVLabelParent; + + fn next(&mut self) -> Option { + 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) { + 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 Pattern for SimplePattern { + type ParentIter<'a> = PatternParents<'a, T> where T:'a; + + fn parents(&self, node: usize) -> Result, 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 Target for SimplePattern { + fn filter_label(&self, label: T) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::>() + .into_boxed_slice() + } +} + +impl Target for PLGraph { + fn filter_label(&self, label: T) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::>() + .into_boxed_slice() + } +} + +impl Target> for BytesForest { + fn filter_label(&self, label: ForestLabel) -> Box<[usize]> { + (0..self.nodes_len()) + .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label))) + .collect::>() + .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(&self, g: &G, from: usize, to: usize) -> Result { + 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) + } + } + } +} -- cgit v1.2.3-18-g5258