ochrepad_core/
diff.rs

1//! Line and word diff for the compare view (PLAN M12), using `similar`.
2//!
3//! The result is a list of aligned rows: each row shows a line of the left
4//! document, a line of the right one, or both. A missing side is a filler
5//! row, so equal text stays side by side. [`SideMap`] exposes one side's
6//! rows as a [`DisplayMap`].
7
8use std::ops::Range;
9use std::time::Duration;
10
11use similar::{Algorithm, ChangeTag, DiffOp, TextDiff};
12
13use crate::text::Document;
14use crate::view::DisplayMap;
15
16/// Give up refining a diff after this long and report a coarser one.
17pub const DIFF_TIMEOUT: Duration = Duration::from_secs(2);
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub enum RowKind {
21    Equal,
22    /// Only on the right.
23    Added,
24    /// Only on the left.
25    Removed,
26    /// On both sides, with different text.
27    Changed,
28}
29
30#[derive(Clone, Debug, PartialEq, Eq)]
31pub struct DiffRow {
32    pub kind: RowKind,
33    pub left: Option<usize>,
34    pub right: Option<usize>,
35}
36
37#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
38pub struct DiffStats {
39    pub added: usize,
40    pub removed: usize,
41    pub changed: usize,
42}
43
44#[derive(Clone, Debug, Default, PartialEq, Eq)]
45pub struct LineDiff {
46    pub rows: Vec<DiffRow>,
47    /// Row ranges of consecutive non-equal rows, for next/previous change.
48    pub hunks: Vec<Range<usize>>,
49    pub stats: DiffStats,
50}
51
52fn lines(doc: &Document) -> Vec<String> {
53    (0..doc.line_count()).map(|l| doc.line_text(l)).collect()
54}
55
56/// Aligns the lines of `left` and `right`. Replaced blocks are paired line
57/// by line as `Changed`; the extra lines of the longer side are `Removed` or
58/// `Added`.
59pub fn diff_lines(left: &Document, right: &Document) -> LineDiff {
60    let a = lines(left);
61    let b = lines(right);
62    let a_refs: Vec<&str> = a.iter().map(String::as_str).collect();
63    let b_refs: Vec<&str> = b.iter().map(String::as_str).collect();
64    let diff = TextDiff::configure()
65        .algorithm(Algorithm::Myers)
66        .timeout(DIFF_TIMEOUT)
67        .diff_slices(&a_refs, &b_refs);
68    let mut out = LineDiff::default();
69    let push = |out: &mut LineDiff, kind, left, right| {
70        if kind != RowKind::Equal {
71            let row = out.rows.len();
72            match out.hunks.last_mut() {
73                Some(h) if h.end == row => h.end += 1,
74                _ => out.hunks.push(row..row + 1),
75            }
76            match kind {
77                RowKind::Added => out.stats.added += 1,
78                RowKind::Removed => out.stats.removed += 1,
79                RowKind::Changed => out.stats.changed += 1,
80                RowKind::Equal => {}
81            }
82        }
83        out.rows.push(DiffRow { kind, left, right });
84    };
85    for op in diff.ops() {
86        match *op {
87            DiffOp::Equal {
88                old_index,
89                new_index,
90                len,
91            } => {
92                for i in 0..len {
93                    push(
94                        &mut out,
95                        RowKind::Equal,
96                        Some(old_index + i),
97                        Some(new_index + i),
98                    );
99                }
100            }
101            DiffOp::Delete {
102                old_index, old_len, ..
103            } => {
104                for i in 0..old_len {
105                    push(&mut out, RowKind::Removed, Some(old_index + i), None);
106                }
107            }
108            DiffOp::Insert {
109                new_index, new_len, ..
110            } => {
111                for i in 0..new_len {
112                    push(&mut out, RowKind::Added, None, Some(new_index + i));
113                }
114            }
115            DiffOp::Replace {
116                old_index,
117                old_len,
118                new_index,
119                new_len,
120            } => {
121                for i in 0..old_len.max(new_len) {
122                    let l = (i < old_len).then_some(old_index + i);
123                    let r = (i < new_len).then_some(new_index + i);
124                    let kind = match (l, r) {
125                        (Some(_), Some(_)) => RowKind::Changed,
126                        (Some(_), None) => RowKind::Removed,
127                        _ => RowKind::Added,
128                    };
129                    push(&mut out, kind, l, r);
130                }
131            }
132        }
133    }
134    out
135}
136
137/// Byte ranges of the words that differ between two changed lines, on each
138/// side. Adjacent ranges are merged.
139pub fn diff_words(left: &str, right: &str) -> (Vec<Range<usize>>, Vec<Range<usize>>) {
140    let diff = TextDiff::configure()
141        .timeout(DIFF_TIMEOUT)
142        .diff_words(left, right);
143    let (mut a, mut b) = (Vec::new(), Vec::new());
144    let (mut ia, mut ib) = (0, 0);
145    let add = |ranges: &mut Vec<Range<usize>>, start: usize, len: usize| match ranges.last_mut() {
146        Some(last) if last.end == start => last.end += len,
147        _ => ranges.push(start..start + len),
148    };
149    for change in diff.iter_all_changes() {
150        let len = change.value().len();
151        match change.tag() {
152            ChangeTag::Equal => {
153                ia += len;
154                ib += len;
155            }
156            ChangeTag::Delete => {
157                add(&mut a, ia, len);
158                ia += len;
159            }
160            ChangeTag::Insert => {
161                add(&mut b, ib, len);
162                ib += len;
163            }
164        }
165    }
166    (a, b)
167}
168
169#[derive(Clone, Copy, Debug, PartialEq, Eq)]
170pub enum Side {
171    Left,
172    Right,
173}
174
175/// One side of a diff as a display map: row → line, with filler rows.
176pub struct SideMap<'a> {
177    pub diff: &'a LineDiff,
178    pub side: Side,
179}
180
181impl DisplayMap for SideMap<'_> {
182    fn row_count(&self, _line_count: usize) -> usize {
183        self.diff.rows.len()
184    }
185
186    fn line_to_row(&self, line: usize) -> usize {
187        let of = |r: &DiffRow| match self.side {
188            Side::Left => r.left,
189            Side::Right => r.right,
190        };
191        self.diff
192            .rows
193            .iter()
194            .position(|r| of(r) == Some(line))
195            .unwrap_or(self.diff.rows.len())
196    }
197
198    fn row_to_line(&self, row: usize) -> Option<usize> {
199        let r = self.diff.rows.get(row)?;
200        match self.side {
201            Side::Left => r.left,
202            Side::Right => r.right,
203        }
204    }
205}
206
207#[cfg(test)]
208mod tests {
209    use super::*;
210
211    fn kinds(d: &LineDiff) -> Vec<(RowKind, Option<usize>, Option<usize>)> {
212        d.rows.iter().map(|r| (r.kind, r.left, r.right)).collect()
213    }
214
215    #[test]
216    fn rows_align_with_fillers() {
217        let left = Document::new("a\nb\nc\nd");
218        let right = Document::new("a\nB\nc\nnew\nd");
219        let d = diff_lines(&left, &right);
220        use RowKind::*;
221        assert_eq!(
222            kinds(&d),
223            vec![
224                (Equal, Some(0), Some(0)),
225                (Changed, Some(1), Some(1)),
226                (Equal, Some(2), Some(2)),
227                (Added, None, Some(3)),
228                (Equal, Some(3), Some(4)),
229            ]
230        );
231        assert_eq!(d.hunks, vec![1..2, 3..4]);
232        assert_eq!(
233            d.stats,
234            DiffStats {
235                added: 1,
236                removed: 0,
237                changed: 1
238            }
239        );
240    }
241
242    #[test]
243    fn uneven_replacements_pair_then_spill() {
244        let left = Document::new("x\none\ntwo\nthree\ny");
245        let right = Document::new("x\nuno\ny");
246        let d = diff_lines(&left, &right);
247        use RowKind::*;
248        assert_eq!(
249            kinds(&d),
250            vec![
251                (Equal, Some(0), Some(0)),
252                (Changed, Some(1), Some(1)),
253                (Removed, Some(2), None),
254                (Removed, Some(3), None),
255                (Equal, Some(4), Some(2)),
256            ]
257        );
258        assert_eq!(d.hunks, vec![1..4]);
259    }
260
261    #[test]
262    fn identical_documents_have_no_hunks() {
263        let doc = Document::new("same\ntext\n");
264        let d = diff_lines(&doc, &doc.clone());
265        assert!(d.hunks.is_empty());
266        assert_eq!(d.rows.len(), 3);
267    }
268
269    #[test]
270    fn word_ranges() {
271        let (a, b) = diff_words("let total = price * qty;", "let total = cost * qty + tax;");
272        let left = "let total = price * qty;";
273        let right = "let total = cost * qty + tax;";
274        let words = |s: &str, r: &[Range<usize>]| -> Vec<String> {
275            r.iter().map(|r| s[r.clone()].to_owned()).collect()
276        };
277        assert_eq!(words(left, &a), vec!["price", "qty;"]);
278        assert_eq!(words(right, &b), vec!["cost", "qty + tax;"]);
279    }
280
281    #[test]
282    fn side_maps_are_display_maps() {
283        let d = diff_lines(&Document::new("a\nb"), &Document::new("a\nnew\nb"));
284        let left = SideMap {
285            diff: &d,
286            side: Side::Left,
287        };
288        let right = SideMap {
289            diff: &d,
290            side: Side::Right,
291        };
292        assert_eq!(left.row_count(2), 3);
293        assert_eq!(
294            (0..3).map(|r| left.row_to_line(r)).collect::<Vec<_>>(),
295            vec![Some(0), None, Some(1)]
296        );
297        assert_eq!(left.line_to_row(1), 2);
298        assert_eq!(right.line_to_row(1), 1);
299    }
300}
ochrepad_core/diff.rs

ochrepad_core/
diff.rs
