//! One file's annotation, as `zit annotate [--partial]` attributes it: the
//! version chain over the target's ancestry (following renames unless told
//! not to), each line credited to the check-in that introduced it. The CLI
//! renders the answer as text and the daemon's `annotate` as JSON; both call
//! `annotate` here, so the attribution cannot differ between them. What the
//! CLI prints on a refusal is the caller's: this returns which refusal.
const std = @import("std");
const artifact = @import("../artifact.zig");
const logstore = @import("../logstore.zig");
const repostate = @import("../repostate.zig");
const repoview = @import("../repoview.zig");
const repocache = @import("../repocache.zig");
const thinned = @import("../thinned.zig");
const merge3 = @import("../merge3.zig");
const engine = @import("../annotate.zig");
const blamecache = @import("../blamecache.zig");
const Repository = @import("../repository.zig").Repository;
const filelog = @import("filelog.zig");
const NameId = filelog.NameId;
const NamedRid = filelog.NamedRid;
const NameTable = filelog.NameTable;
/// Which of PATH's ancestors actually CHANGED it, read from the derived
/// cache's record body in one sequential pass. Fossil answers this
/// from its mlink table; the equivalent here is the changed-file list
/// every record carries. A record's list is a pure function of
/// content-addressed artifacts — the diff of a manifest against its primary
/// parent over their shared baseline — so even a cache older than the log is
/// CORRECT for the check-ins it covers; coverage, not freshness, is the only
/// question, and `covered` answers it. Null when there is no usable cache:
/// the caller then reads a manifest per ancestor, exactly as before. Annotate
/// asks over PATH's ancestry; grep asks over the whole store.
pub const AnnotateTouched = struct {
/// Check-ins with a record whose file facts are known.
covered: std.AutoHashMapUnmanaged(repostate.Rid, void) = .empty,
/// The rows of covered records for the names asked about, by check-in
/// and name.
touched: std.AutoHashMapUnmanaged(NamedRid, TouchedRow) = .empty,
/// The names whose rows were kept. A name outside it (an old name a
/// rename at an uncovered check-in reached) has no rows here even where
/// the record changed it, so it must be read from the manifest.
names: std.AutoHashMapUnmanaged(NameId, void) = .empty,
/// Whether the record body answers `name` at check-in `rid`: absence of
/// a row then means "unchanged against the primary parent".
pub fn answers(self: *const AnnotateTouched, rid: repostate.Rid, name: NameId) bool {
return self.covered.contains(rid) and self.names.contains(name);
}
pub fn deinit(self: *AnnotateTouched, gpa: std.mem.Allocator) void {
self.covered.deinit(gpa);
self.names.deinit(gpa);
var it = self.touched.valueIterator();
while (it.next()) |row| if (row.hash) |b| gpa.free(b);
self.touched.deinit(gpa);
}
};
/// One record row: the hash the check-in gives the file (null when it
/// deletes it) and, on a rename, the name it renamed the file from.
const TouchedRow = struct { hash: ?[]u8, prior: ?NameId };
/// `AnnotateTouched` for `path` and, when `follow`, every name a rename
/// chain reaches from it: the record body's rename rows are read first and
/// closed over from `path`, so the rows of every older name are kept in the
/// same pass. The closure is by name, which may keep a few rows no walk asks
/// for; the walk asks by check-in and name, so an unrelated file that once
/// held one of these names is never mistaken for this one.
pub fn annotateTouchedFromCache(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
names: *NameTable,
path: []const u8,
follow: bool,
) ?AnnotateTouched {
var raw = repocache.loadForExtension(io, repo.root_dir) orelse return null;
defer raw.deinit();
var wanted: std.StringHashMapUnmanaged(void) = .empty;
defer wanted.deinit(gpa);
wanted.put(gpa, path, {}) catch return null;
if (follow) {
var edges: std.ArrayListUnmanaged([2][]const u8) = .empty;
defer edges.deinit(gpa);
var it = repoview.RecordIter.init(raw.body);
while (true) {
var rec = (it.next(gpa) catch break) orelse break;
defer rec.deinit(gpa);
if (rec.kind != .manifest or !rec.files_known) continue;
for (rec.files.items) |f| {
if (f.prior) |old| edges.append(gpa, .{ f.path, old }) catch return null;
}
}
// Each pass adds at least one name or ends, and there are no more
// names than edges.
var grew = true;
while (grew) {
grew = false;
for (edges.items) |e| {
if (wanted.contains(e[0]) and !wanted.contains(e[1])) {
wanted.put(gpa, e[1], {}) catch return null;
grew = true;
}
}
}
}
var out: AnnotateTouched = .{};
errdefer out.deinit(gpa);
var wanted_it = wanted.keyIterator();
while (wanted_it.next()) |w| {
const id = names.intern(gpa, w.*) catch return null;
out.names.put(gpa, id, {}) catch return null;
}
var it = repoview.RecordIter.init(raw.body);
while (true) {
var rec = (it.next(gpa) catch {
// A short or undecodable tail: keep what decoded — every kept
// record is still individually correct — and let the uncovered
// rids take the manifest fallback.
break;
}) orelse break;
defer rec.deinit(gpa);
if (rec.kind != .manifest or !rec.files_known) continue;
const rid = repo.lookup(rec.hash) orelse continue;
out.covered.put(gpa, rid, {}) catch return null;
for (rec.files.items) |f| {
if (!wanted.contains(f.path)) continue;
const name = names.intern(gpa, f.path) catch return null;
const prior: ?NameId = if (follow and f.prior != null) (names.intern(gpa, f.prior.?) catch return null) else null;
const hash: ?[]u8 = if (f.hash) |h| (gpa.dupe(u8, h) catch return null) else null;
out.touched.put(gpa, .{ .rid = rid, .name = name }, .{ .hash = hash, .prior = prior }) catch {
if (hash) |h| gpa.free(h);
return null;
};
}
}
return out;
}
/// The narrow read-failure set the annotate content path collapses the
/// `Repository` file/blob errors into, so the renderer switches once.
pub const ReadError = error{ OutOfMemory, Storage, Corrupt };
/// PATH's effective content in the check-in `rid` (artifact §8 via
/// `Repository.fileAt` + `blob`), owned by the caller on `gpa`, or null when
/// PATH is absent there (never added, or a delta delete). The F card is freed
/// before returning; only the absent blob's name, when there is one, goes on
/// `arena`.
fn annotateContentAt(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
cache: *logstore.PlaintextCache,
memo: *?*Repository.BaselineMemo,
rid: repostate.Rid,
path: []const u8,
absent_hash: *?[]const u8,
) ReadError!?[]u8 {
const maybe_card = repo.fileAtMemo(gpa, rid, path, memo, cache) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead => error.Storage,
// NotARepo/Corrupt/NotManifest/BaselineUnresolvable all
// mean this reachable check-in cannot be reconstructed — corrupt.
else => error.Corrupt,
};
const card = maybe_card orelse return null;
defer Repository.freeFileCard(gpa, card);
// The effective-set iterator suppresses delete markers, so a returned card
// always carries a hash (§4.7.6).
const content = try annotateContentByHash(gpa, repo, cache, card.hash.?);
// PATH is in this check-in but its blob is not here: say which blob, so the
// caller can tell an absence from "not added yet".
if (content == null) absent_hash.* = try arena.dupe(u8, card.hash.?);
return content;
}
/// The blob `hash` names, owned by the caller on `gpa`, or null when the
/// store lacks it. Through the plaintext memo: adjacent versions of PATH are
/// deltas over shared bases, and without the memo every version re-walks its
/// whole chain -- on SQLite's shell.c.in that walk, not the diff, was most of
/// the remaining time once the diff core went O(ND).
fn annotateContentByHash(
gpa: std.mem.Allocator,
repo: *Repository,
cache: *logstore.PlaintextCache,
hash: []const u8,
) ReadError!?[]u8 {
return repo.blobCached(gpa, hash, cache) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead, error.ImportPending => error.Storage,
error.NotARepo, error.Corrupt => error.Corrupt,
};
}
/// One check-in in PATH's ancestry, in the processing order the repostate
/// topological linearization fixes (parent before child; B-annotate-5). `hash`
/// borrows the view's identity space (stable for the view's lifetime).
const AnnotateEntry = struct {
rid: repostate.Rid,
mtime: repostate.Mtime,
hash: []const u8,
};
pub const Options = struct {
/// Fossil's `-n N`: walk back over at most N versions of the file (the
/// check-ins that changed it), newest first in the linearization, so the
/// cost follows N rather than the history. Like Fossil, at least three
/// are walked, and 0 means its default count of 30. A line the oldest
/// version reached already carried, when older versions exist, has no
/// origin the walk can name: its `Origin.beyond` is set.
limit: ?usize = null,
/// Fill `Annotation.versions` even without a limit (`-l`). Off, and
/// without a limit, no version is told from an unchanged check-in.
list_versions: bool = false,
follow: bool = true,
/// A version purged or shunned is a gap the annotation reads through,
/// rather than a refusal; lines claimed across it are approximate.
partial: bool = false,
};
/// How a blob the store names but lacks sits against its cone: `elided`
/// when the cone or horizon leaves it out, `horizon` when the store has a
/// horizon at all. Null from the hook when the store has no cone.
pub const Elision = struct { elided: bool, horizon: bool };
/// The cone classifier lives with the sync machinery; the caller supplies it.
pub const ElisionHook = struct {
ctx: ?*anyopaque = null,
of: *const fn (ctx: ?*anyopaque, gpa: std.mem.Allocator, hash: []const u8) ?Elision,
};
/// Why there is no annotation. Each names what the CLI's message needs.
pub const Refusal = union(enum) {
/// PATH is not in the target check-in.
not_tracked,
/// The target's content is binary: provenance is undefined over it.
binary,
/// A version's content was purged or shunned, and `partial` was not
/// asked (or it is the target itself). Exit 8.
absent: struct { why: enum { purged, shunned }, name: []const u8, rid: repostate.Rid },
/// A version's content is gone for no recorded reason. Exit 1.
missing: struct { name: []const u8, rid: repostate.Rid },
/// The cone or horizon elides `name`'s blob `hash`. Exit 8.
elided: struct { name: []const u8, hash: []const u8 },
/// A rename crosses this store's horizon: `name` (the old name) lies
/// below it, and blob `hash` is the renamed file's. Exit 8.
elided_below: struct { name: []const u8, hash: []const u8 },
};
pub const Origin = struct {
rid: repostate.Rid,
/// The origin's event time, milliseconds since the epoch.
mtime: repostate.Mtime,
/// Claimed across a purged or shunned version (`--partial`'s `~`).
approx: bool,
/// Older than the versions `limit` let the walk reach: `rid` is only
/// where the walk stopped, and Fossil prints no attribution for it.
beyond: bool = false,
/// The origin's committing user (`userOf`), null when its manifest
/// carries none or the origin is `beyond`.
user: ?[]const u8 = null,
};
/// Versions attributed by diffing them against their parents, process-wide:
/// the evidence tests use to show a cached ancestor cut the walk short.
pub var versions_walked: std.atomic.Value(usize) = .init(0);
pub const Annotation = struct {
/// The target's content; `lines` index into it.
target: []const u8,
lines: []const merge3.Line,
/// One per line.
origins: []const Origin,
/// Some version was read through as a gap.
any_gap: bool,
/// The versions of the file walked, newest first, when a limit or
/// `list_versions` asked for them.
versions: []const repostate.Rid,
/// Line `i`'s bytes, its line break included.
pub fn text(self: *const Annotation, i: usize) []const u8 {
return merge3.lineBytes(self.target, self.lines[i]);
}
};
pub const Result = union(enum) {
ok: Annotation,
refused: Refusal,
};
/// Annotations the file index answered without the full walk, process-wide:
/// the evidence a differential test uses to show the indexed walk ran.
pub var indexed_walks: std.atomic.Value(usize) = .init(0);
/// Annotate `path` as of check-in `cur`. Everything returned lives on
/// `arena`; `gpa` carries the repository's own reads.
///
/// With the file index (`filelog.loadPathIndex`, the one `log PATH` reads),
/// the file's versions are found from its change sets and only they are
/// read, so the cost follows the versions walked; whatever the index cannot
/// settle exactly is answered by the walk over the whole linearized
/// ancestry, which this always matches byte for byte.
pub fn annotate(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
io: std.Io,
repo: *Repository,
path: []const u8,
cur: repostate.Rid,
opts: Options,
hook: ElisionHook,
index: ?*filelog.PathIndex,
) ReadError!Result {
if (index) |ix| if (try annotateIndexed(gpa, arena, io, repo, ix, path, cur, opts, hook)) |r| {
_ = indexed_walks.fetchAdd(1, .monotonic);
return r;
};
const all_rids = try repo.ancestryLinearized(gpa, cur);
defer gpa.free(all_rids);
return annotateWalk(gpa, arena, io, repo, path, cur, all_rids, opts, hook);
}
/// The walk over `cur`'s whole ancestry, `all_rids`
/// (`Repository.ancestryLinearized`: oldest first, `cur` last).
///
/// Following renames, a node is a check-in under a NAME: below the check-in
/// whose card renamed the file, its parents are read under the old name, so
/// lines from before the rename keep the check-ins that wrote them. The same
/// check-in can be a node under two names (a rename on a branch merged back
/// reaches the fork point under both); a parent that lacks the old name
/// holds nothing under it and so attributes nothing, which is Fossil's
/// "treat as new" on that side.
///
/// With `partial`, a version purged or shunned is a gap rather than a
/// refusal: its children read through it to its surviving parents, and a
/// line a child claims across a gap is marked approximate, since the absent
/// version may have been the one that wrote it.
fn annotateWalk(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
io: std.Io,
repo: *Repository,
path: []const u8,
cur: repostate.Rid,
all_rids: []const repostate.Rid,
opts: Options,
hook: ElisionHook,
) ReadError!Result {
const follow = opts.follow;
var plaintext: logstore.PlaintextCache = .{};
defer plaintext.deinit(gpa);
// Consecutive versions of PATH sit in delta check-ins over one baseline;
// the memo parses that baseline once instead of once per version.
var baseline: ?*Repository.BaselineMemo = null;
defer if (baseline) |b| b.deinit(gpa);
var names = NameTable.init(gpa);
defer names.deinit(gpa);
const path_name = try names.intern(gpa, path);
// Fossil's annotate_file: at least three versions, and 0 for its 30.
const limit: ?usize = if (opts.limit) |n| (if (n == 0) 30 else @max(n, 3)) else null;
var entries: std.ArrayList(AnnotateEntry) = .empty;
for (all_rids) |rid| {
try entries.append(arena, .{
.rid = rid,
.mtime = repo.state().mtimeOf(rid) orelse 0,
.hash = repo.hashOf(rid),
});
}
// rid → position in processing order, so parent links resolve to indices.
var index_of: std.AutoHashMapUnmanaged(repostate.Rid, u32) = .empty;
for (entries.items, 0..) |e, i| try index_of.put(arena, e.rid, @intCast(i));
// Which ancestors changed PATH, from the cache's record body.
// Reading a manifest per ancestor made annotate proportional to the
// store: SQLite's history is ~36k check-ins of which ~200 touch a given
// file, and fossil (whose mlink table is the same precomputation) answers
// in milliseconds where this took minutes. With the set in hand, an
// ancestor that did not change PATH inherits its primary parent's
// content outright — the record's diff IS against the primary parent, so
// "not listed" means "byte-equal there" — a changed ancestor reads the blob
// the record names, and only an uncovered one opens its manifest.
var touched_opt = annotateTouchedFromCache(gpa, io, repo, &names, path, follow);
defer if (touched_opt) |*t| t.deinit(gpa);
// The names each position is read under, from the target down: a
// child's name passes to its parents, switched to the old name at the
// check-in that renamed the file. Children follow their parents in the
// linearization, so walking it backwards meets every child of a
// position before the position itself.
const names_at = try arena.alloc(std.ArrayListUnmanaged(NameId), entries.items.len);
for (names_at) |*l| l.* = .empty;
var parent_name_of: std.AutoHashMapUnmanaged(NamedRid, NameId) = .empty;
// Nodes a rename reached: an absence there is the old name's, and if the
// store elided its content the honest answer is to say so.
var crossed: std.AutoHashMapUnmanaged(NamedRid, void) = .empty;
const cur_pos = index_of.get(cur).?; // cur is self-inclusive in its ancestry
try names_at[cur_pos].append(arena, path_name);
// The versions met so far, newest first. With a limit, the walk ends at
// the position of the last one it may read: everything below it is
// never opened, so the window is the linearization's tail from there.
var versions: std.ArrayList(repostate.Rid) = .empty;
var window_start: usize = 0;
// A parent the store does not hold makes its child a root of the walk,
// crediting the child with lines the parent wrote. Filling the parent
// in later changes that answer and nothing the cache's fingerprint
// sees, so such an answer is never cached; and since a cached version
// stands for its whole ancestry, no entry below it can hide one.
var any_unheld_parent = false;
var k = entries.items.len;
while (k > 0) {
if (limit) |n| if (versions.items.len >= n) {
window_start = k;
break;
};
k -= 1;
const rid = entries.items[k].rid;
for (names_at[k].items) |n| {
const prior: ?NameId = if (!follow) null else blk: {
if (touched_opt) |*t| if (t.answers(rid, n)) {
// A rename is always a row, so no row means no rename.
break :blk if (t.touched.get(.{ .rid = rid, .name = n })) |row| row.prior else null;
};
const card = (repo.fileAtMemo(gpa, rid, names.get(n), &baseline, &plaintext) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead => error.Storage,
else => error.Corrupt,
}) orelse break :blk null;
defer Repository.freeFileCard(gpa, card);
break :blk if (card.old_name) |old| try names.intern(gpa, old) else null;
};
const pn = prior orelse n;
try parent_name_of.put(arena, .{ .rid = rid, .name = n }, pn);
if ((limit != null or opts.list_versions) and try changedHere(gpa, repo, &names, if (touched_opt) |*t| t else null, rid, n, pn, &baseline, &plaintext)) {
try versions.append(arena, rid);
}
var it = repo.state().parentsOf(rid);
while (it.next()) |p| {
// A parent the store does not hold, across a rename, is
// history below its horizon: the old name's lines cannot be
// read, and attributing them to the rename would be wrong.
const held = repo.state().mtimeOf(p) != null;
const in_ancestry = index_of.get(p);
any_unheld_parent = any_unheld_parent or !held or in_ancestry == null;
if (prior != null and (!held or in_ancestry == null)) {
if (try elidedBelow(gpa, arena, repo, hook, rid, names.get(n))) |hash|
return .{ .refused = .{ .elided_below = .{ .name = try arena.dupe(u8, names.get(pn)), .hash = hash } } };
}
const pi = in_ancestry orelse continue;
if (std.mem.indexOfScalar(NameId, names_at[pi].items, pn) == null) {
try names_at[pi].append(arena, pn);
}
if (prior != null) try crossed.put(arena, .{ .rid = p, .name = pn }, {});
}
}
}
// One engine node per (position, name), in position order so parents
// still precede children.
var node_of: std.AutoHashMapUnmanaged(NamedRid, u32) = .empty;
var node_keys: std.ArrayList(NamedRid) = .empty;
var node_pos: std.ArrayList(u32) = .empty;
for (names_at[window_start..], window_start..) |l, pos| {
for (l.items) |n| {
const key: NamedRid = .{ .rid = entries.items[pos].rid, .name = n };
try node_of.put(arena, key, @intCast(node_keys.items.len));
try node_keys.append(arena, key);
try node_pos.append(arena, @intCast(pos));
}
}
const cur_index = node_of.get(.{ .rid = cur, .name = path_name }).?;
// Provenance is undefined over binary content (B-annotate-9, the merge3
// NUL predicate). A binary target is still walked for the refusals the
// history owes first, but its versions are not diffed: binary "lines"
// can make the line diff quadratic. A target that cannot be read here
// is read again in the walk, which reports why.
const target_binary = blk: {
var absent: ?[]const u8 = null;
const bytes = (annotateContentAt(gpa, arena, repo, &plaintext, &baseline, cur, path, &absent) catch null) orelse break :blk false;
defer gpa.free(bytes);
// The memo's default budget is sized for a store-wide sweep; here it
// filled with old versions of this one file, tens of megabytes held
// per request. A few dozen of the file's own size keeps the hot
// bases of its delta chains.
plaintext.max_bytes = @min(plaintext.max_bytes, @max(4 << 20, 16 * bytes.len));
break :blk merge3.isBinary(bytes);
};
// The blame cache answers only what it was filled with: a clean,
// unlimited walk following renames. A limit, `partial` or a binary
// target neither reads nor writes it.
const fp: ?u32 = if (opts.limit == null and !opts.partial and follow and !target_binary) cacheFingerprint(gpa, io, repo) else null;
var cached_file: ?blamecache.Mapped = if (fp) |f| blamecache.open(gpa, io, repo.root_dir, path, f) else null;
defer if (cached_file) |*m| m.deinit(gpa);
// Logins the cache already holds, by origin.
var cached_users: std.AutoHashMapUnmanaged(repostate.Rid, ?[]const u8) = .empty;
// A file that failed to answer is not carried into the next write.
var cache_failed = false;
var plan: ?CutPlan = null;
defer if (plan) |*p| p.deinit(gpa);
if (cached_file) |*m| {
plan = try planFromCache(gpa, arena, repo, &plaintext, &baseline, &m.file, .{
.path = path,
.path_name = path_name,
.entries = entries.items,
.index_of = &index_of,
.node_keys = node_keys.items,
.node_pos = node_pos.items,
.node_of = &node_of,
.parent_name_of = &parent_name_of,
.target = cur_index,
}, &cached_users, &cache_failed);
}
// Each node's version is dropped once the last node that reads it as a
// parent is attributed, so what is live is the frontier of the walk, not
// the history behind it. The target is kept for the answer. A node the
// cut skips reads nothing, and neither does a seeded one.
const last_use = try arena.alloc(u32, node_keys.items.len);
for (node_keys.items, 0..) |key, i| {
last_use[i] = @intCast(i);
if (plan) |p| if (p.roles[i] != .walk) continue;
const pn = parent_name_of.get(key).?;
var it = repo.state().parentsOf(key.rid);
while (it.next()) |p| {
const idx = node_of.get(.{ .rid = p, .name = pn }) orelse continue;
last_use[idx] = @max(last_use[idx], @as(u32, @intCast(i)));
}
}
last_use[cur_index] = std.math.maxInt(u32);
var walk = try engine.Walk.init(gpa, node_keys.items.len, true);
defer walk.deinit();
// §3.2 primary/merge parents of each node, as the engine was given them.
const links = try arena.alloc(struct { primary: ?u32, merges: []const u32 }, node_keys.items.len);
// Whether each node holds content: the walk's own record, except for a
// binary target's versions, which never reach it.
const present = try arena.alloc(bool, node_keys.items.len);
@memset(present, false);
// Whether this store carries a cone or horizon, asked once and only if
// some version's content turns out to be absent.
var has_cone: ?bool = null;
// partial: the blob of each node absent by policy (null otherwise), and
// whether a node's parents were read through such a gap.
const gap = try arena.alloc(?[]const u8, node_keys.items.len);
@memset(gap, null);
const bridged = try arena.alloc(bool, node_keys.items.len);
@memset(bridged, false);
// Whether a node has a parent below the window that holds the file: its
// lines may come from there, so the walk cannot name their origin.
const cut = try arena.alloc(bool, node_keys.items.len);
@memset(cut, false);
var any_gap = false;
// Some version read as the file's origin because the store's cone or
// horizon cut it: a true answer, but this store's, so never cached.
var any_cut_origin = false;
for (node_keys.items, 0..) |key, i| {
const ni: u32 = @intCast(i);
if (plan) |*p| switch (p.roles[i]) {
.skip => continue,
.seed => {
const sd = p.seeds[i].?;
p.seeds[i] = null; // the walk's now, even if it fails
present[i] = true;
links[i] = .{ .primary = null, .merges = &.{} };
try walk.seed(ni, sd.content, sd.origins);
if (last_use[i] == ni) walk.release(ni);
continue;
},
.walk => {},
};
// Bytes read for this node, freed here unless the walk takes them.
var owned: ?[]u8 = null;
defer if (owned) |o| gpa.free(o);
const pn = parent_name_of.get(key).?;
const primary_rid = repo.state().primaryParentOf(key.rid);
const primary: ?u32 = if (primary_rid) |pr| node_of.get(.{ .rid = pr, .name = pn }) else null;
const known: ?struct { c: ?[]const u8, hash: ?[]const u8 } = blk: {
const t = &(touched_opt orelse break :blk null);
if (!t.answers(key.rid, key.name)) break :blk null; // no record for it: open the manifest
if (t.touched.get(key)) |row| {
// Changed here: the record names the blob (a delete names none).
const h = row.hash orelse break :blk .{ .c = null, .hash = null };
owned = try annotateContentByHash(gpa, repo, &plaintext, h);
break :blk .{ .c = owned, .hash = h };
}
// Unchanged here, and a rename is always a row, so the primary
// parent holds the same content under the same name.
if (pn != key.name) break :blk null;
const pi = primary orelse break :blk null; // below the -n window
std.debug.assert(pi < i); // parents precede children
// Unchanged from a gap is the same absent blob. Under a binary
// target only presence matters, and the parent's bytes are gone.
const c: ?[]const u8 = if (!present[pi]) null else walk.content(pi) orelse "";
break :blk .{ .c = c, .hash = gap[pi] };
};
var absent_hash: ?[]const u8 = null;
const content: ?[]const u8 = if (known) |kn| blk: {
if (kn.c == null) absent_hash = kn.hash;
break :blk kn.c;
} else blk: {
owned = try annotateContentAt(gpa, arena, repo, &plaintext, &baseline, key.rid, names.get(key.name), &absent_hash);
break :blk owned;
};
if (content == null) if (absent_hash) |h| {
// PATH is in this version but its content is not here. Handing the
// engine a null would read as "not added yet" and credit every
// line it carried to the next version that holds content -- a
// wrong answer reported as a success. Refuse unless the absence
// is the store's own cut, below which the origin answers.
// partial bridges a gap anywhere but the annotated version.
const may_bridge = opts.partial and i != cur_index;
switch (try absentVerdict(gpa, io, repo, &has_cone, h, may_bridge)) {
.origin => any_cut_origin = true,
.gap => {
gap[i] = h;
any_gap = true;
},
.purged, .shunned, .missing => |v| {
const name = try arena.dupe(u8, names.get(key.name));
return .{ .refused = switch (v) {
.purged => .{ .absent = .{ .why = .purged, .name = name, .rid = key.rid } },
.shunned => .{ .absent = .{ .why = .shunned, .name = name, .rid = key.rid } },
else => .{ .missing = .{ .name = name, .rid = key.rid } },
} };
},
}
};
if (content == null and crossed.contains(key)) {
// Across a rename, an old version this store elides ends the
// annotation with the elision message rather than handing its
// lines to the check-in that renamed the file.
const hash: ?[]const u8 = if (known) |kn| kn.hash else null;
if (try elidedAt(gpa, arena, repo, hook, key.rid, names.get(key.name), hash)) |r| return .{ .refused = r };
}
if (window_start > 0) {
var below = repo.state().parentsOf(key.rid);
while (below.next()) |p| {
const pos = index_of.get(p) orelse continue;
if (pos >= window_start or cut[i]) continue;
if (try cardAt(gpa, repo, p, names.get(pn), &baseline, &plaintext)) |c| {
Repository.freeFileCard(gpa, c);
cut[i] = true;
}
}
}
var merges: std.ArrayList(u32) = .empty;
var it = repo.state().parentsOf(key.rid);
while (it.next()) |p| {
if (primary_rid != null and p == primary_rid.?) continue; // primary handled separately
const idx = node_of.get(.{ .rid = p, .name = pn }) orelse continue;
if (gap[idx] != null) {
// A gap node already reads through to its own surviving parents.
bridged[i] = true;
cut[i] = cut[i] or cut[idx];
if (links[idx].primary) |gp| try merges.append(arena, gp);
try merges.appendSlice(arena, links[idx].merges);
} else try merges.append(arena, idx);
}
var through: ?u32 = primary;
if (primary) |pi| if (gap[pi] != null) {
bridged[i] = true;
cut[i] = cut[i] or cut[pi];
through = links[pi].primary;
try merges.appendSlice(arena, links[pi].merges);
};
links[i] = .{ .primary = through, .merges = merges.items };
if (gap[i] != null) {
// Its children read through it to these, so they live as long.
if (through) |p| last_use[p] = @max(last_use[p], last_use[i]);
for (merges.items) |p| last_use[p] = @max(last_use[p], last_use[i]);
}
present[i] = content != null;
if (!target_binary) {
owned = null; // the walk's now, even if it fails
_ = versions_walked.fetchAdd(1, .monotonic);
try walk.add(ni, .{ .content = content, .primary = through, .merges = merges.items });
}
// Every holder of a version is this node or one of its parents.
if (last_use[i] == ni) walk.release(ni);
if (through) |p| if (last_use[p] == ni) walk.release(p);
for (merges.items) |p| if (last_use[p] == ni) walk.release(p);
}
if (!present[cur_index]) {
// Sparse-cone RFC section 6.4 / horizon draft section 5.5 -- a file
// the check-in names whose blob this store elides is an absence of a
// named class, not an untracked path.
if (try elidedAt(gpa, arena, repo, hook, cur, path, null)) |r| return .{ .refused = r };
return .{ .refused = .not_tracked };
}
if (target_binary) return .{ .refused = .binary };
const target_bytes = walk.content(cur_index).?;
// Refuse before answering anything.
if (merge3.isBinary(target_bytes)) return .{ .refused = .binary };
const target = try arena.dupe(u8, target_bytes);
const origin_nodes = walk.origins(cur_index).?;
const lines = try merge3.splitLines(arena, target);
std.debug.assert(lines.len == origin_nodes.len);
const origins = try arena.alloc(Origin, lines.len);
// Each origin's user, read once: from the cache when it held it.
var users: std.AutoHashMapUnmanaged(repostate.Rid, ?[]const u8) = .empty;
for (origin_nodes, origins) |node, *o| {
const e = entries.items[node_pos.items[node]];
o.* = .{ .rid = e.rid, .mtime = e.mtime, .approx = bridged[node] and !cut[node], .beyond = cut[node] };
if (o.beyond) continue;
const gop = try users.getOrPut(arena, e.rid);
if (!gop.found_existing) gop.value_ptr.* = cached_users.get(e.rid) orelse try userOfState(gpa, arena, repo, e.rid);
o.user = gop.value_ptr.*;
}
const seeded_target = if (plan) |p| p.roles[cur_index] == .seed else false;
// Each write rewrites the file whole, which the cap of
// `blamecache.max_entries` entries per file keeps bounded.
if (fp) |f| if (!any_gap and !any_cut_origin and !any_unheld_parent and !seeded_target) {
const prior: ?*const blamecache.File = if (cache_failed) null else if (cached_file) |*m| &m.file else null;
try fillCache(gpa, arena, io, repo, path, f, cur, origins, prior);
};
return .{ .ok = .{ .target = target, .lines = lines, .origins = origins, .any_gap = any_gap, .versions = versions.items } };
}
/// Past this many check-ins the index could not know, the indexed walk
/// leaves the answer to the full walk: each costs it a manifest read wherever
/// it sits in the ancestry, which on a store of tree manifests is every one.
const max_unknown_indexed = 64;
/// Card reads the indexed walk makes before it reads the record body
/// instead. A variable so a test can send every walk through the record
/// body.
pub var max_card_reads: usize = 256;
/// What makes the indexed walk give the answer back to the full walk.
const IndexedError = ReadError || error{Fallback};
/// `annotateWalk`'s answer, found from the file index, or null when the
/// index cannot settle it exactly and the full walk must.
fn annotateIndexed(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
io: std.Io,
repo: *Repository,
ix: *filelog.PathIndex,
path: []const u8,
cur: repostate.Rid,
opts: Options,
hook: ElisionHook,
) error{OutOfMemory}!?Result {
var walked: usize = 0;
const result = indexedWalk(gpa, arena, io, repo, ix, path, cur, opts, hook, &walked) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
// A read that failed is the full walk's to report too: it reads in
// its own order, and so names the failure it always has.
error.Storage, error.Corrupt, error.Fallback => null,
};
_ = versions_walked.fetchAdd(walked, .monotonic);
return result;
}
/// The full walk gives every check-in of the ancestry a node, and a node that
/// did not change the file shares its primary parent's version outright, so
/// its lines have their parent's origins. This walk gives nodes only to the
/// check-ins whose version must be read -- the ones the file index names as
/// changing the file, the ones it cannot answer for, phantoms, roots, ones
/// whose primary parent lies below a `-n` window, and cached ones -- and
/// links each to the node its parents' versions come from. The answer is
/// the full walk's because attribution is a function of the versions and
/// their links alone.
///
/// The ancestry itself is still visited, but only through the derived
/// parent links, with nothing read: that settles the name each check-in is
/// read under, what a cached entry cuts off, and the linearization, which is
/// made as `ancestryLinearized` makes it, only as far as a `-n` window
/// reaches. A check-in reached under two names, a rename above a parent the
/// store lacks, or a version whose content is gone go to the full walk,
/// which orders, refuses and bridges them as it always has.
fn indexedWalk(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
io: std.Io,
repo: *Repository,
ix: *filelog.PathIndex,
path: []const u8,
cur: repostate.Rid,
opts: Options,
hook: ElisionHook,
walked: *usize,
) IndexedError!Result {
if (ix.lost or ix.unknown.count() > max_unknown_indexed) return error.Fallback;
// What only the walk needs, a few words per check-in of the store,
// dropped when it ends; the answer lives on `arena`.
var scratch_state = std.heap.ArenaAllocator.init(gpa);
defer scratch_state.deinit();
const scratch = scratch_state.allocator();
const state = repo.state();
const follow = opts.follow;
const slots: usize = @as(usize, @intCast(state.ridCount())) + 1;
std.debug.assert(cur < slots);
var plaintext: logstore.PlaintextCache = .{};
defer plaintext.deinit(gpa);
var baseline: ?*Repository.BaselineMemo = null;
defer if (baseline) |b| b.deinit(gpa);
var names = NameTable.init(gpa);
defer names.deinit(gpa);
const path_name = try names.intern(gpa, path);
const limit: ?usize = if (opts.limit) |n| (if (n == 0) 30 else @max(n, 3)) else null;
var facts: IndexFacts = .{ .gpa = gpa, .arena = scratch, .ix = ix, .slots = slots };
var unknown = try std.DynamicBitSetUnmanaged.initEmpty(scratch, slots);
var unknown_it = ix.unknown.keyIterator();
while (unknown_it.next()) |r| {
if (r.* >= slots) return error.Fallback;
unknown.set(@intCast(r.*));
}
// The ancestry, each check-in under its one name (`name_of`, plus one;
// zero is unvisited), the name its parents are read under (`pn_of`), and
// how many of its children it holds (`pending`), for the linearization.
const name_of = try scratch.alloc(u32, slots);
@memset(name_of, 0);
const pn_of = try scratch.alloc(NameId, slots);
const pending = try scratch.alloc(u32, slots);
@memset(pending, 0);
var stack: std.ArrayList(NamedRid) = .empty;
try stack.append(scratch, .{ .rid = cur, .name = path_name });
// As in the full walk: a parent the store does not hold keeps the
// answer out of the cache.
var any_unheld_parent = false;
var ancestry_len: usize = 0;
while (stack.pop()) |e| {
const at: usize = @intCast(e.rid);
if (name_of[at] != 0) {
if (name_of[at] != e.name + 1) return error.Fallback;
continue;
}
name_of[at] = e.name + 1;
ancestry_len += 1;
const prior: ?NameId = if (!follow or state.mtimeOf(e.rid) == null) null else if (unknown.isSet(at)) blk: {
const card = (try cardAt(gpa, repo, e.rid, names.get(e.name), &baseline, &plaintext)) orelse break :blk null;
defer Repository.freeFileCard(gpa, card);
break :blk if (card.old_name) |old| try names.intern(gpa, old) else null;
} else if (try facts.changed(&names, e.rid, e.name)) blk: {
const old = (ix.priorOf(gpa, e.rid, names.get(e.name)) catch |err| return switch (err) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => error.Fallback,
}) orelse break :blk null;
break :blk try names.intern(gpa, old);
} else null;
const pn = prior orelse e.name;
pn_of[at] = pn;
var it = state.parentsOf(e.rid);
while (it.next()) |p| {
if (p >= slots) return error.Fallback;
if (state.mtimeOf(p) == null) {
any_unheld_parent = true;
if (prior != null) return error.Fallback;
}
pending[@intCast(p)] += 1;
try stack.append(scratch, .{ .rid = p, .name = pn });
}
}
// The linearization, newest first, as `ancestryLinearized` makes it: a
// check-in is ready once its children are out, and the newest ready one
// goes next. Versions are counted as they come out, and with a limit it
// stops at the last one the full walk may read: what came out is the
// window. `order_of` is the place in it, plus one.
const order_of = try scratch.alloc(u32, slots);
@memset(order_of, 0);
var emitted: std.ArrayList(repostate.Rid) = .empty;
var versions: std.ArrayList(repostate.Rid) = .empty;
// The blob each version's card named, so the walk reads it without
// reading the manifest again.
var blob_of: std.AutoHashMapUnmanaged(repostate.Rid, []const u8) = .empty;
var ready: std.PriorityQueue(repostate.Rid, *const repostate.RepoState, newestReady) = .initContext(state);
defer ready.deinit(gpa);
try ready.push(gpa, cur);
while (ready.pop()) |r| {
const at: usize = @intCast(r);
try emitted.append(scratch, r);
order_of[at] = @intCast(emitted.items.len);
if (limit != null or opts.list_versions) {
const name = name_of[at] - 1;
const changed = if (unknown.isSet(at))
try changedHere(gpa, repo, &names, null, r, name, pn_of[at], &baseline, &plaintext)
else if (!try facts.changed(&names, r, name))
false
else if (try cardAt(gpa, repo, r, names.get(name), &baseline, &plaintext)) |card| blk: {
defer Repository.freeFileCard(gpa, card);
try blob_of.put(scratch, r, try scratch.dupe(u8, card.hash.?));
break :blk true;
} else false;
if (changed) try versions.append(arena, r);
if (limit) |n| if (versions.items.len >= n) break;
}
var it = state.parentsOf(r);
while (it.next()) |p| {
const pa: usize = @intCast(p);
pending[pa] -= 1;
if (pending[pa] == 0) try ready.push(gpa, p);
}
}
const anc: Window = .{ .order_of = order_of };
// The limit left check-ins below the window: a line they could have
// written has no origin the walk can name.
const cut_window = emitted.items.len < ancestry_len;
const target_binary = blk: {
var absent: ?[]const u8 = null;
const bytes = (annotateContentAt(gpa, scratch, repo, &plaintext, &baseline, cur, path, &absent) catch null) orelse break :blk false;
defer gpa.free(bytes);
plaintext.max_bytes = @min(plaintext.max_bytes, @max(4 << 20, 16 * bytes.len));
break :blk merge3.isBinary(bytes);
};
// Unlike the full walk, a limited one reads the cache too: see the
// seeds below for why a cached answer cut to the window is exact.
const fp: ?u32 = if (!opts.partial and follow and !target_binary) cacheFingerprint(gpa, io, repo) else null;
var cached_file: ?blamecache.Mapped = if (fp) |f| blamecache.open(gpa, io, repo.root_dir, path, f) else null;
defer if (cached_file) |*m| m.deinit(gpa);
// The check-ins of the ancestry read under the annotated name that have
// an entry: the full walk's cached nodes.
var cached = try std.DynamicBitSetUnmanaged.initEmpty(scratch, slots);
var any_cached = false;
if (cached_file) |*m| for (0..m.file.n_entries) |k| {
const r = repo.lookup(m.file.checkinAt(k)) orelse continue;
if (r >= slots or name_of[@intCast(r)] != path_name + 1) continue;
cached.set(@intCast(r));
any_cached = true;
};
// The nodes, oldest first: parents before children, as the engine reads
// them, in the linearization's own order.
var nodes: std.ArrayList(repostate.Rid) = .empty;
var back = emitted.items.len;
while (back > 0) {
back -= 1;
const r = emitted.items[back];
const at: usize = @intCast(r);
const read = blk: {
if (state.mtimeOf(r) == null or unknown.isSet(at) or cached.isSet(at)) break :blk true;
if (try facts.changed(&names, r, name_of[at] - 1)) break :blk true;
const pp = state.primaryParentOf(r) orelse break :blk true;
break :blk !anc.inWindow(pp);
};
if (read) try nodes.append(scratch, r);
}
// Node index plus one, by check-in; zero for a check-in with no node.
const node_of = try scratch.alloc(u32, slots);
@memset(node_of, 0);
for (nodes.items, 0..) |r, i| node_of[@intCast(r)] = @intCast(i + 1);
var reps: Reps = .{ .state = state, .node_of = node_of, .memo = try scratch.alloc(u32, slots) };
@memset(reps.memo, 0);
// Whether a node has a parent below the window that holds the file: its
// lines may come from there, so the walk cannot name their origin. Asked
// of every node, not only the walked ones, since a cached origin can be
// any of them. `masked` marks a node where such a parent comes before an
// in-window one in the engine's order (primary, then merges in P-card
// order): there the full walk can credit a line to the parent below
// while the limited walk, not seeing it, credits the later one.
const n = nodes.items.len;
const cut = try scratch.alloc(bool, n);
@memset(cut, false);
const masked = try scratch.alloc(bool, n);
@memset(masked, false);
var any_cut = false;
if (cut_window) for (nodes.items, cut, masked) |r, *c, *m| {
const pn = names.get(pn_of[@intCast(r)]);
const primary = state.primaryParentOf(r);
for ([_]bool{ true, false }) |want_primary| {
var it = state.parentsOf(r);
while (it.next()) |p| {
if ((primary != null and p == primary.?) != want_primary) continue;
if (anc.inWindow(p)) {
if (c.*) m.* = true;
continue;
}
if (c.*) continue;
if (try cardAt(gpa, repo, p, pn, &baseline, &plaintext)) |card| {
Repository.freeFileCard(gpa, card);
c.* = true;
any_cut = true;
}
}
}
};
// The origin of a cached line that came from below the window: one past
// the last node, which the walk never adds. A child copying it can never
// mistake it for its own index, the engine's "unclaimed" mark.
const beyond_node: u32 = @intCast(n);
var any_beyond = false;
// The cached entry's cut: a cached check-in the walk reaches stands for
// its ancestry. Reached through every parent link, as the full walk's
// plan is, so a version only a merge that kept its primary side reaches
// is still read (and refused, if it is gone).
const roles = try scratch.alloc(engine.Role, n);
@memset(roles, .walk);
var plan_seeds: ?[]?CutPlan.Seed = null;
defer if (plan_seeds) |seeds| for (seeds) |sd| if (sd) |x| {
gpa.free(x.content);
gpa.free(x.origins);
};
var cached_users: std.AutoHashMapUnmanaged(repostate.Rid, ?[]const u8) = .empty;
var cache_failed = false;
if (any_cached) plan: {
var reached = try std.DynamicBitSetUnmanaged.initEmpty(scratch, slots);
var frontier: std.ArrayList(repostate.Rid) = .empty;
try frontier.append(scratch, cur);
while (frontier.pop()) |r| {
const at: usize = @intCast(r);
if (reached.isSet(at)) continue;
reached.set(at);
if (cached.isSet(at)) continue;
var it = state.parentsOf(r);
while (it.next()) |p| try frontier.append(scratch, p);
}
for (nodes.items, roles) |r, *role| {
const at: usize = @intCast(r);
role.* = if (!reached.isSet(at)) .skip else if (cached.isSet(at)) .seed else .walk;
}
// A cached entry stands for the full walk's choices at every node
// it cuts off, so each of them must choose as the limited walk
// does; see the seeds below. A masked one may not, and the walk is
// made as if nothing were cached. The file itself is sound: it is
// carried into any write as it is.
for (roles, masked) |role, m| if (role != .walk and m) {
@memset(roles, .walk);
break :plan;
};
const seeds = try scratch.alloc(?CutPlan.Seed, n);
@memset(seeds, null);
plan_seeds = seeds;
const m = &cached_file.?;
for (roles, 0..) |role, i| {
if (role != .seed) continue;
const r = nodes.items[i];
const slot = m.file.find(repo.hashOf(r)).?;
var absent: ?[]const u8 = null;
const content = (try annotateContentAt(gpa, scratch, repo, &plaintext, &baseline, r, path, &absent)) orelse {
cache_failed = true;
break :plan;
};
seeds[i] = .{ .content = content, .origins = &.{} };
const lines = try merge3.splitLines(gpa, content);
const line_count = lines.len;
gpa.free(lines);
if (line_count != m.file.lineCount(slot)) {
cache_failed = true;
break :plan;
}
var view = m.file.read(gpa, slot) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => {
cache_failed = true;
break :plan;
},
};
defer view.deinit(gpa);
const node_of_origin = try scratch.alloc(u32, view.origins.len);
for (view.origins, node_of_origin) |o, *slot_node| {
const orid = repo.lookup(o.hash) orelse {
cache_failed = true;
break :plan;
};
// Outside the ancestry, or above the seeded check-in: the
// full walk cannot place it either.
if (orid >= slots or name_of[@intCast(orid)] == 0) {
cache_failed = true;
break :plan;
}
// Below a `-n` window. Follow a line down the full walk's
// chain from the seed. At each node the engine gives it to
// the first parent, in its order, that carries it, else to
// the node. No node here is masked, so every in-window
// parent comes before every parent below that holds the
// file (one that does not hold it carries nothing). If the
// full walk picks an in-window parent, the limited walk,
// which reads the same content minus the parents below,
// picks it too, and the chain goes on inside the window. If
// it picks a parent below, no in-window parent carried the
// line, so the limited walk keeps it at the node, which is
// `cut`: unattributed. A chain below never comes back, the
// window holding every child of what it holds, so an origin
// below it is unattributed by both walks. And an origin in
// the window is the limited walk's too, unattributed when
// `cut`. A check-in with no node shares its primary's
// version, which claims every line, in both walks.
if (!anc.inWindow(orid)) {
slot_node.* = beyond_node;
any_beyond = true;
continue;
}
if (order_of[@intCast(orid)] < order_of[@intCast(r)]) {
cache_failed = true;
break :plan;
}
const node = node_of[@intCast(orid)];
if (node == 0) return error.Fallback;
slot_node.* = node - 1;
const gop = try cached_users.getOrPut(scratch, orid);
if (!gop.found_existing) gop.value_ptr.* = if (o.user) |u| try arena.dupe(u8, u) else null;
}
const origins = try gpa.alloc(u32, line_count);
for (origins, 0..) |*o, li| o.* = node_of_origin[view.lineAt(li)];
seeds[i].?.origins = origins;
}
}
// As the full walk's miss: no cut. The logins read before it stay, as
// there.
if (cache_failed) {
@memset(roles, .walk);
any_beyond = false;
}
// §3.2 primary and merge parents of each node, as the nodes their
// versions come from: a parent below the window holds none for the walk.
const Links = struct { primary: ?u32, merges: []const u32 };
const links = try scratch.alloc(Links, n);
for (nodes.items, links, roles) |r, *l, role| {
l.* = .{ .primary = null, .merges = &.{} };
if (role != .walk) continue;
const primary_rid = state.primaryParentOf(r);
var merges: std.ArrayList(u32) = .empty;
var it = state.parentsOf(r);
while (it.next()) |p| {
if (!anc.inWindow(p)) continue;
if (primary_rid != null and p == primary_rid.?) {
l.primary = reps.of(p);
} else try merges.append(scratch, reps.of(p));
}
l.merges = merges.items;
}
const target = reps.of(cur);
const last_use = try scratch.alloc(u32, n);
for (links, 0..) |l, i| {
last_use[i] = @intCast(i);
if (l.primary) |p| last_use[p] = @max(last_use[p], @as(u32, @intCast(i)));
for (l.merges) |p| last_use[p] = @max(last_use[p], @as(u32, @intCast(i)));
}
last_use[target] = std.math.maxInt(u32);
// Each version's blob is named by its card, a manifest read per version.
// Past a few hundred of those, one pass over the derived cache's record
// body, which names them all, costs less; a check-in it has no row for
// is still read from its manifest.
var unread: usize = 0;
for (nodes.items, roles) |r, role| {
if (role == .walk and !blob_of.contains(r)) unread += 1;
}
var touched_opt: ?AnnotateTouched = if (unread > max_card_reads) annotateTouchedFromCache(gpa, io, repo, &names, path, follow) else null;
defer if (touched_opt) |*t| t.deinit(gpa);
var walk = try engine.Walk.init(gpa, n, true);
defer walk.deinit();
const present = try scratch.alloc(bool, n);
@memset(present, false);
for (nodes.items, roles, 0..) |r, role, i| {
const ni: u32 = @intCast(i);
switch (role) {
.skip => continue,
.seed => {
const sd = plan_seeds.?[i].?;
plan_seeds.?[i] = null; // the walk's now, even if it fails
present[i] = true;
try walk.seed(ni, sd.content, sd.origins);
if (last_use[i] == ni) walk.release(ni);
continue;
},
.walk => {},
}
const at: usize = @intCast(r);
var absent: ?[]const u8 = null;
const name = name_of[at] - 1;
const row: ?TouchedRow = if (touched_opt) |*t| (if (t.answers(r, name)) t.touched.get(.{ .rid = r, .name = name }) else null) else null;
const blob: ?[]const u8 = blob_of.get(r) orelse if (row) |w| w.hash else null;
var owned = if (blob) |h| blk: {
const bytes = try annotateContentByHash(gpa, repo, &plaintext, h);
if (bytes == null) absent = h;
break :blk bytes;
} else if (row != null) null else try annotateContentAt(gpa, scratch, repo, &plaintext, &baseline, r, names.get(name_of[at] - 1), &absent);
defer if (owned) |o| gpa.free(o);
// Content the store lacks is a refusal, a gap or the store's own
// cut, each decided where the full walk meets it.
if (owned == null and absent != null) return error.Fallback;
present[i] = owned != null;
if (!target_binary) {
const content = owned;
owned = null; // the walk's now, even if it fails
walked.* += 1;
try walk.add(ni, .{ .content = content, .primary = links[i].primary, .merges = links[i].merges });
}
if (last_use[i] == ni) walk.release(ni);
if (links[i].primary) |p| if (last_use[p] == ni) walk.release(p);
for (links[i].merges) |p| if (last_use[p] == ni) walk.release(p);
}
if (!present[target]) {
if (try elidedAt(gpa, arena, repo, hook, cur, path, null)) |rf| return .{ .refused = rf };
return .{ .refused = .not_tracked };
}
if (target_binary) return .{ .refused = .binary };
const target_bytes = walk.content(target).?;
if (merge3.isBinary(target_bytes)) return .{ .refused = .binary };
const target_text = try arena.dupe(u8, target_bytes);
const origin_nodes = walk.origins(target).?;
const lines = try merge3.splitLines(arena, target_text);
std.debug.assert(lines.len == origin_nodes.len);
const origins = try arena.alloc(Origin, lines.len);
var users: std.AutoHashMapUnmanaged(repostate.Rid, ?[]const u8) = .empty;
for (origin_nodes, origins) |node, *o| {
// A line from below the window is reported at the oldest node, as
// where the walk stopped; only `beyond` is ever shown for it.
const r = nodes.items[if (node == beyond_node) 0 else node];
o.* = .{ .rid = r, .mtime = state.mtimeOf(r) orelse 0, .approx = false, .beyond = node == beyond_node or cut[node] };
if (o.beyond) continue;
const gop = try users.getOrPut(scratch, r);
if (!gop.found_existing) gop.value_ptr.* = cached_users.get(r) orelse try userOfState(gpa, arena, repo, r);
o.user = gop.value_ptr.*;
}
const seeded_target = !cache_failed and cached.isSet(@intCast(cur));
// Under a limit, the answer is the full one only when nothing below the
// window holds the file; otherwise a line may be cut short of its
// origin, and the cache must never hold that.
if (fp) |f| if (!any_unheld_parent and !seeded_target and !any_cut and !any_beyond) {
const prior: ?*const blamecache.File = if (cache_failed) null else if (cached_file) |*m| &m.file else null;
try fillCache(gpa, scratch, io, repo, path, f, cur, origins, prior);
};
return .{ .ok = .{ .target = target_text, .lines = lines, .origins = origins, .any_gap = false, .versions = versions.items } };
}
/// The file index's change sets as the indexed walk asks them: by check-in
/// and name, one bit per check-in, loaded per name on first use.
const IndexFacts = struct {
/// The index's own allocator: it keeps what it is asked.
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
ix: *filelog.PathIndex,
slots: usize,
sets: std.ArrayListUnmanaged(?std.DynamicBitSetUnmanaged) = .empty,
fn changed(self: *IndexFacts, names: *const NameTable, rid: repostate.Rid, name: NameId) IndexedError!bool {
while (self.sets.items.len <= name) try self.sets.append(self.arena, null);
if (self.sets.items[name] == null) {
const set = self.ix.changedSet(self.gpa, names.get(name)) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => error.Fallback,
};
var bits = try std.DynamicBitSetUnmanaged.initEmpty(self.arena, self.slots);
var it = set.keyIterator();
while (it.next()) |r| if (r.* < self.slots) bits.set(@intCast(r.*));
self.sets.items[name] = bits;
}
return self.sets.items[name].?.isSet(@intCast(rid));
}
};
/// The node each check-in's version comes from: its own, or, for one with
/// no node, its primary parent's, which inside the window always has one
/// down the chain. Memoized, so the chains cost one step per check-in.
const Reps = struct {
state: *const repostate.RepoState,
node_of: []const u32,
memo: []u32,
fn of(self: *Reps, rid: repostate.Rid) u32 {
var r = rid;
const found: u32 = while (true) {
const at: usize = @intCast(r);
if (self.node_of[at] != 0) break self.node_of[at] - 1;
if (self.memo[at] != 0) break self.memo[at] - 1;
r = self.state.primaryParentOf(r).?;
};
r = rid;
while (self.node_of[@intCast(r)] == 0 and self.memo[@intCast(r)] == 0) {
self.memo[@intCast(r)] = found + 1;
r = self.state.primaryParentOf(r).?;
}
return found;
}
};
/// The ancestry's linearization as far as the indexed walk took it.
const Window = struct {
order_of: []const u32,
fn inWindow(self: Window, rid: repostate.Rid) bool {
return self.order_of[@intCast(rid)] != 0;
}
};
/// The linearization's choice among ready check-ins: the later event time,
/// then the greater hash, a phantom's missing time read as zero
/// (`RepoState.chainBefore`).
fn newestReady(state: *const repostate.RepoState, a: repostate.Rid, b: repostate.Rid) std.math.Order {
const ma = state.mtimeOf(a) orelse 0;
const mb = state.mtimeOf(b) orelse 0;
if (ma != mb) return std.math.order(mb, ma);
return std.mem.order(u8, state.hashOf(b), state.hashOf(a));
}
/// The blame cache's fingerprint for this store, or null when it cannot
/// be taken (nothing is then read or written).
fn cacheFingerprint(gpa: std.mem.Allocator, io: std.Io, repo: *Repository) ?u32 {
const log = repo.logStore(gpa) catch return null;
return blamecache.fingerprint(gpa, io, repo.root_dir, log.shunFingerprint());
}
/// The cut a cache file allows: each node's `engine.Role`, and for each
/// seeded node its content and origins, held until the walk takes them.
const CutPlan = struct {
roles: []const engine.Role,
seeds: []?Seed,
const Seed = struct { content: []u8, origins: []u32 };
fn deinit(self: *CutPlan, gpa: std.mem.Allocator) void {
for (self.seeds) |sd| if (sd) |x| {
gpa.free(x.content);
gpa.free(x.origins);
};
}
};
/// The nodes of the walk `annotate` built, as `planFromCache` reads them.
const Graph = struct {
path: []const u8,
path_name: NameId,
entries: []const AnnotateEntry,
index_of: *const std.AutoHashMapUnmanaged(repostate.Rid, u32),
node_keys: []const NamedRid,
node_pos: []const u32,
node_of: *const std.AutoHashMapUnmanaged(NamedRid, u32),
parent_name_of: *const std.AutoHashMapUnmanaged(NamedRid, NameId),
target: u32,
};
/// The cut through `file`'s entries: every node under the annotated name
/// whose check-in has an entry is cached, and the ones the walk reaches are
/// seeded. Null, walking everything, when no entry is reached, or when any
/// reached entry fails to answer: its version gone or of another line
/// count, an origin this store cannot place below it, or a damaged block.
/// The last three set `failed`, so the next write starts the file afresh.
fn planFromCache(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
plaintext: *logstore.PlaintextCache,
baseline: *?*Repository.BaselineMemo,
file: *blamecache.File,
g: Graph,
users: *std.AutoHashMapUnmanaged(repostate.Rid, ?[]const u8),
failed: *bool,
) ReadError!?CutPlan {
const n = g.node_keys.len;
const cached = try arena.alloc(bool, n);
var any = false;
for (g.node_keys, cached) |key, *c| {
c.* = key.name == g.path_name and file.find(repo.hashOf(key.rid)) != null;
any = any or c.*;
}
if (!any) return null;
// The engine's view of the parent links, as the main walk resolves them.
const nodes = try arena.alloc(engine.Node, n);
for (g.node_keys, nodes) |key, *node| {
const pn = g.parent_name_of.get(key).?;
const primary_rid = repo.state().primaryParentOf(key.rid);
var merges: std.ArrayList(u32) = .empty;
var it = repo.state().parentsOf(key.rid);
while (it.next()) |p| {
if (primary_rid != null and p == primary_rid.?) continue;
const idx = g.node_of.get(.{ .rid = p, .name = pn }) orelse continue;
try merges.append(arena, idx);
}
node.* = .{
.content = null,
.primary = if (primary_rid) |pr| g.node_of.get(.{ .rid = pr, .name = pn }) else null,
.merges = merges.items,
};
}
const roles = try engine.planCut(arena, nodes, g.target, cached);
// A cached origin names a check-in; any node at its position stands for
// it, since only the check-in is reported. The first is never above the
// seeded node, as the walk's origins must not be.
const first_at = try arena.alloc(u32, g.entries.len);
@memset(first_at, std.math.maxInt(u32));
for (g.node_pos, 0..) |pos, i| first_at[pos] = @min(first_at[pos], @as(u32, @intCast(i)));
var plan: CutPlan = .{ .roles = roles, .seeds = try arena.alloc(?CutPlan.Seed, n) };
@memset(plan.seeds, null);
errdefer plan.deinit(gpa);
for (roles, 0..) |role, i| {
if (role != .seed) continue;
const ni: u32 = @intCast(i);
const rid = g.node_keys[i].rid;
const slot = file.find(repo.hashOf(rid)).?;
var absent: ?[]const u8 = null;
const content = (try annotateContentAt(gpa, arena, repo, plaintext, baseline, rid, g.path, &absent)) orelse
return miss(gpa, &plan, failed);
plan.seeds[i] = .{ .content = content, .origins = &.{} };
const lines = try merge3.splitLines(gpa, content);
const line_count = lines.len;
gpa.free(lines);
if (line_count != file.lineCount(slot)) return miss(gpa, &plan, failed);
var view = file.read(gpa, slot) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => return miss(gpa, &plan, failed),
};
defer view.deinit(gpa);
const node_of_origin = try arena.alloc(u32, view.origins.len);
for (view.origins, node_of_origin) |o, *slot_node| {
const orid = repo.lookup(o.hash) orelse return miss(gpa, &plan, failed);
const pos = g.index_of.get(orid) orelse return miss(gpa, &plan, failed);
if (first_at[pos] > ni) return miss(gpa, &plan, failed);
slot_node.* = first_at[pos];
const gop = try users.getOrPut(arena, orid);
if (!gop.found_existing) gop.value_ptr.* = if (o.user) |u| try arena.dupe(u8, u) else null;
}
const origins = try gpa.alloc(u32, line_count);
for (origins, 0..) |*o, li| o.* = node_of_origin[view.lineAt(li)];
plan.seeds[i].?.origins = origins;
}
return plan;
}
fn miss(gpa: std.mem.Allocator, plan: *CutPlan, failed: *bool) ?CutPlan {
plan.deinit(gpa);
failed.* = true;
return null;
}
/// `userOf`, from the derived state when it holds a login: a check-in
/// without one reads its manifest, which tells a missing U card from an
/// empty login.
fn userOfState(gpa: std.mem.Allocator, arena: std.mem.Allocator, repo: *Repository, rid: repostate.Rid) error{OutOfMemory}!?[]const u8 {
if (repo.state().userOf(rid)) |u| if (u.len != 0) return u;
return userOf(gpa, arena, repo, rid);
}
/// Record the target's attribution in the blame cache: its distinct origin
/// check-ins by hash, with their users, and one index per line. Past the
/// cache's bounds nothing is written.
fn fillCache(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
io: std.Io,
repo: *Repository,
path: []const u8,
fp: u32,
cur: repostate.Rid,
origins: []const Origin,
prior: ?*const blamecache.File,
) error{OutOfMemory}!void {
var index_of: std.AutoHashMapUnmanaged(repostate.Rid, u16) = .empty;
var table: std.ArrayList(blamecache.Origin) = .empty;
const lines = try arena.alloc(u16, origins.len);
for (origins, lines) |o, *l| {
const gop = try index_of.getOrPut(arena, o.rid);
if (!gop.found_existing) {
if (table.items.len == blamecache.max_origins) return;
gop.value_ptr.* = @intCast(table.items.len);
try table.append(arena, .{ .hash = repo.hashOf(o.rid), .user = o.user });
}
l.* = gop.value_ptr.*;
}
blamecache.store(gpa, io, repo.root_dir, path, fp, .{ .checkin = repo.hashOf(cur), .origins = table.items, .lines = lines }, prior);
}
/// Whether check-in `rid` changed the file it holds under `name` against its
/// primary parent's `parent_name`: a version, in Fossil's sense of a row in
/// its mlink table. A delete is not one; it holds no content to walk.
fn changedHere(
gpa: std.mem.Allocator,
repo: *Repository,
names: *const NameTable,
touched: ?*const AnnotateTouched,
rid: repostate.Rid,
name: NameId,
parent_name: NameId,
baseline: *?*Repository.BaselineMemo,
plaintext: *logstore.PlaintextCache,
) ReadError!bool {
if (touched) |t| if (t.answers(rid, name)) {
const row = t.touched.get(.{ .rid = rid, .name = name }) orelse return false;
return row.hash != null;
};
const card = (try cardAt(gpa, repo, rid, names.get(name), baseline, plaintext)) orelse return false;
defer Repository.freeFileCard(gpa, card);
const pr = repo.state().primaryParentOf(rid) orelse return true;
const parent = (try cardAt(gpa, repo, pr, names.get(parent_name), baseline, plaintext)) orelse return true;
defer Repository.freeFileCard(gpa, parent);
return !std.mem.eql(u8, card.hash.?, parent.hash.?);
}
fn cardAt(
gpa: std.mem.Allocator,
repo: *Repository,
rid: repostate.Rid,
name: []const u8,
baseline: *?*Repository.BaselineMemo,
plaintext: *logstore.PlaintextCache,
) ReadError!?artifact.FCard {
return repo.fileAtMemo(gpa, rid, name, baseline, plaintext) catch |e| switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead => error.Storage,
else => error.Corrupt,
};
}
/// The committing user of check-in `rid` (its U card), on `arena`; null
/// when its manifest cannot be read or carries none.
pub fn userOf(gpa: std.mem.Allocator, arena: std.mem.Allocator, repo: *Repository, rid: repostate.Rid) error{OutOfMemory}!?[]const u8 {
var om = (repo.manifest(gpa, rid) catch null) orelse return null;
defer om.deinit(gpa);
const u = om.manifest.u orelse return null;
return try arena.dupe(u8, u.login);
}
const Verdict = enum {
/// The store's own cut: the version reads as the file's origin.
origin,
/// Purged or shunned, and the caller reads through it.
gap,
purged,
shunned,
missing,
};
/// A version names blob `hash`, and the blob is not here. Purged or shunned
/// is a refusal (or a gap when `bridge`); with a cone or horizon the
/// absence is the store's own cut, the history below it is answered by the
/// origin, and the version reads as the file's origin; otherwise it is
/// missing.
fn absentVerdict(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
has_cone: *?bool,
hash: []const u8,
bridge: bool,
) error{OutOfMemory}!Verdict {
if (thinned.contains(gpa, io, repo.root_dir, hash)) return if (bridge) .gap else .purged;
shun: {
var buf: [logstore.max_hash_len]u8 = undefined;
if (hash.len != 40 and hash.len != 64) break :shun;
const digest = std.fmt.hexToBytes(buf[0 .. hash.len / 2], hash) catch break :shun;
const log = repo.logStore(gpa) catch break :shun;
if (log.isShunned(digest)) return if (bridge) .gap else .shunned;
}
if (has_cone.* == null) {
var cone = repocache.readStoreCone(gpa, io, repo.root_dir);
has_cone.* = cone != null;
if (cone) |*c| c.deinit(gpa);
}
if (has_cone.*.?) return .origin;
return .missing;
}
/// Sparse-cone RFC section 6.4 / horizon draft section 5.5: `name` in
/// check-in `rid` names a blob this store elides. The refusal, or null when
/// the content is absent for any other reason. `hash` is the blob when the
/// caller already knows it, else the check-in's card is read.
fn elidedAt(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
hook: ElisionHook,
rid: repostate.Rid,
name: []const u8,
hash: ?[]const u8,
) error{OutOfMemory}!?Refusal {
var card: ?artifact.FCard = null;
defer if (card) |c| Repository.freeFileCard(gpa, c);
const h = hash orelse blk: {
card = repo.fileAt(gpa, rid, name) catch null;
break :blk (card orelse return null).hash orelse return null;
};
const e = hook.of(hook.ctx, gpa, h) orelse return null;
if (!e.elided) return null;
return .{ .elided = .{ .name = try arena.dupe(u8, name), .hash = try arena.dupe(u8, h) } };
}
/// Check-in `rid` renamed `new_name` from an old name, and a parent that
/// held the old name lies below this store's horizon: the renamed file's
/// blob, which names the cut, or null when the store has no horizon (the
/// parent is then simply missing, and the walk goes on).
fn elidedBelow(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
hook: ElisionHook,
rid: repostate.Rid,
new_name: []const u8,
) error{OutOfMemory}!?[]const u8 {
const card = (repo.fileAt(gpa, rid, new_name) catch null) orelse return null;
defer Repository.freeFileCard(gpa, card);
const e = hook.of(hook.ctx, gpa, card.hash.?) orelse return null;
if (!e.horizon) return null;
return try arena.dupe(u8, card.hash.?);
}