1mod diffable;
2mod types;
3
4pub use diffable::*;
5pub use types::*;
6
7use crate::myers;
8use crate::myers::Edit;
9use std::collections::{HashMap, HashSet};
10
11pub fn diff<T: Diffable>(old: &T, new: &T) -> Vec<Change<T::P>> {
30 diff_nodes(old.to_node(), new.to_node(), vec![])
31}
32
33fn diff_nodes<P: Primitive>(old: Node<P>, new: Node<P>, path: Vec<PathSegment>) -> Vec<Change<P>> {
34 match (old, new) {
35 (Node::Leaf(a), Node::Leaf(b)) => {
36 if a != b {
37 vec![Change {
38 path,
39 kind: ChangeKind::Modified(a, b),
40 }]
41 } else {
42 vec![]
43 }
44 }
45 (Node::Sequence(a), Node::Sequence(b)) => {
46 let result = myers::diff(&a, &b);
47 if result.iter().all(|e| matches!(e, Edit::Equal(_))) {
48 vec![]
49 } else {
50 vec![Change {
51 path,
52 kind: ChangeKind::SequenceChange(result),
53 }]
54 }
55 }
56 (Node::Map(a), Node::Map(b)) => {
57 let keys_a = a.keys().collect::<HashSet<_>>();
58 let keys_b = b.keys().collect::<HashSet<_>>();
59
60 keys_a
61 .union(&keys_b)
62 .flat_map(|key| {
63 let mut new_path = path.clone();
64 new_path.push(PathSegment::Key(key.to_string()));
65 match (a.get(*key), b.get(*key)) {
66 (Some(va), Some(vb)) => diff_nodes(va.clone(), vb.clone(), new_path),
67 (Some(va), None) => match va {
68 Node::Leaf(ve) => vec![Change {
69 path: new_path,
70 kind: ChangeKind::Removed(ve.clone()),
71 }],
72 ve => vec![Change {
73 path: new_path,
74 kind: ChangeKind::NodeRemoved(ve.clone()),
75 }],
76 },
77 (None, Some(vb)) => match vb {
78 Node::Leaf(ve) => vec![Change {
79 path: new_path,
80 kind: ChangeKind::Added(ve.clone()),
81 }],
82 ve => vec![Change {
83 path: new_path,
84 kind: ChangeKind::NodeAdded(ve.clone()),
85 }],
86 },
87 (None, None) => unreachable!(),
88 }
89 })
90 .collect()
91 }
92 (old, new) => vec![
93 Change {
94 path: path.clone(),
95 kind: ChangeKind::NodeRemoved(old),
96 },
97 Change {
98 path,
99 kind: ChangeKind::NodeAdded(new),
100 },
101 ],
102 }
103}
104
105pub fn apply<T: Diffable>(old: &T, changes: &[Change<T::P>]) -> T {
107 let new_node = changes.iter().fold(old.to_node(), apply_change);
108 T::from_node(new_node)
109}
110
111fn apply_change<P: Primitive>(node: Node<P>, change: &Change<P>) -> Node<P> {
112 match (node, change.path.first()) {
113 (Node::Map(m), Some(PathSegment::Key(k))) => apply_to_map(m, k, change),
114 (Node::Sequence(_), _) => match &change.kind {
115 ChangeKind::SequenceChange(edits) => apply_to_sequence(edits.to_vec()),
116 _ => unreachable!(),
117 },
118
119 (Node::Leaf(_), _) => match &change.kind {
120 ChangeKind::Modified(_, new) => Node::Leaf(new.clone()),
121 _ => unreachable!(),
122 },
123 (Node::Map(_), _) => unreachable!(),
124 }
125}
126
127fn apply_to_map<P: Primitive>(
128 map: HashMap<String, Node<P>>,
129 key: &String,
130 change: &Change<P>,
131) -> Node<P> {
132 let mut new_map = map;
133 let node = if change.path.len() > 1 {
134 let new_change = Change {
135 kind: change.kind.clone(),
136 path: change.path[1..].to_vec(),
137 };
138 new_map.insert(
139 key.to_string(),
140 apply_change(new_map.get(key).unwrap().clone(), &new_change),
141 );
142 new_map
143 } else {
144 match &change.kind {
145 ChangeKind::NodeAdded(new) => new_map.insert(key.clone(), new.clone()),
146 ChangeKind::Added(new) => new_map.insert(key.clone(), Node::Leaf(new.clone())),
147 ChangeKind::NodeRemoved(_) | ChangeKind::Removed(_) => new_map.remove(key),
148 ChangeKind::Modified(_, new) => new_map.insert(key.clone(), Node::Leaf(new.clone())),
149 _ => unreachable!(),
150 };
151 new_map
152 };
153
154 Node::Map(node)
155}
156
157fn apply_to_sequence<P: Primitive>(edits: Vec<Edit<Node<P>>>) -> Node<P> {
158 let mut result = vec![];
159 for edit in edits {
160 match edit {
161 Edit::Equal(v) => result.push(v.clone()),
162 Edit::Insert(v) => result.push(v.clone()),
163 Edit::Delete(_) => {}
164 }
165 }
166 Node::Sequence(result)
167}
168
169#[cfg(test)]
170mod tests {
171 use super::*;
172
173 #[test]
174 fn test_key_added() {
175 let mut a = HashMap::new();
176 a.insert("a".to_string(), 1);
177 let mut b = HashMap::new();
178 b.insert("a".to_string(), 1);
179 b.insert("c".to_string(), 2);
180 let result = diff(&a, &b);
181 assert_eq!(
182 result,
183 vec![Change {
184 path: vec![PathSegment::Key("c".to_string())],
185 kind: ChangeKind::Added(2)
186 }]
187 );
188 }
189
190 #[test]
191 fn test_key_removed() {
192 let mut a = HashMap::new();
193 a.insert("a".to_string(), 1);
194 a.insert("c".to_string(), 2);
195 let mut b = HashMap::new();
196 b.insert("a".to_string(), 1);
197 let result = diff(&a, &b);
198 assert_eq!(
199 result,
200 vec![Change {
201 path: vec![PathSegment::Key("c".to_string())],
202 kind: ChangeKind::Removed(2)
203 }]
204 );
205 }
206
207 #[test]
208 fn test_nested_map() {
209 let mut a = HashMap::new();
210 let mut nested_a = HashMap::new();
211 nested_a.insert("nested".to_string(), 1);
212 a.insert("b".to_string(), nested_a);
213 let mut b = HashMap::new();
214 let mut nested_b = HashMap::new();
215 nested_b.insert("nested".to_string(), 2);
216 b.insert("b".to_string(), nested_b);
217 let result = diff(&a, &b);
218 assert_eq!(
219 result,
220 vec![Change {
221 path: vec![
222 PathSegment::Key("b".to_string()),
223 PathSegment::Key("nested".to_string())
224 ],
225 kind: ChangeKind::Modified(1, 2)
226 }]
227 );
228 }
229
230 #[test]
231 fn test_sequence_of_primitives() {
232 let a = vec![1, 2, 3];
233 let b = vec![1, 3, 4];
234 let result = diff(&a, &b);
235 assert_eq!(
236 result,
237 vec![Change {
238 path: vec![],
239 kind: ChangeKind::SequenceChange(vec![
240 Edit::Equal(Node::Leaf(1)),
241 Edit::Delete(Node::Leaf(2)),
242 Edit::Equal(Node::Leaf(3)),
243 Edit::Insert(Node::Leaf(4))
244 ])
245 }]
246 );
247 }
248
249 #[test]
250 fn test_no_changes() {
251 let a = vec![1, 2, 3];
252 let result = diff(&a, &a);
253
254 assert_eq!(result, vec![]);
255 }
256}