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