use core::ops::Range;
use alloc::{boxed::Box, vec::Vec};
use super::diff::diff;
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Edit {
Remove(Range<usize>),
Insert(Range<usize>),
Move {
from: usize,
to: usize,
},
Update(Range<usize>),
}
impl Edit {
const fn order(&self) -> (u8, usize) {
match self {
Self::Remove(range) => (0, range.start),
Self::Insert(range) => (1, range.start),
Self::Move { to, .. } => (2, *to),
Self::Update(range) => (3, range.start),
}
}
const fn range_mut(&mut self) -> Option<&mut Range<usize>> {
match self {
Self::Remove(range) | Self::Insert(range) | Self::Update(range) => Some(range),
Self::Move { .. } => None,
}
}
const fn is_empty(&self) -> bool {
match self {
Self::Remove(range) | Self::Insert(range) | Self::Update(range) => {
range.start >= range.end
}
Self::Move { .. } => false,
}
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
pub struct CollectionChange {
repr: Repr,
}
#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
enum Repr {
#[default]
Empty,
One(Edit),
Many(Box<[Edit]>),
}
impl CollectionChange {
#[must_use]
pub const fn unchanged() -> Self {
Self { repr: Repr::Empty }
}
#[must_use]
pub fn inserted(range: Range<usize>) -> Self {
Self::from(Edit::Insert(range))
}
#[must_use]
pub fn removed(range: Range<usize>) -> Self {
Self::from(Edit::Remove(range))
}
#[must_use]
pub fn updated(range: Range<usize>) -> Self {
Self::from(Edit::Update(range))
}
#[must_use]
pub fn moved(from: usize, to: usize) -> Self {
Self::from(Edit::Move { from, to })
}
#[must_use]
pub fn populated(start: usize, len: usize) -> Self {
Self::inserted(start..start + len)
}
#[must_use]
pub fn from_edits(edits: impl IntoIterator<Item = Edit>) -> Self {
let mut edits: Vec<Edit> = edits.into_iter().filter(|edit| !edit.is_empty()).collect();
edits.sort_by_key(Edit::order);
let mut merged: Vec<Edit> = Vec::with_capacity(edits.len());
for mut edit in edits {
if let Some(last) = merged.last_mut()
&& last.order().0 == edit.order().0
&& let (Some(previous), Some(next)) = (last.range_mut(), edit.range_mut())
&& next.start <= previous.end
{
previous.end = previous.end.max(next.end);
continue;
}
merged.push(edit);
}
if merged.len() > 1 {
return Self {
repr: Repr::Many(merged.into_boxed_slice()),
};
}
merged.pop().map_or_else(Self::unchanged, |edit| Self {
repr: Repr::One(edit),
})
}
#[must_use]
pub fn edits(&self) -> &[Edit] {
match &self.repr {
Repr::Empty => &[],
Repr::One(edit) => core::slice::from_ref(edit),
Repr::Many(edits) => edits,
}
}
#[must_use]
pub const fn is_empty(&self) -> bool {
matches!(self.repr, Repr::Empty)
}
pub fn removals(&self) -> impl Iterator<Item = Range<usize>> + '_ {
self.edits().iter().filter_map(|edit| match edit {
Edit::Remove(range) => Some(range.clone()),
_ => None,
})
}
pub fn insertions(&self) -> impl Iterator<Item = Range<usize>> + '_ {
self.edits().iter().filter_map(|edit| match edit {
Edit::Insert(range) => Some(range.clone()),
_ => None,
})
}
pub fn moves(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
self.edits().iter().filter_map(|edit| match edit {
Edit::Move { from, to } => Some((*from, *to)),
_ => None,
})
}
pub fn updates(&self) -> impl Iterator<Item = Range<usize>> + '_ {
self.edits().iter().filter_map(|edit| match edit {
Edit::Update(range) => Some(range.clone()),
_ => None,
})
}
#[must_use]
pub fn is_updated(&self, index: usize) -> bool {
self.updates().any(|range| range.contains(&index))
}
pub fn apply<U>(&self, items: &mut Vec<U>, mut insert: impl FnMut(usize) -> U) {
if self.is_empty() {
return;
}
let removed: usize = self.removals().map(|range| range.len()).sum();
let inserted: usize = self.insertions().map(|range| range.len()).sum();
let new_len = (items.len() + inserted)
.checked_sub(removed)
.expect("the change removes more items than the collection had");
let mut slots: Vec<Option<U>> = items.drain(..).map(Some).collect();
for range in self.removals() {
for slot in &mut slots[range] {
*slot = None;
}
}
let mut moved = self
.moves()
.map(|(from, to)| {
let item = slots[from]
.take()
.expect("a moved item must exist in the previous snapshot");
(to, item)
})
.collect::<Vec<_>>()
.into_iter()
.peekable();
let mut survivors = slots.into_iter().flatten();
let mut insertions = self.insertions().peekable();
items.reserve(new_len);
for index in 0..new_len {
while insertions.next_if(|range| range.end <= index).is_some() {}
if insertions
.peek()
.is_some_and(|range| range.contains(&index))
{
items.push(insert(index));
} else if let Some((_, item)) = moved.next_if(|(to, _)| *to == index) {
items.push(item);
} else {
items.push(
survivors
.next()
.expect("the change does not match the collection it describes"),
);
}
}
}
}
impl From<Edit> for CollectionChange {
fn from(edit: Edit) -> Self {
if edit.is_empty() {
Self::unchanged()
} else {
Self {
repr: Repr::One(edit),
}
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Origin {
Old(usize),
New(usize),
}
#[derive(Clone, Copy, Debug)]
struct Tag {
origin: Origin,
updated: bool,
}
fn initial_tags(len: usize) -> Vec<Tag> {
(0..len)
.map(|index| Tag {
origin: Origin::Old(index),
updated: false,
})
.collect()
}
#[derive(Clone, Debug)]
pub struct ChangeLog {
len: usize,
current: Option<Vec<Tag>>,
fresh: usize,
}
impl ChangeLog {
#[must_use]
pub const fn new(len: usize) -> Self {
Self {
len,
current: None,
fresh: 0,
}
}
#[must_use]
pub const fn is_empty(&self) -> bool {
self.current.is_none()
}
pub fn push(&mut self, change: &CollectionChange) {
if change.is_empty() {
return;
}
let current = self.current.get_or_insert_with(|| initial_tags(self.len));
change.apply(current, |_| {
let tag = Tag {
origin: Origin::New(self.fresh),
updated: false,
};
self.fresh += 1;
tag
});
for range in change.updates() {
for tag in &mut current[range] {
tag.updated = true;
}
}
}
#[must_use]
pub fn finish(self) -> CollectionChange {
let Some(current) = self.current else {
return CollectionChange::unchanged();
};
let initial = initial_tags(self.len);
diff(
&initial,
¤t,
|_, tag| tag.origin,
|_, new| !new.updated,
)
}
}
#[cfg(test)]
mod tests {
use alloc::{vec, vec::Vec};
use super::{ChangeLog, CollectionChange, Edit};
#[test]
fn from_edits_sorts_and_merges() {
let change = CollectionChange::from_edits([
Edit::Update(4..5),
Edit::Insert(1..2),
Edit::Remove(3..4),
Edit::Insert(0..1),
Edit::Remove(2..3),
Edit::Insert(5..5),
]);
assert_eq!(
change.edits(),
[Edit::Remove(2..4), Edit::Insert(0..2), Edit::Update(4..5)]
);
}
#[test]
fn single_edits_and_empty_ranges() {
assert!(CollectionChange::inserted(3..3).is_empty());
assert_eq!(
CollectionChange::from_edits([Edit::Insert(0..1)]),
CollectionChange::inserted(0..1)
);
}
#[test]
fn apply_follows_removals_insertions_and_moves() {
let change = CollectionChange::from_edits([
Edit::Remove(1..2),
Edit::Insert(0..1),
Edit::Move { from: 3, to: 1 },
]);
let mut items = vec!['a', 'b', 'c', 'd', 'e'];
change.apply(&mut items, |_| 'x');
assert_eq!(items, vec!['x', 'd', 'a', 'c', 'e']);
}
#[test]
fn apply_on_empty_change_is_a_no_op() {
let mut items: Vec<u8> = vec![1, 2, 3];
CollectionChange::unchanged().apply(&mut items, |_| unreachable!());
assert_eq!(items, vec![1, 2, 3]);
}
#[derive(Clone, Copy, Debug, PartialEq)]
struct Item {
tag: usize,
updates: usize,
}
fn changes_on(len: usize) -> Vec<CollectionChange> {
let mut changes = Vec::new();
for start in 0..=len {
for size in 1..=2 {
changes.push(CollectionChange::inserted(start..start + size));
}
}
for start in 0..len {
for end in start + 1..=len {
changes.push(CollectionChange::removed(start..end));
changes.push(CollectionChange::updated(start..end));
}
}
for from in 0..len {
for to in 0..len {
if from != to {
changes.push(CollectionChange::moved(from, to));
}
}
}
changes.push(CollectionChange::from_edits([
Edit::Insert(0..1),
Edit::Update(0..1),
]));
if len >= 1 {
changes.push(CollectionChange::from_edits([
Edit::Remove(0..1),
Edit::Insert(len - 1..len),
]));
changes.push(CollectionChange::from_edits([
Edit::Remove(len - 1..len),
Edit::Insert(0..1),
]));
}
if len >= 2 {
changes.push(CollectionChange::from_edits([
Edit::Remove(0..1),
Edit::Update(0..1),
]));
changes.push(CollectionChange::from_edits([
Edit::Move {
from: 0,
to: len - 1,
},
Edit::Update(len - 1..len),
]));
changes.push(CollectionChange::from_edits([
Edit::Insert(0..1),
Edit::Remove(len - 1..len),
]));
}
changes
}
fn apply_one(items: &mut Vec<Item>, change: &CollectionChange, next_tag: &mut usize) {
change.apply(items, |_| {
let tag = *next_tag;
*next_tag += 1;
Item { tag, updates: 0 }
});
for range in change.updates() {
for item in &mut items[range] {
item.updates += 1;
}
}
}
fn check(initial: &[Item], current: &[Item], sequence: &[CollectionChange]) {
let mut log = ChangeLog::new(initial.len());
for change in sequence {
log.push(change);
}
assert_eq!(log.is_empty(), sequence.is_empty());
let result = log.finish();
let mut inserted = current
.iter()
.filter(|item| item.tag >= initial.len())
.copied();
let mut composed = initial.to_vec();
result.apply(&mut composed, |_| {
inserted
.next()
.expect("the composed change inserts an item the sequence never made")
});
assert!(inserted.next().is_none(), "{result:?}");
for range in result.updates() {
composed[range.clone()].copy_from_slice(¤t[range]);
}
assert_eq!(composed, current, "{sequence:?} composed to {result:?}");
for (index, item) in current.iter().enumerate() {
assert_eq!(
result.is_updated(index),
item.tag < initial.len() && item.updates > 0,
"position {index} of {sequence:?} composed to {result:?}"
);
}
assert_eq!(result.is_empty(), current == initial, "{result:?}");
}
fn enumerate(
initial: &[Item],
items: &[Item],
sequence: &mut Vec<CollectionChange>,
next_tag: &mut usize,
depth: usize,
) -> usize {
let mut sequences = 0;
for change in changes_on(items.len()) {
let mut next_items = items.to_vec();
apply_one(&mut next_items, &change, next_tag);
sequence.push(change);
sequences += 1;
check(initial, &next_items, sequence);
if depth > 1 {
sequences += enumerate(initial, &next_items, sequence, next_tag, depth - 1);
}
sequence.pop();
}
sequences
}
#[test]
fn exhaustive_composition_matches_change_by_change() {
let mut sequences = 0;
for len in 0..=3_usize {
let initial: Vec<Item> = (0..len).map(|tag| Item { tag, updates: 0 }).collect();
let mut sequence = Vec::new();
let mut next_tag = len;
sequences += 1;
check(&initial, &initial, &sequence);
sequences += enumerate(&initial, &initial, &mut sequence, &mut next_tag, 3);
}
assert_eq!(sequences, 73_373);
}
#[test]
fn remove_then_insert_stays_a_remove_and_an_insert() {
let mut log = ChangeLog::new(1);
log.push(&CollectionChange::removed(0..1));
log.push(&CollectionChange::inserted(0..1));
assert_eq!(
log.finish(),
CollectionChange::from_edits([Edit::Remove(0..1), Edit::Insert(0..1)])
);
}
#[test]
fn insert_then_remove_composes_to_nothing() {
let mut log = ChangeLog::new(1);
log.push(&CollectionChange::inserted(0..1));
log.push(&CollectionChange::removed(0..1));
assert!(log.finish().is_empty());
}
#[test]
fn update_then_move_reports_the_update_at_the_new_position() {
let mut log = ChangeLog::new(3);
log.push(&CollectionChange::updated(0..1));
log.push(&CollectionChange::moved(0, 2));
assert_eq!(
log.finish(),
CollectionChange::from_edits([Edit::Move { from: 0, to: 2 }, Edit::Update(2..3)])
);
}
#[test]
fn an_update_undone_by_removal_leaves_no_update() {
let mut log = ChangeLog::new(2);
log.push(&CollectionChange::updated(0..1));
log.push(&CollectionChange::removed(0..1));
assert_eq!(log.finish(), CollectionChange::removed(0..1));
}
#[test]
fn a_log_without_changes_is_empty() {
let log = ChangeLog::new(3);
assert!(log.is_empty());
assert!(log.finish().is_empty());
let mut log = ChangeLog::new(3);
log.push(&CollectionChange::unchanged());
assert!(log.is_empty());
assert!(log.finish().is_empty());
}
}