gunnar_server/

blame.rs

//! **`gunnar blame` — who wrote each line, walked backwards.**
//!
//! `verify --line <path>:<n>` already answers link 1 for ONE line: *which
//! commit put this line here* (see [`crate::verify`]). Blame is that answer for
//! **every** line of a file at a revision.
//!
//! # It reuses link 1's writers, it does not twin them (one implementation)
//!
//! The single-line walk in `verify` rests on three things: the tree/blob reader
//! [`crate::verify::blob_at`], the parent reader [`crate::verify::parents`], and
//! the diff engine [`crate::diff`] (`trace_line` there is `diff_ops` there). A
//! whole-file blame rests on the **same three**. What is genuinely new is the
//! shape of the walk: `verify` follows one line down one lineage, and blame
//! follows a *set* of lines, each down the first parent that still holds it.
//!
//! That set-walk is not a second copy of link 1 — it is link 1 done once for a
//! whole file instead of once per line. Per-line iteration would re-diff the
//! file at every history step for every line (`O(lines · depth)` diffs); the
//! set-walk diffs each revision once (`O(depth)` diffs) and moves every line
//! that survived a revision back through the same script. Both attribute a line
//! to the first parent that contains it and, failing that, to the commit in
//! hand — so a line blamed by this module is the line `verify --line` would
//! blame, by construction.
//!
//! # The follow-up this is not
//!
//! A blame *cache* — precomputed per-line attribution kept beside the repo so a
//! blame is a lookup rather than a walk — is a separate, larger piece of work
//! (it has to be invalidated on every push and stored somewhere). This walks
//! live, bounded by [`WALK_BUDGET`], which is the honest first version.

use std::collections::HashMap;

use anyhow::{Context, Result};
use gunnar_store::git_storage_trait::GitServe;

use crate::stores::ServerStores;

/// How many history steps a blame will take before it refuses.
///
/// A bound rather than a promise, exactly as [`crate::verify::BLAME_BUDGET`] is
/// for one line — but this one counts *commits visited*, not lines, because a
/// whole-file blame legitimately steps once per revision that touched the file.
/// A file with more than a million revisions in its past is a question this
/// command refuses rather than answers in an hour.
pub const WALK_BUDGET: usize = 1 << 20;

/// One line's attribution.
#[derive(Debug, Clone)]
pub struct Blamed {
    /// The commit that last touched this line.
    pub commit: gix_hash::ObjectId,
    /// The author of that commit, lossily decoded — git does not promise a name
    /// is UTF-8 and this is a display string, so the conversion is lossy at this
    /// one boundary.
    pub author: String,
    /// The line's bytes at the revision blamed, without its trailing newline.
    pub line: Vec<u8>,
}

