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