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.
11 use std::hash::Hash;
12 use std::ops::{Index, Range};
13 use std::time::Instant;
14
15 use crate::algorithms::{myers, DiffHook, NoFinishHook, Replace};
16
17 use super::utils::{unique, UniqueItem};
18
19 /// Patience diff algorithm.
20 ///
21 /// Diff `old`, between indices `old_range` and `new` between indices `new_range`.
diff<Old, New, D>( d: &mut D, old: &Old, old_range: Range<usize>, new: &New, new_range: Range<usize>, ) -> Result<(), D::Error> where Old: Index<usize> + ?Sized, New: Index<usize> + ?Sized, Old::Output: Hash + Eq, New::Output: PartialEq<Old::Output> + Hash + Eq, D: DiffHook,22 pub 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>
29 where
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.
diff_deadline<Old, New, D>( d: &mut D, old: &Old, old_range: Range<usize>, new: &New, new_range: Range<usize>, deadline: Option<Instant>, ) -> Result<(), D::Error> where Old: Index<usize> + ?Sized, New: Index<usize> + ?Sized, Old::Output: Hash + Eq, New::Output: PartialEq<Old::Output> + Hash + Eq, D: DiffHook,45 pub 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>
53 where
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
86 /// Shortcut for diffing slices.
87 #[deprecated(
88 since = "1.4.0",
89 note = "slice utility function is now only available via similar::algorithms::diff_slices"
90 )]
diff_slices<D, T>(d: &mut D, old: &[T], new: &[T]) -> Result<(), D::Error> where D: DiffHook, T: Eq + Hash,91 pub fn diff_slices<D, T>(d: &mut D, old: &[T], new: &[T]) -> Result<(), D::Error>
92 where
93 D: DiffHook,
94 T: Eq + Hash,
95 {
96 diff(d, old, 0..old.len(), new, 0..new.len())
97 }
98
99 struct Patience<'old, 'new, 'd, Old: ?Sized, New: ?Sized, D> {
100 d: &'d mut D,
101 old: &'old Old,
102 old_current: usize,
103 old_end: usize,
104 old_indexes: &'old [UniqueItem<'old, Old>],
105 new: &'new New,
106 new_current: usize,
107 new_end: usize,
108 new_indexes: &'new [UniqueItem<'new, New>],
109 deadline: Option<Instant>,
110 }
111
112 impl<'old, 'new, 'd, Old, New, D> DiffHook for Patience<'old, 'new, 'd, Old, New, D>
113 where
114 D: DiffHook + 'd,
115 Old: Index<usize> + ?Sized + 'old,
116 New: Index<usize> + ?Sized + 'new,
117 New::Output: PartialEq<Old::Output>,
118 {
119 type Error = D::Error;
equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error>120 fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {
121 for (old, new) in (old..old + len).zip(new..new + len) {
122 let a0 = self.old_current;
123 let b0 = self.new_current;
124 while self.old_current < self.old_indexes[old].original_index()
125 && self.new_current < self.new_indexes[new].original_index()
126 && self.new[self.new_current] == self.old[self.old_current]
127 {
128 self.old_current += 1;
129 self.new_current += 1;
130 }
131 if self.old_current > a0 {
132 self.d.equal(a0, b0, self.old_current - a0)?;
133 }
134 let mut no_finish_d = NoFinishHook::new(&mut self.d);
135 myers::diff_deadline(
136 &mut no_finish_d,
137 self.old,
138 self.old_current..self.old_indexes[old].original_index(),
139 self.new,
140 self.new_current..self.new_indexes[new].original_index(),
141 self.deadline,
142 )?;
143 self.old_current = self.old_indexes[old].original_index();
144 self.new_current = self.new_indexes[new].original_index();
145 }
146 Ok(())
147 }
148
finish(&mut self) -> Result<(), D::Error>149 fn finish(&mut self) -> Result<(), D::Error> {
150 myers::diff_deadline(
151 self.d,
152 self.old,
153 self.old_current..self.old_end,
154 self.new,
155 self.new_current..self.new_end,
156 self.deadline,
157 )
158 }
159 }
160
161 #[test]
test_patience()162 fn test_patience() {
163 let a: &[usize] = &[11, 1, 2, 2, 3, 4, 4, 4, 5, 47, 19];
164 let b: &[usize] = &[10, 1, 2, 2, 8, 9, 4, 4, 7, 47, 18];
165
166 let mut d = Replace::new(crate::algorithms::Capture::new());
167 diff(&mut d, a, 0..a.len(), b, 0..b.len()).unwrap();
168
169 insta::assert_debug_snapshot!(d.into_inner().ops());
170 }
171
172 #[test]
test_patience_out_of_bounds_bug()173 fn test_patience_out_of_bounds_bug() {
174 // this used to be a bug
175 let a: &[usize] = &[1, 2, 3, 4];
176 let b: &[usize] = &[1, 2, 3];
177
178 let mut d = Replace::new(crate::algorithms::Capture::new());
179 diff(&mut d, a, 0..a.len(), b, 0..b.len()).unwrap();
180
181 insta::assert_debug_snapshot!(d.into_inner().ops());
182 }
183