use std::collections::HashMap;
use std::fmt;
use std::ops::Range;
use std::str::FromStr;
use anyhow::Result;
use patch::{Line as PatchLine, Patch};
use crate::diff_parse::{parse_patches_safely, split_file_diffs};
const MIN_ANCHOR_LEN: usize = 8;
const MIN_MOVE_ALNUM_CHARS: usize = 20;
const MAX_REFLOW_WINDOW: usize = 10;
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum MoveGap {
Absolute(usize),
Relative(f64),
}
impl MoveGap {
fn budget_for(&self, remaining_len: usize) -> usize {
match self {
MoveGap::Absolute(n) => *n,
MoveGap::Relative(ratio) => (ratio * remaining_len as f64).ceil() as usize,
}
}
}
impl FromStr for MoveGap {
type Err = String;
fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
let s = s.trim();
if let Some(pct) = s.strip_suffix('%') {
let v: f64 = pct
.trim()
.parse()
.map_err(|_| format!("invalid percentage: {s}"))?;
if v < 0.0 {
return Err(format!("percentage must be >= 0: {s}"));
}
return Ok(MoveGap::Relative(v / 100.0));
}
let v: f64 = s.parse().map_err(|_| format!("invalid number: {s}"))?;
if v < 0.0 {
return Err(format!("value must be >= 0: {s}"));
}
if v >= 1.0 {
Ok(MoveGap::Absolute(v.round() as usize))
} else {
Ok(MoveGap::Relative(v))
}
}
}
impl fmt::Display for MoveGap {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
MoveGap::Absolute(n) => write!(f, "{n}"),
MoveGap::Relative(ratio) => write!(f, "{}%", ratio * 100.0),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Marker {
Add,
Remove,
MovedOut,
MovedIn,
Reformat,
}
#[derive(Debug, Clone)]
struct ChangedLine {
text: String,
marker: Marker,
block: usize,
}
#[derive(Debug, Clone)]
struct Block {
removes: Range<usize>,
adds: Range<usize>,
}
enum RenderLine {
Context(String),
Removed(usize),
Added(usize),
}
struct FileHunks {
old_path: String,
new_path: String,
hunks: Vec<(String, Vec<RenderLine>)>,
}
enum Unit<'a> {
Parsed(usize),
Raw(&'a str),
}
fn normalize(s: &str) -> String {
s.chars().filter(|c| !c.is_whitespace()).collect()
}
fn is_anchor_eligible(s: &str) -> bool {
normalize(s).chars().count() >= MIN_ANCHOR_LEN
}
fn alnum_len(s: &str) -> usize {
s.chars().filter(|c| c.is_alphanumeric()).count()
}
pub fn render(diff_text: &str, max_move_gap: MoveGap, color: bool) -> Result<String> {
let diff_text = if diff_text.ends_with('\n') {
diff_text.to_string()
} else {
format!("{diff_text}\n")
};
let patches: Vec<Patch<'_>>;
let mut units: Vec<Unit<'_>> = Vec::new();
{
let mut collected = Vec::new();
for chunk in split_file_diffs(&diff_text) {
match parse_patches_safely(chunk) {
Ok(parsed) => {
for p in parsed {
units.push(Unit::Parsed(collected.len()));
collected.push(p);
}
}
Err(msg) => {
eprintln!("warning: move-diff: {msg}; showing this file's plain diff instead");
units.push(Unit::Raw(chunk));
}
}
}
patches = collected;
}
let mut removes: Vec<ChangedLine> = Vec::new();
let mut adds: Vec<ChangedLine> = Vec::new();
let mut blocks: Vec<Block> = Vec::new();
let mut files: Vec<FileHunks> = Vec::new();
for patch in &patches {
let mut hunks_out = Vec::new();
for hunk in &patch.hunks {
let mut render_lines: Vec<RenderLine> = Vec::new();
let mut pend_remove_start: Option<usize> = None;
let mut pend_add_start: Option<usize> = None;
let mut seen_add_in_block = false;
for line in &hunk.lines {
match line {
PatchLine::Context(text) => {
flush_block(
&mut pend_remove_start,
&mut pend_add_start,
&mut seen_add_in_block,
&mut removes,
&mut adds,
&mut blocks,
);
render_lines.push(RenderLine::Context(format!(" {text}")));
}
PatchLine::Remove(text) => {
if seen_add_in_block {
flush_block(
&mut pend_remove_start,
&mut pend_add_start,
&mut seen_add_in_block,
&mut removes,
&mut adds,
&mut blocks,
);
}
if pend_remove_start.is_none() {
pend_remove_start = Some(removes.len());
}
render_lines.push(RenderLine::Removed(removes.len()));
removes.push(ChangedLine {
text: text.to_string(),
marker: Marker::Remove,
block: usize::MAX,
});
}
PatchLine::Add(text) => {
if pend_add_start.is_none() {
pend_add_start = Some(adds.len());
}
seen_add_in_block = true;
render_lines.push(RenderLine::Added(adds.len()));
adds.push(ChangedLine {
text: text.to_string(),
marker: Marker::Add,
block: usize::MAX,
});
}
}
}
flush_block(
&mut pend_remove_start,
&mut pend_add_start,
&mut seen_add_in_block,
&mut removes,
&mut adds,
&mut blocks,
);
hunks_out.push((
format!(
"@@ -{} +{} @@{}",
hunk.old_range, hunk.new_range, hunk.range_hint
),
render_lines,
));
}
files.push(FileHunks {
old_path: patch.old.to_string(),
new_path: patch.new.to_string(),
hunks: hunks_out,
});
}
for block in &blocks {
if block.removes.is_empty() || block.adds.is_empty() {
continue;
}
let old_sig: String = removes[block.removes.clone()]
.iter()
.map(|l| normalize(&l.text))
.collect();
let new_sig: String = adds[block.adds.clone()]
.iter()
.map(|l| normalize(&l.text))
.collect();
if old_sig == new_sig {
for l in removes[block.removes.clone()].iter_mut() {
l.marker = Marker::Reformat;
}
for l in adds[block.adds.clone()].iter_mut() {
l.marker = Marker::Reformat;
}
}
}
detect_moves(&mut removes, &mut adds, &blocks, max_move_gap);
for block in &blocks {
reconcile_leftovers(
&mut removes,
block.removes.clone(),
&mut adds,
block.adds.clone(),
);
}
Ok(render_output(&units, &files, &removes, &adds, color))
}
fn flush_block(
pend_remove_start: &mut Option<usize>,
pend_add_start: &mut Option<usize>,
seen_add_in_block: &mut bool,
removes: &mut [ChangedLine],
adds: &mut [ChangedLine],
blocks: &mut Vec<Block>,
) {
if pend_remove_start.is_some() || pend_add_start.is_some() {
let rs = pend_remove_start.take().unwrap_or(removes.len());
let as_ = pend_add_start.take().unwrap_or(adds.len());
let r_range = rs..removes.len();
let a_range = as_..adds.len();
let block_idx = blocks.len();
for r in removes[r_range.clone()].iter_mut() {
r.block = block_idx;
}
for a in adds[a_range.clone()].iter_mut() {
a.block = block_idx;
}
blocks.push(Block {
removes: r_range,
adds: a_range,
});
}
*seen_add_in_block = false;
}
fn try_reflow(
removes: &[ChangedLine],
r_end: usize,
ri: usize,
adds: &[ChangedLine],
a_end: usize,
ai: usize,
) -> Option<(usize, usize)> {
for total in 2..=(MAX_REFLOW_WINDOW * 2) {
let ro_max = MAX_REFLOW_WINDOW.min(total - 1);
for ro in 1..=ro_max {
let ao = total - ro;
if ao == 0 || ao > MAX_REFLOW_WINDOW {
continue;
}
if ri + ro > r_end || ai + ao > a_end {
continue;
}
if removes[ri..ri + ro]
.iter()
.any(|l| l.marker != Marker::Remove)
|| adds[ai..ai + ao].iter().any(|l| l.marker != Marker::Add)
{
continue;
}
let old_sig: String = removes[ri..ri + ro]
.iter()
.map(|l| normalize(&l.text))
.collect();
let new_sig: String = adds[ai..ai + ao]
.iter()
.map(|l| normalize(&l.text))
.collect();
if old_sig == new_sig {
return Some((ro, ao));
}
}
}
None
}
fn detect_moves(
removes: &mut [ChangedLine],
adds: &mut [ChangedLine],
blocks: &[Block],
max_move_gap: MoveGap,
) {
let mut add_index: HashMap<String, Vec<usize>> = HashMap::new();
for (j, a) in adds.iter().enumerate() {
add_index.entry(normalize(&a.text)).or_default().push(j);
}
for r_anchor in 0..removes.len() {
if removes[r_anchor].marker != Marker::Remove
|| !is_anchor_eligible(&removes[r_anchor].text)
{
continue;
}
let key = normalize(&removes[r_anchor].text);
let r_block_idx = removes[r_anchor].block;
let Some(candidates) = add_index.get(&key) else {
continue;
};
for &a_anchor in candidates {
if adds[a_anchor].marker != Marker::Add || adds[a_anchor].block == r_block_idx {
continue;
}
let r_block = blocks[r_block_idx].clone();
let a_block = blocks[adds[a_anchor].block].clone();
let mut moved_r = vec![r_anchor];
let mut moved_a = vec![a_anchor];
let mut ri = r_anchor + 1;
let mut ai = a_anchor + 1;
let fwd_remaining = (r_block.removes.end - ri).min(a_block.adds.end.saturating_sub(ai));
let mut gap_budget = max_move_gap.budget_for(fwd_remaining);
while ri < r_block.removes.end && ai < a_block.adds.end {
if removes[ri].marker != Marker::Remove || adds[ai].marker != Marker::Add {
break;
}
if normalize(&removes[ri].text) == normalize(&adds[ai].text) {
moved_r.push(ri);
moved_a.push(ai);
ri += 1;
ai += 1;
continue;
}
if let Some((rn, an)) =
try_reflow(removes, r_block.removes.end, ri, adds, a_block.adds.end, ai)
{
moved_r.extend(ri..ri + rn);
moved_a.extend(ai..ai + an);
ri += rn;
ai += an;
continue;
}
if gap_budget == 0 {
break;
}
gap_budget -= 1;
ri += 1;
ai += 1;
}
let mut ri = r_anchor;
let mut ai = a_anchor;
let back_remaining =
(ri - r_block.removes.start).min(ai.saturating_sub(a_block.adds.start));
let mut gap_budget = max_move_gap.budget_for(back_remaining);
while ri > r_block.removes.start && ai > a_block.adds.start {
let pri = ri - 1;
let pai = ai - 1;
if removes[pri].marker != Marker::Remove || adds[pai].marker != Marker::Add {
break;
}
if normalize(&removes[pri].text) == normalize(&adds[pai].text) {
moved_r.push(pri);
moved_a.push(pai);
ri = pri;
ai = pai;
continue;
}
if gap_budget == 0 {
break;
}
gap_budget -= 1;
ri = pri;
ai = pai;
}
let total_alnum: usize = moved_r.iter().map(|&i| alnum_len(&removes[i].text)).sum();
if total_alnum < MIN_MOVE_ALNUM_CHARS {
continue;
}
for &i in &moved_r {
removes[i].marker = Marker::MovedOut;
}
for &j in &moved_a {
adds[j].marker = Marker::MovedIn;
}
break;
}
}
}
fn reconcile_leftovers(
removes: &mut [ChangedLine],
r_range: Range<usize>,
adds: &mut [ChangedLine],
a_range: Range<usize>,
) {
let add_indices: Vec<usize> = a_range.collect();
let mut used = vec![false; add_indices.len()];
for ri in r_range {
if removes[ri].marker != Marker::Remove {
continue;
}
let key = normalize(&removes[ri].text);
if let Some(pos) = add_indices.iter().enumerate().position(|(k, &ai)| {
!used[k] && adds[ai].marker == Marker::Add && normalize(&adds[ai].text) == key
}) {
used[pos] = true;
removes[ri].marker = Marker::Reformat;
adds[add_indices[pos]].marker = Marker::Reformat;
}
}
}
fn render_output(
units: &[Unit<'_>],
files: &[FileHunks],
removes: &[ChangedLine],
adds: &[ChangedLine],
color: bool,
) -> String {
let mut out = String::new();
for unit in units {
match unit {
Unit::Raw(text) => out.push_str(text),
Unit::Parsed(idx) => render_file(&mut out, &files[*idx], removes, adds, color),
}
}
out
}
fn render_file(
out: &mut String,
file: &FileHunks,
removes: &[ChangedLine],
adds: &[ChangedLine],
color: bool,
) {
out.push_str(&format!("--- {}\n", file.old_path));
out.push_str(&format!("+++ {}\n", file.new_path));
for (header, lines) in &file.hunks {
out.push_str(header);
out.push('\n');
for rl in lines {
match rl {
RenderLine::Context(text) => {
out.push_str(text);
out.push('\n');
}
RenderLine::Removed(i) => {
let line = &removes[*i];
if line.marker != Marker::Reformat {
render_changed_line(out, line, color);
}
}
RenderLine::Added(i) => render_changed_line(out, &adds[*i], color),
}
}
}
}
fn render_changed_line(out: &mut String, line: &ChangedLine, color: bool) {
let (ch, code) = match line.marker {
Marker::Remove => ('-', "31"),
Marker::Add => ('+', "32"),
Marker::MovedOut => ('>', "36"),
Marker::MovedIn => ('<', "34"),
Marker::Reformat => ('x', "35"),
};
if color {
out.push_str(&format!("\x1b[{code}m{ch}{}\x1b[0m\n", line.text));
} else {
out.push_str(&format!("{ch}{}\n", line.text));
}
}
#[cfg(test)]
mod tests {
use super::*;
fn strip_ansi(s: &str) -> String {
let mut out = String::new();
let mut chars = s.chars();
while let Some(c) = chars.next() {
if c == '\x1b' {
for n in chars.by_ref() {
if n == 'm' {
break;
}
}
continue;
}
out.push(c);
}
out
}
fn markers_only(rendered: &str) -> Vec<char> {
strip_ansi(rendered)
.lines()
.filter(|l| !l.starts_with("---") && !l.starts_with("+++") && !l.starts_with("@@"))
.map(|l| l.chars().next().unwrap_or(' '))
.collect()
}
const GAP1: MoveGap = MoveGap::Absolute(1);
#[test]
fn plain_add_remove() {
let diff = "--- a/f\n+++ b/f\n@@ -1,2 +1,2 @@\n-foo bar baz\n+quux bar baz\n context\n";
let out = render(diff, GAP1, false).unwrap();
assert_eq!(markers_only(&out), vec!['-', '+', ' ']);
}
#[test]
fn in_hunk_reformat_single_line() {
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";
let out = render(diff, GAP1, false).unwrap();
assert_eq!(markers_only(&out), vec!['x']);
}
#[test]
fn in_hunk_reformat_line_wrap() {
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";
let out = render(diff, GAP1, false).unwrap();
assert_eq!(markers_only(&out), vec!['x', 'x']);
}
#[test]
fn cross_hunk_move_same_file() {
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";
let out = render(diff, GAP1, false).unwrap();
assert_eq!(markers_only(&out), vec!['>', ' ', ' ', '<']);
}
#[test]
fn move_with_real_change_inside() {
let diff = concat!(
"--- a/f\n",
"+++ b/f\n",
"@@ -1,4 +1,2 @@\n",
"- if order.items.is_empty() {\n",
"- return Err(anyhow!(\"empty order\"));\n",
"- }\n",
" context_a\n",
"@@ -10,1 +8,4 @@\n",
" context_b\n",
"+ if order.items.is_empty() {\n",
"+ return Err(anyhow!(\"order has no items\"));\n",
"+ }\n",
);
let out = render(diff, GAP1, false).unwrap();
assert_eq!(
markers_only(&out),
vec!['-', '-', '-', ' ', ' ', '+', '+', '+']
);
}
#[test]
fn move_with_real_change_exceeding_gap_is_not_linked() {
let diff = concat!(
"--- a/f\n",
"+++ b/f\n",
"@@ -1,5 +1,2 @@\n",
"- if order.items.is_empty() {\n",
"- totally different line one\n",
"- totally different line two\n",
"- }\n",
" context_a\n",
"@@ -10,1 +8,5 @@\n",
" context_b\n",
"+ if order.items.is_empty() {\n",
"+ something else entirely one\n",
"+ something else entirely two\n",
"+ }\n",
);
let out = render(diff, GAP1, false).unwrap();
assert_eq!(
markers_only(&out),
vec!['-', '-', '-', '-', ' ', ' ', '+', '+', '+', '+']
);
}
#[test]
fn relative_gap_scales_with_block_size() {
let diff = concat!(
"--- a/f\n",
"+++ b/f\n",
"@@ -1,6 +1,2 @@\n",
"- line_one_in_the_block();\n",
"- line_two_in_the_block();\n",
"- totally_different_line();\n",
"- line_four_in_the_block();\n",
"- line_five_in_the_block();\n",
" context_a\n",
"@@ -20,1 +15,6 @@\n",
" context_b\n",
"+ line_one_in_the_block();\n",
"+ line_two_in_the_block();\n",
"+ something_else_entirely();\n",
"+ line_four_in_the_block();\n",
"+ line_five_in_the_block();\n",
);
let out = render(diff, MoveGap::Relative(0.5), false).unwrap();
assert_eq!(
markers_only(&out),
vec!['>', '>', '-', '>', '>', ' ', ' ', '<', '<', '+', '<', '<']
);
}
#[test]
fn zero_gap_means_no_tolerance() {
let diff = concat!(
"--- a/f\n",
"+++ b/f\n",
"@@ -1,3 +1,2 @@\n",
"- line_one_in_the_block();\n",
"- totally_different_line();\n",
" context_a\n",
"@@ -20,1 +15,3 @@\n",
" context_b\n",
"+ line_one_in_the_block();\n",
"+ something_else_entirely();\n",
);
let out = render(diff, MoveGap::Absolute(0), false).unwrap();
assert_eq!(markers_only(&out), vec!['-', '-', ' ', ' ', '+', '+']);
}
#[test]
fn coincidental_short_line_in_a_large_edit_block_is_not_tagged_as_moved() {
let diff = concat!(
"--- a/f\n",
"+++ b/f\n",
"@@ -1,10 +1,2 @@\n",
"- validate_order_header(&order);\n",
"- validate_order_items(&order);\n",
"- validate_order_total(&order);\n",
"- validate_order_address(&order);\n",
"- return false;\n",
"- validate_order_payment(&order);\n",
"- validate_order_shipping(&order);\n",
"- validate_order_discount(&order);\n",
"- validate_order_customer(&order);\n",
"- validate_order_metadata(&order);\n",
" context_a\n",
"@@ -20,1 +15,10 @@\n",
" context_b\n",
"+ check_header_valid(&order);\n",
"+ check_items_valid(&order);\n",
"+ check_total_valid(&order);\n",
"+ return false;\n",
"+ check_address_valid(&order);\n",
"+ check_payment_valid(&order);\n",
"+ check_shipping_valid(&order);\n",
"+ check_discount_valid(&order);\n",
"+ check_customer_valid(&order);\n",
"+ check_metadata_valid(&order);\n",
);
let out = render(diff, GAP1, false).unwrap();
assert_eq!(
markers_only(&out),
vec![
'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', ' ', ' ', '+', '+', '+', '+',
'+', '+', '+', '+', '+', '+',
]
);
}
#[test]
fn long_enough_single_line_in_a_large_edit_block_is_still_tagged_as_moved() {
let diff = concat!(
"--- a/f\n",
"+++ b/f\n",
"@@ -1,10 +1,2 @@\n",
"- validate_order_header(&order);\n",
"- validate_order_items(&order);\n",
"- validate_order_total(&order);\n",
"- log_security_audit_violation(&order);\n",
"- validate_order_payment(&order);\n",
"- validate_order_shipping(&order);\n",
"- validate_order_discount(&order);\n",
"- validate_order_customer(&order);\n",
"- validate_order_metadata(&order);\n",
"- validate_order_currency(&order);\n",
" context_a\n",
"@@ -20,1 +15,10 @@\n",
" context_b\n",
"+ check_header_valid(&order);\n",
"+ check_items_valid(&order);\n",
"+ check_total_valid(&order);\n",
"+ check_address_valid(&order);\n",
"+ check_payment_valid(&order);\n",
"+ check_shipping_valid(&order);\n",
"+ log_security_audit_violation(&order);\n",
"+ check_discount_valid(&order);\n",
"+ check_customer_valid(&order);\n",
"+ check_metadata_valid(&order);\n",
);
let out = render(diff, GAP1, false).unwrap();
assert_eq!(
markers_only(&out),
vec![
'-', '-', '-', '>', '-', '-', '-', '-', '-', '-', ' ', ' ', '+', '+', '+', '+',
'+', '+', '<', '+', '+', '+',
]
);
}
#[test]
fn parse_absolute_integer() {
assert_eq!("1".parse::<MoveGap>().unwrap(), MoveGap::Absolute(1));
assert_eq!("2".parse::<MoveGap>().unwrap(), MoveGap::Absolute(2));
assert_eq!("0".parse::<MoveGap>().unwrap(), MoveGap::Relative(0.0));
}
#[test]
fn parse_relative_percentage() {
match "10%".parse::<MoveGap>().unwrap() {
MoveGap::Relative(r) => assert!((r - 0.10).abs() < f64::EPSILON),
other => panic!("expected Relative, got {other:?}"),
}
}
#[test]
fn parse_relative_fraction() {
match "0.1".parse::<MoveGap>().unwrap() {
MoveGap::Relative(r) => assert!((r - 0.1).abs() < f64::EPSILON),
other => panic!("expected Relative, got {other:?}"),
}
}
#[test]
fn parse_rejects_negative_and_garbage() {
assert!("-1".parse::<MoveGap>().is_err());
assert!("abc".parse::<MoveGap>().is_err());
assert!("-5%".parse::<MoveGap>().is_err());
}
#[test]
fn missing_trailing_newline_does_not_panic() {
let diff = "--- a/f\n+++ b/f\n@@ -1,2 +1,2 @@\n-old\n+new\n trailing context, no newline after this";
let out = render(diff, GAP1, false).unwrap();
assert_eq!(markers_only(&out), vec!['-', '+', ' ']);
}
#[test]
fn unparseable_input_falls_back_to_plain_text_instead_of_erroring() {
let not_a_diff = "this is not a unified diff at all\njust some text\n";
let out = render(not_a_diff, GAP1, false).unwrap();
assert_eq!(out, not_a_diff);
}
#[test]
fn one_unparseable_file_falls_back_without_losing_annotations_for_others() {
let diff = concat!(
"diff --git a/f b/f\n",
"--- a/f\n",
"+++ b/f\n",
"@@ -1,2 +1,2 @@\n",
"-foo bar baz\n",
"+quux bar baz\n",
" context\n",
"diff --git a/img.png b/img.png\n",
"index 111..222 100644\n",
"Binary files a/img.png and b/img.png differ\n",
);
let out = render(diff, GAP1, false).unwrap();
assert!(out.contains("-foo bar baz\n"), "got: {out}");
assert!(out.contains("+quux bar baz\n"), "got: {out}");
assert!(
out.contains("Binary files a/img.png and b/img.png differ\n"),
"got: {out}"
);
}
#[test]
fn single_chunk_with_no_git_header_still_recovers_from_parser_panic() {
let diff = concat!(
"--- a/f\n+++ b/f\n@@ -1,1 +1,1 @@\n-old\n+new\n",
"Binary files a/img.png and b/img.png differ\n",
);
let out = render(diff, GAP1, false).unwrap();
assert_eq!(out, diff);
}
}