similar/algorithms/
compact.rs

Help
1//! Implements basic compacting.  This is based on the compaction logic from
2//! diffy by Brandon Williams.
3use std::ops::Index;
4
5use crate::{DiffOp, DiffTag};
6
7use super::utils::{common_prefix_len, common_suffix_len};
8use super::DiffHook;
9
10/// Performs semantic cleanup operations on a diff.
11///
12/// This merges similar ops together but also tries to move hunks up and
13/// down the diff with the desire to connect as many hunks as possible.
14/// It still needs to be combined with [`Replace`](crate::algorithms::Replace)
15/// to get actual replace diff ops out.
16#[derive(Debug)]
17pub struct Compact<'old, 'new, Old: ?Sized, New: ?Sized, D> {
18    d: D,
19    ops: Vec<DiffOp>,
20    old: &'old Old,
21    new: &'new New,
22}
23
24impl<'old, 'new, Old, New, D> Compact<'old, 'new, Old, New, D>
25where
26    D: DiffHook,
27    Old: Index<usize> + ?Sized + 'old,
28    New: Index<usize> + ?Sized + 'new,
29    New::Output: PartialEq<Old::Output>,
30{
31    /// Creates a new compact hook wrapping another hook.
32    pub fn new(d: D, old: &'old Old, new: &'new New) -> Self {
33        Compact {
34            d,
35            ops: Vec::new(),
36            old,
37            new,
38        }
39    }
40
41    /// Extracts the inner hook.
42    pub fn into_inner(self) -> D {
43        self.d
44    }
45}
46
47impl<Old: ?Sized, New: ?Sized, D: DiffHook> AsRef<D> for Compact<'_, '_, Old, New, D> {
48    fn as_ref(&self) -> &D {
49        &self.d
50    }
51}
52
53impl<Old: ?Sized, New: ?Sized, D: DiffHook> AsMut<D> for Compact<'_, '_, Old, New, D> {
54    fn as_mut(&mut self) -> &mut D {
55        &mut self.d
56    }
57}
58
59impl<'old, 'new, Old, New, D> DiffHook for Compact<'old, 'new, Old, New, D>
60where
61    D: DiffHook,
62    Old: Index<usize> + ?Sized + 'old,
63    New: Index<usize> + ?Sized + 'new,
64    New::Output: PartialEq<Old::Output>,
65{
66    type Error = D::Error;
67
68    #[inline(always)]
69    fn equal(&mut self, old_index: usize, new_index: usize, len: usize) -> Result<(), Self::Error> {
70        self.ops.push(DiffOp::Equal {
71            old_index,
72            new_index,
73            len,
74        });
75        Ok(())
76    }
77
78    #[inline(always)]
79    fn delete(
80        &mut self,
81        old_index: usize,
82        old_len: usize,
83        new_index: usize,
84    ) -> Result<(), Self::Error> {
85        self.ops.push(DiffOp::Delete {
86            old_index,
87            old_len,
88            new_index,
89        });
90        Ok(())
91    }
92
93    #[inline(always)]
94    fn insert(
95        &mut self,
96        old_index: usize,
97        new_index: usize,
98        new_len: usize,
99    ) -> Result<(), Self::Error> {
100        self.ops.push(DiffOp::Insert {
101            old_index,
102            new_index,
103            new_len,
104        });
105        Ok(())
106    }
107
108    fn finish(&mut self) -> Result<(), Self::Error> {
109        cleanup_diff_ops(self.old, self.new, &mut self.ops);
110        for op in &self.ops {
111            op.apply_to_hook(&mut self.d)?;
112        }
113        self.d.finish()
114    }
115}
116
117// Walks through all edits and shifts them up and then down, trying to see if
118// they run into similar edits which can be merged.
119pub fn cleanup_diff_ops<Old, New>(old: &Old, new: &New, ops: &mut Vec<DiffOp>)
120where
121    Old: Index<usize> + ?Sized,
122    New: Index<usize> + ?Sized,
123    New::Output: PartialEq<Old::Output>,
124{
125    // First attempt to compact all Deletions
126    let mut pointer = 0;
127    while let Some(&op) = ops.get(pointer) {
128        if let DiffTag::Delete = op.tag() {
129            pointer = shift_diff_ops_up(ops, old, new, pointer);
130            pointer = shift_diff_ops_down(ops, old, new, pointer);
131        }
132        pointer += 1;
133    }
134
135    // Then attempt to compact all Insertions
136    let mut pointer = 0;
137    while let Some(&op) = ops.get(pointer) {
138        if let DiffTag::Insert = op.tag() {
139            pointer = shift_diff_ops_up(ops, old, new, pointer);
140            pointer = shift_diff_ops_down(ops, old, new, pointer);
141        }
142        pointer += 1;
143    }
144}
145
146fn shift_diff_ops_up<Old, New>(
147    ops: &mut Vec<DiffOp>,
148    old: &Old,
149    new: &New,
150    mut pointer: usize,
151) -> usize
152where
153    Old: Index<usize> + ?Sized,
154    New: Index<usize> + ?Sized,
155    New::Output: PartialEq<Old::Output>,
156{
157    while let Some(&prev_op) = pointer.checked_sub(1).and_then(|idx| ops.get(idx)) {
158        let this_op = ops[pointer];
159        match (this_op.tag(), prev_op.tag()) {
160            // Shift Inserts Upwards
161            (DiffTag::Insert, DiffTag::Equal) => {
162                let suffix_len =
163                    common_suffix_len(old, prev_op.old_range(), new, this_op.new_range());
164                if suffix_len > 0 {
165                    if let Some(DiffTag::Equal) = ops.get(pointer + 1).map(|x| x.tag()) {
166                        ops[pointer + 1].grow_left(suffix_len);
167                    } else {
168                        ops.insert(
169                            pointer + 1,
170                            DiffOp::Equal {
171                                old_index: prev_op.old_range().end - suffix_len,
172                                new_index: this_op.new_range().end - suffix_len,
173                                len: suffix_len,
174                            },
175                        );
176                    }
177                    ops[pointer].shift_left(suffix_len);
178                    ops[pointer - 1].shrink_left(suffix_len);
179
180                    if ops[pointer - 1].is_empty() {
181                        ops.remove(pointer - 1);
182                        pointer -= 1;
183                    }
184                } else if ops[pointer - 1].is_empty() {
185                    ops.remove(pointer - 1);
186                    pointer -= 1;
187                } else {
188                    // We can't shift upwards anymore
189                    break;
190                }
191            }
192            // Shift Deletions Upwards
193            (DiffTag::Delete, DiffTag::Equal) => {
194                // check common suffix for the amount we can shift
195                let suffix_len =
196                    common_suffix_len(old, prev_op.old_range(), new, this_op.new_range());
197                if suffix_len != 0 {
198                    if let Some(DiffTag::Equal) = ops.get(pointer + 1).map(|x| x.tag()) {
199                        ops[pointer + 1].grow_left(suffix_len);
200                    } else {
201                        let old_range = prev_op.old_range();
202                        ops.insert(
203                            pointer + 1,
204                            DiffOp::Equal {
205                                old_index: old_range.end - suffix_len,
206                                new_index: this_op.new_range().end - suffix_len,
207                                len: old_range.len() - suffix_len,
208                            },
209                        );
210                    }
211                    ops[pointer].shift_left(suffix_len);
212                    ops[pointer - 1].shrink_left(suffix_len);
213
214                    if ops[pointer - 1].is_empty() {
215                        ops.remove(pointer - 1);
216                        pointer -= 1;
217                    }
218                } else if ops[pointer - 1].is_empty() {
219                    ops.remove(pointer - 1);
220                    pointer -= 1;
221                } else {
222                    // We can't shift upwards anymore
223                    break;
224                }
225            }
226            // Swap the Delete and Insert
227            (DiffTag::Insert, DiffTag::Delete) | (DiffTag::Delete, DiffTag::Insert) => {
228                ops.swap(pointer - 1, pointer);
229                pointer -= 1;
230            }
231            // Merge the two ranges
232            (DiffTag::Insert, DiffTag::Insert) => {
233                ops[pointer - 1].grow_right(this_op.new_range().len());
234                ops.remove(pointer);
235                pointer -= 1;
236            }
237            (DiffTag::Delete, DiffTag::Delete) => {
238                ops[pointer - 1].grow_right(this_op.old_range().len());
239                ops.remove(pointer);
240                pointer -= 1;
241            }
242            _ => unreachable!("unexpected tag"),
243        }
244    }
245    pointer
246}
247
248fn shift_diff_ops_down<Old, New>(
249    ops: &mut Vec<DiffOp>,
250    old: &Old,
251    new: &New,
252    mut pointer: usize,
253) -> usize
254where
255    Old: Index<usize> + ?Sized,
256    New: Index<usize> + ?Sized,
257    New::Output: PartialEq<Old::Output>,
258{
259    while let Some(&next_op) = pointer.checked_add(1).and_then(|idx| ops.get(idx)) {
260        let this_op = ops[pointer];
261        match (this_op.tag(), next_op.tag()) {
262            // Shift Inserts Downwards
263            (DiffTag::Insert, DiffTag::Equal) => {
264                let prefix_len =
265                    common_prefix_len(old, next_op.old_range(), new, this_op.new_range());
266                if prefix_len > 0 {
267                    if let Some(DiffTag::Equal) = pointer
268                        .checked_sub(1)
269                        .and_then(|x| ops.get(x))
270                        .map(|x| x.tag())
271                    {
272                        ops[pointer - 1].grow_right(prefix_len);
273                    } else {
274                        ops.insert(
275                            pointer,
276                            DiffOp::Equal {
277                                old_index: next_op.old_range().start,
278                                new_index: this_op.new_range().start,
279                                len: prefix_len,
280                            },
281                        );
282                        pointer += 1;
283                    }
284                    ops[pointer].shift_right(prefix_len);
285                    ops[pointer + 1].shrink_right(prefix_len);
286
287                    if ops[pointer + 1].is_empty() {
288                        ops.remove(pointer + 1);
289                    }
290                } else if ops[pointer + 1].is_empty() {
291                    ops.remove(pointer + 1);
292                } else {
293                    // We can't shift upwards anymore
294                    break;
295                }
296            }
297            // Shift Deletions Downwards
298            (DiffTag::Delete, DiffTag::Equal) => {
299                // check common suffix for the amount we can shift
300                let prefix_len =
301                    common_prefix_len(old, next_op.old_range(), new, this_op.new_range());
302                if prefix_len > 0 {
303                    if let Some(DiffTag::Equal) = pointer
304                        .checked_sub(1)
305                        .and_then(|x| ops.get(x))
306                        .map(|x| x.tag())
307                    {
308                        ops[pointer - 1].grow_right(prefix_len);
309                    } else {
310                        ops.insert(
311                            pointer,
312                            DiffOp::Equal {
313                                old_index: next_op.old_range().start,
314                                new_index: this_op.new_range().start,
315                                len: prefix_len,
316                            },
317                        );
318                        pointer += 1;
319                    }
320                    ops[pointer].shift_right(prefix_len);
321                    ops[pointer + 1].shrink_right(prefix_len);
322
323                    if ops[pointer + 1].is_empty() {
324                        ops.remove(pointer + 1);
325                    }
326                } else if ops[pointer + 1].is_empty() {
327                    ops.remove(pointer + 1);
328                } else {
329                    // We can't shift downwards anymore
330                    break;
331                }
332            }
333            // Swap the Delete and Insert
334            (DiffTag::Insert, DiffTag::Delete) | (DiffTag::Delete, DiffTag::Insert) => {
335                ops.swap(pointer, pointer + 1);
336                pointer += 1;
337            }
338            // Merge the two ranges
339            (DiffTag::Insert, DiffTag::Insert) => {
340                ops[pointer].grow_right(next_op.new_range().len());
341                ops.remove(pointer + 1);
342            }
343            (DiffTag::Delete, DiffTag::Delete) => {
344                ops[pointer].grow_right(next_op.old_range().len());
345                ops.remove(pointer + 1);
346            }
347            _ => unreachable!("unexpected tag"),
348        }
349    }
350    pointer
351}
similar/algorithms/compact.rs

similar/algorithms/
compact.rs
