//! Tiny line-based unified diff (LCS + hunks). Zero deps; good enough for
//! showing "what changed" between two versions of a text file on the hub
//! and in the cli. Not a patch tool — output is for reading.
const MAX_LINES: usize = 4000;
const CONTEXT: usize = 3;
#[derive(Clone, Copy, PartialEq)]
enum Kind {
Eq,
Del,
Ins,
}
struct Line {
kind: Kind,
text: String,
/// line number in the old file (Eq/Del) — 0 when not applicable
a_no: usize,
/// line number in the new file (Eq/Ins) — 0 when not applicable
b_no: usize,
}
/// Unified diff of `a` (old) -> `b` (new), with `a_label`/`b_label` headers.
/// Returns an empty string when the contents are identical.
pub fn unified(a: &str, b: &str, a_label: &str, b_label: &str) -> String {
if a == b {
return String::new();
}
let al: Vec<&str> = a.lines().collect();
let bl: Vec<&str> = b.lines().collect();
if al.len() > MAX_LINES || bl.len() > MAX_LINES {
return format!(
"(file too large to diff: {} vs {} lines)\n",
al.len(),
bl.len()
);
}
// LCS table
let (n, m) = (al.len(), bl.len());
let mut dp = vec![vec![0u32; m + 1]; n + 1];
for i in (0..n).rev() {
for j in (0..m).rev() {
dp[i][j] = if al[i] == bl[j] {
dp[i + 1][j + 1] + 1
} else {
dp[i + 1][j].max(dp[i][j + 1])
};
}
}
// walk -> flat op list with line numbers
let mut lines: Vec<Line> = Vec::new();
let (mut i, mut j) = (0usize, 0usize);
let (mut an, mut bn) = (1usize, 1usize);
while i < n && j < m {
if al[i] == bl[j] {
lines.push(Line { kind: Kind::Eq, text: al[i].into(), a_no: an, b_no: bn });
i += 1;
j += 1;
an += 1;
bn += 1;
} else if dp[i + 1][j] >= dp[i][j + 1] {
lines.push(Line { kind: Kind::Del, text: al[i].into(), a_no: an, b_no: 0 });
i += 1;
an += 1;
} else {
lines.push(Line { kind: Kind::Ins, text: bl[j].into(), a_no: 0, b_no: bn });
j += 1;
bn += 1;
}
}
while i < n {
lines.push(Line { kind: Kind::Del, text: al[i].into(), a_no: an, b_no: 0 });
i += 1;
an += 1;
}
while j < m {
lines.push(Line { kind: Kind::Ins, text: bl[j].into(), a_no: 0, b_no: bn });
j += 1;
bn += 1;
}
// group change runs (+/- CONTEXT) into hunks
let changes: Vec<usize> = lines
.iter()
.enumerate()
.filter(|(_, l)| l.kind != Kind::Eq)
.map(|(k, _)| k)
.collect();
if changes.is_empty() {
return String::new();
}
let mut hunks: Vec<(usize, usize)> = Vec::new(); // [start, end)
for &c in &changes {
let s = c.saturating_sub(CONTEXT);
let e = (c + CONTEXT + 1).min(lines.len());
match hunks.last_mut() {
Some(last) if s <= last.1 => last.1 = last.1.max(e),
_ => hunks.push((s, e)),
}
}
let mut out = String::new();
out.push_str(&format!("--- {a_label}\n+++ {b_label}\n"));
for (s, e) in hunks {
let slice = &lines[s..e];
let old_start = slice
.iter()
.find(|l| l.a_no != 0)
.map(|l| l.a_no)
.unwrap_or(0);
let new_start = slice
.iter()
.find(|l| l.b_no != 0)
.map(|l| l.b_no)
.unwrap_or(0);
let old_len = slice.iter().filter(|l| l.kind != Kind::Ins).count();
let new_len = slice.iter().filter(|l| l.kind != Kind::Del).count();
out.push_str(&format!(
"@@ -{old_start},{old_len} +{new_start},{new_len} @@\n"
));
for l in slice {
let sign = match l.kind {
Kind::Eq => ' ',
Kind::Del => '-',
Kind::Ins => '+',
};
// avoid a trailing-space ambiguity for blank lines
if l.text.is_empty() {
out.push(sign);
out.push('\n');
} else {
out.push(sign);
out.push_str(&l.text);
out.push('\n');
}
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn identical_is_empty() {
assert_eq!(unified("a\nb\n", "a\nb\n", "a", "b"), "");
}
#[test]
fn modify_line() {
let d = unified("one\ntwo\nthree\n", "one\nTWO\nthree\n", "old", "new");
assert!(d.contains("--- old"));
assert!(d.contains("+++ new"));
assert!(d.contains("-two"));
assert!(d.contains("+TWO"));
assert!(d.contains(" one")); // context
}
#[test]
fn add_remove() {
let d = unified("a\nb\n", "a\nb\nc\n", "o", "n");
assert!(d.contains("+c"));
assert!(!d.contains("-a")); // a is context, not removed
let d2 = unified("a\nb\nc\n", "a\nc\n", "o", "n");
assert!(d2.contains("-b"));
}
#[test]
fn hunk_headers_and_context_cap() {
let old: String = (1..=50).map(|i| format!("line {i}\n")).collect();
let mut new = old.clone();
new = new.replace("line 25\n", "line 25 CHANGED\n");
let d = unified(&old, &new, "a", "b");
assert!(d.contains("@@"));
assert!(d.contains("-line 25"));
assert!(d.contains("+line 25 CHANGED"));
// only ~7 lines around the change, not all 50
assert!(d.lines().count() < 15);
}
}