Skip to main content

qualia_core_db/query/
graph_index.rs

1//! Revision-cached graph index — the per-cell index lifecycle (#22 step 3).
2//!
3//! Building a `QuinIndex` over the daemon-graph snapshot on every resolve would be O(n)
4//! per call. Instead we memoize it by `daemon_graph::graph_revision()`: the index is
5//! rebuilt LAZILY only when the graph has actually changed, so resolution is O(1)
6//! amortized. The cache is host-side (separate from the 42 MB SlgArena).
7//!
8//! "Per-cell" in the Fractal-Shard model means one cache per 512 MB cell; for the single
9//! daemon graph today this is that one cache. Streaming a huge graph via BIDX/demand-
10//! paging — so the index need not copy the whole snapshot — remains future work.
11
12#[cfg(not(target_arch = "wasm32"))]
13use crate::indexing::QuinIndex;
14use std::sync::{Mutex, RwLock};
15
16/// Memoizes a value `T` by a monotonically-advancing `revision`, rebuilding via `build`
17/// only when the supplied revision exceeds the cached one.
18///
19/// Uses a dedicated single-flight `build_lock` alongside the `RwLock` storage so:
20/// 1. Concurrent callers requesting a newer revision coalesce into a single `build()`
21///    invocation instead of triggering an $N$-thread rebuild stampede.
22/// 2. Existing readers can continue reading the previous snapshot while the new revision
23///    is being built, blocking only for the $O(1)$ pointer swap.
24/// 3. Monotonic revision checks prevent a stale revision from overwriting a newer one.
25pub struct RevisionCache<T> {
26    inner: RwLock<Option<(u64, T)>>,
27    build_lock: Mutex<()>,
28}
29
30impl<T> RevisionCache<T> {
31    /// Creates a default `RevisionCache`.
32    pub const fn new() -> Self {
33        Self {
34            inner: RwLock::new(None),
35            build_lock: Mutex::new(()),
36        }
37    }
38
39    /// Returns the currently cached revision, or `None` if the cache is empty.
40    pub fn current_revision(&self) -> Option<u64> {
41        let guard = self.inner.read().unwrap_or_else(|e| e.into_inner());
42        guard.as_ref().map(|(rev, _)| *rev)
43    }
44
45    /// Clears the cached value so the next [`Self::with`] call rebuilds it.
46    pub fn invalidate(&self) {
47        let _build_guard = self.build_lock.lock().unwrap_or_else(|e| e.into_inner());
48        let mut w = self.inner.write().unwrap_or_else(|e| e.into_inner());
49        *w = None;
50    }
51
52    /// Run `f` against the value cached at `revision` (or newer), building it via `build`
53    /// first if the cache is empty or at a lower revision. `build` runs at most once per
54    /// distinct monotonic revision advance, and only when a caller actually needs the value.
55    pub fn with<R>(&self, revision: u64, build: impl FnOnce() -> T, f: impl FnOnce(&T) -> R) -> R {
56        // Fast path: cache present and at or ahead of `revision`.
57        {
58            let guard = self.inner.read().unwrap_or_else(|e| e.into_inner());
59            if let Some((rev, value)) = guard.as_ref() {
60                if *rev >= revision {
61                    return f(value);
62                }
63            }
64        }
65        // Slow path: serialize rebuilds with `build_lock` and double-check `inner`.
66        {
67            let _build_guard = self.build_lock.lock().unwrap_or_else(|e| e.into_inner());
68            let needs_build = {
69                let guard = self.inner.read().unwrap_or_else(|e| e.into_inner());
70                guard.as_ref().map_or(true, |(rev, _)| *rev < revision)
71            };
72            if needs_build {
73                let value = build();
74                let mut w = self.inner.write().unwrap_or_else(|e| e.into_inner());
75                if w.as_ref().map_or(true, |(cur_rev, _)| revision >= *cur_rev) {
76                    *w = Some((revision, value));
77                }
78            }
79        }
80        let guard = self.inner.read().unwrap_or_else(|e| e.into_inner());
81        let (_, value) = guard.as_ref().expect("cache just populated");
82        f(value)
83    }
84}
85
86impl<T> Default for RevisionCache<T> {
87    fn default() -> Self {
88        Self::new()
89    }
90}
91
92#[cfg(not(target_arch = "wasm32"))]
93static GRAPH_INDEX: RevisionCache<QuinIndex> = RevisionCache::new();
94
95/// Run `f` against a `QuinIndex` over the current daemon graph, rebuilt only when the
96/// graph revision has changed since the last build. This is what `graph_resolve` (and
97/// other index consumers) route through, so a burst of resolves between graph changes
98/// shares a single O(n) build.
99// Routes through `daemon_graph` (the native daemon's in-memory graph), which does not exist on
100// wasm32; the only caller (mcp_tool_impls) is native-only too.
101#[cfg(not(target_arch = "wasm32"))]
102/// Builder: `graph-index`.
103pub fn with_graph_index<R>(f: impl FnOnce(&QuinIndex) -> R) -> R {
104    let revision = crate::daemon_graph::graph_revision();
105    GRAPH_INDEX.with(
106        revision,
107        || {
108            let guard = crate::daemon_graph::graph_read_guard();
109            QuinIndex::from_slice(guard.as_slice())
110        },
111        f,
112    )
113}
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118    use std::sync::atomic::{AtomicUsize, Ordering};
119    use std::sync::{Arc, Barrier};
120
121    #[test]
122    fn rebuilds_only_on_revision_change() {
123        let cache: RevisionCache<usize> = RevisionCache::new();
124        let builds = AtomicUsize::new(0);
125        assert_eq!(cache.current_revision(), None);
126
127        // First touch at rev 1 builds.
128        let v = cache.with(
129            1,
130            || {
131                builds.fetch_add(1, Ordering::SeqCst);
132                42
133            },
134            |v| *v,
135        );
136        assert_eq!(v, 42);
137        assert_eq!(cache.current_revision(), Some(1));
138        // Same rev: served from cache, no rebuild.
139        cache.with(
140            1,
141            || {
142                builds.fetch_add(1, Ordering::SeqCst);
143                0
144            },
145            |_| (),
146        );
147        assert_eq!(
148            builds.load(Ordering::SeqCst),
149            1,
150            "same revision must not rebuild"
151        );
152
153        // New rev: rebuild.
154        cache.with(
155            2,
156            || {
157                builds.fetch_add(1, Ordering::SeqCst);
158                99
159            },
160            |_| (),
161        );
162        assert_eq!(
163            builds.load(Ordering::SeqCst),
164            2,
165            "changed revision must rebuild"
166        );
167        assert_eq!(cache.current_revision(), Some(2));
168        // And stays cached at the new rev.
169        cache.with(
170            2,
171            || {
172                builds.fetch_add(1, Ordering::SeqCst);
173                0
174            },
175            |_| (),
176        );
177        assert_eq!(builds.load(Ordering::SeqCst), 2);
178    }
179
180    #[test]
181    fn monotonic_revision_prevents_stale_overwrite() {
182        let cache: RevisionCache<usize> = RevisionCache::new();
183        let builds = AtomicUsize::new(0);
184
185        let v2 = cache.with(
186            2,
187            || {
188                builds.fetch_add(1, Ordering::SeqCst);
189                200
190            },
191            |v| *v,
192        );
193        assert_eq!(v2, 200);
194        assert_eq!(cache.current_revision(), Some(2));
195
196        // Requesting a stale revision (1 < 2) must neither rebuild nor overwrite revision 2.
197        let v_stale = cache.with(
198            1,
199            || {
200                builds.fetch_add(1, Ordering::SeqCst);
201                100
202            },
203            |v| *v,
204        );
205        assert_eq!(v_stale, 200);
206        assert_eq!(builds.load(Ordering::SeqCst), 1);
207        assert_eq!(cache.current_revision(), Some(2));
208
209        // Explicit invalidation resets the cache so revision 1 can be built fresh if needed.
210        cache.invalidate();
211        assert_eq!(cache.current_revision(), None);
212        let v1 = cache.with(
213            1,
214            || {
215                builds.fetch_add(1, Ordering::SeqCst);
216                100
217            },
218            |v| *v,
219        );
220        assert_eq!(v1, 100);
221        assert_eq!(cache.current_revision(), Some(1));
222    }
223
224    #[test]
225    fn single_flight_deduplicates_concurrent_rebuilds() {
226        let cache = Arc::new(RevisionCache::<usize>::new());
227        let builds = Arc::new(AtomicUsize::new(0));
228        let barrier = Arc::new(Barrier::new(8));
229
230        let mut handles = Vec::with_capacity(8);
231        for _ in 0..8 {
232            let cache = Arc::clone(&cache);
233            let builds = Arc::clone(&builds);
234            let barrier = Arc::clone(&barrier);
235            handles.push(std::thread::spawn(move || {
236                barrier.wait();
237                cache.with(
238                    5,
239                    || {
240                        builds.fetch_add(1, Ordering::SeqCst);
241                        555
242                    },
243                    |v| *v,
244                )
245            }));
246        }
247
248        for h in handles {
249            assert_eq!(h.join().unwrap(), 555);
250        }
251        assert_eq!(
252            builds.load(Ordering::SeqCst),
253            1,
254            "8 concurrent threads requesting revision 5 must invoke build() exactly once"
255        );
256        assert_eq!(cache.current_revision(), Some(5));
257    }
258
259    #[test]
260    fn reentrant_with_inside_callback_does_not_deadlock() {
261        let cache: RevisionCache<usize> = RevisionCache::new();
262        let outer = cache.with(
263            3,
264            || 30,
265            |v| {
266                let inner = cache.with(3, || 999, |inner_v| *inner_v + 7);
267                *v + inner
268            },
269        );
270        assert_eq!(outer, 67);
271    }
272}