crates/gunnar-server/src/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())
.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"
);
}
}