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