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