diffler_core/
diffalgo.rs

1//! Selectable line-diff algorithms. libgit2 has no histogram, so we run
2//! `Histogram` and `Structural` through imara-diff.
3
4use std::collections::HashMap;
5
6use imara_diff::{Algorithm, Diff, InternedInput};
7use serde::{Deserialize, Deserializer, Serialize, Serializer};
8
9use crate::model::{DiffLine, Hunk, HunkId, LineKind, disambiguated_hunk_id};
10
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
12pub enum DiffAlgorithm {
13    #[default]
14    Myers,
15    Minimal,
16    Patience,
17    Histogram,
18    /// Histogram, plus dimming paired lines that differ in layout alone.
19    Structural,
20}
21
22impl DiffAlgorithm {
23    pub const ALL: [Self; 5] = [
24        Self::Myers,
25        Self::Minimal,
26        Self::Patience,
27        Self::Histogram,
28        Self::Structural,
29    ];
30
31    pub const fn as_str(self) -> &'static str {
32        match self {
33            Self::Myers => "myers",
34            Self::Minimal => "minimal",
35            Self::Patience => "patience",
36            Self::Histogram => "histogram",
37            Self::Structural => "structural",
38        }
39    }
40
41    pub fn parse(value: &str) -> Option<Self> {
42        Self::ALL.into_iter().find(|a| a.as_str() == value)
43    }
44
45    pub const fn is_imara(self) -> bool {
46        matches!(self, Self::Histogram | Self::Structural)
47    }
48}
49
50impl std::fmt::Display for DiffAlgorithm {
51    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
52        f.write_str(self.as_str())
53    }
54}
55
56impl Serialize for DiffAlgorithm {
57    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
58        serializer.serialize_str(self.as_str())
59    }
60}
61
62impl<'de> Deserialize<'de> for DiffAlgorithm {
63    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
64        let name = String::deserialize(deserializer)?;
65        Self::parse(&name).ok_or_else(|| {
66            let names = Self::ALL.map(Self::as_str).join(", ");
67            serde::de::Error::custom(format!(
68                "unknown diff algorithm `{name}`, expected one of {names}"
69            ))
70        })
71    }
72}
73
74/// One value for every backend we open, so the review's backend and the
75/// workers' never drift apart.
76#[derive(Debug, Clone, Copy, PartialEq, Eq)]
77pub struct DiffSettings {
78    pub context_lines: u32,
79    pub algorithm: DiffAlgorithm,
80    pub indent_heuristic: bool,
81}
82
83impl Default for DiffSettings {
84    fn default() -> Self {
85        Self {
86            context_lines: crate::git::DEFAULT_CONTEXT_LINES,
87            algorithm: DiffAlgorithm::default(),
88            indent_heuristic: crate::git::DEFAULT_INDENT_HEURISTIC,
89        }
90    }
91}
92
93impl DiffSettings {
94    pub fn with_context(context_lines: u32) -> Self {
95        Self {
96            context_lines,
97            ..Self::default()
98        }
99    }
100}
101
102/// Histogram hunks of `old` vs `new`, merged the way git merges nearby hunks.
103/// We seed ids like [`crate::git`] so staging finds the hunk it shows.
104pub fn histogram_hunks(
105    old: &str,
106    new: &str,
107    file_path: &str,
108    context: u32,
109    indent_heuristic: bool,
110) -> Vec<Hunk> {
111    let input = InternedInput::new(old, new);
112    let mut diff = Diff::compute(Algorithm::Histogram, &input);
113    if indent_heuristic {
114        diff.postprocess_lines(&input);
115    } else {
116        diff.postprocess_no_heuristic(&input);
117    }
118
119    let before_len = input.before.len() as u32;
120    let raw: Vec<imara_diff::Hunk> = diff.hunks().collect();
121    if raw.is_empty() {
122        return Vec::new();
123    }
124
125    let two_context = context.saturating_mul(2);
126    let mut groups: Vec<Vec<imara_diff::Hunk>> = Vec::new();
127    let mut pos = 0u32;
128    for hunk in raw {
129        let starts_new = groups.is_empty() || hunk.before.start.saturating_sub(pos) > two_context;
130        if starts_new {
131            groups.push(Vec::new());
132        }
133        pos = hunk.before.end;
134        if let Some(group) = groups.last_mut() {
135            group.push(hunk);
136        }
137    }
138
139    let mut seen: HashMap<HunkId, usize> = HashMap::new();
140    let mut heading = FuncHeading::default();
141    groups
142        .into_iter()
143        .map(|group| {
144            build_hunk(
145                &group,
146                &input,
147                file_path,
148                context,
149                before_len,
150                &mut seen,
151                &mut heading,
152            )
153        })
154        .collect()
155}
156
157fn line_text(input: &InternedInput<&str>, token: imara_diff::Token) -> String {
158    input.interner[token]
159        .trim_end_matches(['\n', '\r'])
160        .to_owned()
161}
162
163/// libgit2's default funcname rule: the nearest old-side line above the hunk
164/// that opens with an ASCII letter, `_` or `$`, cut to 80 bytes. Hunks arrive
165/// in file order, so we scan only the rows since the previous hunk.
166#[derive(Default)]
167struct FuncHeading {
168    scanned: u32,
169    text: String,
170}
171
172impl FuncHeading {
173    const MAX_BYTES: usize = 80;
174
175    fn above(&mut self, input: &InternedInput<&str>, row: u32) -> String {
176        let found = (self.scanned..row)
177            .rev()
178            .filter_map(|idx| input.before.get(idx as usize))
179            .map(|&token| input.interner[token].trim_end())
180            .find(|line| {
181                line.starts_with(|c: char| c.is_ascii_alphabetic() || c == '_' || c == '$')
182            });
183        if let Some(line) = found {
184            let mut end = line.len().min(Self::MAX_BYTES);
185            while !line.is_char_boundary(end) {
186                end -= 1;
187            }
188            line[..end].trim_end().clone_into(&mut self.text);
189        }
190        self.scanned = self.scanned.max(row);
191        self.text.clone()
192    }
193}
194
195fn push_context_lines(
196    lines: &mut Vec<DiffLine>,
197    input: &InternedInput<&str>,
198    old_from: u32,
199    old_to: u32,
200    new_from: u32,
201) {
202    for offset in 0..old_to.saturating_sub(old_from) {
203        let old_idx = old_from + offset;
204        let new_idx = new_from + offset;
205        let Some(&token) = input.before.get(old_idx as usize) else {
206            continue;
207        };
208        lines.push(DiffLine::new(
209            LineKind::Context,
210            Some(old_idx + 1),
211            Some(new_idx + 1),
212            line_text(input, token),
213        ));
214    }
215}
216
217fn build_hunk(
218    group: &[imara_diff::Hunk],
219    input: &InternedInput<&str>,
220    file_path: &str,
221    context: u32,
222    before_len: u32,
223    seen: &mut HashMap<HunkId, usize>,
224    heading: &mut FuncHeading,
225) -> Hunk {
226    let first = group.first().unwrap_or(&imara_diff::Hunk::NONE);
227    let last = group.last().unwrap_or(&imara_diff::Hunk::NONE);
228
229    let lead_start = first.before.start.saturating_sub(context);
230    let lead_len = first.before.start - lead_start;
231    let after_lead_start = first.after.start.saturating_sub(lead_len);
232    let tail_end = last.before.end.saturating_add(context).min(before_len);
233
234    let mut lines = Vec::new();
235    push_context_lines(
236        &mut lines,
237        input,
238        lead_start,
239        first.before.start,
240        after_lead_start,
241    );
242
243    for (index, hunk) in group.iter().enumerate() {
244        for old_idx in hunk.before.start..hunk.before.end {
245            let Some(&token) = input.before.get(old_idx as usize) else {
246                continue;
247            };
248            lines.push(DiffLine::new(
249                LineKind::Deleted,
250                Some(old_idx + 1),
251                None,
252                line_text(input, token),
253            ));
254        }
255        for new_idx in hunk.after.start..hunk.after.end {
256            let Some(&token) = input.after.get(new_idx as usize) else {
257                continue;
258            };
259            lines.push(DiffLine::new(
260                LineKind::Added,
261                None,
262                Some(new_idx + 1),
263                line_text(input, token),
264            ));
265        }
266        if let Some(next) = group.get(index + 1) {
267            push_context_lines(
268                &mut lines,
269                input,
270                hunk.before.end,
271                next.before.start,
272                hunk.after.end,
273            );
274        }
275    }
276    push_context_lines(&mut lines, input, last.before.end, tail_end, last.after.end);
277
278    let old_lines = lines.iter().filter(|l| l.kind != LineKind::Added).count() as u32;
279    let new_lines = lines.iter().filter(|l| l.kind != LineKind::Deleted).count() as u32;
280    // git's header gives an empty side the line before the change
281    let start = |index: u32, len: u32| if len == 0 { index } else { index + 1 };
282    let id = disambiguated_hunk_id(file_path, &lines, seen);
283    Hunk {
284        id,
285        old_start: start(lead_start, old_lines),
286        old_lines,
287        new_start: start(after_lead_start, new_lines),
288        new_lines,
289        context: heading.above(input, lead_start),
290        lines,
291    }
292}
293
294#[cfg(test)]
295mod tests {
296    use super::*;
297
298    #[test]
299    fn algorithm_names_round_trip() {
300        for algo in DiffAlgorithm::ALL {
301            assert_eq!(DiffAlgorithm::parse(algo.as_str()), Some(algo));
302            let json = serde_json::to_string(&algo).expect("serialize");
303            assert_eq!(json, format!("\"{}\"", algo.as_str()));
304            assert_eq!(
305                serde_json::from_str::<DiffAlgorithm>(&json).expect("deserialize"),
306                algo
307            );
308        }
309        assert_eq!(DiffAlgorithm::parse("bogus"), None);
310        assert!(serde_json::from_str::<DiffAlgorithm>("\"bogus\"").is_err());
311    }
312
313    #[test]
314    fn default_algorithm_is_myers() {
315        assert_eq!(DiffAlgorithm::default(), DiffAlgorithm::Myers);
316    }
317
318    #[test]
319    fn single_line_change_yields_one_hunk_with_context() {
320        let old = "a\nb\nc\nd\ne\n";
321        let new = "a\nb\nX\nd\ne\n";
322        let hunks = histogram_hunks(old, new, "f.txt", 1, true);
323        assert_eq!(hunks.len(), 1);
324        let h = &hunks[0];
325        assert_eq!(h.old_start, 2);
326        assert_eq!(h.old_lines, 3);
327        assert_eq!(h.new_start, 2);
328        assert_eq!(h.new_lines, 3);
329        let kinds: Vec<_> = h.lines.iter().map(|l| (l.kind, l.text.as_str())).collect();
330        assert_eq!(
331            kinds,
332            vec![
333                (LineKind::Context, "b"),
334                (LineKind::Deleted, "c"),
335                (LineKind::Added, "X"),
336                (LineKind::Context, "d"),
337            ]
338        );
339    }
340
341    #[test]
342    fn nearby_changes_merge_into_one_hunk() {
343        let old = "a\nb\nc\nd\ne\n";
344        let new = "A\nb\nc\nD\ne\n";
345        let hunks = histogram_hunks(old, new, "f.txt", 3, true);
346        assert_eq!(hunks.len(), 1, "the two edits merge: {hunks:?}");
347        assert_eq!(hunks[0].old_start, 1);
348        assert_eq!(hunks[0].old_lines, 5);
349    }
350
351    #[test]
352    fn distant_changes_stay_separate_hunks() {
353        let mut old = vec!["a".to_owned()];
354        old.extend((0..20).map(|i| format!("ctx{i}")));
355        old.push("z".to_owned());
356        let mut new = old.clone();
357        new[0] = "A".to_owned();
358        let last = new.len() - 1;
359        new[last] = "Z".to_owned();
360        let old_text = format!("{}\n", old.join("\n"));
361        let new_text = format!("{}\n", new.join("\n"));
362        let hunks = histogram_hunks(&old_text, &new_text, "f.txt", 3, true);
363        assert_eq!(hunks.len(), 2, "far-apart edits stay separate: {hunks:?}");
364    }
365
366    #[test]
367    fn leading_and_trailing_context_clip_to_file_bounds() {
368        let old = "a\nb\n";
369        let new = "A\nb\n";
370        let hunks = histogram_hunks(old, new, "f.txt", 3, true);
371        assert_eq!(hunks.len(), 1);
372        assert_eq!(hunks[0].old_start, 1);
373        assert_eq!(hunks[0].old_lines, 2);
374    }
375
376    #[test]
377    fn no_context_only_shows_changed_lines() {
378        let old = "a\nb\nc\n";
379        let new = "a\nB\nc\n";
380        let hunks = histogram_hunks(old, new, "f.txt", 0, true);
381        assert_eq!(hunks.len(), 1);
382        let kinds: Vec<_> = hunks[0].lines.iter().map(|l| l.kind).collect();
383        assert_eq!(kinds, vec![LineKind::Deleted, LineKind::Added]);
384    }
385
386    #[test]
387    fn an_empty_side_starts_at_the_line_before_like_git() {
388        let insert = histogram_hunks("a\nb\n", "a\nX\nb\n", "f.txt", 0, true);
389        assert_eq!(
390            (
391                insert[0].old_start,
392                insert[0].old_lines,
393                insert[0].new_start
394            ),
395            (1, 0, 2)
396        );
397        let delete = histogram_hunks("a\nX\nb\n", "a\nb\n", "f.txt", 0, true);
398        assert_eq!(
399            (
400                delete[0].old_start,
401                delete[0].new_start,
402                delete[0].new_lines
403            ),
404            (2, 1, 0)
405        );
406    }
407
408    #[test]
409    fn hunk_ids_are_stable_for_identical_input() {
410        let old = "a\nb\nc\n";
411        let new = "a\nB\nc\n";
412        let first = histogram_hunks(old, new, "f.txt", 1, true);
413        let second = histogram_hunks(old, new, "f.txt", 1, true);
414        assert_eq!(first[0].id, second[0].id);
415    }
416
417    // the hunk_context expectations below match `git diff` on the same input
418
419    #[test]
420    fn hunk_context_finds_the_enclosing_function() {
421        let old = "def parse_config():\n    a = 1\n    b = 2\n    c = 3\n";
422        let new = "def parse_config():\n    a = 1\n    b = 20\n    c = 3\n";
423        let hunks = histogram_hunks(old, new, "f.py", 0, true);
424        assert_eq!(hunks[0].context, "def parse_config():");
425    }
426
427    #[test]
428    fn hunk_context_skips_a_same_indent_sibling() {
429        let old = "def parse_config():\n    a = 1\n    b = 2\n";
430        let new = "def parse_config():\n    a = 1\n    b = 20\n";
431        let hunks = histogram_hunks(old, new, "f.py", 0, true);
432        assert_eq!(hunks[0].context, "def parse_config():");
433    }
434
435    #[test]
436    fn hunk_context_climbs_to_the_outermost_scope() {
437        let old = "class Foo:\n    def bar():\n        a = 1\n        b = 2\n";
438        let new = "class Foo:\n    def bar():\n        a = 1\n        b = 20\n";
439        let hunks = histogram_hunks(old, new, "f.py", 0, true);
440        assert_eq!(hunks[0].context, "class Foo:");
441    }
442
443    #[test]
444    fn hunk_context_prefers_the_nearest_top_level_definition() {
445        let old =
446            "def first():\n    pass\n\ndef second():\n    if true:\n        x = 1\n        y = 2\n";
447        let new = "def first():\n    pass\n\ndef second():\n    if true:\n        x = 1\n        y = 20\n";
448        let hunks = histogram_hunks(old, new, "f.py", 0, true);
449        assert_eq!(hunks[0].context, "def second():");
450    }
451
452    #[test]
453    fn hunk_context_for_an_insertion_reads_the_enclosing_function() {
454        let old = "def outer():\n    a = 1\n    b = 2\n";
455        let new = "def outer():\n    a = 1\n    newline = 99\n    b = 2\n";
456        let hunks = histogram_hunks(old, new, "f.py", 0, true);
457        assert_eq!(hunks[0].context, "def outer():");
458    }
459
460    #[test]
461    fn hunk_context_for_a_top_level_change_names_the_definition_above() {
462        let old = "fn top() {\n    1;\n}\n\nfn next() {\n    2;\n}\n";
463        let new = "fn top() {\n    1;\n}\n\nfn renamed() {\n    2;\n}\n";
464        let hunks = histogram_hunks(old, new, "f.rs", 0, true);
465        assert_eq!(hunks[0].context, "fn top() {");
466    }
467
468    #[test]
469    fn hunk_context_reads_above_the_leading_context_lines() {
470        let old = "fn a() {\n    1;\n    2;\n}\n";
471        let new = "fn a() {\n    10;\n    2;\n}\n";
472        let hunks = histogram_hunks(old, new, "f.rs", 3, true);
473        assert_eq!(hunks[0].context, "", "the definition is a context line");
474    }
475
476    #[test]
477    fn a_later_hunk_keeps_the_heading_when_no_definition_lies_between() {
478        let mut old = String::from("fn only() {\n");
479        old.extend((0..20).map(|i| format!("    line{i};\n")));
480        old.push_str("}\n");
481        let new = old
482            .replace("line2;", "LINE2;")
483            .replace("line17;", "LINE17;");
484        let hunks = histogram_hunks(&old, &new, "f.rs", 1, true);
485        let contexts: Vec<_> = hunks.iter().map(|h| h.context.as_str()).collect();
486        assert_eq!(contexts, ["fn only() {", "fn only() {"]);
487    }
488
489    #[test]
490    fn hunk_context_is_cut_to_git_s_80_bytes_on_a_char_boundary() {
491        let name = "é".repeat(60);
492        let old = format!("fn {name}() {{\n    a;\n    b;\n}}\n");
493        let new = old.replace("    b;", "    B;");
494        let hunks = histogram_hunks(&old, &new, "f.rs", 0, true);
495        assert_eq!(hunks[0].context, format!("fn {}", "é".repeat(38)));
496    }
497}
diffler_core/diffalgo.rs

diffler_core/
diffalgo.rs
