crates/gunnar-server/src/diff.rs
//! **The tree diff `Refs.Diff` serves** (the event stream).
//!
//! Until this module existed the RPC answered:
//!
//! > `Refs.Diff`: the server has no tree-diff engine; gix's blob-diff is
//! > client-side porcelain and an S crate must not link it
//!
//! The second half of that sentence is still true and is why this file is here
//! rather than a dependency line. What it got wrong was the conclusion: a tree
//! diff is not blob porcelain. It is a walk over two trees, and the only thing
//! it needs from a repository is `GitServe::read` — which every engine has,
//! which the appliance already links, and which costs no crate.
//!
//! # What it computes, and what it does not
//!
//! * **Structure, exactly**: which paths were added, deleted, modified or
//! changed type, with both object ids and both raw modes. This is what a
//! change proposal is built on and it is never approximated.
//! * **Line counts, exactly**, by way of [`edit_counts`] — a bounded Myers
//! walk. Where the bound is hit the answer is a genuine *upper bound* (every
//! old line deleted, every new line inserted) and never a zero: a `0/0` on a
//! file that changed is the shape of "we did not look", and it is
//! indistinguishable from "nothing happened" to whoever reads it.
//! * **No rename detection.** `RENAMED` and `COPIED` exist in the proto and are
//! never emitted: a rename is a *heuristic* over content similarity, and
//! inventing one here would make the answer depend on a threshold nobody
//! chose. A rename is reported the way `git diff` without `-M` reports it —
//! one `DELETED` and one `ADDED` — which is the truth about the trees.
use std::collections::BTreeMap;
use gunnar_proto::{ChangeKind, FileChange};
use gunnar_store::git_storage_trait::{GitServe, ObjType};
use gunnar_store::object::{EntryKind, NamedTreeEntry, TreeIter};
/// How much of a blob is inspected for a NUL before it is called binary.
///
/// git's own number (`buffer_is_binary` reads the first 8000 bytes). Matching
/// it matters more than the value does: a file that `git diff` calls binary and
/// gunnar calls text is a difference two people will argue about.
const BINARY_PROBE_BYTES: usize = 8000;
/// The largest edit distance [`edit_counts`] will walk before giving the
/// upper-bound answer.
///
/// Myers is `O((N+M)·D)`, so the bound is on `D` — the number of changed lines
/// — and not on file size. A file of any length whose change is small is walked
/// exactly; a file whose change is enormous is the case where a minimal script
/// is both expensive and useless, since nobody reads a 100 000-line hunk.
const MAX_EDIT_DISTANCE: usize = 4096;
/// One side of the walk: a tree's entries by name.
type Entries = BTreeMap<Vec<u8>, Owned>;
/// A [`NamedTreeEntry`] that owns its name, so the tree buffer can be dropped.
#[derive(Debug, Clone)]
struct Owned {
oid: gix_hash::ObjectId,
kind: EntryKind,
mode: u32,
}
/// Everything that went wrong reading a repository during a diff.
#[derive(Debug)]
pub enum DiffError {
/// The object is not in this repository.
Missing(gix_hash::ObjectId),
/// The object is here and is not the kind the walk needed.
WrongKind {
oid: gix_hash::ObjectId,
want: &'static str,
got: ObjType,
},
/// The store could not answer.
Backend(String),
/// A tree object did not decode.
Corrupt {
oid: gix_hash::ObjectId,
reason: String,
},
}
impl std::fmt::Display for DiffError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
DiffError::Missing(oid) => write!(f, "object {oid} is not in this repository"),
DiffError::WrongKind { oid, want, got } => {
write!(f, "object {oid} is a {got:?} where a {want} was needed")
}
DiffError::Backend(why) => write!(f, "the repository could not be read: {why}"),
DiffError::Corrupt { oid, reason } => write!(f, "tree {oid} does not decode: {reason}"),
}
}
}
type Result<T> = std::result::Result<T, DiffError>;
/// Compare two trees and report every path that differs.
///
/// `path_prefixes` is a filter in the caller's terms: a change is reported when
/// its path starts with any of them, and an empty list means everything. The
/// walk **prunes** on it as well as filtering — a directory that no prefix can
/// reach is never read — which is what keeps a one-file diff of a large
/// repository a one-file cost.
///
/// The output is ordered by path, because the walk is: `BTreeMap` at every
/// level and depth-first in name order. A caller that sorted the result again
/// would be sorting a sorted list, and a caller that relied on insertion order
/// would be relying on nothing.
pub fn compare(
git: &dyn GitServe,
hash: gix_hash::Kind,
old_tree: Option<gix_hash::ObjectId>,
new_tree: Option<gix_hash::ObjectId>,
path_prefixes: &[String],
) -> Result<Vec<FileChange>> {
let mut out = Vec::new();
walk(git, hash, "", old_tree, new_tree, path_prefixes, &mut out)?;
Ok(out)
}
/// Does any filter reach into `dir`, or does `dir` reach into any filter?
///
/// Both directions are needed. `src/` must be walked for the filter
/// `src/lib.rs` (the filter reaches in), and it must also be walked for the
/// filter `src` (the directory is inside the filter). Checking only one of them
/// silently drops half the matches, which reads as "nothing changed there".
fn dir_is_interesting(dir: &str, prefixes: &[String]) -> bool {
if prefixes.is_empty() || dir.is_empty() {
return true;
}
prefixes
.iter()
.any(|p| p.starts_with(dir) || dir.starts_with(p.as_str()))
}
fn path_matches(path: &str, prefixes: &[String]) -> bool {
prefixes.is_empty() || prefixes.iter().any(|p| path.starts_with(p.as_str()))
}
fn read(git: &dyn GitServe, oid: gix_hash::ObjectId) -> Result<(ObjType, Vec<u8>)> {
git.read(oid.as_bytes())
.map_err(|err| DiffError::Backend(err.to_string()))?
.ok_or(DiffError::Missing(oid))
}
fn entries(git: &dyn GitServe, hash: gix_hash::Kind, tree: gix_hash::ObjectId) -> Result<Entries> {
let (kind, bytes) = read(git, tree)?;
if kind != ObjType::Tree {
return Err(DiffError::WrongKind {
oid: tree,
want: "tree",
got: kind,
});
}
let mut map = Entries::new();
for entry in TreeIter::from_bytes(&bytes, hash).named() {
let NamedTreeEntry {
oid,
kind,
name,
mode,
} = entry.map_err(|err| DiffError::Corrupt {
oid: tree,
reason: err.to_string(),
})?;
map.insert(name.to_vec(), Owned { oid, kind, mode });
}
Ok(map)
}
fn join(dir: &str, name: &[u8]) -> String {
// Lossy, once, at the boundary. git does not promise a path is UTF-8 and
// the proto field is a `string`, so the conversion has to happen somewhere;
// here it is visible rather than buried in a `Display`.
let name = String::from_utf8_lossy(name);
if dir.is_empty() {
name.into_owned()
} else {
format!("{dir}/{name}")
}
}
#[allow(clippy::too_many_arguments)]
fn walk(
git: &dyn GitServe,
hash: gix_hash::Kind,
dir: &str,
old_tree: Option<gix_hash::ObjectId>,
new_tree: Option<gix_hash::ObjectId>,
prefixes: &[String],
out: &mut Vec<FileChange>,
) -> Result<()> {
// **The one optimisation that makes this affordable**: two trees with the
// same id have the same contents, all the way down. Reading them to find
// that out is the difference between a diff of one commit and a diff of the
// repository.
if old_tree == new_tree {
return Ok(());
}
if !dir_is_interesting(dir, prefixes) {
return Ok(());
}
let old = match old_tree {
Some(id) => entries(git, hash, id)?,
None => Entries::new(),
};
let new = match new_tree {
Some(id) => entries(git, hash, id)?,
None => Entries::new(),
};
// Every name on either side, in order, each visited once.
let mut names: Vec<&Vec<u8>> = old.keys().chain(new.keys()).collect();
names.sort_unstable();
names.dedup();
for name in names {
let path = join(dir, name);
match (old.get(name), new.get(name)) {
(Some(a), Some(b)) => {
match (a.kind == EntryKind::Tree, b.kind == EntryKind::Tree) {
(true, true) => {
walk(git, hash, &path, Some(a.oid), Some(b.oid), prefixes, out)?
}
// A directory became a file or the other way round. Reported
// as the removal of everything under the tree plus the
// arrival of the file, because that is what happened to the
// paths — `TYPE_CHANGED` on the directory's own name would
// hide every file that went with it.
(true, false) => {
walk(git, hash, &path, Some(a.oid), None, prefixes, out)?;
emit_added(git, &path, b, prefixes, out)?;
}
(false, true) => {
emit_deleted(git, &path, a, prefixes, out)?;
walk(git, hash, &path, None, Some(b.oid), prefixes, out)?;
}
(false, false) => {
if a.oid == b.oid && a.mode == b.mode {
continue;
}
if !path_matches(&path, prefixes) {
continue;
}
// A blob that became a symlink, or either becoming a
// gitlink: the path survives and what lives there does
// not. `MODIFIED` would invite a line diff between two
// things that are not the same kind of thing.
let kind = if a.kind != b.kind {
ChangeKind::TypeChanged
} else {
ChangeKind::Modified
};
let (insertions, deletions, binary) =
if kind == ChangeKind::TypeChanged || a.oid == b.oid {
// Same bytes, different mode: no lines moved,
// and that 0/0 is a measurement rather than a
// gap.
(0, 0, false)
} else {
line_counts(git, Some(a.oid), Some(b.oid))?
};
out.push(FileChange {
kind: kind as i32,
path,
old_path: String::new(),
old_oid: a.oid.to_string(),
new_oid: b.oid.to_string(),
old_mode: a.mode,
new_mode: b.mode,
insertions,
deletions,
binary,
});
}
}
}
(Some(a), None) => {
if a.kind == EntryKind::Tree {
walk(git, hash, &path, Some(a.oid), None, prefixes, out)?;
} else {
emit_deleted(git, &path, a, prefixes, out)?;
}
}
(None, Some(b)) => {
if b.kind == EntryKind::Tree {
walk(git, hash, &path, None, Some(b.oid), prefixes, out)?;
} else {
emit_added(git, &path, b, prefixes, out)?;
}
}
(None, None) => unreachable!("the name came from one of the two maps"),
}
}
Ok(())
}
fn emit_added(
git: &dyn GitServe,
path: &str,
entry: &Owned,
prefixes: &[String],
out: &mut Vec<FileChange>,
) -> Result<()> {
if !path_matches(path, prefixes) {
return Ok(());
}
let (insertions, deletions, binary) = line_counts(git, None, Some(entry.oid))?;
out.push(FileChange {
kind: ChangeKind::Added as i32,
path: path.to_owned(),
old_path: String::new(),
old_oid: String::new(),
new_oid: entry.oid.to_string(),
old_mode: 0,
new_mode: entry.mode,
insertions,
deletions,
binary,
});
Ok(())
}
fn emit_deleted(
git: &dyn GitServe,
path: &str,
entry: &Owned,
prefixes: &[String],
out: &mut Vec<FileChange>,
) -> Result<()> {
if !path_matches(path, prefixes) {
return Ok(());
}
let (insertions, deletions, binary) = line_counts(git, Some(entry.oid), None)?;
out.push(FileChange {
kind: ChangeKind::Deleted as i32,
path: path.to_owned(),
old_path: String::new(),
old_oid: entry.oid.to_string(),
new_oid: String::new(),
old_mode: entry.mode,
new_mode: 0,
insertions,
deletions,
binary,
});
Ok(())
}
/// `(insertions, deletions, binary)` for one path.
///
/// A gitlink has no blob to read — its "oid" names a commit in another
/// repository — so it is reported as a zero-line, non-binary change. That is
/// the honest answer: the submodule pointer moved and no line in *this*
/// repository did.
fn line_counts(
git: &dyn GitServe,
old: Option<gix_hash::ObjectId>,
new: Option<gix_hash::ObjectId>,
) -> Result<(u64, u64, bool)> {
let load = |id: Option<gix_hash::ObjectId>| -> Result<Option<Vec<u8>>> {
match id {
None => Ok(None),
Some(id) => match read(git, id)? {
(ObjType::Blob, bytes) => Ok(Some(bytes)),
// A gitlink, or a tree reached through a path that is not one.
// Neither has lines; neither is an error.
_ => Ok(None),
},
}
};
let old = load(old)?;
let new = load(new)?;
let binary = [old.as_deref(), new.as_deref()]
.into_iter()
.flatten()
.any(is_binary);
if binary {
return Ok((0, 0, true));
}
let old_lines = lines(old.as_deref().unwrap_or_default());
let new_lines = lines(new.as_deref().unwrap_or_default());
let (insertions, deletions) = edit_counts(&old_lines, &new_lines);
Ok((insertions as u64, deletions as u64, false))
}
/// git's own binary probe: a NUL in the first [`BINARY_PROBE_BYTES`] bytes.
///
/// `pub(crate)` so [`crate::search`] skips the same blobs a diff would call
/// binary — one definition of "binary" for both, rather than two that can
/// disagree about the same file (one implementation).
pub(crate) fn is_binary(bytes: &[u8]) -> bool {
bytes.iter().take(BINARY_PROBE_BYTES).any(|byte| *byte == 0)
}
/// Split on `\n`, dropping the empty tail a trailing newline produces.
///
/// So a file of three newline-terminated lines is three lines and not four. A
/// file with no trailing newline is the same three, which means the *absence*
/// of a trailing newline is invisible to the counts — git reports it as a
/// marker in the patch text rather than as a line, and there is no patch text
/// here.
fn lines(bytes: &[u8]) -> Vec<&[u8]> {
let mut out: Vec<&[u8]> = bytes.split(|b| *b == b'\n').collect();
if bytes.is_empty() || matches!(out.last(), Some(last) if last.is_empty()) {
out.pop();
}
out
}
/// **How many lines were inserted and how many deleted**, exactly.
///
/// # Why the edit *distance* is enough
///
/// Myers' greedy algorithm finds `D`, the length of the shortest edit script,
/// which is `insertions + deletions`. The other equation is free: an edit
/// script turns a sequence of length `n` into one of length `m`, so
/// `insertions − deletions = m − n`. Two equations, two unknowns —
///
/// ```text
/// insertions = (D + (m − n)) / 2
/// deletions = (D − (m − n)) / 2
/// ```
///
/// — and `D` and `m − n` always have the same parity, so the division is exact.
/// That means the full edit *script* never has to be materialised, and with it
/// goes the `O(N·D)` memory that makes a naive Myers implementation fall over
/// on a large file. This walk keeps one `V` array of `2D+1` entries.
///
/// # The bound, and why exceeding it is still an answer
///
/// Past [`MAX_EDIT_DISTANCE`] the walk stops and returns
/// `(new.len(), old.len())` — delete everything, insert everything. That is a
/// **valid** edit script, merely not the shortest one, so the numbers stay an
/// upper bound on a real quantity. The alternative — reporting `0, 0` — is not
/// a worse estimate, it is a different claim, and it is false.
fn edit_counts(old: &[&[u8]], new: &[&[u8]]) -> (usize, usize) {
// Common prefix and suffix carry no edits and shrink the problem to the
// part that changed, which is what makes a one-line change in a large file
// cost one step instead of thousands.
let mut start = 0;
while start < old.len() && start < new.len() && old[start] == new[start] {
start += 1;
}
let mut end = 0;
while end < old.len() - start
&& end < new.len() - start
&& old[old.len() - 1 - end] == new[new.len() - 1 - end]
{
end += 1;
}
let a = &old[start..old.len() - end];
let b = &new[start..new.len() - end];
if a.is_empty() {
return (b.len(), 0);
}
if b.is_empty() {
return (0, a.len());
}
let (n, m) = (a.len(), b.len());
let max = (n + m).min(MAX_EDIT_DISTANCE);
// `v[k + max]` is the furthest `x` reached on diagonal `k`.
let mut v = vec![0usize; 2 * max + 2];
for d in 0..=max {
// `k` runs −d..=d in steps of two; the offset keeps the index positive.
let mut k = -(d as isize);
while k <= d as isize {
let idx = (k + max as isize) as usize;
let mut x = if k == -(d as isize) || (k != d as isize && v[idx - 1] < v[idx + 1]) {
v[idx + 1]
} else {
v[idx - 1] + 1
};
let mut y = (x as isize - k) as usize;
while x < n && y < m && a[x] == b[y] {
x += 1;
y += 1;
}
v[idx] = x;
if x >= n && y >= m {
// d == insertions + deletions, and m − n == insertions − deletions.
let delta = m as isize - n as isize;
let insertions = ((d as isize + delta) / 2) as usize;
let deletions = d - insertions;
return (insertions, deletions);
}
k += 2;
}
}
// The bound. An upper bound, and said as one.
(b.len(), a.len())
}
/// One step of an edit script, in old-file order.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Op {
/// `count` lines that are the same in both, starting at these offsets.
Equal {
old: usize,
new: usize,
count: usize,
},
/// `count` lines present only in the old file.
Delete { old: usize, count: usize },
/// `count` lines present only in the new file.
Insert { new: usize, count: usize },
}
/// **The full edit script**, not just its length.
///
/// [`edit_counts`] answers *how many* lines moved and needs only the edit
/// distance; a blame needs *which*, so this is the same Myers walk with its
/// trace kept and backtracked. It is a separate function because the trace
/// costs `O(D²)` where the distance alone costs `O(D)`, and the common caller —
/// a diff's line counts — must not pay for a script nobody reads.
///
/// Past [`MAX_EDIT_DISTANCE`] it returns the trivial script (delete everything,
/// insert everything). That is a **valid** script, so a blame built on it
/// attributes every line to the commit that rewrote the file — which is what
/// actually happened when a file changes that much.
pub fn diff_ops(old: &[&[u8]], new: &[&[u8]]) -> Vec<Op> {
let (n, m) = (old.len(), new.len());
if n == 0 && m == 0 {
return Vec::new();
}
let max = (n + m).min(MAX_EDIT_DISTANCE);
// `trace[d]` is the `V` array as it stood after round `d`. Myers' backtrack
// walks it in reverse to recover the path.
let mut trace: Vec<Vec<usize>> = Vec::new();
let mut v = vec![0usize; 2 * max + 2];
let mut found = None;
'outer: for d in 0..=max {
trace.push(v.clone());
let mut k = -(d as isize);
while k <= d as isize {
let idx = (k + max as isize) as usize;
let mut x = if k == -(d as isize) || (k != d as isize && v[idx - 1] < v[idx + 1]) {
v[idx + 1]
} else {
v[idx - 1] + 1
};
let mut y = (x as isize - k) as usize;
while x < n && y < m && old[x] == new[y] {
x += 1;
y += 1;
}
v[idx] = x;
if x >= n && y >= m {
found = Some(d);
break 'outer;
}
k += 2;
}
}
let Some(d_end) = found else {
// The bound. The trivial script, and it is a real one.
let mut out = Vec::new();
if n > 0 {
out.push(Op::Delete { old: 0, count: n });
}
if m > 0 {
out.push(Op::Insert { new: 0, count: m });
}
return out;
};
// Backtrack: from (n, m) down to (0, 0), recording the moves in reverse.
let mut ops: Vec<Op> = Vec::new();
let (mut x, mut y) = (n, m);
for d in (1..=d_end).rev() {
let v = &trace[d];
let k = x as isize - y as isize;
let idx = (k + max as isize) as usize;
let down = k == -(d as isize) || (k != d as isize && v[idx - 1] < v[idx + 1]);
let prev_k = if down { k + 1 } else { k - 1 };
let prev_x = v[(prev_k + max as isize) as usize];
let prev_y = (prev_x as isize - prev_k) as usize;
// The diagonal run first (it happened last), then the single step.
while x > prev_x && y > prev_y {
x -= 1;
y -= 1;
push_run(
&mut ops,
Op::Equal {
old: x,
new: y,
count: 1,
},
);
}
if down {
y -= 1;
push_run(&mut ops, Op::Insert { new: y, count: 1 });
} else {
x -= 1;
push_run(&mut ops, Op::Delete { old: x, count: 1 });
}
}
while x > 0 && y > 0 {
x -= 1;
y -= 1;
push_run(
&mut ops,
Op::Equal {
old: x,
new: y,
count: 1,
},
);
}
ops.reverse();
ops
}
/// Merge a one-line op into the run being built, backwards.
fn push_run(ops: &mut Vec<Op>, op: Op) {
match (ops.last_mut(), op) {
(
Some(Op::Equal { old, new, count }),
Op::Equal {
old: o,
new: nw,
count: 1,
},
) if *old == o + 1 && *new == nw + 1 => {
*old = o;
*new = nw;
*count += 1;
}
(Some(Op::Delete { old, count }), Op::Delete { old: o, count: 1 }) if *old == o + 1 => {
*old = o;
*count += 1;
}
(Some(Op::Insert { new, count }), Op::Insert { new: nw, count: 1 }) if *new == nw + 1 => {
*new = nw;
*count += 1;
}
_ => ops.push(op),
}
}
/// Where line `new_line` of the new file came from in the old one, if it was
/// already there.
///
/// `None` means the line is **new in this version** — which is exactly the
/// answer a blame stops on.
pub fn trace_line(old: &[&[u8]], new: &[&[u8]], new_line: usize) -> Option<usize> {
for op in diff_ops(old, new) {
if let Op::Equal { old, new, count } = op {
if new_line >= new && new_line < new + count {
return Some(old + (new_line - new));
}
}
}
None
}
/// Split a blob into lines, for callers outside this module.
pub fn split_lines(bytes: &[u8]) -> Vec<&[u8]> {
lines(bytes)
}
#[cfg(test)]
mod tests {
use super::{edit_counts, is_binary, lines, MAX_EDIT_DISTANCE};
fn count(old: &str, new: &str) -> (usize, usize) {
let old_lines = lines(old.as_bytes());
let new_lines = lines(new.as_bytes());
edit_counts(&old_lines, &new_lines)
}
#[test]
fn identical_files_have_no_edits() {
assert_eq!(count("a\nb\nc\n", "a\nb\nc\n"), (0, 0));
}
#[test]
fn one_line_replaced_is_one_in_and_one_out() {
// The classic case a "diff" that counts changed *files* gets wrong: a
// replacement is an insertion AND a deletion, not one edit.
assert_eq!(count("a\nb\nc\n", "a\nB\nc\n"), (1, 1));
}
#[test]
fn appended_lines_are_insertions_only() {
assert_eq!(count("a\n", "a\nb\nc\n"), (2, 0));
}
#[test]
fn removed_lines_are_deletions_only() {
assert_eq!(count("a\nb\nc\n", "a\n"), (0, 2));
}
#[test]
fn a_line_moved_is_counted_as_one_move_not_two_rewrites() {
// `b` moves from the front to the back. The minimal script is one
// delete and one insert; a line-by-line comparison would say three of
// each, which is the number that makes a review look enormous.
assert_eq!(count("b\na\nc\n", "a\nc\nb\n"), (1, 1));
}
#[test]
fn an_empty_file_gaining_content_is_all_insertions() {
assert_eq!(count("", "a\nb\n"), (2, 0));
assert_eq!(count("a\nb\n", ""), (0, 2));
}
#[test]
fn a_file_with_no_trailing_newline_has_the_same_line_count() {
assert_eq!(lines(b"a\nb").len(), 2);
assert_eq!(lines(b"a\nb\n").len(), 2);
assert_eq!(lines(b"").len(), 0);
}
/// Past the bound the answer is the trivial script, and the trivial script
/// is still an edit script. What must never happen is `(0, 0)`.
#[test]
fn a_change_past_the_bound_reports_an_upper_bound_and_never_zero() {
let old: String = (0..MAX_EDIT_DISTANCE + 100)
.map(|i| format!("old {i}\n"))
.collect();
let new: String = (0..MAX_EDIT_DISTANCE + 100)
.map(|i| format!("new {i}\n"))
.collect();
let (insertions, deletions) = count(&old, &new);
assert!(
insertions > 0 && deletions > 0,
"a wholesale rewrite reported {insertions} insertions and {deletions} deletions; a \
zero here is indistinguishable from `nothing changed`"
);
}
#[test]
fn a_nul_byte_makes_a_file_binary_and_a_high_byte_does_not() {
assert!(is_binary(b"\x89PNG\r\n\x1a\n\0\0"));
// UTF-8 text is full of bytes above 127 and is not binary.
assert!(!is_binary("räksmörgås\n".as_bytes()));
}
}
#[cfg(test)]
mod script_tests {
use super::{diff_ops, lines, trace_line, Op};
fn split(text: &str) -> Vec<&[u8]> {
lines(text.as_bytes())
}
/// The script must **cover** both files: every old line is deleted or
/// equal, every new line inserted or equal, each exactly once. A script
/// that skips a line is a blame that attributes it to the wrong commit.
fn covers(old: &str, new: &str) {
let (o, n) = (split(old), split(new));
let mut old_seen = vec![0usize; o.len()];
let mut new_seen = vec![0usize; n.len()];
for op in diff_ops(&o, &n) {
match op {
Op::Equal { old, new, count } => {
for i in 0..count {
old_seen[old + i] += 1;
new_seen[new + i] += 1;
assert_eq!(
o[old + i],
n[new + i],
"an Equal run names two lines that are not equal"
);
}
}
Op::Delete { old, count } => {
for i in 0..count {
old_seen[old + i] += 1;
}
}
Op::Insert { new, count } => {
for i in 0..count {
new_seen[new + i] += 1;
}
}
}
}
assert!(
old_seen.iter().all(|c| *c == 1),
"the script does not cover every old line exactly once: {old_seen:?}"
);
assert!(
new_seen.iter().all(|c| *c == 1),
"the script does not cover every new line exactly once: {new_seen:?}"
);
}
#[test]
fn the_script_covers_both_files_in_every_shape_that_matters() {
covers("", "");
covers("a\n", "");
covers("", "a\n");
covers("a\nb\nc\n", "a\nb\nc\n");
covers("a\nb\nc\n", "a\nB\nc\n");
covers("a\nb\nc\n", "c\nb\na\n");
covers("a\nb\nc\nd\ne\n", "a\nc\ne\n");
covers("x\n", "a\nb\nc\nd\n");
covers(
&(0..40).map(|i| format!("l{i}\n")).collect::<String>(),
&(0..40)
.map(|i| {
if i % 7 == 0 {
format!("L{i}\n")
} else {
format!("l{i}\n")
}
})
.collect::<String>(),
);
}
/// **A line that survived is traced back; a line that is new is not.**
/// Both halves are the blame's stopping rule.
#[test]
fn a_surviving_line_traces_back_and_a_new_line_does_not() {
let old = split("alpha\nbeta\ngamma\n");
let new = split("alpha\nINSERTED\nbeta\ngamma\n");
assert_eq!(trace_line(&old, &new, 0), Some(0), "`alpha` did not move");
assert_eq!(
trace_line(&old, &new, 1),
None,
"the inserted line must have no ancestor — that is where a blame stops"
);
assert_eq!(
trace_line(&old, &new, 2),
Some(1),
"`beta` moved down one and must trace back to where it was"
);
assert_eq!(trace_line(&old, &new, 3), Some(2));
}
/// A rewritten line is new, even though its neighbours survived.
#[test]
fn a_changed_line_has_no_ancestor() {
let old = split("keep\nold value\nkeep\n");
let new = split("keep\nnew value\nkeep\n");
assert_eq!(trace_line(&old, &new, 0), Some(0));
assert_eq!(
trace_line(&old, &new, 1),
None,
"the changed line must be attributed to the commit that changed it"
);
assert_eq!(trace_line(&old, &new, 2), Some(2));
}
}