1use crate::Edit;
2use std::{
3 cmp, mem,
4 ops::{Add, AddAssign, Sub},
5};
6
7#[derive(Clone, Default, Debug, PartialEq, Eq)]
8pub struct Patch<T>(Vec<Edit<T>>);
9
10impl<T> Patch<T>
11where
12 T: 'static + Clone + Copy + Ord + Default,
13{
14 pub const fn empty() -> Self {
15 Self(Vec::new())
16 }
17
18 pub fn new(edits: Vec<Edit<T>>) -> Self {
19 #[cfg(debug_assertions)]
20 {
21 let mut last_edit: Option<&Edit<T>> = None;
22 for edit in &edits {
23 if let Some(last_edit) = last_edit {
24 assert!(edit.old.start > last_edit.old.end);
25 assert!(edit.new.start > last_edit.new.end);
26 }
27 last_edit = Some(edit);
28 }
29 }
30 Self(edits)
31 }
32
33 pub fn edits(&self) -> &[Edit<T>] {
34 &self.0
35 }
36
37 pub fn into_inner(self) -> Vec<Edit<T>> {
38 self.0
39 }
40 pub fn invert(&mut self) -> &mut Self {
41 for edit in &mut self.0 {
42 mem::swap(&mut edit.old, &mut edit.new);
43 }
44 self
45 }
46
47 pub fn clear(&mut self) {
48 self.0.clear();
49 }
50
51 pub fn is_empty(&self) -> bool {
52 self.0.is_empty()
53 }
54
55 pub fn push(&mut self, edit: Edit<T>) {
56 if edit.is_empty() {
57 return;
58 }
59
60 if let Some(last) = self.0.last_mut() {
61 if last.old.end >= edit.old.start {
62 last.old.end = edit.old.end;
63 last.new.end = edit.new.end;
64 } else {
65 self.0.push(edit);
66 }
67 } else {
68 self.0.push(edit);
69 }
70 }
71}
72
73impl<T, TDelta> Patch<T>
74where
75 T: 'static
76 + Copy
77 + Ord
78 + Sub<T, Output = TDelta>
79 + Add<TDelta, Output = T>
80 + AddAssign<TDelta>
81 + Default,
82 TDelta: Ord + Copy,
83{
84 #[must_use]
85 pub fn compose(&self, new_edits_iter: impl IntoIterator<Item = Edit<T>>) -> Self {
86 let mut old_edits_iter = self.0.iter().cloned().peekable();
87 let mut new_edits_iter = new_edits_iter.into_iter().peekable();
88 let mut composed = Patch(Vec::new());
89
90 let mut old_start = T::default();
91 let mut new_start = T::default();
92 loop {
93 let old_edit = old_edits_iter.peek_mut();
94 let new_edit = new_edits_iter.peek_mut();
95
96 // Push the old edit if its new end is before the new edit's old start.
97 if let Some(old_edit) = old_edit.as_ref() {
98 let new_edit = new_edit.as_ref();
99 if new_edit.is_none_or(|new_edit| old_edit.new.end < new_edit.old.start) {
100 let catchup = old_edit.old.start - old_start;
101 old_start += catchup;
102 new_start += catchup;
103
104 let old_end = old_start + old_edit.old_len();
105 let new_end = new_start + old_edit.new_len();
106 composed.push(Edit {
107 old: old_start..old_end,
108 new: new_start..new_end,
109 });
110 old_start = old_end;
111 new_start = new_end;
112 old_edits_iter.next();
113 continue;
114 }
115 }
116
117 // Push the new edit if its old end is before the old edit's new start.
118 if let Some(new_edit) = new_edit.as_ref() {
119 let old_edit = old_edit.as_ref();
120 if old_edit.is_none_or(|old_edit| new_edit.old.end < old_edit.new.start) {
121 let catchup = new_edit.new.start - new_start;
122 old_start += catchup;
123 new_start += catchup;
124
125 let old_end = old_start + new_edit.old_len();
126 let new_end = new_start + new_edit.new_len();
127 composed.push(Edit {
128 old: old_start..old_end,
129 new: new_start..new_end,
130 });
131 old_start = old_end;
132 new_start = new_end;
133 new_edits_iter.next();
134 continue;
135 }
136 }
137
138 // If we still have edits by this point then they must intersect, so we compose them.
139 if let Some((old_edit, new_edit)) = old_edit.zip(new_edit) {
140 if old_edit.new.start < new_edit.old.start {
141 let catchup = old_edit.old.start - old_start;
142 old_start += catchup;
143 new_start += catchup;
144
145 let overshoot = new_edit.old.start - old_edit.new.start;
146 let old_end = cmp::min(old_start + overshoot, old_edit.old.end);
147 let new_end = new_start + overshoot;
148 composed.push(Edit {
149 old: old_start..old_end,
150 new: new_start..new_end,
151 });
152
153 old_edit.old.start = old_end;
154 old_edit.new.start += overshoot;
155 old_start = old_end;
156 new_start = new_end;
157 } else {
158 let catchup = new_edit.new.start - new_start;
159 old_start += catchup;
160 new_start += catchup;
161
162 let overshoot = old_edit.new.start - new_edit.old.start;
163 let old_end = old_start + overshoot;
164 let new_end = cmp::min(new_start + overshoot, new_edit.new.end);
165 composed.push(Edit {
166 old: old_start..old_end,
167 new: new_start..new_end,
168 });
169
170 new_edit.old.start += overshoot;
171 new_edit.new.start = new_end;
172 old_start = old_end;
173 new_start = new_end;
174 }
175
176 if old_edit.new.end > new_edit.old.end {
177 let old_end = old_start + cmp::min(old_edit.old_len(), new_edit.old_len());
178 let new_end = new_start + new_edit.new_len();
179 composed.push(Edit {
180 old: old_start..old_end,
181 new: new_start..new_end,
182 });
183
184 old_edit.old.start = old_end;
185 old_edit.new.start = new_edit.old.end;
186 old_start = old_end;
187 new_start = new_end;
188 new_edits_iter.next();
189 } else {
190 let old_end = old_start + old_edit.old_len();
191 let new_end = new_start + cmp::min(old_edit.new_len(), new_edit.new_len());
192 composed.push(Edit {
193 old: old_start..old_end,
194 new: new_start..new_end,
195 });
196
197 new_edit.old.start = old_edit.new.end;
198 new_edit.new.start = new_end;
199 old_start = old_end;
200 new_start = new_end;
201 old_edits_iter.next();
202 }
203 } else {
204 break;
205 }
206 }
207
208 composed
209 }
210
211 pub fn old_to_new(&self, old: T) -> T {
212 let ix = match self.0.binary_search_by(|probe| probe.old.start.cmp(&old)) {
213 Ok(ix) => ix,
214 Err(ix) => {
215 if ix == 0 {
216 return old;
217 } else {
218 ix - 1
219 }
220 }
221 };
222 if let Some(edit) = self.0.get(ix) {
223 if old >= edit.old.end {
224 edit.new.end + (old - edit.old.end)
225 } else {
226 edit.new.start
227 }
228 } else {
229 old
230 }
231 }
232
233 /// Returns the edit that touches the given old position.
234 ///
235 /// An edit is considered to touch the given old position if edit.old.start <= old <= edit.old.end (note, inclusive on the right).
236 ///
237 /// If there are no edits touching the given old position, an empty edit with appropriate (empty) old and new ranges is returned.
238 pub fn edit_for_old_position(&self, old: T) -> Edit<T> {
239 let edits = self.edits();
240
241 let ix = match edits.binary_search_by(|probe| probe.old.start.cmp(&old)) {
242 Ok(ix) => ix,
243 Err(ix) => {
244 if ix == 0 {
245 return Edit {
246 old: old..old,
247 new: old..old,
248 };
249 } else {
250 ix - 1
251 }
252 }
253 };
254
255 if let Some(edit) = edits.get(ix) {
256 if old > edit.old.end {
257 let translated = edit.new.end + (old - edit.old.end);
258 Edit {
259 new: translated..translated,
260 old: old..old,
261 }
262 } else {
263 edit.clone()
264 }
265 } else {
266 Edit {
267 old: old..old,
268 new: old..old,
269 }
270 }
271 }
272}
273
274impl<T> Patch<T> {
275 pub fn retain_mut<F>(&mut self, f: F)
276 where
277 F: FnMut(&mut Edit<T>) -> bool,
278 {
279 self.0.retain_mut(f);
280 }
281}
282
283impl<T: Clone> IntoIterator for Patch<T> {
284 type Item = Edit<T>;
285 type IntoIter = std::vec::IntoIter<Edit<T>>;
286
287 fn into_iter(self) -> Self::IntoIter {
288 self.0.into_iter()
289 }
290}
291
292impl<'a, T: Clone> IntoIterator for &'a Patch<T> {
293 type Item = Edit<T>;
294 type IntoIter = std::iter::Cloned<std::slice::Iter<'a, Edit<T>>>;
295
296 fn into_iter(self) -> Self::IntoIter {
297 self.0.iter().cloned()
298 }
299}
300
301impl<'a, T: Clone> IntoIterator for &'a mut Patch<T> {
302 type Item = Edit<T>;
303 type IntoIter = std::iter::Cloned<std::slice::Iter<'a, Edit<T>>>;
304
305 fn into_iter(self) -> Self::IntoIter {
306 self.0.iter().cloned()
307 }
308}
309
310#[cfg(test)]
311mod tests {
312 use super::*;
313 use rand::prelude::*;
314 use std::env;
315
316 #[gpui::test]
317 fn test_one_disjoint_edit() {
318 assert_patch_composition(
319 Patch(vec![Edit {
320 old: 1..3,
321 new: 1..4,
322 }]),
323 Patch(vec![Edit {
324 old: 0..0,
325 new: 0..4,
326 }]),
327 Patch(vec![
328 Edit {
329 old: 0..0,
330 new: 0..4,
331 },
332 Edit {
333 old: 1..3,
334 new: 5..8,
335 },
336 ]),
337 );
338
339 assert_patch_composition(
340 Patch(vec![Edit {
341 old: 1..3,
342 new: 1..4,
343 }]),
344 Patch(vec![Edit {
345 old: 5..9,
346 new: 5..7,
347 }]),
348 Patch(vec![
349 Edit {
350 old: 1..3,
351 new: 1..4,
352 },
353 Edit {
354 old: 4..8,
355 new: 5..7,
356 },
357 ]),
358 );
359 }
360
361 #[gpui::test]
362 fn test_one_overlapping_edit() {
363 assert_patch_composition(
364 Patch(vec![Edit {
365 old: 1..3,
366 new: 1..4,
367 }]),
368 Patch(vec![Edit {
369 old: 3..5,
370 new: 3..6,
371 }]),
372 Patch(vec![Edit {
373 old: 1..4,
374 new: 1..6,
375 }]),
376 );
377 }
378
379 #[gpui::test]
380 fn test_two_disjoint_and_overlapping() {
381 assert_patch_composition(
382 Patch(vec![
383 Edit {
384 old: 1..3,
385 new: 1..4,
386 },
387 Edit {
388 old: 8..12,
389 new: 9..11,
390 },
391 ]),
392 Patch(vec![
393 Edit {
394 old: 0..0,
395 new: 0..4,
396 },
397 Edit {
398 old: 3..10,
399 new: 7..9,
400 },
401 ]),
402 Patch(vec![
403 Edit {
404 old: 0..0,
405 new: 0..4,
406 },
407 Edit {
408 old: 1..12,
409 new: 5..10,
410 },
411 ]),
412 );
413 }
414
415 #[gpui::test]
416 fn test_two_new_edits_overlapping_one_old_edit() {
417 assert_patch_composition(
418 Patch(vec![Edit {
419 old: 0..0,
420 new: 0..3,
421 }]),
422 Patch(vec![
423 Edit {
424 old: 0..0,
425 new: 0..1,
426 },
427 Edit {
428 old: 1..2,
429 new: 2..2,
430 },
431 ]),
432 Patch(vec![Edit {
433 old: 0..0,
434 new: 0..3,
435 }]),
436 );
437
438 assert_patch_composition(
439 Patch(vec![Edit {
440 old: 2..3,
441 new: 2..4,
442 }]),
443 Patch(vec![
444 Edit {
445 old: 0..2,
446 new: 0..1,
447 },
448 Edit {
449 old: 3..3,
450 new: 2..5,
451 },
452 ]),
453 Patch(vec![Edit {
454 old: 0..3,
455 new: 0..6,
456 }]),
457 );
458
459 assert_patch_composition(
460 Patch(vec![Edit {
461 old: 0..0,
462 new: 0..2,
463 }]),
464 Patch(vec![
465 Edit {
466 old: 0..0,
467 new: 0..2,
468 },
469 Edit {
470 old: 2..5,
471 new: 4..4,
472 },
473 ]),
474 Patch(vec![Edit {
475 old: 0..3,
476 new: 0..4,
477 }]),
478 );
479 }
480
481 #[gpui::test]
482 fn test_two_new_edits_touching_one_old_edit() {
483 assert_patch_composition(
484 Patch(vec![
485 Edit {
486 old: 2..3,
487 new: 2..4,
488 },
489 Edit {
490 old: 7..7,
491 new: 8..11,
492 },
493 ]),
494 Patch(vec![
495 Edit {
496 old: 2..3,
497 new: 2..2,
498 },
499 Edit {
500 old: 4..4,
501 new: 3..4,
502 },
503 ]),
504 Patch(vec![
505 Edit {
506 old: 2..3,
507 new: 2..4,
508 },
509 Edit {
510 old: 7..7,
511 new: 8..11,
512 },
513 ]),
514 );
515 }
516
517 #[gpui::test]
518 fn test_old_to_new() {
519 let patch = Patch(vec![
520 Edit {
521 old: 2..4,
522 new: 2..4,
523 },
524 Edit {
525 old: 7..8,
526 new: 7..11,
527 },
528 ]);
529 assert_eq!(patch.old_to_new(0), 0);
530 assert_eq!(patch.old_to_new(1), 1);
531 assert_eq!(patch.old_to_new(2), 2);
532 assert_eq!(patch.old_to_new(3), 2);
533 assert_eq!(patch.old_to_new(4), 4);
534 assert_eq!(patch.old_to_new(5), 5);
535 assert_eq!(patch.old_to_new(6), 6);
536 assert_eq!(patch.old_to_new(7), 7);
537 assert_eq!(patch.old_to_new(8), 11);
538 assert_eq!(patch.old_to_new(9), 12);
539 }
540
541 #[gpui::test(iterations = 100)]
542 fn test_random_patch_compositions(mut rng: StdRng) {
543 let operations = env::var("OPERATIONS")
544 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
545 .unwrap_or(20);
546
547 let initial_chars = (0..rng.random_range(0..=100))
548 .map(|_| rng.random_range(b'a'..=b'z') as char)
549 .collect::<Vec<_>>();
550 log::info!("initial chars: {:?}", initial_chars);
551
552 // Generate two sequential patches
553 let mut patches = Vec::new();
554 let mut expected_chars = initial_chars.clone();
555 for i in 0..2 {
556 log::info!("patch {}:", i);
557
558 let mut delta = 0i32;
559 let mut last_edit_end = 0;
560 let mut edits = Vec::new();
561
562 for _ in 0..operations {
563 if last_edit_end >= expected_chars.len() {
564 break;
565 }
566
567 let end = rng.random_range(last_edit_end..=expected_chars.len());
568 let start = rng.random_range(last_edit_end..=end);
569 let old_len = end - start;
570
571 let mut new_len = rng.random_range(0..=3);
572 if start == end && new_len == 0 {
573 new_len += 1;
574 }
575
576 last_edit_end = start + new_len + 1;
577
578 let new_chars = (0..new_len)
579 .map(|_| rng.random_range(b'A'..=b'Z') as char)
580 .collect::<Vec<_>>();
581 log::info!(
582 " editing {:?}: {:?}",
583 start..end,
584 new_chars.iter().collect::<String>()
585 );
586 edits.push(Edit {
587 old: (start as i32 - delta) as u32..(end as i32 - delta) as u32,
588 new: start as u32..(start + new_len) as u32,
589 });
590 expected_chars.splice(start..end, new_chars);
591
592 delta += new_len as i32 - old_len as i32;
593 }
594
595 patches.push(Patch(edits));
596 }
597
598 log::info!("old patch: {:?}", &patches[0]);
599 log::info!("new patch: {:?}", &patches[1]);
600 log::info!("initial chars: {:?}", initial_chars);
601 log::info!("final chars: {:?}", expected_chars);
602
603 // Compose the patches, and verify that it has the same effect as applying the
604 // two patches separately.
605 let composed = patches[0].compose(&patches[1]);
606 log::info!("composed patch: {:?}", &composed);
607
608 let mut actual_chars = initial_chars;
609 for edit in composed.0 {
610 actual_chars.splice(
611 edit.new.start as usize..edit.new.start as usize + edit.old.len(),
612 expected_chars[edit.new.start as usize..edit.new.end as usize]
613 .iter()
614 .copied(),
615 );
616 }
617
618 assert_eq!(actual_chars, expected_chars);
619 }
620
621 #[track_caller]
622 #[allow(clippy::almost_complete_range)]
623 fn assert_patch_composition(old: Patch<u32>, new: Patch<u32>, composed: Patch<u32>) {
624 let original = ('a'..'z').collect::<Vec<_>>();
625 let inserted = ('A'..'Z').collect::<Vec<_>>();
626
627 let mut expected = original.clone();
628 apply_patch(&mut expected, &old, &inserted);
629 apply_patch(&mut expected, &new, &inserted);
630
631 let mut actual = original;
632 apply_patch(&mut actual, &composed, &expected);
633 assert_eq!(
634 actual.into_iter().collect::<String>(),
635 expected.into_iter().collect::<String>(),
636 "expected patch is incorrect"
637 );
638
639 assert_eq!(old.compose(&new), composed);
640 }
641
642 fn apply_patch(text: &mut Vec<char>, patch: &Patch<u32>, new_text: &[char]) {
643 for edit in patch.0.iter().rev() {
644 text.splice(
645 edit.old.start as usize..edit.old.end as usize,
646 new_text[edit.new.start as usize..edit.new.end as usize]
647 .iter()
648 .copied(),
649 );
650 }
651 }
652}