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/**
255Process an insert.
256
257- Upgrade `Change::Remove(n), Change::Insert((n, item))` to `Change::Update((n, item))`.
258*/
259pub fn insert<T: PartialEq + Clone + Debug>(n: usize, item: &T, changes: &mut Vec<Change<T>>) {
260    if let Some(prev_change) = changes.pop() {
261        if let Change::Remove(prev_n) = prev_change
262            && n == prev_n
263        {
264            changes.push(Change::Update((n, (*item).clone())));
265            return;
266        }
267        changes.push(prev_change);
268    }
269    changes.push(Change::Insert((n, (*item).clone())));
270}
271
272/*
273Process a remove.
274
275- Upgrade `Change::Insert((n, item)), Change::Remove(n+1)` to `Change::Update((n, item))`.
276*/
277pub fn remove<T: PartialEq + Clone + Debug>(n: usize, changes: &mut Vec<Change<T>>) {
278    if let Some(prev_change) = changes.pop() {
279        if let Change::Insert((prev_n, ref item)) = prev_change
280            && n == prev_n + 1
281        {
282            changes.push(Change::Update((prev_n, item.clone())));
283            return;
284        }
285        changes.push(prev_change);
286    }
287    changes.push(Change::Remove(n));
288}
289
290/**
291Abstraction for [`diff::Result`], [`lcs_diff::DiffResult`], and [`wu_diff::DiffResult`] that
292excludes a variant for common sequence, stores a clone of inserted items, and indices relate
293iteratively to `a`.
294
295[`diff::Result`]: https://docs.rs/diff/latest/diff/enum.Result.html
296[`lcs_diff::DiffResult`]: https://docs.rs/lcs-diff/latest/lcs_diff/enum.DiffResult.html
297[`wu_diff::DiffResult`]: https://docs.rs/wu-diff/latest/wu_diff/enum.DiffResult.html
298*/
299#[derive(Debug, Clone, PartialEq)]
300pub enum Change<T: PartialEq + Clone + Debug> {
301    Remove(usize),
302    Insert((usize, T)),
303    Update((usize, T)),
304}
305
306/**
307Convert a slice of [`diff::Result`] into a [`Vec<Change>`].
308
309Note that unlike [`wu_changes`], `b` is not needed to clone inserted items because they are included
310in the [`diff::Result`].
311
312[`diff::Result`]: https://docs.rs/diff/latest/diff/enum.Result.html
313*/
314#[must_use]
315pub fn diff_changes<T: PartialEq + Clone + Debug>(d: &[diff::Result<&T>]) -> Vec<Change<T>> {
316    let mut changes = vec![];
317    let mut removed = 0;
318    for (i, j) in d.iter().enumerate() {
319        let n = i - removed;
320        match j {
321            diff::Result::Left(_) => {
322                remove(n, &mut changes);
323                removed += 1;
324            }
325            diff::Result::Right(r) => {
326                insert(n, *r, &mut changes);
327            }
328            diff::Result::Both(..) => {}
329        }
330    }
331    changes
332}
333
334/**
335Calculate the diff between `a` and `b` via [`diff::slice`] and convert to a [`Vec<Change>`].
336
337[`diff::slice`]: https://docs.rs/diff/latest/diff/fn.diff.html
338*/
339pub fn diff_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
340    diff_changes(&diff::slice(a, b))
341}
342
343/**
344Convert a slice of [`lcs_diff::DiffResult`] into a [`Vec<Change>`].
345
346Note that unlike [`wu_changes`], `b` is not needed to clone inserted items because they are included
347in the [`lcs_diff::DiffResult`].
348
349[`lcs_diff::DiffResult`]: https://docs.rs/lcs-diff/latest/lcs_diff/enum.DiffResult.html
350
351# Panics
352
353Panics if not able to resolve the old index of a removed item or the new index of an added item
354*/
355pub fn lcs_changes<T: PartialEq + Clone + Debug>(d: &[lcs_diff::DiffResult<T>]) -> Vec<Change<T>> {
356    let mut changes = vec![];
357    let mut removed = 0;
358    let mut added = 0;
359    for i in d {
360        match i {
361            lcs_diff::DiffResult::Removed(r) => {
362                let n = r.old_index.unwrap() + added - removed;
363                remove(n, &mut changes);
364                removed += 1;
365            }
366            lcs_diff::DiffResult::Added(r) => {
367                let n = r.new_index.unwrap();
368                insert(n, &r.data, &mut changes);
369                added += 1;
370            }
371            lcs_diff::DiffResult::Common(_) => {}
372        }
373    }
374    changes
375}
376
377/**
378Calculate the diff between `a` and `b` via [`lcs_diff::diff`] and convert to a [`Vec<Change>`].
379
380[`lcs_diff::diff`]: https://docs.rs/lcs-diff/latest/lcs_diff/fn.diff.html
381*/
382pub fn lcs_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
383    lcs_changes(lcs_diff::diff(a, b).as_slice())
384}
385
386/**
387Convert a slice of [`wu_diff::DiffResult`] into a [`Vec<Change>`].
388
389Note that unlike [`lcs_changes()`], `b` is needed to clone inserted items because they are not
390included in the [`wu_diff::DiffResult`].
391
392[`wu_diff::DiffResult`]: https://docs.rs/wu-diff/latest/wu_diff/enum.DiffResult.html
393
394# Panics
395
396Panics if not able to resolve the old index of a removed item or the new index of an added item
397*/
398pub fn wu_changes<T: PartialEq + Clone + Debug>(
399    d: &[wu_diff::DiffResult],
400    b: &[T],
401) -> Vec<Change<T>> {
402    let mut changes = vec![];
403    let mut removed = 0;
404    let mut added = 0;
405    for i in d {
406        match i {
407            wu_diff::DiffResult::Removed(r) => {
408                let n = r.old_index.unwrap() + added - removed;
409                remove(n, &mut changes);
410                removed += 1;
411            }
412            wu_diff::DiffResult::Added(r) => {
413                let n = r.new_index.unwrap();
414                insert(n, &b[n], &mut changes);
415                added += 1;
416            }
417            wu_diff::DiffResult::Common(_) => {}
418        }
419    }
420    changes
421}
422
423/**
424Calculate the diff between `a` and `b` via [`wu_diff::diff`] and convert to a [`Vec<Change>`].
425
426[`wu_diff::diff`]: https://docs.rs/wu-diff/latest/wu_diff/fn.diff.html
427*/
428pub fn wu_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
429    wu_changes(&wu_diff::diff(a, b), b)
430}
431
432/// Reproduce `b` from the `a` slice and [`Vec<Change>`].
433pub fn patch<T: PartialEq + Clone + Debug>(a: &[T], changes: &[Change<T>]) -> Vec<T> {
434    let mut a = a.to_vec();
435    for i in changes {
436        match i {
437            Change::Remove(n) => {
438                a.remove(*n);
439            }
440            Change::Insert((n, item)) => {
441                a.insert(*n, item.clone());
442            }
443            Change::Update((n, item)) => {
444                a.remove(*n);
445                a.insert(*n, item.clone());
446            }
447        }
448    }
449    a
450}
slice_diff_patch/lib.rs

slice_diff_patch/
lib.rs
