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
182/// Holds decoded private blocks only while a bounded batch reads them.
183pub(crate) struct ChangesReadScope {
184    _identities: Option<uqa_storage::mvcc::PrivateRecordReadScope>,
185    _staged: BudgetedVec<uqa_storage::mvcc::PrivateRecordReadScope>,
186}
187
188impl DocumentChanges {
189    pub(crate) fn read_scope(
190        &self,
191        control: &StorageReadControl,
192    ) -> StorageBackendResult<ChangesReadScope> {
193        control.check()?;
194        let identities = self
195            .identities
196            .as_ref()
197            .map(|layer| {
198                layer.control.check()?;
199                layer.view.read_scope(control)
200            })
201            .transpose()?;
202        let mut staged = BudgetedVec::new(control.memory());
203        if let Some(layers) = &self.staged {
204            layers.control.check()?;
205            for view in layers.views.iter() {
206                if let Some(scope) = view.read_scope(control)? {
207                    staged.push(scope)?;
208                }
209            }
210        }
211        Ok(ChangesReadScope {
212            _identities: identities,
213            _staged: staged,
214        })
215    }
216
217    /// These changes with the rows that views of running commands staged above them, the newest command's view last.
218    pub(crate) fn with_staged(
219        mut self,
220        views: impl IntoIterator<Item = StagedRowsView>,
221        control: &StorageReadControl,
222    ) -> StorageBackendResult<Self> {
223        let mut layers = BudgetedVec::new(control.memory());
224        for view in self.staged_views() {
225            layers.push(view.clone())?;
226        }
227        for view in views {
228            control.check()?;
229            layers.push(view)?;
230        }
231        if !layers.is_empty() {
232            self.staged = Some(Arc::new(StagedLayers {
233                views: layers,
234                control: control.clone(),
235            }));
236        }
237        Ok(self)
238    }
239
240    /// These changes with the rows a transaction changed above them, below any rows that commands staged.
241    pub(super) fn with_identity_layer(
242        mut self,
243        view: ChangedIdentitiesView,
244        rows: IdentityRows,
245        control: &StorageReadControl,
246    ) -> StorageBackendResult<Self> {
247        if self.staged.is_some() || self.identities.is_some() {
248            return Err(super::selection::staged_below());
249        }
250        self.identities = Some(Arc::new(IdentityLayer {
251            view,
252            rows,
253            control: control.clone(),
254        }));
255        Ok(self)
256    }
257
258    pub(super) fn staged_views(&self) -> &[StagedRowsView] {
259        self.staged.as_ref().map_or(&[], |staged| &staged.views)
260    }
261
262    pub(super) fn has_identities(&self) -> bool {
263        self.identities.is_some()
264    }
265
266    /// The counted rows a transaction changed, when these changes are exactly those rows, which a read then counts without visiting them.
267    pub fn identity_counts(&self) -> Option<ChangedRowCounts> {
268        if !self.rows().is_empty() || self.staged.is_some() {
269            return None;
270        }
271        self.identities.as_ref().map(|layer| layer.view.counts())
272    }
273
274    /// The change the newest command staged for `id`.
275    fn staged_change(&self, id: DocId) -> StorageBackendResult<Option<Change>> {
276        let Some(staged) = &self.staged else {
277            return Ok(None);
278        };
279        for view in staged.views.iter().rev() {
280            if let Some(row) = view.get(id, &staged.control)? {
281                return Ok(Some(staged_change(row)));
282            }
283        }
284        Ok(None)
285    }
286
287    /// Whether a command staged a change for `id`, without decoding a spilled row.
288    pub(super) fn stages(&self, id: DocId) -> StorageBackendResult<bool> {
289        let Some(staged) = &self.staged else {
290            return Ok(false);
291        };
292        for view in staged.views.iter() {
293            if view.contains(id, &staged.control)? {
294                return Ok(true);
295            }
296        }
297        Ok(false)
298    }
299
300    /// Whether the transaction changed the row `id`, and whether it is present now.
301    pub(super) fn identity_presence(&self, id: DocId) -> StorageBackendResult<Option<bool>> {
302        match &self.identities {
303            Some(layer) => layer.view.presence(id, &layer.control),
304            None => Ok(None),
305        }
306    }
307
308    /// Whether a lazy layer changes `id`.
309    pub(super) fn layers_change(&self, id: DocId) -> StorageBackendResult<bool> {
310        Ok(self.stages(id)? || self.identity_presence(id)?.is_some())
311    }
312
313    /// A reader of the lazy layers' changes of the identities of the batch `ids`, or `None` when there is no lazy layer.
314    pub(super) fn layer_reader(&self, ids: &[DocId]) -> Option<LayerReader<'_>> {
315        if self.staged.is_none() && self.identities.is_none() {
316            return None;
317        }
318        let ascending = ids.len() > 1 && ids.windows(2).all(|pair| pair[0] < pair[1]);
319        let start = ids.first().and_then(|first| first.checked_sub(1));
320        Some(LayerReader {
321            changes: self,
322            ascending,
323            heads: if ascending {
324                self.staged_views()
325                    .iter()
326                    .map(|view| StagedHead {
327                        cursor: view.rows(start),
328                        next: None,
329                        done: false,
330                    })
331                    .collect()
332            } else {
333                Vec::new()
334            },
335            identity: self
336                .identities
337                .as_ref()
338                .filter(|_| ascending)
339                .map(|layer| IdentityHead {
340                    cursor: layer.view.cursor(start),
341                    next: None,
342                    done: false,
343                }),
344            last: None,
345        })
346    }
347
348    /// The newest change of `id`, an identity of the batch that `reader` reads.
349    pub(super) fn batch_change<'a>(
350        &'a self,
351        reader: &mut Option<LayerReader<'a>>,
352        id: DocId,
353    ) -> StorageBackendResult<Option<ChangeRef<'a>>> {
354        if let Some(reader) = reader {
355            match reader.lazy(id)? {
356                LazyChange::Staged(change) => return Ok(Some(ChangeRef::Owned(change))),
357                LazyChange::Changed(present) => {
358                    let layer = self.identities.as_ref().expect("an identity layer");
359                    return Ok(Some(ChangeRef::Owned(layer.change(present))));
360                }
361                LazyChange::Unchanged => {}
362            }
363        }
364        Ok(self.selected(id).map(ChangeRef::Borrowed))
365    }
366
367    /// 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.
368    pub(super) fn batch_source_run<'a>(
369        &'a self,
370        ids: &[DocId],
371        start: usize,
372        reader: &mut Option<LayerReader<'a>>,
373    ) -> StorageBackendResult<Option<(usize, &'a Arc<dyn DocumentStore>)>> {
374        let mut retained = |id: DocId| -> StorageBackendResult<Option<&'a Arc<dyn DocumentStore>>> {
375            if let Some(reader) = reader.as_mut() {
376                match reader.lazy(id)? {
377                    // A staged row is evaluated fields, which no retained source supplies.
378                    LazyChange::Staged(_) | LazyChange::Changed(false) => return Ok(None),
379                    LazyChange::Changed(true) => {
380                        return Ok(self.identities.as_ref().map(|layer| layer.source()));
381                    }
382                    LazyChange::Unchanged => {}
383                }
384            }
385            Ok(self.selected(id).and_then(Change::retained_source))
386        };
387        let Some(source) = retained(ids[start])? else {
388            return Ok(None);
389        };
390        let mut end = start + 1;
391        while end < ids.len() && retained(ids[end])?.is_some_and(|next| Arc::ptr_eq(source, next)) {
392            end += 1;
393        }
394        Ok(Some((end, source)))
395    }
396
397    /// The newest change of `id`.
398    pub(super) fn get(&self, id: DocId) -> StorageBackendResult<Option<ChangeRef<'_>>> {
399        if let Some(change) = self.staged_change(id)? {
400            return Ok(Some(ChangeRef::Owned(change)));
401        }
402        if let (Some(present), Some(layer)) = (self.identity_presence(id)?, &self.identities) {
403            return Ok(Some(ChangeRef::Owned(layer.change(present))));
404        }
405        Ok(self.selected(id).map(ChangeRef::Borrowed))
406    }
407
408    /// Visit the changes after `after` in identity order, each with whether its row is present afterwards.
409    pub fn changes_after(&self, after: Option<DocId>) -> Changes<bool, bool> {
410        Changes::new(
411            self,
412            after,
413            ChangeKind {
414                from_selection: Change::present,
415                from_identity: |_, present| present,
416                from_staged: std::convert::identity,
417                cursor: StagedRowsView::presence,
418            },
419        )
420    }
421
422    /// Visit the changes after `after` in identity order.
423    pub(super) fn change_rows_after(&self, after: Option<DocId>) -> Changes<StagedRow, Change> {
424        Changes::new(
425            self,
426            after,
427            ChangeKind {
428                from_selection: Change::clone,
429                from_identity: IdentityLayer::change,
430                from_staged: staged_change,
431                cursor: StagedRowsView::rows,
432            },
433        )
434    }
435}
436
437/// What a merged iteration yields from each layer.
438struct ChangeKind<S, T> {
439    from_selection: fn(&Change) -> T,
440    from_identity: fn(&IdentityLayer, bool) -> T,
441    from_staged: fn(S) -> T,
442    cursor: fn(&StagedRowsView, Option<DocId>) -> StagedCursor<S>,
443}
444
445/// 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.
446pub struct Changes<S, T> {
447    changes: DocumentChanges,
448    /// The position of the next selected change.
449    selected: usize,
450    from_selection: fn(&Change) -> T,
451    from_identity: fn(&IdentityLayer, bool) -> T,
452    from_staged: fn(S) -> T,
453    identity: Option<IdentityHead>,
454    /// Each command's staged rows, the oldest first.
455    staged: Vec<StagedHead<S>>,
456    failed: bool,
457}
458
459/// One command's staged rows and the next of them.
460struct StagedHead<S> {
461    cursor: StagedCursor<S>,
462    next: Option<(DocId, S)>,
463    done: bool,
464}
465
466impl<S: Default, T> Changes<S, T> {
467    fn new(changes: &DocumentChanges, after: Option<DocId>, kind: ChangeKind<S, T>) -> Self {
468        let selected = changes
469            .rows()
470            .partition_point(|(id, _)| after.is_some_and(|after| *id <= after));
471        Self {
472            changes: changes.clone(),
473            selected,
474            from_selection: kind.from_selection,
475            from_identity: kind.from_identity,
476            from_staged: kind.from_staged,
477            identity: changes.identities.as_ref().map(|layer| IdentityHead {
478                cursor: layer.view.cursor(after),
479                next: None,
480                done: false,
481            }),
482            staged: changes
483                .staged_views()
484                .iter()
485                .map(|view| StagedHead {
486                    cursor: (kind.cursor)(view, after),
487                    next: None,
488                    done: false,
489                })
490                .collect(),
491            failed: false,
492        }
493    }
494
495    fn advance(&mut self) -> StorageBackendResult<Option<(DocId, T)>> {
496        if let Some(staged) = &self.changes.staged {
497            for head in &mut self.staged {
498                if head.next.is_none() && !head.done {
499                    head.next = head.cursor.next(&staged.control)?;
500                    head.done = head.next.is_none();
501                }
502            }
503        }
504        if let (Some(head), Some(layer)) = (&mut self.identity, &self.changes.identities) {
505            if head.next.is_none() && !head.done {
506                head.next = head.cursor.next(&layer.control)?;
507                head.done = head.next.is_none();
508            }
509        }
510        let rows = self.changes.rows();
511        let selected = rows.get(self.selected).map(|(id, _)| *id);
512        let changed = self
513            .identity
514            .as_ref()
515            .and_then(|head| head.next.map(|(id, _)| id));
516        let Some(least) = self
517            .staged
518            .iter()
519            .filter_map(|head| head.next.as_ref().map(|(id, _)| *id))
520            .chain(changed)
521            .chain(selected)
522            .min()
523        else {
524            return Ok(None);
525        };
526        let mut found = None;
527        for head in self.staged.iter_mut().rev() {
528            if head.next.as_ref().is_some_and(|(id, _)| *id == least) {
529                let (id, row) = head.next.take().expect("a peeked staged row");
530                if found.is_none() {
531                    found = Some((id, (self.from_staged)(row)));
532                }
533            }
534        }
535        if changed == Some(least) {
536            let head = self.identity.as_mut().expect("a peeked identity");
537            let (id, present) = head.next.take().expect("a peeked identity");
538            if found.is_none() {
539                let layer = self.changes.identities.as_ref().expect("an identity layer");
540                found = Some((id, (self.from_identity)(layer, present)));
541            }
542        }
543        if selected == Some(least) {
544            let (id, change) = &rows[self.selected];
545            self.selected += 1;
546            if found.is_none() {
547                found = Some((*id, (self.from_selection)(change)));
548            }
549        }
550        Ok(found)
551    }
552}
553
554impl<S: Default, T> Iterator for Changes<S, T> {
555    type Item = StorageBackendResult<(DocId, T)>;
556
557    fn next(&mut self) -> Option<Self::Item> {
558        if self.failed {
559            return None;
560        }
561        match self.advance() {
562            Ok(change) => change.map(Ok),
563            Err(error) => {
564                self.failed = true;
565                Some(Err(error))
566            }
567        }
568    }
569}