1use 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 views: BudgetedVec<StagedRowsView>,
20 pub(super) control: StorageReadControl,
22}
23
24pub(super) struct IdentityLayer {
26 view: ChangedIdentitiesView,
27 rows: IdentityRows,
28 control: StorageReadControl,
29}
30
31pub(super) enum IdentityRows {
33 Retained(Arc<dyn DocumentStore>),
34 Captured(Arc<Budgeted<CapturedRows>>),
36}
37
38impl IdentityLayer {
39 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 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#[derive(Clone)]
59enum LazyChange {
60 Staged(Change),
62 Changed(bool),
64 Unchanged,
65}
66
67pub(super) struct LayerReader<'a> {
69 changes: &'a DocumentChanges,
70 ascending: bool,
71 heads: Vec<StagedHead<StagedRow>>,
73 identity: Option<IdentityHead>,
74 last: Option<(DocId, LazyChange)>,
76}
77
78struct IdentityHead {
79 cursor: IdentityCursor,
80 next: Option<(DocId, bool)>,
81 done: bool,
82}
83
84impl IdentityHead {
85 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
149pub(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
175fn 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 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 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 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 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 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 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 pub(super) fn layers_change(&self, id: DocId) -> StorageBackendResult<bool> {
276 Ok(self.stages(id)? || self.identity_presence(id)?.is_some())
277 }
278
279 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 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 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 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 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 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 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
403struct 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
411pub struct Changes<S, T> {
413 changes: DocumentChanges,
414 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 staged: Vec<StagedHead<S>>,
422 failed: bool,
423}
424
425struct 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}