1use core::ops::Range;
4
5use alloc::{boxed::Box, vec::Vec};
6
7use super::diff::diff;
8
9#[derive(Clone, Debug, PartialEq, Eq, Hash)]
18pub enum Edit {
19 Remove(Range<usize>),
21 Insert(Range<usize>),
23 Move {
29 from: usize,
31 to: usize,
33 },
34 Update(Range<usize>),
40}
41
42impl Edit {
43 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#[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 Many(Box<[Edit]>),
98}
99
100impl CollectionChange {
101 #[must_use]
103 pub const fn unchanged() -> Self {
104 Self { repr: Repr::Empty }
105 }
106
107 #[must_use]
109 pub fn inserted(range: Range<usize>) -> Self {
110 Self::from(Edit::Insert(range))
111 }
112
113 #[must_use]
115 pub fn removed(range: Range<usize>) -> Self {
116 Self::from(Edit::Remove(range))
117 }
118
119 #[must_use]
121 pub fn updated(range: Range<usize>) -> Self {
122 Self::from(Edit::Update(range))
123 }
124
125 #[must_use]
127 pub fn moved(from: usize, to: usize) -> Self {
128 Self::from(Edit::Move { from, to })
129 }
130
131 #[must_use]
134 pub fn populated(start: usize, len: usize) -> Self {
135 Self::inserted(start..start + len)
136 }
137
138 #[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 #[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 #[must_use]
183 pub const fn is_empty(&self) -> bool {
184 matches!(self.repr, Repr::Empty)
185 }
186
187 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 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 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 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 #[must_use]
221 pub fn is_updated(&self, index: usize) -> bool {
222 self.updates().any(|range| range.contains(&index))
223 }
224
225 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 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#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
307enum Origin {
308 Old(usize),
310 New(usize),
313}
314
315#[derive(Clone, Copy, Debug)]
317struct Tag {
318 origin: Origin,
319 updated: bool,
322}
323
324fn 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#[derive(Clone, Debug)]
355pub struct ChangeLog {
356 len: usize,
358 current: Option<Vec<Tag>>,
361 fresh: usize,
363}
364
365impl ChangeLog {
366 #[must_use]
368 pub const fn new(len: usize) -> Self {
369 Self {
370 len,
371 current: None,
372 fresh: 0,
373 }
374 }
375
376 #[must_use]
382 pub const fn is_empty(&self) -> bool {
383 self.current.is_none()
384 }
385
386 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 for range in change.updates() {
409 for tag in &mut current[range] {
410 tag.updated = true;
411 }
412 }
413 }
414
415 #[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 ¤t,
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 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 #[derive(Clone, Copy, Debug, PartialEq)]
487 struct Item {
488 tag: usize,
489 updates: usize,
490 }
491
492 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 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 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 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(¤t[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 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 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 let mut log = ChangeLog::new(3);
690 log.push(&CollectionChange::unchanged());
691 assert!(log.is_empty());
692 assert!(log.finish().is_empty());
693 }
694}