1use crate::textutil::{normalize_quotes, split_sentences, tokenize_words};
6
7#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
9pub enum Granularity {
10 Char,
12 #[default]
14 Word,
15 Sentence,
17}
18
19impl Granularity {
20 pub fn parse(s: &str) -> Result<Self, String> {
22 match s.to_ascii_lowercase().as_str() {
23 "char" | "character" => Ok(Self::Char),
24 "word" => Ok(Self::Word),
25 "sentence" => Ok(Self::Sentence),
26 other => Err(format!(
27 "unknown granularity '{other}' (expected char, word, or sentence)"
28 )),
29 }
30 }
31}
32
33impl std::str::FromStr for Granularity {
34 type Err = String;
35 fn from_str(s: &str) -> Result<Self, Self::Err> {
36 Self::parse(s)
37 }
38}
39
40#[derive(Debug, Clone, PartialEq, Eq)]
43pub enum DiffHunk {
44 Equal(String),
46 Delete(String),
48 Insert(String),
50}
51
52pub fn mark(old: &str, new: &str, granularity: Granularity) -> String {
58 if old == new {
59 return old.to_string();
60 }
61 let mut out = String::new();
62 for hunk in diff(old, new, granularity) {
63 match hunk {
64 DiffHunk::Equal(s) => out.push_str(&s),
65 DiffHunk::Delete(s) => {
66 out.push_str("[-");
67 out.push_str(&s);
68 out.push_str("-]");
69 }
70 DiffHunk::Insert(s) => {
71 out.push_str("{+");
72 out.push_str(&s);
73 out.push_str("+}");
74 }
75 }
76 }
77 out
78}
79
80pub fn mark_minimal(old: &str, new: &str, granularity: Granularity) -> String {
86 if old == new {
87 return old.to_string();
88 }
89 let mut out = String::new();
90 for hunk in diff_minimal(old, new, granularity) {
91 match hunk {
92 DiffHunk::Equal(s) => out.push_str(&s),
93 DiffHunk::Delete(s) => {
94 out.push_str("[-");
95 out.push_str(&s);
96 out.push_str("-]");
97 }
98 DiffHunk::Insert(s) => {
99 out.push_str("{+");
100 out.push_str(&s);
101 out.push_str("+}");
102 }
103 }
104 }
105 out
106}
107
108pub fn diff_minimal(old: &str, new: &str, granularity: Granularity) -> Vec<DiffHunk> {
119 minimize_hunks(&diff(old, new, granularity))
120}
121
122pub fn minimize_hunks(hunks: &[DiffHunk]) -> Vec<DiffHunk> {
124 let mut out = Vec::new();
125 let mut i = 0;
126 while i < hunks.len() {
127 match (&hunks[i], hunks.get(i + 1)) {
128 (DiffHunk::Delete(deleted), Some(DiffHunk::Insert(inserted))) => {
129 out.extend(refine_pair(deleted, inserted));
130 i += 2;
131 }
132 (DiffHunk::Insert(inserted), Some(DiffHunk::Delete(deleted))) => {
133 out.extend(refine_pair(deleted, inserted));
134 i += 2;
135 }
136 (hunk, _) => {
137 out.push(hunk.clone());
138 i += 1;
139 }
140 }
141 }
142 coalesce(out)
143}
144
145fn refine_pair(deleted: &str, inserted: &str) -> Vec<DiffHunk> {
146 if deleted.is_empty() && inserted.is_empty() {
147 return Vec::new();
148 }
149 if normalize_quotes(deleted) == normalize_quotes(inserted) {
150 return if deleted.is_empty() {
151 Vec::new()
152 } else {
153 vec![DiffHunk::Equal(deleted.to_string())]
154 };
155 }
156 if deleted.is_empty() {
157 return vec![DiffHunk::Insert(inserted.to_string())];
158 }
159 if inserted.is_empty() {
160 return vec![DiffHunk::Delete(deleted.to_string())];
161 }
162 diff(deleted, inserted, Granularity::Char)
163}
164
165pub fn diff(old: &str, new: &str, granularity: Granularity) -> Vec<DiffHunk> {
169 if old == new {
170 return if old.is_empty() {
171 Vec::new()
172 } else {
173 vec![DiffHunk::Equal(old.to_string())]
174 };
175 }
176 let hunks = match granularity {
177 Granularity::Char => {
178 let old_t: Vec<String> = old.chars().map(|c| c.to_string()).collect();
179 let new_t: Vec<String> = new.chars().map(|c| c.to_string()).collect();
180 lcs_hunks(&old_t, &new_t)
181 }
182 Granularity::Word => {
183 let old_t: Vec<String> = tokenize_words(old)
184 .into_iter()
185 .map(str::to_string)
186 .collect();
187 let new_t: Vec<String> = tokenize_words(new)
188 .into_iter()
189 .map(str::to_string)
190 .collect();
191 let raw = lcs_hunks(&old_t, &new_t);
192 coalesce_near(raw, 2)
193 }
194 Granularity::Sentence => {
195 let old_t: Vec<String> = split_sentences(old)
196 .into_iter()
197 .map(str::to_string)
198 .collect();
199 let new_t: Vec<String> = split_sentences(new)
200 .into_iter()
201 .map(str::to_string)
202 .collect();
203 lcs_hunks(&old_t, &new_t)
204 }
205 };
206 coalesce(hunks)
207}
208
209fn lcs_hunks(old: &[String], new: &[String]) -> Vec<DiffHunk> {
210 let n = old.len();
211 let m = new.len();
212 let mut dp = vec![vec![0u32; m + 1]; n + 1];
214 for i in 0..n {
215 for j in 0..m {
216 dp[i + 1][j + 1] = if old[i] == new[j] {
217 dp[i][j] + 1
218 } else {
219 dp[i][j + 1].max(dp[i + 1][j])
220 };
221 }
222 }
223 let mut hunks = Vec::new();
224 let mut i = n;
225 let mut j = m;
226 while i > 0 || j > 0 {
227 if i > 0 && j > 0 && old[i - 1] == new[j - 1] {
228 hunks.push(DiffHunk::Equal(old[i - 1].clone()));
229 i -= 1;
230 j -= 1;
231 } else if j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j]) {
232 hunks.push(DiffHunk::Insert(new[j - 1].clone()));
233 j -= 1;
234 } else {
235 hunks.push(DiffHunk::Delete(old[i - 1].clone()));
236 i -= 1;
237 }
238 }
239 hunks.reverse();
240 hunks
241}
242
243fn coalesce(hunks: Vec<DiffHunk>) -> Vec<DiffHunk> {
244 let mut out: Vec<DiffHunk> = Vec::new();
245 for h in hunks {
246 match (out.last_mut(), &h) {
247 (Some(DiffHunk::Equal(a)), DiffHunk::Equal(b)) => a.push_str(b),
248 (Some(DiffHunk::Delete(a)), DiffHunk::Delete(b)) => a.push_str(b),
249 (Some(DiffHunk::Insert(a)), DiffHunk::Insert(b)) => a.push_str(b),
250 _ => out.push(h),
251 }
252 }
253 out
254}
255
256fn coalesce_near(hunks: Vec<DiffHunk>, max_equal: usize) -> Vec<DiffHunk> {
257 let mut out = Vec::new();
261 let mut i = 0;
262 while i < hunks.len() {
263 if let DiffHunk::Equal(eq) = &hunks[i] {
264 let tokens = tokenize_words(eq).len();
265 let prev_change = i > 0 && !matches!(hunks[i - 1], DiffHunk::Equal(_));
266 let next_change = i + 1 < hunks.len() && !matches!(hunks[i + 1], DiffHunk::Equal(_));
267 if prev_change && next_change && tokens > 0 && tokens <= max_equal {
268 out.push(DiffHunk::Delete(eq.clone()));
269 out.push(DiffHunk::Insert(eq.clone()));
270 i += 1;
271 continue;
272 }
273 }
274 out.push(hunks[i].clone());
275 i += 1;
276 }
277 coalesce(out)
278}
279
280#[cfg(test)]
281mod tests {
282 use super::*;
283
284 #[test]
285 fn identical() {
286 let d = diff("hello", "hello", Granularity::Word);
287 assert_eq!(d, vec![DiffHunk::Equal("hello".into())]);
288 }
289
290 #[test]
291 fn word_replace() {
292 let d = diff("the cat sat", "the dog sat", Granularity::Word);
293 assert!(d
294 .iter()
295 .any(|h| matches!(h, DiffHunk::Delete(s) if s.contains("cat"))));
296 assert!(d
297 .iter()
298 .any(|h| matches!(h, DiffHunk::Insert(s) if s.contains("dog"))));
299 let old: String = d
300 .iter()
301 .filter_map(|h| match h {
302 DiffHunk::Equal(s) | DiffHunk::Delete(s) => Some(s.as_str()),
303 _ => None,
304 })
305 .collect();
306 let new: String = d
307 .iter()
308 .filter_map(|h| match h {
309 DiffHunk::Equal(s) | DiffHunk::Insert(s) => Some(s.as_str()),
310 _ => None,
311 })
312 .collect();
313 assert_eq!(old, "the cat sat");
314 assert_eq!(new, "the dog sat");
315 }
316
317 #[test]
318 fn char_split() {
319 let d = diff("ab", "ac", Granularity::Char);
320 assert_eq!(
321 d,
322 vec![
323 DiffHunk::Equal("a".into()),
324 DiffHunk::Delete("b".into()),
325 DiffHunk::Insert("c".into()),
326 ]
327 );
328 }
329
330 #[test]
331 fn append_is_pure_insert() {
332 let d = diff("hello", "hello world", Granularity::Word);
333 assert!(matches!(d.last(), Some(DiffHunk::Insert(s)) if s.contains("world")));
334 assert!(!d.iter().any(|h| matches!(h, DiffHunk::Delete(_))));
335 }
336 #[test]
337 fn mark_shows_both_sides() {
338 assert_eq!(
339 mark("the cat", "the dog", Granularity::Word),
340 "the[- cat-]{+ dog+}"
341 );
342 assert_eq!(mark("same", "same", Granularity::Word), "same");
343 assert_eq!(mark("", "hi", Granularity::Word), "{+hi+}");
344 assert_eq!(mark("bye", "", Granularity::Word), "[-bye-]");
345 }
346
347 #[test]
348 fn minimize_cancels_identical_delete_insert() {
349 let hunks = vec![
350 DiffHunk::Equal("the".into()),
351 DiffHunk::Delete(" x".into()),
352 DiffHunk::Insert(" x".into()),
353 DiffHunk::Equal(" cat".into()),
354 ];
355 assert_eq!(
356 minimize_hunks(&hunks),
357 vec![DiffHunk::Equal("the x cat".into())]
358 );
359 }
360
361 #[test]
362 fn minimize_cancels_smart_quote_no_op() {
363 let hunks = vec![
364 DiffHunk::Delete("don\u{2019}t".into()),
365 DiffHunk::Insert("don't".into()),
366 ];
367 let refined = minimize_hunks(&hunks);
368 assert_eq!(refined.len(), 1);
369 assert!(matches!(&refined[0], DiffHunk::Equal(_)));
370 assert!(!refined.iter().any(|h| matches!(h, DiffHunk::Delete(_))));
371 }
372
373 #[test]
374 fn minimize_keeps_shared_prefix_of_a_replacement() {
375 let d = diff_minimal("the cat sat", "the dog sat", Granularity::Word);
376 let deleted: String = d
377 .iter()
378 .filter_map(|h| match h {
379 DiffHunk::Delete(s) => Some(s.as_str()),
380 _ => None,
381 })
382 .collect();
383 let inserted: String = d
384 .iter()
385 .filter_map(|h| match h {
386 DiffHunk::Insert(s) => Some(s.as_str()),
387 _ => None,
388 })
389 .collect();
390 assert_eq!(deleted, "cat");
391 assert_eq!(inserted, "dog");
392 assert_eq!(
393 mark_minimal("the cat sat", "the dog sat", Granularity::Word),
394 "the [-cat-]{+dog+} sat"
395 );
396 }
397
398 #[test]
399 fn minimize_reconstructs_both_sides() {
400 let old = "a x b y c";
401 let new = "a z b y c";
402 let d = diff_minimal(old, new, Granularity::Word);
403 let rebuilt_old: String = d
404 .iter()
405 .filter_map(|h| match h {
406 DiffHunk::Equal(s) | DiffHunk::Delete(s) => Some(s.as_str()),
407 _ => None,
408 })
409 .collect();
410 let rebuilt_new: String = d
411 .iter()
412 .filter_map(|h| match h {
413 DiffHunk::Equal(s) | DiffHunk::Insert(s) => Some(s.as_str()),
414 _ => None,
415 })
416 .collect();
417 assert_eq!(rebuilt_old, old);
418 assert_eq!(rebuilt_new, new);
419 }
420}