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