oxgraph_postgres/
overlay.rs

1//! Overlay buffers and tombstones layered on immutable base snapshots.
2
3use alloc::{
4    collections::{BTreeMap, BTreeSet},
5    vec::Vec,
6};
7
8/// Edge insertion applied on top of the frozen artifact.
9#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
10pub struct OverlayEdge {
11    /// Source node id in dense index space.
12    pub source: u32,
13    /// Target node id in dense index space.
14    pub target: u32,
15}
16
17/// Mutable overlay state for sync replay and query freshness.
18#[derive(Clone, Debug, Default, PartialEq, Eq)]
19pub struct OverlayState {
20    /// Edges inserted after the base artifact was published.
21    pub added_edges: Vec<OverlayEdge>,
22    /// Overlay targets grouped by source for `O(1)` forward expansion lookup.
23    by_source: BTreeMap<u32, Vec<u32>>,
24    /// Overlay sources grouped by target for `O(1)` inbound expansion lookup.
25    by_target: BTreeMap<u32, Vec<u32>>,
26    /// Base edge ids tombstoned by sync events.
27    pub tombstoned_edges: BTreeSet<u32>,
28    /// Node ids hidden from traversal results.
29    pub tombstoned_nodes: BTreeSet<u32>,
30}
31
32impl OverlayState {
33    /// Clears all overlay buffers and adjacency indexes.
34    pub fn clear(&mut self) {
35        self.added_edges.clear();
36        self.by_source.clear();
37        self.by_target.clear();
38        self.tombstoned_edges.clear();
39        self.tombstoned_nodes.clear();
40    }
41
42    /// Returns whether any base edge tombstones are recorded.
43    #[must_use]
44    pub fn has_edge_tombstones(&self) -> bool {
45        !self.tombstoned_edges.is_empty()
46    }
47
48    /// Returns whether any node tombstones are recorded.
49    #[must_use]
50    pub fn has_node_tombstones(&self) -> bool {
51        !self.tombstoned_nodes.is_empty()
52    }
53
54    /// Returns whether an edge id is visible to traversal.
55    ///
56    /// # Performance
57    ///
58    /// This method is `O(log t)` for `t` tombstoned edge ids.
59    #[must_use]
60    pub fn edge_visible(&self, edge_id: u32) -> bool {
61        !self.tombstoned_edges.contains(&edge_id)
62    }
63
64    /// Returns whether a node id is visible to traversal.
65    ///
66    /// # Performance
67    ///
68    /// This method is `O(log t)` for `t` tombstoned node ids.
69    #[must_use]
70    pub fn node_visible(&self, node_id: u32) -> bool {
71        !self.tombstoned_nodes.contains(&node_id)
72    }
73
74    /// Records an overlay edge and updates adjacency indexes.
75    ///
76    /// # Performance
77    ///
78    /// This method is `O(log s + log t)` for index map sizes `s` and `t`.
79    pub fn push_edge(&mut self, edge: OverlayEdge) {
80        self.added_edges.push(edge);
81        self.by_source
82            .entry(edge.source)
83            .or_default()
84            .push(edge.target);
85        self.by_target
86            .entry(edge.target)
87            .or_default()
88            .push(edge.source);
89    }
90
91    /// Returns overlay outgoing targets for `source` (empty when none).
92    ///
93    /// # Performance
94    ///
95    /// This method is `O(log s)` for `s` indexed sources.
96    #[must_use]
97    pub fn overlay_targets(&self, source: u32) -> &[u32] {
98        self.by_source
99            .get(&source)
100            .map_or(&[] as &[u32], Vec::as_slice)
101    }
102
103    /// Returns overlay incoming sources for `target` (empty when none).
104    ///
105    /// # Performance
106    ///
107    /// This method is `O(log t)` for `t` indexed targets.
108    #[must_use]
109    pub fn overlay_sources(&self, target: u32) -> &[u32] {
110        self.by_target
111            .get(&target)
112            .map_or(&[] as &[u32], Vec::as_slice)
113    }
114
115    /// Removes one overlay edge and rebuilds adjacency indexes.
116    ///
117    /// # Performance
118    ///
119    /// This method is `O(a)` for `a` overlay edges.
120    pub fn remove_edge(&mut self, source: u32, target: u32) {
121        self.added_edges
122            .retain(|edge| edge.source != source || edge.target != target);
123        self.rebuild_indexes();
124    }
125
126    /// Rebuilds `by_source` / `by_target` from `added_edges`.
127    ///
128    /// # Performance
129    ///
130    /// This method is `O(a)` for `a` overlay edges.
131    pub fn rebuild_indexes(&mut self) {
132        self.by_source.clear();
133        self.by_target.clear();
134        for edge in &self.added_edges {
135            self.by_source
136                .entry(edge.source)
137                .or_default()
138                .push(edge.target);
139            self.by_target
140                .entry(edge.target)
141                .or_default()
142                .push(edge.source);
143        }
144    }
145}
146
147#[cfg(test)]
148mod tests {
149    use super::{OverlayEdge, OverlayState};
150
151    #[test]
152    fn indexes_match_linear_scan() {
153        let mut overlay = OverlayState::default();
154        overlay.push_edge(OverlayEdge {
155            source: 1,
156            target: 2,
157        });
158        overlay.push_edge(OverlayEdge {
159            source: 1,
160            target: 3,
161        });
162        overlay.push_edge(OverlayEdge {
163            source: 4,
164            target: 1,
165        });
166        assert_eq!(overlay.overlay_targets(1), &[2, 3]);
167        assert_eq!(overlay.overlay_sources(1), &[4]);
168        overlay.clear();
169        assert!(overlay.overlay_targets(1).is_empty());
170    }
171
172    #[test]
173    fn rebuild_indexes_after_manual_edges() {
174        let mut overlay = OverlayState {
175            added_edges: vec![
176                OverlayEdge {
177                    source: 0,
178                    target: 1,
179                },
180                OverlayEdge {
181                    source: 2,
182                    target: 0,
183                },
184            ],
185            ..OverlayState::default()
186        };
187        overlay.rebuild_indexes();
188        assert_eq!(overlay.overlay_targets(0), &[1]);
189        assert_eq!(overlay.overlay_sources(0), &[2]);
190    }
191}
oxgraph_postgres/overlay.rs

oxgraph_postgres/
overlay.rs
