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