1use crate::{ChangeSignal, RowKey, RowLifetime};
2use std::{
3 cell::{Cell, RefCell},
4 cmp::Ordering as Comparison,
5 collections::BTreeMap,
6 fmt,
7 ops::Range,
8 rc::{Rc, Weak},
9 sync::atomic::{AtomicU64, Ordering},
10};
11
12static NEXT_MODEL: AtomicU64 = AtomicU64::new(1);
13
14struct Entry<T> {
15 id: u64,
16 value: T,
17}
18
19#[derive(Default)]
20struct RowSignals {
21 signals: BTreeMap<usize, ChangeSignal>,
22 next_prune: usize,
23}
24
25impl RowSignals {
26 fn track(&mut self, index: usize) {
27 if !self.signals.contains_key(&index) && self.signals.len() >= self.next_prune {
28 self.signals.retain(|_, signal| signal.has_observers());
29 self.next_prune = (self.signals.len() * 2).max(64);
30 }
31 self.signals.entry(index).or_default().track();
32 }
33}
34
35type ProjectionDiff<T> = dyn Fn(usize, &T, &T) -> bool;
36pub(crate) type RowObserver<T> = dyn Fn(RowKey, Option<&T>);
37
38struct RowProjection<T> {
39 signal: Weak<ChangeSignal>,
40 limit: usize,
41 changed: Box<ProjectionDiff<T>>,
42}
43
44struct ModelData<T> {
45 id: u64,
46 rows: RefCell<Vec<Entry<T>>>,
47 next_row: Cell<u64>,
48 revision: Cell<u64>,
49 edit_revision: Cell<u64>,
50 lifetimes: RefCell<BTreeMap<u64, Rc<()>>>,
51 count: ChangeSignal,
52 structure: ChangeSignal,
53 values: ChangeSignal,
54 row_signals: RefCell<RowSignals>,
55 projections: RefCell<Vec<RowProjection<T>>>,
56 row_observers: RefCell<Vec<Weak<RowObserver<T>>>>,
57}
58
59pub struct VecModel<T>(Rc<ModelData<T>>);
62
63impl<T> fmt::Debug for VecModel<T> {
64 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
65 f.debug_struct("VecModel")
66 .field("id", &self.0.id)
67 .finish_non_exhaustive()
68 }
69}
70
71impl<T> Clone for VecModel<T> {
72 fn clone(&self) -> Self {
73 Self(self.0.clone())
74 }
75}
76
77impl<T> From<Vec<T>> for VecModel<T> {
78 fn from(rows: Vec<T>) -> Self {
79 let id = NEXT_MODEL
80 .try_update(Ordering::Relaxed, Ordering::Relaxed, |id| id.checked_add(1))
81 .expect("model identity exhausted");
82 let next_row = rows.len() as u64;
83 Self(Rc::new(ModelData {
84 id,
85 rows: RefCell::new(
86 rows.into_iter()
87 .enumerate()
88 .map(|(id, value)| Entry {
89 id: id as u64,
90 value,
91 })
92 .collect(),
93 ),
94 next_row: Cell::new(next_row),
95 revision: Cell::default(),
96 edit_revision: Cell::default(),
97 lifetimes: RefCell::default(),
98 count: ChangeSignal::default(),
99 structure: ChangeSignal::default(),
100 values: ChangeSignal::default(),
101 row_signals: RefCell::default(),
102 projections: RefCell::default(),
103 row_observers: RefCell::default(),
104 }))
105 }
106}
107
108impl<T> Default for VecModel<T> {
109 fn default() -> Self {
110 Self::from(Vec::new())
111 }
112}
113
114impl<T> PartialEq for VecModel<T> {
115 fn eq(&self, other: &Self) -> bool {
116 Rc::ptr_eq(&self.0, &other.0)
117 }
118}
119
120impl<T> Eq for VecModel<T> {}
121
122impl<T> VecModel<T> {
123 pub(crate) fn is_shared(&self) -> bool {
124 Rc::strong_count(&self.0) > 1
125 }
126
127 fn entry(&self, value: T) -> Entry<T> {
128 let id = self.0.next_row.get();
129 self.0
130 .next_row
131 .set(id.checked_add(1).expect("model row identity exhausted"));
132 Entry { id, value }
133 }
134
135 pub fn row_key(&self, index: usize) -> Option<RowKey> {
137 self.0.structure.track();
138 self.0.rows.borrow().get(index).map(|entry| RowKey {
139 model: self.0.id,
140 row: entry.id,
141 scope: 0,
142 })
143 }
144
145 pub fn row_index(&self, key: RowKey) -> Option<usize> {
147 self.0.structure.track();
148 self.row_index_untracked(key)
149 }
150
151 pub(crate) fn row_index_untracked(&self, key: RowKey) -> Option<usize> {
152 if key.model != self.0.id {
153 return None;
154 }
155 self.0
156 .rows
157 .borrow()
158 .iter()
159 .position(|entry| entry.id == key.row)
160 }
161
162 pub(crate) fn visit_row_keys(&self, range: Range<usize>, mut visit: impl FnMut(RowKey)) {
163 self.0.structure.track();
164 for entry in &self.0.rows.borrow()[range] {
165 visit(RowKey {
166 model: self.0.id,
167 row: entry.id,
168 scope: 0,
169 });
170 }
171 }
172
173 pub(crate) fn visit_row_data(&self, count: usize, visit: impl FnMut(usize, RowKey, &T)) {
174 self.0.values.track();
175 self.visit_rows_untracked(count, visit);
176 }
177
178 pub(crate) fn visit_rows_untracked(
180 &self,
181 count: usize,
182 mut visit: impl FnMut(usize, RowKey, &T),
183 ) {
184 for (index, entry) in self.0.rows.borrow().iter().take(count).enumerate() {
185 visit(
186 index,
187 RowKey {
188 model: self.0.id,
189 row: entry.id,
190 scope: 0,
191 },
192 &entry.value,
193 );
194 }
195 }
196
197 pub(crate) fn position_untracked(
199 &self,
200 range: std::ops::Range<usize>,
201 mut predicate: impl FnMut(&T) -> bool,
202 ) -> Option<usize> {
203 let start = range.start;
204 self.0
205 .rows
206 .borrow()
207 .get(range)?
208 .iter()
209 .position(|entry| predicate(&entry.value))
210 .map(|offset| start + offset)
211 }
212
213 #[doc(hidden)]
215 pub fn row_matches(&self, index: usize, key: RowKey, matches: impl FnOnce(&T) -> bool) -> bool {
216 key.model == self.0.id
217 && self
218 .0
219 .rows
220 .borrow()
221 .get(index)
222 .is_some_and(|entry| entry.id == key.row && matches(&entry.value))
223 }
224
225 pub(crate) fn project_row_untracked<R>(
226 &self,
227 index: usize,
228 project: impl FnOnce(&T) -> R,
229 ) -> Option<R> {
230 self.0
231 .rows
232 .borrow()
233 .get(index)
234 .map(|entry| project(&entry.value))
235 }
236
237 pub(crate) fn observe_projection<P: PartialEq>(
240 &self,
241 limit: usize,
242 project: impl Fn(&T) -> P + 'static,
243 ) -> Rc<ChangeSignal> {
244 self.observe_projection_changes(limit, move |_, before, after| {
245 project(before) != project(after)
246 })
247 }
248
249 pub(crate) fn observe_projection_changes(
250 &self,
251 limit: usize,
252 changed: impl Fn(usize, &T, &T) -> bool + 'static,
253 ) -> Rc<ChangeSignal> {
254 let signal = Rc::new(ChangeSignal::default());
255 let mut projections = self.0.projections.borrow_mut();
256 projections.retain(|projection| projection.signal.strong_count() != 0);
257 projections.push(RowProjection {
258 signal: Rc::downgrade(&signal),
259 limit,
260 changed: Box::new(changed),
261 });
262 signal
263 }
264
265 pub(crate) fn observe_rows(&self, observer: &Rc<RowObserver<T>>) {
267 let mut observers = self.0.row_observers.borrow_mut();
268 observers.retain(|observer| observer.strong_count() != 0);
269 observers.push(Rc::downgrade(observer));
270 }
271
272 fn row_changed(&self, id: u64, value: Option<&T>) {
273 let key = RowKey {
274 model: self.0.id,
275 row: id,
276 scope: 0,
277 };
278 self.0.row_observers.borrow_mut().retain(|observer| {
279 if let Some(observer) = observer.upgrade() {
280 observer(key, value);
281 true
282 } else {
283 false
284 }
285 });
286 }
287
288 pub(crate) fn row_lifetime(&self, key: RowKey) -> RowLifetime {
289 let mut lifetimes = self.0.lifetimes.borrow_mut();
290 RowLifetime(Some(Rc::downgrade(lifetimes.entry(key.row).or_default())))
291 }
292
293 pub(crate) fn structure_stamp(&self) -> (u64, u64) {
294 self.0.structure.track();
295 (self.0.id, self.0.revision.get())
296 }
297
298 #[doc(hidden)]
300 pub fn edit_stamp(&self) -> (u64, u64) {
301 (self.0.id, self.0.edit_revision.get())
302 }
303
304 pub(crate) fn contents_stamp(&self) -> (u64, u64) {
305 self.0.values.track();
306 self.edit_stamp()
307 }
308
309 pub fn len(&self) -> usize {
310 self.0.count.track();
311 self.0.rows.borrow().len()
312 }
313
314 #[doc(hidden)]
316 pub fn inspect_rows<R>(
317 &self,
318 offset: usize,
319 limit: usize,
320 map: impl FnMut(&T) -> R,
321 ) -> (usize, Vec<R>) {
322 let rows = self.0.rows.borrow();
323 let items = rows
324 .iter()
325 .skip(offset)
326 .take(limit)
327 .map(|row| &row.value)
328 .map(map)
329 .collect();
330 (rows.len(), items)
331 }
332
333 pub fn is_empty(&self) -> bool {
334 self.len() == 0
335 }
336
337 pub fn push(&self, value: T) {
338 let index = {
339 let mut rows = self.0.rows.borrow_mut();
340 let index = rows.len();
341 let entry = self.entry(value);
342 self.row_changed(entry.id, Some(&entry.value));
343 rows.push(entry);
344 index
345 };
346 self.structure_changed(index, true);
347 }
348
349 pub fn insert(&self, index: usize, value: T) -> bool {
351 {
352 let mut rows = self.0.rows.borrow_mut();
353 if index > rows.len() {
354 return false;
355 }
356 let entry = self.entry(value);
357 self.row_changed(entry.id, Some(&entry.value));
358 rows.insert(index, entry);
359 }
360 self.structure_changed(index, true);
361 true
362 }
363
364 pub fn remove(&self, index: usize) -> Option<T> {
365 let removed = {
366 let mut rows = self.0.rows.borrow_mut();
367 if index >= rows.len() {
368 return None;
369 }
370 rows.remove(index)
371 };
372 self.row_changed(removed.id, None);
373 self.0.lifetimes.borrow_mut().remove(&removed.id);
374 self.structure_changed(index, true);
375 Some(removed.value)
376 }
377
378 pub(crate) fn sorted_indices_untracked(
379 &self,
380 limit: usize,
381 compare: impl FnMut(&T, &T) -> Comparison,
382 ) -> Vec<usize> {
383 self.projected_indices_untracked(limit, None, |_| true, Some(compare))
384 }
385
386 pub(crate) fn projected_indices_untracked(
387 &self,
388 limit: usize,
389 base_order: Option<&[usize]>,
390 include: impl Fn(&T) -> bool,
391 compare: Option<impl FnMut(&T, &T) -> Comparison>,
392 ) -> Vec<usize> {
393 let rows = self.0.rows.borrow();
394 let mut order: Vec<_> = (0..rows.len().min(limit))
395 .map(|index| base_order.map_or(index, |order| order[index]))
396 .filter(|&index| include(&rows[index].value))
397 .collect();
398 if let Some(mut compare) = compare {
399 order.sort_by(|&a, &b| compare(&rows[a].value, &rows[b].value));
400 }
401 order
402 }
403
404 pub fn sort_by(&self, compare: impl FnMut(&T, &T) -> Comparison) -> bool {
406 let order = self.sorted_indices_untracked(usize::MAX, compare);
407 let Some(first_changed) = order.iter().enumerate().position(|(new, old)| new != *old)
408 else {
409 return false;
410 };
411 {
412 let mut rows = self.0.rows.borrow_mut();
413 let mut source: Vec<_> = rows.drain(first_changed..).map(Some).collect();
414 rows.extend(order.into_iter().skip(first_changed).map(|index| {
415 source[index - first_changed]
416 .take()
417 .expect("sort permutation contains each row once")
418 }));
419 }
420 self.structure_changed(first_changed, false);
421 true
422 }
423
424 fn structure_changed(&self, index: usize, count_changed: bool) {
425 self.0.revision.set(self.0.revision.get().wrapping_add(1));
426 let shifted = self.0.row_signals.borrow_mut().signals.split_off(&index);
428 for signal in shifted.into_values() {
429 signal.notify();
430 }
431 if count_changed {
432 self.0.count.notify();
433 }
434 self.0.structure.notify();
435 self.values_changed();
436 }
437
438 fn values_changed(&self) {
439 self.0
440 .edit_revision
441 .set(self.0.edit_revision.get().wrapping_add(1));
442 self.0.values.notify();
443 }
444}
445
446impl<T> VecModel<T> {
447 pub(crate) fn project_row<R>(&self, index: usize, project: impl FnOnce(&T) -> R) -> Option<R> {
448 let rows = self.0.rows.borrow();
449 if let Some(entry) = rows.get(index) {
450 if ChangeSignal::is_tracking() {
451 self.0.row_signals.borrow_mut().track(index);
452 }
453 Some(project(&entry.value))
454 } else {
455 self.0.count.track();
456 None
457 }
458 }
459}
460
461impl<T: Clone> VecModel<T> {
462 pub fn row(&self, index: usize) -> Option<T> {
463 self.project_row(index, T::clone)
464 }
465
466 #[doc(hidden)]
468 pub fn row_at(&self, index: i64) -> Option<T> {
469 self.row(usize::try_from(index).ok()?)
470 }
471
472 pub fn snapshot(&self) -> Vec<T> {
473 self.0.values.track();
474 self.snapshot_untracked()
475 }
476
477 #[doc(hidden)]
479 pub fn snapshot_untracked(&self) -> Vec<T> {
480 self.0
481 .rows
482 .borrow()
483 .iter()
484 .map(|entry| entry.value.clone())
485 .collect()
486 }
487
488 #[doc(hidden)]
491 pub fn into_snapshot(self) -> Vec<T> {
492 match Rc::try_unwrap(self.0) {
493 Ok(data) => data
494 .rows
495 .into_inner()
496 .into_iter()
497 .map(|entry| entry.value)
498 .collect(),
499 Err(data) => Self(data).snapshot(),
500 }
501 }
502}
503
504impl<T: PartialEq> VecModel<T> {
505 pub fn set_row_if_current(&self, index: usize, key: RowKey, expected: &T, value: T) -> bool {
507 self.update_row_if_key(index, key, |current| (current == expected).then_some(value))
508 }
509
510 pub fn update_row_if_key(
512 &self,
513 index: usize,
514 key: RowKey,
515 update: impl FnOnce(&T) -> Option<T>,
516 ) -> bool {
517 let next = {
518 let rows = self.0.rows.borrow();
519 let Some(entry) = rows
520 .get(index)
521 .filter(|entry| key.model == self.0.id && entry.id == key.row)
522 else {
523 return false;
524 };
525 update(&entry.value)
526 };
527 next.is_some_and(|value| self.set_row(index, value))
528 }
529
530 pub fn set_row(&self, index: usize, value: T) -> bool {
532 let mut value = value;
533 let changed = {
534 let mut rows = self.0.rows.borrow_mut();
535 let Some(current) = rows.get_mut(index) else {
536 return false;
537 };
538 self.swap_row(index, current, &mut value)
539 };
540 if changed {
541 self.values_changed();
542 }
543 changed
544 }
545
546 pub(crate) fn replace_rows_if_current(
547 &self,
548 stamp: (u64, u64),
549 mut values: Vec<(usize, T)>,
550 ) -> bool {
551 if self.edit_stamp() != stamp {
552 return false;
553 }
554 let mut rows = self.0.rows.borrow_mut();
555 if values.iter().any(|(index, _)| *index >= rows.len()) {
556 return false;
557 }
558 let mut changed = false;
559 for (index, value) in &mut values {
560 changed |= self.swap_row(*index, &mut rows[*index], value);
561 }
562 drop(rows);
563 if changed {
564 self.values_changed();
565 }
566 changed
567 }
568
569 fn swap_row(&self, index: usize, entry: &mut Entry<T>, next: &mut T) -> bool {
570 if &entry.value == next {
571 return false;
572 }
573 self.0.projections.borrow_mut().retain(|projection| {
574 let Some(signal) = projection.signal.upgrade() else {
575 return false;
576 };
577 if index < projection.limit && (projection.changed)(index, &entry.value, next) {
578 signal.notify();
579 }
580 true
581 });
582 std::mem::swap(&mut entry.value, next);
583 self.row_changed(entry.id, Some(&entry.value));
584 if let Some(signal) = self.0.row_signals.borrow().signals.get(&index) {
585 signal.notify();
586 }
587 true
588 }
589
590 pub fn values_eq(&self, other: &Self) -> bool {
592 self.compare_values(other, |model| model.0.values.track())
593 }
594
595 #[doc(hidden)]
598 pub fn values_eq_owned(self, other: Self) -> bool {
599 self.compare_values(&other, |model| {
600 if model.is_shared() {
601 model.0.values.track();
602 }
603 })
604 }
605
606 fn compare_values(&self, other: &Self, track: impl Fn(&Self)) -> bool {
607 if self == other {
608 return true;
609 }
610 track(self);
611 track(other);
612 self.0.rows.borrow().iter().map(|row| &row.value).eq(other
613 .0
614 .rows
615 .borrow()
616 .iter()
617 .map(|row| &row.value))
618 }
619}
620
621#[cfg(test)]
622mod tests {
623 use super::*;
624 use crate::Property;
625 use std::cell::Cell;
626
627 #[test]
628 fn sorting_retains_stable_keys_and_invalidates_only_affected_reads() {
629 let model = VecModel::from(vec![(0, 'a'), (2, 'b'), (1, 'c'), (2, 'd')]);
630 let keys: Vec<_> = (0..4).map(|index| model.row_key(index).unwrap()).collect();
631 let lifetime = model.row_lifetime(keys[2]);
632 let len = Property::default();
633 let first = Property::default();
634 let second = Property::default();
635 let count_reads = Cell::new(0);
636 let prefix_reads = Cell::new(0);
637 let count = || {
638 len.get(|| {
639 count_reads.set(count_reads.get() + 1);
640 model.len()
641 })
642 };
643 let prefix = || {
644 first.get(|| {
645 prefix_reads.set(prefix_reads.get() + 1);
646 model.row(0)
647 })
648 };
649 let row = || second.get(|| model.row(1));
650 assert_eq!(
651 (count(), prefix(), row()),
652 (4, Some((0, 'a')), Some((2, 'b')))
653 );
654 assert!(model.sort_by(|a, b| a.0.cmp(&b.0)));
655 assert_eq!(
656 (count(), prefix(), row()),
657 (4, Some((0, 'a')), Some((1, 'c')))
658 );
659 assert_eq!((count_reads.get(), prefix_reads.get()), (1, 1));
660 assert_eq!(model.snapshot(), [(0, 'a'), (1, 'c'), (2, 'b'), (2, 'd')]);
661 assert_eq!(model.row_key(1), Some(keys[2]));
662 assert_eq!(model.row_key(2), Some(keys[1]));
663 assert_eq!(model.row_key(3), Some(keys[3]));
664 assert!(lifetime.is_live(keys[2], model.structure_stamp().0, 4));
665 assert!(!model.sort_by(|a, b| a.0.cmp(&b.0)));
666 }
667
668 #[test]
669 fn watched_model_rows_survive_pruning_and_detect_shifts() {
670 use crate::property::watch_reads;
671
672 let model = VecModel::from((0..128).collect::<Vec<_>>());
673 watch_reads(|reads| {
674 for index in 0..100 {
675 assert_eq!(model.row(index), Some(index));
676 }
677 assert!(model.set_row(120, 0));
678 assert!(!reads.changed());
679 assert!(model.set_row(0, 120));
680 assert!(reads.changed());
681 });
682 watch_reads(|reads| {
683 assert_eq!(model.row(1), Some(1));
684 assert_eq!(model.remove(0), Some(120));
685 assert!(reads.changed());
686 });
687 }
688
689 #[test]
690 fn consuming_snapshot_tracks_only_models_with_a_live_owner() {
691 let temporary = Property::default();
692 assert_eq!(
693 temporary.get(|| VecModel::from(vec![1]).into_snapshot()),
694 [1]
695 );
696 assert!(!temporary.is_dirty());
697
698 let shared = VecModel::from(vec![2]);
699 let snapshot = Property::default();
700 let read = || snapshot.get(|| shared.clone().into_snapshot());
701 assert_eq!(read(), [2]);
702 assert!(!snapshot.is_dirty());
703 assert!(shared.set_row(0, 3));
704 assert!(snapshot.is_dirty());
705 assert_eq!(read(), [3]);
706 }
707
708 #[test]
709 fn model_tracks_rows_length_and_snapshots_independently() {
710 let model = VecModel::from(vec![10, 20, 30]);
711 let count = Property::default();
712 let second = Property::default();
713 let missing = Property::default();
714 let snapshot = Property::default();
715 let reads = Cell::new(0);
716 let len = || {
717 count.get(|| {
718 reads.set(reads.get() + 1);
719 model.len()
720 })
721 };
722 let row = || second.get(|| model.row(1));
723 let tail = || missing.get(|| model.row(3));
724 let values = || snapshot.get(|| model.snapshot());
725
726 assert_eq!((len(), row(), tail()), (3, Some(20), None));
727 assert_eq!(values(), [10, 20, 30]);
728 assert!(model.set_row(0, 11));
729 assert_eq!((len(), row()), (3, Some(20)));
730 assert_eq!(reads.get(), 1);
731 assert_eq!(values(), [11, 20, 30]);
732 assert!(!model.set_row(0, 11));
733 assert!(!model.set_row(9, 11));
734 model.push(40);
735 assert_eq!((len(), row(), tail()), (4, Some(20), Some(40)));
736 assert!(model.insert(0, 5));
737 assert_eq!((len(), row(), tail()), (5, Some(11), Some(30)));
738 assert_eq!(model.remove(0), Some(5));
739 assert_eq!((len(), row(), tail()), (4, Some(20), Some(40)));
740 }
741}