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