graph_r/traverse.rs
1// Author: spicyzhug@gmail.com
2// Copyright: lituus-io, all rights reserved
3//
4//! Zero-alloc traversal. [`LendingIterator`] is the crate's GAT seam: each
5//! step lends a view tied to the iterator's borrow, so implementations are
6//! free to reuse internal state per step without allocating — and future
7//! sources that materialize per-step stay possible behind the same trait.
8
9use crate::key::{EdgeType, NodeId, UrlKey};
10
11/// A GAT-based iterator whose items may borrow from the iterator itself.
12pub trait LendingIterator {
13 /// The lent item type.
14 type Item<'a>
15 where
16 Self: 'a;
17 /// Advance and lend the next item.
18 fn next(&mut self) -> Option<Self::Item<'_>>;
19}
20
21/// One outbound edge as seen from a snapshot.
22#[derive(Clone, Copy, Debug)]
23pub struct EdgeRef<'a> {
24 /// Destination node id in the current base generation, when resolved.
25 pub dst: Option<NodeId>,
26 /// Destination durable key (always present).
27 pub dst_key: UrlKey,
28 /// Destination canonical URL, when the destination is a known node with
29 /// a URL label (stubs have none).
30 pub dst_url: Option<&'a str>,
31 /// Edge type.
32 pub etype: EdgeType,
33 /// Raw edge flags (`format::base::eflags`).
34 pub flags: u8,
35 /// Weight in 1/65535 units.
36 pub weight: u16,
37}
38
39impl EdgeRef<'_> {
40 /// True when the edge was inferred rather than extracted from source.
41 #[must_use]
42 pub fn is_inferred(&self) -> bool {
43 self.flags & crate::format::base::eflags::INFERRED != 0
44 }
45}
46
47/// Lending iterator over a node's outbound edges. Constructed by
48/// [`crate::Snapshot::neighbors`]; each step resolves the destination lazily
49/// against the snapshot, allocating nothing.
50#[derive(Debug)]
51pub struct Neighbors<'s> {
52 pub(crate) inner: NeighborsInner<'s>,
53}
54
55#[derive(Debug)]
56pub(crate) enum NeighborsInner<'s> {
57 /// CSR run in the base file.
58 Base { snap: &'s crate::snapshot::Snapshot<'s>, edges: &'s [u8], idx: usize, end: usize },
59 /// Whole-set replacement living in the overlay: the op's fixed-width
60 /// entries, read in place.
61 Overlay { snap: &'s crate::snapshot::Snapshot<'s>, edges: &'s [u8], idx: usize },
62 /// The node has no edges.
63 Empty,
64}
65
66impl LendingIterator for Neighbors<'_> {
67 type Item<'a>
68 = EdgeRef<'a>
69 where
70 Self: 'a;
71
72 fn next(&mut self) -> Option<EdgeRef<'_>> {
73 match &mut self.inner {
74 NeighborsInner::Base { snap, edges, idx, end } => {
75 if idx >= end {
76 return None;
77 }
78 let rec = &edges[*idx * crate::format::base::EDGE_LEN
79 ..(*idx + 1) * crate::format::base::EDGE_LEN];
80 *idx += 1;
81 let dst = NodeId(crate::bytesio::get_u32(rec, 0));
82 let (dst_key, dst_url) = snap.node_identity(dst);
83 Some(EdgeRef {
84 dst: Some(dst),
85 dst_key,
86 dst_url,
87 etype: EdgeType::from_tag(rec[4]),
88 flags: rec[5],
89 weight: crate::bytesio::get_u16(rec, 6),
90 })
91 }
92 NeighborsInner::Overlay { snap, edges, idx } => {
93 if *idx >= crate::format::wal::edge_count(edges) {
94 return None;
95 }
96 let (dst_key, etype, flags, weight) = crate::format::wal::edge_at(edges, *idx);
97 *idx += 1;
98 let dst = snap.base_node_id(dst_key);
99 let dst_url = dst.and_then(|id| snap.node_identity(id).1);
100 Some(EdgeRef {
101 dst,
102 dst_key,
103 dst_url,
104 etype: EdgeType::from_tag(etype),
105 flags,
106 weight,
107 })
108 }
109 NeighborsInner::Empty => None,
110 }
111 }
112}
113
114/// Which edges a [`crate::Snapshot::walk`] follows.
115#[derive(Clone, Copy, Debug, PartialEq, Eq)]
116pub enum Direction {
117 /// Outbound: from a node to what it points at (a column to the columns
118 /// it derives from — upstream lineage).
119 Out,
120 /// Inbound: from a node to what points at it (a column to the columns
121 /// computed from it — downstream impact).
122 In,
123}
124
125/// One node reached by a walk.
126#[derive(Clone, Copy, Debug, PartialEq, Eq)]
127pub struct Hop {
128 /// The node reached.
129 pub key: UrlKey,
130 /// The node it was reached from.
131 pub from: UrlKey,
132 /// The type of the edge crossed.
133 pub etype: EdgeType,
134 /// Hops from the start (1 for direct neighbours).
135 pub depth: u32,
136 /// Every edge on the path carries `eflags::EXACT` (an unchanged copy).
137 pub exact_chain: bool,
138}
139
140/// Reusable walk state (visited set and frontiers). Keep one per thread:
141/// once its buffers have grown, walks allocate nothing.
142#[derive(Debug, Default)]
143pub struct Walk {
144 seen: std::collections::HashSet<u64>,
145 frontier: Vec<(UrlKey, bool)>,
146 next: Vec<(UrlKey, bool)>,
147}
148
149impl Walk {
150 /// Empty walk state.
151 #[must_use]
152 pub fn new() -> Self {
153 Self::default()
154 }
155}
156
157impl crate::Snapshot<'_> {
158 /// Breadth-first walk from `from` along edges in `dir` whose type
159 /// `follow` accepts, at most `max_depth` hops. `visit` sees every node
160 /// reached once, nearest first, and returns whether to continue past it
161 /// (so "the nearest described ancestor" is a walk that stops at
162 /// described nodes).
163 pub fn walk(
164 &self,
165 from: UrlKey,
166 dir: Direction,
167 max_depth: u32,
168 follow: impl Fn(EdgeType) -> bool,
169 w: &mut Walk,
170 visit: impl FnMut(Hop) -> bool,
171 ) {
172 let out = dir == Direction::Out;
173 self.walk_along(from, out, !out, max_depth, follow, w, visit);
174 }
175
176 /// [`crate::Snapshot::walk`] along outbound **and** inbound edges at once: the
177 /// lineage neighbourhood of a node (what it derives from and what derives
178 /// from it, and so on outwards). Each node is reached once, at its
179 /// shortest distance over either direction; a node's outbound edges are
180 /// offered before its inbound ones.
181 pub fn walk_both(
182 &self,
183 from: UrlKey,
184 max_depth: u32,
185 follow: impl Fn(EdgeType) -> bool,
186 w: &mut Walk,
187 visit: impl FnMut(Hop) -> bool,
188 ) {
189 self.walk_along(from, true, true, max_depth, follow, w, visit);
190 }
191
192 #[allow(clippy::too_many_arguments, clippy::fn_params_excessive_bools)] // private seam of the two walks
193 fn walk_along(
194 &self,
195 from: UrlKey,
196 out: bool,
197 inbound: bool,
198 max_depth: u32,
199 follow: impl Fn(EdgeType) -> bool,
200 w: &mut Walk,
201 mut visit: impl FnMut(Hop) -> bool,
202 ) {
203 w.seen.clear();
204 w.frontier.clear();
205 w.seen.insert(from.0);
206 w.frontier.push((from, true));
207 let exact = crate::format::base::eflags::EXACT;
208 for depth in 1..=max_depth {
209 w.next.clear();
210 for k in 0..w.frontier.len() {
211 let (node, chain) = w.frontier[k];
212 let mut step = |key: UrlKey, etype: EdgeType, flags: u8, w: &mut Walk| {
213 if !follow(etype) || !w.seen.insert(key.0) {
214 return;
215 }
216 let hop = Hop {
217 key,
218 from: node,
219 etype,
220 depth,
221 exact_chain: chain && flags & exact != 0,
222 };
223 if visit(hop) {
224 w.next.push((key, hop.exact_chain));
225 }
226 };
227 if out {
228 let mut it = self.neighbors(node);
229 while let Some(e) = it.next() {
230 step(e.dst_key, e.etype, e.flags, w);
231 }
232 }
233 if inbound {
234 self.in_edges(node, |src, etype, flags, _| step(src, etype, flags, w));
235 }
236 }
237 if w.next.is_empty() {
238 break;
239 }
240 std::mem::swap(&mut w.frontier, &mut w.next);
241 }
242 }
243}