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
56pub 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 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 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 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 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 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 #[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 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 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 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 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 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 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 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}