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