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