manifoldb_query/exec/
graph_accessor.rs

1//! Graph storage accessor trait for query execution.
2//!
3//! This module provides the [`GraphAccessor`] trait that abstracts
4//! graph traversal operations for use in query execution. The trait
5//! is object-safe and can be stored in the execution context.
6
7use manifoldb_core::{EdgeId, EdgeType, EntityId};
8use manifoldb_graph::traversal::{Direction, PathPattern, PathStep, PatternMatch, StepFilter};
9
10/// Result of a neighbor expansion.
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct NeighborResult {
13    /// The neighbor entity ID.
14    pub node: EntityId,
15    /// The edge ID connecting to this neighbor.
16    pub edge_id: EdgeId,
17    /// The direction the edge was traversed.
18    pub direction: Direction,
19}
20
21impl NeighborResult {
22    /// Create a new neighbor result.
23    pub const fn new(node: EntityId, edge_id: EdgeId, direction: Direction) -> Self {
24        Self { node, edge_id, direction }
25    }
26}
27
28/// Result of a multi-hop expansion.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct TraversalResult {
31    /// The reached entity ID.
32    pub node: EntityId,
33    /// The edge ID used to reach this node (from the previous node).
34    pub edge_id: Option<EdgeId>,
35    /// The depth at which this node was discovered.
36    pub depth: usize,
37}
38
39impl TraversalResult {
40    /// Create a new traversal result.
41    pub const fn new(node: EntityId, edge_id: Option<EdgeId>, depth: usize) -> Self {
42        Self { node, edge_id, depth }
43    }
44}
45
46/// Result of a path pattern match.
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct PathMatchResult {
49    /// The nodes traversed, in order.
50    pub nodes: Vec<EntityId>,
51    /// The edges used for each step.
52    /// Each inner vector contains edges for one step (may have multiple for variable-length steps).
53    pub step_edges: Vec<Vec<EdgeId>>,
54}
55
56impl PathMatchResult {
57    /// Create a new path match result.
58    pub fn new(nodes: Vec<EntityId>, step_edges: Vec<Vec<EdgeId>>) -> Self {
59        Self { nodes, step_edges }
60    }
61
62    /// Get the starting node.
63    pub fn source(&self) -> Option<EntityId> {
64        self.nodes.first().copied()
65    }
66
67    /// Get the ending node.
68    pub fn target(&self) -> Option<EntityId> {
69        self.nodes.last().copied()
70    }
71
72    /// Get all edges as a flat list.
73    pub fn all_edges(&self) -> Vec<EdgeId> {
74        self.step_edges.iter().flatten().copied().collect()
75    }
76
77    /// Get the total path length (number of edges).
78    pub fn length(&self) -> usize {
79        self.step_edges.iter().map(std::vec::Vec::len).sum()
80    }
81}
82
83impl From<PatternMatch> for PathMatchResult {
84    fn from(pm: PatternMatch) -> Self {
85        Self { nodes: pm.nodes, step_edges: pm.step_edges }
86    }
87}
88
89/// Configuration for path finding.
90#[derive(Debug, Clone)]
91pub struct PathFindConfig {
92    /// Path steps to match.
93    pub steps: Vec<PathStepConfig>,
94    /// Maximum number of results to return (None for unlimited).
95    pub limit: Option<usize>,
96    /// Whether to allow cycles in the path.
97    pub allow_cycles: bool,
98}
99
100/// Configuration for a single step in a path pattern.
101#[derive(Debug, Clone)]
102pub struct PathStepConfig {
103    /// Direction to traverse.
104    pub direction: Direction,
105    /// Edge type filters (empty means any).
106    pub edge_types: Vec<EdgeType>,
107    /// Minimum number of hops.
108    pub min_hops: usize,
109    /// Maximum number of hops (None for unlimited).
110    pub max_hops: Option<usize>,
111}
112
113impl PathStepConfig {
114    /// Convert to a `PathStep` for the traversal module.
115    pub fn to_path_step(&self) -> PathStep {
116        let filter = if self.edge_types.is_empty() {
117            StepFilter::Any
118        } else if self.edge_types.len() == 1 {
119            StepFilter::EdgeType(self.edge_types[0].clone())
120        } else {
121            StepFilter::EdgeTypes(self.edge_types.clone())
122        };
123
124        PathStep::new(self.direction, filter).with_hops(self.min_hops, self.max_hops)
125    }
126}
127
128/// Graph accessor error type.
129#[derive(Debug, Clone, thiserror::Error)]
130pub enum GraphAccessError {
131    /// No graph storage is available.
132    #[error("no graph storage available")]
133    NoStorage,
134    /// An internal error occurred.
135    #[error("graph error: {0}")]
136    Internal(String),
137}
138
139/// Result type for graph accessor operations.
140pub type GraphAccessResult<T> = Result<T, GraphAccessError>;
141
142/// A trait for accessing graph storage during query execution.
143///
144/// This trait is object-safe and provides the graph operations
145/// needed by the query executor. It abstracts over the actual
146/// storage transaction type.
147pub trait GraphAccessor: Send + Sync {
148    /// Get neighbors of a node in the specified direction.
149    ///
150    /// Returns immediate neighbors (single hop).
151    fn neighbors(
152        &self,
153        node: EntityId,
154        direction: Direction,
155    ) -> GraphAccessResult<Vec<NeighborResult>>;
156
157    /// Get neighbors filtered by edge type.
158    fn neighbors_by_type(
159        &self,
160        node: EntityId,
161        direction: Direction,
162        edge_type: &EdgeType,
163    ) -> GraphAccessResult<Vec<NeighborResult>>;
164
165    /// Get neighbors filtered by multiple edge types.
166    fn neighbors_by_types(
167        &self,
168        node: EntityId,
169        direction: Direction,
170        edge_types: &[EdgeType],
171    ) -> GraphAccessResult<Vec<NeighborResult>>;
172
173    /// Perform multi-hop expansion from a node.
174    ///
175    /// Returns all nodes reachable within the depth range.
176    fn expand_all(
177        &self,
178        node: EntityId,
179        direction: Direction,
180        min_depth: usize,
181        max_depth: Option<usize>,
182        edge_types: Option<&[EdgeType]>,
183    ) -> GraphAccessResult<Vec<TraversalResult>>;
184
185    /// Find paths matching a pattern from a starting node.
186    ///
187    /// Executes multi-hop path patterns with support for variable-length steps.
188    fn find_paths(
189        &self,
190        start: EntityId,
191        config: &PathFindConfig,
192    ) -> GraphAccessResult<Vec<PathMatchResult>>;
193}
194
195/// A null implementation of `GraphAccessor` that returns no results.
196///
197/// Used when no graph storage is configured.
198#[derive(Debug, Clone, Copy, Default)]
199pub struct NullGraphAccessor;
200
201impl GraphAccessor for NullGraphAccessor {
202    fn neighbors(
203        &self,
204        _node: EntityId,
205        _direction: Direction,
206    ) -> GraphAccessResult<Vec<NeighborResult>> {
207        Err(GraphAccessError::NoStorage)
208    }
209
210    fn neighbors_by_type(
211        &self,
212        _node: EntityId,
213        _direction: Direction,
214        _edge_type: &EdgeType,
215    ) -> GraphAccessResult<Vec<NeighborResult>> {
216        Err(GraphAccessError::NoStorage)
217    }
218
219    fn neighbors_by_types(
220        &self,
221        _node: EntityId,
222        _direction: Direction,
223        _edge_types: &[EdgeType],
224    ) -> GraphAccessResult<Vec<NeighborResult>> {
225        Err(GraphAccessError::NoStorage)
226    }
227
228    fn expand_all(
229        &self,
230        _node: EntityId,
231        _direction: Direction,
232        _min_depth: usize,
233        _max_depth: Option<usize>,
234        _edge_types: Option<&[EdgeType]>,
235    ) -> GraphAccessResult<Vec<TraversalResult>> {
236        Err(GraphAccessError::NoStorage)
237    }
238
239    fn find_paths(
240        &self,
241        _start: EntityId,
242        _config: &PathFindConfig,
243    ) -> GraphAccessResult<Vec<PathMatchResult>> {
244        Err(GraphAccessError::NoStorage)
245    }
246}
247
248/// A concrete implementation of `GraphAccessor` backed by a storage transaction.
249///
250/// This wraps a transaction reference and delegates to the actual graph traversal code.
251pub struct TransactionGraphAccessor<T> {
252    tx: T,
253}
254
255impl<T> TransactionGraphAccessor<T> {
256    /// Create a new accessor wrapping a transaction.
257    pub fn new(tx: T) -> Self {
258        Self { tx }
259    }
260}
261
262impl<T> GraphAccessor for TransactionGraphAccessor<T>
263where
264    T: manifoldb_storage::Transaction + Send + Sync,
265{
266    fn neighbors(
267        &self,
268        node: EntityId,
269        direction: Direction,
270    ) -> GraphAccessResult<Vec<NeighborResult>> {
271        manifoldb_graph::traversal::Expand::neighbors(&self.tx, node, direction)
272            .map(|results| {
273                results
274                    .into_iter()
275                    .map(|r| NeighborResult::new(r.node, r.edge_id, r.direction))
276                    .collect()
277            })
278            .map_err(|e| GraphAccessError::Internal(e.to_string()))
279    }
280
281    fn neighbors_by_type(
282        &self,
283        node: EntityId,
284        direction: Direction,
285        edge_type: &EdgeType,
286    ) -> GraphAccessResult<Vec<NeighborResult>> {
287        manifoldb_graph::traversal::Expand::neighbors_by_type(&self.tx, node, direction, edge_type)
288            .map(|results| {
289                results
290                    .into_iter()
291                    .map(|r| NeighborResult::new(r.node, r.edge_id, r.direction))
292                    .collect()
293            })
294            .map_err(|e| GraphAccessError::Internal(e.to_string()))
295    }
296
297    fn neighbors_by_types(
298        &self,
299        node: EntityId,
300        direction: Direction,
301        edge_types: &[EdgeType],
302    ) -> GraphAccessResult<Vec<NeighborResult>> {
303        // For multiple edge types, we collect results from each type
304        let mut results = Vec::new();
305        for edge_type in edge_types {
306            let neighbors = manifoldb_graph::traversal::Expand::neighbors_by_type(
307                &self.tx, node, direction, edge_type,
308            )
309            .map_err(|e| GraphAccessError::Internal(e.to_string()))?;
310
311            results.extend(
312                neighbors.into_iter().map(|r| NeighborResult::new(r.node, r.edge_id, r.direction)),
313            );
314        }
315        Ok(results)
316    }
317
318    fn expand_all(
319        &self,
320        node: EntityId,
321        direction: Direction,
322        min_depth: usize,
323        max_depth: Option<usize>,
324        edge_types: Option<&[EdgeType]>,
325    ) -> GraphAccessResult<Vec<TraversalResult>> {
326        let mut expander =
327            manifoldb_graph::traversal::ExpandAll::new(node, direction).with_min_depth(min_depth);
328
329        if let Some(max) = max_depth {
330            expander = expander.with_max_depth(max);
331        }
332
333        // Add edge type filters
334        if let Some(types) = edge_types {
335            for edge_type in types {
336                expander = expander.with_edge_type(edge_type.clone());
337            }
338        }
339
340        expander
341            .execute(&self.tx)
342            .map(|results| {
343                results.into_iter().map(|r| TraversalResult::new(r.id, None, r.depth)).collect()
344            })
345            .map_err(|e| GraphAccessError::Internal(e.to_string()))
346    }
347
348    fn find_paths(
349        &self,
350        start: EntityId,
351        config: &PathFindConfig,
352    ) -> GraphAccessResult<Vec<PathMatchResult>> {
353        // Build the path pattern from the configuration
354        let mut pattern = PathPattern::new();
355
356        for step in &config.steps {
357            pattern = pattern.add_step(step.to_path_step());
358        }
359
360        // Apply limit if configured
361        if let Some(limit) = config.limit {
362            pattern = pattern.with_limit(limit);
363        }
364
365        // Apply cycle policy
366        if config.allow_cycles {
367            pattern = pattern.allow_cycles();
368        }
369
370        // Execute the pattern match
371        pattern
372            .find_from(&self.tx, start)
373            .map(|matches| matches.into_iter().map(PathMatchResult::from).collect())
374            .map_err(|e| GraphAccessError::Internal(e.to_string()))
375    }
376}
377
378#[cfg(test)]
379mod tests {
380    use super::*;
381
382    #[test]
383    fn null_accessor_returns_no_storage() {
384        let accessor = NullGraphAccessor;
385
386        let result = accessor.neighbors(EntityId::new(1), Direction::Outgoing);
387        assert!(matches!(result, Err(GraphAccessError::NoStorage)));
388    }
389
390    #[test]
391    fn neighbor_result_creation() {
392        let result = NeighborResult::new(EntityId::new(1), EdgeId::new(10), Direction::Outgoing);
393        assert_eq!(result.node, EntityId::new(1));
394        assert_eq!(result.edge_id, EdgeId::new(10));
395        assert_eq!(result.direction, Direction::Outgoing);
396    }
397
398    #[test]
399    fn traversal_result_creation() {
400        let result = TraversalResult::new(EntityId::new(2), Some(EdgeId::new(20)), 3);
401        assert_eq!(result.node, EntityId::new(2));
402        assert_eq!(result.edge_id, Some(EdgeId::new(20)));
403        assert_eq!(result.depth, 3);
404    }
405
406    #[test]
407    fn path_match_result_creation() {
408        let result = PathMatchResult::new(
409            vec![EntityId::new(1), EntityId::new(2), EntityId::new(3)],
410            vec![vec![EdgeId::new(10)], vec![EdgeId::new(20)]],
411        );
412        assert_eq!(result.source(), Some(EntityId::new(1)));
413        assert_eq!(result.target(), Some(EntityId::new(3)));
414        assert_eq!(result.length(), 2);
415        assert_eq!(result.all_edges(), vec![EdgeId::new(10), EdgeId::new(20)]);
416    }
417
418    #[test]
419    fn path_step_config_to_path_step() {
420        let config = PathStepConfig {
421            direction: Direction::Outgoing,
422            edge_types: vec![EdgeType::new("FRIEND")],
423            min_hops: 1,
424            max_hops: Some(3),
425        };
426        let step = config.to_path_step();
427        assert_eq!(step.direction, Direction::Outgoing);
428        assert_eq!(step.min_hops, 1);
429        assert_eq!(step.max_hops, Some(3));
430    }
431
432    #[test]
433    fn null_accessor_find_paths_returns_no_storage() {
434        let accessor = NullGraphAccessor;
435        let config = PathFindConfig { steps: vec![], limit: None, allow_cycles: false };
436        let result = accessor.find_paths(EntityId::new(1), &config);
437        assert!(matches!(result, Err(GraphAccessError::NoStorage)));
438    }
439}
manifoldb_query/exec/graph_accessor.rs

manifoldb_query/exec/
graph_accessor.rs
