1use std::{cmp, iter::Peekable, mem, ops::Range};
2
3type Edit = buffer::Edit<u32>;
4
5#[derive(Default, Debug, PartialEq, Eq)]
6struct Patch(Vec<Edit>);
7
8impl Patch {
9 fn compose(&self, other: &Self) -> Self {
10 let mut old_edits_iter = self.0.iter().cloned().peekable();
11 let mut new_edits_iter = other.0.iter().cloned().peekable();
12 let mut composed = Patch(Vec::new());
13
14 let mut old_start = 0;
15 let mut new_start = 0;
16 loop {
17 match (old_edits_iter.peek_mut(), new_edits_iter.peek_mut()) {
18 (None, None) => break,
19 (Some(old_edit), None) => {
20 let catchup = old_edit.old.start - old_start;
21 old_start += catchup;
22 new_start += catchup;
23
24 let old_end = old_start + old_edit.old.len() as u32;
25 let new_end = new_start + old_edit.new.len() as u32;
26 composed.push(Edit {
27 old: old_start..old_end,
28 new: new_start..new_end,
29 });
30 old_start = old_end;
31 new_start = new_end;
32 old_edits_iter.next();
33 }
34 (None, Some(new_edit)) => {
35 let catchup = new_edit.new.start - new_start;
36 old_start += catchup;
37 new_start += catchup;
38
39 let old_end = old_start + new_edit.old.len() as u32;
40 let new_end = new_start + new_edit.new.len() as u32;
41 composed.push(Edit {
42 old: old_start..old_end,
43 new: new_start..new_end,
44 });
45 old_start = old_end;
46 new_start = new_end;
47 new_edits_iter.next();
48 }
49 (Some(old_edit), Some(new_edit)) => {
50 if old_edit.new.end < new_edit.old.start {
51 let catchup = old_edit.old.start - old_start;
52 old_start += catchup;
53 new_start += catchup;
54
55 let old_end = old_start + old_edit.old.len() as u32;
56 let new_end = new_start + old_edit.new.len() as u32;
57 composed.push(Edit {
58 old: old_start..old_end,
59 new: new_start..new_end,
60 });
61 old_start = old_end;
62 new_start = new_end;
63 old_edits_iter.next();
64 continue;
65 } else if new_edit.old.end < old_edit.new.start {
66 let catchup = new_edit.new.start - new_start;
67 old_start += catchup;
68 new_start += catchup;
69
70 let old_end = old_start + new_edit.old.len() as u32;
71 let new_end = new_start + new_edit.new.len() as u32;
72 composed.push(Edit {
73 old: old_start..old_end,
74 new: new_start..new_end,
75 });
76 old_start = old_end;
77 new_start = new_end;
78 new_edits_iter.next();
79 } else {
80 if old_edit.new.start < new_edit.old.start {
81 let catchup = old_edit.old.start - old_start;
82 old_start += catchup;
83 new_start += catchup;
84
85 let overshoot = new_edit.old.start - old_edit.new.start;
86 let old_end = cmp::min(old_start + overshoot, old_edit.old.end);
87 let new_end = new_start + overshoot;
88 composed.push(Edit {
89 old: old_start..old_end,
90 new: new_start..new_end,
91 });
92
93 old_edit.old.start += overshoot;
94 old_edit.new.start += overshoot;
95 old_start = old_end;
96 new_start = new_end;
97 } else {
98 let catchup = new_edit.new.start - new_start;
99 old_start += catchup;
100 new_start += catchup;
101
102 let overshoot = old_edit.new.start - new_edit.old.start;
103 let old_end = old_start + overshoot;
104 let new_end = cmp::min(new_start + overshoot, new_edit.new.end);
105 composed.push(Edit {
106 old: old_start..old_end,
107 new: new_start..new_end,
108 });
109
110 new_edit.old.start += overshoot;
111 new_edit.new.start += overshoot;
112 old_start = old_end;
113 new_start = new_end;
114 }
115
116 if old_edit.new.end > new_edit.old.end {
117 let old_len =
118 cmp::min(old_edit.old.len() as u32, new_edit.old.len() as u32);
119
120 let old_end = old_start + old_len;
121 let new_end = new_start + new_edit.new.len() as u32;
122 composed.push(Edit {
123 old: old_start..old_end,
124 new: new_start..new_end,
125 });
126
127 old_edit.old.start = old_end;
128 old_edit.new.start = new_edit.old.end;
129 old_start = old_end;
130 new_start = new_end;
131 new_edits_iter.next();
132 } else {
133 let new_len =
134 cmp::min(old_edit.new.len() as u32, new_edit.new.len() as u32);
135
136 let old_end = old_start + old_edit.old.len() as u32;
137 let new_end = new_start + new_len;
138 composed.push(Edit {
139 old: old_start..old_end,
140 new: new_start..new_end,
141 });
142
143 new_edit.old.start = old_edit.new.end;
144 new_edit.new.start = new_end;
145 old_start = old_end;
146 new_start = new_end;
147 old_edits_iter.next();
148 }
149 }
150 }
151 }
152 }
153
154 composed
155 }
156
157 fn push(&mut self, edit: Edit) {
158 if edit.old.len() == 0 && edit.new.len() == 0 {
159 return;
160 }
161
162 if let Some(last) = self.0.last_mut() {
163 if last.old.end >= edit.old.start {
164 last.old.end = edit.old.end;
165 last.new.end = edit.new.end;
166 } else {
167 self.0.push(edit);
168 }
169 } else {
170 self.0.push(edit);
171 }
172 }
173}
174
175#[cfg(test)]
176mod tests {
177 use super::*;
178 use rand::prelude::*;
179 use std::env;
180
181 #[gpui::test]
182 fn test_one_disjoint_edit() {
183 assert_patch_composition(
184 Patch(vec![Edit {
185 old: 1..3,
186 new: 1..4,
187 }]),
188 Patch(vec![Edit {
189 old: 0..0,
190 new: 0..4,
191 }]),
192 Patch(vec![
193 Edit {
194 old: 0..0,
195 new: 0..4,
196 },
197 Edit {
198 old: 1..3,
199 new: 5..8,
200 },
201 ]),
202 );
203
204 assert_patch_composition(
205 Patch(vec![Edit {
206 old: 1..3,
207 new: 1..4,
208 }]),
209 Patch(vec![Edit {
210 old: 5..9,
211 new: 5..7,
212 }]),
213 Patch(vec![
214 Edit {
215 old: 1..3,
216 new: 1..4,
217 },
218 Edit {
219 old: 4..8,
220 new: 5..7,
221 },
222 ]),
223 );
224 }
225
226 #[gpui::test]
227 fn test_one_overlapping_edit() {
228 assert_patch_composition(
229 Patch(vec![Edit {
230 old: 1..3,
231 new: 1..4,
232 }]),
233 Patch(vec![Edit {
234 old: 3..5,
235 new: 3..6,
236 }]),
237 Patch(vec![Edit {
238 old: 1..4,
239 new: 1..6,
240 }]),
241 );
242 }
243
244 #[gpui::test]
245 fn test_two_disjoint_and_overlapping() {
246 assert_patch_composition(
247 Patch(vec![
248 Edit {
249 old: 1..3,
250 new: 1..4,
251 },
252 Edit {
253 old: 8..12,
254 new: 9..11,
255 },
256 ]),
257 Patch(vec![
258 Edit {
259 old: 0..0,
260 new: 0..4,
261 },
262 Edit {
263 old: 3..10,
264 new: 7..9,
265 },
266 ]),
267 Patch(vec![
268 Edit {
269 old: 0..0,
270 new: 0..4,
271 },
272 Edit {
273 old: 1..12,
274 new: 5..10,
275 },
276 ]),
277 );
278 }
279
280 #[gpui::test]
281 fn test_two_new_edits_overlapping_one_old_edit() {
282 assert_patch_composition(
283 Patch(vec![Edit {
284 old: 0..0,
285 new: 0..3,
286 }]),
287 Patch(vec![
288 Edit {
289 old: 0..0,
290 new: 0..1,
291 },
292 Edit {
293 old: 1..2,
294 new: 2..2,
295 },
296 ]),
297 Patch(vec![Edit {
298 old: 0..0,
299 new: 0..3,
300 }]),
301 );
302
303 assert_patch_composition(
304 Patch(vec![Edit {
305 old: 2..3,
306 new: 2..4,
307 }]),
308 Patch(vec![
309 Edit {
310 old: 0..2,
311 new: 0..1,
312 },
313 Edit {
314 old: 3..3,
315 new: 2..5,
316 },
317 ]),
318 Patch(vec![Edit {
319 old: 0..3,
320 new: 0..6,
321 }]),
322 );
323
324 assert_patch_composition(
325 Patch(vec![Edit {
326 old: 0..0,
327 new: 0..2,
328 }]),
329 Patch(vec![
330 Edit {
331 old: 0..0,
332 new: 0..2,
333 },
334 Edit {
335 old: 2..5,
336 new: 4..4,
337 },
338 ]),
339 Patch(vec![Edit {
340 old: 0..3,
341 new: 0..4,
342 }]),
343 );
344 }
345
346 // #[test]
347 // fn test_compose_edits() {
348 // assert_eq!(
349 // compose_edits(
350 // &Edit {
351 // old: 3..3,
352 // new: 3..6,
353 // },
354 // &Edit {
355 // old: 2..7,
356 // new: 2..4,
357 // },
358 // ),
359 // Edit {
360 // old: 2..4,
361 // new: 2..4
362 // }
363 // );
364 // }
365
366 #[gpui::test]
367 fn test_two_new_edits_touching_one_old_edit() {
368 assert_patch_composition(
369 Patch(vec![
370 Edit {
371 old: 2..3,
372 new: 2..4,
373 },
374 Edit {
375 old: 7..7,
376 new: 8..11,
377 },
378 ]),
379 Patch(vec![
380 Edit {
381 old: 2..3,
382 new: 2..2,
383 },
384 Edit {
385 old: 4..4,
386 new: 3..4,
387 },
388 ]),
389 Patch(vec![
390 Edit {
391 old: 2..3,
392 new: 2..4,
393 },
394 Edit {
395 old: 7..7,
396 new: 8..11,
397 },
398 ]),
399 );
400 }
401
402 #[gpui::test(iterations = 100, seed = 1)]
403 fn test_random_patch_compositions(mut rng: StdRng) {
404 let operations = env::var("OPERATIONS")
405 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
406 .unwrap_or(5);
407
408 let initial_chars = (0..rng.gen_range(0..=10))
409 .map(|_| rng.gen_range(b'a'..=b'z') as char)
410 .collect::<Vec<_>>();
411 println!("initial chars: {:?}", initial_chars);
412
413 // Generate two sequential patches
414 let mut patches = Vec::new();
415 let mut expected_chars = initial_chars.clone();
416 for i in 0..2 {
417 println!("patch {}:", i);
418
419 let mut delta = 0i32;
420 let mut last_edit_end = 0;
421 let mut edits = Vec::new();
422
423 for _ in 0..operations {
424 if last_edit_end >= expected_chars.len() {
425 break;
426 }
427
428 let end = rng.gen_range(last_edit_end..=expected_chars.len());
429 let start = rng.gen_range(last_edit_end..=end);
430 let old_len = end - start;
431
432 let mut new_len = rng.gen_range(0..=3);
433 if start == end && new_len == 0 {
434 new_len += 1;
435 }
436
437 last_edit_end = start + new_len + 1;
438
439 let new_chars = (0..new_len)
440 .map(|_| rng.gen_range(b'A'..=b'Z') as char)
441 .collect::<Vec<_>>();
442 println!(
443 " editing {:?}: {:?}",
444 start..end,
445 new_chars.iter().collect::<String>()
446 );
447 edits.push(Edit {
448 old: (start as i32 - delta) as u32..(end as i32 - delta) as u32,
449 new: start as u32..(start + new_len) as u32,
450 });
451 expected_chars.splice(start..end, new_chars);
452
453 delta += new_len as i32 - old_len as i32;
454 }
455
456 patches.push(Patch(edits));
457 }
458
459 println!("old patch: {:?}", &patches[0]);
460 println!("new patch: {:?}", &patches[1]);
461 println!("initial chars: {:?}", initial_chars);
462 println!("final chars: {:?}", expected_chars);
463
464 // Compose the patches, and verify that it has the same effect as applying the
465 // two patches separately.
466 let composed = patches[0].compose(&patches[1]);
467 println!("composed patch: {:?}", &composed);
468
469 let mut actual_chars = initial_chars.clone();
470 for edit in composed.0 {
471 actual_chars.splice(
472 edit.new.start as usize..edit.new.start as usize + edit.old.len(),
473 expected_chars[edit.new.start as usize..edit.new.end as usize]
474 .iter()
475 .copied(),
476 );
477 }
478
479 assert_eq!(actual_chars, expected_chars);
480 }
481
482 #[track_caller]
483 fn assert_patch_composition(old: Patch, new: Patch, composed: Patch) {
484 let original = ('a'..'z').collect::<Vec<_>>();
485 let inserted = ('A'..'Z').collect::<Vec<_>>();
486
487 let mut expected = original.clone();
488 apply_patch(&mut expected, &old, &inserted);
489 apply_patch(&mut expected, &new, &inserted);
490
491 let mut actual = original.clone();
492 apply_patch(&mut actual, &composed, &expected);
493 assert_eq!(
494 actual.into_iter().collect::<String>(),
495 expected.into_iter().collect::<String>(),
496 "expected patch is incorrect"
497 );
498
499 assert_eq!(old.compose(&new), composed);
500 }
501
502 fn apply_patch(text: &mut Vec<char>, patch: &Patch, new_text: &[char]) {
503 for edit in patch.0.iter().rev() {
504 text.splice(
505 edit.old.start as usize..edit.old.end as usize,
506 new_text[edit.new.start as usize..edit.new.end as usize]
507 .iter()
508 .copied(),
509 );
510 }
511 }
512}