Skip to main content

nami_core/collection/
change.rs

1//! What a collection notification changed.
2
3use core::ops::Range;
4
5use alloc::{boxed::Box, vec::Vec};
6
7use super::diff::diff;
8
9/// One step of a [`CollectionChange`].
10///
11/// Indices follow batch-update semantics, the model `UIKit`'s
12/// `performBatchUpdates` and diffable data sources use: removals and the
13/// source of a move name positions in the *previous* snapshot; insertions,
14/// updates and the destination of a move name positions in the *new*
15/// snapshot. Edits are not applied one after another; every index refers to
16/// one of the two snapshots as a whole.
17#[derive(Clone, Debug, PartialEq, Eq, Hash)]
18pub enum Edit {
19    /// The items at this range of the previous snapshot no longer exist.
20    Remove(Range<usize>),
21    /// The items at this range of the new snapshot did not exist before.
22    Insert(Range<usize>),
23    /// The item at `from` in the previous snapshot is now at `to` in the new
24    /// snapshot, and its order relative to the other surviving items changed.
25    ///
26    /// Items that only shift because of insertions or removals around them
27    /// are not reported as moves.
28    Move {
29        /// Position in the previous snapshot.
30        from: usize,
31        /// Position in the new snapshot.
32        to: usize,
33    },
34    /// The items at this range of the new snapshot kept their identity but
35    /// their content may differ.
36    ///
37    /// An item can be both moved and updated; it then appears in a
38    /// [`Edit::Move`] and in an [`Edit::Update`] covering its new position.
39    Update(Range<usize>),
40}
41
42impl Edit {
43    /// Sort key of the canonical edit order: removals, insertions, moves,
44    /// updates, each ascending by position.
45    const fn order(&self) -> (u8, usize) {
46        match self {
47            Self::Remove(range) => (0, range.start),
48            Self::Insert(range) => (1, range.start),
49            Self::Move { to, .. } => (2, *to),
50            Self::Update(range) => (3, range.start),
51        }
52    }
53
54    const fn range_mut(&mut self) -> Option<&mut Range<usize>> {
55        match self {
56            Self::Remove(range) | Self::Insert(range) | Self::Update(range) => Some(range),
57            Self::Move { .. } => None,
58        }
59    }
60
61    const fn is_empty(&self) -> bool {
62        match self {
63            Self::Remove(range) | Self::Insert(range) | Self::Update(range) => {
64                range.start >= range.end
65            }
66            Self::Move { .. } => false,
67        }
68    }
69}
70
71/// What a collection notification changed, aligned by item identity.
72///
73/// A notification carries the new snapshot together with the edits that turn
74/// the previous snapshot into it; see [`Edit`] for which snapshot each index
75/// refers to. Indices are collection-wide: a watcher subscribed to a
76/// sub-range still receives positions relative to index 0 of the whole
77/// collection and intersects them with its range itself.
78///
79/// Collections compute the change by item id (see
80/// [`Identifiable::Id`](super::Identifiable::Id)): a reordered or front-inserted
81/// replacement reports moves and insertions instead of rewriting every
82/// position.
83///
84/// A change made of a single edit is stored inline, so the common mutations
85/// (`push`, `insert`, `remove`, `set`) do not allocate for it.
86#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
87pub struct CollectionChange {
88    repr: Repr,
89}
90
91#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
92enum Repr {
93    #[default]
94    Empty,
95    One(Edit),
96    /// Two or more edits in canonical order.
97    Many(Box<[Edit]>),
98}
99
100impl CollectionChange {
101    /// A notification that touched nothing.
102    #[must_use]
103    pub const fn unchanged() -> Self {
104        Self { repr: Repr::Empty }
105    }
106
107    /// `range` of the new snapshot was inserted.
108    #[must_use]
109    pub fn inserted(range: Range<usize>) -> Self {
110        Self::from(Edit::Insert(range))
111    }
112
113    /// `range` of the previous snapshot was removed.
114    #[must_use]
115    pub fn removed(range: Range<usize>) -> Self {
116        Self::from(Edit::Remove(range))
117    }
118
119    /// The items at `range` of the new snapshot were updated in place.
120    #[must_use]
121    pub fn updated(range: Range<usize>) -> Self {
122        Self::from(Edit::Update(range))
123    }
124
125    /// The item at `from` (previous snapshot) moved to `to` (new snapshot).
126    #[must_use]
127    pub fn moved(from: usize, to: usize) -> Self {
128        Self::from(Edit::Move { from, to })
129    }
130
131    /// `len` items appear from nothing starting at `start`, for example to
132    /// seed a view with contents read through [`Collection::get_item`](crate::collection::Collection::get_item).
133    #[must_use]
134    pub fn populated(start: usize, len: usize) -> Self {
135        Self::inserted(start..start + len)
136    }
137
138    /// Builds a change from edits in any order.
139    ///
140    /// Empty ranges are dropped, the edits are sorted into canonical order
141    /// (removals, insertions, moves, updates, each ascending) and adjacent or
142    /// overlapping ranges of the same kind are merged, so two changes that
143    /// describe the same edits compare equal.
144    #[must_use]
145    pub fn from_edits(edits: impl IntoIterator<Item = Edit>) -> Self {
146        let mut edits: Vec<Edit> = edits.into_iter().filter(|edit| !edit.is_empty()).collect();
147        edits.sort_by_key(Edit::order);
148        let mut merged: Vec<Edit> = Vec::with_capacity(edits.len());
149        for mut edit in edits {
150            if let Some(last) = merged.last_mut()
151                && last.order().0 == edit.order().0
152                && let (Some(previous), Some(next)) = (last.range_mut(), edit.range_mut())
153                && next.start <= previous.end
154            {
155                previous.end = previous.end.max(next.end);
156                continue;
157            }
158            merged.push(edit);
159        }
160        if merged.len() > 1 {
161            return Self {
162                repr: Repr::Many(merged.into_boxed_slice()),
163            };
164        }
165        merged.pop().map_or_else(Self::unchanged, |edit| Self {
166            repr: Repr::One(edit),
167        })
168    }
169
170    /// The edits in canonical order: removals, insertions, moves, updates,
171    /// each ascending by position.
172    #[must_use]
173    pub fn edits(&self) -> &[Edit] {
174        match &self.repr {
175            Repr::Empty => &[],
176            Repr::One(edit) => core::slice::from_ref(edit),
177            Repr::Many(edits) => edits,
178        }
179    }
180
181    /// True when the notification touched nothing.
182    #[must_use]
183    pub const fn is_empty(&self) -> bool {
184        matches!(self.repr, Repr::Empty)
185    }
186
187    /// Ranges of the previous snapshot that were removed, ascending.
188    pub fn removals(&self) -> impl Iterator<Item = Range<usize>> + '_ {
189        self.edits().iter().filter_map(|edit| match edit {
190            Edit::Remove(range) => Some(range.clone()),
191            _ => None,
192        })
193    }
194
195    /// Ranges of the new snapshot that were inserted, ascending.
196    pub fn insertions(&self) -> impl Iterator<Item = Range<usize>> + '_ {
197        self.edits().iter().filter_map(|edit| match edit {
198            Edit::Insert(range) => Some(range.clone()),
199            _ => None,
200        })
201    }
202
203    /// Moves as `(from, to)` pairs, ascending by destination.
204    pub fn moves(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
205        self.edits().iter().filter_map(|edit| match edit {
206            Edit::Move { from, to } => Some((*from, *to)),
207            _ => None,
208        })
209    }
210
211    /// Ranges of the new snapshot updated in place, ascending.
212    pub fn updates(&self) -> impl Iterator<Item = Range<usize>> + '_ {
213        self.edits().iter().filter_map(|edit| match edit {
214            Edit::Update(range) => Some(range.clone()),
215            _ => None,
216        })
217    }
218
219    /// Whether the item at `index` of the new snapshot was updated in place.
220    #[must_use]
221    pub fn is_updated(&self, index: usize) -> bool {
222        self.updates().any(|range| range.contains(&index))
223    }
224
225    /// Applies the structural part of this change to `items`, a vector
226    /// parallel to the previous snapshot, leaving it parallel to the new
227    /// one.
228    ///
229    /// Removed elements are dropped, moved and untouched elements are carried
230    /// to their new positions, and every inserted position is filled by
231    /// `insert(new_index)`. Updates are not applied: the caller refreshes the
232    /// positions [`Self::updates`] names.
233    ///
234    /// This is how a consumer that keeps per-item state (views, native
235    /// cells) follows a collection without diffing it.
236    ///
237    /// # Panics
238    ///
239    /// Panics if the change names positions `items` does not have, which
240    /// means it was not computed against a snapshot of `items`' length.
241    pub fn apply<U>(&self, items: &mut Vec<U>, mut insert: impl FnMut(usize) -> U) {
242        if self.is_empty() {
243            return;
244        }
245        let removed: usize = self.removals().map(|range| range.len()).sum();
246        let inserted: usize = self.insertions().map(|range| range.len()).sum();
247        let new_len = (items.len() + inserted)
248            .checked_sub(removed)
249            .expect("the change removes more items than the collection had");
250
251        let mut slots: Vec<Option<U>> = items.drain(..).map(Some).collect();
252        for range in self.removals() {
253            for slot in &mut slots[range] {
254                *slot = None;
255            }
256        }
257        // Moves come out in ascending destination order.
258        let mut moved = self
259            .moves()
260            .map(|(from, to)| {
261                let item = slots[from]
262                    .take()
263                    .expect("a moved item must exist in the previous snapshot");
264                (to, item)
265            })
266            .collect::<Vec<_>>()
267            .into_iter()
268            .peekable();
269        let mut survivors = slots.into_iter().flatten();
270        let mut insertions = self.insertions().peekable();
271
272        items.reserve(new_len);
273        for index in 0..new_len {
274            while insertions.next_if(|range| range.end <= index).is_some() {}
275            if insertions
276                .peek()
277                .is_some_and(|range| range.contains(&index))
278            {
279                items.push(insert(index));
280            } else if let Some((_, item)) = moved.next_if(|(to, _)| *to == index) {
281                items.push(item);
282            } else {
283                items.push(
284                    survivors
285                        .next()
286                        .expect("the change does not match the collection it describes"),
287                );
288            }
289        }
290    }
291}
292
293impl From<Edit> for CollectionChange {
294    fn from(edit: Edit) -> Self {
295        if edit.is_empty() {
296            Self::unchanged()
297        } else {
298            Self {
299                repr: Repr::One(edit),
300            }
301        }
302    }
303}
304
305/// Where the item at a tracked position came from.
306#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
307enum Origin {
308    /// The item was at this position when the log started.
309    Old(usize),
310    /// The item was inserted by a recorded change; a fresh counter keeps it
311    /// distinct from initial items and from other inserts.
312    New(usize),
313}
314
315/// One position of the collection a [`ChangeLog`] tracks.
316#[derive(Clone, Copy, Debug)]
317struct Tag {
318    origin: Origin,
319    /// Whether a recorded change reported the item at this position as
320    /// updated.
321    updated: bool,
322}
323
324/// The tags of a collection of `len` items that no change has touched yet.
325fn initial_tags(len: usize) -> Vec<Tag> {
326    (0..len)
327        .map(|index| Tag {
328            origin: Origin::Old(index),
329            updated: false,
330        })
331        .collect()
332}
333
334/// Accumulates the [`CollectionChange`]s made to one collection and
335/// composes them into the single change from the first snapshot to the
336/// last.
337///
338/// A collection that holds back its notifications — batched updates, for
339/// example — pushes each change it makes and, when it finally notifies,
340/// sends [`Self::finish`] instead of the individual changes.
341///
342/// Items are tracked by where they came from, never by value, so no bound
343/// on the item type is involved and a remove followed by an insert of an
344/// equal value stays a remove plus an insert. Moves are composed through
345/// [`diff`](crate::collection::diff)'s longest increasing subsequence, so
346/// the result reports as few as possible.
347///
348/// Each pushed change is in the indices of the collection as it was right
349/// before that change; see [`Edit`] for which snapshot each index of an
350/// edit refers to.
351///
352/// The tracker is only allocated when the first non-empty change is
353/// pushed: a log that records nothing allocates nothing.
354#[derive(Clone, Debug)]
355pub struct ChangeLog {
356    /// The collection's length when the log started.
357    len: usize,
358    /// One tag per position of the current snapshot; `None` until the
359    /// first push.
360    current: Option<Vec<Tag>>,
361    /// The next fresh [`Origin::New`] tag.
362    fresh: usize,
363}
364
365impl ChangeLog {
366    /// Starts a log for a collection of `len` items.
367    #[must_use]
368    pub const fn new(len: usize) -> Self {
369        Self {
370            len,
371            current: None,
372            fresh: 0,
373        }
374    }
375
376    /// Whether no change has been recorded yet.
377    ///
378    /// This is about pushes, not the outcome: changes that later ones undo
379    /// still count as recorded, and [`Self::finish`] then returns an empty
380    /// [`CollectionChange`].
381    #[must_use]
382    pub const fn is_empty(&self) -> bool {
383        self.current.is_none()
384    }
385
386    /// Records `change`, expressed in the indices of the collection as it
387    /// is after the previously recorded changes.
388    ///
389    /// # Panics
390    ///
391    /// Panics if `change` names positions the collection does not have,
392    /// like [`CollectionChange::apply`].
393    pub fn push(&mut self, change: &CollectionChange) {
394        if change.is_empty() {
395            return;
396        }
397        let current = self.current.get_or_insert_with(|| initial_tags(self.len));
398        change.apply(current, |_| {
399            let tag = Tag {
400                origin: Origin::New(self.fresh),
401                updated: false,
402            };
403            self.fresh += 1;
404            tag
405        });
406        // `updates()` names positions of the new snapshot, which `apply`
407        // has just left `current` parallel to, moved items included.
408        for range in change.updates() {
409            for tag in &mut current[range] {
410                tag.updated = true;
411            }
412        }
413    }
414
415    /// The single change from the snapshot the log started on to the
416    /// current one.
417    #[must_use]
418    pub fn finish(self) -> CollectionChange {
419        let Some(current) = self.current else {
420            return CollectionChange::unchanged();
421        };
422        let initial = initial_tags(self.len);
423        diff(
424            &initial,
425            &current,
426            |_, tag| tag.origin,
427            |_, new| !new.updated,
428        )
429    }
430}
431
432#[cfg(test)]
433mod tests {
434    use alloc::{vec, vec::Vec};
435
436    use super::{ChangeLog, CollectionChange, Edit};
437
438    #[test]
439    fn from_edits_sorts_and_merges() {
440        let change = CollectionChange::from_edits([
441            Edit::Update(4..5),
442            Edit::Insert(1..2),
443            Edit::Remove(3..4),
444            Edit::Insert(0..1),
445            Edit::Remove(2..3),
446            Edit::Insert(5..5),
447        ]);
448        assert_eq!(
449            change.edits(),
450            [Edit::Remove(2..4), Edit::Insert(0..2), Edit::Update(4..5)]
451        );
452    }
453
454    #[test]
455    fn single_edits_and_empty_ranges() {
456        assert!(CollectionChange::inserted(3..3).is_empty());
457        assert_eq!(
458            CollectionChange::from_edits([Edit::Insert(0..1)]),
459            CollectionChange::inserted(0..1)
460        );
461    }
462
463    #[test]
464    fn apply_follows_removals_insertions_and_moves() {
465        // previous: a b c d e  ->  new: x d a c e   (b removed, x inserted, d moved)
466        let change = CollectionChange::from_edits([
467            Edit::Remove(1..2),
468            Edit::Insert(0..1),
469            Edit::Move { from: 3, to: 1 },
470        ]);
471        let mut items = vec!['a', 'b', 'c', 'd', 'e'];
472        change.apply(&mut items, |_| 'x');
473        assert_eq!(items, vec!['x', 'd', 'a', 'c', 'e']);
474    }
475
476    #[test]
477    fn apply_on_empty_change_is_a_no_op() {
478        let mut items: Vec<u8> = vec![1, 2, 3];
479        CollectionChange::unchanged().apply(&mut items, |_| unreachable!());
480        assert_eq!(items, vec![1, 2, 3]);
481    }
482
483    /// A test item: `tag` identifies where the item came from — below the
484    /// initial length an initial position, at or above it an inserted one —
485    /// and `updates` counts the updates it lived through.
486    #[derive(Clone, Copy, Debug, PartialEq)]
487    struct Item {
488        tag: usize,
489        updates: usize,
490    }
491
492    /// Every structurally valid single-edit change on a collection of
493    /// `len` items — insert, remove, update and move at every valid
494    /// position or range — plus a few multi-edit changes as `from_edits`
495    /// merges them.
496    fn changes_on(len: usize) -> Vec<CollectionChange> {
497        let mut changes = Vec::new();
498        for start in 0..=len {
499            for size in 1..=2 {
500                changes.push(CollectionChange::inserted(start..start + size));
501            }
502        }
503        for start in 0..len {
504            for end in start + 1..=len {
505                changes.push(CollectionChange::removed(start..end));
506                changes.push(CollectionChange::updated(start..end));
507            }
508        }
509        for from in 0..len {
510            for to in 0..len {
511                if from != to {
512                    changes.push(CollectionChange::moved(from, to));
513                }
514            }
515        }
516        changes.push(CollectionChange::from_edits([
517            Edit::Insert(0..1),
518            Edit::Update(0..1),
519        ]));
520        if len >= 1 {
521            changes.push(CollectionChange::from_edits([
522                Edit::Remove(0..1),
523                Edit::Insert(len - 1..len),
524            ]));
525            changes.push(CollectionChange::from_edits([
526                Edit::Remove(len - 1..len),
527                Edit::Insert(0..1),
528            ]));
529        }
530        if len >= 2 {
531            changes.push(CollectionChange::from_edits([
532                Edit::Remove(0..1),
533                Edit::Update(0..1),
534            ]));
535            changes.push(CollectionChange::from_edits([
536                Edit::Move {
537                    from: 0,
538                    to: len - 1,
539                },
540                Edit::Update(len - 1..len),
541            ]));
542            changes.push(CollectionChange::from_edits([
543                Edit::Insert(0..1),
544                Edit::Remove(len - 1..len),
545            ]));
546        }
547        changes
548    }
549
550    /// Applies `change` to `items`: inserted positions get a fresh tag,
551    /// updated positions count up.
552    fn apply_one(items: &mut Vec<Item>, change: &CollectionChange, next_tag: &mut usize) {
553        change.apply(items, |_| {
554            let tag = *next_tag;
555            *next_tag += 1;
556            Item { tag, updates: 0 }
557        });
558        for range in change.updates() {
559            for item in &mut items[range] {
560                item.updates += 1;
561            }
562        }
563    }
564
565    /// The composed change applied to `initial` must reproduce `current`,
566    /// with updates reported for exactly the surviving items the sequence
567    /// updated — an inserted item is reported as an insert, never an
568    /// update.
569    fn check(initial: &[Item], current: &[Item], sequence: &[CollectionChange]) {
570        let mut log = ChangeLog::new(initial.len());
571        for change in sequence {
572            log.push(change);
573        }
574        assert_eq!(log.is_empty(), sequence.is_empty());
575        let result = log.finish();
576
577        // `apply` fills inserted positions in ascending order, and the
578        // surviving inserted items are exactly the fresh-tag items of the
579        // final snapshot, in order.
580        let mut inserted = current
581            .iter()
582            .filter(|item| item.tag >= initial.len())
583            .copied();
584        let mut composed = initial.to_vec();
585        result.apply(&mut composed, |_| {
586            inserted
587                .next()
588                .expect("the composed change inserts an item the sequence never made")
589        });
590        assert!(inserted.next().is_none(), "{result:?}");
591        for range in result.updates() {
592            composed[range.clone()].copy_from_slice(&current[range]);
593        }
594        assert_eq!(composed, current, "{sequence:?} composed to {result:?}");
595        for (index, item) in current.iter().enumerate() {
596            assert_eq!(
597                result.is_updated(index),
598                item.tag < initial.len() && item.updates > 0,
599                "position {index} of {sequence:?} composed to {result:?}"
600            );
601        }
602        assert_eq!(result.is_empty(), current == initial, "{result:?}");
603    }
604
605    /// Runs `check` for every sequence of up to `depth` changes starting
606    /// from `items`, returning how many sequences were checked.
607    fn enumerate(
608        initial: &[Item],
609        items: &[Item],
610        sequence: &mut Vec<CollectionChange>,
611        next_tag: &mut usize,
612        depth: usize,
613    ) -> usize {
614        let mut sequences = 0;
615        for change in changes_on(items.len()) {
616            let mut next_items = items.to_vec();
617            apply_one(&mut next_items, &change, next_tag);
618            sequence.push(change);
619            sequences += 1;
620            check(initial, &next_items, sequence);
621            if depth > 1 {
622                sequences += enumerate(initial, &next_items, sequence, next_tag, depth - 1);
623            }
624            sequence.pop();
625        }
626        sequences
627    }
628
629    #[test]
630    fn exhaustive_composition_matches_change_by_change() {
631        // Every sequence of up to three changes over initial lengths 0..=3.
632        let mut sequences = 0;
633        for len in 0..=3_usize {
634            let initial: Vec<Item> = (0..len).map(|tag| Item { tag, updates: 0 }).collect();
635            let mut sequence = Vec::new();
636            let mut next_tag = len;
637            sequences += 1;
638            check(&initial, &initial, &sequence);
639            sequences += enumerate(&initial, &initial, &mut sequence, &mut next_tag, 3);
640        }
641        assert_eq!(sequences, 73_373);
642    }
643
644    #[test]
645    fn remove_then_insert_stays_a_remove_and_an_insert() {
646        let mut log = ChangeLog::new(1);
647        log.push(&CollectionChange::removed(0..1));
648        log.push(&CollectionChange::inserted(0..1));
649        assert_eq!(
650            log.finish(),
651            CollectionChange::from_edits([Edit::Remove(0..1), Edit::Insert(0..1)])
652        );
653    }
654
655    #[test]
656    fn insert_then_remove_composes_to_nothing() {
657        let mut log = ChangeLog::new(1);
658        log.push(&CollectionChange::inserted(0..1));
659        log.push(&CollectionChange::removed(0..1));
660        assert!(log.finish().is_empty());
661    }
662
663    #[test]
664    fn update_then_move_reports_the_update_at_the_new_position() {
665        let mut log = ChangeLog::new(3);
666        log.push(&CollectionChange::updated(0..1));
667        log.push(&CollectionChange::moved(0, 2));
668        assert_eq!(
669            log.finish(),
670            CollectionChange::from_edits([Edit::Move { from: 0, to: 2 }, Edit::Update(2..3)])
671        );
672    }
673
674    #[test]
675    fn an_update_undone_by_removal_leaves_no_update() {
676        let mut log = ChangeLog::new(2);
677        log.push(&CollectionChange::updated(0..1));
678        log.push(&CollectionChange::removed(0..1));
679        assert_eq!(log.finish(), CollectionChange::removed(0..1));
680    }
681
682    #[test]
683    fn a_log_without_changes_is_empty() {
684        let log = ChangeLog::new(3);
685        assert!(log.is_empty());
686        assert!(log.finish().is_empty());
687
688        // An empty change records nothing.
689        let mut log = ChangeLog::new(3);
690        log.push(&CollectionChange::unchanged());
691        assert!(log.is_empty());
692        assert!(log.finish().is_empty());
693    }
694}