oxgraph_postgres/traverse/
mod.rs

1//! Zero-copy query traversal (session, profile-dispatched BFS kernel).
2#![expect(
3    clippy::redundant_pub_crate,
4    reason = "kernel entrypoints are crate-internal but live in a private parent module"
5)]
6
7mod kernel;
8mod profile;
9mod scratch;
10mod session;
11
12use core::num::{NonZeroU32, NonZeroUsize};
13
14use kernel::{KernelOutcome, run_bfs_multi};
15use profile::TraverseMode;
16#[expect(
17    clippy::redundant_pub_crate,
18    reason = "re-exported to engine and builder"
19)]
20pub(crate) use scratch::TraverseScratch;
21use session::TraverseSession;
22
23use crate::{config::Config, error::PostgresGraphError};
24
25/// Traversal direction matching pgGraph `direction` semantics.
26#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
27pub enum TraversalDirection {
28    /// Follow CSR outgoing adjacency.
29    #[default]
30    Out,
31    /// Follow inbound CSC adjacency.
32    In,
33}
34
35/// Limits for a single traverse query (result cap and optional hop bound).
36///
37/// ## Semantics
38///
39/// - `result_limit`: maximum nodes returned or counted; each seed counts toward the cap.
40/// - `max_depth`: when `Some(d)`, discovers all nodes within `d` hops of a seed (boundary nodes are
41///   counted but not enqueued past the depth cap). When `None`, expansion is unbounded by depth
42///   (still capped by `result_limit`).
43#[derive(Clone, Copy, Debug, PartialEq, Eq)]
44pub struct TraverseLimits {
45    /// Maximum nodes returned (each seed counts toward the cap).
46    pub result_limit: NonZeroUsize,
47    /// `None` = unlimited hops; `Some(d)` discovers nodes within `d` hops of a seed.
48    pub max_depth: Option<NonZeroU32>,
49}
50
51impl TraverseLimits {
52    /// Creates limits with only a result cap.
53    ///
54    /// # Performance
55    ///
56    /// This method is `O(1)`.
57    #[must_use]
58    pub const fn bounded(result_limit: NonZeroUsize) -> Self {
59        Self {
60            result_limit,
61            max_depth: None,
62        }
63    }
64
65    /// Applies configured traverse cap from `config`.
66    ///
67    /// # Errors
68    ///
69    /// Returns [`PostgresGraphError::Query`] when the capped limit is zero.
70    ///
71    /// # Performance
72    ///
73    /// This method is `O(1)`.
74    pub fn capped_by(self, config: &Config) -> Result<Self, PostgresGraphError> {
75        let cap = config.traverse_limit as usize;
76        let capped = core::cmp::min(self.result_limit.get(), cap);
77        let result_limit = NonZeroUsize::new(capped).ok_or(crate::error::QueryError::LimitZero)?;
78        Ok(Self {
79            result_limit,
80            max_depth: self.max_depth,
81        })
82    }
83}
84
85/// Runs traversal through the shared BFS kernel.
86pub(crate) fn traverse_core(
87    engine: &mut crate::engine::Engine,
88    seeds: &[u32],
89    limits: TraverseLimits,
90    direction: TraversalDirection,
91    mode: TraverseMode,
92) -> Result<KernelTraversalOutcome, PostgresGraphError> {
93    let session = TraverseSession::open(engine, seeds, limits, direction, mode)?;
94    match run_bfs_multi(engine, &session)? {
95        KernelOutcome::Nodes(nodes) => Ok(KernelTraversalOutcome::Nodes(nodes)),
96        KernelOutcome::Count(count) => Ok(KernelTraversalOutcome::Count(count)),
97    }
98}
99
100/// Outcome of a kernel traversal before mode validation.
101pub(crate) enum KernelTraversalOutcome {
102    /// Collect mode node ids in BFS first-discovery order.
103    Nodes(alloc::vec::Vec<u32>),
104    /// Count-only mode cardinality.
105    Count(usize),
106}
107
108/// Collect-mode traversal through the shared kernel.
109pub(crate) fn traverse_core_collect(
110    engine: &mut crate::engine::Engine,
111    seeds: &[u32],
112    limits: TraverseLimits,
113    direction: TraversalDirection,
114) -> Result<alloc::vec::Vec<u32>, PostgresGraphError> {
115    match traverse_core(engine, seeds, limits, direction, TraverseMode::Collect)? {
116        KernelTraversalOutcome::Nodes(nodes) => Ok(nodes),
117        KernelTraversalOutcome::Count(_) => Err(crate::error::QueryError::InternalInvariant(
118            "expected nodes from collect traversal",
119        )
120        .into()),
121    }
122}
123
124/// Count-only traversal through the shared kernel.
125pub(crate) fn traverse_core_count(
126    engine: &mut crate::engine::Engine,
127    seeds: &[u32],
128    limits: TraverseLimits,
129    direction: TraversalDirection,
130) -> Result<usize, PostgresGraphError> {
131    match traverse_core(engine, seeds, limits, direction, TraverseMode::Count)? {
132        KernelTraversalOutcome::Count(count) => Ok(count),
133        KernelTraversalOutcome::Nodes(_) => Err(crate::error::QueryError::InternalInvariant(
134            "expected count from count-only traversal",
135        )
136        .into()),
137    }
138}
oxgraph_postgres/traverse/mod.rs

oxgraph_postgres/traverse/
mod.rs
