1use 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#[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 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 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 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 #[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 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 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 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}