Skip to main content

uqa_graph/persistent_store/
trait_impl.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Graph operations over indexed durable records and storage checkpoints.
8
9use super::{
10    BTreeMap, BTreeSet, Direction, Edge, GraphEntityFilter, GraphEntityKind, GraphLabelRegistry,
11    GraphStore, GraphStoreError, GraphStoreResult, LabelKind, PersistentGraphStore, Vertex,
12};
13
14impl GraphStore for PersistentGraphStore {
15    fn vertex_id_page(
16        &self,
17        graph: &str,
18        after: Option<u64>,
19        limit: usize,
20    ) -> GraphStoreResult<Vec<u64>> {
21        self.require_graph(graph)?;
22        let filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
23        self.observe_selection(filter, after)?;
24        self.storage.ids(filter, after, limit)
25    }
26    fn edge_id_page(
27        &self,
28        graph: &str,
29        after: Option<u64>,
30        limit: usize,
31    ) -> GraphStoreResult<Vec<u64>> {
32        self.require_graph(graph)?;
33        let filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
34        self.observe_selection(filter, after)?;
35        self.storage.ids(filter, after, limit)
36    }
37    fn transaction<T>(
38        &mut self,
39        operation: impl FnOnce(&mut Self) -> GraphStoreResult<T>,
40    ) -> GraphStoreResult<T> {
41        self.transaction_mapped(operation, std::convert::identity)
42    }
43
44    fn create_graph(&mut self, name: &str) -> GraphStoreResult<()> {
45        self.transaction(|store| {
46            if !store.has_graph(name)? {
47                store.storage.create_graph(name)?;
48                let registry = GraphLabelRegistry {
49                    allocation_id: if store.storage.identifiers()?.is_some() {
50                        uqa_storage::catalog::new_nonzero_catalog_identity("graph", "allocation")?
51                    } else {
52                        [0; 16]
53                    },
54                    ..GraphLabelRegistry::default()
55                };
56                store.save_registry(name, &registry)?;
57            }
58            Ok(())
59        })
60    }
61    fn drop_graph(&mut self, name: &str) -> GraphStoreResult<()> {
62        self.transaction(|store| {
63            if !store.has_graph(name)? {
64                return Ok(());
65            }
66            for kind in [GraphEntityKind::Edge, GraphEntityKind::Vertex] {
67                store.for_each_selected_id(GraphEntityFilter::new(kind, Some(name)), |id| {
68                    store.detach_entity(kind, id, name)
69                })?;
70            }
71            store.storage.delete_graph(name)
72        })
73    }
74    fn graph_names(&self) -> GraphStoreResult<Vec<String>> {
75        self.observe_definition(
76            uqa_storage::catalog::graph_observations::GraphDefinitionKind::NamedGraph,
77            None,
78        )?;
79        self.storage.graph_names()
80    }
81    fn has_graph(&self, name: &str) -> GraphStoreResult<bool> {
82        self.observe_definition(
83            uqa_storage::catalog::graph_observations::GraphDefinitionKind::NamedGraph,
84            Some(name),
85        )?;
86        self.storage.has_graph(name)
87    }
88    fn union_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
89        self.algebra(g1, Some(g2), target, |_| true, true)
90    }
91    fn intersect_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
92        self.algebra(g1, Some(g2), target, |common| common, false)
93    }
94    fn difference_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
95        self.algebra(g1, Some(g2), target, |common| !common, false)
96    }
97    fn copy_graph(&mut self, source: &str, target: &str) -> GraphStoreResult<()> {
98        self.algebra(source, None, target, |_| true, false)
99    }
100
101    fn add_vertex(&mut self, vertex: Vertex, graph: &str) -> GraphStoreResult<()> {
102        self.transaction(|store| {
103            store.require_graph(graph)?;
104            store.storage.guard_definition(Some(graph))?;
105            store.reserve_id(GraphEntityKind::Vertex, vertex.vertex_id)?;
106            store.storage.save_vertex(&vertex)?;
107            store
108                .storage
109                .attach(GraphEntityKind::Vertex, vertex.vertex_id, graph)?;
110            for owner in store
111                .storage
112                .memberships(GraphEntityKind::Vertex, vertex.vertex_id)?
113            {
114                store.storage.guard_definition(Some(&owner))?;
115                let mut registry = store.restored_registry(&owner)?;
116                if registry.observe(&vertex.label, vertex.vertex_id, LabelKind::Vertex) {
117                    store.save_registry(&owner, &registry)?;
118                }
119            }
120            Ok(())
121        })
122    }
123    fn add_edge(&mut self, edge: Edge, graph: &str) -> GraphStoreResult<()> {
124        self.transaction(|store| {
125            store.require_graph(graph)?;
126            let mut owners = store
127                .storage
128                .memberships(GraphEntityKind::Edge, edge.edge_id)?;
129            if !owners.iter().any(|owner| owner == graph) {
130                owners.push(graph.to_owned());
131            }
132            for owner in &owners {
133                store.storage.guard_definition(Some(owner))?;
134                for id in [edge.source_id, edge.target_id] {
135                    if !store
136                        .storage
137                        .has_membership(GraphEntityKind::Vertex, id, owner)?
138                    {
139                        return Err(GraphStoreError::InvalidMutation(format!(
140                            "edge {} references endpoint outside graph {owner:?}: {} -> {}",
141                            edge.edge_id, edge.source_id, edge.target_id
142                        )));
143                    }
144                    store.require_vertex(id)?;
145                }
146            }
147            store.reserve_id(GraphEntityKind::Edge, edge.edge_id)?;
148            store.storage.save_edge(&edge)?;
149            store
150                .storage
151                .attach(GraphEntityKind::Edge, edge.edge_id, graph)?;
152            for owner in owners {
153                let mut registry = store.restored_registry(&owner)?;
154                if registry.observe(&edge.label, edge.edge_id, LabelKind::Edge) {
155                    store.save_registry(&owner, &registry)?;
156                }
157            }
158            Ok(())
159        })
160    }
161    fn remove_vertex(&mut self, vertex_id: u64, graph: &str) -> GraphStoreResult<()> {
162        self.transaction(|store| {
163            store.require_graph(graph)?;
164            if !store
165                .storage
166                .has_membership(GraphEntityKind::Vertex, vertex_id, graph)?
167            {
168                return Ok(());
169            }
170            for outgoing in [true, false] {
171                let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
172                if outgoing {
173                    filter.source = Some(vertex_id);
174                } else {
175                    filter.target = Some(vertex_id);
176                }
177                store.for_each_selected_id(filter, |id| {
178                    store.detach_entity(GraphEntityKind::Edge, id, graph)
179                })?;
180            }
181            store.detach_entity(GraphEntityKind::Vertex, vertex_id, graph)
182        })
183    }
184    fn remove_edge(&mut self, edge_id: u64, graph: &str) -> GraphStoreResult<()> {
185        self.transaction(|store| {
186            store.require_graph(graph)?;
187            store.detach_entity(GraphEntityKind::Edge, edge_id, graph)
188        })
189    }
190
191    fn neighbors(
192        &self,
193        vertex_id: u64,
194        label: Option<&str>,
195        direction: Direction,
196        graph: &str,
197    ) -> GraphStoreResult<Vec<u64>> {
198        self.require_vertex_in_graph(vertex_id, graph)?;
199        let mut neighbors = Vec::new();
200        for outgoing in [true, false] {
201            if (outgoing && direction == Direction::In)
202                || (!outgoing && direction == Direction::Out)
203            {
204                continue;
205            }
206            let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
207            filter.label = label;
208            if outgoing {
209                filter.source = Some(vertex_id);
210            } else {
211                filter.target = Some(vertex_id);
212            }
213            self.for_each_selected_id(filter, |id| {
214                let edge = self.require_edge(id, graph)?;
215                neighbors.push(if outgoing {
216                    edge.target_id
217                } else {
218                    edge.source_id
219                });
220                Ok(())
221            })?;
222        }
223        if direction == Direction::Both {
224            neighbors.sort_unstable();
225            neighbors.dedup();
226        }
227        Ok(neighbors)
228    }
229    fn vertices_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Vertex>> {
230        self.require_graph(graph)?;
231        let mut filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
232        filter.label = Some(label);
233        let mut result = Vec::new();
234        self.for_each_selected_id(filter, |id| {
235            self.observe_entity(GraphEntityKind::Vertex, id)?;
236            result.push(self.require_vertex(id)?);
237            Ok(())
238        })?;
239        Ok(result)
240    }
241    fn vertex_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<u64>> {
242        self.require_graph(graph)?;
243        let mut filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
244        filter.label = Some(label);
245        Ok(self.collect_ids(filter)?.into_iter().collect())
246    }
247    fn vertices_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Vertex>> {
248        self.require_graph(graph)?;
249        let mut result = Vec::new();
250        self.for_each_selected_id(
251            GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
252            |id| {
253                self.observe_entity(GraphEntityKind::Vertex, id)?;
254                result.push(self.require_vertex(id)?);
255                Ok(())
256            },
257        )?;
258        Ok(result)
259    }
260    fn edges_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Edge>> {
261        self.require_graph(graph)?;
262        let mut result = Vec::new();
263        self.for_each_selected_id(
264            GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph)),
265            |id| {
266                self.observe_entity(GraphEntityKind::Edge, id)?;
267                result.push(self.require_edge(id, graph)?);
268                Ok(())
269            },
270        )?;
271        Ok(result)
272    }
273    fn vertex_graphs(&self, id: u64) -> GraphStoreResult<BTreeSet<String>> {
274        self.observe_membership(GraphEntityKind::Vertex, id, None)?;
275        Ok(self
276            .storage
277            .memberships(GraphEntityKind::Vertex, id)?
278            .into_iter()
279            .collect())
280    }
281    fn edges_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Edge>> {
282        self.require_graph(graph)?;
283        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
284        filter.label = Some(label);
285        let mut edges = Vec::new();
286        self.for_each_selected_id(filter, |id| {
287            self.observe_entity(GraphEntityKind::Edge, id)?;
288            edges.push(self.require_edge(id, graph)?);
289            Ok(())
290        })?;
291        Ok(edges)
292    }
293
294    fn edge_graphs(&self, id: u64) -> GraphStoreResult<BTreeSet<String>> {
295        self.observe_membership(GraphEntityKind::Edge, id, None)?;
296        Ok(self
297            .storage
298            .memberships(GraphEntityKind::Edge, id)?
299            .into_iter()
300            .collect())
301    }
302    fn out_edge_ids(&self, id: u64, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
303        self.require_vertex_in_graph(id, graph)?;
304        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
305        filter.source = Some(id);
306        let ids = self.collect_ids(filter)?;
307        for id in &ids {
308            self.require_edge(*id, graph)?;
309        }
310        Ok(ids)
311    }
312    fn in_edge_ids(&self, id: u64, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
313        self.require_vertex_in_graph(id, graph)?;
314        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
315        filter.target = Some(id);
316        let ids = self.collect_ids(filter)?;
317        for id in &ids {
318            self.require_edge(*id, graph)?;
319        }
320        Ok(ids)
321    }
322    fn edge_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
323        self.require_graph(graph)?;
324        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
325        filter.label = Some(label);
326        let ids = self.collect_ids(filter)?;
327        for id in &ids {
328            self.require_edge(*id, graph)?;
329        }
330        Ok(ids)
331    }
332    fn vertex_ids_in_graph(&self, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
333        self.require_graph(graph)?;
334        self.collect_ids(GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)))
335    }
336    fn require_vertex_in_graph(&self, id: u64, graph: &str) -> GraphStoreResult<()> {
337        self.require_graph(graph)?;
338        self.observe_membership(GraphEntityKind::Vertex, id, Some(graph))?;
339        if !self
340            .storage
341            .has_membership(GraphEntityKind::Vertex, id, graph)?
342        {
343            return Err(GraphStoreError::InvalidQuery(format!(
344                "vertex {id} is not a member of graph {graph:?}"
345            )));
346        }
347        self.require_vertex(id)?;
348        Ok(())
349    }
350
351    fn degree_distribution(&self, graph: &str) -> GraphStoreResult<BTreeMap<u64, u64>> {
352        self.require_graph(graph)?;
353        let mut result = BTreeMap::new();
354        self.for_each_selected_id(
355            GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
356            |id| {
357                let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
358                filter.source = Some(id);
359                self.observe_selection(filter, None)?;
360                result.insert(id, self.storage.count(filter)?);
361                Ok(())
362            },
363        )?;
364        Ok(result)
365    }
366    fn label_degree(&self, label: &str, graph: &str) -> GraphStoreResult<f64> {
367        self.require_graph(graph)?;
368        let mut sources = BTreeSet::new();
369        let mut count = 0_usize;
370        let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
371        filter.label = Some(label);
372        self.for_each_selected_id(filter, |id| {
373            sources.insert(self.require_edge(id, graph)?.source_id);
374            count += 1;
375            Ok(())
376        })?;
377        if sources.is_empty() {
378            return Ok(0.0);
379        }
380        Ok(
381            crate::memory_store::usize_to_f64_exact(count, "edge label count")?
382                / crate::memory_store::usize_to_f64_exact(
383                    sources.len(),
384                    "edge label source count",
385                )?,
386        )
387    }
388    fn vertex_label_counts(&self, graph: &str) -> GraphStoreResult<BTreeMap<String, u64>> {
389        self.require_graph(graph)?;
390        let mut result = BTreeMap::new();
391        self.for_each_selected_id(
392            GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
393            |id| {
394                *result.entry(self.require_vertex(id)?.label).or_default() += 1;
395                Ok(())
396            },
397        )?;
398        Ok(result)
399    }
400    fn get_vertex(&self, id: u64) -> GraphStoreResult<Option<Vertex>> {
401        self.observe_entity(GraphEntityKind::Vertex, id)?;
402        self.storage.vertex(id)
403    }
404    fn for_each_vertex_borrowed(
405        &self,
406        ids: &[u64],
407        visit: &mut dyn FnMut(u64, Option<&Vertex>) -> bool,
408    ) -> GraphStoreResult<Option<usize>> {
409        // Observation namespaces can themselves require storage reads. Keep
410        // those per-entity admissions outside a borrowed physical read window.
411        if self.read.is_some() {
412            return Ok(None);
413        }
414        self.storage.for_each_vertex_borrowed(ids, visit)
415    }
416    fn get_edge(&self, id: u64) -> GraphStoreResult<Option<Edge>> {
417        self.observe_entity(GraphEntityKind::Edge, id)?;
418        self.storage.edge(id)
419    }
420    fn next_vertex_id(&mut self) -> GraphStoreResult<u64> {
421        self.allocate_counter(GraphEntityKind::Vertex)
422    }
423    fn next_edge_id(&mut self) -> GraphStoreResult<u64> {
424        self.allocate_counter(GraphEntityKind::Edge)
425    }
426    fn allocate_vertex_id(&mut self, label: &str, graph: &str) -> GraphStoreResult<u64> {
427        self.allocate_label_id(label, graph, LabelKind::Vertex)
428    }
429    fn allocate_edge_id(&mut self, label: &str, graph: &str) -> GraphStoreResult<u64> {
430        self.allocate_label_id(label, graph, LabelKind::Edge)
431    }
432    fn clear(&mut self) -> GraphStoreResult<()> {
433        self.transaction(|store| {
434            for graph in store.graph_names()? {
435                store.drop_graph(&graph)?;
436            }
437            for kind in [GraphEntityKind::Vertex, GraphEntityKind::Edge] {
438                // Also release global records left without any membership.
439                store.for_each_selected_id(
440                    GraphEntityFilter::new(kind, None),
441                    |id| match kind {
442                        GraphEntityKind::Vertex => store.storage.delete_vertex(id),
443                        GraphEntityKind::Edge => store.storage.delete_edge(id),
444                    },
445                )?;
446                store.storage.save_counter(kind, 1)?;
447            }
448            store.storage.reset_identifiers()?;
449            Ok(())
450        })
451    }
452    fn vertices(&self) -> GraphStoreResult<BTreeMap<u64, Vertex>> {
453        let mut result = BTreeMap::new();
454        self.for_each_selected_id(
455            GraphEntityFilter::new(GraphEntityKind::Vertex, None),
456            |id| {
457                self.observe_entity(GraphEntityKind::Vertex, id)?;
458                result.insert(id, self.require_vertex(id)?);
459                Ok(())
460            },
461        )?;
462        Ok(result)
463    }
464    fn edges(&self) -> GraphStoreResult<BTreeMap<u64, Edge>> {
465        let mut result = BTreeMap::new();
466        self.for_each_selected_id(GraphEntityFilter::new(GraphEntityKind::Edge, None), |id| {
467            self.observe_entity(GraphEntityKind::Edge, id)?;
468            let edge = self
469                .storage
470                .edge(id)?
471                .ok_or_else(|| GraphStoreError::CorruptGraph(format!("missing edge {id}")))?;
472            result.insert(id, edge);
473            Ok(())
474        })?;
475        Ok(result)
476    }
477}