Skip to main content

durable/
memory.rs

1//! In-memory reference backend, a port of upstream `storage/memory.ts`.
2
3use crate::{
4    ConversationId, ConversationQuery, ConversationRecord, Cursor, DocumentAddress, DocumentContent, DocumentCreate,
5    DocumentId, DocumentPoint, DocumentQuery, DocumentRecord, DocumentScope, EntryId, EntryQuery, EntryRecord,
6    MAX_SAFE_ID, Page, Result, ScanOrder, ScanStart, Seq, Storage, StorageWrite, StoredDocument, StoredEntry,
7    SubmissionId, SubmissionQuery, SubmissionRecord, SubmissionStatus, TaskId, TaskQuery, TaskRecord, TaskStatus,
8    cursor_after, failed, request, scan_start,
9};
10use crate::{DocumentAction, Table, check_global_ids, document_actions, page};
11use chord_delta::{Op, apply_immutable_batches};
12use serde_json::Value;
13use std::collections::{BTreeSet, HashMap};
14use std::ops::Bound::{Excluded, Included, Unbounded};
15
16struct Revision {
17    seq: Seq,
18    content: DocumentContent,
19}
20
21struct StoredDoc {
22    record: DocumentRecord,
23    revisions: Vec<Revision>,
24}
25
26#[derive(Default)]
27struct AddressIndex {
28    ids: BTreeSet<u64>,
29    current: Option<u64>,
30}
31
32type AddressKey = (String, DocumentScope, Option<String>);
33
34fn address_key(kind: &str, scope: DocumentScope, key: Option<&str>) -> AddressKey {
35    (kind.to_owned(), scope, key.map(str::to_owned))
36}
37
38fn create_address(create: &DocumentCreate) -> AddressKey {
39    address_key(&create.kind, create.scope, create.key.as_deref())
40}
41
42/// Sorted IDs in scan order, after the cursor's ID when there is one.
43fn scan_ids(ids: &BTreeSet<u64>, start: ScanStart) -> Box<dyn Iterator<Item = u64> + '_> {
44    let after = start.after.map(|after| u64::try_from(after).ok());
45    match (start.order, after) {
46        (ScanOrder::Ascending, None | Some(None)) => Box::new(ids.iter().copied()),
47        (ScanOrder::Ascending, Some(Some(after))) => Box::new(ids.range((Excluded(after), Unbounded)).copied()),
48        (ScanOrder::Descending, None) => Box::new(ids.iter().rev().copied()),
49        (ScanOrder::Descending, Some(None)) => Box::new(std::iter::empty()),
50        (ScanOrder::Descending, Some(Some(after))) => Box::new(ids.range(..after).rev().copied()),
51    }
52}
53
54/// IDs in `ids` within the inclusive signed bounds, ascending.
55fn bounded(ids: &BTreeSet<u64>, min: i64, max: i64) -> impl DoubleEndedIterator<Item = u64> + '_ {
56    let empty = max < 0 || min > max;
57    let low = if empty { 1 } else { u64::try_from(min).unwrap_or(0) };
58    let high = if empty { 0 } else { u64::try_from(max).unwrap_or(0) };
59    ids.range((Included(low), Included(high.max(low.saturating_sub(1)))))
60        .copied()
61        .filter(move |_| !empty)
62}
63
64fn insert_index<K: std::hash::Hash + Eq>(index: &mut HashMap<K, BTreeSet<u64>>, key: K, id: u64) {
65    index.entry(key).or_default().insert(id);
66}
67
68/// A validated commit whose writes have their document copies resolved to creations.
69pub struct PreparedCommit {
70    pub seq: Seq,
71    /// The writes as they will be applied: no `DocumentCopy` remains.
72    pub writes: Vec<StorageWrite>,
73    actions: Vec<(u64, DocumentAction)>,
74}
75
76/// Sees each commit as it will be applied, before it is: an error fails the commit unapplied. A backend that keeps
77/// its records elsewhere persists them here (session-core's journal; a replay log).
78pub type CommitSink = Box<dyn FnMut(&PreparedCommit) -> Result<()> + Send>;
79
80/// Detached in-memory reference implementation of [`Storage`]. Reads return owned copies.
81pub struct MemoryStorage {
82    record_types: HashMap<u64, Table>,
83    conversations: HashMap<u64, ConversationRecord>,
84    conversation_ids: BTreeSet<u64>,
85    conversations_by_owner_conversation: HashMap<u64, BTreeSet<u64>>,
86    conversations_by_owner_task: HashMap<u64, BTreeSet<u64>>,
87    entries: HashMap<u64, (EntryRecord, Seq)>,
88    entry_ids: HashMap<u64, BTreeSet<u64>>,
89    head_entry_ids: HashMap<u64, BTreeSet<u64>>,
90    tasks: HashMap<u64, TaskRecord>,
91    task_ids: BTreeSet<u64>,
92    task_ids_by_status: HashMap<TaskStatus, BTreeSet<u64>>,
93    submissions: HashMap<u64, SubmissionRecord>,
94    submission_ids: BTreeSet<u64>,
95    submission_ids_by_status: HashMap<SubmissionStatus, BTreeSet<u64>>,
96    submission_ids_by_request: HashMap<(u64, String), u64>,
97    documents: HashMap<u64, StoredDoc>,
98    document_addresses: HashMap<AddressKey, AddressIndex>,
99    document_ids_by_scope: HashMap<DocumentScope, BTreeSet<u64>>,
100    next_id: u64,
101    next_seq: u64,
102    closed: bool,
103    sink: Option<CommitSink>,
104}
105
106impl Default for MemoryStorage {
107    fn default() -> Self {
108        Self::new()
109    }
110}
111
112impl MemoryStorage {
113    pub fn new() -> Self {
114        MemoryStorage {
115            record_types: HashMap::new(),
116            conversations: HashMap::new(),
117            conversation_ids: BTreeSet::new(),
118            conversations_by_owner_conversation: HashMap::new(),
119            conversations_by_owner_task: HashMap::new(),
120            entries: HashMap::new(),
121            entry_ids: HashMap::new(),
122            head_entry_ids: HashMap::new(),
123            tasks: HashMap::new(),
124            task_ids: BTreeSet::new(),
125            task_ids_by_status: HashMap::new(),
126            submissions: HashMap::new(),
127            submission_ids: BTreeSet::new(),
128            submission_ids_by_status: HashMap::new(),
129            submission_ids_by_request: HashMap::new(),
130            documents: HashMap::new(),
131            document_addresses: HashMap::new(),
132            document_ids_by_scope: HashMap::new(),
133            next_id: 2,
134            next_seq: 1,
135            closed: false,
136            sink: None,
137        }
138    }
139
140    /// Every later commit goes through `sink` before it is applied.
141    pub fn with_commit_sink(mut self, sink: CommitSink) -> Self {
142        self.sink = Some(sink);
143        self
144    }
145
146    /// Validate one commit and resolve its document copies without changing observable state. `seq` defaults to the
147    /// next sequence; a replaying caller (JSONL recovery) supplies the recorded one, which must not go backwards.
148    pub fn prepare_commit(&self, mut writes: Vec<StorageWrite>, seq: Option<Seq>) -> Result<PreparedCommit> {
149        self.assert_open()?;
150        let seq = seq.unwrap_or(Seq(self.next_seq));
151        if seq.0 < self.next_seq || seq.0 > MAX_SAFE_ID {
152            return failed(format!("Commit sequence {} does not strictly increase", seq.0));
153        }
154        self.resolve_document_copies(&mut writes)?;
155        check_global_ids(&writes, |id| Ok(self.record_types.get(&id).copied()))?;
156        let actions = document_actions(&writes)?;
157        self.check_document_actions(&actions)?;
158        Ok(PreparedCommit { seq, writes, actions })
159    }
160
161    /// Apply a commit prepared against the current state; nothing in it can fail.
162    pub fn apply_commit(&mut self, prepared: PreparedCommit) -> Seq {
163        let PreparedCommit { seq, writes, actions } = prepared;
164        for write in writes {
165            self.apply_write(write, seq);
166        }
167        self.apply_document_actions(actions, seq);
168        self.next_seq = seq.0 + 1;
169        seq
170    }
171
172    fn assert_open(&self) -> Result<()> {
173        if self.closed {
174            failed("MemoryStorage is closed")
175        } else {
176            Ok(())
177        }
178    }
179
180    fn materialize(&self, id: DocumentId, at: DocumentPoint) -> Result<Option<StoredDocument>> {
181        let Some(stored) = self.documents.get(&id.0) else {
182            return Ok(None);
183        };
184        if at != DocumentPoint::Current && stored.record.identity.is_current_only() {
185            return request(format!("Document {} does not retain historical content", id.0));
186        }
187        if !stored.record.is_alive_at(at) {
188            return Ok(None);
189        }
190        let revisions = match at {
191            DocumentPoint::Current => &stored.revisions[..],
192            DocumentPoint::At(seq) => &stored.revisions[..stored.revisions.partition_point(|r| r.seq <= seq)],
193        };
194        let Some(base_index) = revisions
195            .iter()
196            .rposition(|r| matches!(r.content, DocumentContent::Base { .. }))
197        else {
198            return failed(format!("Document {} is missing a required base", id.0));
199        };
200        let DocumentContent::Base { version, value } = &revisions[base_index].content else {
201            unreachable!()
202        };
203        let mut batches: Vec<&[Op]> = Vec::new();
204        for revision in &revisions[base_index + 1..] {
205            match &revision.content {
206                DocumentContent::Delta { version: v, ops } if v == version => batches.push(ops),
207                _ => {
208                    return failed(format!(
209                        "Document {} crosses a stored version boundary without a base",
210                        id.0
211                    ));
212                }
213            }
214        }
215        let value = match apply_immutable_batches(&Value::Object(value.clone()), batches) {
216            Ok(Value::Object(value)) => value,
217            Ok(_) => return failed(format!("Document {} is not an object", id.0)),
218            Err(error) => return failed(error.to_string()),
219        };
220        Ok(Some(StoredDocument {
221            record: stored.record.clone(),
222            version: *version,
223            value,
224            deltas_since_base: revisions.len() - base_index - 1,
225        }))
226    }
227
228    fn check_conversation(&self, id: ConversationId) -> Result<()> {
229        if self.conversations.contains_key(&id.0) {
230            Ok(())
231        } else {
232            request(format!("Unknown conversation: {}", id.0))
233        }
234    }
235
236    /// Visible entries newest first through the fork chain, at most `take` of them.
237    fn visible_descending(&self, id: ConversationId, min: i64, max: i64, take: usize) -> Result<Vec<&EntryRecord>> {
238        self.check_conversation(id)?;
239        let mut out = Vec::new();
240        let (mut current, mut upper) = (id.0, max);
241        loop {
242            if let Some(ids) = self.entry_ids.get(&current) {
243                for entry in bounded(ids, min, upper).rev() {
244                    if out.len() == take {
245                        return Ok(out);
246                    }
247                    out.push(&self.entries[&entry].0);
248                }
249            }
250            let Some(parent) = self.conversations[&current].parent else {
251                break;
252            };
253            upper = upper.min(parent.at.0 as i64);
254            if upper < min {
255                break;
256            }
257            current = parent.conversation_id.0;
258        }
259        Ok(out)
260    }
261
262    /// Visible entries oldest first: the fork chain's segments from the root conversation forward.
263    fn visible_ascending(&self, id: ConversationId, min: i64, max: i64, take: usize) -> Result<Vec<&EntryRecord>> {
264        self.check_conversation(id)?;
265        let mut segments = Vec::new();
266        let (mut current, mut upper) = (id.0, max);
267        loop {
268            segments.push((current, upper));
269            let Some(parent) = self.conversations[&current].parent else {
270                break;
271            };
272            upper = upper.min(parent.at.0 as i64);
273            if upper < min {
274                break;
275            }
276            current = parent.conversation_id.0;
277        }
278        let mut out = Vec::new();
279        for (conversation, upper) in segments.into_iter().rev() {
280            let Some(ids) = self.entry_ids.get(&conversation) else {
281                continue;
282            };
283            for entry in bounded(ids, min, upper) {
284                if out.len() == take {
285                    return Ok(out);
286                }
287                out.push(&self.entries[&entry].0);
288            }
289        }
290        Ok(out)
291    }
292
293    /// Replace each `document.copy` with a `document.create` of the source's materialized base.
294    fn resolve_document_copies(&self, writes: &mut [StorageWrite]) -> Result<()> {
295        let changed: BTreeSet<u64> = writes
296            .iter()
297            .filter_map(|write| match write {
298                StorageWrite::DocumentCreate { record, .. } | StorageWrite::DocumentCopy { record, .. } => {
299                    Some(record.id.0)
300                }
301                StorageWrite::DocumentChange { id, .. } | StorageWrite::DocumentRetire { id } => Some(id.0),
302                _ => None,
303            })
304            .collect();
305        for write in writes.iter_mut() {
306            let StorageWrite::DocumentCopy { record, source } = write else {
307                continue;
308            };
309            let resolved = (|| -> Result<DocumentContent> {
310                if changed.contains(&source.id.0) {
311                    return failed(format!(
312                        "Fork source document {} is changed in the copy batch",
313                        source.id.0
314                    ));
315                }
316                let Some(stored) = self.materialize(source.id, source.at)? else {
317                    return failed(format!("Fork source document {} cannot be read", source.id.0));
318                };
319                let from = &stored.record.identity;
320                if !matches!(from.scope, DocumentScope::Conversation { .. })
321                    || !matches!(record.scope, DocumentScope::Conversation { .. })
322                    || from.kind != record.kind
323                    || from.key != record.key
324                    || from.history != record.history
325                    || from.fork != record.fork
326                {
327                    return failed(format!(
328                        "Fork source document {} does not match the copied record",
329                        source.id.0
330                    ));
331                }
332                Ok(DocumentContent::Base {
333                    version: stored.version,
334                    value: stored.value,
335                })
336            })();
337            let Ok(content) = resolved else {
338                return failed(format!("Document copy {} was rejected", record.id.0));
339            };
340            *write = StorageWrite::DocumentCreate {
341                record: record.clone(),
342                content,
343            };
344        }
345        Ok(())
346    }
347
348    fn check_document_actions(&self, actions: &[(u64, DocumentAction)]) -> Result<()> {
349        let mut live_counts: Vec<(AddressKey, i64)> = Vec::new();
350        for (id, action) in actions {
351            let existing = self.documents.get(id);
352            if action.create.is_none() && existing.is_none() {
353                return failed(format!("Unknown document: {id}"));
354            }
355            if action.create.is_some() && existing.is_some() {
356                return failed(format!("Document {id} already exists"));
357            }
358            if existing.is_some_and(|existing| existing.record.retired_at.is_some()) {
359                return failed(format!("Document {id} is retired"));
360            }
361            if action.create.is_some() && !matches!(action.content, Some(DocumentContent::Base { .. })) {
362                return failed(format!("Document {id} is created without a base"));
363            }
364            if let Some(DocumentContent::Delta { version, .. }) = &action.content {
365                let Some(previous) = existing.and_then(|existing| existing.revisions.last()) else {
366                    return failed(format!("Document {id} delta has no base"));
367                };
368                if previous.content.version() != *version {
369                    return failed(format!("Document {id} version transition requires a base"));
370                }
371            }
372            let key = match (&action.create, existing) {
373                (Some(create), _) => create_address(create),
374                (None, Some(existing)) => create_address(&existing.record.identity),
375                (None, None) => unreachable!("checked above"),
376            };
377            let current = self.document_addresses.get(&key).and_then(|address| address.current);
378            let index = match live_counts.iter().position(|(k, _)| *k == key) {
379                Some(index) => index,
380                None => {
381                    live_counts.push((key, i64::from(current.is_some())));
382                    live_counts.len() - 1
383                }
384            };
385            if action.retire && current == Some(*id) {
386                live_counts[index].1 -= 1;
387            }
388            if action.create.is_some() && !action.retire {
389                live_counts[index].1 += 1;
390            }
391        }
392        if live_counts.iter().any(|(_, live)| *live > 1) {
393            return failed("Document address already has a current incarnation");
394        }
395        Ok(())
396    }
397
398    fn apply_document_actions(&mut self, actions: Vec<(u64, DocumentAction)>, seq: Seq) {
399        for (id, action) in actions {
400            let created = action.create.is_some();
401            if let Some(create) = action.create {
402                let key = create_address(&create);
403                let scope = create.scope;
404                let content = action.content.expect("checked: creation carries a base");
405                let record = DocumentRecord {
406                    identity: create,
407                    created_at: seq,
408                    retired_at: action.retire.then_some(seq),
409                };
410                self.documents.insert(
411                    id,
412                    StoredDoc {
413                        record,
414                        revisions: vec![Revision { seq, content }],
415                    },
416                );
417                self.record_types.insert(id, Table::Document);
418                self.document_addresses.entry(key).or_default().ids.insert(id);
419                insert_index(&mut self.document_ids_by_scope, scope, id);
420                self.next_id = self.next_id.max(id + 1);
421            } else if let Some(content) = action.content {
422                let stored = self.documents.get_mut(&id).expect("checked: document exists");
423                let base = matches!(content, DocumentContent::Base { .. });
424                let revision = Revision { seq, content };
425                if base && stored.record.identity.is_current_only() {
426                    stored.revisions = vec![revision];
427                } else {
428                    stored.revisions.push(revision);
429                }
430            }
431            let stored = self.documents.get_mut(&id).expect("checked: document exists");
432            if action.retire && !created {
433                stored.record.retired_at = Some(seq);
434            }
435            if action.retire && stored.record.identity.is_current_only() {
436                stored.revisions.clear();
437            }
438            if created || action.retire {
439                let key = create_address(&stored.record.identity);
440                let address = self.document_addresses.get_mut(&key).expect("indexed at creation");
441                if action.retire && address.current == Some(id) {
442                    address.current = None;
443                }
444                if created && !action.retire {
445                    address.current = Some(id);
446                }
447            }
448        }
449    }
450
451    fn apply_write(&mut self, write: StorageWrite, seq: Seq) {
452        match write {
453            StorageWrite::Conversation { value } => {
454                let id = value.id.0;
455                self.record_types.insert(id, Table::Conversation);
456                self.conversation_ids.insert(id);
457                if let Some(owner) = value.owner {
458                    insert_index(
459                        &mut self.conversations_by_owner_conversation,
460                        owner.conversation_id.0,
461                        id,
462                    );
463                    insert_index(&mut self.conversations_by_owner_task, owner.task_id.0, id);
464                }
465                self.conversations.insert(id, value);
466                self.next_id = self.next_id.max(id + 1);
467            }
468            StorageWrite::Entry { value } => {
469                let (id, conversation) = (value.id.0, value.conversation_id.0);
470                self.record_types.insert(id, Table::Entry);
471                insert_index(&mut self.entry_ids, conversation, id);
472                if value.head.is_some() {
473                    insert_index(&mut self.head_entry_ids, conversation, id);
474                }
475                self.entries.insert(id, (value, seq));
476                self.next_id = self.next_id.max(id + 1);
477            }
478            StorageWrite::Task { value } => {
479                let (id, status) = (value.id.0, value.state.status());
480                self.record_types.insert(id, Table::Task);
481                match self.tasks.get(&id).map(|previous| previous.state.status()) {
482                    None => {
483                        self.task_ids.insert(id);
484                        insert_index(&mut self.task_ids_by_status, status, id);
485                    }
486                    Some(previous) if previous != status => {
487                        self.task_ids_by_status.entry(previous).or_default().remove(&id);
488                        insert_index(&mut self.task_ids_by_status, status, id);
489                    }
490                    Some(_) => {}
491                }
492                self.tasks.insert(id, value);
493                self.next_id = self.next_id.max(id + 1);
494            }
495            StorageWrite::Submission { value } => {
496                let id = value.id.0;
497                self.record_types.insert(id, Table::Submission);
498                let previous = self.submissions.get(&id);
499                match previous.map(|previous| previous.status) {
500                    None => {
501                        self.submission_ids.insert(id);
502                        insert_index(&mut self.submission_ids_by_status, value.status, id);
503                    }
504                    Some(status) if status != value.status => {
505                        self.submission_ids_by_status.entry(status).or_default().remove(&id);
506                        insert_index(&mut self.submission_ids_by_status, value.status, id);
507                    }
508                    Some(_) => {}
509                }
510                if let Some(previous) = previous
511                    && let Some(request_id) = &previous.request_id
512                {
513                    let key = (previous.conversation_id.0, request_id.clone());
514                    if self.submission_ids_by_request.get(&key) == Some(&id) {
515                        self.submission_ids_by_request.remove(&key);
516                    }
517                }
518                if let Some(request_id) = &value.request_id {
519                    self.submission_ids_by_request
520                        .insert((value.conversation_id.0, request_id.clone()), id);
521                }
522                self.submissions.insert(id, value);
523                self.next_id = self.next_id.max(id + 1);
524            }
525            StorageWrite::DocumentCreate { .. }
526            | StorageWrite::DocumentCopy { .. }
527            | StorageWrite::DocumentChange { .. }
528            | StorageWrite::DocumentRetire { .. } => {}
529        }
530    }
531}
532
533impl Storage for MemoryStorage {
534    fn commit(&mut self, writes: Vec<StorageWrite>) -> Result<Seq> {
535        let prepared = self.prepare_commit(writes, None)?;
536        if let Some(sink) = &mut self.sink {
537            sink(&prepared)?;
538        }
539        Ok(self.apply_commit(prepared))
540    }
541
542    fn mint_id(&mut self) -> Result<u64> {
543        self.assert_open()?;
544        if self.next_id > MAX_SAFE_ID {
545            return failed("ID space is exhausted");
546        }
547        self.next_id += 1;
548        Ok(self.next_id - 1)
549    }
550
551    fn conversation(&self, id: ConversationId) -> Result<Option<ConversationRecord>> {
552        self.assert_open()?;
553        Ok(self.conversations.get(&id.0).cloned())
554    }
555
556    fn scan_conversations(
557        &self,
558        query: &ConversationQuery,
559        limit: usize,
560        cursor: Option<&Cursor>,
561    ) -> Result<Page<ConversationRecord>> {
562        self.assert_open()?;
563        let empty = BTreeSet::new();
564        let ids = match (query.owner_task_id, query.owner_conversation_id) {
565            (Some(task), _) => self.conversations_by_owner_task.get(&task.0).unwrap_or(&empty),
566            (None, Some(owner)) => self.conversations_by_owner_conversation.get(&owner.0).unwrap_or(&empty),
567            (None, None) => &self.conversation_ids,
568        };
569        let start = scan_start(query.order, cursor, ScanOrder::Ascending)?;
570        let values = scan_ids(ids, start)
571            .map(|id| &self.conversations[&id])
572            .filter(|value| {
573                query.owner_conversation_id.is_none_or(|owner| {
574                    value
575                        .owner
576                        .is_some_and(|value_owner| value_owner.conversation_id == owner)
577                })
578            })
579            .take(limit + 1)
580            .cloned()
581            .collect();
582        Ok(page(values, limit, start.order, |value: &ConversationRecord| {
583            value.id.0
584        }))
585    }
586
587    fn entry(&self, id: EntryId) -> Result<Option<StoredEntry>> {
588        self.assert_open()?;
589        Ok(self.entries.get(&id.0).map(|(entry, commit_seq)| StoredEntry {
590            entry: entry.clone(),
591            commit_seq: *commit_seq,
592        }))
593    }
594
595    fn visible_entry(&self, conversation_id: ConversationId, id: EntryId) -> Result<Option<StoredEntry>> {
596        self.assert_open()?;
597        let bound = id.0 as i64;
598        let found = self.visible_descending(conversation_id, bound, bound, 1)?;
599        Ok(found.first().map(|entry| StoredEntry {
600            entry: (*entry).clone(),
601            commit_seq: self.entries[&entry.id.0].1,
602        }))
603    }
604
605    fn find_latest_head_marker(
606        &self,
607        conversation_id: ConversationId,
608        at_or_before: Option<EntryId>,
609    ) -> Result<Option<EntryRecord>> {
610        self.assert_open()?;
611        self.check_conversation(conversation_id)?;
612        let (mut current, mut upper) = (conversation_id.0, at_or_before.map_or(i64::MAX, |at| at.0 as i64));
613        loop {
614            if let Some(ids) = self.head_entry_ids.get(&current)
615                && let Some(id) = bounded(ids, i64::MIN, upper).next_back()
616            {
617                return Ok(Some(self.entries[&id].0.clone()));
618            }
619            let Some(parent) = self.conversations[&current].parent else {
620                return Ok(None);
621            };
622            upper = upper.min(parent.at.0 as i64);
623            current = parent.conversation_id.0;
624        }
625    }
626
627    fn scan_entries(&self, query: &EntryQuery, limit: usize, cursor: Option<&Cursor>) -> Result<Page<EntryRecord>> {
628        self.assert_open()?;
629        let ScanStart { order, after } = scan_start(query.order, cursor, ScanOrder::Descending)?;
630        // The cursor narrows the bound on the side the scan moves away from.
631        let mut min = query.min_entry_id.map_or(i64::MIN, |id| id.0 as i64);
632        let mut max = query.max_entry_id.map_or(i64::MAX, |id| id.0 as i64);
633        if let Some(after) = after {
634            match order {
635                ScanOrder::Descending => max = query.max_entry_id.map_or(after, |id| id.0 as i64).min(after - 1),
636                ScanOrder::Ascending => min = query.min_entry_id.map_or(after, |id| id.0 as i64).max(after + 1),
637            }
638        }
639        let visible = match order {
640            ScanOrder::Descending => self.visible_descending(query.conversation_id, min, max, limit + 1)?,
641            ScanOrder::Ascending => self.visible_ascending(query.conversation_id, min, max, limit + 1)?,
642        };
643        Ok(page(
644            visible.into_iter().cloned().collect(),
645            limit,
646            order,
647            |entry: &EntryRecord| entry.id.0,
648        ))
649    }
650
651    fn task(&self, id: TaskId) -> Result<Option<TaskRecord>> {
652        self.assert_open()?;
653        Ok(self.tasks.get(&id.0).cloned())
654    }
655
656    fn scan_tasks(&self, query: &TaskQuery, limit: usize, cursor: Option<&Cursor>) -> Result<Page<TaskRecord>> {
657        self.assert_open()?;
658        let start = scan_start(query.order, cursor, ScanOrder::Ascending)?;
659        let empty = BTreeSet::new();
660        let ids = match query.status {
661            None => &self.task_ids,
662            Some(status) => self.task_ids_by_status.get(&status).unwrap_or(&empty),
663        };
664        let values = scan_ids(ids, start)
665            .map(|id| &self.tasks[&id])
666            .filter(|task| {
667                query.conversation_id.is_none_or(|id| task.conversation_id == id)
668                    && query.kind.as_ref().is_none_or(|kind| task.kind == *kind)
669                    && query.abort_requested.is_none_or(|abort| task.abort_requested == abort)
670                    && query.background.is_none_or(|background| task.background == background)
671            })
672            .take(limit + 1)
673            .cloned()
674            .collect();
675        Ok(page(values, limit, start.order, |task: &TaskRecord| task.id.0))
676    }
677
678    fn submission(&self, id: SubmissionId) -> Result<Option<SubmissionRecord>> {
679        self.assert_open()?;
680        Ok(self.submissions.get(&id.0).cloned())
681    }
682
683    fn scan_submissions(
684        &self,
685        query: &SubmissionQuery,
686        limit: usize,
687        cursor: Option<&Cursor>,
688    ) -> Result<Page<SubmissionRecord>> {
689        self.assert_open()?;
690        let start = scan_start(query.order, cursor, ScanOrder::Ascending)?;
691        let empty = BTreeSet::new();
692        let ids = match query.status {
693            None => &self.submission_ids,
694            Some(status) => self.submission_ids_by_status.get(&status).unwrap_or(&empty),
695        };
696        let values = scan_ids(ids, start)
697            .map(|id| &self.submissions[&id])
698            .filter(|submission| query.conversation_id.is_none_or(|id| submission.conversation_id == id))
699            .take(limit + 1)
700            .cloned()
701            .collect();
702        Ok(page(values, limit, start.order, |submission: &SubmissionRecord| {
703            submission.id.0
704        }))
705    }
706
707    fn submission_by_request(
708        &self,
709        conversation_id: ConversationId,
710        request_id: &str,
711    ) -> Result<Option<SubmissionRecord>> {
712        self.assert_open()?;
713        let id = self
714            .submission_ids_by_request
715            .get(&(conversation_id.0, request_id.to_owned()));
716        Ok(id.map(|id| self.submissions[id].clone()))
717    }
718
719    fn find_document(&self, address: &DocumentAddress, at: DocumentPoint) -> Result<Option<DocumentRecord>> {
720        self.assert_open()?;
721        let key = address_key(&address.kind, address.scope, address.key.as_deref());
722        let Some(index) = self.document_addresses.get(&key) else {
723            return Ok(None);
724        };
725        let id = match at {
726            DocumentPoint::Current => index.current,
727            DocumentPoint::At(_) => index
728                .ids
729                .iter()
730                .copied()
731                .find(|id| self.documents[id].record.is_alive_at(at)),
732        };
733        Ok(id.map(|id| self.documents[&id].record.clone()))
734    }
735
736    fn document(&self, id: DocumentId, at: DocumentPoint) -> Result<Option<StoredDocument>> {
737        self.assert_open()?;
738        self.materialize(id, at)
739    }
740
741    fn scan_documents(
742        &self,
743        query: &DocumentQuery,
744        limit: usize,
745        cursor: Option<&Cursor>,
746    ) -> Result<Page<DocumentRecord>> {
747        self.assert_open()?;
748        let empty = BTreeSet::new();
749        let ids = self.document_ids_by_scope.get(&query.scope).unwrap_or(&empty);
750        let after = match cursor {
751            Some(cursor) => cursor_after(cursor)?,
752            None => None,
753        };
754        let values = scan_ids(
755            ids,
756            ScanStart {
757                order: ScanOrder::Ascending,
758                after,
759            },
760        )
761        .map(|id| &self.documents[&id].record)
762        .filter(|record| {
763            query.kind.as_ref().is_none_or(|kind| record.identity.kind == *kind) && record.is_alive_at(query.at)
764        })
765        .take(limit + 1)
766        .cloned()
767        .collect();
768        Ok(page(values, limit, ScanOrder::Ascending, |record: &DocumentRecord| {
769            record.identity.id.0
770        }))
771    }
772
773    fn close(&mut self) -> Result<()> {
774        self.closed = true;
775        Ok(())
776    }
777}