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
182pub(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 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 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 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 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 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 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 pub(super) fn layers_change(&self, id: DocId) -> StorageBackendResult<bool> {
310 Ok(self.stages(id)? || self.identity_presence(id)?.is_some())
311 }
312
313 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 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 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 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 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 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 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
437struct 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
445pub struct Changes<S, T> {
447 changes: DocumentChanges,
448 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 staged: Vec<StagedHead<S>>,
456 failed: bool,
457}
458
459struct 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}