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