1mod catalog;
11mod identifiers;
12mod observations;
13mod overlay;
14pub mod storage;
15mod trait_impl;
16
17use std::collections::{BTreeMap, BTreeSet};
18use std::sync::Arc;
19
20use uqa_core::{Edge, Vertex};
21use uqa_storage::{CatalogFacade, GraphEntityFilter, GraphEntityKind, PersistentStorageBackend};
22
23use crate::{
24 graphid_label_id, make_graphid, Direction, GraphLabelInfo, GraphLabelRegistry, GraphStore,
25 GraphStoreError, GraphStoreResult, LabelKind,
26};
27use storage::GraphStorage;
28
29const ID_PAGE_SIZE: usize = 256;
30
31pub struct PersistentGraphStore {
34 storage: Arc<dyn GraphStorage>,
35 resource: Option<Arc<dyn Send + Sync>>,
36 read: Option<observations::GraphRead>,
37}
38
39impl Clone for PersistentGraphStore {
40 fn clone(&self) -> Self {
41 Self {
42 storage: Arc::clone(&self.storage),
43 resource: self.resource.clone(),
44 read: self.read.clone(),
45 }
46 }
47}
48
49impl std::fmt::Debug for PersistentGraphStore {
50 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
51 f.debug_struct("PersistentGraphStore")
52 .finish_non_exhaustive()
53 }
54}
55
56impl PersistentGraphStore {
57 #[must_use]
59 pub fn from_catalog(
60 catalog: Arc<dyn CatalogFacade>,
61 backend: Arc<dyn PersistentStorageBackend>,
62 ) -> Self {
63 Self::from_storage(Arc::new(catalog::CatalogGraphStorage { catalog, backend }))
64 }
65
66 pub fn from_storage(storage: Arc<dyn GraphStorage>) -> Self {
67 Self {
68 storage,
69 resource: None,
70 read: None,
71 }
72 }
73
74 pub fn retain_resource(mut self, resource: Arc<dyn Send + Sync>) -> Self {
77 self.resource = Some(resource);
78 self
79 }
80
81 pub fn with_read_snapshot(&self, snapshot: &Self) -> Self {
84 let mut store = Self::from_storage(Arc::new(overlay::OverlayGraphStorage::new(
85 self.clone(),
86 snapshot.clone(),
87 )));
88 store.read.clone_from(&snapshot.read);
89 store
90 }
91
92 pub fn fork_for_mutation(&self) -> Self {
95 Self {
96 storage: self
97 .storage
98 .fork_overlay()
99 .unwrap_or_else(|| Arc::clone(&self.storage)),
100 resource: self.resource.clone(),
101 read: self.read.clone(),
102 }
103 }
104
105 pub fn unmodified_read_snapshot(&self) -> Option<Self> {
108 self.storage.unmodified_read_snapshot().map(|mut snapshot| {
109 if self.read.is_some() {
110 snapshot.read.clone_from(&self.read);
111 }
112 snapshot
113 })
114 }
115
116 pub(crate) fn transaction_mapped<T, E>(
117 &mut self,
118 operation: impl FnOnce(&mut Self) -> Result<T, E>,
119 map_error: impl Fn(GraphStoreError) -> E,
120 ) -> Result<T, E>
121 where
122 E: std::fmt::Display,
123 {
124 let mut checkpoint = self.storage.begin_write().map_err(&map_error)?;
125 let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| operation(self)));
126 match result {
127 Ok(Ok(value)) => match checkpoint.commit() {
128 Ok(()) => Ok(value),
129 Err(error) => {
130 checkpoint.rollback().map_err(|rollback| {
131 map_error(GraphStoreError::Storage(format!(
132 "{error}; rollback failed: {rollback}"
133 )))
134 })?;
135 Err(map_error(error))
136 }
137 },
138 Ok(Err(error)) => {
139 checkpoint.rollback().map_err(|rollback| {
140 map_error(GraphStoreError::Storage(format!(
141 "{error}; rollback failed: {rollback}"
142 )))
143 })?;
144 Err(error)
145 }
146 Err(panic) => {
147 drop(checkpoint);
148 std::panic::resume_unwind(panic)
149 }
150 }
151 }
152
153 fn require_graph(&self, graph: &str) -> GraphStoreResult<()> {
154 if self.storage.has_graph(graph)? {
155 Ok(())
156 } else {
157 Err(GraphStoreError::UnknownGraph(graph.to_owned()))
158 }
159 }
160
161 fn for_each_id(
162 &self,
163 filter: GraphEntityFilter<'_>,
164 mut visit: impl FnMut(u64) -> GraphStoreResult<()>,
165 ) -> GraphStoreResult<()> {
166 let mut after = None;
167 loop {
168 let ids = self.storage.ids(filter, after, ID_PAGE_SIZE)?;
169 if ids.is_empty() {
170 return Ok(());
171 }
172 after = ids.last().copied();
173 for id in ids {
174 visit(id)?;
175 }
176 }
177 }
178
179 fn collect_ids(&self, filter: GraphEntityFilter<'_>) -> GraphStoreResult<BTreeSet<u64>> {
180 self.observe_selection(filter, None)?;
181 let mut ids = BTreeSet::new();
182 self.for_each_id(filter, |id| {
183 ids.insert(id);
184 Ok(())
185 })?;
186 Ok(ids)
187 }
188
189 fn require_vertex(&self, id: u64) -> GraphStoreResult<Vertex> {
190 self.storage.vertex(id)?.ok_or_else(|| {
191 GraphStoreError::CorruptGraph(format!(
192 "graph membership references missing vertex {id}"
193 ))
194 })
195 }
196
197 fn require_edge(&self, id: u64, graph: &str) -> GraphStoreResult<Edge> {
198 let edge = self.storage.edge(id)?.ok_or_else(|| {
199 GraphStoreError::CorruptGraph(format!("graph {graph:?} references missing edge {id}"))
200 })?;
201 for endpoint in [edge.source_id, edge.target_id] {
202 if self
203 .storage
204 .has_membership(GraphEntityKind::Vertex, endpoint, graph)?
205 {
206 if self.storage.vertex(endpoint)?.is_some() {
207 continue;
208 }
209 } else if self
210 .storage
211 .registry(graph)?
212 .dropped_label_ids
213 .contains(&graphid_label_id(endpoint))
214 {
215 continue;
216 }
217 return Err(GraphStoreError::CorruptGraph(format!(
218 "graph {graph:?} edge {id} references missing endpoint {endpoint}"
219 )));
220 }
221 Ok(edge)
222 }
223
224 fn detach_entity(&self, kind: GraphEntityKind, id: u64, graph: &str) -> GraphStoreResult<()> {
225 self.storage.detach(kind, id, graph)?;
226 if self.storage.memberships(kind, id)?.is_empty() {
227 match kind {
228 GraphEntityKind::Vertex => self.storage.delete_vertex(id)?,
229 GraphEntityKind::Edge => self.storage.delete_edge(id)?,
230 }
231 }
232 Ok(())
233 }
234
235 fn reserve_id(&self, kind: GraphEntityKind, id: u64) -> GraphStoreResult<()> {
236 let next = id.checked_add(1).ok_or_else(|| {
237 GraphStoreError::IdExhausted(format!("{} id counter overflow", kind.as_str()))
238 })?;
239 if let Some(identifiers) = self.storage.identifiers()? {
240 return self.observe_durable_id(&identifiers, kind, id);
241 }
242 let previous = self.next_counter(kind)?;
243 if next > previous || self.storage.counter(kind)?.is_none() {
244 self.storage.save_counter(kind, next.max(previous))?;
245 }
246 Ok(())
247 }
248
249 fn next_counter(&self, kind: GraphEntityKind) -> GraphStoreResult<u64> {
250 if let Some(next) = self.storage.counter(kind)? {
251 return Ok(next);
252 }
253 self.storage
254 .max_id(kind)?
255 .unwrap_or(0)
256 .checked_add(1)
257 .ok_or_else(|| {
258 GraphStoreError::IdExhausted(format!("{} id counter overflow", kind.as_str()))
259 })
260 }
261
262 fn allocate_counter(&mut self, kind: GraphEntityKind) -> GraphStoreResult<u64> {
263 self.transaction(|store| {
264 store.storage.guard_definition(None)?;
265 if let Some(identifiers) = store.storage.identifiers()? {
266 return store.allocate_durable_counter(&identifiers, kind);
267 }
268 let id = store.next_counter(kind)?;
269 let next = id.checked_add(1).ok_or_else(|| {
270 GraphStoreError::IdExhausted(format!("{} id counter overflow", kind.as_str()))
271 })?;
272 store.storage.save_counter(kind, next)?;
273 Ok(id)
274 })
275 }
276
277 fn allocate_label_id(
278 &mut self,
279 label: &str,
280 graph: &str,
281 kind: LabelKind,
282 ) -> GraphStoreResult<u64> {
283 self.transaction(|store| {
284 store.require_graph(graph)?;
285 store.storage.guard_definition(Some(graph))?;
286 let mut registry = store.restored_registry(graph)?;
287 let selected = if label.is_empty() {
288 kind.default_label_name()
289 } else {
290 label
291 };
292 store.observe_labels(graph, Some(selected))?;
293 if registry.label_kind(selected).is_none() {
294 store.observe_labels(graph, Some(kind.default_label_name()))?;
295 }
296 let label_id = store.resolve_label(&mut registry, label, kind)?;
297 if let Some(identifiers) = store.storage.identifiers()? {
298 let id = store.allocate_durable_label(&identifiers, ®istry, label_id, kind)?;
299 store.save_registry(graph, ®istry)?;
300 return Ok(id);
301 }
302 let id = make_graphid(label_id, registry.next_sequence(label_id)?)?;
303 store.save_registry(graph, ®istry)?;
304 Ok(id)
305 })
306 }
307
308 pub fn label_registry(&self, graph: &str) -> GraphStoreResult<GraphLabelRegistry> {
309 self.observe_definition(
310 uqa_storage::catalog::graph_observations::GraphDefinitionKind::NamedGraph,
311 Some(graph),
312 )?;
313 self.observe_definition(
314 uqa_storage::catalog::graph_observations::GraphDefinitionKind::LabelRegistry,
315 Some(graph),
316 )?;
317 self.restored_registry(graph)
318 }
319
320 pub(crate) fn restored_registry(&self, graph: &str) -> GraphStoreResult<GraphLabelRegistry> {
321 self.require_graph(graph)?;
322 let mut registry = self.storage.registry(graph)?;
323 if let Some(identifiers) = self.storage.identifiers()? {
324 identifiers.restore_registry(graph, &mut registry)?;
325 }
326 Ok(registry)
327 }
328
329 pub fn graph_labels(&self, graph: &str) -> GraphStoreResult<Vec<GraphLabelInfo>> {
330 self.observe_labels(graph, None)?;
331 Ok(self.restored_registry(graph)?.labels())
332 }
333
334 pub fn graph_label_kind(
335 &self,
336 graph: &str,
337 label: &str,
338 ) -> GraphStoreResult<Option<LabelKind>> {
339 self.observe_labels(graph, Some(label))?;
340 Ok(self.restored_registry(graph)?.label_kind(label))
341 }
342
343 pub fn import_label_registry(
344 &mut self,
345 graph: &str,
346 registry: &GraphLabelRegistry,
347 ) -> GraphStoreResult<()> {
348 self.transaction(|store| {
349 let mut combined = store.label_registry(graph)?;
350 combined.merge(registry);
351 store.save_registry(graph, &combined)
352 })
353 }
354
355 pub fn rebuild_label_registry_from_ids(&mut self, graph: &str) -> GraphStoreResult<()> {
358 self.transaction(|store| {
359 let mut registry = store.restored_registry(graph)?;
360 for kind in [GraphEntityKind::Vertex, GraphEntityKind::Edge] {
361 store.for_each_id(GraphEntityFilter::new(kind, Some(graph)), |id| {
362 match kind {
363 GraphEntityKind::Vertex => registry.observe(
364 &store.require_vertex(id)?.label,
365 id,
366 LabelKind::Vertex,
367 ),
368 GraphEntityKind::Edge => registry.observe(
369 &store.require_edge(id, graph)?.label,
370 id,
371 LabelKind::Edge,
372 ),
373 };
374 Ok(())
375 })?;
376 }
377 store.save_registry(graph, ®istry)
378 })
379 }
380
381 pub fn create_label(
382 &mut self,
383 graph: &str,
384 label: &str,
385 kind: LabelKind,
386 ) -> GraphStoreResult<Option<u32>> {
387 self.transaction(|store| {
388 store.observe_labels(graph, Some(label))?;
389 let mut registry = store.restored_registry(graph)?;
390 if registry.label_kind(label).is_none() {
391 store.observe_labels(graph, Some(kind.default_label_name()))?;
392 }
393 let result = registry
394 .register_label(label, kind)?
395 .map(|proposed| store.reserve_label_definition(&mut registry, label, proposed))
396 .transpose()?;
397 if result.is_some() {
398 store.save_registry(graph, ®istry)?;
399 }
400 Ok(result)
401 })
402 }
403
404 pub fn drop_label(
405 &mut self,
406 graph: &str,
407 label: &str,
408 ) -> GraphStoreResult<Option<(u32, LabelKind)>> {
409 self.transaction(|store| {
410 store.observe_labels(graph, Some(label))?;
411 let mut registry = store.restored_registry(graph)?;
412 let Some(kind) = registry.label_kind(label) else {
413 return Ok(None);
414 };
415 let default = label == kind.default_label_name();
416 let id = if default {
417 store.observe_labels(graph, None)?;
418 if let Some(dependent) = registry
419 .labels
420 .keys()
421 .find(|name| registry.label_kind(name) == Some(kind))
422 {
423 return Err(GraphStoreError::InvalidMutation(format!(
424 "cannot drop default label {label} while label {dependent} depends on it"
425 )));
426 }
427 kind.default_label_id()
428 } else {
429 *registry.labels.get(label).ok_or_else(|| {
430 GraphStoreError::CorruptGraph(format!(
431 "graph {graph:?} label {label:?} has no registry id"
432 ))
433 })?
434 };
435 let entity_kind = match kind {
436 LabelKind::Vertex => GraphEntityKind::Vertex,
437 LabelKind::Edge => GraphEntityKind::Edge,
438 };
439 let mut filter = GraphEntityFilter::new(entity_kind, Some(graph));
440 if !default {
441 filter.label = Some(label);
442 }
443 store.for_each_selected_id(filter, |entity_id| {
446 if !default || graphid_label_id(entity_id) == id {
447 store.detach_entity(entity_kind, entity_id, graph)?;
448 }
449 Ok(())
450 })?;
451 registry.remove_label(label);
452 store.save_registry(graph, ®istry)?;
453 Ok(Some((id, kind)))
454 })
455 }
456
457 pub fn rename_graph(&mut self, from: &str, to: &str) -> GraphStoreResult<()> {
458 if from == to {
459 return Ok(());
460 }
461 self.transaction(|store| {
462 store.require_graph(from)?;
463 if store.storage.has_graph(to)? {
464 return Err(GraphStoreError::InvalidMutation(format!(
465 "graph {to:?} already exists"
466 )));
467 }
468 store.storage.create_graph(to)?;
469 store.save_registry(to, &store.label_registry(from)?)?;
470 for kind in [GraphEntityKind::Vertex, GraphEntityKind::Edge] {
471 store.for_each_selected_id(GraphEntityFilter::new(kind, Some(from)), |id| {
472 store.storage.attach(kind, id, to)?;
473 store.storage.detach(kind, id, from)
474 })?;
475 }
476 store.storage.delete_graph(from)
477 })
478 }
479
480 fn algebra(
481 &mut self,
482 first: &str,
483 second: Option<&str>,
484 target: &str,
485 keep: impl Fn(bool) -> bool,
486 include_second: bool,
487 ) -> GraphStoreResult<()> {
488 self.transaction(|store| {
489 store.require_graph(first)?;
490 if let Some(second) = second {
491 store.require_graph(second)?;
492 }
493 store.create_graph(target)?;
494 for kind in [GraphEntityKind::Vertex, GraphEntityKind::Edge] {
495 store.for_each_selected_id(GraphEntityFilter::new(kind, Some(first)), |id| {
496 let common = match second {
497 Some(second) => {
498 store.observe_membership(kind, id, Some(second))?;
499 store.storage.has_membership(kind, id, second)?
500 }
501 None => false,
502 };
503 if keep(common) {
504 store.storage.attach(kind, id, target)?;
505 }
506 Ok(())
507 })?;
508 if let Some(second) = second.filter(|_| include_second) {
509 store
510 .for_each_selected_id(GraphEntityFilter::new(kind, Some(second)), |id| {
511 store.storage.attach(kind, id, target)
512 })?;
513 }
514 }
515 let mut registry = store.label_registry(target)?;
516 registry.merge(&store.label_registry(first)?);
517 if let Some(second) = second {
518 registry.merge(&store.label_registry(second)?);
519 }
520 store.save_registry(target, ®istry)
521 })
522 }
523}