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