//! The file-history index: which check-ins changed which path.
//!
//! `zit log CHECKIN PATH` names the check-ins whose effective content for PATH
//! differs from their primary parent's. Answering that by reconstructing two
//! manifests per visited check-in made one file's history on a mirror of
//! SQLite take minutes: the cost grew with how much history sat behind the
//! walk rather than with the answer's size.
//!
//! Fossil answers the same question from `mlink`, an index. zit already
//! computes the identical fact — `repoview.ChangedFile` is documented as
//! Fossil's mlink row, and `captureFileFacts` produces one check-in's change
//! set against its primary parent — but only streams it to the `crosslink`
//! feed. This module persists it, inverted by path, so the predicate becomes a
//! lookup instead of a reconstruction.
//!
//! Advisory, like every other member of the `.zit-cache` tier: keyed to the
//! log prefix and the shun fingerprint, rebuilt by one pass on any refusal,
//! and deleting it can only cost time. The answer stays derivable from the log
//! without it, which is what lets the reader fall back.
//!
//! **Unknown is recorded, not guessed.** `captureFileFacts` returns "files
//! unknown" for a tree manifest, an absent or shunned parent, or an
//! unresolvable baseline. Those check-ins are listed in `unknown`, and a
//! consumer that finds any of them in the ancestry it is asking about must
//! fall back to the reconstructing predicate. An empty change set is a claim;
//! silence is not the same as "changed nothing".
const std = @import("std");
const repeat = @import("repeat.zig").repeat;
const logstore = @import("logstore.zig");
const repoview = @import("repoview.zig");
const crc32 = @import("crc32.zig");
/// Rids are stored as u32: a log with more than 4 billion frames is past
/// several other limits first, and the index refuses to claim coverage it
/// cannot address rather than truncating one.
pub const max_rid: u64 = std.math.maxInt(u32);
/// Accumulates `repoview.eachChangeSet` into the path -> rids inversion.
pub const Builder = struct {
gpa: std.mem.Allocator,
arena: std.heap.ArenaAllocator,
map: std.StringArrayHashMapUnmanaged(std.ArrayListUnmanaged(u32)) = .empty,
unknown: std.ArrayListUnmanaged(u32) = .empty,
/// Set when a rid exceeds `max_rid`; the caller must not persist a blob
/// that silently covers less than the log.
overflow: bool = false,
pub fn init(gpa: std.mem.Allocator) Builder {
return .{ .gpa = gpa, .arena = std.heap.ArenaAllocator.init(gpa) };
}
pub fn deinit(self: *Builder) void {
for (self.map.values()) |*list| list.deinit(self.gpa);
self.map.deinit(self.gpa);
self.unknown.deinit(self.gpa);
self.arena.deinit();
}
pub fn sink(self: *Builder) repoview.ChangeSetSink {
return .{ .ctx = self, .emit = emit };
}
/// Seed this builder with an adopted index, so a tail walk extends it
/// rather than replacing it. Paths are copied into the builder's arena;
/// the blob may be freed afterwards.
pub fn absorb(self: *Builder, idx: *const Index) error{OutOfMemory}!void {
var u: usize = 0;
while (u < idx.unknownCount()) : (u += 1) try self.unknown.append(self.gpa, idx.unknownAt(u));
var pos = idx.first;
var i: u32 = 0;
while (i < idx.n_paths) : (i += 1) {
const len = std.mem.readInt(u16, idx.blob[pos..][0..2], .little);
pos += 2;
const name = idx.blob[pos..][0..len];
pos += len;
const count = std.mem.readInt(u32, idx.blob[pos..][0..4], .little);
pos += 4;
const gop = try self.map.getOrPut(self.gpa, name);
if (!gop.found_existing) {
gop.value_ptr.* = .empty; // before the copy can fail; see `emit`
gop.key_ptr.* = self.arena.allocator().dupe(u8, name) catch |e| {
self.map.swapRemoveAt(gop.index);
return e;
};
}
var k: u32 = 0;
while (k < count) : (k += 1) {
try gop.value_ptr.append(self.gpa, std.mem.readInt(u32, idx.blob[pos + k * 4 ..][0..4], .little));
}
pos += count * 4;
}
}
fn emit(ctx: *anyopaque, rid: logstore.Rid, files: ?[]const repoview.ChangedFile) error{OutOfMemory}!void {
const self: *Builder = @ptrCast(@alignCast(ctx));
if (rid > max_rid) {
self.overflow = true;
return;
}
const small: u32 = @intCast(rid);
const changed = files orelse {
try self.unknown.append(self.gpa, small);
return;
};
for (changed) |f| {
const gop = try self.map.getOrPut(self.gpa, f.path);
if (!gop.found_existing) {
// The value is initialized BEFORE the key copy can fail, and a
// failed copy removes the slot: otherwise an allocation failure
// here left a slot holding a borrowed key and an undefined list
// for `deinit` to free. The change set is freed per check-in,
// so the key is copied.
gop.value_ptr.* = .empty;
gop.key_ptr.* = self.arena.allocator().dupe(u8, f.path) catch |e| {
self.map.swapRemoveAt(gop.index);
return e;
};
}
// One check-in reports a path at most once, so a rid never repeats
// in a path's list. The list is NOT guaranteed ascending: the
// on-query build walks rids in order, but the derive walks frames
// in persisted order, and a phantom filled after later frames has a
// low rid at a high offset. Consumers treat the list as a set.
try gop.value_ptr.append(self.gpa, small);
}
}
};
// ---------------------------------------------------------------------------
// Codec. magic | version | LogKey | shun | n_paths | n_unknown
// | unknown rids | (path len, path, count, rids)* sorted by path | crc
//
// Paths are written in sorted order so a reader sweeps record headers and
// stops early on a miss, without building a map it would use once (logstore's
// sorted directory, same reasoning).
// ---------------------------------------------------------------------------
const magic = "ZITFIDX\x00";
/// v2 records `n_rids`, the log entry count the index covers, so a later
/// append is walked as a TAIL instead of rebuilding the whole index. A v1
/// blob is refused and rebuilt once; it could not say where its coverage
/// ended, so it could not be extended.
///
/// v3 is the same layout: the bump refuses a v2 blob built before
/// tree manifests were diffed, which recorded every tree check-in as UNKNOWN.
/// Such a blob is valid, adopted, and never rebuilt — so without the bump the
/// fix would never take effect on a store that already carried one.
///
/// v4 adds `key_entries`: how many log entries existed when the index was
/// written. An index is COMPLETE when `n_rids == key_entries`, and only a
/// complete index may be adopted by a derive extending a checkpoint over a
/// tail. The on-query build checkpoints partial indexes mid-walk under the
/// live log's key — that is what makes it resumable — and without this field
/// a partial index whose key matched the checkpoint's was adopted as complete,
/// which claimed coverage over the gap and silently omitted history.
const version: u16 = 4;
const header_len = 8 + 2 + 8 + 8 + 8 + 4 + 4 + 4 + 4 + 8 + 8;
pub fn serialize(
gpa: std.mem.Allocator,
log: *const logstore.LogStore,
b: *Builder,
/// Log entries this index covers; the next open resumes after it.
n_rids: u64,
) error{OutOfMemory}!?[]u8 {
if (b.overflow) return null;
const key = log.logKey() catch return null;
const order = try gpa.alloc(usize, b.map.count());
defer gpa.free(order);
for (order, 0..) |*o, i| o.* = i;
const keys = b.map.keys();
std.mem.sort(usize, order, keys, struct {
fn less(ks: []const []const u8, x: usize, y: usize) bool {
return std.mem.lessThan(u8, ks[x], ks[y]);
}
}.less);
var body: usize = @as(usize, b.unknown.items.len) * 4;
for (keys) |k| {
if (k.len > std.math.maxInt(u16)) return null;
body += 2 + k.len + 4;
}
for (b.map.values()) |v| body += v.items.len * 4;
const blob = try gpa.alloc(u8, header_len + body + 4);
errdefer gpa.free(blob);
@memcpy(blob[0..8], magic);
std.mem.writeInt(u16, blob[8..10], version, .little);
std.mem.writeInt(u64, blob[10..18], key.end, .little);
std.mem.writeInt(u64, blob[18..26], key.frame_count, .little);
std.mem.writeInt(u64, blob[26..34], key.last_frame_offset, .little);
std.mem.writeInt(u32, blob[34..38], key.last_header_crc, .little);
std.mem.writeInt(u32, blob[38..42], log.shunFingerprint(), .little);
std.mem.writeInt(u32, blob[42..46], @intCast(b.map.count()), .little);
std.mem.writeInt(u32, blob[46..50], @intCast(b.unknown.items.len), .little);
std.mem.writeInt(u64, blob[50..58], n_rids, .little);
std.mem.writeInt(u64, blob[58..66], @intCast(log.entryCount()), .little);
var pos: usize = header_len;
for (b.unknown.items) |r| {
std.mem.writeInt(u32, blob[pos..][0..4], r, .little);
pos += 4;
}
for (order) |i| {
const k = keys[i];
const rids = b.map.values()[i].items;
std.mem.writeInt(u16, blob[pos..][0..2], @intCast(k.len), .little);
pos += 2;
@memcpy(blob[pos..][0..k.len], k);
pos += k.len;
std.mem.writeInt(u32, blob[pos..][0..4], @intCast(rids.len), .little);
pos += 4;
for (rids) |r| {
std.mem.writeInt(u32, blob[pos..][0..4], r, .little);
pos += 4;
}
}
std.debug.assert(pos == blob.len - 4);
var crc = crc32.Crc32.init();
crc.update(blob[0 .. blob.len - 4]);
std.mem.writeInt(u32, blob[blob.len - 4 ..][0..4], crc.final(), .little);
return blob;
}
/// A parsed index, borrowing the blob it was adopted from.
pub const Index = struct {
blob: []const u8,
n_paths: u32,
/// Rids whose change set could not be known; a query whose candidate set
/// touches one of these must fall back to reconstruction.
unknown: []const u8,
/// Offset of the first path record.
first: usize,
/// Log entries this index covers. A log that has grown past it is walked
/// from here rather than from the beginning.
n_rids: u64,
/// The log key's frame count at build time — the same unit a cache
/// checkpoint records, so a derive extending a checkpoint over a tail can
/// tell whether this index stops at exactly that checkpoint. Entries and
/// frames are not the same count (a header frame is not an entry), so
/// `n_rids` cannot be compared against a checkpoint directly.
key_frame_count: u64,
/// Log entries that existed when this index was written. The index is
/// COMPLETE — covers every entry up to its key — when `n_rids` equals it;
/// a mid-walk checkpoint of the on-query build has `n_rids` below it.
key_entries: u64,
/// Whether this index covers every entry up to its key. Only a complete
/// index may be extended over a checkpoint's tail; a partial one is
/// resumed from `n_rids` by the on-query build, which walks the gap.
pub fn complete(self: *const Index) bool {
return self.n_rids == self.key_entries;
}
/// The check-ins that changed `path`, ascending. Empty is a real answer —
/// "no check-in changed it" — distinct from `unknown`.
pub fn changedBy(self: *const Index, path: []const u8, out: *std.ArrayListUnmanaged(u32), gpa: std.mem.Allocator) error{OutOfMemory}!void {
// Records are variable-width, so this sweeps rather than bisects: it
// reads each record's header and steps over its rid block, so the cost
// is one iteration per PATH (a few thousand), not per rid (hundreds of
// thousands). Sorted order lets it stop early on a miss. A bisect would
// need a second offset table for a lookup that is already microseconds.
var pos = self.first;
var i: u32 = 0;
while (i < self.n_paths) : (i += 1) {
const len = std.mem.readInt(u16, self.blob[pos..][0..2], .little);
pos += 2;
const name = self.blob[pos..][0..len];
pos += len;
const count = std.mem.readInt(u32, self.blob[pos..][0..4], .little);
pos += 4;
if (std.mem.eql(u8, name, path)) {
var k: u32 = 0;
while (k < count) : (k += 1) {
try out.append(gpa, std.mem.readInt(u32, self.blob[pos + k * 4 ..][0..4], .little));
}
return;
}
// Sorted: once past the name, it is absent.
if (std.mem.order(u8, name, path) == .gt) return;
pos += count * 4;
}
}
pub fn unknownCount(self: *const Index) usize {
return self.unknown.len / 4;
}
pub fn unknownAt(self: *const Index, i: usize) u32 {
return std.mem.readInt(u32, self.unknown[i * 4 ..][0..4], .little);
}
};
/// Adopt a blob against `log`: magic, version, CRC, the log prefix it was
/// keyed to, and the shun fingerprint must all hold, or the answer is null and
/// the caller rebuilds.
pub fn parse(blob: []const u8, log: *const logstore.LogStore) ?Index {
if (blob.len < header_len + 4) return null;
if (!std.mem.eql(u8, blob[0..8], magic)) return null;
if (std.mem.readInt(u16, blob[8..10], .little) != version) return null;
var crc = crc32.Crc32.init();
crc.update(blob[0 .. blob.len - 4]);
if (std.mem.readInt(u32, blob[blob.len - 4 ..][0..4], .little) != crc.final()) return null;
const key = logstore.LogStore.LogKey{
.end = std.mem.readInt(u64, blob[10..18], .little),
.frame_count = std.mem.readInt(u64, blob[18..26], .little),
.last_frame_offset = std.mem.readInt(u64, blob[26..34], .little),
.last_header_crc = std.mem.readInt(u32, blob[34..38], .little),
};
// A PREFIX match, not an exact tail: an append adds check-ins the index
// never saw, and those are walked as a tail (`n_rids` says where to
// resume). Refusing the whole index on any append is what made every
// commit cost a full rebuild.
if (!logstore.LogStore.validatePrefix(log.file, key)) return null;
if (std.mem.readInt(u32, blob[38..42], .little) != log.shunFingerprint()) return null;
const n_paths = std.mem.readInt(u32, blob[42..46], .little);
const n_unknown = std.mem.readInt(u32, blob[46..50], .little);
const ubytes = @as(usize, n_unknown) * 4;
if (header_len + ubytes > blob.len - 4) return null;
return .{
.blob = blob,
.n_paths = n_paths,
.unknown = blob[header_len..][0..ubytes],
.first = header_len + ubytes,
.n_rids = std.mem.readInt(u64, blob[50..58], .little),
.key_frame_count = key.frame_count,
.key_entries = std.mem.readInt(u64, blob[58..66], .little),
};
}
test "fileindex: a built index answers by path and round-trips through the codec" {
const gpa = std.testing.allocator;
const io = std.testing.io;
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const raw = try tmp.dir.createFile(io, "log", .{ .read = true });
var fs = @import("storage.zig").FileStorage.init(io, raw, 0);
var log = try logstore.LogStore.open(gpa, fs.storageFile(), 0);
defer log.deinit(gpa);
var b = Builder.init(gpa);
defer b.deinit();
const s = b.sink();
// Two check-ins touching overlapping paths, and one unknown.
try s.emit(s.ctx, 1, &.{
.{ .disp = .added, .path = "src/a.zig", .hash = repeat("1", 64) },
.{ .disp = .added, .path = "README.md", .hash = repeat("2", 64) },
});
try s.emit(s.ctx, 2, &.{.{ .disp = .modified, .path = "README.md", .hash = repeat("3", 64) }});
try s.emit(s.ctx, 3, null); // a tree manifest: unknown, never "changed nothing"
const blob = (try serialize(gpa, &log, &b, 3)).?;
defer gpa.free(blob);
const idx = parse(blob, &log).?;
var out: std.ArrayListUnmanaged(u32) = .empty;
defer out.deinit(gpa);
try idx.changedBy("README.md", &out, gpa);
try std.testing.expectEqualSlices(u32, &.{ 1, 2 }, out.items);
out.clearRetainingCapacity();
try idx.changedBy("src/a.zig", &out, gpa);
try std.testing.expectEqualSlices(u32, &.{1}, out.items);
out.clearRetainingCapacity();
// A path no check-in touched is an empty ANSWER, not an absence of one.
try idx.changedBy("never.txt", &out, gpa);
try std.testing.expectEqual(@as(usize, 0), out.items.len);
try std.testing.expectEqual(@as(u64, 3), idx.n_rids);
try std.testing.expectEqual(@as(usize, 1), idx.unknownCount());
try std.testing.expectEqual(@as(u32, 3), idx.unknownAt(0));
// A flipped byte is refused rather than adopted.
const bad = try gpa.dupe(u8, blob);
defer gpa.free(bad);
bad[header_len + 2] ^= 1;
try std.testing.expect(parse(bad, &log) == null);
}