slice_diff_patch/
lib.rs

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

slice_diff_patch/
lib.rs
