diffy_fork_filenames/diff/
cleanup.rs

1use crate::range::{DiffRange, SliceLike};
2
3// Walks through all edits and shifts them up and then down, trying to see if they run into similar
4// edits which can be merged
5#[allow(clippy::needless_lifetimes)]
6pub fn compact<'a, 'b, T: ?Sized + SliceLike>(diffs: &mut Vec<DiffRange<'a, 'b, T>>) {
7    // First attempt to compact all Deletions
8    let mut pointer = 0;
9    while let Some(&diff) = diffs.get(pointer) {
10        if let DiffRange::Delete(_) = diff {
11            pointer = shift_diff_up(diffs, pointer);
12            pointer = shift_diff_down(diffs, pointer);
13        }
14        pointer += 1;
15    }
16
17    // TODO maybe able to merge these and do them in the same pass?
18    // Then attempt to compact all Insertions
19    let mut pointer = 0;
20    while let Some(&diff) = diffs.get(pointer) {
21        if let DiffRange::Insert(_) = diff {
22            pointer = shift_diff_up(diffs, pointer);
23            pointer = shift_diff_down(diffs, pointer);
24        }
25        pointer += 1;
26    }
27}
28
29// Attempts to shift the Insertion or Deletion at location `pointer` as far upwards as possible.
30#[allow(clippy::needless_lifetimes)]
31fn shift_diff_up<'a, 'b, T: ?Sized + SliceLike>(
32    diffs: &mut Vec<DiffRange<'a, 'b, T>>,
33    mut pointer: usize,
34) -> usize {
35    while let Some(&prev_diff) = pointer.checked_sub(1).and_then(|idx| diffs.get(idx)) {
36        match (diffs[pointer], prev_diff) {
37            //
38            // Shift Inserts Upwards
39            //
40            (DiffRange::Insert(this_diff), DiffRange::Equal(prev_diff1, _)) => {
41                // check common suffix for the amount we can shift
42                let suffix_len = this_diff.common_suffix_len(prev_diff1);
43                if suffix_len != 0 {
44                    if let Some(DiffRange::Equal(..)) = diffs.get(pointer + 1) {
45                        diffs[pointer + 1].grow_up(suffix_len);
46                    } else {
47                        diffs.insert(
48                            pointer + 1,
49                            DiffRange::Equal(
50                                prev_diff1.slice(prev_diff1.len() - suffix_len..),
51                                this_diff.slice(this_diff.len() - suffix_len..),
52                            ),
53                        );
54                    }
55                    diffs[pointer].shift_up(suffix_len);
56                    diffs[pointer - 1].shrink_back(suffix_len);
57
58                    if diffs[pointer - 1].is_empty() {
59                        diffs.remove(pointer - 1);
60                        pointer -= 1;
61                    }
62                } else if diffs[pointer - 1].is_empty() {
63                    diffs.remove(pointer - 1);
64                    pointer -= 1;
65                } else {
66                    // We can't shift upwards anymore
67                    break;
68                }
69            }
70
71            //
72            // Shift Deletions Upwards
73            //
74            (DiffRange::Delete(this_diff), DiffRange::Equal(_, prev_diff2)) => {
75                // check common suffix for the amount we can shift
76                let suffix_len = this_diff.common_suffix_len(prev_diff2);
77                if suffix_len != 0 {
78                    if let Some(DiffRange::Equal(..)) = diffs.get(pointer + 1) {
79                        diffs[pointer + 1].grow_up(suffix_len);
80                    } else {
81                        diffs.insert(
82                            pointer + 1,
83                            DiffRange::Equal(
84                                this_diff.slice(this_diff.len() - suffix_len..),
85                                prev_diff2.slice(prev_diff2.len() - suffix_len..),
86                            ),
87                        );
88                    }
89                    diffs[pointer].shift_up(suffix_len);
90                    diffs[pointer - 1].shrink_back(suffix_len);
91
92                    if diffs[pointer - 1].is_empty() {
93                        diffs.remove(pointer - 1);
94                        pointer -= 1;
95                    }
96                } else if diffs[pointer - 1].is_empty() {
97                    diffs.remove(pointer - 1);
98                    pointer -= 1;
99                } else {
100                    // We can't shift upwards anymore
101                    break;
102                }
103            }
104
105            //
106            // Swap the Delete and Insert
107            //
108            (DiffRange::Insert(_), DiffRange::Delete(_))
109            | (DiffRange::Delete(_), DiffRange::Insert(_)) => {
110                diffs.swap(pointer - 1, pointer);
111                pointer -= 1;
112            }
113
114            //
115            // Merge the two ranges
116            //
117            (this_diff @ DiffRange::Insert(_), DiffRange::Insert(_))
118            | (this_diff @ DiffRange::Delete(_), DiffRange::Delete(_)) => {
119                diffs[pointer - 1].grow_down(this_diff.len());
120                diffs.remove(pointer);
121                pointer -= 1;
122            }
123
124            _ => panic!("range to shift must be either Insert or Delete"),
125        }
126    }
127
128    pointer
129}
130
131// Attempts to shift the Insertion or Deletion at location `pointer` as far downwards as possible.
132#[allow(clippy::needless_lifetimes)]
133fn shift_diff_down<'a, 'b, T: ?Sized + SliceLike>(
134    diffs: &mut Vec<DiffRange<'a, 'b, T>>,
135    mut pointer: usize,
136) -> usize {
137    while let Some(&next_diff) = pointer.checked_add(1).and_then(|idx| diffs.get(idx)) {
138        match (diffs[pointer], next_diff) {
139            //
140            // Shift Insert Downward
141            //
142            (DiffRange::Insert(this_diff), DiffRange::Equal(next_diff1, _)) => {
143                // check common prefix for the amoutn we can shift
144                let prefix_len = this_diff.common_prefix_len(next_diff1);
145                if prefix_len != 0 {
146                    if let Some(DiffRange::Equal(..)) =
147                        pointer.checked_sub(1).and_then(|idx| diffs.get(idx))
148                    {
149                        diffs[pointer - 1].grow_down(prefix_len);
150                    } else {
151                        diffs.insert(
152                            pointer,
153                            DiffRange::Equal(
154                                next_diff1.slice(..prefix_len),
155                                this_diff.slice(..prefix_len),
156                            ),
157                        );
158                        pointer += 1;
159                    }
160
161                    diffs[pointer].shift_down(prefix_len);
162                    diffs[pointer + 1].shrink_front(prefix_len);
163
164                    if diffs[pointer + 1].is_empty() {
165                        diffs.remove(pointer + 1);
166                    }
167                } else if diffs[pointer + 1].is_empty() {
168                    diffs.remove(pointer + 1);
169                } else {
170                    // We can't shift downwards anymore
171                    break;
172                }
173            }
174
175            //
176            // Shift Deletion Downward
177            //
178            (DiffRange::Delete(this_diff), DiffRange::Equal(_, next_diff2)) => {
179                // check common prefix for the amoutn we can shift
180                let prefix_len = this_diff.common_prefix_len(next_diff2);
181                if prefix_len != 0 {
182                    if let Some(DiffRange::Equal(..)) =
183                        pointer.checked_sub(1).and_then(|idx| diffs.get(idx))
184                    {
185                        diffs[pointer - 1].grow_down(prefix_len);
186                    } else {
187                        diffs.insert(
188                            pointer,
189                            DiffRange::Equal(
190                                this_diff.slice(..prefix_len),
191                                next_diff2.slice(..prefix_len),
192                            ),
193                        );
194                        pointer += 1;
195                    }
196
197                    diffs[pointer].shift_down(prefix_len);
198                    diffs[pointer + 1].shrink_front(prefix_len);
199
200                    if diffs[pointer + 1].is_empty() {
201                        diffs.remove(pointer + 1);
202                    }
203                } else if diffs[pointer + 1].is_empty() {
204                    diffs.remove(pointer + 1);
205                } else {
206                    // We can't shift downwards anymore
207                    break;
208                }
209            }
210
211            //
212            // Swap the Delete and Insert
213            //
214            (DiffRange::Insert(_), DiffRange::Delete(_))
215            | (DiffRange::Delete(_), DiffRange::Insert(_)) => {
216                diffs.swap(pointer, pointer + 1);
217                pointer += 1;
218            }
219
220            //
221            // Merge the two ranges
222            //
223            (DiffRange::Insert(_), next_diff @ DiffRange::Insert(_))
224            | (DiffRange::Delete(_), next_diff @ DiffRange::Delete(_)) => {
225                diffs[pointer].grow_down(next_diff.len());
226                diffs.remove(pointer + 1);
227            }
228
229            _ => panic!("range to shift must be either Insert or Delete"),
230        }
231    }
232
233    pointer
234}
diffy_fork_filenames/diff/cleanup.rs

diffy_fork_filenames/diff/
cleanup.rs