/// **Blame every line of `path` at `tip`.**
///
/// The testable core: it needs only a [`GitServe`] and the tip commit, so a
/// test can build a commit graph whose oids it chose and assert the exact
/// commit each line is attributed to — not merely that an answer came back.
///
/// The returned vector has one entry per line of the file at `tip`, in file
/// order.
pub fn blame_file(
    git: &dyn GitServe,
    hash: gix_hash::Kind,
    tip: gix_hash::ObjectId,
    path: &str,
) -> Result<Vec<Blamed>> {
    // The file at the tip is the set of lines that must be attributed.
    let (_, tip_blob) = crate::verify::blob_at(git, hash, tip, path)?
        .with_context(|| format!("{path} is not a file at {tip}"))?;
    let tip_lines: Vec<Vec<u8>> = crate::diff::split_lines(&tip_blob)
        .into_iter()
        .map(<[u8]>::to_vec)
        .collect();
    let n = tip_lines.len();

    // `assigned[i]` is the commit that last touched original line `i`.
    let mut assigned: Vec<Option<gix_hash::ObjectId>> = vec![None; n];

    // The frontier: `(commit, care)` where `care` maps a line index *in that
    // commit's version of the file* to the original line index it descends to.
    //
    // A line is passed to the FIRST parent that still holds it and to no other,
    // so each original line follows exactly one lineage — a merge never splits
    // it in two — and the walk cannot fan out exponentially over a diamond.
    let mut frontier: Vec<(gix_hash::ObjectId, Vec<(usize, usize)>)> =
        vec![(tip, (0..n).map(|i| (i, i)).collect())];

    let mut steps = 0usize;
    while let Some((commit, care)) = frontier.pop() {
        if care.is_empty() {
            continue;
        }
        steps += 1;
        anyhow::ensure!(
            steps <= WALK_BUDGET,
            "blame walked {WALK_BUDGET} history steps without finishing; that is a bound, not \
             an answer"
        );

        let (_, blob) = crate::verify::blob_at(git, hash, commit, path)?
            .with_context(|| format!("{path} left {commit} in the middle of a blame walk"))?;
        let lines = crate::diff::split_lines(&blob);

        // `handed[c]` — this care entry has been passed to some parent.
        let mut handed = vec![false; care.len()];
        let mut handoffs: Vec<(gix_hash::ObjectId, Vec<(usize, usize)>)> = Vec::new();

        for parent in crate::verify::parents(git, hash, commit)? {
            let Some((_, parent_blob)) = crate::verify::blob_at(git, hash, parent, path)? else {
                // This parent does not carry the file; the line cannot have come
                // through it. `verify`'s link-1 skips it the same way.
                continue;
            };
            let mut moved: Vec<(usize, usize)> = Vec::new();
            if parent_blob == blob {
                // Identical blobs: every still-unhanded line survives at the
                // same index, and diffing them would be work for a known answer.
                for (c, &(line_idx, orig)) in care.iter().enumerate() {
                    if !handed[c] {
                        moved.push((line_idx, orig));
                        handed[c] = true;
                    }
                }
            } else {
                let older = crate::diff::split_lines(&parent_blob);
                // Where each surviving line of `commit` sat in `parent`.
                let mut new_to_old: HashMap<usize, usize> = HashMap::new();
                for op in crate::diff::diff_ops(&older, &lines) {
                    if let crate::diff::Op::Equal { old, new, count } = op {
                        for k in 0..count {
                            new_to_old.insert(new + k, old + k);
                        }
                    }
                }
                for (c, &(line_idx, orig)) in care.iter().enumerate() {
                    if handed[c] {
                        continue;
                    }
                    if let Some(&old) = new_to_old.get(&line_idx) {
                        moved.push((old, orig));
                        handed[c] = true;
                    }
                }
            }
            if !moved.is_empty() {
                handoffs.push((parent, moved));
            }
        }

        // A line no parent held was written here. `assigned[orig].is_none()`
        // guards the one case a diamond could reach the same commit twice: the
        // first attribution wins, and it is the same commit either way.
        for (c, &(_, orig)) in care.iter().enumerate() {
            if !handed[c] && assigned[orig].is_none() {
                assigned[orig] = Some(commit);
            }
        }
        frontier.extend(handoffs);
    }

    // Turn the per-line commit into the printable row, reading each author once.
    let mut author_of: HashMap<gix_hash::ObjectId, String> = HashMap::new();
    let mut out = Vec::with_capacity(n);
    for (i, line) in tip_lines.into_iter().enumerate() {
        let commit = assigned[i]
            .with_context(|| format!("line {} was never attributed to a commit", i + 1))?;
        let author = match author_of.get(&commit) {
            Some(name) => name.clone(),
            None => {
                let name = author_name(git, hash, commit)?;
                author_of.insert(commit, name.clone());
                name
            }
        };
        out.push(Blamed {
            commit,
            author,
            line,
        });
    }
    Ok(out)
}

/// The author name of `commit`, lossily decoded for display.
fn author_name(
    git: &dyn GitServe,
    hash: gix_hash::Kind,
    commit: gix_hash::ObjectId,
) -> Result<String> {
    let (_, bytes) = git
        .read(commit.as_bytes())?
        .with_context(|| format!("commit {commit} is not in this repository"))?;
    let decoded = gunnar_store::object::commit(&bytes, hash)
        .with_context(|| format!("decoding commit {commit}"))?;
    Ok(String::from_utf8_lossy(&decoded.author.name).into_owned())
}

/// **Blame `path` at `rev` in `repo`**, resolving the revision the way
/// `verify` and `Refs.Log` do so `HEAD`, a branch and a hex oid all mean here
/// what they mean there.
pub fn blame(
    stores: &ServerStores,
    plane: &crate::control_plane::CoreControlPlane,
    repo: &gunnar_proto::RepoPath,
    rev: &str,
    path: &str,
) -> Result<Vec<Blamed>> {
    use gunnar_grpc::ControlPlane as _;

    let repo_ref = gunnar_core::RepoRef::new(&repo.namespace, &repo.repo)
        .context("the repository path is not a legal one")?;
    let entry = stores
        .catalog()
        .get(&repo_ref)?
        .with_context(|| format!("no such repository: {repo_ref}"))?;
    let store = stores.repo_store(&entry)?;
    let git = store.serve();
    let hash = store.hash_kind();

    let commits = plane
        .log(repo, rev, 1, "")
        .map_err(|err| anyhow::anyhow!("{err}"))?;
    let head = commits
        .first()
        .with_context(|| format!("{rev} names no commit in {repo_ref}"))?;
    let tip = gix_hash::ObjectId::from_hex(head.oid.as_bytes())
        .map_err(gix_error::Error::from)
        .with_context(|| format!("{} is not an object id", head.oid))?;

    blame_file(git, hash, tip, path)
}

