Skip to main content

xrack_runtime/
model.rs

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
59/// A shared UI-thread model with separately tracked row and length reads.
60/// Cloning the handle shares its data and subscriptions.
61pub 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    /// A stable identity that survives edits, inserts, removes of other rows, and sorting.
136    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    /// Find a record's current index by its stable identity.
146    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    /// Borrow the rows after the caller has established the appropriate dependencies.
179    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    /// Locate a row after the caller has established the appropriate dependencies.
198    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    /// Check an editor's field against the identified row without watching other fields.
214    #[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    /// Subscribe to changes in the projected value of existing rows. The caller also tracks
238    /// structure changes and keeps the returned signal alive for as long as it uses the projection.
239    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    /// Observe row contents by stable key. Observers run while the model may be borrowed.
266    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    /// Identify the exact model contents and order seen by an asynchronous edit.
299    #[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    /// Inspect a bounded page without recording reactive dependencies.
315    #[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    /// Insert at a model index. An index beyond the end leaves the model unchanged.
350    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    /// Stably reorder rows, retaining their keys and delegate lifetimes.
405    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        // Notify readers before discarding signals for indices whose rows have shifted.
427        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    /// Resolve a DSL model index with the same dependency tracking as a row read.
467    #[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    /// Copy rows that the caller has already sampled from the live model.
478    #[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    /// Transfer an owned model's rows at a by-value boundary. A shared model
489    /// still needs a tracked read because its other owners can edit it.
490    #[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    /// Commit a value against the row and value observed by an editor.
506    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    /// Update an identified record from its latest value. Returning None declines the edit.
511    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    /// Replace one row. Returns false for an invalid index or equal value.
531    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    /// Compare the current values, independently of handle identity.
591    pub fn values_eq(&self, other: &Self) -> bool {
592        self.compare_values(other, |model| model.0.values.track())
593    }
594
595    /// Compare expression operands, tracking only models that can outlive
596    /// the comparison and be changed by another owner.
597    #[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}