Skip to main content

move_diff/
annotate_diff.rs

1//! Annotates a unified diff with extra markers for moved and reformatted
2//! code, on top of the usual `+`/`-` lines, to make large mechanical
3//! refactors easier to review.
4//!
5//! Marker legend:
6//! - `' '` context  (unchanged)
7//! - `'+'` addition (green)   — genuinely new content
8//! - `'-'` removal  (red)     — genuinely removed content
9//! - `'>'` moved out (cyan)   — this line left its old spot
10//! - `'<'` moved in  (blue)   — this line arrived from elsewhere
11//! - `'x'` reformat (magenta) — same content, only whitespace/layout changed;
12//!   only the new side is shown (the old side would be a whitespace-only
13//!   duplicate, so it's dropped rather than printed twice)
14//!
15//! Detection runs in three passes over each hunk's "change blocks" (a run of
16//! consecutive removed lines immediately followed by a run of consecutive
17//! added lines):
18//!
19//! 1. Whole-block reformat: if a block's removed lines and added lines are
20//!    identical once all whitespace is stripped, the entire block is a pure
21//!    reflow (handles reindentation and a linter wrapping/joining lines)
22//!    and gets `x`.
23//! 2. Global move detection: lines left over after pass 1 are matched,
24//!    whitespace-normalized, against lines in *other* blocks (any file). A
25//!    match seeds an anchor that is then extended line-by-line in both
26//!    directions within its block; forward extension tolerates a small
27//!    reflow window (so a moved line that was also split/joined still
28//!    counts as moved) and a configurable number of lines that differ for
29//!    real — an edit made during the move — before giving up. The
30//!    resulting run is only accepted as a move once it totals at least
31//!    `MIN_MOVE_ALNUM_CHARS` alphanumeric characters — the same rule
32//!    `git diff --color-moved`'s `blocks`/`zebra` modes use — otherwise
33//!    it's left as plain `+`/`-` and the next matching candidate (if any)
34//!    is tried instead.
35//! 3. Local leftover reconciliation: whatever remains unconsumed within a
36//!    single block is matched against the rest of that same block
37//!    (whitespace-normalized) to catch an in-place reformat sitting right
38//!    next to a move or a genuine addition. A match can be a single line or
39//!    a run of 2+ consecutive removed lines whose text, line-by-line, equals
40//!    2+ consecutive added lines (a run never skips over an unrelated line
41//!    on either side to stay alive). Two matches that *cross* — an earlier
42//!    removed line pairing with a later added line than a later removed
43//!    line does — are both rejected, since that describes the lines
44//!    swapping order, a real logic change, not a reformat. Anything still
45//!    unpaired is a plain addition/removal.
46
47use std::collections::HashMap;
48use std::fmt;
49use std::ops::Range;
50use std::str::FromStr;
51
52use anyhow::Result;
53use patch::{Line as PatchLine, Patch};
54
55use crate::diff_parse::{parse_patches_safely, split_file_diffs};
56
57/// Minimum number of non-whitespace characters a line needs before it's
58/// trusted as a move *anchor* on its own. Short/common lines (`}`, `{`,
59/// blank lines) are too likely to collide; they can still be swept into a
60/// moved block once extension reaches them from a trustworthy anchor.
61const MIN_ANCHOR_LEN: usize = 8;
62
63/// Minimum number of alphanumeric characters a matched run must contain,
64/// summed across every line it ends up covering, before it's accepted as
65/// a move rather than left as plain `+`/`-`.
66///
67/// Mirrors `git diff --color-moved`'s `blocks`/`zebra` modes exactly: same
68/// threshold, same metric (letters + digits only — punctuation and
69/// whitespace don't count), same hardcoded, unconfigurable constant. Below
70/// this, a match is indistinguishable from a coincidentally-duplicated
71/// short/common line sitting inside an unrelated block of real edits.
72const MIN_MOVE_ALNUM_CHARS: usize = 20;
73
74/// How many lines we're willing to try merging/splitting on either side
75/// when checking whether a mismatch during block extension is actually a
76/// pure reflow (e.g. a linter wrapping a long line into several).
77const MAX_REFLOW_WINDOW: usize = 10;
78
79/// How many real content changes are tolerated inside an otherwise-moved
80/// block before move detection gives up extending into that block (lines
81/// beyond this fall back to plain `+`/`-`).
82///
83/// Accepts either an absolute line count or a fraction/percentage of the
84/// remaining block length in whichever direction extension is currently
85/// going — a flat count under-tolerates large moved blocks that picked up
86/// a handful of real edits, while a fraction scales with the block.
87///
88/// Parsed from a string: a trailing `%` means relative (`"10%"` → 0.10), a
89/// bare value `< 1` is also relative (`"0.1"` is the same as `"10%"`), and
90/// a bare value `>= 1` is an absolute count (`"2"` → tolerate 2 lines).
91#[derive(Debug, Clone, Copy, PartialEq)]
92pub enum MoveGap {
93    Absolute(usize),
94    Relative(f64),
95}
96
97impl MoveGap {
98    /// The tolerance budget for a direction with `remaining_len` lines left
99    /// before the enclosing block's boundary.
100    fn budget_for(&self, remaining_len: usize) -> usize {
101        match self {
102            MoveGap::Absolute(n) => *n,
103            // `ceil` means any ratio > 0 yields a budget >= 1 as soon as
104            // there's at least one line left to extend into, with no need
105            // for a separate hardcoded floor — while an explicit ratio of
106            // exactly 0 still means exactly zero tolerance.
107            MoveGap::Relative(ratio) => (ratio * remaining_len as f64).ceil() as usize,
108        }
109    }
110}
111
112impl FromStr for MoveGap {
113    type Err = String;
114
115    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
116        let s = s.trim();
117        if let Some(pct) = s.strip_suffix('%') {
118            let v: f64 = pct
119                .trim()
120                .parse()
121                .map_err(|_| format!("invalid percentage: {s}"))?;
122            if v < 0.0 {
123                return Err(format!("percentage must be >= 0: {s}"));
124            }
125            return Ok(MoveGap::Relative(v / 100.0));
126        }
127        let v: f64 = s.parse().map_err(|_| format!("invalid number: {s}"))?;
128        if v < 0.0 {
129            return Err(format!("value must be >= 0: {s}"));
130        }
131        if v >= 1.0 {
132            Ok(MoveGap::Absolute(v.round() as usize))
133        } else {
134            Ok(MoveGap::Relative(v))
135        }
136    }
137}
138
139impl fmt::Display for MoveGap {
140    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
141        match self {
142            MoveGap::Absolute(n) => write!(f, "{n}"),
143            MoveGap::Relative(ratio) => write!(f, "{}%", ratio * 100.0),
144        }
145    }
146}
147
148#[derive(Debug, Clone, Copy, PartialEq, Eq)]
149enum Marker {
150    Add,
151    Remove,
152    MovedOut,
153    MovedIn,
154    Reformat,
155}
156
157/// One changed (non-context) line inside a hunk.
158#[derive(Debug, Clone)]
159struct ChangedLine {
160    text: String,
161    marker: Marker,
162    /// Index into the global `blocks` vector.
163    block: usize,
164}
165
166/// A maximal run of consecutive removed lines immediately followed by a
167/// maximal run of consecutive added lines, inside a single hunk.
168#[derive(Debug, Clone)]
169struct Block {
170    removes: Range<usize>,
171    adds: Range<usize>,
172}
173
174/// One element of a file's rendered hunk, in original diff order.
175enum RenderLine {
176    Context(String),
177    Removed(usize),
178    Added(usize),
179}
180
181struct FileHunks {
182    old_path: String,
183    new_path: String,
184    hunks: Vec<(String, Vec<RenderLine>)>,
185}
186
187/// One entry of the top-level diff, in original order: either a
188/// successfully parsed file (indexing into the parallel `files`/patch
189/// vectors) or the raw, unparsed text of a file whose entry couldn't be
190/// parsed (binary diff, mode-only change, pure rename, ...).
191enum Unit<'a> {
192    Parsed(usize),
193    Raw(&'a str),
194}
195
196fn normalize(s: &str) -> String {
197    s.chars().filter(|c| !c.is_whitespace()).collect()
198}
199
200fn is_anchor_eligible(s: &str) -> bool {
201    normalize(s).chars().count() >= MIN_ANCHOR_LEN
202}
203
204fn alnum_len(s: &str) -> usize {
205    s.chars().filter(|c| c.is_alphanumeric()).count()
206}
207
208/// Render `diff_text` (as produced by `git diff`) with move/reformat
209/// annotations.
210///
211/// `max_move_gap` bounds how many real (non-reflow) content changes are
212/// tolerated inside an otherwise-moved block before extension gives up.
213/// `color` enables ANSI colors.
214///
215/// Falls back to printing a file's own diff entry unannotated (with a
216/// warning on stderr) if that entry can't be parsed (e.g. a binary diff,
217/// mode-only change, or pure rename), rather than failing outright or
218/// discarding annotations for the rest of the diff — this is best-effort
219/// tooling on top of `git diff`, and one file's parser limitation
220/// shouldn't make every other file's diff unreadable.
221pub fn render(diff_text: &str, max_move_gap: MoveGap, color: bool) -> Result<String> {
222    // `git::local_diff` captures output via `duct`'s `.read()`, which (like
223    // shell `$()`) strips the trailing newline — but the `patch` crate's
224    // parser requires every line, including the last, to be newline
225    // terminated and *panics* (via an internal `assert!`, not a `Result`)
226    // if it isn't. Restoring the newline here fixes the overwhelmingly
227    // common case (any diff ending in a context line, which is most of
228    // them with the default 3-line context).
229    let diff_text = if diff_text.ends_with('\n') {
230        diff_text.to_string()
231    } else {
232        format!("{diff_text}\n")
233    };
234
235    let patches: Vec<Patch<'_>>;
236    let mut units: Vec<Unit<'_>> = Vec::new();
237    {
238        let mut collected = Vec::new();
239        for chunk in split_file_diffs(&diff_text) {
240            match parse_patches_safely(chunk) {
241                Ok(parsed) => {
242                    for p in parsed {
243                        units.push(Unit::Parsed(collected.len()));
244                        collected.push(p);
245                    }
246                }
247                Err(msg) => {
248                    eprintln!("warning: move-diff: {msg}; showing this file's plain diff instead");
249                    units.push(Unit::Raw(chunk));
250                }
251            }
252        }
253        patches = collected;
254    }
255
256    let mut removes: Vec<ChangedLine> = Vec::new();
257    let mut adds: Vec<ChangedLine> = Vec::new();
258    let mut blocks: Vec<Block> = Vec::new();
259    let mut files: Vec<FileHunks> = Vec::new();
260
261    for patch in &patches {
262        let mut hunks_out = Vec::new();
263
264        for hunk in &patch.hunks {
265            let mut render_lines: Vec<RenderLine> = Vec::new();
266
267            let mut pend_remove_start: Option<usize> = None;
268            let mut pend_add_start: Option<usize> = None;
269            let mut seen_add_in_block = false;
270
271            for line in &hunk.lines {
272                match line {
273                    PatchLine::Context(text) => {
274                        flush_block(
275                            &mut pend_remove_start,
276                            &mut pend_add_start,
277                            &mut seen_add_in_block,
278                            &mut removes,
279                            &mut adds,
280                            &mut blocks,
281                        );
282                        render_lines.push(RenderLine::Context(format!(" {text}")));
283                    }
284                    PatchLine::Remove(text) => {
285                        if seen_add_in_block {
286                            // A new remove run started without a context
287                            // line separating it from the previous block's
288                            // adds: treat it as a new block.
289                            flush_block(
290                                &mut pend_remove_start,
291                                &mut pend_add_start,
292                                &mut seen_add_in_block,
293                                &mut removes,
294                                &mut adds,
295                                &mut blocks,
296                            );
297                        }
298                        if pend_remove_start.is_none() {
299                            pend_remove_start = Some(removes.len());
300                        }
301                        render_lines.push(RenderLine::Removed(removes.len()));
302                        removes.push(ChangedLine {
303                            text: text.to_string(),
304                            marker: Marker::Remove,
305                            block: usize::MAX,
306                        });
307                    }
308                    PatchLine::Add(text) => {
309                        if pend_add_start.is_none() {
310                            pend_add_start = Some(adds.len());
311                        }
312                        seen_add_in_block = true;
313                        render_lines.push(RenderLine::Added(adds.len()));
314                        adds.push(ChangedLine {
315                            text: text.to_string(),
316                            marker: Marker::Add,
317                            block: usize::MAX,
318                        });
319                    }
320                }
321            }
322            flush_block(
323                &mut pend_remove_start,
324                &mut pend_add_start,
325                &mut seen_add_in_block,
326                &mut removes,
327                &mut adds,
328                &mut blocks,
329            );
330
331            hunks_out.push((
332                format!(
333                    "@@ -{} +{} @@{}",
334                    hunk.old_range, hunk.new_range, hunk.range_hint
335                ),
336                render_lines,
337            ));
338        }
339
340        files.push(FileHunks {
341            old_path: patch.old.to_string(),
342            new_path: patch.new.to_string(),
343            hunks: hunks_out,
344        });
345    }
346
347    // Pass 1: whole-block reformat.
348    for block in &blocks {
349        if block.removes.is_empty() || block.adds.is_empty() {
350            continue;
351        }
352        let old_sig: String = removes[block.removes.clone()]
353            .iter()
354            .map(|l| normalize(&l.text))
355            .collect();
356        let new_sig: String = adds[block.adds.clone()]
357            .iter()
358            .map(|l| normalize(&l.text))
359            .collect();
360        if old_sig == new_sig {
361            for l in removes[block.removes.clone()].iter_mut() {
362                l.marker = Marker::Reformat;
363            }
364            for l in adds[block.adds.clone()].iter_mut() {
365                l.marker = Marker::Reformat;
366            }
367        }
368    }
369
370    // Pass 2: global move detection (anchor + extend).
371    detect_moves(&mut removes, &mut adds, &blocks, max_move_gap);
372
373    // Pass 3: local leftover reconciliation.
374    for block in &blocks {
375        reconcile_leftovers(
376            &mut removes,
377            block.removes.clone(),
378            &mut adds,
379            block.adds.clone(),
380        );
381    }
382
383    Ok(render_output(&units, &files, &removes, &adds, color))
384}
385
386fn flush_block(
387    pend_remove_start: &mut Option<usize>,
388    pend_add_start: &mut Option<usize>,
389    seen_add_in_block: &mut bool,
390    removes: &mut [ChangedLine],
391    adds: &mut [ChangedLine],
392    blocks: &mut Vec<Block>,
393) {
394    // A block exists as soon as there's *either* a pending remove run or a
395    // pending add run — a run of pure additions (no removes before it) is
396    // just as much a block as a run with both sides.
397    if pend_remove_start.is_some() || pend_add_start.is_some() {
398        let rs = pend_remove_start.take().unwrap_or(removes.len());
399        let as_ = pend_add_start.take().unwrap_or(adds.len());
400        let r_range = rs..removes.len();
401        let a_range = as_..adds.len();
402        let block_idx = blocks.len();
403        for r in removes[r_range.clone()].iter_mut() {
404            r.block = block_idx;
405        }
406        for a in adds[a_range.clone()].iter_mut() {
407            a.block = block_idx;
408        }
409        blocks.push(Block {
410            removes: r_range,
411            adds: a_range,
412        });
413    }
414    *seen_add_in_block = false;
415}
416
417fn try_reflow(
418    removes: &[ChangedLine],
419    r_end: usize,
420    ri: usize,
421    adds: &[ChangedLine],
422    a_end: usize,
423    ai: usize,
424) -> Option<(usize, usize)> {
425    for total in 2..=(MAX_REFLOW_WINDOW * 2) {
426        let ro_max = MAX_REFLOW_WINDOW.min(total - 1);
427        for ro in 1..=ro_max {
428            let ao = total - ro;
429            if ao == 0 || ao > MAX_REFLOW_WINDOW {
430                continue;
431            }
432            if ri + ro > r_end || ai + ao > a_end {
433                continue;
434            }
435            if removes[ri..ri + ro]
436                .iter()
437                .any(|l| l.marker != Marker::Remove)
438                || adds[ai..ai + ao].iter().any(|l| l.marker != Marker::Add)
439            {
440                continue;
441            }
442            let old_sig: String = removes[ri..ri + ro]
443                .iter()
444                .map(|l| normalize(&l.text))
445                .collect();
446            let new_sig: String = adds[ai..ai + ao]
447                .iter()
448                .map(|l| normalize(&l.text))
449                .collect();
450            if old_sig == new_sig {
451                return Some((ro, ao));
452            }
453        }
454    }
455    None
456}
457
458fn detect_moves(
459    removes: &mut [ChangedLine],
460    adds: &mut [ChangedLine],
461    blocks: &[Block],
462    max_move_gap: MoveGap,
463) {
464    // Index every added line by its whitespace-normalized text once, up
465    // front, instead of rescanning the whole `adds` slice from scratch for
466    // every anchor attempt (that used to make this O(matches × R × A)). A
467    // stale entry (pointing at a line already consumed elsewhere) is cheap
468    // to detect per-candidate via the marker check below, so there's no
469    // need to prune the index as lines get consumed.
470    let mut add_index: HashMap<String, Vec<usize>> = HashMap::new();
471    for (j, a) in adds.iter().enumerate() {
472        add_index.entry(normalize(&a.text)).or_default().push(j);
473    }
474
475    // A single forward pass over `removes`: once visited here (whether it
476    // became an anchor or not), a line never needs revisiting — markers
477    // only ever move away from `Remove`, never back to it, so a line that
478    // wasn't eligible (or whose candidates all got rejected) now can't
479    // become eligible on some later, repeated pass.
480    for r_anchor in 0..removes.len() {
481        if removes[r_anchor].marker != Marker::Remove
482            || !is_anchor_eligible(&removes[r_anchor].text)
483        {
484            continue;
485        }
486        let key = normalize(&removes[r_anchor].text);
487        let r_block_idx = removes[r_anchor].block;
488        let Some(candidates) = add_index.get(&key) else {
489            continue;
490        };
491
492        for &a_anchor in candidates {
493            if adds[a_anchor].marker != Marker::Add || adds[a_anchor].block == r_block_idx {
494                continue;
495            }
496
497            let r_block = blocks[r_block_idx].clone();
498            let a_block = blocks[adds[a_anchor].block].clone();
499
500            // Measure the run first, without mutating anything, so a run
501            // that doesn't clear MIN_MOVE_ALNUM_CHARS can be left exactly
502            // as-is and the next candidate (if any) tried instead.
503            let mut moved_r = vec![r_anchor];
504            let mut moved_a = vec![a_anchor];
505
506            // Extend forward.
507            let mut ri = r_anchor + 1;
508            let mut ai = a_anchor + 1;
509            let fwd_remaining = (r_block.removes.end - ri).min(a_block.adds.end.saturating_sub(ai));
510            let mut gap_budget = max_move_gap.budget_for(fwd_remaining);
511            while ri < r_block.removes.end && ai < a_block.adds.end {
512                if removes[ri].marker != Marker::Remove || adds[ai].marker != Marker::Add {
513                    break;
514                }
515                if normalize(&removes[ri].text) == normalize(&adds[ai].text) {
516                    moved_r.push(ri);
517                    moved_a.push(ai);
518                    ri += 1;
519                    ai += 1;
520                    continue;
521                }
522                if let Some((rn, an)) =
523                    try_reflow(removes, r_block.removes.end, ri, adds, a_block.adds.end, ai)
524                {
525                    moved_r.extend(ri..ri + rn);
526                    moved_a.extend(ai..ai + an);
527                    ri += rn;
528                    ai += an;
529                    continue;
530                }
531                if gap_budget == 0 {
532                    break;
533                }
534                gap_budget -= 1;
535                ri += 1;
536                ai += 1;
537            }
538
539            // Extend backward (exact matches only — a reflow at the start
540            // of a moved block is rare enough that tracking variable-size
541            // backward windows isn't worth the complexity for v1).
542            let mut ri = r_anchor;
543            let mut ai = a_anchor;
544            let back_remaining =
545                (ri - r_block.removes.start).min(ai.saturating_sub(a_block.adds.start));
546            let mut gap_budget = max_move_gap.budget_for(back_remaining);
547            while ri > r_block.removes.start && ai > a_block.adds.start {
548                let pri = ri - 1;
549                let pai = ai - 1;
550                if removes[pri].marker != Marker::Remove || adds[pai].marker != Marker::Add {
551                    break;
552                }
553                if normalize(&removes[pri].text) == normalize(&adds[pai].text) {
554                    moved_r.push(pri);
555                    moved_a.push(pai);
556                    ri = pri;
557                    ai = pai;
558                    continue;
559                }
560                if gap_budget == 0 {
561                    break;
562                }
563                gap_budget -= 1;
564                ri = pri;
565                ai = pai;
566            }
567
568            // Same rule as `git diff --color-moved`'s `blocks`/`zebra`
569            // modes: a matched run is only painted as moved once it
570            // totals at least MIN_MOVE_ALNUM_CHARS alphanumeric
571            // characters. Below that, it's indistinguishable from a
572            // coincidentally-duplicated short/common line sitting inside
573            // an unrelated block of real edits — try the next candidate
574            // add for this same anchor (if any) instead of committing.
575            let total_alnum: usize = moved_r.iter().map(|&i| alnum_len(&removes[i].text)).sum();
576            if total_alnum < MIN_MOVE_ALNUM_CHARS {
577                continue;
578            }
579
580            for &i in &moved_r {
581                removes[i].marker = Marker::MovedOut;
582            }
583            for &j in &moved_a {
584                adds[j].marker = Marker::MovedIn;
585            }
586            break;
587        }
588    }
589}
590
591/// How many consecutive matching lines on each side a run needs before it
592/// wins out over a shorter candidate starting at the same removed line.
593const MIN_RECONCILE_RUN: usize = 2;
594
595/// A tentative leftover match found within one block: `len` consecutive
596/// removed lines starting at `ri_start`, matched (whitespace-normalized)
597/// against `len` consecutive added lines starting at `add_indices[pos_start]`.
598struct ReconcileMatch {
599    ri_start: usize,
600    pos_start: usize,
601    len: usize,
602}
603
604fn reconcile_leftovers(
605    removes: &mut [ChangedLine],
606    r_range: Range<usize>,
607    adds: &mut [ChangedLine],
608    a_range: Range<usize>,
609) {
610    let r_start = r_range.start;
611    let add_indices: Vec<usize> = a_range.collect();
612    let mut remove_claimed = vec![false; r_range.len()];
613    let mut add_used = vec![false; add_indices.len()];
614    let mut matches: Vec<ReconcileMatch> = Vec::new();
615
616    // Phase 1: find a tentative match for every leftover removed line,
617    // preferring the longest run it can start. Claims are tracked
618    // separately from `ChangedLine::marker` (rather than committing markers
619    // immediately) so a crossing conflict discovered later can still be
620    // rejected without having to undo anything.
621    for ri in r_range.clone() {
622        let local = ri - r_start;
623        if remove_claimed[local] || removes[ri].marker != Marker::Remove {
624            continue;
625        }
626        let key = normalize(&removes[ri].text);
627
628        let mut best: Option<(usize, usize)> = None; // (pos in add_indices, run length)
629        for (pos, &ai) in add_indices.iter().enumerate() {
630            if add_used[pos] || adds[ai].marker != Marker::Add || normalize(&adds[ai].text) != key {
631                continue;
632            }
633            // Extend forward with strict +1 adjacency on *both* sides: a run
634            // never skips over an unrelated or already-claimed line on
635            // either side to keep itself alive, so lines only "follow each
636            // other" when they're truly next to one another.
637            let mut len = 1;
638            loop {
639                let next_ri = ri + len;
640                let next_pos = pos + len;
641                if next_ri >= r_range.end || next_pos >= add_indices.len() {
642                    break;
643                }
644                let next_local = next_ri - r_start;
645                if remove_claimed[next_local] || add_used[next_pos] {
646                    break;
647                }
648                let next_ai = add_indices[next_pos];
649                if removes[next_ri].marker != Marker::Remove
650                    || adds[next_ai].marker != Marker::Add
651                    || normalize(&removes[next_ri].text) != normalize(&adds[next_ai].text)
652                {
653                    break;
654                }
655                len += 1;
656            }
657            if best.is_none_or(|(_, best_len)| len > best_len) {
658                best = Some((pos, len));
659            }
660            if len >= MIN_RECONCILE_RUN {
661                break;
662            }
663        }
664
665        let Some((pos, len)) = best else { continue };
666
667        for k in 0..len {
668            remove_claimed[local + k] = true;
669            add_used[pos + k] = true;
670        }
671        matches.push(ReconcileMatch {
672            ri_start: ri,
673            pos_start: pos,
674            len,
675        });
676    }
677
678    // Phase 2: reject any match that crosses another — an earlier removed
679    // line pairing with a later added line than a later removed line does.
680    // That describes the two lines swapping relative order, a real logic
681    // change, so neither side of either match is trusted as a reformat.
682    for (i, m) in matches.iter().enumerate() {
683        let crosses_another = matches.iter().enumerate().any(|(j, other)| {
684            i != j
685                && ((m.ri_start < other.ri_start && m.pos_start > other.pos_start)
686                    || (m.ri_start > other.ri_start && m.pos_start < other.pos_start))
687        });
688        if crosses_another {
689            continue;
690        }
691        for k in 0..m.len {
692            removes[m.ri_start + k].marker = Marker::Reformat;
693            adds[add_indices[m.pos_start + k]].marker = Marker::Reformat;
694        }
695    }
696}
697
698fn render_output(
699    units: &[Unit<'_>],
700    files: &[FileHunks],
701    removes: &[ChangedLine],
702    adds: &[ChangedLine],
703    color: bool,
704) -> String {
705    let mut out = String::new();
706    for unit in units {
707        match unit {
708            Unit::Raw(text) => out.push_str(text),
709            Unit::Parsed(idx) => render_file(&mut out, &files[*idx], removes, adds, color),
710        }
711    }
712    out
713}
714
715fn render_file(
716    out: &mut String,
717    file: &FileHunks,
718    removes: &[ChangedLine],
719    adds: &[ChangedLine],
720    color: bool,
721) {
722    out.push_str(&format!("--- {}\n", file.old_path));
723    out.push_str(&format!("+++ {}\n", file.new_path));
724    for (header, lines) in &file.hunks {
725        out.push_str(header);
726        out.push('\n');
727        for rl in lines {
728            match rl {
729                RenderLine::Context(text) => {
730                    out.push_str(text);
731                    out.push('\n');
732                }
733                RenderLine::Removed(i) => {
734                    let line = &removes[*i];
735                    // A reformat's removed side is a whitespace-only
736                    // duplicate of its added side (that's the definition of
737                    // `Marker::Reformat`); printing both would show the same
738                    // content twice, so only the added/new side is kept.
739                    if line.marker != Marker::Reformat {
740                        render_changed_line(out, line, color);
741                    }
742                }
743                RenderLine::Added(i) => render_changed_line(out, &adds[*i], color),
744            }
745        }
746    }
747}
748
749fn render_changed_line(out: &mut String, line: &ChangedLine, color: bool) {
750    let (ch, code) = match line.marker {
751        Marker::Remove => ('-', "31"),
752        Marker::Add => ('+', "32"),
753        Marker::MovedOut => ('>', "36"),
754        Marker::MovedIn => ('<', "34"),
755        Marker::Reformat => ('x', "35"),
756    };
757    if color {
758        out.push_str(&format!("\x1b[{code}m{ch}{}\x1b[0m\n", line.text));
759    } else {
760        out.push_str(&format!("{ch}{}\n", line.text));
761    }
762}
763
764#[cfg(test)]
765mod tests {
766    use super::*;
767
768    fn strip_ansi(s: &str) -> String {
769        let mut out = String::new();
770        let mut chars = s.chars();
771        while let Some(c) = chars.next() {
772            if c == '\x1b' {
773                for n in chars.by_ref() {
774                    if n == 'm' {
775                        break;
776                    }
777                }
778                continue;
779            }
780            out.push(c);
781        }
782        out
783    }
784
785    fn markers_only(rendered: &str) -> Vec<char> {
786        strip_ansi(rendered)
787            .lines()
788            .filter(|l| !l.starts_with("---") && !l.starts_with("+++") && !l.starts_with("@@"))
789            .map(|l| l.chars().next().unwrap_or(' '))
790            .collect()
791    }
792
793    const GAP1: MoveGap = MoveGap::Absolute(1);
794
795    #[test]
796    fn plain_add_remove() {
797        let diff = "--- a/f\n+++ b/f\n@@ -1,2 +1,2 @@\n-foo bar baz\n+quux bar baz\n context\n";
798        let out = render(diff, GAP1, false).unwrap();
799        assert_eq!(markers_only(&out), vec!['-', '+', ' ']);
800    }
801
802    #[test]
803    fn in_hunk_reformat_single_line() {
804        let diff = "--- a/f\n+++ b/f\n@@ -1,1 +1,1 @@\n-    if order.total>0.0 {\n+    if order.total > 0.0 {\n";
805        let out = render(diff, GAP1, false).unwrap();
806        // The removed side is a whitespace-only duplicate of the added
807        // side, so only the added side is rendered (as `x`).
808        assert_eq!(markers_only(&out), vec!['x']);
809    }
810
811    #[test]
812    fn in_hunk_reformat_line_wrap() {
813        let diff = "--- a/f\n+++ b/f\n@@ -1,1 +1,2 @@\n-    println!(\"a {} b {}\", x, y);\n+    println!(\"a {} b {}\",\n+        x, y);\n";
814        let out = render(diff, GAP1, false).unwrap();
815        // Same here: the single removed line is dropped, leaving only the
816        // two wrapped added lines, both `x`.
817        assert_eq!(markers_only(&out), vec!['x', 'x']);
818    }
819
820    #[test]
821    fn cross_hunk_move_same_file() {
822        let diff = "--- a/f\n+++ b/f\n@@ -1,3 +1,2 @@\n-    long_distinctive_call_one();\n context_a\n@@ -10,2 +9,3 @@\n context_b\n+    long_distinctive_call_one();\n";
823        let out = render(diff, GAP1, false).unwrap();
824        assert_eq!(markers_only(&out), vec!['>', ' ', ' ', '<']);
825    }
826
827    #[test]
828    fn move_with_real_change_inside() {
829        let diff = concat!(
830            "--- a/f\n",
831            "+++ b/f\n",
832            "@@ -1,4 +1,2 @@\n",
833            "-    if order.items.is_empty() {\n",
834            "-        return Err(anyhow!(\"empty order\"));\n",
835            "-    }\n",
836            " context_a\n",
837            "@@ -10,1 +8,4 @@\n",
838            " context_b\n",
839            "+    if order.items.is_empty() {\n",
840            "+        return Err(anyhow!(\"order has no items\"));\n",
841            "+    }\n",
842        );
843        let out = render(diff, GAP1, false).unwrap();
844        // The matched run ("if order.items.is_empty() {" + "}") totals
845        // only 19 alphanumeric characters — just under
846        // MIN_MOVE_ALNUM_CHARS (20) — so it's left as plain `-`/`+`
847        // rather than tagged as a move.
848        assert_eq!(
849            markers_only(&out),
850            vec!['-', '-', '-', ' ', ' ', '+', '+', '+']
851        );
852    }
853
854    #[test]
855    fn move_with_real_change_exceeding_gap_is_not_linked() {
856        let diff = concat!(
857            "--- a/f\n",
858            "+++ b/f\n",
859            "@@ -1,5 +1,2 @@\n",
860            "-    if order.items.is_empty() {\n",
861            "-        totally different line one\n",
862            "-        totally different line two\n",
863            "-    }\n",
864            " context_a\n",
865            "@@ -10,1 +8,5 @@\n",
866            " context_b\n",
867            "+    if order.items.is_empty() {\n",
868            "+        something else entirely one\n",
869            "+        something else entirely two\n",
870            "+    }\n",
871        );
872        // max_move_gap = 1: two consecutive real changes in a row should
873        // stop extension before reaching the closing brace. The anchor
874        // alone totals only 19 alphanumeric characters — under
875        // MIN_MOVE_ALNUM_CHARS (20) — so it's left as plain `-`/`+`.
876        let out = render(diff, GAP1, false).unwrap();
877        assert_eq!(
878            markers_only(&out),
879            vec!['-', '-', '-', '-', ' ', ' ', '+', '+', '+', '+']
880        );
881    }
882
883    #[test]
884    fn relative_gap_scales_with_block_size() {
885        // A 10-line moved block with 1 real change in the middle: an
886        // absolute gap of 1 would also allow this, but a relative gap large
887        // enough (50%) should too, while a tiny relative gap (5%, which
888        // ceils to 1 for a remaining length of ~4-5) still should — this
889        // mainly checks that Relative actually gets threaded through and
890        // produces a sane (non-zero) budget rather than panicking/always
891        // rejecting.
892        let diff = concat!(
893            "--- a/f\n",
894            "+++ b/f\n",
895            "@@ -1,6 +1,2 @@\n",
896            "-    line_one_in_the_block();\n",
897            "-    line_two_in_the_block();\n",
898            "-    totally_different_line();\n",
899            "-    line_four_in_the_block();\n",
900            "-    line_five_in_the_block();\n",
901            " context_a\n",
902            "@@ -20,1 +15,6 @@\n",
903            " context_b\n",
904            "+    line_one_in_the_block();\n",
905            "+    line_two_in_the_block();\n",
906            "+    something_else_entirely();\n",
907            "+    line_four_in_the_block();\n",
908            "+    line_five_in_the_block();\n",
909        );
910        let out = render(diff, MoveGap::Relative(0.5), false).unwrap();
911        assert_eq!(
912            markers_only(&out),
913            vec!['>', '>', '-', '>', '>', ' ', ' ', '<', '<', '+', '<', '<']
914        );
915    }
916
917    #[test]
918    fn zero_gap_means_no_tolerance() {
919        let diff = concat!(
920            "--- a/f\n",
921            "+++ b/f\n",
922            "@@ -1,3 +1,2 @@\n",
923            "-    line_one_in_the_block();\n",
924            "-    totally_different_line();\n",
925            " context_a\n",
926            "@@ -20,1 +15,3 @@\n",
927            " context_b\n",
928            "+    line_one_in_the_block();\n",
929            "+    something_else_entirely();\n",
930        );
931        let out = render(diff, MoveGap::Absolute(0), false).unwrap();
932        // Anchor-only match ("line_one_in_the_block();", 17 alphanumeric
933        // characters) stays under MIN_MOVE_ALNUM_CHARS (20), so it's left
934        // as plain `-`/`+` regardless of the zero gap tolerance.
935        assert_eq!(markers_only(&out), vec!['-', '-', ' ', ' ', '+', '+']);
936    }
937
938    #[test]
939    fn coincidental_short_line_in_a_large_edit_block_is_not_tagged_as_moved() {
940        // A block of 10 genuinely-rewritten lines where exactly one
941        // removed line happens to also appear, verbatim, among 10
942        // unrelated added lines elsewhere — the "single line moved in a
943        // block of 10 removals" false positive this threshold exists to
944        // suppress. "return false;" is anchor-eligible (12 non-whitespace
945        // chars) but only 11 alphanumeric characters, under
946        // MIN_MOVE_ALNUM_CHARS (20), and none of its neighbors match
947        // anything either, so extension can't grow the run. It must stay
948        // plain `-`/`+`, not `>`/`<`.
949        let diff = concat!(
950            "--- a/f\n",
951            "+++ b/f\n",
952            "@@ -1,10 +1,2 @@\n",
953            "-    validate_order_header(&order);\n",
954            "-    validate_order_items(&order);\n",
955            "-    validate_order_total(&order);\n",
956            "-    validate_order_address(&order);\n",
957            "-    return false;\n",
958            "-    validate_order_payment(&order);\n",
959            "-    validate_order_shipping(&order);\n",
960            "-    validate_order_discount(&order);\n",
961            "-    validate_order_customer(&order);\n",
962            "-    validate_order_metadata(&order);\n",
963            " context_a\n",
964            "@@ -20,1 +15,10 @@\n",
965            " context_b\n",
966            "+    check_header_valid(&order);\n",
967            "+    check_items_valid(&order);\n",
968            "+    check_total_valid(&order);\n",
969            "+    return false;\n",
970            "+    check_address_valid(&order);\n",
971            "+    check_payment_valid(&order);\n",
972            "+    check_shipping_valid(&order);\n",
973            "+    check_discount_valid(&order);\n",
974            "+    check_customer_valid(&order);\n",
975            "+    check_metadata_valid(&order);\n",
976        );
977        let out = render(diff, GAP1, false).unwrap();
978        assert_eq!(
979            markers_only(&out),
980            vec![
981                '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', ' ', ' ', '+', '+', '+', '+',
982                '+', '+', '+', '+', '+', '+',
983            ]
984        );
985    }
986
987    #[test]
988    fn long_enough_single_line_in_a_large_edit_block_is_still_tagged_as_moved() {
989        // Same shape as the test above — one matching line surrounded by
990        // 9 unrelated real edits on each side, no extension possible —
991        // but the matching line itself is long enough on its own
992        // (`log_security_audit_violation(&order);`, 25 alphanumeric
993        // characters) to clear MIN_MOVE_ALNUM_CHARS (20). This confirms
994        // the threshold is purely about match length, not about whether
995        // the surrounding block is otherwise "pure": a sufficiently
996        // distinctive single-line match is still a real move signal even
997        // inside a block of unrelated changes.
998        let diff = concat!(
999            "--- a/f\n",
1000            "+++ b/f\n",
1001            "@@ -1,10 +1,2 @@\n",
1002            "-    validate_order_header(&order);\n",
1003            "-    validate_order_items(&order);\n",
1004            "-    validate_order_total(&order);\n",
1005            "-    log_security_audit_violation(&order);\n",
1006            "-    validate_order_payment(&order);\n",
1007            "-    validate_order_shipping(&order);\n",
1008            "-    validate_order_discount(&order);\n",
1009            "-    validate_order_customer(&order);\n",
1010            "-    validate_order_metadata(&order);\n",
1011            "-    validate_order_currency(&order);\n",
1012            " context_a\n",
1013            "@@ -20,1 +15,10 @@\n",
1014            " context_b\n",
1015            "+    check_header_valid(&order);\n",
1016            "+    check_items_valid(&order);\n",
1017            "+    check_total_valid(&order);\n",
1018            "+    check_address_valid(&order);\n",
1019            "+    check_payment_valid(&order);\n",
1020            "+    check_shipping_valid(&order);\n",
1021            "+    log_security_audit_violation(&order);\n",
1022            "+    check_discount_valid(&order);\n",
1023            "+    check_customer_valid(&order);\n",
1024            "+    check_metadata_valid(&order);\n",
1025        );
1026        let out = render(diff, GAP1, false).unwrap();
1027        assert_eq!(
1028            markers_only(&out),
1029            vec![
1030                '-', '-', '-', '>', '-', '-', '-', '-', '-', '-', ' ', ' ', '+', '+', '+', '+',
1031                '+', '+', '<', '+', '+', '+',
1032            ]
1033        );
1034    }
1035
1036    #[test]
1037    fn contiguous_leftover_run_is_merged_into_one_reformat_block() {
1038        // "a = b" / "b = c" sit right next to each other on both sides, so
1039        // the pair is merged into one reformat run and both lines are
1040        // hidden on the removed side. The unrelated line on each side
1041        // (which keeps pass 1's whole-block check from firing) is left as a
1042        // plain addition/removal.
1043        let diff = concat!(
1044            "--- a/f\n",
1045            "+++ b/f\n",
1046            "@@ -1,3 +1,3 @@\n",
1047            "-    a = b\n",
1048            "-    b = c\n",
1049            "-    totally_unrelated_remove_line\n",
1050            "+    a=b\n",
1051            "+    b=c\n",
1052            "+    totally_unrelated_add_line\n",
1053        );
1054        let out = render(diff, GAP1, false).unwrap();
1055        assert_eq!(markers_only(&out), vec!['-', 'x', 'x', '+']);
1056    }
1057
1058    #[test]
1059    fn isolated_single_line_match_still_merges_despite_unrelated_neighbors() {
1060        // "a = b" matches "a=b", and neither of its neighbors matches
1061        // anything — but a single matching line is self-explanatory on its
1062        // own (it's just a whitespace reflow of that one line), regardless
1063        // of what unrelated changes happen to sit nearby in the same block.
1064        let diff = concat!(
1065            "--- a/f\n",
1066            "+++ b/f\n",
1067            "@@ -1,3 +1,3 @@\n",
1068            "-    a = b\n",
1069            "-    unrelated_remove_one\n",
1070            "-    unrelated_remove_two\n",
1071            "+    unrelated_add_one\n",
1072            "+    a=b\n",
1073            "+    unrelated_add_two\n",
1074        );
1075        let out = render(diff, GAP1, false).unwrap();
1076        assert_eq!(markers_only(&out), vec!['-', '-', '+', 'x', '+']);
1077    }
1078
1079    #[test]
1080    fn sole_leftover_single_line_match_is_still_merged() {
1081        // The distinctive line is long enough to be detected as a move to
1082        // a different block elsewhere, which leaves "a = b" / "a=b" as the
1083        // only remaining leftover on each side of this block. A single
1084        // match still merges regardless of neighbors (see the test above),
1085        // so this is really just confirming the interaction with pass 2
1086        // doesn't change that.
1087        let diff = concat!(
1088            "--- a/f\n",
1089            "+++ b/f\n",
1090            "@@ -1,3 +1,2 @@\n",
1091            "-    really_long_distinctive_line_that_will_move_elsewhere();\n",
1092            "-    a = b\n",
1093            "+    a=b\n",
1094            " context_a\n",
1095            "@@ -10,1 +9,2 @@\n",
1096            " context_b\n",
1097            "+    really_long_distinctive_line_that_will_move_elsewhere();\n",
1098        );
1099        let out = render(diff, GAP1, false).unwrap();
1100        assert_eq!(markers_only(&out), vec!['>', 'x', ' ', ' ', '<']);
1101    }
1102
1103    #[test]
1104    fn gap_in_the_middle_prevents_grouping_but_each_line_still_matches() {
1105        // "a=b" and "b=c" each have a match on the other side, but an
1106        // unrelated line sits between them at the same relative position on
1107        // *both* sides, breaking the strict adjacency a run requires. They
1108        // can't be grouped into one run, but each is still matched (and
1109        // merged) individually, since matching them in this order doesn't
1110        // cross anything.
1111        let diff = concat!(
1112            "--- a/f\n",
1113            "+++ b/f\n",
1114            "@@ -1,3 +1,3 @@\n",
1115            "-    a = b\n",
1116            "-    totally_unrelated_remove_line\n",
1117            "-    b = c\n",
1118            "+    a=b\n",
1119            "+    totally_unrelated_add_line\n",
1120            "+    b=c\n",
1121        );
1122        let out = render(diff, GAP1, false).unwrap();
1123        assert_eq!(markers_only(&out), vec!['-', 'x', '+', 'x']);
1124    }
1125
1126    #[test]
1127    fn crossing_matches_are_rejected_as_a_reorder_not_a_reformat() {
1128        // "a = b" / "c = d" come out in the opposite order on the added
1129        // side. Matching either one to its counterpart would require
1130        // crossing the other — i.e. the lines swapped relative order, which
1131        // is a real logic change (statement reordering), not a pure
1132        // reflow — so neither match is accepted and all four lines stay
1133        // plain -/+.
1134        let diff = concat!(
1135            "--- a/f\n",
1136            "+++ b/f\n",
1137            "@@ -1,2 +1,2 @@\n",
1138            "-    a = b\n",
1139            "-    c = d\n",
1140            "+    c=d\n",
1141            "+    a=b\n",
1142        );
1143        let out = render(diff, GAP1, false).unwrap();
1144        assert_eq!(markers_only(&out), vec!['-', '-', '+', '+']);
1145    }
1146
1147    #[test]
1148    fn parse_absolute_integer() {
1149        assert_eq!("1".parse::<MoveGap>().unwrap(), MoveGap::Absolute(1));
1150        assert_eq!("2".parse::<MoveGap>().unwrap(), MoveGap::Absolute(2));
1151        assert_eq!("0".parse::<MoveGap>().unwrap(), MoveGap::Relative(0.0));
1152    }
1153
1154    #[test]
1155    fn parse_relative_percentage() {
1156        match "10%".parse::<MoveGap>().unwrap() {
1157            MoveGap::Relative(r) => assert!((r - 0.10).abs() < f64::EPSILON),
1158            other => panic!("expected Relative, got {other:?}"),
1159        }
1160    }
1161
1162    #[test]
1163    fn parse_relative_fraction() {
1164        match "0.1".parse::<MoveGap>().unwrap() {
1165            MoveGap::Relative(r) => assert!((r - 0.1).abs() < f64::EPSILON),
1166            other => panic!("expected Relative, got {other:?}"),
1167        }
1168    }
1169
1170    #[test]
1171    fn parse_rejects_negative_and_garbage() {
1172        assert!("-1".parse::<MoveGap>().is_err());
1173        assert!("abc".parse::<MoveGap>().is_err());
1174        assert!("-5%".parse::<MoveGap>().is_err());
1175    }
1176
1177    #[test]
1178    fn missing_trailing_newline_does_not_panic() {
1179        // `git::local_diff` strips the trailing newline (duct's `.read()`
1180        // behaves like shell `$()`); the `patch` crate's parser panics on
1181        // that unless we restore it. Regression test for that fix.
1182        let diff = "--- a/f\n+++ b/f\n@@ -1,2 +1,2 @@\n-old\n+new\n trailing context, no newline after this";
1183        let out = render(diff, GAP1, false).unwrap();
1184        assert_eq!(markers_only(&out), vec!['-', '+', ' ']);
1185    }
1186
1187    #[test]
1188    fn unparseable_input_falls_back_to_plain_text_instead_of_erroring() {
1189        let not_a_diff = "this is not a unified diff at all\njust some text\n";
1190        let out = render(not_a_diff, GAP1, false).unwrap();
1191        assert_eq!(out, not_a_diff);
1192    }
1193
1194    #[test]
1195    fn one_unparseable_file_falls_back_without_losing_annotations_for_others() {
1196        // A normal text-hunk file followed by a binary file, each with its
1197        // own `diff --git` header as real `git diff` output would produce.
1198        // Regression test for "one bad file nukes annotations for the
1199        // whole diff": the binary entry should fall back to its raw text
1200        // while the text file is still fully annotated.
1201        let diff = concat!(
1202            "diff --git a/f b/f\n",
1203            "--- a/f\n",
1204            "+++ b/f\n",
1205            "@@ -1,2 +1,2 @@\n",
1206            "-foo bar baz\n",
1207            "+quux bar baz\n",
1208            " context\n",
1209            "diff --git a/img.png b/img.png\n",
1210            "index 111..222 100644\n",
1211            "Binary files a/img.png and b/img.png differ\n",
1212        );
1213        let out = render(diff, GAP1, false).unwrap();
1214        // The text file is still parsed and annotated normally (not just
1215        // echoed verbatim): its hunk header is reconstructed by the
1216        // `patch` crate's `Display` impl rather than preserved byte-for-
1217        // byte.
1218        assert!(out.contains("-foo bar baz\n"), "got: {out}");
1219        assert!(out.contains("+quux bar baz\n"), "got: {out}");
1220        // The binary file's entry is preserved verbatim since it can't be
1221        // parsed into annotated hunks.
1222        assert!(
1223            out.contains("Binary files a/img.png and b/img.png differ\n"),
1224            "got: {out}"
1225        );
1226    }
1227
1228    #[test]
1229    fn single_chunk_with_no_git_header_still_recovers_from_parser_panic() {
1230        // Without a `diff --git` separator between the hunk and the binary
1231        // marker, this whole input is one unparseable chunk (see
1232        // `diff_parse::tests::parse_patches_safely_catches_parser_panic_on_binary_file_entry`).
1233        // `render` must still recover via `catch_unwind` and fall back to
1234        // the raw text instead of crashing.
1235        let diff = concat!(
1236            "--- a/f\n+++ b/f\n@@ -1,1 +1,1 @@\n-old\n+new\n",
1237            "Binary files a/img.png and b/img.png differ\n",
1238        );
1239        let out = render(diff, GAP1, false).unwrap();
1240        assert_eq!(out, diff);
1241    }
1242}