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*/
314pub fn diff_changes<T: PartialEq + Clone + Debug>(d: &[diff::Result<&T>]) -> Vec<Change<T>> {
315    let mut changes = vec![];
316    let mut removed = 0;
317    for (i, j) in d.iter().enumerate() {
318        let n = i - removed;
319        match j {
320            diff::Result::Left(_) => {
321                remove(n, &mut changes);
322                removed += 1;
323            }
324            diff::Result::Right(r) => {
325                insert(n, *r, &mut changes);
326            }
327            _ => {}
328        }
329    }
330    changes
331}
332
333/**
334Calculate the diff between `a` and `b` via [`diff::slice`] and convert to a [`Vec<Change>`].
335
336[`diff::slice`]: https://docs.rs/diff/latest/diff/fn.diff.html
337*/
338pub fn diff_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
339    diff_changes(&diff::slice(a, b))
340}
341
342/**
343Convert a slice of [`lcs_diff::DiffResult`] into a [`Vec<Change>`].
344
345Note that unlike [`wu_changes`], `b` is not needed to clone inserted items because they are included
346in the [`lcs_diff::DiffResult`].
347
348[`lcs_diff::DiffResult`]: https://docs.rs/lcs-diff/latest/lcs_diff/enum.DiffResult.html
349*/
350pub fn lcs_changes<T: PartialEq + Clone + Debug>(d: &[lcs_diff::DiffResult<T>]) -> Vec<Change<T>> {
351    let mut changes = vec![];
352    let mut removed = 0;
353    let mut added = 0;
354    for i in d {
355        match i {
356            lcs_diff::DiffResult::Removed(r) => {
357                let n = r.old_index.unwrap() + added - removed;
358                remove(n, &mut changes);
359                removed += 1;
360            }
361            lcs_diff::DiffResult::Added(r) => {
362                let n = r.new_index.unwrap();
363                insert(n, &r.data, &mut changes);
364                added += 1;
365            }
366            _ => {}
367        }
368    }
369    changes
370}
371
372/**
373Calculate the diff between `a` and `b` via [`lcs_diff::diff`] and convert to a [`Vec<Change>`].
374
375[`lcs_diff::diff`]: https://docs.rs/lcs-diff/latest/lcs_diff/fn.diff.html
376*/
377pub fn lcs_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
378    lcs_changes(lcs_diff::diff(a, b).as_slice())
379}
380
381/**
382Convert a slice of [`wu_diff::DiffResult`] into a [`Vec<Change>`].
383
384Note that unlike [`lcs_changes()`], `b` is needed to clone inserted items because they are not
385included in the [`wu_diff::DiffResult`].
386
387[`wu_diff::DiffResult`]: https://docs.rs/wu-diff/latest/wu_diff/enum.DiffResult.html
388*/
389pub fn wu_changes<T: PartialEq + Clone + Debug>(
390    d: &[wu_diff::DiffResult],
391    b: &[T],
392) -> Vec<Change<T>> {
393    let mut changes = vec![];
394    let mut removed = 0;
395    let mut added = 0;
396    for i in d {
397        match i {
398            wu_diff::DiffResult::Removed(r) => {
399                let n = r.old_index.unwrap() + added - removed;
400                remove(n, &mut changes);
401                removed += 1;
402            }
403            wu_diff::DiffResult::Added(r) => {
404                let n = r.new_index.unwrap();
405                insert(n, &b[n], &mut changes);
406                added += 1;
407            }
408            _ => {}
409        }
410    }
411    changes
412}
413
414/**
415Calculate the diff between `a` and `b` via [`wu_diff::diff`] and convert to a [`Vec<Change>`].
416
417[`wu_diff::diff`]: https://docs.rs/wu-diff/latest/wu_diff/fn.diff.html
418*/
419pub fn wu_diff<T: PartialEq + Clone + Debug>(a: &[T], b: &[T]) -> Vec<Change<T>> {
420    wu_changes(&wu_diff::diff(a, b), b)
421}
422
423/// Reproduce `b` from the `a` slice and [`Vec<Change>`].
424pub fn patch<T: PartialEq + Clone + Debug>(a: &[T], changes: &[Change<T>]) -> Vec<T> {
425    let mut a = a.to_vec();
426    for i in changes {
427        match i {
428            Change::Remove(n) => {
429                a.remove(*n);
430            }
431            Change::Insert((n, item)) => {
432                a.insert(*n, item.clone());
433            }
434            Change::Update((n, item)) => {
435                a.remove(*n);
436                a.insert(*n, item.clone());
437            }
438        }
439    }
440    a
441}
slice_diff_patch/lib.rs

slice_diff_patch/
lib.rs
