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