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
204impl<T: Clone> IntoIterator for Patch<T> {
205 type Item = Edit<T>;
206 type IntoIter = std::vec::IntoIter<Edit<T>>;
207
208 fn into_iter(self) -> Self::IntoIter {
209 self.0.into_iter()
210 }
211}
212
213impl<'a, T: Clone> IntoIterator for &'a Patch<T> {
214 type Item = Edit<T>;
215 type IntoIter = std::iter::Cloned<std::slice::Iter<'a, Edit<T>>>;
216
217 fn into_iter(self) -> Self::IntoIter {
218 self.0.iter().cloned()
219 }
220}
221
222impl<'a, T: Clone> IntoIterator for &'a mut Patch<T> {
223 type Item = Edit<T>;
224 type IntoIter = std::iter::Cloned<std::slice::Iter<'a, Edit<T>>>;
225
226 fn into_iter(self) -> Self::IntoIter {
227 self.0.iter().cloned()
228 }
229}
230
231#[cfg(test)]
232mod tests {
233 use super::*;
234 use rand::prelude::*;
235 use std::env;
236
237 #[gpui::test]
238 fn test_one_disjoint_edit() {
239 assert_patch_composition(
240 Patch(vec![Edit {
241 old: 1..3,
242 new: 1..4,
243 }]),
244 Patch(vec![Edit {
245 old: 0..0,
246 new: 0..4,
247 }]),
248 Patch(vec![
249 Edit {
250 old: 0..0,
251 new: 0..4,
252 },
253 Edit {
254 old: 1..3,
255 new: 5..8,
256 },
257 ]),
258 );
259
260 assert_patch_composition(
261 Patch(vec![Edit {
262 old: 1..3,
263 new: 1..4,
264 }]),
265 Patch(vec![Edit {
266 old: 5..9,
267 new: 5..7,
268 }]),
269 Patch(vec![
270 Edit {
271 old: 1..3,
272 new: 1..4,
273 },
274 Edit {
275 old: 4..8,
276 new: 5..7,
277 },
278 ]),
279 );
280 }
281
282 #[gpui::test]
283 fn test_one_overlapping_edit() {
284 assert_patch_composition(
285 Patch(vec![Edit {
286 old: 1..3,
287 new: 1..4,
288 }]),
289 Patch(vec![Edit {
290 old: 3..5,
291 new: 3..6,
292 }]),
293 Patch(vec![Edit {
294 old: 1..4,
295 new: 1..6,
296 }]),
297 );
298 }
299
300 #[gpui::test]
301 fn test_two_disjoint_and_overlapping() {
302 assert_patch_composition(
303 Patch(vec![
304 Edit {
305 old: 1..3,
306 new: 1..4,
307 },
308 Edit {
309 old: 8..12,
310 new: 9..11,
311 },
312 ]),
313 Patch(vec![
314 Edit {
315 old: 0..0,
316 new: 0..4,
317 },
318 Edit {
319 old: 3..10,
320 new: 7..9,
321 },
322 ]),
323 Patch(vec![
324 Edit {
325 old: 0..0,
326 new: 0..4,
327 },
328 Edit {
329 old: 1..12,
330 new: 5..10,
331 },
332 ]),
333 );
334 }
335
336 #[gpui::test]
337 fn test_two_new_edits_overlapping_one_old_edit() {
338 assert_patch_composition(
339 Patch(vec![Edit {
340 old: 0..0,
341 new: 0..3,
342 }]),
343 Patch(vec![
344 Edit {
345 old: 0..0,
346 new: 0..1,
347 },
348 Edit {
349 old: 1..2,
350 new: 2..2,
351 },
352 ]),
353 Patch(vec![Edit {
354 old: 0..0,
355 new: 0..3,
356 }]),
357 );
358
359 assert_patch_composition(
360 Patch(vec![Edit {
361 old: 2..3,
362 new: 2..4,
363 }]),
364 Patch(vec![
365 Edit {
366 old: 0..2,
367 new: 0..1,
368 },
369 Edit {
370 old: 3..3,
371 new: 2..5,
372 },
373 ]),
374 Patch(vec![Edit {
375 old: 0..3,
376 new: 0..6,
377 }]),
378 );
379
380 assert_patch_composition(
381 Patch(vec![Edit {
382 old: 0..0,
383 new: 0..2,
384 }]),
385 Patch(vec![
386 Edit {
387 old: 0..0,
388 new: 0..2,
389 },
390 Edit {
391 old: 2..5,
392 new: 4..4,
393 },
394 ]),
395 Patch(vec![Edit {
396 old: 0..3,
397 new: 0..4,
398 }]),
399 );
400 }
401
402 // #[test]
403 // fn test_compose_edits() {
404 // assert_eq!(
405 // compose_edits(
406 // &Edit {
407 // old: 3..3,
408 // new: 3..6,
409 // },
410 // &Edit {
411 // old: 2..7,
412 // new: 2..4,
413 // },
414 // ),
415 // Edit {
416 // old: 2..4,
417 // new: 2..4
418 // }
419 // );
420 // }
421
422 #[gpui::test]
423 fn test_two_new_edits_touching_one_old_edit() {
424 assert_patch_composition(
425 Patch(vec![
426 Edit {
427 old: 2..3,
428 new: 2..4,
429 },
430 Edit {
431 old: 7..7,
432 new: 8..11,
433 },
434 ]),
435 Patch(vec![
436 Edit {
437 old: 2..3,
438 new: 2..2,
439 },
440 Edit {
441 old: 4..4,
442 new: 3..4,
443 },
444 ]),
445 Patch(vec![
446 Edit {
447 old: 2..3,
448 new: 2..4,
449 },
450 Edit {
451 old: 7..7,
452 new: 8..11,
453 },
454 ]),
455 );
456 }
457
458 #[gpui::test(iterations = 100)]
459 fn test_random_patch_compositions(mut rng: StdRng) {
460 let operations = env::var("OPERATIONS")
461 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
462 .unwrap_or(20);
463
464 let initial_chars = (0..rng.gen_range(0..=100))
465 .map(|_| rng.gen_range(b'a'..=b'z') as char)
466 .collect::<Vec<_>>();
467 log::info!("initial chars: {:?}", initial_chars);
468
469 // Generate two sequential patches
470 let mut patches = Vec::new();
471 let mut expected_chars = initial_chars.clone();
472 for i in 0..2 {
473 log::info!("patch {}:", i);
474
475 let mut delta = 0i32;
476 let mut last_edit_end = 0;
477 let mut edits = Vec::new();
478
479 for _ in 0..operations {
480 if last_edit_end >= expected_chars.len() {
481 break;
482 }
483
484 let end = rng.gen_range(last_edit_end..=expected_chars.len());
485 let start = rng.gen_range(last_edit_end..=end);
486 let old_len = end - start;
487
488 let mut new_len = rng.gen_range(0..=3);
489 if start == end && new_len == 0 {
490 new_len += 1;
491 }
492
493 last_edit_end = start + new_len + 1;
494
495 let new_chars = (0..new_len)
496 .map(|_| rng.gen_range(b'A'..=b'Z') as char)
497 .collect::<Vec<_>>();
498 log::info!(
499 " editing {:?}: {:?}",
500 start..end,
501 new_chars.iter().collect::<String>()
502 );
503 edits.push(Edit {
504 old: (start as i32 - delta) as u32..(end as i32 - delta) as u32,
505 new: start as u32..(start + new_len) as u32,
506 });
507 expected_chars.splice(start..end, new_chars);
508
509 delta += new_len as i32 - old_len as i32;
510 }
511
512 patches.push(Patch(edits));
513 }
514
515 log::info!("old patch: {:?}", &patches[0]);
516 log::info!("new patch: {:?}", &patches[1]);
517 log::info!("initial chars: {:?}", initial_chars);
518 log::info!("final chars: {:?}", expected_chars);
519
520 // Compose the patches, and verify that it has the same effect as applying the
521 // two patches separately.
522 let composed = patches[0].compose(&patches[1]);
523 log::info!("composed patch: {:?}", &composed);
524
525 let mut actual_chars = initial_chars.clone();
526 for edit in composed.0 {
527 actual_chars.splice(
528 edit.new.start as usize..edit.new.start as usize + edit.old.len(),
529 expected_chars[edit.new.start as usize..edit.new.end as usize]
530 .iter()
531 .copied(),
532 );
533 }
534
535 assert_eq!(actual_chars, expected_chars);
536 }
537
538 #[track_caller]
539 fn assert_patch_composition(old: Patch<u32>, new: Patch<u32>, composed: Patch<u32>) {
540 let original = ('a'..'z').collect::<Vec<_>>();
541 let inserted = ('A'..'Z').collect::<Vec<_>>();
542
543 let mut expected = original.clone();
544 apply_patch(&mut expected, &old, &inserted);
545 apply_patch(&mut expected, &new, &inserted);
546
547 let mut actual = original.clone();
548 apply_patch(&mut actual, &composed, &expected);
549 assert_eq!(
550 actual.into_iter().collect::<String>(),
551 expected.into_iter().collect::<String>(),
552 "expected patch is incorrect"
553 );
554
555 assert_eq!(old.compose(&new), composed);
556 }
557
558 fn apply_patch(text: &mut Vec<char>, patch: &Patch<u32>, new_text: &[char]) {
559 for edit in patch.0.iter().rev() {
560 text.splice(
561 edit.old.start as usize..edit.old.end as usize,
562 new_text[edit.new.start as usize..edit.new.end as usize]
563 .iter()
564 .copied(),
565 );
566 }
567 }
568}