Skip to main content

blackline_core/
diff.rs

1//! Token-level LCS diff. Used by tracked replacements and two-document redlines.
2//!
3//! Implemented here so the toolkit does not depend on an external diff crate.
4
5use crate::textutil::{normalize_quotes, split_sentences, tokenize_words};
6
7/// How tightly a tracked replacement / redline is chunked.
8#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
9pub enum Granularity {
10    /// Character-level (tightest; can split words).
11    Char,
12    /// Word-level. Default.
13    #[default]
14    Word,
15    /// Whole changed sentences become one deletion + insertion.
16    Sentence,
17}
18
19impl Granularity {
20    /// Parse `char` / `word` / `sentence`.
21    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/// One hunk of a diff. Concatenating Equal + Delete from `old` and
41/// Equal + Insert from `new` reconstructs the respective strings.
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub enum DiffHunk {
44    /// Unchanged text.
45    Equal(String),
46    /// Deleted text (present only in the original).
47    Delete(String),
48    /// Inserted text (present only in the revision).
49    Insert(String),
50}
51
52/// Render a two-sided inline redline (`[-deleted-]` / `{+inserted+}`).
53///
54/// Word uses `w:ins` / `w:del`. Spreadsheet cells and slide frames have
55/// no equivalent, so format redlines compile the same LCS hunks to this
56/// mark-up instead.
57pub 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
80/// Render a two-sided inline redline using [`diff_minimal`].
81///
82/// Prefer this for track / surgical redline: identical delete+insert
83/// pairs cancel, and adjacent replacements keep shared prefix/suffix
84/// as [`DiffHunk::Equal`].
85pub 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
108/// Diff `old` against `new` at `granularity`, then minimize.
109///
110/// Word-level [`diff`] folds short equal spans into the surrounding
111/// delete+insert (so markup stays on word boundaries). That can mark
112/// text as deleted and immediately re-inserted. This pass:
113///
114/// 1. Cancels a delete+insert whose normalized text is identical
115///    (the add is the same as the delete — a no-op).
116/// 2. Otherwise re-diffs that pair at character granularity so shared
117///    prefix/suffix is not marked.
118pub fn diff_minimal(old: &str, new: &str, granularity: Granularity) -> Vec<DiffHunk> {
119    minimize_hunks(&diff(old, new, granularity))
120}
121
122/// Refine LCS hunks so we do not delete text we immediately add back.
123pub 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
165/// Diff `old` against `new` at `granularity`. Adjacent hunks of the same
166/// kind are coalesced. At word granularity, changed regions separated by
167/// at most two equal tokens are coalesced to avoid noisy mid-word markup.
168pub 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    // DP table of LCS lengths. n,m are paragraph-scale.
213    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    // If an Equal of at most `max_equal` tokens sits between two change
258    // regions, fold it into the surrounding changes (delete+insert the equal
259    // text on both sides). Token count is approximated by whitespace splits.
260    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}