1use crate::capabilities::{
3 context::{ContextSeed, ContextSession},
4 excerpts::Excerpt,
5 relationships::{RelationshipSeed, RelationshipSession},
6 search::SearchSession,
7};
8use crate::graph::query_snapshot::QuerySnapshot;
9use crate::{Cursor, EngineError, Search, SnapshotId};
10use serde::Serialize;
11use std::collections::{BTreeMap, HashMap};
12use std::hash::BuildHasher;
13use std::sync::Arc;
14use std::time::{Duration, Instant};
15
16#[derive(Debug, Clone, Copy, Serialize, serde::Deserialize, PartialEq, Eq)]
17#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
18pub struct QueryLimits {
19 pub max_queries: usize,
20 pub max_query_bytes: usize,
21 pub max_total_bytes: usize,
22 pub lifetime_seconds: u64,
23}
24impl Default for QueryLimits {
25 fn default() -> Self {
26 Self {
27 max_queries: 16,
28 max_query_bytes: 32 * 1024 * 1024,
29 max_total_bytes: 128 * 1024 * 1024,
30 lifetime_seconds: 600,
31 }
32 }
33}
34
35#[derive(Debug, Serialize)]
36pub(crate) enum QueryData {
37 Search(Search),
38 Context(ContextSeed),
39 Relationships(RelationshipSeed),
40}
41#[derive(Debug, Clone, Serialize)]
42pub(crate) enum Checkpoint {
43 Search(SearchSession),
44 Context(ContextSession),
45 Relationships(RelationshipSession),
46 Excerpt(Excerpt),
47}
48impl Checkpoint {
49 fn kind(&self) -> &'static str {
50 if matches!(self, Self::Excerpt(_)) {
51 "e"
52 } else {
53 "q"
54 }
55 }
56}
57#[derive(Debug, Serialize)]
58pub(crate) struct QueryRoot {
59 pub snapshot: QuerySnapshot,
60 pub identity: SnapshotId,
61 pub data: QueryData,
62 pub revision: u64,
63 #[serde(skip)]
64 pub created: Instant,
65}
66#[derive(Clone)]
67pub(crate) struct Lease {
68 pub id: u64,
69 pub root: Arc<QueryRoot>,
70 pub checkpoint: Checkpoint,
71}
72struct StoredQuery {
73 root: Arc<QueryRoot>,
74 checkpoints: BTreeMap<Cursor, Checkpoint>,
75 created: Instant,
76 used: Instant,
77 bytes: usize,
78}
79pub(crate) struct QueryStore {
80 nonce: String,
81 next: u64,
82 roots: HashMap<u64, StoredQuery>,
83 limits: QueryLimits,
84}
85impl Default for QueryStore {
86 fn default() -> Self {
87 Self {
88 nonce: format!(
89 "{:016x}",
90 std::collections::hash_map::RandomState::new().hash_one("vvv query store")
91 ),
92 next: 0,
93 roots: HashMap::new(),
94 limits: QueryLimits::default(),
95 }
96 }
97}
98impl QueryStore {
99 pub(crate) fn weight(value: &impl Serialize) -> usize {
102 serde_json::to_vec(value)
103 .expect("query state serializes")
104 .len()
105 .saturating_mul(4)
106 .saturating_add(1024)
107 }
108 pub(crate) fn allocate(&mut self) -> u64 {
109 self.next += 1;
110 self.next
111 }
112 pub(crate) fn cursor(&self, id: u64, checkpoint: &Checkpoint) -> Cursor {
113 let digest = blake3::hash(&serde_json::to_vec(checkpoint).expect("checkpoint serializes"));
114 Cursor(format!(
115 "v1.{}.{id:016x}.{}.{}",
116 self.nonce,
117 checkpoint.kind(),
118 digest.to_hex()
119 ))
120 }
121 pub(crate) fn lease(
122 &mut self,
123 cursor: &Cursor,
124 excerpt: bool,
125 revision: u64,
126 now: Instant,
127 ) -> Result<Lease, EngineError> {
128 let parts: Vec<_> = cursor.0.split('.').collect();
129 if parts.len() != 5
130 || parts[0] != "v1"
131 || parts[1].len() != 16
132 || parts[2].len() != 16
133 || parts[4].len() != 64
134 || ![parts[1], parts[2], parts[4]]
135 .iter()
136 .all(|s| s.bytes().all(|c| c.is_ascii_hexdigit()))
137 || !["q", "e"].contains(&parts[3])
138 {
139 return Err(EngineError::InvalidCursor);
140 }
141 if (parts[3] == "e") != excerpt {
142 return Err(EngineError::InvalidCursor);
143 }
144 if parts[1] != self.nonce {
145 return Err(EngineError::CursorExpired);
146 }
147 let id = u64::from_str_radix(parts[2], 16).map_err(|_| EngineError::InvalidCursor)?;
148 self.expire(now);
149 let root = self.roots.get_mut(&id).ok_or(EngineError::CursorExpired)?;
150 if root.root.revision != revision {
151 self.roots.remove(&id);
152 return Err(EngineError::StaleQuery);
153 }
154 let checkpoint = root
155 .checkpoints
156 .get(cursor)
157 .ok_or(EngineError::InvalidCursor)?
158 .clone();
159 root.used = now;
160 Ok(Lease {
161 id,
162 root: root.root.clone(),
163 checkpoint,
164 })
165 }
166 fn expire(&mut self, now: Instant) {
167 let ttl = Duration::from_secs(self.limits.lifetime_seconds);
168 self.roots
169 .retain(|_, root| now.saturating_duration_since(root.created) < ttl);
170 }
171 pub(crate) fn invalidate(&mut self, id: u64) {
172 self.roots.remove(&id);
173 }
174 pub(crate) fn publish(
175 &mut self,
176 id: u64,
177 root: Arc<QueryRoot>,
178 checkpoints: Vec<Checkpoint>,
179 now: Instant,
180 ) -> Result<(), EngineError> {
181 if now.saturating_duration_since(root.created)
182 >= Duration::from_secs(self.limits.lifetime_seconds)
183 {
184 self.invalidate(id);
185 return Err(EngineError::CursorExpired);
186 }
187 if checkpoints.is_empty() {
188 return Ok(());
189 }
190 self.expire(now);
191 let existing = self.roots.get(&id);
192 let mut additions = BTreeMap::new();
193 for checkpoint in checkpoints {
194 let cursor = self.cursor(id, &checkpoint);
195 if existing.is_none_or(|q| !q.checkpoints.contains_key(&cursor)) {
196 additions.insert(cursor, checkpoint);
197 }
198 }
199 let old_bytes = existing.map_or(0, |q| q.bytes);
200 let added_bytes = additions
201 .iter()
202 .map(|(k, v)| Self::weight(&(k, v)))
203 .sum::<usize>()
204 + if existing.is_none() {
205 Self::weight(root.as_ref())
206 } else {
207 0
208 };
209 let bytes = old_bytes.saturating_add(added_bytes);
210 if bytes > self.limits.max_query_bytes || bytes > self.limits.max_total_bytes {
211 return Err(EngineError::RetentionLimit);
212 }
213 while self
214 .roots
215 .values()
216 .map(|q| q.bytes)
217 .sum::<usize>()
218 .saturating_add(added_bytes)
219 > self.limits.max_total_bytes
220 || (!self.roots.contains_key(&id) && self.roots.len() >= self.limits.max_queries)
221 {
222 let oldest = self
223 .roots
224 .iter()
225 .filter(|(other, _)| **other != id)
226 .min_by_key(|(key, q)| (q.used, **key))
227 .map(|(key, _)| *key)
228 .ok_or(EngineError::RetentionLimit)?;
229 self.roots.remove(&oldest);
230 }
231 let entry = self.roots.entry(id).or_insert_with(|| StoredQuery {
232 created: root.created,
233 root,
234 checkpoints: BTreeMap::new(),
235 used: now,
236 bytes: 0,
237 });
238 entry.checkpoints.extend(additions);
239 entry.bytes = bytes;
240 entry.used = now;
241 Ok(())
242 }
243}
244
245#[cfg(test)]
246mod tests {
247 use super::*;
248 struct Fixture {
249 store: QueryStore,
250 root: Arc<QueryRoot>,
251 now: Instant,
252 }
253 impl Fixture {
254 fn new() -> Self {
255 let now = Instant::now();
256 let engine = crate::Engine::new(
257 crate::Workspace::new("/ws", Arc::new(crate::MemoryVfs::new())),
258 crate::Languages::new(),
259 );
260 let (_, snapshot) = QuerySnapshot::capture(&engine).unwrap();
261 let root = Arc::new(QueryRoot {
262 snapshot,
263 identity: crate::ContentId::of("query").into(),
264 data: QueryData::Search(Search {
265 scope: Default::default(),
266 query: crate::Query::pattern("x"),
267 matches: vec![],
268 skipped: vec![],
269 }),
270 revision: 0,
271 created: now,
272 });
273 Self {
274 store: QueryStore::default(),
275 root,
276 now,
277 }
278 }
279 fn add(&mut self) -> (u64, Cursor) {
280 let id = self.store.allocate();
281 let checkpoint = Checkpoint::Search(SearchSession { next: 1 });
282 let token = self.store.cursor(id, &checkpoint);
283 self.store
284 .publish(id, self.root.clone(), vec![checkpoint], self.now)
285 .unwrap();
286 (id, token)
287 }
288 }
289 #[test]
290 fn fixed_lifetime_is_not_extended_by_reads_or_checkpoint_publication() {
291 let mut f = Fixture::new();
292 let (id, token) = f.add();
293 let later = f.now + Duration::from_secs(599);
294 f.store.lease(&token, false, 0, later).unwrap();
295 f.store
296 .publish(
297 id,
298 f.root.clone(),
299 vec![Checkpoint::Search(SearchSession { next: 2 })],
300 later,
301 )
302 .unwrap();
303 let expired = f.now + Duration::from_secs(600);
304 assert!(matches!(
305 f.store.lease(&token, false, 0, expired),
306 Err(EngineError::CursorExpired)
307 ));
308 assert!(matches!(
309 f.store.publish(
310 id,
311 f.root,
312 vec![Checkpoint::Search(SearchSession { next: 3 })],
313 expired
314 ),
315 Err(EngineError::CursorExpired)
316 ));
317 }
318 #[test]
319 fn lru_evicts_whole_roots_and_replay_does_not_grow_retention() {
320 let mut f = Fixture::new();
321 f.store.limits.max_queries = 2;
322 let (id, token) = f.add();
323 let (_, old) = f.add();
324 let later = f.now + Duration::from_secs(1);
325 f.store.lease(&token, false, 0, later).unwrap();
326 let before = f.store.roots[&id].bytes;
327 f.store
328 .publish(
329 id,
330 f.root.clone(),
331 vec![Checkpoint::Search(SearchSession { next: 1 })],
332 later,
333 )
334 .unwrap();
335 assert_eq!(f.store.roots[&id].bytes, before);
336 f.add();
337 assert!(matches!(
338 f.store.lease(&old, false, 0, later),
339 Err(EngineError::CursorExpired)
340 ));
341 f.store.lease(&token, false, 0, later).unwrap();
342 }
343 #[test]
344 fn failed_admission_keeps_existing_checkpoint_and_bounds_total_bytes() {
345 let mut f = Fixture::new();
346 let (id, token) = f.add();
347 let retained = f.store.roots[&id].bytes;
348 f.store.limits.max_query_bytes = retained;
349 assert!(matches!(
350 f.store.publish(
351 id,
352 f.root.clone(),
353 vec![Checkpoint::Search(SearchSession { next: 2 })],
354 f.now
355 ),
356 Err(EngineError::RetentionLimit)
357 ));
358 assert_eq!(f.store.roots[&id].bytes, retained);
359 f.store.lease(&token, false, 0, f.now).unwrap();
360 f.store.limits.max_total_bytes = retained;
361 let (_, replacement) = f.add();
362 assert!(matches!(
363 f.store.lease(&token, false, 0, f.now),
364 Err(EngineError::CursorExpired)
365 ));
366 f.store.lease(&replacement, false, 0, f.now).unwrap();
367 assert!(f.store.roots.values().map(|q| q.bytes).sum::<usize>() <= retained);
368 }
369}