slice_diff_patch/
lib.rs

1#[doc = include_str!("../README.md")]
2#[cfg(test)]
3mod tests {
4    use super::*;
5
6    fn display<T: PartialEq + Clone + Debug>(a: &[T], b: &[T], d: &[Change<T>]) {
7        println!("a = {:?}", a);
8        println!("b = {:?}", b);
9        for i in d {
10            println!("i = {:?}", i);
11        }
12    }
13
14    fn test_states<T: PartialEq + Clone + Debug>(
15        states: &[&[T]],
16        diff: &dyn Fn(&[T], &[T]) -> Vec<Change<T>>,
17    ) {
18        for i in 0..states.len() - 1 {
19            let a = &states[i];
20            let b = &states[i + 1];
21            let d = diff(&a, &b);
22            display(&a, &b, &d);
23            let c = patch(&a, &d);
24            assert_eq!(&c, b);
25        }
26    }
27
28    #[test]
29    fn diff_int() {
30        test_states(
31            &[
32                &[],
33                &[2],
34                &[2, 6],
35                &[2, 4, 6],
36                &[2, 4, 6, 8],
37                &[1, 2, 4, 6, 8],
38                &[1, 2, 3, 5, 8],
39                &[1, 2, 3, 5, 8],
40                &[2, 3, 5, 8],
41                &[2, 5, 8],
42                &[2, 5],
43                &[],
44            ],
45            &diff_diff,
46        );
47    }
48
49    #[test]
50    fn diff_str() {
51        test_states(
52            &[
53                &[],
54                &["alpha"],
55                &["alpha", "delta"],
56                &["alpha", "bravo", "delta"],
57                &["alpha", "bravo", "charlie", "delta"],
58                &["pre-alpha", "alpha", "pre-bravo", "pre-charlie", "delta"],
59                &["pre-alpha", "alpha", "pre-bravo", "pre-charlie"],
60                &["pre-alpha", "pre-bravo", "pre-charlie"],
61                &["pre-bravo", "pre-charlie"],
62                &["pre-bravo"],
63                &[],
64            ],
65            &diff_diff,
66        );
67    }
68
69    #[test]
70    fn lcs_int() {
71        test_states(
72            &[
73                &[],
74                &[2],
75                &[2, 6],
76                &[2, 4, 6],
77                &[2, 4, 6, 8],
78                &[1, 2, 4, 6, 8],
79                &[1, 2, 3, 5, 8],
80                &[1, 2, 3, 5, 8],
81                &[2, 3, 5, 8],
82                &[2, 5, 8],
83                &[2, 5],
84                &[],
85            ],
86            &lcs_diff,
87        );
88    }
89
90    #[test]
91    fn lcs_str() {
92        test_states(
93            &[
94                &[],
95                &["alpha"],
96                &["alpha", "delta"],
97                &["alpha", "bravo", "delta"],
98                &["alpha", "bravo", "charlie", "delta"],
99                &["pre-alpha", "alpha", "pre-bravo", "pre-charlie", "delta"],
100                &["pre-alpha", "alpha", "pre-bravo", "pre-charlie"],
101                &["pre-alpha", "pre-bravo", "pre-charlie"],
102                &["pre-bravo", "pre-charlie"],
103                &["pre-bravo"],
104                &[],
105            ],
106            &lcs_diff,
107        );
108    }
109
110    #[test]
111    fn wu_int() {
112        test_states(
113            &[
114                &[],
115                &[2],
116                &[2, 6],
117                &[2, 4, 6],
118                &[2, 4, 6, 8],
119                &[1, 2, 4, 6, 8],
120                &[1, 2, 3, 5, 8],
121                &[1, 2, 3, 5, 8],
122                &[2, 3, 5, 8],
123                &[2, 5, 8],
124                &[2, 5],
125                &[],
126            ],
127            &wu_diff,
128        );
129    }
130
131    #[test]
132    fn wu_str() {
133        test_states(
134            &[
135                &[],
136                &["alpha"],
137                &["alpha", "delta"],
138                &["alpha", "bravo", "delta"],
139                &["alpha", "bravo", "charlie", "delta"],
140                &["pre-alpha", "alpha", "pre-bravo", "pre-charlie", "delta"],
141                &["pre-alpha", "alpha", "pre-bravo", "pre-charlie"],
142                &["pre-alpha", "pre-bravo", "pre-charlie"],
143                &["pre-bravo", "pre-charlie"],
144                &["pre-bravo"],
145                &[],
146            ],
147            &wu_diff,
148        );
149    }
150
151    fn update<T: PartialEq + Clone + Debug>(
152        a: &[T],
153        b: &[T],
154        changes: Vec<Change<T>>,
155        diff: &dyn Fn(&[T], &[T]) -> Vec<Change<T>>,
156    ) {
157        assert_eq!(diff(&a, &b), changes);
158    }
159
160    #[test]
161    fn diff_update() {
162        update(&[1], &[2], vec![Change::Update((0, 2))], &diff_diff);
163        update(&[1, 2], &[1, 3], vec![Change::Update((1, 3))], &diff_diff);
164        update(
165            &[1, 2, 3],
166            &[1, 2, 4],
167            vec![Change::Update((2, 4))],
168            &diff_diff,
169        );
170        update(
171            &["alpha"],
172            &["bravo"],
173            vec![Change::Update((0, "bravo"))],
174            &diff_diff,
175        );
176        update(
177            &["alpha", "bravo"],
178            &["alpha", "charlie"],
179            vec![Change::Update((1, "charlie"))],
180            &diff_diff,
181        );
182        update(
183            &["alpha", "bravo", "charlie"],
184            &["alpha", "bravo", "delta"],
185            vec![Change::Update((2, "delta"))],
186            &diff_diff,
187        );
188    }
189
190    #[test]
191    fn lcs_update() {
192        update(&[1], &[2], vec![Change::Update((0, 2))], &lcs_diff);
193        update(&[1, 2], &[1, 3], vec![Change::Update((1, 3))], &lcs_diff);
194        update(
195            &[1, 2, 3],
196            &[1, 2, 4],
197            vec![Change::Update((2, 4))],
198            &lcs_diff,
199        );
200        update(
201            &["alpha"],
202            &["bravo"],
203            vec![Change::Update((0, "bravo"))],
204            &lcs_diff,
205        );
206        update(
207            &["alpha", "bravo"],
208            &["alpha", "charlie"],
209            vec![Change::Update((1, "charlie"))],
210            &lcs_diff,
211        );
212        update(
213            &["alpha", "bravo", "charlie"],
214            &["alpha", "bravo", "delta"],
215            vec![Change::Update((2, "delta"))],
216            &lcs_diff,
217        );
218    }
219
220    #[test]
221    fn wu_update() {
222        update(&[1], &[2], vec![Change::Update((0, 2))], &wu_diff);
223        update(&[1, 2], &[1, 3], vec![Change::Update((1, 3))], &wu_diff);
224        update(
225            &[1, 2, 3],
226            &[1, 2, 4],
227            vec![Change::Update((2, 4))],
228            &wu_diff,
229        );
230        update(
231            &["alpha"],
232            &["bravo"],
233            vec![Change::Update((0, "bravo"))],
234            &wu_diff,
235        );
236        update(
237            &["alpha", "bravo"],
238            &["alpha", "charlie"],
239            vec![Change::Update((1, "charlie"))],
240            &wu_diff,
241        );
242        update(
243            &["alpha", "bravo", "charlie"],
244            &["alpha", "bravo", "delta"],
245            vec![Change::Update((2, "delta"))],
246            &wu_diff,
247        );
248    }
249}
250
251use std::fmt::Debug;
252
253/// Process an insert.
254///
255/// * Upgrade `Change::Remove(n), Change::Insert((n, item))` to `Change::Update((n, item))`.
256pub fn insert<T: PartialEq + Clone + Debug>(n: usize, item: &T, changes: &mut Vec<Change<T>>) {
257    if let Some(prev_change) = changes.pop() {
258        if let Change::Remove(prev_n) = prev_change {
259            if n == prev_n {
260                changes.push(Change::Update((n, (*item).clone())));
261                return;
262            }
263        }
264        changes.push(prev_change);
265    }
266    changes.push(Change::Insert((n, (*item).clone())));
267}
268
269/// Process a remove.
270///
271/// * Upgrade `Change::Insert((n, item)), Change::Remove(n+1)` to `Change::Update((n, item))`.
272pub fn remove<T: PartialEq + Clone + Debug>(n: usize, changes: &mut Vec<Change<T>>) {
273    if let Some(prev_change) = changes.pop() {
274        if let Change::Insert((prev_n, ref item)) = prev_change {
275            if n == prev_n + 1 {
276                changes.push(Change::Update((prev_n, item.clone())));
277                return;
278            }
279        }
280        changes.push(prev_change);
281    }
282    changes.push(Change::Remove(n));
283}
284
285/// Abstraction for [`diff::Result`], [`lcs_diff::DiffResult`], and [`wu_diff::DiffResult`] that
286/// excludes a variant for common sequence, stores a clone of inserted items, and indices relate
287/// iteratively to `a`.
288///
289/// [`diff::Result`]: https://docs.rs/diff/latest/diff/enum.Result.html
290/// [`lcs_diff::DiffResult`]: https://docs.rs/lcs-diff/latest/lcs_diff/enum.DiffResult.html
291/// [`wu_diff::DiffResult`]: https://docs.rs/wu-diff/latest/wu_diff/enum.DiffResult.html
292#[derive(Debug, Clone, PartialEq)]
293pub enum Change<T: PartialEq + Clone + Debug> {
294    Remove(usize),
295    Insert((usize, T)),
296    Update((usize, T)),
297}
298
299/// Convert a slice of [`diff::Result`] into a [`Vec<Change>`].
300///
301/// Note that unlike [`wu_changes`], `b` is not needed to clone inserted items because they are
302/// included in the [`diff::Result`].
303///
304/// [`diff::Result`]: https://docs.rs/diff/latest/diff/enum.Result.html
305pub fn diff_changes<T: PartialEq + Clone + Debug>(d: &[diff::Result<&T>]) -> Vec<Change<T>> {
306    let mut changes = vec![];
307    let mut removed = 0;
308    for (i, j) in d.iter().enumerate() {
309        let n = i - removed;
310        match j {
311            diff::Result::Left(_) => {
312                remove(n, &mut changes);
313                removed += 1;
314            }
315            diff::Result::Right(r) => {
316                insert(n, *r, &mut changes);
317            }
318            _ => {}
319        }
320    }
321    changes
322}
323
324/// Calculate the diff between `a` and `b` via [`diff::slice`] and convert to a [`Vec<Change>`].
325///
326/// [`diff::slice`]: https://docs.rs/diff/latest/diff/fn.diff.html
327pub fn diff_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
328    diff_changes(&diff::slice(a, b))
329}
330
331/// Convert a slice of [`lcs_diff::DiffResult`] into a [`Vec<Change>`].
332///
333/// Note that unlike [`wu_changes`], `b` is not needed to clone inserted items because they are
334/// included in the [`lcs_diff::DiffResult`].
335///
336/// [`lcs_diff::DiffResult`]: https://docs.rs/lcs-diff/latest/lcs_diff/enum.DiffResult.html
337pub fn lcs_changes<T: PartialEq + Clone + Debug>(d: &[lcs_diff::DiffResult<T>]) -> Vec<Change<T>> {
338    let mut changes = vec![];
339    let mut removed = 0;
340    let mut added = 0;
341    for i in d {
342        match i {
343            lcs_diff::DiffResult::Removed(r) => {
344                let n = r.old_index.unwrap() + added - removed;
345                remove(n, &mut changes);
346                removed += 1;
347            }
348            lcs_diff::DiffResult::Added(r) => {
349                let n = r.new_index.unwrap();
350                insert(n, &r.data, &mut changes);
351                added += 1;
352            }
353            _ => {}
354        }
355    }
356    changes
357}
358
359/// Calculate the diff between `a` and `b` via [`lcs_diff::diff`] and convert to a [`Vec<Change>`].
360///
361/// [`lcs_diff::diff`]: https://docs.rs/lcs-diff/latest/lcs_diff/fn.diff.html
362pub fn lcs_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
363    lcs_changes(lcs_diff::diff(a, b).as_slice())
364}
365
366/// Convert a slice of [`wu_diff::DiffResult`] into a [`Vec<Change>`].
367///
368/// Note that unlike [`lcs_changes()`], `b` is needed to clone inserted items because they are not
369/// included in the [`wu_diff::DiffResult`].
370///
371/// [`wu_diff::DiffResult`]: https://docs.rs/wu-diff/latest/wu_diff/enum.DiffResult.html
372pub fn wu_changes<T: PartialEq + Clone + Debug>(
373    d: &[wu_diff::DiffResult],
374    b: &[T],
375) -> Vec<Change<T>> {
376    let mut changes = vec![];
377    let mut removed = 0;
378    let mut added = 0;
379    for i in d {
380        match i {
381            wu_diff::DiffResult::Removed(r) => {
382                let n = r.old_index.unwrap() + added - removed;
383                remove(n, &mut changes);
384                removed += 1;
385            }
386            wu_diff::DiffResult::Added(r) => {
387                let n = r.new_index.unwrap();
388                insert(n, &b[n], &mut changes);
389                added += 1;
390            }
391            _ => {}
392        }
393    }
394    changes
395}
396
397/// Calculate the diff between `a` and `b` via [`wu_diff::diff`] and convert to a [`Vec<Change>`].
398///
399/// [`wu_diff::diff`]: https://docs.rs/wu-diff/latest/wu_diff/fn.diff.html
400pub fn wu_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
401    wu_changes(&wu_diff::diff(a, b), b)
402}
403
404/// Reproduce `b` from the `a` slice and [`Vec<Change>`].
405pub fn patch<T: PartialEq + Clone + Debug>(a: &[T], changes: &[Change<T>]) -> Vec<T> {
406    let mut a = a.to_vec();
407    for i in changes {
408        match i {
409            Change::Remove(n) => {
410                a.remove(*n);
411            }
412            Change::Insert((n, item)) => {
413                a.insert(*n, item.clone());
414            }
415            Change::Update((n, item)) => {
416                a.remove(*n);
417                a.insert(*n, item.clone());
418            }
419        }
420    }
421    a
422}
slice_diff_patch/lib.rs

slice_diff_patch/
lib.rs
