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