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    ops::Range,
7    rc::{Rc, Weak},
8    sync::atomic::{AtomicU64, Ordering},
9};
10
11static NEXT_MODEL: AtomicU64 = AtomicU64::new(1);
12
13struct Entry<T> {
14    id: u64,
15    value: T,
16}
17
18#[derive(Default)]
19struct RowSignals {
20    signals: BTreeMap<usize, ChangeSignal>,
21    next_prune: usize,
22}
23
24impl RowSignals {
25    fn track(&mut self, index: usize) {
26        if !self.signals.contains_key(&index) && self.signals.len() >= self.next_prune {
27            self.signals.retain(|_, signal| signal.has_dependents());
28            self.next_prune = (self.signals.len() * 2).max(64);
29        }
30        self.signals.entry(index).or_default().track();
31    }
32}
33
34type ProjectionDiff<T> = dyn Fn(usize, &T, &T) -> bool;
35
36struct RowProjection<T> {
37    signal: Weak<ChangeSignal>,
38    limit: usize,
39    changed: Box<ProjectionDiff<T>>,
40}
41
42struct ModelData<T> {
43    id: u64,
44    rows: RefCell<Vec<Entry<T>>>,
45    next_row: Cell<u64>,
46    revision: Cell<u64>,
47    edit_revision: Cell<u64>,
48    lifetimes: RefCell<BTreeMap<u64, Rc<()>>>,
49    count: ChangeSignal,
50    structure: ChangeSignal,
51    values: ChangeSignal,
52    row_signals: RefCell<RowSignals>,
53    projections: RefCell<Vec<RowProjection<T>>>,
54}
55
56/// A shared UI-thread model with separately tracked row and length reads.
57/// Cloning the handle shares its data and subscriptions.
58pub struct VecModel<T>(Rc<ModelData<T>>);
59
60impl<T> Clone for VecModel<T> {
61    fn clone(&self) -> Self {
62        Self(self.0.clone())
63    }
64}
65
66impl<T> From<Vec<T>> for VecModel<T> {
67    fn from(rows: Vec<T>) -> Self {
68        let id = NEXT_MODEL
69            .try_update(Ordering::Relaxed, Ordering::Relaxed, |id| id.checked_add(1))
70            .expect("model identity exhausted");
71        let next_row = rows.len() as u64;
72        Self(Rc::new(ModelData {
73            id,
74            rows: RefCell::new(
75                rows.into_iter()
76                    .enumerate()
77                    .map(|(id, value)| Entry {
78                        id: id as u64,
79                        value,
80                    })
81                    .collect(),
82            ),
83            next_row: Cell::new(next_row),
84            revision: Cell::default(),
85            edit_revision: Cell::default(),
86            lifetimes: RefCell::default(),
87            count: ChangeSignal::default(),
88            structure: ChangeSignal::default(),
89            values: ChangeSignal::default(),
90            row_signals: RefCell::default(),
91            projections: RefCell::default(),
92        }))
93    }
94}
95
96impl<T> Default for VecModel<T> {
97    fn default() -> Self {
98        Self::from(Vec::new())
99    }
100}
101
102impl<T> PartialEq for VecModel<T> {
103    fn eq(&self, other: &Self) -> bool {
104        Rc::ptr_eq(&self.0, &other.0)
105    }
106}
107
108impl<T> Eq for VecModel<T> {}
109
110impl<T> VecModel<T> {
111    fn entry(&self, value: T) -> Entry<T> {
112        let id = self.0.next_row.get();
113        self.0
114            .next_row
115            .set(id.checked_add(1).expect("model row identity exhausted"));
116        Entry { id, value }
117    }
118
119    /// A stable identity that survives edits, inserts, removes of other rows, and sorting.
120    pub fn row_key(&self, index: usize) -> Option<RowKey> {
121        self.0.structure.track();
122        self.0.rows.borrow().get(index).map(|entry| RowKey {
123            model: self.0.id,
124            row: entry.id,
125            scope: 0,
126        })
127    }
128
129    /// Find a record's current index by its stable identity.
130    pub fn row_index(&self, key: RowKey) -> Option<usize> {
131        self.0.structure.track();
132        if key.model != self.0.id {
133            return None;
134        }
135        self.0
136            .rows
137            .borrow()
138            .iter()
139            .position(|entry| entry.id == key.row)
140    }
141
142    pub(crate) fn visit_row_keys(&self, range: Range<usize>, mut visit: impl FnMut(RowKey)) {
143        self.0.structure.track();
144        for entry in &self.0.rows.borrow()[range] {
145            visit(RowKey {
146                model: self.0.id,
147                row: entry.id,
148                scope: 0,
149            });
150        }
151    }
152
153    pub(crate) fn visit_row_data(&self, count: usize, visit: impl FnMut(usize, RowKey, &T)) {
154        self.0.values.track();
155        self.visit_rows_untracked(count, visit);
156    }
157
158    /// Borrow the rows after the caller has established the appropriate dependencies.
159    pub(crate) fn visit_rows_untracked(
160        &self,
161        count: usize,
162        mut visit: impl FnMut(usize, RowKey, &T),
163    ) {
164        for (index, entry) in self.0.rows.borrow().iter().take(count).enumerate() {
165            visit(
166                index,
167                RowKey {
168                    model: self.0.id,
169                    row: entry.id,
170                    scope: 0,
171                },
172                &entry.value,
173            );
174        }
175    }
176
177    /// Locate a row after the caller has established the appropriate dependencies.
178    pub(crate) fn position_untracked(
179        &self,
180        range: std::ops::Range<usize>,
181        mut predicate: impl FnMut(&T) -> bool,
182    ) -> Option<usize> {
183        let start = range.start;
184        self.0
185            .rows
186            .borrow()
187            .get(range)?
188            .iter()
189            .position(|entry| predicate(&entry.value))
190            .map(|offset| start + offset)
191    }
192
193    pub(crate) fn project_row_untracked<R>(
194        &self,
195        index: usize,
196        project: impl FnOnce(&T) -> R,
197    ) -> Option<R> {
198        self.0
199            .rows
200            .borrow()
201            .get(index)
202            .map(|entry| project(&entry.value))
203    }
204
205    /// Subscribe to changes in the projected value of existing rows. The caller also tracks
206    /// structure changes and keeps the returned signal alive for as long as it uses the projection.
207    pub(crate) fn observe_projection<P: PartialEq>(
208        &self,
209        limit: usize,
210        project: impl Fn(&T) -> P + 'static,
211    ) -> Rc<ChangeSignal> {
212        self.observe_projection_changes(limit, move |_, before, after| {
213            project(before) != project(after)
214        })
215    }
216
217    pub(crate) fn observe_projection_changes(
218        &self,
219        limit: usize,
220        changed: impl Fn(usize, &T, &T) -> bool + 'static,
221    ) -> Rc<ChangeSignal> {
222        let signal = Rc::new(ChangeSignal::default());
223        let mut projections = self.0.projections.borrow_mut();
224        projections.retain(|projection| projection.signal.strong_count() != 0);
225        projections.push(RowProjection {
226            signal: Rc::downgrade(&signal),
227            limit,
228            changed: Box::new(changed),
229        });
230        signal
231    }
232
233    pub(crate) fn row_lifetime(&self, key: RowKey) -> RowLifetime {
234        let mut lifetimes = self.0.lifetimes.borrow_mut();
235        RowLifetime(Some(Rc::downgrade(lifetimes.entry(key.row).or_default())))
236    }
237
238    pub(crate) fn structure_stamp(&self) -> (u64, u64) {
239        self.0.structure.track();
240        (self.0.id, self.0.revision.get())
241    }
242
243    /// Identify the exact model contents and order seen by an asynchronous edit.
244    #[doc(hidden)]
245    pub fn edit_stamp(&self) -> (u64, u64) {
246        (self.0.id, self.0.edit_revision.get())
247    }
248
249    pub fn len(&self) -> usize {
250        self.0.count.track();
251        self.0.rows.borrow().len()
252    }
253
254    pub fn is_empty(&self) -> bool {
255        self.len() == 0
256    }
257
258    pub fn push(&self, value: T) {
259        let index = {
260            let mut rows = self.0.rows.borrow_mut();
261            let index = rows.len();
262            rows.push(self.entry(value));
263            index
264        };
265        self.structure_changed(index, true);
266    }
267
268    /// Insert at a model index. An index beyond the end leaves the model unchanged.
269    pub fn insert(&self, index: usize, value: T) -> bool {
270        {
271            let mut rows = self.0.rows.borrow_mut();
272            if index > rows.len() {
273                return false;
274            }
275            rows.insert(index, self.entry(value));
276        }
277        self.structure_changed(index, true);
278        true
279    }
280
281    pub fn remove(&self, index: usize) -> Option<T> {
282        let removed = {
283            let mut rows = self.0.rows.borrow_mut();
284            if index >= rows.len() {
285                return None;
286            }
287            rows.remove(index)
288        };
289        self.0.lifetimes.borrow_mut().remove(&removed.id);
290        self.structure_changed(index, true);
291        Some(removed.value)
292    }
293
294    pub(crate) fn sorted_indices_untracked(
295        &self,
296        limit: usize,
297        compare: impl FnMut(&T, &T) -> Comparison,
298    ) -> Vec<usize> {
299        self.projected_indices_untracked(limit, None, |_| true, Some(compare))
300    }
301
302    pub(crate) fn projected_indices_untracked(
303        &self,
304        limit: usize,
305        base_order: Option<&[usize]>,
306        include: impl Fn(&T) -> bool,
307        compare: Option<impl FnMut(&T, &T) -> Comparison>,
308    ) -> Vec<usize> {
309        let rows = self.0.rows.borrow();
310        let mut order: Vec<_> = (0..rows.len().min(limit))
311            .map(|index| base_order.map_or(index, |order| order[index]))
312            .filter(|&index| include(&rows[index].value))
313            .collect();
314        if let Some(mut compare) = compare {
315            order.sort_by(|&a, &b| compare(&rows[a].value, &rows[b].value));
316        }
317        order
318    }
319
320    /// Stably reorder rows, retaining their keys and delegate lifetimes.
321    pub fn sort_by(&self, compare: impl FnMut(&T, &T) -> Comparison) -> bool {
322        let order = self.sorted_indices_untracked(usize::MAX, compare);
323        let Some(first_changed) = order.iter().enumerate().position(|(new, old)| new != *old)
324        else {
325            return false;
326        };
327        {
328            let mut rows = self.0.rows.borrow_mut();
329            let mut source: Vec<_> = rows.drain(first_changed..).map(Some).collect();
330            rows.extend(order.into_iter().skip(first_changed).map(|index| {
331                source[index - first_changed]
332                    .take()
333                    .expect("sort permutation contains each row once")
334            }));
335        }
336        self.structure_changed(first_changed, false);
337        true
338    }
339
340    fn structure_changed(&self, index: usize, count_changed: bool) {
341        self.0.revision.set(self.0.revision.get().wrapping_add(1));
342        // Dropping the old signals invalidates reads at the shifted indices.
343        let shifted = self.0.row_signals.borrow_mut().signals.split_off(&index);
344        drop(shifted);
345        if count_changed {
346            self.0.count.notify();
347        }
348        self.0.structure.notify();
349        self.values_changed();
350    }
351
352    fn values_changed(&self) {
353        self.0
354            .edit_revision
355            .set(self.0.edit_revision.get().wrapping_add(1));
356        self.0.values.notify();
357    }
358}
359
360impl<T> VecModel<T> {
361    pub(crate) fn project_row<R>(&self, index: usize, project: impl FnOnce(&T) -> R) -> Option<R> {
362        let rows = self.0.rows.borrow();
363        if let Some(entry) = rows.get(index) {
364            if ChangeSignal::is_tracking() {
365                self.0.row_signals.borrow_mut().track(index);
366            }
367            Some(project(&entry.value))
368        } else {
369            self.0.count.track();
370            None
371        }
372    }
373}
374
375impl<T: Clone> VecModel<T> {
376    pub fn row(&self, index: usize) -> Option<T> {
377        self.project_row(index, T::clone)
378    }
379
380    pub fn snapshot(&self) -> Vec<T> {
381        self.0.values.track();
382        self.0
383            .rows
384            .borrow()
385            .iter()
386            .map(|entry| entry.value.clone())
387            .collect()
388    }
389}
390
391impl<T: PartialEq> VecModel<T> {
392    /// Commit a value against the row and value observed by an editor.
393    pub fn set_row_if_current(&self, index: usize, key: RowKey, expected: &T, value: T) -> bool {
394        self.update_row_if_key(index, key, |current| (current == expected).then_some(value))
395    }
396
397    /// Update an identified record from its latest value. Returning None declines the edit.
398    pub fn update_row_if_key(
399        &self,
400        index: usize,
401        key: RowKey,
402        update: impl FnOnce(&T) -> Option<T>,
403    ) -> bool {
404        let next = {
405            let rows = self.0.rows.borrow();
406            let Some(entry) = rows
407                .get(index)
408                .filter(|entry| key.model == self.0.id && entry.id == key.row)
409            else {
410                return false;
411            };
412            update(&entry.value)
413        };
414        next.is_some_and(|value| self.set_row(index, value))
415    }
416
417    /// Replace one row. Returns false for an invalid index or equal value.
418    pub fn set_row(&self, index: usize, value: T) -> bool {
419        let mut value = value;
420        let changed = {
421            let mut rows = self.0.rows.borrow_mut();
422            let Some(current) = rows.get_mut(index) else {
423                return false;
424            };
425            self.swap_row(index, &mut current.value, &mut value)
426        };
427        if changed {
428            self.values_changed();
429        }
430        changed
431    }
432
433    pub(crate) fn replace_rows_if_current(
434        &self,
435        stamp: (u64, u64),
436        mut values: Vec<(usize, T)>,
437    ) -> bool {
438        if self.edit_stamp() != stamp {
439            return false;
440        }
441        let mut rows = self.0.rows.borrow_mut();
442        if values.iter().any(|(index, _)| *index >= rows.len()) {
443            return false;
444        }
445        let mut changed = false;
446        for (index, value) in &mut values {
447            changed |= self.swap_row(*index, &mut rows[*index].value, value);
448        }
449        drop(rows);
450        if changed {
451            self.values_changed();
452        }
453        changed
454    }
455
456    fn swap_row(&self, index: usize, current: &mut T, next: &mut T) -> bool {
457        if current == next {
458            return false;
459        }
460        self.0.projections.borrow_mut().retain(|projection| {
461            let Some(signal) = projection.signal.upgrade() else {
462                return false;
463            };
464            if index < projection.limit && (projection.changed)(index, current, next) {
465                signal.notify();
466            }
467            true
468        });
469        std::mem::swap(current, next);
470        if let Some(signal) = self.0.row_signals.borrow().signals.get(&index) {
471            signal.notify();
472        }
473        true
474    }
475
476    /// Compare the current values, independently of handle identity.
477    pub fn values_eq(&self, other: &Self) -> bool {
478        if self == other {
479            return true;
480        }
481        self.0.values.track();
482        other.0.values.track();
483        self.0.rows.borrow().iter().map(|row| &row.value).eq(other
484            .0
485            .rows
486            .borrow()
487            .iter()
488            .map(|row| &row.value))
489    }
490}
491
492#[cfg(test)]
493mod tests {
494    use super::*;
495    use crate::Property;
496    use std::cell::Cell;
497
498    #[test]
499    fn sorting_retains_stable_keys_and_invalidates_only_affected_reads() {
500        let model = VecModel::from(vec![(0, 'a'), (2, 'b'), (1, 'c'), (2, 'd')]);
501        let keys: Vec<_> = (0..4).map(|index| model.row_key(index).unwrap()).collect();
502        let lifetime = model.row_lifetime(keys[2]);
503        let len = Property::default();
504        let first = Property::default();
505        let second = Property::default();
506        let count_reads = Cell::new(0);
507        let prefix_reads = Cell::new(0);
508        let count = || {
509            len.get(|| {
510                count_reads.set(count_reads.get() + 1);
511                model.len()
512            })
513        };
514        let prefix = || {
515            first.get(|| {
516                prefix_reads.set(prefix_reads.get() + 1);
517                model.row(0)
518            })
519        };
520        let row = || second.get(|| model.row(1));
521        assert_eq!(
522            (count(), prefix(), row()),
523            (4, Some((0, 'a')), Some((2, 'b')))
524        );
525        assert!(model.sort_by(|a, b| a.0.cmp(&b.0)));
526        assert_eq!(
527            (count(), prefix(), row()),
528            (4, Some((0, 'a')), Some((1, 'c')))
529        );
530        assert_eq!((count_reads.get(), prefix_reads.get()), (1, 1));
531        assert_eq!(model.snapshot(), [(0, 'a'), (1, 'c'), (2, 'b'), (2, 'd')]);
532        assert_eq!(model.row_key(1), Some(keys[2]));
533        assert_eq!(model.row_key(2), Some(keys[1]));
534        assert_eq!(model.row_key(3), Some(keys[3]));
535        assert!(lifetime.is_live(keys[2], model.structure_stamp().0, 4));
536        assert!(!model.sort_by(|a, b| a.0.cmp(&b.0)));
537    }
538
539    #[test]
540    fn model_tracks_rows_length_and_snapshots_independently() {
541        let model = VecModel::from(vec![10, 20, 30]);
542        let count = Property::default();
543        let second = Property::default();
544        let missing = Property::default();
545        let snapshot = Property::default();
546        let reads = Cell::new(0);
547        let len = || {
548            count.get(|| {
549                reads.set(reads.get() + 1);
550                model.len()
551            })
552        };
553        let row = || second.get(|| model.row(1));
554        let tail = || missing.get(|| model.row(3));
555        let values = || snapshot.get(|| model.snapshot());
556
557        assert_eq!((len(), row(), tail()), (3, Some(20), None));
558        assert_eq!(values(), [10, 20, 30]);
559        assert!(model.set_row(0, 11));
560        assert_eq!((len(), row()), (3, Some(20)));
561        assert_eq!(reads.get(), 1);
562        assert_eq!(values(), [11, 20, 30]);
563        assert!(!model.set_row(0, 11));
564        assert!(!model.set_row(9, 11));
565        model.push(40);
566        assert_eq!((len(), row(), tail()), (4, Some(20), Some(40)));
567        assert!(model.insert(0, 5));
568        assert_eq!((len(), row(), tail()), (5, Some(11), Some(30)));
569        assert_eq!(model.remove(0), Some(5));
570        assert_eq!((len(), row(), tail()), (4, Some(20), Some(40)));
571    }
572}