Skip to main content

uqa_graph/index/
path_index.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Reachability indexes: primary memory for memory graphs, physical records
8//! for durable graphs. No persistent index is rebuilt or hydrated on open.
9
10use crate::{Direction, GraphStore, GraphStoreError, GraphStoreResult, PersistentGraphStore};
11use std::collections::{BTreeMap, BTreeSet};
12use std::sync::Arc;
13use uqa_storage::{CatalogFacade, PersistentStorageBackend};
14
15type Pairs = BTreeSet<(u64, u64)>;
16type MemoryPaths = BTreeMap<Vec<String>, Pairs>;
17
18#[derive(Clone)]
19enum PathStorage {
20    Memory(Arc<MemoryPaths>),
21    Persistent(Arc<DurablePathIndex>),
22    ReadView {
23        store: Arc<crate::GraphStoreHandle>,
24        graph: String,
25        sequences: Vec<Vec<String>>,
26    },
27}
28
29struct DurablePathIndex {
30    catalog: Arc<dyn CatalogFacade>,
31    backend: Arc<dyn PersistentStorageBackend>,
32    key: String,
33    graph: String,
34    sequences: Vec<Vec<String>>,
35    definition: String,
36    read_gate: parking_lot::ReentrantMutex<()>,
37}
38
39/// Fixed-label-sequence reachability. Durable clones copy only a handle.
40/// Queries return owned results and can report storage errors.
41#[derive(Clone)]
42pub struct PathIndex {
43    storage: PathStorage,
44}
45
46impl std::fmt::Debug for PathIndex {
47    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48        formatter
49            .debug_struct("PathIndex")
50            .field("paths", &self.indexed_paths())
51            .field(
52                "persistent",
53                &matches!(self.storage, PathStorage::Persistent(_)),
54            )
55            .finish()
56    }
57}
58
59impl Default for PathIndex {
60    fn default() -> Self {
61        Self {
62            storage: PathStorage::Memory(Arc::default()),
63        }
64    }
65}
66
67fn json_error(error: &serde_json::Error) -> GraphStoreError {
68    GraphStoreError::CorruptGraph(error.to_string())
69}
70
71fn observed_store(
72    catalog: Arc<dyn CatalogFacade>,
73    backend: Arc<dyn PersistentStorageBackend>,
74) -> GraphStoreResult<PersistentGraphStore> {
75    let context = backend
76        .serializable_session()
77        .map(uqa_storage::mvcc::SerializableSession::serializable_read_context)
78        .transpose()?
79        .flatten();
80    let cancellation = backend.write_cancellation().unwrap_or_default();
81    let store = PersistentGraphStore::from_catalog(catalog, backend);
82    Ok(match context {
83        Some(context) => store.with_serializable_read(context, &cancellation),
84        None => store,
85    })
86}
87
88impl PathIndex {
89    pub fn build<G: GraphStore>(
90        store: &G,
91        graph: &str,
92        sequences: &[Vec<String>],
93    ) -> GraphStoreResult<Self> {
94        let mut paths = BTreeMap::new();
95        for sequence in sequences {
96            let mut pairs = Pairs::new();
97            visit_pairs(store, graph, sequence, |pair| {
98                pairs.insert(pair);
99                Ok(())
100            })?;
101            paths.insert(sequence.clone(), pairs);
102        }
103        Ok(Self {
104            storage: PathStorage::Memory(Arc::new(paths)),
105        })
106    }
107
108    /// Bind a durable definition without reading any entity or reachability row.
109    pub fn open_persistent(
110        catalog: Arc<dyn CatalogFacade>,
111        backend: Arc<dyn PersistentStorageBackend>,
112        key: &str,
113        graph: &str,
114        sequences: &[Vec<String>],
115    ) -> GraphStoreResult<Self> {
116        Ok(Self {
117            storage: PathStorage::Persistent(Arc::new(DurablePathIndex {
118                catalog,
119                backend,
120                key: key.to_owned(),
121                graph: graph.to_owned(),
122                sequences: sequences.to_vec(),
123                definition: serde_json::to_string(sequences).map_err(|error| json_error(&error))?,
124                read_gate: parking_lot::ReentrantMutex::new(()),
125            })),
126        })
127    }
128
129    /// Build in bounded batches in one storage checkpoint. A failure preserves
130    /// both the old definition and its materialization.
131    pub fn build_persistent(
132        catalog: Arc<dyn CatalogFacade>,
133        backend: Arc<dyn PersistentStorageBackend>,
134        key: &str,
135        graph: &str,
136        sequences: &[Vec<String>],
137    ) -> GraphStoreResult<Self> {
138        let definition = serde_json::to_string(sequences).map_err(|error| json_error(&error))?;
139        let mut store = observed_store(Arc::clone(&catalog), Arc::clone(&backend))?;
140        store.transaction(|store| {
141            catalog.save_path_index(key, &definition)?;
142            catalog.clear_path_index_data(key)?;
143            for sequence in sequences {
144                let sequence_key =
145                    serde_json::to_string(sequence).map_err(|error| json_error(&error))?;
146                let mut page = Vec::with_capacity(256);
147                visit_pairs(store, graph, sequence, |pair| {
148                    page.push(pair);
149                    if page.len() == 256 {
150                        catalog.save_path_index_pairs(key, &sequence_key, &page)?;
151                        page.clear();
152                    }
153                    Ok(())
154                })?;
155                if !page.is_empty() {
156                    catalog.save_path_index_pairs(key, &sequence_key, &page)?;
157                }
158            }
159            catalog.finish_path_index_data(key, graph, &definition)?;
160            Ok(())
161        })?;
162        Self::open_persistent(catalog, backend, key, graph, sequences)
163    }
164
165    /// Rebind only the physical session, never copy the index's data.
166    pub fn rebind_persistent(
167        &self,
168        catalog: Arc<dyn CatalogFacade>,
169        backend: Arc<dyn PersistentStorageBackend>,
170    ) -> GraphStoreResult<Self> {
171        match &self.storage {
172            PathStorage::Memory(_) | PathStorage::ReadView { .. } => Ok(self.clone()),
173            PathStorage::Persistent(index) => {
174                Self::open_persistent(catalog, backend, &index.key, &index.graph, &index.sequences)
175            }
176        }
177    }
178
179    /// Bind a transaction/cursor view whose own-write overlay cannot use
180    /// reachability pages from the live storage transaction. Only requested
181    /// sequences are evaluated; no resident index or graph is constructed.
182    #[must_use]
183    pub fn with_graph_read_view(&self, store: Arc<crate::GraphStoreHandle>) -> Self {
184        let (graph, sequences) = match &self.storage {
185            PathStorage::Memory(_) => return self.clone(),
186            PathStorage::Persistent(index) => (&index.graph, &index.sequences),
187            PathStorage::ReadView {
188                graph, sequences, ..
189            } => (graph, sequences),
190        };
191        Self {
192            storage: PathStorage::ReadView {
193                store,
194                graph: graph.clone(),
195                sequences: sequences.clone(),
196            },
197        }
198    }
199
200    pub fn lookup(&self, sequence: &[String]) -> GraphStoreResult<Option<Pairs>> {
201        match &self.storage {
202            PathStorage::Memory(paths) => Ok(paths.get(sequence).cloned()),
203            PathStorage::ReadView {
204                store,
205                graph,
206                sequences,
207            } => {
208                if !sequences.iter().any(|candidate| candidate == sequence) {
209                    return Ok(None);
210                }
211                let mut pairs = Pairs::new();
212                visit_pairs(store.as_ref(), graph, sequence, |pair| {
213                    pairs.insert(pair);
214                    Ok(())
215                })?;
216                Ok(Some(pairs))
217            }
218            PathStorage::Persistent(index) => {
219                if !index
220                    .sequences
221                    .iter()
222                    .any(|candidate| candidate == sequence)
223                {
224                    return Ok(None);
225                }
226                index.lookup(sequence).map(Some)
227            }
228        }
229    }
230
231    pub fn has_path(&self, sequence: &[String]) -> bool {
232        match &self.storage {
233            PathStorage::Memory(paths) => paths.contains_key(sequence),
234            PathStorage::ReadView { sequences, .. } => {
235                sequences.iter().any(|candidate| candidate == sequence)
236            }
237            PathStorage::Persistent(index) => index
238                .sequences
239                .iter()
240                .any(|candidate| candidate == sequence),
241        }
242    }
243
244    pub fn indexed_paths(&self) -> Vec<String> {
245        let paths: BTreeSet<String> = match &self.storage {
246            PathStorage::Memory(paths) => paths.keys().map(|sequence| sequence.join("/")).collect(),
247            PathStorage::ReadView { sequences, .. } => sequences
248                .iter()
249                .map(|sequence| sequence.join("/"))
250                .collect(),
251            PathStorage::Persistent(index) => index
252                .sequences
253                .iter()
254                .map(|sequence| sequence.join("/"))
255                .collect(),
256        };
257        paths.into_iter().collect()
258    }
259}
260
261impl DurablePathIndex {
262    fn lookup(&self, sequence: &[String]) -> GraphStoreResult<Pairs> {
263        struct ReadCheckpoint(Option<Arc<dyn PersistentStorageBackend>>);
264        impl Drop for ReadCheckpoint {
265            fn drop(&mut self) {
266                if let Some(backend) = &self.0 {
267                    let _ = backend.rollback_transaction();
268                }
269            }
270        }
271        let _read = self.read_gate.lock();
272        if self.backend.in_transaction() {
273            return self.lookup_in_snapshot(&self.catalog, Arc::clone(&self.backend), sequence);
274        }
275        // Own completion independently while retaining this handle's selected view and original participant, including an already retained reader.
276        let session = if self.backend.transaction_model().is_versioned() {
277            self.backend.open_retained_read_session(
278                &self.backend.write_cancellation().unwrap_or_default(),
279            )?
280        } else if self.backend.supports_concurrent_pinned_read_and_write() {
281            self.backend.open_session()?
282        } else {
283            // Single-session providers are supported too; their caller owns
284            // session serialization, as with direct GraphStore queries.
285            uqa_storage::PersistentStorageSession::new(
286                Arc::clone(&self.catalog),
287                Arc::clone(&self.backend),
288            )
289        };
290        let catalog = session.catalog;
291        let backend = session.backend;
292        backend.begin_read_transaction()?;
293        let mut checkpoint = ReadCheckpoint(Some(Arc::clone(&backend)));
294        let result = self.lookup_in_snapshot(&catalog, Arc::clone(&backend), sequence);
295        backend.rollback_transaction()?;
296        checkpoint.0 = None;
297        result
298    }
299
300    fn lookup_in_snapshot(
301        &self,
302        catalog: &Arc<dyn CatalogFacade>,
303        backend: Arc<dyn PersistentStorageBackend>,
304        sequence: &[String],
305    ) -> GraphStoreResult<Pairs> {
306        let store = observed_store(Arc::clone(catalog), backend)?;
307        store.observe_definition(
308            uqa_storage::catalog::graph_observations::GraphDefinitionKind::PathIndex,
309            Some(&self.key),
310        )?;
311        let definition = catalog
312            .load_path_indexes()?
313            .into_iter()
314            .find_map(|(key, json)| (key == self.key).then_some(json));
315        if definition.as_deref() != Some(self.definition.as_str()) {
316            return Err(GraphStoreError::InvalidQuery(format!(
317                "path index {:?} was dropped or redefined",
318                self.key
319            )));
320        }
321        let mut result = Pairs::new();
322        if catalog.path_index_data_is_current(&self.key, &self.definition)? {
323            store.observe_cached_paths(&self.graph, sequence)?;
324            let sequence_key =
325                serde_json::to_string(sequence).map_err(|error| json_error(&error))?;
326            let mut after = None;
327            loop {
328                let pairs = catalog.path_index_pairs(&self.key, &sequence_key, after, 256)?;
329                if pairs.is_empty() {
330                    break;
331                }
332                after = pairs.last().copied();
333                result.extend(pairs);
334            }
335        } else {
336            // A legacy or invalidated index is not a valid access path.
337            // Evaluate only this requested sequence in the current read
338            // snapshot; do not rebuild/retain a whole index or write on read.
339            visit_pairs(&store, &self.graph, sequence, |pair| {
340                result.insert(pair);
341                Ok(())
342            })?;
343        }
344        Ok(result)
345    }
346}
347
348fn visit_pairs<G: GraphStore>(
349    store: &G,
350    graph: &str,
351    sequence: &[String],
352    mut visit: impl FnMut((u64, u64)) -> GraphStoreResult<()>,
353) -> GraphStoreResult<()> {
354    let mut after = None;
355    loop {
356        let ids = store.vertex_id_page(graph, after, 256)?;
357        if ids.is_empty() {
358            break;
359        }
360        after = ids.last().copied();
361        for start in ids {
362            let mut frontier = BTreeSet::from([start]);
363            for label in sequence {
364                let mut next = BTreeSet::new();
365                for vertex in frontier {
366                    next.extend(store.neighbors(vertex, Some(label), Direction::Out, graph)?);
367                }
368                frontier = next;
369                if frontier.is_empty() {
370                    break;
371                }
372            }
373            for end in frontier {
374                visit((start, end))?;
375            }
376        }
377    }
378    Ok(())
379}