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