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