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