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