1use std::mem;
2
3type Edit = buffer::Edit<u32>;
4
5#[derive(Default, Debug)]
6struct Patch(Vec<Edit>);
7
8impl Patch {
9 fn compose(&self, new: &Self) -> Patch {
10 let mut composed = Vec::new();
11 let mut new_edits = new.0.iter().cloned().peekable();
12 let mut old_delta = 0;
13 let mut new_delta = 0;
14
15 for mut old_edit in self.0.iter().cloned() {
16 let old_edit_new_start = old_edit.new.start;
17 let old_edit_new_end = old_edit.new.end;
18 let mut next_new_delta = new_delta;
19 while let Some(mut new_edit) = new_edits.peek().cloned() {
20 let new_edit_delta = new_edit.new.len() as i32 - new_edit.old.len() as i32;
21 if new_edit.old.end < old_edit_new_start {
22 new_edit.old.start = (new_edit.old.start as i32 - old_delta) as u32;
23 new_edit.old.end = (new_edit.old.end as i32 - old_delta) as u32;
24 new_edits.next();
25 new_delta += new_edit_delta;
26 next_new_delta += new_edit_delta;
27 composed.push(new_edit);
28 } else if new_edit.old.start <= old_edit_new_end {
29 if new_edit.old.start < old_edit_new_start {
30 old_edit.old.start -= old_edit_new_start - new_edit.old.start;
31 old_edit.new.start -= old_edit_new_start - new_edit.old.start;
32 }
33 if new_edit.old.end > old_edit_new_end {
34 old_edit.old.end += new_edit.old.end - old_edit_new_end;
35 old_edit.new.end += new_edit.old.end - old_edit_new_end;
36 }
37
38 old_edit.new.end = (old_edit.new.end as i32 + new_edit_delta) as u32;
39 new_edits.next();
40 next_new_delta += new_edit_delta;
41 } else {
42 break;
43 }
44 }
45
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 old_delta += old_edit.new.len() as i32 - old_edit.old.len() as i32;
49 new_delta = next_new_delta;
50 composed.push(old_edit);
51 }
52 composed.extend(new_edits.map(|mut new_edit| {
53 new_edit.old.start = (new_edit.old.start as i32 - old_delta) as u32;
54 new_edit.old.end = (new_edit.old.end as i32 - old_delta) as u32;
55 new_edit
56 }));
57
58 Patch(composed)
59 }
60
61 fn invert(&mut self) -> &mut Self {
62 for edit in &mut self.0 {
63 mem::swap(&mut edit.old, &mut edit.new);
64 }
65 self
66 }
67}
68
69#[cfg(test)]
70mod tests {
71 use super::*;
72 use rand::prelude::*;
73 use std::env;
74
75 #[gpui::test(iterations = 1000, seed = 131)]
76 fn test_random(mut rng: StdRng) {
77 let operations = env::var("OPERATIONS")
78 .map(|i| i.parse().expect("invalid `OPERATIONS` variable"))
79 .unwrap_or(3);
80
81 let initial_chars = (0..rng.gen_range(0..=5))
82 .map(|_| rng.gen_range(b'a'..=b'z') as char)
83 .collect::<Vec<_>>();
84 let mut final_chars = initial_chars.clone();
85 let mut patches = Vec::new();
86
87 println!("initial chars: {:?}", initial_chars);
88 for _ in 0..operations {
89 let end = rng.gen_range(0..=final_chars.len());
90 let start = rng.gen_range(0..=end);
91 let mut len = rng.gen_range(0..=3);
92 if start == end && len == 0 {
93 len += 1;
94 }
95 let new_chars = (0..len)
96 .map(|_| rng.gen_range(b'a'..=b'z') as char)
97 .collect::<Vec<_>>();
98 println!(
99 "editing {:?}: {:?}",
100 start..end,
101 new_chars.iter().collect::<String>()
102 );
103
104 let patch = Patch(vec![Edit {
105 old: start as u32..end as u32,
106 new: start as u32..start as u32 + new_chars.len() as u32,
107 }]);
108 if patches.is_empty() || rng.gen() {
109 println!("pushing singleton patch: {:?}", patch.0);
110 patches.push(patch);
111 } else {
112 let patch = patches.pop().unwrap().compose(&patch);
113 println!("composed patches: {:?}", patch.0);
114 patches.push(patch);
115 }
116 final_chars.splice(start..end, new_chars);
117 }
118
119 println!("final chars: {:?}", final_chars);
120 println!("final patches: {:?}", patches);
121
122 let mut composed = Patch::default();
123 for patch in patches {
124 println!("composing patches {:?} and {:?}", composed, patch);
125 composed = composed.compose(&patch);
126 println!("composed {:?}", composed);
127 }
128 println!("composed edits: {:?}", composed);
129 let mut chars = initial_chars.clone();
130 for edit in composed.0 {
131 chars.splice(
132 edit.new.start as usize..edit.new.start as usize + edit.old.len(),
133 final_chars[edit.new.start as usize..edit.new.end as usize]
134 .iter()
135 .copied(),
136 );
137 }
138
139 assert_eq!(chars, final_chars);
140 }
141}