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