Skip to main content

uqa_execution/query/document_changes/
layers.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Lazy layers above a selection of changes: the rows a transaction changed, read at a fixed snapshot, and above them the rows running commands staged, each command's above the commands' before it. A read takes immutable views of the layers, so it copies none of their rows.
8
9use super::identities::{ChangedIdentitiesView, ChangedRowCounts, IdentityCursor};
10use super::vectors::CapturedRows;
11use super::{
12    Arc, Change, DocId, DocumentChanges, DocumentStore, StorageBackendResult, StorageReadControl,
13};
14use crate::mutation::overlay::{StagedCursor, StagedRow, StagedRowsView};
15use uqa_core::memory::{Budgeted, BudgetedVec};
16
17pub(super) struct StagedLayers {
18    /// The commands' rows, the oldest command first.
19    views: BudgetedVec<StagedRowsView>,
20    /// The allowance that reads decode spilled rows into.
21    pub(super) control: StorageReadControl,
22}
23
24/// The rows a transaction changed in one relation, read from the transaction's view of it.
25pub(super) struct IdentityLayer {
26    view: ChangedIdentitiesView,
27    rows: IdentityRows,
28    control: StorageReadControl,
29}
30
31/// Where the present rows of an identity layer are read.
32pub(super) enum IdentityRows {
33    Retained(Arc<dyn DocumentStore>),
34    /// The rows with the vector sources the relation held when the layer was taken.
35    Captured(Arc<Budgeted<CapturedRows>>),
36}
37
38impl IdentityLayer {
39    /// The change of a changed row that is present now or not.
40    fn change(&self, present: bool) -> Change {
41        match (&self.rows, present) {
42            (IdentityRows::Retained(source), true) => Change::Retained(Arc::clone(source)),
43            (IdentityRows::Retained(_), false) => Change::Deleted,
44            (IdentityRows::Captured(rows), present) => Change::Captured(Arc::clone(rows), present),
45        }
46    }
47
48    /// The source of the present rows.
49    fn source(&self) -> &Arc<dyn DocumentStore> {
50        match &self.rows {
51            IdentityRows::Retained(source) => source,
52            IdentityRows::Captured(rows) => &rows.documents,
53        }
54    }
55}
56
57/// How a lazy layer changes one identity.
58#[derive(Clone)]
59enum LazyChange {
60    /// A command staged this change.
61    Staged(Change),
62    /// The transaction changed the row, which is present now or not.
63    Changed(bool),
64    Unchanged,
65}
66
67/// Reads the lazy layers' changes of the identities of one batch, in the batch's order. Ascending identities advance each layer once over the batch, holding one bounded page of each; other batches look each identity up.
68pub(super) struct LayerReader<'a> {
69    changes: &'a DocumentChanges,
70    ascending: bool,
71    /// Each command's staged rows, the oldest first.
72    heads: Vec<StagedHead<StagedRow>>,
73    identity: Option<IdentityHead>,
74    /// The identity read last and its change, which a lookahead and the read that follows it share.
75    last: Option<(DocId, LazyChange)>,
76}
77
78struct IdentityHead {
79    cursor: IdentityCursor,
80    next: Option<(DocId, bool)>,
81    done: bool,
82}
83
84impl IdentityHead {
85    /// Advance to `id` and take its entry when the cursor holds one.
86    fn take(
87        &mut self,
88        id: DocId,
89        control: &StorageReadControl,
90    ) -> StorageBackendResult<Option<bool>> {
91        while !self.done && self.next.is_none_or(|(next, _)| next < id) {
92            self.next = self.cursor.next(control)?;
93            self.done = self.next.is_none();
94        }
95        match self.next {
96            Some((next, present)) if next == id => {
97                self.next = None;
98                Ok(Some(present))
99            }
100            _ => Ok(None),
101        }
102    }
103}
104
105impl LayerReader<'_> {
106    fn lazy(&mut self, id: DocId) -> StorageBackendResult<LazyChange> {
107        if let Some((last, change)) = &self.last {
108            if *last == id {
109                return Ok(change.clone());
110            }
111        }
112        let change = if self.ascending {
113            let mut found = None;
114            if let Some(staged) = &self.changes.staged {
115                for head in self.heads.iter_mut().rev() {
116                    while !head.done && head.next.as_ref().is_none_or(|(next, _)| *next < id) {
117                        head.next = head.cursor.next(&staged.control)?;
118                        head.done = head.next.is_none();
119                    }
120                    if head.next.as_ref().is_some_and(|(next, _)| *next == id) {
121                        let (_, row) = head.next.take().expect("a matched staged row");
122                        if found.is_none() {
123                            found = Some(staged_change(row));
124                        }
125                    }
126                }
127            }
128            let changed = match (&mut self.identity, &self.changes.identities) {
129                (Some(head), Some(layer)) => head.take(id, &layer.control)?,
130                _ => None,
131            };
132            match (found, changed) {
133                (Some(change), _) => LazyChange::Staged(change),
134                (None, Some(present)) => LazyChange::Changed(present),
135                (None, None) => LazyChange::Unchanged,
136            }
137        } else if let Some(change) = self.changes.staged_change(id)? {
138            LazyChange::Staged(change)
139        } else {
140            self.changes
141                .identity_presence(id)?
142                .map_or(LazyChange::Unchanged, LazyChange::Changed)
143        };
144        self.last = Some((id, change.clone()));
145        Ok(change)
146    }
147}
148
149/// A change read from a selection, or produced by a lazy layer.
150pub(super) enum ChangeRef<'a> {
151    Borrowed(&'a Change),
152    Owned(Change),
153}
154
155impl std::ops::Deref for ChangeRef<'_> {
156    type Target = Change;
157
158    fn deref(&self) -> &Change {
159        match self {
160            Self::Borrowed(change) => change,
161            Self::Owned(change) => change,
162        }
163    }
164}
165
166impl ChangeRef<'_> {
167    pub(super) fn into_owned(self) -> Change {
168        match self {
169            Self::Borrowed(change) => change.clone(),
170            Self::Owned(change) => change,
171        }
172    }
173}
174
175/// The change a staged row makes.
176fn staged_change(row: StagedRow) -> Change {
177    row.map_or(Change::Deleted, |row| {
178        Change::Fields(row.fields, row.metadata)
179    })
180}
181
182impl DocumentChanges {
183    /// These changes with the rows that views of running commands staged above them, the newest command's view last.
184    pub(crate) fn with_staged(
185        mut self,
186        views: impl IntoIterator<Item = StagedRowsView>,
187        control: &StorageReadControl,
188    ) -> StorageBackendResult<Self> {
189        let mut layers = BudgetedVec::new(control.memory());
190        for view in self.staged_views() {
191            layers.push(view.clone())?;
192        }
193        for view in views {
194            control.check()?;
195            layers.push(view)?;
196        }
197        if !layers.is_empty() {
198            self.staged = Some(Arc::new(StagedLayers {
199                views: layers,
200                control: control.clone(),
201            }));
202        }
203        Ok(self)
204    }
205
206    /// These changes with the rows a transaction changed above them, below any rows that commands staged.
207    pub(super) fn with_identity_layer(
208        mut self,
209        view: ChangedIdentitiesView,
210        rows: IdentityRows,
211        control: &StorageReadControl,
212    ) -> StorageBackendResult<Self> {
213        if self.staged.is_some() || self.identities.is_some() {
214            return Err(super::selection::staged_below());
215        }
216        self.identities = Some(Arc::new(IdentityLayer {
217            view,
218            rows,
219            control: control.clone(),
220        }));
221        Ok(self)
222    }
223
224    pub(super) fn staged_views(&self) -> &[StagedRowsView] {
225        self.staged.as_ref().map_or(&[], |staged| &staged.views)
226    }
227
228    pub(super) fn has_identities(&self) -> bool {
229        self.identities.is_some()
230    }
231
232    /// The counted rows a transaction changed, when these changes are exactly those rows, which a read then counts without visiting them.
233    pub fn identity_counts(&self) -> Option<ChangedRowCounts> {
234        if !self.rows().is_empty() || self.staged.is_some() {
235            return None;
236        }
237        self.identities.as_ref().map(|layer| layer.view.counts())
238    }
239
240    /// The change the newest command staged for `id`.
241    fn staged_change(&self, id: DocId) -> StorageBackendResult<Option<Change>> {
242        let Some(staged) = &self.staged else {
243            return Ok(None);
244        };
245        for view in staged.views.iter().rev() {
246            if let Some(row) = view.get(id, &staged.control)? {
247                return Ok(Some(staged_change(row)));
248            }
249        }
250        Ok(None)
251    }
252
253    /// Whether a command staged a change for `id`, without decoding a spilled row.
254    pub(super) fn stages(&self, id: DocId) -> StorageBackendResult<bool> {
255        let Some(staged) = &self.staged else {
256            return Ok(false);
257        };
258        for view in staged.views.iter() {
259            if view.contains(id, &staged.control)? {
260                return Ok(true);
261            }
262        }
263        Ok(false)
264    }
265
266    /// Whether the transaction changed the row `id`, and whether it is present now.
267    pub(super) fn identity_presence(&self, id: DocId) -> StorageBackendResult<Option<bool>> {
268        match &self.identities {
269            Some(layer) => layer.view.presence(id, &layer.control),
270            None => Ok(None),
271        }
272    }
273
274    /// Whether a lazy layer changes `id`.
275    pub(super) fn layers_change(&self, id: DocId) -> StorageBackendResult<bool> {
276        Ok(self.stages(id)? || self.identity_presence(id)?.is_some())
277    }
278
279    /// A reader of the lazy layers' changes of the identities of the batch `ids`, or `None` when there is no lazy layer.
280    pub(super) fn layer_reader(&self, ids: &[DocId]) -> Option<LayerReader<'_>> {
281        if self.staged.is_none() && self.identities.is_none() {
282            return None;
283        }
284        let ascending = ids.len() > 1 && ids.windows(2).all(|pair| pair[0] < pair[1]);
285        let start = ids.first().and_then(|first| first.checked_sub(1));
286        Some(LayerReader {
287            changes: self,
288            ascending,
289            heads: if ascending {
290                self.staged_views()
291                    .iter()
292                    .map(|view| StagedHead {
293                        cursor: view.rows(start),
294                        next: None,
295                        done: false,
296                    })
297                    .collect()
298            } else {
299                Vec::new()
300            },
301            identity: self
302                .identities
303                .as_ref()
304                .filter(|_| ascending)
305                .map(|layer| IdentityHead {
306                    cursor: layer.view.cursor(start),
307                    next: None,
308                    done: false,
309                }),
310            last: None,
311        })
312    }
313
314    /// The newest change of `id`, an identity of the batch that `reader` reads.
315    pub(super) fn batch_change<'a>(
316        &'a self,
317        reader: &mut Option<LayerReader<'a>>,
318        id: DocId,
319    ) -> StorageBackendResult<Option<ChangeRef<'a>>> {
320        if let Some(reader) = reader {
321            match reader.lazy(id)? {
322                LazyChange::Staged(change) => return Ok(Some(ChangeRef::Owned(change))),
323                LazyChange::Changed(present) => {
324                    let layer = self.identities.as_ref().expect("an identity layer");
325                    return Ok(Some(ChangeRef::Owned(layer.change(present))));
326                }
327                LazyChange::Unchanged => {}
328            }
329        }
330        Ok(self.selected(id).map(ChangeRef::Borrowed))
331    }
332
333    /// The end of the run of `ids` from `start` whose rows one retained source supplies, with that source; `reader` reads the batch's lazy layers.
334    pub(super) fn batch_source_run<'a>(
335        &'a self,
336        ids: &[DocId],
337        start: usize,
338        reader: &mut Option<LayerReader<'a>>,
339    ) -> StorageBackendResult<Option<(usize, &'a Arc<dyn DocumentStore>)>> {
340        let mut retained = |id: DocId| -> StorageBackendResult<Option<&'a Arc<dyn DocumentStore>>> {
341            if let Some(reader) = reader.as_mut() {
342                match reader.lazy(id)? {
343                    // A staged row is evaluated fields, which no retained source supplies.
344                    LazyChange::Staged(_) | LazyChange::Changed(false) => return Ok(None),
345                    LazyChange::Changed(true) => {
346                        return Ok(self.identities.as_ref().map(|layer| layer.source()));
347                    }
348                    LazyChange::Unchanged => {}
349                }
350            }
351            Ok(self.selected(id).and_then(Change::retained_source))
352        };
353        let Some(source) = retained(ids[start])? else {
354            return Ok(None);
355        };
356        let mut end = start + 1;
357        while end < ids.len() && retained(ids[end])?.is_some_and(|next| Arc::ptr_eq(source, next)) {
358            end += 1;
359        }
360        Ok(Some((end, source)))
361    }
362
363    /// The newest change of `id`.
364    pub(super) fn get(&self, id: DocId) -> StorageBackendResult<Option<ChangeRef<'_>>> {
365        if let Some(change) = self.staged_change(id)? {
366            return Ok(Some(ChangeRef::Owned(change)));
367        }
368        if let (Some(present), Some(layer)) = (self.identity_presence(id)?, &self.identities) {
369            return Ok(Some(ChangeRef::Owned(layer.change(present))));
370        }
371        Ok(self.selected(id).map(ChangeRef::Borrowed))
372    }
373
374    /// Visit the changes after `after` in identity order, each with whether its row is present afterwards.
375    pub fn changes_after(&self, after: Option<DocId>) -> Changes<bool, bool> {
376        Changes::new(
377            self,
378            after,
379            ChangeKind {
380                from_selection: Change::present,
381                from_identity: |_, present| present,
382                from_staged: std::convert::identity,
383                cursor: StagedRowsView::presence,
384            },
385        )
386    }
387
388    /// Visit the changes after `after` in identity order.
389    pub(super) fn change_rows_after(&self, after: Option<DocId>) -> Changes<StagedRow, Change> {
390        Changes::new(
391            self,
392            after,
393            ChangeKind {
394                from_selection: Change::clone,
395                from_identity: IdentityLayer::change,
396                from_staged: staged_change,
397                cursor: StagedRowsView::rows,
398            },
399        )
400    }
401}
402
403/// What a merged iteration yields from each layer.
404struct ChangeKind<S, T> {
405    from_selection: fn(&Change) -> T,
406    from_identity: fn(&IdentityLayer, bool) -> T,
407    from_staged: fn(S) -> T,
408    cursor: fn(&StagedRowsView, Option<DocId>) -> StagedCursor<S>,
409}
410
411/// The changes of a selection and of the lazy layers above it, in identity order. The newest change of an identity shadows the older ones. The iterator shares the changes it reads, so it outlives the reader that created it.
412pub struct Changes<S, T> {
413    changes: DocumentChanges,
414    /// The position of the next selected change.
415    selected: usize,
416    from_selection: fn(&Change) -> T,
417    from_identity: fn(&IdentityLayer, bool) -> T,
418    from_staged: fn(S) -> T,
419    identity: Option<IdentityHead>,
420    /// Each command's staged rows, the oldest first.
421    staged: Vec<StagedHead<S>>,
422    failed: bool,
423}
424
425/// One command's staged rows and the next of them.
426struct StagedHead<S> {
427    cursor: StagedCursor<S>,
428    next: Option<(DocId, S)>,
429    done: bool,
430}
431
432impl<S: Default, T> Changes<S, T> {
433    fn new(changes: &DocumentChanges, after: Option<DocId>, kind: ChangeKind<S, T>) -> Self {
434        let selected = changes
435            .rows()
436            .partition_point(|(id, _)| after.is_some_and(|after| *id <= after));
437        Self {
438            changes: changes.clone(),
439            selected,
440            from_selection: kind.from_selection,
441            from_identity: kind.from_identity,
442            from_staged: kind.from_staged,
443            identity: changes.identities.as_ref().map(|layer| IdentityHead {
444                cursor: layer.view.cursor(after),
445                next: None,
446                done: false,
447            }),
448            staged: changes
449                .staged_views()
450                .iter()
451                .map(|view| StagedHead {
452                    cursor: (kind.cursor)(view, after),
453                    next: None,
454                    done: false,
455                })
456                .collect(),
457            failed: false,
458        }
459    }
460
461    fn advance(&mut self) -> StorageBackendResult<Option<(DocId, T)>> {
462        if let Some(staged) = &self.changes.staged {
463            for head in &mut self.staged {
464                if head.next.is_none() && !head.done {
465                    head.next = head.cursor.next(&staged.control)?;
466                    head.done = head.next.is_none();
467                }
468            }
469        }
470        if let (Some(head), Some(layer)) = (&mut self.identity, &self.changes.identities) {
471            if head.next.is_none() && !head.done {
472                head.next = head.cursor.next(&layer.control)?;
473                head.done = head.next.is_none();
474            }
475        }
476        let rows = self.changes.rows();
477        let selected = rows.get(self.selected).map(|(id, _)| *id);
478        let changed = self
479            .identity
480            .as_ref()
481            .and_then(|head| head.next.map(|(id, _)| id));
482        let Some(least) = self
483            .staged
484            .iter()
485            .filter_map(|head| head.next.as_ref().map(|(id, _)| *id))
486            .chain(changed)
487            .chain(selected)
488            .min()
489        else {
490            return Ok(None);
491        };
492        let mut found = None;
493        for head in self.staged.iter_mut().rev() {
494            if head.next.as_ref().is_some_and(|(id, _)| *id == least) {
495                let (id, row) = head.next.take().expect("a peeked staged row");
496                if found.is_none() {
497                    found = Some((id, (self.from_staged)(row)));
498                }
499            }
500        }
501        if changed == Some(least) {
502            let head = self.identity.as_mut().expect("a peeked identity");
503            let (id, present) = head.next.take().expect("a peeked identity");
504            if found.is_none() {
505                let layer = self.changes.identities.as_ref().expect("an identity layer");
506                found = Some((id, (self.from_identity)(layer, present)));
507            }
508        }
509        if selected == Some(least) {
510            let (id, change) = &rows[self.selected];
511            self.selected += 1;
512            if found.is_none() {
513                found = Some((*id, (self.from_selection)(change)));
514            }
515        }
516        Ok(found)
517    }
518}
519
520impl<S: Default, T> Iterator for Changes<S, T> {
521    type Item = StorageBackendResult<(DocId, T)>;
522
523    fn next(&mut self) -> Option<Self::Item> {
524        if self.failed {
525            return None;
526        }
527        match self.advance() {
528            Ok(change) => change.map(Ok),
529            Err(error) => {
530                self.failed = true;
531                Some(Err(error))
532            }
533        }
534    }
535}