1use std::mem;
2
3type Edit = buffer::Edit<u32>;
4
5#[derive(Default, Debug, PartialEq, Eq)]
6struct Patch(Vec<Edit>);
7
8impl Patch {
9 fn compose(&self, new: &Self) -> Patch {
10 let mut composed = Vec::<Edit>::new();
11 let mut old_edits = self.0.iter().cloned().peekable();
12 let mut old_delta = 0;
13 let mut new_delta = 0;
14 let mut intermediate_start;
15 let mut intermediate_end = 0;
16
17 for mut new_edit in new.0.iter().cloned() {
18 let new_edit_delta = new_edit.new.len() as i32 - new_edit.old.len() as i32;
19
20 if let Some(last_edit) = composed.last_mut() {
21 if intermediate_end >= new_edit.old.start {
22 if new_edit.old.end > intermediate_end {
23 last_edit.old.end += new_edit.old.end - intermediate_end;
24 last_edit.new.end += new_edit.old.end - intermediate_end;
25 intermediate_end = new_edit.old.end;
26 }
27 last_edit.new.end = (last_edit.new.end as i32 + new_edit_delta) as u32;
28 continue;
29 }
30 }
31
32 intermediate_start = new_edit.old.start;
33 intermediate_end = new_edit.old.end;
34 new_edit.old.start = (new_edit.old.start as i32 - old_delta) as u32;
35 new_edit.old.end = (new_edit.old.end as i32 - old_delta) as u32;
36
37 while let Some(old_edit) = old_edits.peek() {
38 let old_edit_delta = old_edit.new.len() as i32 - old_edit.old.len() as i32;
39
40 if old_edit.new.end < intermediate_start {
41 let mut old_edit = old_edit.clone();
42 old_edit.new.start = (old_edit.new.start as i32 + new_delta) as u32;
43 old_edit.new.end = (old_edit.new.end as i32 + new_delta) as u32;
44 new_edit.old.start = (new_edit.old.start as i32 - old_edit_delta) as u32;
45 new_edit.old.end = (new_edit.old.end as i32 - old_edit_delta) as u32;
46 composed.push(old_edit);
47 } else if old_edit.new.start <= intermediate_end {
48 if old_edit.new.start < intermediate_start {
49 new_edit.new.start -= intermediate_start - old_edit.new.start;
50 new_edit.old.start -= intermediate_start - old_edit.new.start;
51 }
52 if old_edit.new.end > intermediate_end {
53 new_edit.new.end += old_edit.new.end - intermediate_end;
54 new_edit.old.end += old_edit.new.end - intermediate_end;
55 intermediate_end = old_edit.new.end;
56 }
57 new_edit.old.end = (new_edit.old.end as i32 - old_edit_delta) as u32;
58 } else {
59 break;
60 }
61
62 old_delta += old_edit_delta;
63 old_edits.next();
64 }
65
66 new_delta += new_edit_delta;
67 composed.push(new_edit);
68 }
69
70 while let Some(mut old_edit) = old_edits.next() {
71 old_edit.new.start = (old_edit.new.start as i32 + new_delta) as u32;
72 old_edit.new.end = (old_edit.new.end as i32 + new_delta) as u32;
73 composed.push(old_edit);
74 }
75
76 Patch(composed)
77 }
78
79 fn invert(&mut self) -> &mut Self {
80 for edit in &mut self.0 {
81 mem::swap(&mut edit.old, &mut edit.new);
82 }
83 self
84 }
85}
86
87#[cfg(test)]
88mod tests {
89 use super::*;
90 use rand::prelude::*;
91 use std::env;
92
93 #[gpui::test]
94 fn test_one_disjoint_edit() {
95 assert_patch_composition(
96 Patch(vec![Edit {
97 old: 1..3,
98 new: 1..4,
99 }]),
100 Patch(vec![Edit {
101 old: 0..0,
102 new: 0..4,
103 }]),
104 Patch(vec![
105 Edit {
106 old: 0..0,
107 new: 0..4,
108 },
109 Edit {
110 old: 1..3,
111 new: 5..8,
112 },
113 ]),
114 );
115
116 assert_patch_composition(
117 Patch(vec![Edit {
118 old: 1..3,
119 new: 1..4,
120 }]),
121 Patch(vec![Edit {
122 old: 5..9,
123 new: 5..7,
124 }]),
125 Patch(vec![
126 Edit {
127 old: 1..3,
128 new: 1..4,
129 },
130 Edit {
131 old: 4..8,
132 new: 5..7,
133 },
134 ]),
135 );
136 }
137
138 #[gpui::test]
139 fn test_one_overlapping_edit() {
140 assert_patch_composition(
141 Patch(vec![Edit {
142 old: 1..3,
143 new: 1..4,
144 }]),
145 Patch(vec![Edit {
146 old: 3..5,
147 new: 3..6,
148 }]),
149 Patch(vec![Edit {
150 old: 1..4,
151 new: 1..6,
152 }]),
153 );
154 }
155
156 #[gpui::test]
157 fn test_two_disjoint_and_overlapping() {
158 assert_patch_composition(
159 Patch(vec![
160 Edit {
161 old: 1..3,
162 new: 1..4,
163 },
164 Edit {
165 old: 8..12,
166 new: 9..11,
167 },
168 ]),
169 Patch(vec![
170 Edit {
171 old: 0..0,
172 new: 0..4,
173 },
174 Edit {
175 old: 3..10,
176 new: 7..9,
177 },
178 ]),
179 Patch(vec![
180 Edit {
181 old: 0..0,
182 new: 0..4,
183 },
184 Edit {
185 old: 1..12,
186 new: 5..10,
187 },
188 ]),
189 );
190 }
191
192 #[gpui::test]
193 fn test_two_new_edits_overlapping_one_old_edit() {
194 assert_patch_composition(
195 Patch(vec![Edit {
196 old: 0..0,
197 new: 0..3,
198 }]),
199 Patch(vec![
200 Edit {
201 old: 0..0,
202 new: 0..1,
203 },
204 Edit {
205 old: 1..2,
206 new: 2..2,
207 },
208 ]),
209 Patch(vec![Edit {
210 old: 0..0,
211 new: 0..3,
212 }]),
213 );
214
215 assert_patch_composition(
216 Patch(vec![Edit {
217 old: 2..3,
218 new: 2..4,
219 }]),
220 Patch(vec![
221 Edit {
222 old: 0..2,
223 new: 0..1,
224 },
225 Edit {
226 old: 3..3,
227 new: 2..5,
228 },
229 ]),
230 Patch(vec![Edit {
231 old: 0..3,
232 new: 0..6,
233 }]),
234 );
235
236 assert_patch_composition(
237 Patch(vec![Edit {
238 old: 0..0,
239 new: 0..2,
240 }]),
241 Patch(vec![
242 Edit {
243 old: 0..0,
244 new: 0..2,
245 },
246 Edit {
247 old: 2..5,
248 new: 4..4,
249 },
250 ]),
251 Patch(vec![Edit {
252 old: 0..3,
253 new: 0..4,
254 }]),
255 );
256 }
257
258 #[gpui::test(iterations = 1000, seed = 131)]
259 fn test_random(mut rng: StdRng) {
260 let operations = env::var("OPERATIONS")
261 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
262 .unwrap_or(3);
263
264 let initial_chars = (0..rng.gen_range(0..=5))
265 .map(|_| rng.gen_range(b'a'..=b'z') as char)
266 .collect::<Vec<_>>();
267 let mut final_chars = initial_chars.clone();
268 let mut patches = Vec::new();
269
270 println!("initial chars: {:?}", initial_chars);
271 for _ in 0..operations {
272 let end = rng.gen_range(0..=final_chars.len());
273 let start = rng.gen_range(0..=end);
274 let mut len = rng.gen_range(0..=3);
275 if start == end && len == 0 {
276 len += 1;
277 }
278 let new_chars = (0..len)
279 .map(|_| rng.gen_range(b'a'..=b'z') as char)
280 .collect::<Vec<_>>();
281 println!(
282 "editing {:?}: {:?}",
283 start..end,
284 new_chars.iter().collect::<String>()
285 );
286
287 let patch = Patch(vec![Edit {
288 old: start as u32..end as u32,
289 new: start as u32..start as u32 + new_chars.len() as u32,
290 }]);
291 if patches.is_empty() || rng.gen() {
292 println!("pushing singleton patch: {:?}", patch.0);
293 patches.push(patch);
294 } else {
295 let patch = patches.pop().unwrap().compose(&patch);
296 println!("composed patches: {:?}", patch.0);
297 patches.push(patch);
298 }
299 final_chars.splice(start..end, new_chars);
300 }
301
302 println!("final chars: {:?}", final_chars);
303 println!("final patches: {:?}", patches);
304
305 let mut composed = Patch::default();
306 for patch in patches {
307 println!("composing patches {:?} and {:?}", composed, patch);
308 composed = composed.compose(&patch);
309 println!("composed {:?}", composed);
310 }
311 println!("composed edits: {:?}", composed);
312 let mut chars = initial_chars.clone();
313 for edit in composed.0 {
314 chars.splice(
315 edit.new.start as usize..edit.new.start as usize + edit.old.len(),
316 final_chars[edit.new.start as usize..edit.new.end as usize]
317 .iter()
318 .copied(),
319 );
320 }
321
322 assert_eq!(chars, final_chars);
323 }
324
325 #[track_caller]
326 fn assert_patch_composition(old: Patch, new: Patch, composed: Patch) {
327 let original = ('a'..'z').collect::<Vec<_>>();
328 let inserted = ('A'..'Z').collect::<Vec<_>>();
329
330 let mut expected = original.clone();
331 apply_patch(&mut expected, &old, &inserted);
332 apply_patch(&mut expected, &new, &inserted);
333
334 let mut actual = original.clone();
335 apply_patch(&mut actual, &composed, &expected);
336 assert_eq!(
337 actual.into_iter().collect::<String>(),
338 expected.into_iter().collect::<String>(),
339 "expected patch is incorrect"
340 );
341
342 assert_eq!(old.compose(&new), composed);
343 }
344
345 fn apply_patch(text: &mut Vec<char>, patch: &Patch, new_text: &[char]) {
346 for edit in patch.0.iter().rev() {
347 text.splice(
348 edit.old.start as usize..edit.old.end as usize,
349 new_text[edit.new.start as usize..edit.new.end as usize]
350 .iter()
351 .copied(),
352 );
353 }
354 }
355}