similar/algorithms/
patience.rs

Help
1//! Patience diff algorithm.
2//!
3//! * time: `O(N log N + M log M + (N+M)D)`
4//! * space: `O(N+M)`
5//!
6//! Tends to give more human-readable outputs. See [Bram Cohen's blog
7//! post](https://bramcohen.livejournal.com/73318.html) describing it.
8//!
9//! This is based on the patience implementation of [pijul](https://pijul.org/)
10//! by Pierre-Étienne Meunier.
11use std::hash::Hash;
12use std::ops::{Index, Range};
13
14use crate::algorithms::{myers, DiffHook, NoFinishHook, Replace};
15use crate::deadline_support::Instant;
16
17use super::utils::{unique, UniqueItem};
18
19/// Patience diff algorithm.
20///
21/// Diff `old`, between indices `old_range` and `new` between indices `new_range`.
22pub fn diff<Old, New, D>(
23    d: &mut D,
24    old: &Old,
25    old_range: Range<usize>,
26    new: &New,
27    new_range: Range<usize>,
28) -> Result<(), D::Error>
29where
30    Old: Index<usize> + ?Sized,
31    New: Index<usize> + ?Sized,
32    Old::Output: Hash + Eq,
33    New::Output: PartialEq<Old::Output> + Hash + Eq,
34    D: DiffHook,
35{
36    diff_deadline(d, old, old_range, new, new_range, None)
37}
38
39/// Patience diff algorithm with deadline.
40///
41/// Diff `old`, between indices `old_range` and `new` between indices `new_range`.
42///
43/// This diff is done with an optional deadline that defines the maximal
44/// execution time permitted before it bails and falls back to an approximation.
45pub fn diff_deadline<Old, New, D>(
46    d: &mut D,
47    old: &Old,
48    old_range: Range<usize>,
49    new: &New,
50    new_range: Range<usize>,
51    deadline: Option<Instant>,
52) -> Result<(), D::Error>
53where
54    Old: Index<usize> + ?Sized,
55    New: Index<usize> + ?Sized,
56    Old::Output: Hash + Eq,
57    New::Output: PartialEq<Old::Output> + Hash + Eq,
58    D: DiffHook,
59{
60    let old_indexes = unique(old, old_range.clone());
61    let new_indexes = unique(new, new_range.clone());
62
63    let mut d = Replace::new(Patience {
64        d,
65        old,
66        old_current: old_range.start,
67        old_end: old_range.end,
68        old_indexes: &old_indexes,
69        new,
70        new_current: new_range.start,
71        new_end: new_range.end,
72        new_indexes: &new_indexes,
73        deadline,
74    });
75    myers::diff_deadline(
76        &mut d,
77        &old_indexes,
78        0..old_indexes.len(),
79        &new_indexes,
80        0..new_indexes.len(),
81        deadline,
82    )?;
83    Ok(())
84}
85
86struct Patience<'old, 'new, 'd, Old: ?Sized, New: ?Sized, D> {
87    d: &'d mut D,
88    old: &'old Old,
89    old_current: usize,
90    old_end: usize,
91    old_indexes: &'old [UniqueItem<'old, Old>],
92    new: &'new New,
93    new_current: usize,
94    new_end: usize,
95    new_indexes: &'new [UniqueItem<'new, New>],
96    deadline: Option<Instant>,
97}
98
99impl<'old, 'new, 'd, Old, New, D> DiffHook for Patience<'old, 'new, 'd, Old, New, D>
100where
101    D: DiffHook + 'd,
102    Old: Index<usize> + ?Sized + 'old,
103    New: Index<usize> + ?Sized + 'new,
104    New::Output: PartialEq<Old::Output>,
105{
106    type Error = D::Error;
107    fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {
108        for (old, new) in (old..old + len).zip(new..new + len) {
109            let a0 = self.old_current;
110            let b0 = self.new_current;
111            while self.old_current < self.old_indexes[old].original_index()
112                && self.new_current < self.new_indexes[new].original_index()
113                && self.new[self.new_current] == self.old[self.old_current]
114            {
115                self.old_current += 1;
116                self.new_current += 1;
117            }
118            if self.old_current > a0 {
119                self.d.equal(a0, b0, self.old_current - a0)?;
120            }
121            let mut no_finish_d = NoFinishHook::new(&mut self.d);
122            myers::diff_deadline(
123                &mut no_finish_d,
124                self.old,
125                self.old_current..self.old_indexes[old].original_index(),
126                self.new,
127                self.new_current..self.new_indexes[new].original_index(),
128                self.deadline,
129            )?;
130            self.old_current = self.old_indexes[old].original_index();
131            self.new_current = self.new_indexes[new].original_index();
132        }
133        Ok(())
134    }
135
136    fn finish(&mut self) -> Result<(), D::Error> {
137        myers::diff_deadline(
138            self.d,
139            self.old,
140            self.old_current..self.old_end,
141            self.new,
142            self.new_current..self.new_end,
143            self.deadline,
144        )
145    }
146}
147
148#[test]
149fn test_patience() {
150    let a: &[usize] = &[11, 1, 2, 2, 3, 4, 4, 4, 5, 47, 19];
151    let b: &[usize] = &[10, 1, 2, 2, 8, 9, 4, 4, 7, 47, 18];
152
153    let mut d = Replace::new(crate::algorithms::Capture::new());
154    diff(&mut d, a, 0..a.len(), b, 0..b.len()).unwrap();
155
156    insta::assert_debug_snapshot!(d.into_inner().ops());
157}
158
159#[test]
160fn test_patience_out_of_bounds_bug() {
161    // this used to be a bug
162    let a: &[usize] = &[1, 2, 3, 4];
163    let b: &[usize] = &[1, 2, 3];
164
165    let mut d = Replace::new(crate::algorithms::Capture::new());
166    diff(&mut d, a, 0..a.len(), b, 0..b.len()).unwrap();
167
168    insta::assert_debug_snapshot!(d.into_inner().ops());
169}
170
171#[test]
172fn test_finish_called() {
173    struct HasRunFinish(bool);
174
175    impl DiffHook for HasRunFinish {
176        type Error = ();
177        fn finish(&mut self) -> Result<(), Self::Error> {
178            self.0 = true;
179            Ok(())
180        }
181    }
182
183    let mut d = HasRunFinish(false);
184    let slice = &[1, 2];
185    let slice2 = &[1, 2, 3];
186    diff(&mut d, slice, 0..slice.len(), slice2, 0..slice2.len()).unwrap();
187    assert!(d.0);
188
189    let mut d = HasRunFinish(false);
190    let slice = &[1, 2];
191    diff(&mut d, slice, 0..slice.len(), slice, 0..slice.len()).unwrap();
192    assert!(d.0);
193
194    let mut d = HasRunFinish(false);
195    let slice: &[u8] = &[];
196    diff(&mut d, slice, 0..slice.len(), slice, 0..slice.len()).unwrap();
197    assert!(d.0);
198}
similar/algorithms/patience.rs

similar/algorithms/
patience.rs
