1#![no_std]
2
3extern crate alloc;
11#[cfg(feature = "std")]
12extern crate std;
13
14mod collections;
15
16use core::hash::Hash;
17
18use crate::collections::{
19 Box,
20 HashMap,
21 Vec,
22 VecDeque,
23};
24
25pub trait DiffNode: Sized {
28 type Key: Eq + Hash;
29 type Modifications;
30
31 #[cfg_attr(feature = "hotpath", hotpath::measure)]
34 fn diff(&self, previous: Option<&Self>, diff: &mut Diff<Self::Modifications>) {
35 diff_inner(self, previous, diff, false);
36 }
37
38 fn key(&self) -> &Self::Key;
39 fn path(&self) -> &[u32];
40 fn children(&self) -> &[Self];
41
42 fn same_children(&self, _previous: &Self) -> bool {
44 false
45 }
46
47 fn compatible(&self, previous: &Self) -> bool;
49
50 fn modifications(&self, previous: &Self) -> Option<Self::Modifications>;
52
53 #[cfg(debug_assertions)]
55 fn validate_children(&self) {}
56}
57
58#[derive(Debug)]
60pub struct Diff<Modifications> {
61 pub added: Vec<Box<[u32]>>,
62 pub modified: Vec<(Box<[u32]>, Modifications)>,
63 pub removed: Vec<Box<[u32]>>,
64 pub moved: HashMap<Box<[u32]>, Vec<(u32, u32)>>,
65}
66
67impl<Modifications> Default for Diff<Modifications> {
68 fn default() -> Self {
69 Self {
70 added: Vec::new(),
71 modified: Vec::new(),
72 removed: Vec::new(),
73 moved: HashMap::default(),
74 }
75 }
76}
77
78fn diff_inner<Node: DiffNode>(
79 current: &Node,
80 previous: Option<&Node>,
81 diff: &mut Diff<Node::Modifications>,
82 parent_removed: bool,
83) {
84 let Some(previous) = previous else {
86 diff.added.push(current.path().into());
87
88 for child in current.children() {
89 diff_inner(child, None, diff, false);
90 }
91
92 return;
93 };
94
95 if !current.compatible(previous) {
97 diff.removed.push(previous.path().into());
98 diff_inner(current, None, diff, false);
99 return;
100 }
101
102 let removed_here = current.key() != previous.key() || parent_removed;
104 if removed_here {
105 diff.added.push(current.path().into());
106 diff.removed.push(previous.path().into());
107 } else {
108 if let Some(modifications) = current.modifications(previous) {
109 diff.modified.push((current.path().into(), modifications));
110 }
111
112 if let (Some((&new_index, parent)), Some(&old_index)) =
114 (current.path().split_last(), previous.path().last())
115 && new_index != old_index
116 {
117 diff.moved
118 .entry(parent.into())
119 .or_default()
120 .push((old_index, new_index));
121 }
122 }
123
124 if !removed_here && current.same_children(previous) {
125 return;
126 }
127
128 #[cfg(debug_assertions)]
129 current.validate_children();
130
131 let current_children = current.children();
132 let previous_children = previous.children();
133
134 let mut start = 0;
136 while start < current_children.len() && start < previous_children.len() {
137 if current_children[start].key() != previous_children[start].key() {
138 break;
139 }
140
141 diff_inner(
142 ¤t_children[start],
143 Some(&previous_children[start]),
144 diff,
145 removed_here,
146 );
147 start += 1;
148 }
149
150 if start < current_children.len() || start < previous_children.len() {
151 let mut previous_keys = HashMap::<&Node::Key, VecDeque<usize>>::default();
153 for (index, child) in previous_children.iter().enumerate().skip(start) {
154 previous_keys
155 .entry(child.key())
156 .or_default()
157 .push_back(index);
158 }
159
160 for child in ¤t_children[start..] {
162 if let Some(old_index) = previous_keys
163 .get_mut(child.key())
164 .and_then(VecDeque::pop_front)
165 {
166 diff_inner(
167 child,
168 Some(&previous_children[old_index]),
169 diff,
170 removed_here,
171 );
172 } else {
173 diff_inner(child, None, diff, false);
174 }
175 }
176
177 for indices in previous_keys.values() {
179 for index in indices {
180 diff.removed.push(previous_children[*index].path().into());
181 }
182 }
183 }
184}