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