Skip to main content

uqa_execution/query/document_changes/
selection.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Ordered private selections retain their allocation leases with every shared view.
8
9use super::{Arc, Change, DocId, DocumentChanges, StorageBackendResult};
10use uqa_core::memory::{BudgetedVec, MemoryBudget, MemoryReservation};
11use uqa_storage::read_control::StorageReadControl;
12
13pub(super) struct Selection {
14    pub(super) rows: BudgetedVec<(DocId, Change)>,
15    // Release the shared payload charge after its rows and their source owners.
16    allocation: MemoryReservation,
17}
18
19impl Selection {
20    pub(super) fn into_parts(self) -> (Vec<(DocId, Change)>, MemoryReservation, MemoryReservation) {
21        let (rows, capacity) = self.rows.into_parts();
22        (rows, capacity, self.allocation)
23    }
24
25    fn new(memory: &MemoryBudget, capacity: usize) -> StorageBackendResult<Self> {
26        let allocation = memory.reserve(size_of::<Self>())?;
27        let mut rows = BudgetedVec::new(memory);
28        rows.reserve(capacity)?;
29        Ok(Self { rows, allocation })
30    }
31}
32
33impl DocumentChanges {
34    pub(super) fn retention_control(&self, control: &StorageReadControl) -> StorageReadControl {
35        let memory = self
36            .selection
37            .as_ref()
38            .map_or(control.memory(), |selection| selection.rows.budget());
39        StorageReadControl::new(memory, control.cancellation())
40    }
41
42    pub(super) fn rows(&self) -> &[(DocId, Change)] {
43        self.selection
44            .as_ref()
45            .map_or(&[], |selection| &selection.rows)
46    }
47
48    /// The selected change of `id`, below any rows that commands staged.
49    pub(super) fn selected(&self, id: DocId) -> Option<&Change> {
50        let rows = self.rows();
51        rows.binary_search_by_key(&id, |(id, _)| *id)
52            .ok()
53            .map(|index| &rows[index].1)
54    }
55
56    fn writable(
57        &mut self,
58        additional: usize,
59        control: &StorageReadControl,
60    ) -> StorageBackendResult<&mut Selection> {
61        control.check()?;
62        if self.staged.is_some() || self.identities.is_some() {
63            return Err(staged_below());
64        }
65        if self
66            .selection
67            .as_ref()
68            .is_none_or(|rows| Arc::strong_count(rows) != 1)
69        {
70            let memory = self
71                .selection
72                .as_ref()
73                .map_or(control.memory(), |selection| selection.rows.budget());
74            let capacity = self
75                .rows()
76                .len()
77                .checked_add(additional)
78                .ok_or(uqa_core::memory::MemoryError::SizeOverflow)?;
79            let mut selection = Selection::new(memory, capacity)?;
80            for row in self.rows() {
81                control.check()?;
82                selection.rows.push(row.clone())?;
83            }
84            control.check()?;
85            self.selection = Some(Arc::new(selection));
86        }
87        let selection = Arc::get_mut(self.selection.as_mut().expect("selection initialized"))
88            .expect("selection uniquely owned");
89        selection.rows.reserve(additional)?;
90        Ok(selection)
91    }
92
93    pub(super) fn insert(
94        &mut self,
95        id: DocId,
96        change: Change,
97        control: &StorageReadControl,
98    ) -> StorageBackendResult<()> {
99        let position = self.rows().binary_search_by_key(&id, |(id, _)| *id);
100        let selection = self.writable(usize::from(position.is_err()), control)?;
101        match position {
102            Ok(index) => selection.rows[index].1 = change,
103            Err(index) => {
104                selection.rows.push((id, change))?;
105                selection.rows[index..].rotate_right(1);
106            }
107        }
108        Ok(())
109    }
110
111    /// Merge complete ordered views before publication. Failure leaves both the original selection and its charged capacity unchanged.
112    pub fn extend(
113        &mut self,
114        newer: Self,
115        control: &StorageReadControl,
116    ) -> StorageBackendResult<()> {
117        control.check()?;
118        if self.staged.is_some()
119            || newer.staged.is_some()
120            || self.identities.is_some()
121            || newer.identities.is_some()
122        {
123            return Err(staged_below());
124        }
125        if !newer.has_changes() {
126            return Ok(());
127        }
128        let Some(original) = &self.selection else {
129            *self = newer;
130            return Ok(());
131        };
132        let mut count = original.rows.len();
133        for (id, _) in newer.rows() {
134            control.check()?;
135            if self.selected(*id).is_none() {
136                count = count
137                    .checked_add(1)
138                    .ok_or(uqa_core::memory::MemoryError::SizeOverflow)?;
139            }
140        }
141        let mut selection = Selection::new(original.rows.budget(), count)?;
142        let mut old = self.rows().iter().peekable();
143        for row in newer.rows() {
144            while old.peek().is_some_and(|(id, _)| *id < row.0) {
145                control.check()?;
146                selection
147                    .rows
148                    .push(old.next().expect("peeked row").clone())?;
149            }
150            control.check()?;
151            if old.peek().is_some_and(|(id, _)| *id == row.0) {
152                old.next();
153            }
154            selection.rows.push(row.clone())?;
155        }
156        for row in old {
157            control.check()?;
158            selection.rows.push(row.clone())?;
159        }
160        control.check()?;
161        self.selection = Some(Arc::new(selection));
162        Ok(())
163    }
164}
165
166/// Selected changes are older than the lazy layers, the rows a transaction changed and the rows running commands staged, so they cannot be added above those rows.
167pub(super) fn staged_below() -> uqa_storage::StorageBackendError {
168    uqa_storage::StorageBackendError::Other(
169        "selected changes cannot be added above the rows a transaction changed or commands staged"
170            .into(),
171    )
172}