//! One file's history, as `zit log CHECKIN PATH` lists it: the ancestry
//! walk restricted to the check-ins that change PATH (following renames
//! unless told not to), the file index that narrows it, and the per-row facts
//! `-F json` and the daemon's `log` report. The CLI and the daemon both
//! call this, so the two cannot list different check-ins or describe one
//! differently.
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 fileindex = @import("../fileindex.zig");
const Repository = @import("../repository.zig").Repository;
const feed = @import("feed.zig");
const digest_len = 32;
pub const LogWalkError = error{
OutOfMemory,
Storage,
Corrupt,
MissingRoot,
InvalidRoot,
InvalidTarget,
};
fn decodeFullId(id: []const u8, out: *[digest_len]u8) error{InvalidId}![]const u8 {
if (!artifact.validateName(id)) return error.InvalidId;
const decoded = out[0 .. id.len / 2];
_ = std.fmt.hexToBytes(decoded, id) catch return error.InvalidId;
// §3.6: `validateName` accepted a 40/64-hex token, so the decode is a whole
// 20/32-byte digest that fits the fixed buffer — never a truncated prefix.
std.debug.assert(decoded.len <= digest_len);
return decoded;
}
/// The optional PATH restriction for a `zit log CHECKIN PATH` walk (B-log-2).
/// `repo` answers the one general-purpose §8 effective-set query (`fileAt`) the
/// change predicate consumes (B-log-5); `path` is the exact repo-relative name.
pub const LogPathFilter = struct {
repo: *Repository,
path: []const u8,
/// Follow renames: below a check-in whose card for the followed name
/// carries an old name, the walk continues under the old name. False is
/// `--no-follow`, the name-literal history.
follow: bool = true,
/// The file index, when it can be trusted. When present the predicate
/// starts as a set membership test and a check-in the index does not name
/// is skipped without reading anything; when null the walk computes the
/// same answer by reconstruction. The index is refused whenever it cannot
/// be trusted whole (stale key, changed shun set), and a check-in whose
/// change set it records as UNKNOWN is reconstructed individually, so the
/// reconstruction is the correctness backstop, never a second definition
/// of the predicate.
index: ?*PathIndex = null,
};
/// A name a PATH walk follows, interned in a `NameTable`.
pub const NameId = u32;
/// One check-in under one of the names a walk follows. A rename makes the
/// same check-in reachable under two names, and each is a different question.
pub const NamedRid = struct { rid: repostate.Rid, name: NameId };
/// The names a following walk has met, interned so a (check-in, name) pair is
/// two integers. A walk meets one more name per rename it crosses, so this
/// grows with the file's rename history, not with the walk.
pub const NameTable = struct {
arena: std.heap.ArenaAllocator,
ids: std.StringHashMapUnmanaged(NameId) = .empty,
names: std.ArrayListUnmanaged([]const u8) = .empty,
pub fn init(gpa: std.mem.Allocator) NameTable {
return .{ .arena = std.heap.ArenaAllocator.init(gpa) };
}
pub fn deinit(self: *NameTable, gpa: std.mem.Allocator) void {
self.ids.deinit(gpa);
self.names.deinit(gpa);
self.arena.deinit();
}
pub fn intern(self: *NameTable, gpa: std.mem.Allocator, name: []const u8) error{OutOfMemory}!NameId {
if (self.ids.get(name)) |id| return id;
const copy = try self.arena.allocator().dupe(u8, name);
const id: NameId = @intCast(self.names.items.len);
try self.names.append(gpa, copy);
errdefer _ = self.names.pop();
try self.ids.put(gpa, copy, id);
return id;
}
pub fn get(self: *const NameTable, id: NameId) []const u8 {
return self.names.items[id];
}
};
/// Emit each check-in's own D/U/C cards beside its id. The manifest is
/// already parsed at the emit site to walk its P cards, so the facts are free
/// here and cost a subprocess per row anywhere else: a consumer drawing a file
/// history page (`log CHECKIN PATH`) otherwise runs `zit info` once per entry.
/// Same defect, and same fix, as `ls --long`.
///
/// `event_time` is the check-in's stored event time when derived state knows
/// it, which a date tag may have moved off the D card (repo-state §4.2 step
/// 6); it is printed in the writer form `info` and `timeline` use. Only the
/// walk with no derived state passes null and prints the D card itself.
pub fn logEmit(out: *std.Io.Writer, id: []const u8, manifest: *const artifact.Manifest, long: bool, event_time: ?repostate.Mtime) void {
if (!long) {
out.print("checkin {s}\n", .{id}) catch {};
return;
}
// Comment last: it is the only field that may contain spaces, so every
// earlier column stays splittable. A check-in with no C card prints an
// empty trailing field rather than a short line, so the arity is fixed.
var iso_buf: [19]u8 = undefined;
const when = if (event_time) |mt|
artifact.formatWriterTimestamp(@intCast(mt / 1000), &iso_buf)
else if (manifest.d) |d| d.timestamp else "-";
const who = if (manifest.u) |u| u.login else "-";
const what = if (manifest.c) |c| c.comment else "";
out.print("checkin {s} {s} {s} {s}\n", .{ id, when, who, what }) catch {};
}
/// `times`, when present, supplies each emitted check-in's stored event time
/// for `--long`; without it the row prints the D card.
pub fn eventTimeOf(times: ?*Repository, id: []const u8) ?repostate.Mtime {
const repo = times orelse return null;
const rid = repo.lookup(id) orelse return null;
return repo.state().mtimeOf(rid);
}
/// One check-in a PATH walk listed: the name PATH had there and, on a rename
/// row, the name it was renamed from. `-F json` renders these; the strings
/// live in the caller's arena.
pub const LogRow = struct { id: []const u8, name: []const u8, prior: ?[]const u8 };
/// Where a PATH walk reports its rows besides the text lines.
pub const LogRows = struct {
arena: std.mem.Allocator,
rows: std.ArrayListUnmanaged(LogRow) = .empty,
/// `walkPath` resumes after this check-in in its newest-first order:
/// the rows up to and including it are neither kept nor counted toward
/// the limit, so a page picks up where the previous one ended. Cleared
/// once found; still set afterwards means the walk does not list it.
after: ?[]const u8 = null,
fn add(self: *LogRows, names: *const NameTable, id: []const u8, name: NameId, prior: ?NameId) error{OutOfMemory}!void {
try self.rows.append(self.arena, .{
.id = try self.arena.dupe(u8, id),
.name = try self.arena.dupe(u8, names.get(name)),
.prior = if (prior) |p| try self.arena.dupe(u8, names.get(p)) else null,
});
}
};
/// What one visited check-in means for the name a PATH walk follows there.
pub const PathStep = struct {
/// List it: its content or presence for the name differs from its primary
/// parent's, or (following) it renamed the file onto the name.
hit: bool = false,
/// Following, on a rename row: the name the parents are walked under.
prior: ?NameId = null,
/// The name is present here. Only meaningful when `known`.
present: bool = false,
/// The content was reconstructed; false for a check-in the index skipped.
known: bool = false,
/// The primary parent holds the parent-side name.
parent_present: bool = false,
/// Following, the walk ends on this side: the name was renamed away here
/// after the walk had already met the file now at this name, so what lies
/// below under this name is the renamed file's history, not this one's.
stop: bool = false,
};
/// The step a PATH walk takes at check-in `rid` (null: not interned, a
/// phantom the derived view never crosslinked) under `name`. `primary` is its
/// §3.2 primary parent. `on_file` says whether the walk has already met the
/// file present under the name it follows.
pub fn pathStep(
gpa: std.mem.Allocator,
f: LogPathFilter,
probe: *PathProbe,
rid: ?repostate.Rid,
primary: ?repostate.Rid,
name: NameId,
on_file: bool,
) LogWalkError!PathStep {
// An index lost to damage no rebuild could mend answers nothing; the
// reconstruction it only ever narrowed answers alone, from this step on.
var unindexed = f;
unindexed.index = null;
if (f.index) |i| if (i.lost) return pathStepWith(gpa, unindexed, probe, rid, primary, name, on_file);
return pathStepWith(gpa, f, probe, rid, primary, name, on_file) catch |e| switch (e) {
error.Corrupt => if (f.index) |i| (if (i.lost) pathStepWith(gpa, unindexed, probe, rid, primary, name, on_file) else e) else e,
else => e,
};
}
fn pathStepWith(
gpa: std.mem.Allocator,
f: LogPathFilter,
probe: *PathProbe,
rid: ?repostate.Rid,
primary: ?repostate.Rid,
name: NameId,
on_file: bool,
) LogWalkError!PathStep {
// The index NARROWS; the reconstruction DECIDES. A check-in the index
// does not name for this name is skipped without reading anything; one
// it does name is still confirmed by reconstruction, because the two
// relations are not identical: `captureFileFacts` diffs at F-card level,
// so a delta manifest that restates a path with the hash it already had
// reads as a change there while the path's effective content did not
// move. On the SQLite mirror that is one check-in in 2,113 — an
// over-report, never an omission — and confirming costs one
// reconstruction per CANDIDATE instead of one per visited check-in.
//
// The direction being trusted is stated plainly: a check-in the index
// omits is taken as unchanged. The differential test pins that against
// the reconstructing walk so a regression in `captureFileFacts` cannot
// silently drop a file's history.
const ix: ?*PathIndex = if (f.index) |i| (if (rid) |r| (if (i.unknown.contains(r)) null else i) else null) else null;
if (ix) |i| {
const set = try i.changedSet(gpa, probe.names.get(name));
if (!set.contains(rid.?)) {
// Not a row: nothing to list. But until a following walk has met
// the file, whether this check-in HOLDS the name is what decides
// the walk below it (`stop`), and the reconstruction learns that
// at every check-in it visits. Asked here too, the two walks
// agree; it costs one read per check-in only on the stretch
// above the point where the file is first met.
if (!f.follow or on_file) return .{};
const here = try effectivePathContent(gpa, f.repo, probe, rid, name);
return .{ .present = here.present, .known = true };
}
}
const here = try effectivePathContent(gpa, f.repo, probe, rid, name);
// The rename edge: from the index when it answers this check-in, else
// from the card. Both are keyed by THIS check-in and name, never by the
// path alone, so a file later created at the old name is never routed
// into the renamed file's history.
const prior: ?NameId = if (!f.follow or !here.present)
null
else if (ix) |i|
(if (try i.priorOf(gpa, rid.?, probe.names.get(name))) |old| try probe.names.intern(gpa, old) else null)
else
here.prior;
const parent = if (primary) |p|
try effectivePathContent(gpa, f.repo, probe, p, prior orelse name)
else
PathContent{ .present = false };
const changed = here.present != parent.present or
(here.present and !std.mem.eql(u8, here.hash[0..here.hash_len], parent.hash[0..parent.hash_len]));
var step: PathStep = .{
.hit = changed or prior != null,
.prior = prior,
.present = here.present,
.known = true,
.parent_present = parent.present,
};
if (f.follow and on_file and !here.present and parent.present) {
const away = if (ix) |i|
try i.renamedAway(gpa, rid.?, probe.names.get(name))
else
try renamedAway(gpa, f.repo, probe, rid.?, name);
if (away) {
step.hit = false;
step.stop = true;
}
}
return step;
}
/// Whether check-in `rid` renamed a file away from `name`: one of its own F
/// cards carries `name` as its old name. Read only at a check-in that removes
/// the name a walk follows, so the full file list is read rarely.
fn renamedAway(gpa: std.mem.Allocator, repo: *Repository, probe: *PathProbe, rid: repostate.Rid, name: NameId) LogWalkError!bool {
var list = (repo.files(gpa, rid) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead => error.Storage,
else => error.Corrupt,
}) orelse return false;
defer list.deinit(gpa);
const wanted = probe.names.get(name);
var it = list.iterator();
while (it.next()) |card| {
if (card.old_name) |old| if (std.mem.eql(u8, old, wanted)) return true;
}
return false;
}
pub fn walkLog(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
root_id: []const u8,
out: *std.Io.Writer,
filter: ?LogPathFilter,
limit: ?usize,
long: bool,
times: ?*Repository,
rows: ?*LogRows,
/// The caller's memos, kept past the walk so the rows' facts are read
/// from what the walk already reconstructed; null keeps them local.
shared: ?*PathProbe,
) LogWalkError!void {
const Pending = struct { id: []u8, name: NameId, on_file: bool };
var pending: std.ArrayList(Pending) = .empty;
defer {
for (pending.items) |p| gpa.free(p.id);
pending.deinit(gpa);
}
// Keyed by id, and by name too once a walk follows a rename: the same
// check-in under another name is another question.
var visited: std.StringHashMapUnmanaged(void) = .empty;
defer visited.deinit(gpa);
var visited_keys: std.ArrayList([]u8) = .empty;
defer {
for (visited_keys.items) |k| gpa.free(k);
visited_keys.deinit(gpa);
}
var shown: std.StringHashMapUnmanaged(void) = .empty;
defer shown.deinit(gpa);
// The plaintext memo, and this walk is the case it exists for. Check-in manifests
// are routinely stored as deltas against their neighbours, so reconstructing
// each one from `content` alone re-resolves the SAME base chain once per
// check-in — work that grows with how much history sits behind the node
// rather than with the node, which is why the per-check-in cost climbed with
// repository size instead of staying flat. Every other read path in this
// file already takes the memo; this one did not.
var own_plaintext: logstore.PlaintextCache = .{};
defer own_plaintext.deinit(gpa);
// The PATH predicate reads through the SAME plaintext memo, plus
// a baseline memo and an answer memo of its own. It runs twice per node
// (here, and the primary parent), so it, not the walk, was the cost.
var own_probe = PathProbe.init(gpa, &own_plaintext);
defer own_probe.deinit(gpa);
const probe = shared orelse &own_probe;
const plaintext = probe.plaintext;
// `-n N` caps the ENTRIES NAMED, not the nodes traversed: with a PATH filter
// most visited check-ins print nothing, and capping traversal would make the
// answer depend on how much unrelated history sat in between. Counting the
// lines the user actually sees is the only reading that stays stable.
var emitted: usize = 0;
var root_name: NameId = 0;
var root_on_file = false;
if (filter) |f| {
root_name = try probe.names.intern(gpa, f.path);
root_on_file = (try effectivePathContent(gpa, f.repo, probe, f.repo.lookup(root_id), root_name)).present;
}
const root_copy = try gpa.dupe(u8, root_id);
pending.append(gpa, .{ .id = root_copy, .name = root_name, .on_file = root_on_file }) catch {
gpa.free(root_copy);
return error.OutOfMemory;
};
var first = true;
while (pending.pop()) |entry| {
const id = entry.id;
// `-n N` (N ≥ 1; `parseLimitValue` maps 0 → null) returns the moment the
// Nth line is named, so at every loop entry fewer than N lines are out.
if (limit) |n| std.debug.assert(emitted < n);
const key: []u8 = if (entry.name == 0) id else blk: {
defer gpa.free(id);
break :blk try std.fmt.allocPrint(gpa, "{s}/{d}", .{ id, entry.name });
};
if (visited.contains(key)) {
gpa.free(key);
continue;
}
visited_keys.append(gpa, key) catch {
gpa.free(key);
return error.OutOfMemory;
};
visited.put(gpa, key, {}) catch {
_ = visited_keys.pop();
gpa.free(key);
return error.OutOfMemory;
};
const hex = key[0 .. std.mem.indexOfScalar(u8, key, '/') orelse key.len];
const is_root = first;
first = false;
var hash_buf: [digest_len]u8 = undefined;
const decoded = decodeFullId(hex, &hash_buf) catch
return if (is_root) error.InvalidRoot else error.InvalidTarget;
// A decoded id is a full §3.6 artifact name (40/64 hex), never a prefix —
// it is exactly what every `checkin`/`phantom` line below renders.
std.debug.assert(artifact.validateName(hex));
const rid = log.lookup(decoded) orelse {
if (is_root) return error.MissingRoot;
// A phantom's effective set is unknowable, so the PATH filter cannot
// assert it changes PATH — it is silently skipped (the unfiltered
// walk still names it once).
if (filter == null) {
out.print("phantom {s}\n", .{hex}) catch {};
emitted += 1;
if (limit) |n| if (emitted >= n) return;
}
continue;
};
const bytes = (try log.contentCached(gpa, rid, plaintext)) orelse {
if (is_root) return error.MissingRoot;
if (filter == null) {
out.print("phantom {s}\n", .{hex}) catch {};
emitted += 1;
if (limit) |n| if (emitted >= n) return;
}
continue;
};
defer gpa.free(bytes);
if (!artifact.verify(hex, bytes)) return error.Corrupt;
// Read path: the log-walk reads fossil-origin history, so it tolerates
// the legacy F-card trailing separator.
var loaded = artifact.parseForImport(gpa, bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return if (is_root) error.InvalidRoot else error.InvalidTarget,
};
defer loaded.deinit(gpa);
const manifest = &loaded.manifest;
if (manifest.kind != .manifest)
return if (is_root) error.InvalidRoot else error.InvalidTarget;
// With no PATH the walk names every reachable check-in (B-log-1); with
// PATH it names only the check-ins whose effective content for PATH
// differs from their primary parent's (B-log-2), and, following, the
// check-in that renamed the file onto the name it follows.
var step: PathStep = .{ .hit = true };
if (filter) |f| {
// §3.2: the primary parent is the first hash of the first P card.
var primary: ?[]const u8 = null;
for (manifest.p) |pc| {
var hashes = pc.hashes();
if (hashes.next()) |p| {
primary = p;
break;
}
}
const primary_rid: ?repostate.Rid = if (primary) |p| f.repo.lookup(p) else null;
step = try pathStep(gpa, f, probe, f.repo.lookup(hex), primary_rid, entry.name, entry.on_file);
}
if (step.hit and !shown.contains(key[0..hex.len])) {
try shown.put(gpa, key[0..hex.len], {});
logEmit(out, hex, manifest, long, eventTimeOf(times, hex));
if (rows) |r| try r.add(&probe.names, hex, entry.name, step.prior);
emitted += 1;
if (limit) |n| if (emitted >= n) return;
}
if (step.stop) continue;
// Push in reverse wire order so the LIFO stack visits the first P hash
// first. Reversing only this node's appended segment preserves DFS when
// older sibling work is already below it.
const parent_name = step.prior orelse entry.name;
const on_file = entry.on_file or (step.known and step.present);
const parent_start = pending.items.len;
for (manifest.p) |pc| {
var hashes = pc.hashes();
while (hashes.next()) |parent| {
// Across a rename, a parent that lacks the old name ends the
// walk on that side (Fossil treats the file as new there).
if (step.prior != null) {
const f = filter.?;
const held = (try effectivePathContent(gpa, f.repo, probe, f.repo.lookup(parent), parent_name)).present;
if (!held) continue;
}
const owned = try gpa.dupe(u8, parent);
pending.append(gpa, .{ .id = owned, .name = parent_name, .on_file = on_file }) catch {
gpa.free(owned);
return error.OutOfMemory;
};
}
}
std.mem.reverse(Pending, pending.items[parent_start..]);
}
}
/// `plink` — walk the check-in DAG from DERIVED ADJACENCY instead of
/// re-parsing every manifest, which is what fossil does and what this walk
/// used to not do.
///
/// Fossil parses a manifest exactly ONCE, when it crosslinks it, and records
/// the edge in a persistent table:
///
/// CREATE TABLE plink(pid, cid, isprim, mtime, baseid, UNIQUE(pid,cid));
/// CREATE INDEX plink_i2 ON plink(cid,pid);
///
/// Every later traversal is an indexed query over that table -- `timeline.c`'s
/// ancestor walk is a recursive CTE reading `plink.cid ... WHERE plink.pid=dx.id`
/// and touches no manifest at all. The tell is fossil's parsed-manifest cache:
/// `#define MX_MANIFEST_CACHE 6`, six entries, and its comment says it is there
/// for `rebuild`. Nothing on fossil's read path re-parses manifests, so nothing
/// needed a cache big enough to make that fast.
///
/// zit's derived state holds the same relation -- `parents_by_child`, carrying
/// the `is_primary` flag `plink.isprim` carries -- and the zero-parse
/// image carries it too, so this walk reads no artifact content whatever.
///
/// WHAT THIS GIVES UP, stated plainly: the manifest walk verified every
/// reachable artifact's name hash and re-validated its card grammar, so a
/// corrupt frame or a wrong-ID blob surfaced as a `log` failure. This does not.
/// That is fossil's behaviour too -- validation happens once at crosslink, and
/// `fossil test-integrity` is the verb that re-checks a repository, exactly as
/// `zit verify` is here. Paying a full-history re-verification on every history
/// listing was the anomaly, not the guarantee.
///
/// Order is preserved exactly: depth-first, parents pushed in reverse wire
/// order so the LIFO stack visits the first P hash first, first visit winning
/// across a diamond. A parent the store never received is `phantom`, the same
/// line the manifest walk printed for it.
///
/// With a PATH that follows renames, a stack entry is a check-in under a
/// name: crossing the check-in that renamed the file, the parents are walked
/// under the old name, and the same check-in reached under another name is
/// visited again (a rename on a merged branch reaches the fork point under
/// both). Each check-in is still listed once, under the first name that
/// lists it.
pub fn walkLogDerived(
gpa: std.mem.Allocator,
repo: *Repository,
root_id: []const u8,
out: *std.Io.Writer,
limit: ?usize,
/// The PATH filter, answered from the file index. Null walks
/// everything (B-log-1).
filter: ?LogPathFilter,
/// `--long` needs each row's own D/U/C cards, and derived state keeps the
/// timestamp PARSED, not as the check-in wrote it. So a long row reads its
/// own manifest — one read per EMITTED row, a page of them, rather than
/// the per-visited-node read that made this verb slow. The bytes then come
/// from the same place the manifest walk printed them, which is what keeps
/// the line identical.
long: bool,
rows: ?*LogRows,
/// As `walkLog`'s.
shared: ?*PathProbe,
) LogWalkError!void {
const root_rid = repo.lookup(root_id) orelse return error.MissingRoot;
// A crosslinked check-in has an event row; a rid interned only because some
// P card named it does not. That is the derive's record of "we actually
// received this", and it is what distinguishes a check-in from a phantom
// here -- NOT the view's own store, whose `held` answers about the identity
// space rather than about artifact bytes.
if (repo.state().mtimeOf(root_rid) == null) return error.MissingRoot;
const Pending = struct { rid: repostate.Rid, name: NameId, on_file: bool };
var pending: std.ArrayList(Pending) = .empty;
defer pending.deinit(gpa);
var visited: std.AutoHashMapUnmanaged(NamedRid, void) = .empty;
defer visited.deinit(gpa);
var shown: std.AutoHashMapUnmanaged(repostate.Rid, void) = .empty;
defer shown.deinit(gpa);
var emitted: usize = 0;
var own_plaintext: logstore.PlaintextCache = .{};
defer own_plaintext.deinit(gpa);
var own_probe = PathProbe.init(gpa, &own_plaintext);
defer own_probe.deinit(gpa);
const probe = shared orelse &own_probe;
const plaintext = probe.plaintext;
var root_name: NameId = 0;
var root_on_file = false;
if (filter) |f| {
root_name = try probe.names.intern(gpa, f.path);
if (f.follow) root_on_file = (try effectivePathContent(gpa, repo, probe, root_rid, root_name)).present;
}
try pending.append(gpa, .{ .rid = root_rid, .name = root_name, .on_file = root_on_file });
while (pending.pop()) |entry| {
const rid = entry.rid;
if (limit) |n| std.debug.assert(emitted < n);
if ((try visited.getOrPut(gpa, .{ .rid = rid, .name = entry.name })).found_existing) continue;
// A rid interned from a P card that never arrived. The manifest walk
// reached the same verdict by failing to read its content.
if (repo.state().mtimeOf(rid) == null) {
// A PATH filter cannot assert that a phantom changes PATH — its
// effective set is unknowable — so it is skipped silently, which
// is what the manifest walk does. Unfiltered, it is named.
if (filter == null) {
out.print("phantom {s}\n", .{repo.hashOf(rid)}) catch {};
emitted += 1;
if (limit) |n| if (emitted >= n) return;
}
continue;
}
// A manifest is read ONLY for an emitted row under `--long`; the
// predicate reads through `fileAt`, and only for the check-ins the
// index names. Reading one per visited check-in is the cost the
// index removed.
var step: PathStep = .{ .hit = true };
if (filter) |f| {
step = try pathStep(gpa, f, probe, rid, repo.state().primaryParentOf(rid), entry.name, entry.on_file);
}
if (step.hit and !(try shown.getOrPut(gpa, rid)).found_existing) {
var owned: ?Repository.OwnedManifest = null;
defer if (owned) |*o| o.deinit(gpa);
if (long) {
owned = repo.manifestCached(gpa, rid, plaintext) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => null,
};
}
if (owned) |*o| {
logEmit(out, repo.hashOf(rid), &o.manifest, true, repo.state().mtimeOf(rid));
} else {
out.print("checkin {s}\n", .{repo.hashOf(rid)}) catch {};
}
if (rows) |r| try r.add(&probe.names, repo.hashOf(rid), entry.name, step.prior);
emitted += 1;
if (limit) |n| if (emitted >= n) return;
}
if (step.stop) continue;
// Push the parents for the LIFO stack, reversing only this node's
// own appended segment so the first P hash is visited first while
// older sibling work stays below it.
const parent_name = step.prior orelse entry.name;
const on_file = entry.on_file or (step.known and step.present);
const start = pending.items.len;
var it = repo.state().parentsOf(rid);
while (it.next()) |p| {
// Across a rename, a parent that lacks the old name ends the walk
// on that side (Fossil treats the file as new there).
if (step.prior != null) {
const held = if (repo.state().primaryParentOf(rid) == p)
step.parent_present
else
(try effectivePathContent(gpa, repo, probe, p, parent_name)).present;
if (!held) continue;
}
try pending.append(gpa, .{ .rid = p, .name = parent_name, .on_file = on_file });
}
std.mem.reverse(Pending, pending.items[start..]);
}
}
/// PATH's presence and effective content hash inside one check-in's file set.
/// The hash is a 40/64-char lowercase-hex F-card token (§4.7.6), copied into a
/// fixed buffer so the comparison outlives `fileAt`'s duped card. `prior` is
/// the card's own old name, which only the check-in that recorded a rename
/// carries (an inherited card never does).
pub const PathContent = struct {
present: bool,
hash: [2 * digest_len]u8 = undefined,
hash_len: usize = 0,
prior: ?NameId = null,
};
/// The memos the PATH predicate reads through. Two of them, because
/// the predicate repeats two different things:
///
/// * `plaintext` and `baseline` are the pair `annotate` already threads
/// through `fileAtMemo`. A check-in manifest is routinely stored as a
/// delta against its neighbour, so reconstructing one per `fileAt` call
/// re-resolves the SAME base chain per check-in, and a wide baseline is
/// re-parsed per check-in on top of that — the cost then grows with how
/// much history sits behind the node rather than with the node. The walk
/// built this memo for its own manifest reads and did not hand it to the
/// predicate, which is the part that runs twice per node.
/// * `content` memoizes the ANSWER by check-in and name. Every check-in is
/// asked for its content twice — once as `here` when it is visited, once
/// as `parent` when its child is — so in a mostly-linear history this
/// halves what is left. It is bounded by the nodes visited.
///
/// Neither changes what the predicate answers: both are pure memos over a
/// reconstruction that is a function of the store. `names` interns the names
/// a following walk meets.
pub const PathProbe = struct {
plaintext: *logstore.PlaintextCache,
baseline: ?*Repository.BaselineMemo = null,
content: std.AutoHashMapUnmanaged(NamedRid, PathContent) = .empty,
names: NameTable,
pub fn init(gpa: std.mem.Allocator, plaintext: *logstore.PlaintextCache) PathProbe {
return .{ .plaintext = plaintext, .names = NameTable.init(gpa) };
}
pub fn deinit(self: *PathProbe, gpa: std.mem.Allocator) void {
if (self.baseline) |b| b.deinit(gpa);
self.content.deinit(gpa);
self.names.deinit(gpa);
}
};
/// The effective content of `name` in check-in `rid` (artifact §8
/// reconstruction via `Repository.fileAt` — the one general-purpose query, so
/// no CLI-side re-derivation off raw F cards, B-log-5). `present` is false when
/// `rid` is null (a phantom the derived view never crosslinked) or the name
/// is not in its effective set (never added, or a delta delete marker §4.7.6).
pub fn effectivePathContent(
gpa: std.mem.Allocator,
repo: *Repository,
probe: *PathProbe,
rid: ?repostate.Rid,
name: NameId,
) LogWalkError!PathContent {
const r = rid orelse return .{ .present = false };
// Asked once as `here`, once as `parent` of the child below it.
if (probe.content.get(.{ .rid = r, .name = name })) |hit| return hit;
const answer = try effectivePathContentAt(gpa, repo, probe, r, name);
try probe.content.put(gpa, .{ .rid = r, .name = name }, answer);
return answer;
}
/// `effectivePathContent` past the memo: the actual §8 reconstruction for one
/// interned rid, through the caller's baseline and plaintext memos.
fn effectivePathContentAt(
gpa: std.mem.Allocator,
repo: *Repository,
probe: *PathProbe,
rid: repostate.Rid,
name: NameId,
) LogWalkError!PathContent {
const card = (repo.fileAtMemo(gpa, rid, probe.names.get(name), &probe.baseline, probe.plaintext) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead => error.Storage,
// NotManifest/BaselineUnresolvable/Corrupt/NotARepo all
// mean the reachable check-in cannot be reconstructed — the same class
// the unfiltered walk reports as a corrupt/invalid target.
else => error.Corrupt,
}) orelse return .{ .present = false };
defer Repository.freeFileCard(gpa, card);
// The iterator behind `fileAt` suppresses delete markers, so a returned
// card always carries a hash (§4.7.6).
const h = card.hash.?;
std.debug.assert(h.len <= 2 * digest_len);
var out: PathContent = .{ .present = true, .hash_len = h.len };
@memcpy(out.hash[0..h.len], h);
if (card.old_name) |old| out.prior = try probe.names.intern(gpa, old);
return out;
}
/// Set from `$ZIT_NO_FILE_INDEX` at the one environment seam in
/// `main`. The differential test drives the reconstructing answer through it.
pub var no_file_index: bool = false;
/// Evidence seam — how many check-ins the adopted file index recorded
/// as UNKNOWN (reconstructed per query rather than answered). On a tree-
/// manifest store this was the whole log, which is how an index that was
/// valid, adopted and never rebuilt still cost 39 minutes a query. Printed
/// by `main` under `ZIT_FILEINDEX_WALK`, beside the walk count. Null when
/// no index was adopted at all — printed as `none`, so a test asserting
/// zero unknowns cannot pass on a query that never consulted an index.
pub var file_index_unknown: ?usize = null;
/// The file index as a PATH walk reads it: the check-ins that changed each
/// name the walk follows, filled on first use, and every rename edge keyed by
/// check-in and name. All rids are DERIVED rids.
pub const PathIndex = struct {
repo: *Repository,
log: *logstore.LogStore,
/// Where the index is stored, so a damaged one can be rebuilt in place.
io: std.Io,
root_dir: std.Io.Dir,
/// Owned; `index` borrows it.
bytes: logstore.LogStore.IndexBytes,
index: fileindex.Index,
/// The names below are interned here, so the index is asked by string
/// and never shares ids with a walk's own table.
names: NameTable,
/// The check-ins whose change set the index could not know. They are
/// resolved ONE AT A TIME by reconstruction, rather than refusing the
/// whole index: a real corpus carries a handful (the SQLite mirror has
/// exactly one, a 2009 check-in whose parent is genuinely absent), and
/// discarding 32,000 answers over one of them is how an index ends up
/// built, stored, and never used.
unknown: std.AutoHashMapUnmanaged(repostate.Rid, void) = .empty,
changed: std.AutoHashMapUnmanaged(NameId, std.AutoHashMapUnmanaged(repostate.Rid, void)) = .empty,
/// (check-in, new name) -> old name: the check-in renamed the file onto
/// the new name from the old. Filled per name on first use, from the
/// edges the index finds for that name alone (`from_loaded`).
renamed_from: std.AutoHashMapUnmanaged(NamedRid, NameId) = .empty,
from_loaded: std.AutoHashMapUnmanaged(NameId, void) = .empty,
/// (check-in, old name): the check-in renamed a file away from the name,
/// filled per name on first use (`away_loaded`).
renamed_away: std.AutoHashMapUnmanaged(NamedRid, void) = .empty,
away_loaded: std.AutoHashMapUnmanaged(NameId, void) = .empty,
/// No trustworthy index could be had after a damaged block: every
/// question is left to the reconstructing walk from then on.
lost: bool = false,
pub fn deinit(self: *PathIndex, gpa: std.mem.Allocator) void {
var it = self.changed.valueIterator();
while (it.next()) |set| set.deinit(gpa);
self.changed.deinit(gpa);
self.unknown.deinit(gpa);
self.renamed_from.deinit(gpa);
self.from_loaded.deinit(gpa);
self.renamed_away.deinit(gpa);
self.away_loaded.deinit(gpa);
self.names.deinit(gpa);
self.index.deinit(gpa);
self.bytes.release(gpa);
}
/// Ask the index, through `method` (an `Index` lookup appending to
/// `out`). A lookup that finds a damaged block rebuilds the index from
/// the log, stores it, and asks again. Answers drawn earlier came from
/// blocks that checked, so the sets already filled stand. When no good
/// index can be had the answer is `error.Corrupt` and `lost` is set: the
/// walk then drops the index and reconstructs (`pathStep`).
fn ask(self: *PathIndex, gpa: std.mem.Allocator, comptime method: anytype, name: []const u8, out: anytype) error{ OutOfMemory, Corrupt }!void {
if (self.lost) return error.Corrupt;
method(&self.index, name, out, gpa) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => {
out.clearRetainingCapacity();
self.rebuild(gpa) catch |r| {
if (r == error.Corrupt) self.lost = true;
return r;
};
method(&self.index, name, out, gpa) catch |again| {
if (again == error.Corrupt) self.lost = true;
out.clearRetainingCapacity();
return again;
};
},
};
}
fn rebuild(self: *PathIndex, gpa: std.mem.Allocator) error{ OutOfMemory, Corrupt }!void {
var fresh = (try adoptOrBuild(gpa, self.io, self.root_dir, self.log, .rebuild)) orelse return error.Corrupt;
errdefer fresh.deinit(gpa);
var unknown: std.AutoHashMapUnmanaged(repostate.Rid, void) = .empty;
errdefer unknown.deinit(gpa);
try fillUnknown(gpa, self.repo, self.log, &fresh.index, &unknown);
self.index.deinit(gpa);
self.bytes.release(gpa);
self.unknown.deinit(gpa);
self.bytes = fresh.bytes;
self.index = fresh.index;
self.unknown = unknown;
}
/// The check-ins the index says changed `name`.
pub fn changedSet(self: *PathIndex, gpa: std.mem.Allocator, name: []const u8) error{ OutOfMemory, Corrupt }!*const std.AutoHashMapUnmanaged(repostate.Rid, void) {
const id = try self.names.intern(gpa, name);
if (self.changed.getPtr(id)) |set| return set;
// Asked before anything is cached, so a failed ask leaves no entry
// that would later read as "no check-in changed it".
var rids: std.ArrayListUnmanaged(u32) = .empty;
defer rids.deinit(gpa);
try self.ask(gpa, fileindex.Index.changedBy, name, &rids);
var set: std.AutoHashMapUnmanaged(repostate.Rid, void) = .empty;
errdefer set.deinit(gpa);
for (rids.items) |r| {
if (ridOfLogRid(self.repo, self.log, r)) |view_rid| try set.put(gpa, view_rid, {});
}
const gop = try self.changed.getOrPut(gpa, id);
std.debug.assert(!gop.found_existing);
gop.value_ptr.* = set;
return gop.value_ptr;
}
/// The name check-in `rid` renamed `name` from, if it recorded a rename.
/// Only `name`'s own edges are read, by bisection, the first time it is
/// asked: a walk pays for the renames of the file it follows, not for
/// every rename the repository holds.
pub fn priorOf(self: *PathIndex, gpa: std.mem.Allocator, rid: repostate.Rid, name: []const u8) error{ OutOfMemory, Corrupt }!?[]const u8 {
const id = try self.names.intern(gpa, name);
if (!self.from_loaded.contains(id)) {
var edges: std.ArrayListUnmanaged(fileindex.Edge) = .empty;
defer edges.deinit(gpa);
try self.ask(gpa, fileindex.Index.renamesInto, name, &edges);
for (edges.items) |e| {
const view_rid = ridOfLogRid(self.repo, self.log, e.rid) orelse continue;
const old = try self.names.intern(gpa, e.old);
try self.renamed_from.put(gpa, .{ .rid = view_rid, .name = id }, old);
}
// Marked only once its edges are in: a failed ask must not
// leave the name reading as "never renamed onto".
try self.from_loaded.put(gpa, id, {});
}
const old = self.renamed_from.get(.{ .rid = rid, .name = id }) orelse return null;
return self.names.get(old);
}
/// Whether no check-in ever held `name`, so a PATH walk has nothing to
/// find. A file present anywhere was added by some check-in, which then
/// names it in its change set or is UNKNOWN; so it is enough that no change
/// set names it, no rename leads onto it, and no unknown check-in holds it.
/// The unknown check-ins asked are those the derived view can place; one
/// it cannot, the walk could not visit either. A phantom filled after the
/// index was built is neither known nor unknown, which the walk this
/// replaces never saw either. Any doubt answers false and the walk decides.
pub fn neverHeld(self: *PathIndex, gpa: std.mem.Allocator, name: []const u8) error{ OutOfMemory, Corrupt }!bool {
var rids: std.ArrayListUnmanaged(u32) = .empty;
defer rids.deinit(gpa);
try self.ask(gpa, fileindex.Index.changedBy, name, &rids);
if (rids.items.len != 0) return false;
var edges: std.ArrayListUnmanaged(fileindex.Edge) = .empty;
defer edges.deinit(gpa);
try self.ask(gpa, fileindex.Index.renamesInto, name, &edges);
if (edges.items.len != 0) return false;
// Each unknown check-in costs a read; past a handful the walk, which
// reconstructs them anyway, is no slower than asking here.
if (self.unknown.count() > max_unknown_probed) return false;
var it = self.unknown.keyIterator();
while (it.next()) |rid| {
const card = self.repo.fileAt(gpa, rid.*, name) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return false,
};
if (card) |c| {
Repository.freeFileCard(gpa, c);
return false;
}
}
return true;
}
const max_unknown_probed = 64;
/// Whether check-in `rid` renamed a file away from `name`, read the
/// first time `name` is asked.
fn renamedAway(self: *PathIndex, gpa: std.mem.Allocator, rid: repostate.Rid, name: []const u8) error{ OutOfMemory, Corrupt }!bool {
const id = try self.names.intern(gpa, name);
if (!self.away_loaded.contains(id)) {
var edges: std.ArrayListUnmanaged(fileindex.Edge) = .empty;
defer edges.deinit(gpa);
try self.ask(gpa, fileindex.Index.renamesFrom, name, &edges);
for (edges.items) |e| {
const view_rid = ridOfLogRid(self.repo, self.log, e.rid) orelse continue;
try self.renamed_away.put(gpa, .{ .rid = view_rid, .name = id }, {});
}
try self.away_loaded.put(gpa, id, {});
}
return self.renamed_away.contains(.{ .rid = rid, .name = id });
}
};
/// The file index for a PATH walk, or null when it cannot be trusted and the
/// walk must reconstruct the predicate.
///
/// Adopt-or-build, the shape every other `.zit-cache` member uses: a blob whose
/// key and shun fingerprint still validate is used as it stands; anything else
/// is rebuilt by one `repoview.eachChangeSet` pass and stored. The store is
/// advisory — a write that fails costs the next query a rebuild and nothing
/// else.
///
/// A check-in whose change set is UNKNOWN (a tree manifest, an absent or
/// shunned parent, an unresolvable baseline) is recorded in `unknown` and
/// reconstructed individually by the walk. Dropping such a check-in from the
/// index's answer would silently drop it from a file's history — a wrong
/// answer rather than a slow one.
pub fn loadPathIndex(
gpa: std.mem.Allocator,
io: std.Io,
root_dir: std.Io.Dir,
repo: *Repository,
log: *logstore.LogStore,
) error{OutOfMemory}!?PathIndex {
// A test seam, and the operator's escape hatch: set, the query is answered
// by reconstruction alone, which is what the differential test compares
// the indexed answer against. Read from the environment in `main` and set
// here, never read in a runner: that is the design-seams rule, and reading
// it through libc also made the build refuse on any target that does not
// link libc (every Linux runner, while macOS links it always).
if (no_file_index) return null;
const got = (try adoptOrBuild(gpa, io, root_dir, log, .adopt)) orelse return null;
var out: PathIndex = .{
.repo = repo,
.log = log,
.io = io,
.root_dir = root_dir,
.bytes = got.bytes,
.index = got.index,
.names = NameTable.init(gpa),
};
errdefer out.deinit(gpa);
fillUnknown(gpa, repo, log, &out.index, &out.unknown) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
// The unknown rids sit in a damaged block: rebuild from the log.
error.Corrupt => out.rebuild(gpa) catch |r| switch (r) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => {
out.deinit(gpa);
return null;
},
},
};
file_index_unknown = out.index.unknownCount();
return out;
}
const Adopted = struct {
bytes: logstore.LogStore.IndexBytes,
index: fileindex.Index,
fn deinit(self: *Adopted, gpa: std.mem.Allocator) void {
self.index.deinit(gpa);
self.bytes.release(gpa);
}
};
/// The view rids of the check-ins the index could not know.
fn fillUnknown(
gpa: std.mem.Allocator,
repo: *Repository,
log: *logstore.LogStore,
index: *fileindex.Index,
unknown: *std.AutoHashMapUnmanaged(repostate.Rid, void),
) fileindex.ReadError!void {
var u: usize = 0;
while (u < index.unknownCount()) : (u += 1) {
if (ridOfLogRid(repo, log, try index.unknownAt(u))) |view_rid| try unknown.put(gpa, view_rid, {});
}
}
/// The stored index if it validates (`.adopt`), extended over any tail the
/// log has grown since; otherwise, or always under `.rebuild` (a lookup
/// found a damaged block), one built from the log and stored. Null when no
/// index can be built: an empty log, or one past the codec's limits.
fn adoptOrBuild(
gpa: std.mem.Allocator,
io: std.Io,
root_dir: std.Io.Dir,
log: *logstore.LogStore,
mode: enum { adopt, rebuild },
) error{OutOfMemory}!?Adopted {
var held: ?logstore.LogStore.IndexBytes = if (mode == .adopt) repocache.mapFileIndex(io, root_dir) else null;
defer if (held) |*h| h.release(gpa);
var idx: ?fileindex.Index = if (held) |*h| try fileindex.parse(gpa, h.bytes(), log) else null;
defer if (idx) |*i| i.deinit(gpa);
var covered: u64 = if (idx) |i| i.n_rids else 0;
const want: u64 = @intCast(log.entryCount());
// Three cases, and only the first two cost anything. An index that
// already covers the log is used as it stands; one that covers a prefix
// is EXTENDED over the appended tail; anything else is built once.
// Rebuilding on every append is what made a commit cost a full pass.
if (idx != null and covered >= want) {
const out: Adopted = .{ .bytes = held.?, .index = idx.? };
held = null;
idx = null;
return out;
}
var builder = fileindex.Builder.init(gpa);
defer builder.deinit();
if (idx) |*i| builder.absorb(i) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
// A damaged stored index: discard it and build from the start.
error.Corrupt => {
builder.deinit();
builder = fileindex.Builder.init(gpa);
covered = 0;
},
};
// The derive builds this index as it captures, so this is the fallback
// for a store whose cache predates that. Walked in bounded chunks, each
// checkpointed: a build a restart interrupts resumes from the last
// chunk instead of from zero, so a forge that restarts more often than
// the whole build takes still converges.
// Known limit of this fallback, and the reason the derive-built index
// is primary: coverage here is by entry count, so a phantom filled
// after a build (its rid already below the count) is never revisited
// by a later resume. The derive walks by frame offset and re-covers it.
const chunk: u64 = 8192;
var fresh: ?[]u8 = null;
defer if (fresh) |f| gpa.free(f);
while (covered < want) {
const upto: u64 = @min(covered + chunk, want);
try repoview.eachChangeSet(gpa, log, @intCast(covered), @intCast(upto), builder.sink());
const blob = (try fileindex.serialize(gpa, log, &builder, upto)) orelse return null;
repocache.storeFileIndex(io, root_dir, blob);
if (fresh) |f| gpa.free(f);
fresh = blob;
covered = upto;
}
// Nothing walked: an empty log has nothing to index. A stored index
// already covering it was returned above.
const final = fresh orelse return null;
const index = (try fileindex.parse(gpa, final, log)) orelse return null;
fresh = null;
return .{ .bytes = .{ .heap = final }, .index = index };
}
/// Translate a LOG rid (a frame index, which is what the file index stores)
/// into the DERIVED rid the walk uses. The two spaces are not the same — the
/// derived space interns phantoms a P card named and orders by first sight —
/// so comparing one to the other silently matches unrelated check-ins. The
/// artifact name is the identity both agree on.
pub fn ridOfLogRid(repo: *Repository, log: *logstore.LogStore, log_rid: u32) ?repostate.Rid {
const digest = log.hashOf(@intCast(log_rid));
const hex: []const u8 = if (digest.len == 32)
&std.fmt.bytesToHex(digest[0..32].*, .lower)
else if (digest.len == 20)
&std.fmt.bytesToHex(digest[0..20].*, .lower)
else
return null;
return repo.lookup(hex);
}
/// What a PATH walk is asked: the file, how many rows (`-n`), whether rows
/// carry their D/U/C cards (`--long`), and whether renames are followed.
pub const PathQuery = struct {
path: []const u8,
limit: ?usize = null,
/// Rows skipped before the first listed, after any resume point
/// (`--offset`).
offset: usize = 0,
long: bool = false,
follow: bool = true,
};
/// `zit log ROOT PATH`'s walk, writing its text lines to `out` and, when
/// `rows` is given, its rows there too. The predicate is answered from
/// `index` when one is given; the derived adjacency is walked when the root
/// is crosslinked, and the manifest walk otherwise.
pub fn walkPath(
gpa: std.mem.Allocator,
repo: *Repository,
log: *logstore.LogStore,
index: ?*PathIndex,
root_id: []const u8,
q: PathQuery,
out: *std.Io.Writer,
rows: ?*LogRows,
/// Kept by the caller so each row's facts reuse the walk's reads.
probe: *PathProbe,
) LogWalkError!void {
const filter: LogPathFilter = .{
.repo = repo,
.path = q.path,
.follow = q.follow,
.index = index,
};
// Traverse the DERIVED adjacency, exactly as the unfiltered walk
// does: same phantom line, and no
// artifact content read for traversal. With the predicate answered from
// the index, that leaves nothing per visited check-in at all — the reads
// that remain are one per EMITTED row under `--long`. The manifest walk
// stays as the fallback for a root the derived state cannot resolve.
const derived = repo.lookup(root_id) != null and repo.state().mtimeOf(repo.lookup(root_id).?) != null;
// A following walk reads each check-in's file list until it meets the
// file, so a name no check-in ever held would be read for in every
// ancestor. The answer there is no rows, known without walking.
if (derived) if (index) |ix| {
// A lost index answers "don't know", and the walk decides.
const never = ix.neverHeld(gpa, q.path) catch |e| switch (e) {
error.Corrupt => if (ix.lost) false else return e,
else => return e,
};
if (never) return;
};
if (derived) if (index) |ix| if (!ix.lost)
return walkPathIndexed(gpa, repo, ix, root_id, q, out, rows, probe);
// The walk's order is traversal order: first parents depth-first, side
// branches after. Fossil lists a file's history by check-in time
// (`finfo`: ORDER BY event.mtime DESC), and `-n` with a cursor pages
// only if the order is a total one fixed by the rows themselves, so the
// whole set is collected, then ordered as `timeline` orders check-ins.
// A merge walk on a time-keyed queue could stop after N rows, but only
// if no parent were ever newer than its child; clock skew breaks that,
// and Fossil's sort does not assume it. Without an index every row is
// decided while walking anyway, so the whole set is decided here.
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
var all: LogRows = .{ .arena = arena_state.allocator() };
var discard: std.Io.Writer.Discarding = .init(&.{});
if (derived)
try walkLogDerived(gpa, repo, root_id, &discard.writer, null, filter, false, &all, probe)
else
try walkLog(gpa, log, root_id, &discard.writer, filter, null, false, repo, &all, probe);
const sorted = try newestFirst(gpa, arena_state.allocator(), repo, derived, all.rows.items, probe.plaintext);
var start: usize = 0;
if (rows) |r| if (r.after) |resume_at| {
for (sorted, 0..) |row, i| {
if (std.mem.eql(u8, row.id, resume_at)) {
start = i + 1;
r.after = null;
break;
}
} else return;
};
start = @min(sorted.len, start + q.offset);
const end = if (q.limit) |n| @min(sorted.len, start + n) else sorted.len;
for (sorted[start..end]) |row| {
try emitRow(gpa, repo, out, row.id, q.long, probe.plaintext);
if (rows) |r| try r.rows.append(r.arena, .{
.id = try r.arena.dupe(u8, row.id),
.name = try r.arena.dupe(u8, row.name),
.prior = if (row.prior) |p| try r.arena.dupe(u8, p) else null,
});
}
}
/// One (check-in, name) pair the indexed walk met that may list the
/// check-in. `next` chains the same check-in's later visits in walk order,
/// so the first visit that lists it names the row, as `shown` decides in
/// the walk this mirrors.
const Visit = struct {
name: NameId,
prior: ?NameId,
state: enum { pending, hit, miss },
next: ?u32 = null,
};
/// `walkPath` over derived state with a usable file index, at a cost that
/// follows the page rather than the history. It is the walk
/// `walkLogDerived` makes, with one difference: a step whose answer cannot
/// steer the traversal is not decided where it is met. That is a check-in
/// the index names for the name walked, when renames are not followed, or
/// when they are, the walk has met the file and the index records no
/// rename onto or away from the name there. Then `pathStep` can neither
/// stop the walk nor change the name below it, so whether the check-in is
/// a row is a fact of the check-in and the name alone. Every other step
/// (unknown check-ins, rename edges, the stretch above where the file is
/// first met) is decided in place, exactly as before.
///
/// Fossil's `finfo` reads its per-file mlink rows by mtime; here the
/// candidates are ordered once as `timeline` orders check-ins, and the
/// deferred ones are decided in that order only until the page is full.
/// The order is a total one on (time, generation, hash), so ordering the
/// candidates and dropping the ones that are not rows gives the order the
/// rows alone would have.
fn walkPathIndexed(
gpa: std.mem.Allocator,
repo: *Repository,
ix: *PathIndex,
root_id: []const u8,
q: PathQuery,
out: *std.Io.Writer,
rows: ?*LogRows,
probe: *PathProbe,
) LogWalkError!void {
const filter: LogPathFilter = .{ .repo = repo, .path = q.path, .follow = q.follow, .index = ix };
const root_rid = repo.lookup(root_id).?;
const state = repo.state();
std.debug.assert(state.mtimeOf(root_rid) != null);
var visits: std.ArrayListUnmanaged(Visit) = .empty;
defer visits.deinit(gpa);
const Chain = struct { head: u32, tail: u32 };
var chains: std.AutoHashMapUnmanaged(repostate.Rid, Chain) = .empty;
defer chains.deinit(gpa);
var candidates: std.ArrayListUnmanaged(repostate.Rid) = .empty;
defer candidates.deinit(gpa);
const Pending = struct { rid: repostate.Rid, name: NameId, on_file: bool };
var pending: std.ArrayListUnmanaged(Pending) = .empty;
defer pending.deinit(gpa);
var visited: std.AutoHashMapUnmanaged(NamedRid, void) = .empty;
defer visited.deinit(gpa);
const root_name = try probe.names.intern(gpa, q.path);
const root_on_file = q.follow and (try effectivePathContent(gpa, repo, probe, root_rid, root_name)).present;
try pending.append(gpa, .{ .rid = root_rid, .name = root_name, .on_file = root_on_file });
while (pending.pop()) |entry| {
const rid = entry.rid;
if ((try visited.getOrPut(gpa, .{ .rid = rid, .name = entry.name })).found_existing) continue;
// A phantom: its effective set is unknowable, so it is no row, and
// derived state records no parents to walk below it.
if (state.mtimeOf(rid) == null) continue;
var step: PathStep = .{};
var visit: ?Visit = null;
if (try deferrable(gpa, ix, filter, probe, rid, entry.name, entry.on_file)) {
visit = .{ .name = entry.name, .prior = null, .state = .pending };
} else {
step = try pathStep(gpa, filter, probe, rid, state.primaryParentOf(rid), entry.name, entry.on_file);
if (step.hit) visit = .{ .name = entry.name, .prior = step.prior, .state = .hit };
}
if (visit) |v| {
const at: u32 = @intCast(visits.items.len);
try visits.append(gpa, v);
const gop = try chains.getOrPut(gpa, rid);
if (gop.found_existing) {
visits.items[gop.value_ptr.tail].next = at;
gop.value_ptr.tail = at;
} else {
gop.value_ptr.* = .{ .head = at, .tail = at };
try candidates.append(gpa, rid);
}
}
if (step.stop) continue;
const parent_name = step.prior orelse entry.name;
const on_file = entry.on_file or (step.known and step.present);
const start = pending.items.len;
var it = state.parentsOf(rid);
while (it.next()) |p| {
if (step.prior != null) {
const held = if (state.primaryParentOf(rid) == p)
step.parent_present
else
(try effectivePathContent(gpa, repo, probe, p, parent_name)).present;
if (!held) continue;
}
try pending.append(gpa, .{ .rid = p, .name = parent_name, .on_file = on_file });
}
std.mem.reverse(Pending, pending.items[start..]);
}
try state.sortTimeline(gpa, candidates.items);
const Resolver = struct {
gpa: std.mem.Allocator,
filter: LogPathFilter,
probe: *PathProbe,
visits: []Visit,
chains: *const std.AutoHashMapUnmanaged(repostate.Rid, Chain),
/// The visit that lists `rid`, deciding deferred ones as needed.
fn row(self: @This(), rid: repostate.Rid) LogWalkError!?*const Visit {
var at: ?u32 = self.chains.get(rid).?.head;
while (at) |i| : (at = self.visits[i].next) {
const v = &self.visits[i];
if (v.state == .pending) {
try self.seedParent(rid, v.name);
const step = try pathStep(self.gpa, self.filter, self.probe, rid, self.filter.repo.state().primaryParentOf(rid), v.name, true);
std.debug.assert(!step.stop);
v.prior = step.prior;
v.state = if (step.hit) .hit else .miss;
}
if (v.state == .hit) return v;
}
return null;
}
/// The primary parent's content for `name`, without reading the
/// parent: walking primary parents down from it, the first check-in
/// the index names for `name` holds what the parent holds, since
/// every check-in above it changed nothing there against its own
/// primary parent — the direction the walk already trusts. That
/// check-in is usually the next row, read anyway, so a page reads
/// about one manifest per row instead of two. An unknown check-in,
/// a phantom, or a long gap leaves the parent to be read.
fn seedParent(self: @This(), rid: repostate.Rid, name: NameId) LogWalkError!void {
const store = self.filter.repo;
const index = self.filter.index.?;
const view = store.state();
const parent = view.primaryParentOf(rid) orelse return;
const key: NamedRid = .{ .rid = parent, .name = name };
if (self.probe.content.contains(key)) return;
const set = index.changedSet(self.gpa, self.probe.names.get(name)) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => return,
};
var at = parent;
var steps: usize = 0;
while (steps < max_seed_steps) : (steps += 1) {
if (view.mtimeOf(at) == null or index.unknown.contains(at)) return;
if (set.contains(at)) {
var held = try effectivePathContent(self.gpa, store, self.probe, at, name);
// A rename is recorded only where it was made, which is
// a check-in the index names; the parent is not one.
held.prior = null;
try self.probe.content.put(self.gpa, key, held);
return;
}
// A root the index does not name never held the name.
at = view.primaryParentOf(at) orelse {
try self.probe.content.put(self.gpa, key, .{ .present = false });
return;
};
}
}
const max_seed_steps = 256;
};
const resolver: Resolver = .{ .gpa = gpa, .filter = filter, .probe = probe, .visits = visits.items, .chains = &chains };
var start: usize = 0;
if (rows) |r| if (r.after) |resume_at| {
const after_rid = repo.lookup(resume_at) orelse return;
const at = std.mem.indexOfScalar(repostate.Rid, candidates.items, after_rid) orelse return;
if ((try resolver.row(after_rid)) == null) return;
start = at + 1;
r.after = null;
};
var emitted: usize = 0;
var skipped: usize = 0;
for (candidates.items[start..]) |rid| {
if (q.limit) |n| if (emitted >= n) break;
const v = (try resolver.row(rid)) orelse continue;
if (skipped < q.offset) {
skipped += 1;
continue;
}
const id = repo.hashOf(rid);
try emitRow(gpa, repo, out, id, q.long, probe.plaintext);
if (rows) |r| try r.rows.append(r.arena, .{
.id = try r.arena.dupe(u8, id),
.name = try r.arena.dupe(u8, probe.names.get(v.name)),
.prior = if (v.prior) |p| try r.arena.dupe(u8, probe.names.get(p)) else null,
});
emitted += 1;
}
}
/// Whether the indexed walk may leave the step at (`rid`, `name`) for later:
/// see `walkPathIndexed`. Any doubt, an index fault included, answers
/// false and the step is decided where it is met.
fn deferrable(
gpa: std.mem.Allocator,
ix: *PathIndex,
f: LogPathFilter,
probe: *PathProbe,
rid: repostate.Rid,
name: NameId,
on_file: bool,
) error{OutOfMemory}!bool {
if (ix.lost or ix.unknown.contains(rid)) return false;
// Until the walk meets the file, a check-in's presence decides whether a
// later rename away stops it.
if (f.follow and !on_file) return false;
const text = probe.names.get(name);
const set = ix.changedSet(gpa, text) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => false,
};
// Not a candidate: `pathStep` answers it from the index without reading.
if (!set.contains(rid)) return false;
if (!f.follow) return true;
const prior = ix.priorOf(gpa, rid, text) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => false,
};
if (prior != null) return false;
const away = ix.renamedAway(gpa, rid, text) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => false,
};
return !away;
}
/// `rows`, newest first. With derived state every row is a crosslinked
/// check-in and orders exactly as `timeline` lists it; the manifest walk's
/// rows, which derived state may not know, order by their D cards, then
/// by hash.
fn newestFirst(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
derived: bool,
rows: []const LogRow,
plaintext: *logstore.PlaintextCache,
) LogWalkError![]const LogRow {
if (derived) {
var by_rid: std.AutoHashMapUnmanaged(repostate.Rid, LogRow) = .empty;
defer by_rid.deinit(gpa);
const rids = try arena.alloc(repostate.Rid, rows.len);
for (rows, rids) |row, *rid| {
rid.* = repo.lookup(row.id).?;
try by_rid.putNoClobber(gpa, rid.*, row);
}
try repo.state().sortTimeline(gpa, rids);
const out = try arena.alloc(LogRow, rows.len);
for (rids, out) |rid, *row| row.* = by_rid.get(rid).?;
return out;
}
const Keyed = struct { row: LogRow, time: repostate.Mtime };
const keyed = try arena.alloc(Keyed, rows.len);
for (rows, keyed) |row, *k| {
const time = eventTimeOf(repo, row.id) orelse blk: {
const bytes = (repo.blobCached(gpa, row.id, plaintext) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead => error.Storage,
else => error.Corrupt,
}) orelse return error.Corrupt;
defer gpa.free(bytes);
var loaded = artifact.parseForImport(gpa, bytes) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
else => error.InvalidTarget,
};
defer loaded.deinit(gpa);
const d = loaded.manifest.d orelse return error.InvalidTarget;
break :blk repostate.parseMtime(d.timestamp) orelse return error.InvalidTarget;
};
k.* = .{ .row = row, .time = time };
}
std.mem.sort(Keyed, keyed, {}, struct {
fn lessThan(_: void, a: Keyed, b: Keyed) bool {
if (a.time != b.time) return a.time > b.time;
return std.mem.order(u8, a.row.id, b.row.id) == .lt;
}
}.lessThan);
const out = try arena.alloc(LogRow, rows.len);
for (keyed, out) |k, *row| row.* = k.row;
return out;
}
/// One listed check-in's text line. `--long` reads its manifest, one read
/// per row printed; a manifest that cannot be read prints the short line,
/// as the walk over derived state always has.
fn emitRow(gpa: std.mem.Allocator, repo: *Repository, out: *std.Io.Writer, id: []const u8, long: bool, plaintext: *logstore.PlaintextCache) LogWalkError!void {
if (long) if (repo.lookup(id)) |rid| {
var owned = repo.manifestCached(gpa, rid, plaintext) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => null,
};
if (owned) |*o| {
defer o.deinit(gpa);
logEmit(out, id, &o.manifest, true, repo.state().mtimeOf(rid));
return;
}
} else {
// A root derived state never crosslinked: the manifest walk's rows,
// whose manifests it has already read and verified.
const bytes = (repo.blobCached(gpa, id, plaintext) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.CannotRead => error.Storage,
else => error.Corrupt,
}) orelse return error.Corrupt;
defer gpa.free(bytes);
var loaded = artifact.parseForImport(gpa, bytes) catch |e| return switch (e) {
error.OutOfMemory => error.OutOfMemory,
else => error.InvalidTarget,
};
defer loaded.deinit(gpa);
logEmit(out, id, &loaded.manifest, true, null);
return;
};
out.print("checkin {s}\n", .{id}) catch {};
}
/// One listed check-in as `log CHECKIN PATH -F json` describes it. Field
/// names and change words are Fossil's (`json_finfo.c`): `uuid` is the
/// file's content in the check-in, `parent` its content in the primary
/// parent, `state` one of added, modified, removed — a pure rename is
/// `modified`, as there. `name` is the file's name in that check-in, which
/// differs from the queried path below a rename, and `prior` is the name a
/// rename row moved it from. A version whose content is absent by policy
/// has a null `size` and names why in `content`.
pub const Entry = struct {
checkin: []const u8,
name: []const u8,
prior: ?[]const u8,
uuid: ?[]const u8,
parent: ?[]const u8,
state: []const u8,
time_ms: ?repostate.Mtime,
user: ?[]const u8,
comment: ?[]const u8,
size: ?u64,
/// Purged, shunned or elided; null whenever the content is here.
content: ?feed.Absence,
};
/// Why a blob the store names is not here, as the caller can tell: the
/// cone and horizon classifier lives with the sync machinery.
pub const Classify = struct {
ctx: ?*anyopaque = null,
absence: *const fn (ctx: ?*anyopaque, hash: []const u8) feed.Absence,
};
/// The facts of one row the walk listed. Strings live on `arena`. Content
/// missing for no recorded reason is damage: `error.Corrupt`.
pub fn entryOf(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
probe: *PathProbe,
row: LogRow,
classify: Classify,
) !Entry {
const id = row.id;
const facts = try cardFactsOf(gpa, arena, repo, probe, id);
const name = try probe.names.intern(gpa, row.name);
const parent_name = try probe.names.intern(gpa, row.prior orelse row.name);
const here = try effectivePathContent(gpa, repo, probe, repo.lookup(id), name);
const before: PathContent = if (facts.primary) |pid| try effectivePathContent(gpa, repo, probe, pid, parent_name) else .{ .present = false };
var size: ?u64 = null;
var content: ?feed.Absence = null;
if (here.present) {
const hash = here.hash[0..here.hash_len];
// The size is in the frame; the version itself need not be rebuilt.
if (try repo.blobSize(gpa, hash)) |n| {
size = n;
} else {
// A version purged, shunned or elided by a cone is still part
// of the history; only its size is unknown. Content missing
// for no recorded reason is damage and keeps failing.
const why = classify.absence(classify.ctx, hash);
if (why == .missing) return error.Corrupt;
content = why;
}
}
return .{
.checkin = try arena.dupe(u8, id),
.name = try arena.dupe(u8, row.name),
.prior = if (row.prior) |p| try arena.dupe(u8, p) else null,
.uuid = if (here.present) try arena.dupe(u8, here.hash[0..here.hash_len]) else null,
.parent = if (before.present) try arena.dupe(u8, before.hash[0..before.hash_len]) else null,
.state = if (!before.present) "added" else if (!here.present) "removed" else "modified",
.time_ms = if (repo.lookup(id)) |rid| repo.state().mtimeOf(rid) else null,
.user = facts.user,
.comment = facts.comment,
.size = size,
.content = content,
};
}
/// A row's own cards: its U login, its C comment, and its §3.2 primary
/// parent (null for a root, or a parent the view never interned).
const CardFacts = struct { user: ?[]const u8, comment: ?[]const u8, primary: ?repostate.Rid };
/// `CardFacts` for check-in `id`, from derived state when it crosslinked
/// the check-in, which records the same cards the manifest carries; a page
/// then reads no manifest a row's decision did not already read. State
/// answers "" both for a manifest without a C card and for an empty
/// comment, which JSON tells apart, so only then is the manifest read.
fn cardFactsOf(gpa: std.mem.Allocator, arena: std.mem.Allocator, repo: *Repository, probe: *PathProbe, id: []const u8) !CardFacts {
const state = repo.state();
if (repo.lookup(id)) |rid| if (state.mtimeOf(rid) != null) {
if (state.userOf(rid)) |user| if (state.commentOf(rid)) |comment| if (comment.len != 0) {
return .{
// A U card's login is never empty (a bare U is anonymous),
// so "" is a manifest without one.
.user = if (user.len == 0) null else try arena.dupe(u8, user),
.comment = try arena.dupe(u8, comment),
.primary = state.primaryParentOf(rid),
};
};
};
// Neighbouring check-ins are stored as deltas of each other: the page's
// plaintext memo rebuilds each chain once, not once per row.
const bytes = (try repo.blobCached(gpa, id, probe.plaintext)) orelse return error.Corrupt;
defer gpa.free(bytes);
var loaded = try artifact.parseForImport(gpa, bytes);
defer loaded.deinit(gpa);
const m = &loaded.manifest;
var primary: ?[]const u8 = null;
for (m.p) |pc| {
var hashes = pc.hashes();
if (hashes.next()) |first| {
primary = first;
break;
}
}
return .{
.user = if (m.u) |u| try arena.dupe(u8, u.login) else null,
.comment = if (m.c) |c| try arena.dupe(u8, c.comment) else null,
.primary = if (primary) |pid| repo.lookup(pid) else null,
};
}
pub const TextWriter = fn (jw: *std.json.Stringify, s: []const u8) std.json.Stringify.Error!void;
/// A string as `std.json.Stringify` writes it.
pub fn plainText(jw: *std.json.Stringify, s: []const u8) std.json.Stringify.Error!void {
return jw.write(s);
}
/// One row as a JSON object, in `log -F json`'s field order. `text` writes
/// the strings the store holds (names, user, comment), which need not be
/// UTF-8: the CLI writes them as they are, the daemon as valid JSON.
pub fn writeEntry(jw: *std.json.Stringify, e: Entry, comptime text: TextWriter) std.json.Stringify.Error!void {
const opt = struct {
fn write(w: *std.json.Stringify, s: ?[]const u8) std.json.Stringify.Error!void {
if (s) |v| return text(w, v);
return w.write(null);
}
}.write;
try jw.beginObject();
try jw.objectField("checkin");
try jw.write(e.checkin);
try jw.objectField("name");
try text(jw, e.name);
try jw.objectField("prior");
try opt(jw, e.prior);
try jw.objectField("uuid");
try jw.write(e.uuid);
try jw.objectField("parent");
try jw.write(e.parent);
try jw.objectField("state");
try jw.write(e.state);
try jw.objectField("time");
if (e.time_ms) |t| {
var buf: [24]u8 = undefined;
try jw.write(rfc3339Millis(&buf, t));
} else try jw.write(null);
try jw.objectField("user");
try opt(jw, e.user);
try jw.objectField("comment");
try opt(jw, e.comment);
try jw.objectField("size");
try jw.write(e.size);
if (e.content) |why| {
try jw.objectField("content");
try jw.write(switch (why) {
.purged => "purged",
.shunned => "shunned",
.elided => "elided",
.missing => unreachable, // `entryOf` refuses it as damage
});
}
try jw.endObject();
}
/// `mt` (milliseconds since the epoch) as RFC 3339 UTC with milliseconds.
pub fn rfc3339Millis(buf: *[24]u8, mt: repostate.Mtime) []const u8 {
var iso_buf: [19]u8 = undefined;
const secs = artifact.formatWriterTimestamp(@intCast(@divFloor(mt, 1000)), &iso_buf);
return std.fmt.bufPrint(buf, "{s}.{d:0>3}Z", .{ secs, @as(u64, @intCast(@mod(mt, 1000))) }) catch unreachable; // 19 + 5 bytes
}
// ---------------------------------------------------------------------------
// Paging, for a resident reader
/// One page of a file's history and where the next one starts.
pub const Page = struct {
entries: []const Entry,
/// Null when nothing follows this page.
cursor: ?[]const u8,
};
/// A page cursor: the check-in the walk started from, then the last row
/// listed. Rows are unique per check-in, so the last row's check-in alone
/// says where to resume; carrying the root keeps the walk the same one when
/// new check-ins land on the branch between pages.
pub const Cursor = struct { root: []const u8, after: []const u8 };
pub fn parseCursor(text: []const u8) ?Cursor {
const colon = std.mem.indexOfScalar(u8, text, ':') orelse return null;
const c: Cursor = .{ .root = text[0..colon], .after = text[colon + 1 ..] };
if (!artifact.validateName(c.root) or !artifact.validateName(c.after)) return null;
return c;
}
pub fn formatCursor(arena: std.mem.Allocator, root: []const u8, after: []const u8) error{OutOfMemory}![]const u8 {
return std.fmt.allocPrint(arena, "{s}:{s}", .{ root, after });
}
pub const PageError = LogWalkError || error{
/// The cursor's row is not in this walk: another path, another
/// `follow`, or history the store no longer holds.
CursorInvalid,
};
/// The rows after `after` (all of them when null), at most `limit` (all
/// when null), from the walk `zit log root_id PATH -F json` makes. Each
/// page re-walks the root's ancestry; with the file index it reads
/// content only for the rows from its resume point to the page's end.
/// Nothing is held between pages.
pub fn page(
gpa: std.mem.Allocator,
arena: std.mem.Allocator,
repo: *Repository,
log: *logstore.LogStore,
index: ?*PathIndex,
root_id: []const u8,
after: ?[]const u8,
q: PathQuery,
classify: Classify,
) PageError!Page {
std.debug.assert(!q.long and (q.limit orelse 1) >= 1);
var rows: LogRows = .{ .arena = arena, .after = after };
var discard: std.Io.Writer.Discarding = .init(&.{});
// One row past the page says whether another page follows.
var walk_q = q;
if (q.limit) |n| walk_q.limit = n + 1;
var plaintext: logstore.PlaintextCache = .{};
defer plaintext.deinit(gpa);
var probe = PathProbe.init(gpa, &plaintext);
defer probe.deinit(gpa);
try walkPath(gpa, repo, log, index, root_id, walk_q, &discard.writer, &rows, &probe);
if (rows.after != null) return error.CursorInvalid;
const kept = rows.rows.items;
const shown = if (q.limit) |n| kept[0..@min(n, kept.len)] else kept;
const entries = try arena.alloc(Entry, shown.len);
for (shown, entries) |row, *e| e.* = entryOf(gpa, arena, repo, &probe, row, classify) catch |err| return switch (err) {
error.OutOfMemory => error.OutOfMemory,
error.Storage => error.Storage,
else => error.Corrupt,
};
const more = shown.len < kept.len;
return .{
.entries = entries,
.cursor = if (more) try formatCursor(arena, root_id, shown[shown.len - 1].id) else null,
};
}