1use std::{collections::VecDeque, io};
6
7pub fn diff(
8 text1: &[String],
9 text2: &[String],
10 context_radius: usize,
11) -> io::Result<Vec<String>> {
12 let mut processor = Processor::new(&text1, &text2, context_radius);
13 {
14 let mut replace = diffs::Replace::new(&mut processor);
15 diffs::myers::diff(&mut replace, &text1, &text2)?;
16 }
17 Ok(processor.result())
18}
19
20struct Processor<'a> {
21 text1: &'a [String],
22 text2: &'a [String],
23
24 context_radius: usize,
25 inserted: usize,
26 removed: usize,
27
28 context: Context,
29 result: Vec<String>,
30}
31
32impl<'a> Processor<'a> {
33 pub fn new(text1: &'a [String], text2: &'a [String], context_radius: usize) -> Self {
34 Self {
35 text1,
36 text2,
37
38 context_radius,
39 inserted: 0,
40 removed: 0,
41
42 context: Context::new(),
43 result: Vec::new(),
44 }
45 }
46
47 pub fn result(self) -> Vec<String> {
48 self.result
49 }
50}
51
52struct Context {
53 pub start: Option<usize>,
54 pub data: VecDeque<String>,
55 pub changed: bool,
56
57 pub counter: usize,
58 pub equaled: usize,
59 pub removed: usize,
60 pub inserted: usize,
61}
62
63impl Context {
64 pub fn new() -> Self {
65 Self {
66 start: None,
67 data: VecDeque::new(),
68 changed: false,
69
70 counter: 0,
71 equaled: 0,
72 removed: 0,
73 inserted: 0,
74 }
75 }
76
77 pub fn to_vec(&self, removed: usize, inserted: usize) -> Vec<String> {
78 let mut start = if let Some(start) = self.start {
79 start
80 } else {
81 return Vec::new();
82 };
83 if start == 0 {
84 start = 1;
85 }
86 let mut data = Vec::with_capacity(self.data.len() + 1);
87 if self.changed {
88 data.push(format!(
89 "@@ -{},{} +{},{} @@",
90 start,
91 self.equaled + self.removed,
92 start + inserted - removed,
93 self.equaled + self.inserted,
94 ));
95 for s in self.data.iter() {
96 data.push(s.to_owned());
97 }
98 }
99 data
100 }
101}
102
103impl<'a> diffs::Diff for Processor<'a> {
104 type Error = io::Error;
105
106 fn equal(&mut self, old: usize, _new: usize, len: usize) -> Result<(), Self::Error> {
107 if self.context.start.is_none() {
108 self.context.start = Some(old);
109 }
110
111 self.context.counter = 0;
112 for i in old..old + len {
113 if !self.context.changed {
114 if self.context.counter < self.context_radius {
115 self.context.data.push_back(format!(" {}", self.text1[i]));
116 self.context.equaled += 1;
117 self.context.counter += 1;
118 }
119 if self.context.counter >= self.context_radius {
120 self.context.data.push_back(format!(" {}", self.text1[i]));
121 self.context.data.pop_front();
122 if let Some(ref mut start) = self.context.start {
123 *start += 1;
124 }
125 self.context.counter += 1;
126 }
127 }
128 if self.context.changed {
129 if self.context.counter < self.context_radius * 2 {
130 self.context.data.push_back(format!(" {}", self.text1[i]));
131 self.context.equaled += 1;
132 self.context.counter += 1;
133 }
134 if self.context.counter == self.context_radius && len > self.context_radius * 2 {
135 self.result
136 .append(&mut self.context.to_vec(self.removed, self.inserted));
137
138 let mut context = Context::new();
139 for _ in 0..self.context_radius {
140 context.data.push_back(String::new());
141 }
142 context.counter = self.context_radius;
143 context.equaled = self.context_radius;
144 context.start = Some(i - 1);
145
146 self.removed += self.context.removed;
147 self.inserted += self.context.inserted;
148 self.context = context;
149 }
150 }
151 }
152
153 Ok(())
154 }
155
156 fn delete(&mut self, old: usize, len: usize) -> Result<(), Self::Error> {
157 if self.context.start.is_none() {
158 self.context.start = Some(old);
159 }
160
161 for i in old..old + len {
162 self.context.data.push_back(format!("-{}", self.text1[i]));
163 }
164 self.context.changed = true;
165 self.context.removed += len;
166
167 Ok(())
168 }
169
170 fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), Self::Error> {
171 if self.context.start.is_none() {
172 self.context.start = Some(old);
173 }
174
175 for i in new..new + new_len {
176 self.context.data.push_back(format!("+{}", self.text2[i]));
177 }
178 self.context.changed = true;
179 self.context.inserted += new_len;
180
181 Ok(())
182 }
183
184 fn replace(
185 &mut self,
186 old: usize,
187 old_len: usize,
188 new: usize,
189 new_len: usize,
190 ) -> Result<(), Self::Error> {
191 if self.context.start.is_none() {
192 self.context.start = Some(old);
193 }
194
195 for i in old..old + old_len {
196 self.context.data.push_back(format!("-{}", self.text1[i]));
197 }
198 for i in new..new + new_len {
199 self.context.data.push_back(format!("+{}", self.text2[i]));
200 }
201 self.context.changed = true;
202 self.context.removed += old_len;
203 self.context.inserted += new_len;
204
205 Ok(())
206 }
207
208 fn finish(&mut self) -> Result<(), Self::Error> {
209 if self.context.counter > self.context_radius {
210 let truncation = self.context.counter - self.context_radius;
211 if self.context.data.len() > truncation {
212 let new_size = self.context.data.len() - truncation;
213 self.context.equaled -= truncation;
214 self.context.data.truncate(new_size);
215 }
216 }
217 self.result
218 .append(&mut self.context.to_vec(self.removed, self.inserted));
219 Ok(())
220 }
221}