gunnar_server/

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));
    }
}