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 })
126 }
127
128 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 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 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 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 #[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 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 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 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 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 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 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 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}