1use crate::algorithms::DiffHook;
2
3/// A [`DiffHook`] that combines deletions and insertions to give blocks
4/// of maximal length, and replacements when appropriate.
5///
6/// It will replace [`DiffHook::insert`] and [`DiffHook::delete`] events when
7/// possible with [`DiffHook::replace`] events. Note that even though the
8/// text processing in the crate does not use replace events and always resolves
9/// then back to delete and insert, it's useful to always use the replacer to
10/// ensure a consistent order of inserts and deletes. This is why for instance
11/// the text diffing automatically uses this hook internally.
12pub struct Replace<D: DiffHook> {
13 d: D,
14 del: Option<(usize, usize, usize)>,
15 ins: Option<(usize, usize, usize)>,
16 eq: Option<(usize, usize, usize)>,
17}
18
19impl<D: DiffHook> Replace<D> {
20 /// Creates a new replace hook wrapping another hook.
21 pub fn new(d: D) -> Self {
22 Replace {
23 d,
24 del: None,
25 ins: None,
26 eq: None,
27 }
28 }
29
30 /// Extracts the inner hook.
31 pub fn into_inner(self) -> D {
32 self.d
33 }
34
35 fn flush_eq(&mut self) -> Result<(), D::Error> {
36 if let Some((eq_old_index, eq_new_index, eq_len)) = self.eq.take() {
37 self.d.equal(eq_old_index, eq_new_index, eq_len)?
38 }
39 Ok(())
40 }
41
42 fn flush_del_ins(&mut self) -> Result<(), D::Error> {
43 if let Some((del_old_index, del_old_len, del_new_index)) = self.del.take() {
44 if let Some((_, ins_new_index, ins_new_len)) = self.ins.take() {
45 self.d
46 .replace(del_old_index, del_old_len, ins_new_index, ins_new_len)?;
47 } else {
48 self.d.delete(del_old_index, del_old_len, del_new_index)?;
49 }
50 } else if let Some((ins_old_index, ins_new_index, ins_new_len)) = self.ins.take() {
51 self.d.insert(ins_old_index, ins_new_index, ins_new_len)?;
52 }
53 Ok(())
54 }
55}
56
57impl<D: DiffHook> AsRef<D> for Replace<D> {
58 fn as_ref(&self) -> &D {
59 &self.d
60 }
61}
62
63impl<D: DiffHook> AsMut<D> for Replace<D> {
64 fn as_mut(&mut self) -> &mut D {
65 &mut self.d
66 }
67}
68
69impl<D: DiffHook> DiffHook for Replace<D> {
70 type Error = D::Error;
71
72 fn equal(&mut self, old_index: usize, new_index: usize, len: usize) -> Result<(), D::Error> {
73 self.flush_del_ins()?;
74
75 self.eq = if let Some((eq_old_index, eq_new_index, eq_len)) = self.eq.take() {
76 Some((eq_old_index, eq_new_index, eq_len + len))
77 } else {
78 Some((old_index, new_index, len))
79 };
80
81 Ok(())
82 }
83
84 fn delete(
85 &mut self,
86 old_index: usize,
87 old_len: usize,
88 new_index: usize,
89 ) -> Result<(), D::Error> {
90 self.flush_eq()?;
91 if let Some((del_old_index, del_old_len, del_new_index)) = self.del.take() {
92 debug_assert_eq!(old_index, del_old_index + del_old_len);
93 self.del = Some((del_old_index, del_old_len + old_len, del_new_index));
94 } else {
95 self.del = Some((old_index, old_len, new_index));
96 }
97 Ok(())
98 }
99
100 fn insert(
101 &mut self,
102 old_index: usize,
103 new_index: usize,
104 new_len: usize,
105 ) -> Result<(), D::Error> {
106 self.flush_eq()?;
107 self.ins = if let Some((ins_old_index, ins_new_index, ins_new_len)) = self.ins.take() {
108 debug_assert_eq!(ins_new_index + ins_new_len, new_index);
109 Some((ins_old_index, ins_new_index, new_len + ins_new_len))
110 } else {
111 Some((old_index, new_index, new_len))
112 };
113
114 Ok(())
115 }
116
117 fn replace(
118 &mut self,
119 old_index: usize,
120 old_len: usize,
121 new_index: usize,
122 new_len: usize,
123 ) -> Result<(), D::Error> {
124 self.flush_eq()?;
125 self.d.replace(old_index, old_len, new_index, new_len)
126 }
127
128 fn finish(&mut self) -> Result<(), D::Error> {
129 self.flush_eq()?;
130 self.flush_del_ins()?;
131 self.d.finish()
132 }
133}
134
135#[test]
136fn test_mayers_replace() {
137 use crate::algorithms::{diff_slices, Algorithm};
138 let a: &[&str] = &[
139 ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n",
140 "a\n",
141 "b\n",
142 "c\n",
143 "================================\n",
144 "d\n",
145 "e\n",
146 "f\n",
147 "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
148 ];
149 let b: &[&str] = &[
150 ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n",
151 "x\n",
152 "b\n",
153 "c\n",
154 "================================\n",
155 "y\n",
156 "e\n",
157 "f\n",
158 "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n",
159 ];
160
161 let mut d = Replace::new(crate::algorithms::Capture::new());
162 diff_slices(Algorithm::Myers, &mut d, a, b).unwrap();
163
164 insta::assert_debug_snapshot!(&d.into_inner().ops(), @r###"
165 [
166 Equal {
167 old_index: 0,
168 new_index: 0,
169 len: 1,
170 },
171 Replace {
172 old_index: 1,
173 old_len: 1,
174 new_index: 1,
175 new_len: 1,
176 },
177 Equal {
178 old_index: 2,
179 new_index: 2,
180 len: 3,
181 },
182 Replace {
183 old_index: 5,
184 old_len: 1,
185 new_index: 5,
186 new_len: 1,
187 },
188 Equal {
189 old_index: 6,
190 new_index: 6,
191 len: 3,
192 },
193 ]
194 "###);
195}
196
197#[test]
198fn test_replace() {
199 use crate::algorithms::{diff_slices, Algorithm};
200
201 let a: &[usize] = &[0, 1, 2, 3, 4];
202 let b: &[usize] = &[0, 1, 2, 7, 8, 9];
203
204 let mut d = Replace::new(crate::algorithms::Capture::new());
205 diff_slices(Algorithm::Myers, &mut d, a, b).unwrap();
206 insta::assert_debug_snapshot!(d.into_inner().ops(), @r###"
207 [
208 Equal {
209 old_index: 0,
210 new_index: 0,
211 len: 3,
212 },
213 Replace {
214 old_index: 3,
215 old_len: 2,
216 new_index: 3,
217 new_len: 3,
218 },
219 ]
220 "###);
221}
222