/// [`blame`] over a data root, opening the stores itself — the CLI verb's entry.
pub fn blame_at(
    data_root: &std::path::Path,
    repo: &gunnar_proto::RepoPath,
    rev: &str,
    path: &str,
) -> Result<Vec<Blamed>> {
    let stores = std::sync::Arc::new(ServerStores::open(data_root)?);
    let plane = crate::control_plane::CoreControlPlane::new(std::sync::Arc::clone(&stores));
    blame(&stores, &plane, repo, rev, path)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::testgit::{Repo, TREE_MODE_BLOB};

    /// **Commit A writes lines 1-3; commit B rewrites line 2. Blame names B for
    /// line 2 and A for lines 1 and 3 — by their exact oids.**
    ///
    /// The oids are the ones the test *chose* for each commit, so this asserts
    /// the attribution and not merely that a vector came back. The red it is
    /// written against is the naive blame that answers "the tip" for every line:
    /// that would put commit B on lines 1 and 3, and the two `assert_eq!`s on
    /// `commit_a` below would fail. Proven red on 2026-08-31 by stubbing
    /// `blame_file` to return `tip` for every line — lines 1 and 3 came back as
    /// B and the test failed exactly there.
    #[test]
    fn blame_names_the_commit_that_wrote_each_line_not_the_tip() {
        let repo = Repo::new();
        let blob_a = repo.blob(b"line one\nline two\nline three\n");
        let tree_a = repo.tree(&[(TREE_MODE_BLOB, "src.txt", blob_a)]);
        let commit_a = repo.commit(tree_a, &[], "Ada", "commit A: write the file");

        let blob_b = repo.blob(b"line one\nLINE TWO CHANGED\nline three\n");
        let tree_b = repo.tree(&[(TREE_MODE_BLOB, "src.txt", blob_b)]);
        let commit_b = repo.commit(tree_b, &[commit_a], "Bo", "commit B: rewrite line 2");

        let blamed =
            blame_file(repo.serve(), repo.hash_kind(), commit_b, "src.txt").expect("blame");

        assert_eq!(blamed.len(), 3, "the file at the tip has three lines");
        assert_eq!(
            blamed[0].commit, commit_a,
            "line 1 was untouched since A and must be attributed to A, not the tip"
        );
        assert_eq!(
            blamed[1].commit, commit_b,
            "line 2 was rewritten by B and must be attributed to B"
        );
        assert_eq!(
            blamed[2].commit, commit_a,
            "line 3 was untouched since A and must be attributed to A, not the tip"
        );
        // The author rode along with the commit.
        assert_eq!(blamed[0].author, "Ada");
        assert_eq!(blamed[1].author, "Bo");
        assert_eq!(blamed[1].line, b"LINE TWO CHANGED");
    }

    /// An inserted line is attributed to the commit that inserted it, and the
    /// lines that merely shifted down keep their original author. This is the
    /// case a blame that keyed on line *number* rather than line *content* would
    /// get wrong — it would blame the whole tail on B.
    #[test]
    fn an_inserted_line_does_not_reblame_the_lines_it_pushed_down() {
        let repo = Repo::new();
        let blob_a = repo.blob(b"alpha\nbeta\ngamma\n");
        let tree_a = repo.tree(&[(TREE_MODE_BLOB, "f", blob_a)]);
        let commit_a = repo.commit(tree_a, &[], "Ada", "A");

        let blob_b = repo.blob(b"alpha\nINSERTED\nbeta\ngamma\n");
        let tree_b = repo.tree(&[(TREE_MODE_BLOB, "f", blob_b)]);
        let commit_b = repo.commit(tree_b, &[commit_a], "Bo", "B");

        let blamed = blame_file(repo.serve(), repo.hash_kind(), commit_b, "f").expect("blame");
        let names: Vec<_> = blamed.iter().map(|b| b.commit).collect();
        assert_eq!(
            names,
            vec![commit_a, commit_b, commit_a, commit_a],
            "only the inserted line is B's; alpha/beta/gamma stay A's"
        );
    }
}