//! 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.
//!
//! **Renames are edges, keyed per check-in.** A row that carries a prior name
//! (`ChangedFile.prior`, Fossil's `mlink.pfnid`) is also recorded as the edge
//! (check-in, new path) -> old path. A history reader following renames
//! switches names only at the check-in that recorded the edge: keying it by
//! path alone would route a file later created at the old path into the
//! renamed file's history, and the reverse.
//!
//! **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");
const blockcrc = @import("blockcrc.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,
/// Every rename a check-in recorded; the paths live in `arena`.
edges: std.ArrayListUnmanaged(Edge) = .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.edges.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. Every block is checked first: a damaged
/// index is `error.Corrupt` with nothing absorbed, and the caller builds
/// from the log instead. Paths are copied into the builder's arena; the
/// blob may be freed afterwards.
pub fn absorb(self: *Builder, idx: *Index) ReadError!void {
if (!idx.verifier.checkAll()) return error.Corrupt;
var u: usize = 0;
while (u < idx.unknownCount()) : (u += 1) try self.unknown.append(self.gpa, try idx.unknownAt(u));
var i: usize = 0;
while (i < idx.n_paths) : (i += 1) {
const rec = try idx.pathAt(i);
const gop = try self.map.getOrPut(self.gpa, rec.name);
if (!gop.found_existing) {
gop.value_ptr.* = .empty; // before the copy can fail; see `emit`
gop.key_ptr.* = self.arena.allocator().dupe(u8, rec.name) catch |e| {
self.map.swapRemoveAt(gop.index);
return e;
};
}
const rids = try idx.span(rec.rids_at, @as(usize, rec.count) * 4);
var k: usize = 0;
while (k < rec.count) : (k += 1) {
try gop.value_ptr.append(self.gpa, std.mem.readInt(u32, rids[k * 4 ..][0..4], .little));
}
}
var k: usize = 0;
while (k < idx.n_edges) : (k += 1) {
const e = try idx.edgeAt(k);
try self.addEdge(e.rid, e.new, e.old);
}
}
fn addEdge(self: *Builder, rid: u32, new: []const u8, old: []const u8) error{OutOfMemory}!void {
const a = self.arena.allocator();
const new_copy = try a.dupe(u8, new);
const old_copy = try a.dupe(u8, old);
try self.edges.append(self.gpa, .{ .rid = rid, .new = new_copy, .old = old_copy });
}
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);
if (f.prior) |old| try self.addEdge(small, f.path, old);
}
}
};
/// One rename: check-in `rid` holds `new`, which it renamed from `old`.
pub const Edge = struct { rid: u32, new: []const u8, old: []const u8 };
// ---------------------------------------------------------------------------
// Codec. A fixed header, then the body, then the body's block CRC table
// (`blockcrc`):
//
// header: magic | version | LogKey | shun | n_paths | n_unknown | n_rids
// | key_entries | n_edges | body_len | edges_at | table_crc
// | header_crc
// body: unknown rids (u32 each)
// | path offsets (u32 each, sorted by path)
// | (path len, path, count, rids)* sorted by path
// | edge offsets (u32 each, at `edges_at`)
// | (rid, new len, new, old len, old)* sorted by new path, rid
//
// Offsets are body-relative. Paths and edges are each found by bisecting an
// offset table, so a lookup reads a handful of blocks and checks only those;
// a reader that needs everything (`Builder.absorb`) checks every block first.
// ---------------------------------------------------------------------------
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.
///
/// v5 adds the rename edges. A v4 blob is valid but cannot say where a file
/// was renamed, so a history that follows renames would stop at every one;
/// it is refused and rebuilt once.
///
/// v6 replaces the one CRC over the file with a header CRC and a CRC per
/// body block, and adds the path offset table, so an open checks the header
/// and the block table and a lookup checks the blocks it reads. A v5 blob
/// is refused and rebuilt once.
const version: u16 = 6;
const header_len = 8 + 2 + 8 + 8 + 8 + 4 + 4 + 4 + 4 + 8 + 8 + 4 + 8 + 8 + 4 + 4; // = 94
const body_len_at = 70;
const edges_at_at = 78;
const table_crc_at = 86;
const header_crc_at = 90;
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 + keys.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 edge_order = try gpa.alloc(usize, b.edges.items.len);
defer gpa.free(edge_order);
for (edge_order, 0..) |*o, i| o.* = i;
std.mem.sort(usize, edge_order, b.edges.items, struct {
fn less(es: []const Edge, x: usize, y: usize) bool {
return switch (std.mem.order(u8, es[x].new, es[y].new)) {
.lt => true,
.gt => false,
.eq => es[x].rid < es[y].rid,
};
}
}.less);
if (b.edges.items.len > std.math.maxInt(u32)) return null;
for (b.edges.items) |e| {
if (e.new.len > std.math.maxInt(u16) or e.old.len > std.math.maxInt(u16)) return null;
body += 4 + 4 + 2 + e.new.len + 2 + e.old.len;
}
// Offsets are u32: an index past 4 GiB is not persisted, and the
// reconstructing walk answers instead.
if (body > std.math.maxInt(u32)) return null;
const blob = try gpa.alloc(u8, header_len + body + blockcrc.tableLen(body));
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);
std.mem.writeInt(u32, blob[66..70], @intCast(b.edges.items.len), .little);
std.mem.writeInt(u64, blob[body_len_at..][0..8], body, .little);
const out = blob[header_len..][0..body];
var pos: usize = 0;
for (b.unknown.items) |r| {
std.mem.writeInt(u32, out[pos..][0..4], r, .little);
pos += 4;
}
const path_table = pos;
pos += keys.len * 4;
for (order, 0..) |i, k| {
std.mem.writeInt(u32, out[path_table + k * 4 ..][0..4], @intCast(pos), .little);
const name = keys[i];
const rids = b.map.values()[i].items;
std.mem.writeInt(u16, out[pos..][0..2], @intCast(name.len), .little);
pos += 2;
@memcpy(out[pos..][0..name.len], name);
pos += name.len;
std.mem.writeInt(u32, out[pos..][0..4], @intCast(rids.len), .little);
pos += 4;
for (rids) |r| {
std.mem.writeInt(u32, out[pos..][0..4], r, .little);
pos += 4;
}
}
std.mem.writeInt(u64, blob[edges_at_at..][0..8], pos, .little);
const edge_table = pos;
pos += edge_order.len * 4;
for (edge_order, 0..) |i, k| {
std.mem.writeInt(u32, out[edge_table + k * 4 ..][0..4], @intCast(pos), .little);
const e = b.edges.items[i];
std.mem.writeInt(u32, out[pos..][0..4], e.rid, .little);
pos += 4;
std.mem.writeInt(u16, out[pos..][0..2], @intCast(e.new.len), .little);
pos += 2;
@memcpy(out[pos..][0..e.new.len], e.new);
pos += e.new.len;
std.mem.writeInt(u16, out[pos..][0..2], @intCast(e.old.len), .little);
pos += 2;
@memcpy(out[pos..][0..e.old.len], e.old);
pos += e.old.len;
}
std.debug.assert(pos == body);
const table = blob[header_len + body ..];
blockcrc.writeTable(out, table);
std.mem.writeInt(u32, blob[table_crc_at..][0..4], crc32.Crc32.hash(table), .little);
std.mem.writeInt(u32, blob[header_crc_at..][0..4], crc32.Crc32.hash(blob[0..header_crc_at]), .little);
return blob;
}
/// The error every lookup can return beside allocation failure: a block it
/// read failed its CRC, or a record pointed outside the body. Either way the
/// index is no longer trusted, and the owner rebuilds it from the log.
pub const ReadError = error{ OutOfMemory, Corrupt };
/// A parsed index, borrowing the blob it was adopted from. Its body is
/// checked block by block as lookups read it; `deinit` frees that record.
pub const Index = struct {
verifier: blockcrc.Verifier,
n_paths: u32,
n_unknown: u32,
/// 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,
/// The rename edges: an offset table of `n_edges` entries at
/// `edges_at`, then the records it points at.
n_edges: u32,
edges_at: usize,
pub fn deinit(self: *Index, gpa: std.mem.Allocator) void {
self.verifier.deinit(gpa);
self.* = undefined;
}
/// `len` body bytes at `at`, checked against their blocks' CRCs.
fn span(self: *Index, at: usize, len: usize) error{Corrupt}![]const u8 {
if (!self.verifier.check(at, len)) return error.Corrupt;
return self.verifier.body[at..][0..len];
}
fn readU32(self: *Index, at: usize) error{Corrupt}!u32 {
return std.mem.readInt(u32, (try self.span(at, 4))[0..4], .little);
}
fn readU16(self: *Index, at: usize) error{Corrupt}!u16 {
return std.mem.readInt(u16, (try self.span(at, 2))[0..2], .little);
}
const PathRecord = struct { name: []const u8, count: u32, rids_at: usize };
/// Path record `i` in sorted order.
fn pathAt(self: *Index, i: usize) error{Corrupt}!PathRecord {
std.debug.assert(i < self.n_paths);
const at: usize = try self.readU32(@as(usize, self.n_unknown) * 4 + i * 4);
const len = try self.readU16(at);
const name = try self.span(at + 2, len);
const count = try self.readU32(at + 2 + len);
return .{ .name = name, .count = count, .rids_at = at + 2 + len + 4 };
}
/// Edge `k` in sorted order.
fn edgeAt(self: *Index, k: usize) error{Corrupt}!Edge {
std.debug.assert(k < self.n_edges);
const at: usize = try self.readU32(self.edges_at + k * 4);
const rid = try self.readU32(at);
const new_len = try self.readU16(at + 4);
const new = try self.span(at + 6, new_len);
const old_len = try self.readU16(at + 6 + new_len);
const old = try self.span(at + 8 + new_len, old_len);
return .{ .rid = rid, .new = new, .old = old };
}
/// The renames onto `new`: every check-in that renamed a file to that
/// name, found by bisection over the edges sorted by new path, so the
/// cost follows this name's renames, not the repository's.
pub fn renamesInto(self: *Index, new: []const u8, out: *std.ArrayListUnmanaged(Edge), gpa: std.mem.Allocator) ReadError!void {
var lo: usize = 0;
var hi: usize = self.n_edges;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
const e = try self.edgeAt(mid);
if (std.mem.order(u8, e.new, new) == .lt) lo = mid + 1 else hi = mid;
}
var k = lo;
while (k < self.n_edges) : (k += 1) {
const e = try self.edgeAt(k);
if (!std.mem.eql(u8, e.new, new)) return;
try out.append(gpa, e);
}
}
/// The renames away from `old`. A scan: a walk asks this only at a
/// check-in that removes the name it follows, which is rare.
pub fn renamesFrom(self: *Index, old: []const u8, out: *std.ArrayListUnmanaged(Edge), gpa: std.mem.Allocator) ReadError!void {
var k: usize = 0;
while (k < self.n_edges) : (k += 1) {
const e = try self.edgeAt(k);
if (std.mem.eql(u8, e.old, old)) try out.append(gpa, e);
}
}
/// 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`. Empty is a real answer — "no
/// check-in changed it" — distinct from `unknown`. Found by bisecting
/// the path offsets, so a lookup reads a few blocks of a large index.
pub fn changedBy(self: *Index, path: []const u8, out: *std.ArrayListUnmanaged(u32), gpa: std.mem.Allocator) ReadError!void {
var lo: usize = 0;
var hi: usize = self.n_paths;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
const rec = try self.pathAt(mid);
switch (std.mem.order(u8, rec.name, path)) {
.lt => lo = mid + 1,
.gt => hi = mid,
.eq => {
const rids = try self.span(rec.rids_at, @as(usize, rec.count) * 4);
var k: usize = 0;
while (k < rec.count) : (k += 1) try out.append(gpa, std.mem.readInt(u32, rids[k * 4 ..][0..4], .little));
return;
},
}
}
}
pub fn unknownCount(self: *const Index) usize {
return self.n_unknown;
}
pub fn unknownAt(self: *Index, i: usize) error{Corrupt}!u32 {
std.debug.assert(i < self.n_unknown);
return self.readU32(i * 4);
}
};
/// Adopt a blob against `log`: magic, version, the header's CRC, the block
/// table's CRC, the log prefix it was keyed to, and the shun fingerprint
/// must all hold, or the answer is null and the caller rebuilds. The body is
/// not read here; each lookup checks the blocks it reads.
pub fn parse(gpa: std.mem.Allocator, blob: []const u8, log: *const logstore.LogStore) error{OutOfMemory}!?Index {
if (blob.len < header_len) 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;
if (crc32.Crc32.hash(blob[0..header_crc_at]) != std.mem.readInt(u32, blob[header_crc_at..][0..4], .little)) return null;
const body_len = std.mem.readInt(u64, blob[body_len_at..][0..8], .little);
if (body_len > blob.len - header_len) return null;
const body = blob[header_len..][0..@intCast(body_len)];
const table = blob[header_len + body.len ..];
if (table.len != blockcrc.tableLen(body.len)) return null;
if (crc32.Crc32.hash(table) != std.mem.readInt(u32, blob[table_crc_at..][0..4], .little)) 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 n_edges = std.mem.readInt(u32, blob[66..70], .little);
const edges_at = std.mem.readInt(u64, blob[edges_at_at..][0..8], .little);
// The fixed tables must fit inside the body. Where the edge table sits
// relative to the path records is not checked here: every byte either
// table points at is CRC-checked as it is read, so an offset can only
// name bytes as the serializer wrote them.
const tables = (@as(u64, n_unknown) + n_paths) * 4;
if (tables > body.len or edges_at < tables or edges_at > body.len or
@as(u64, n_edges) * 4 > body.len - edges_at) return null;
return .{
.verifier = try blockcrc.Verifier.init(gpa, body, table),
.n_paths = n_paths,
.n_unknown = n_unknown,
.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),
.n_edges = n_edges,
.edges_at = @intCast(edges_at),
};
}
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"
// A rename at check-in 4, and a NEW file created at the old name at 5:
// the edge belongs to check-in 4 alone.
try s.emit(s.ctx, 4, &.{
.{ .disp = .deleted, .path = "README.md", .hash = null },
.{ .disp = .added, .path = "docs/README.md", .hash = repeat("3", 64), .prior = "README.md" },
});
try s.emit(s.ctx, 5, &.{.{ .disp = .added, .path = "README.md", .hash = repeat("4", 64) }});
// Two more renames, one onto a name sorting first and one onto the same
// name again, so a lookup by name must bisect past unrelated edges.
try s.emit(s.ctx, 6, &.{.{ .disp = .added, .path = "a.md", .hash = repeat("5", 64), .prior = "z.md" }});
try s.emit(s.ctx, 7, &.{.{ .disp = .modified, .path = "docs/README.md", .hash = repeat("6", 64), .prior = "README.md" }});
const blob = (try serialize(gpa, &log, &b, 7)).?;
defer gpa.free(blob);
var idx = (try parse(gpa, blob, &log)).?;
defer idx.deinit(gpa);
var out: std.ArrayListUnmanaged(u32) = .empty;
defer out.deinit(gpa);
try idx.changedBy("README.md", &out, gpa);
try std.testing.expectEqualSlices(u32, &.{ 1, 2, 4, 5 }, 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, 7), idx.n_rids);
var found: std.ArrayListUnmanaged(Edge) = .empty;
defer found.deinit(gpa);
try idx.renamesInto("docs/README.md", &found, gpa);
try std.testing.expectEqual(@as(usize, 2), found.items.len);
try std.testing.expectEqual(@as(u32, 4), found.items[0].rid);
try std.testing.expectEqual(@as(u32, 7), found.items[1].rid);
try std.testing.expectEqualStrings("README.md", found.items[0].old);
found.clearRetainingCapacity();
try idx.renamesInto("a.md", &found, gpa);
try std.testing.expectEqual(@as(usize, 1), found.items.len);
try std.testing.expectEqualStrings("z.md", found.items[0].old);
found.clearRetainingCapacity();
try idx.renamesInto("README.md", &found, gpa); // renamed FROM, never onto
try std.testing.expectEqual(@as(usize, 0), found.items.len);
try idx.renamesFrom("README.md", &found, gpa);
try std.testing.expectEqual(@as(usize, 2), found.items.len);
// Absorbed into a fresh builder, the edges survive a re-serialize.
var again = Builder.init(gpa);
defer again.deinit();
try again.absorb(&idx);
try std.testing.expectEqual(@as(usize, 3), again.edges.items.len);
try std.testing.expectEqual(@as(usize, 1), idx.unknownCount());
try std.testing.expectEqual(@as(u32, 3), try idx.unknownAt(0));
// A flipped header byte is refused rather than adopted.
const bad = try gpa.dupe(u8, blob);
defer gpa.free(bad);
bad[42] ^= 1;
try std.testing.expect((try parse(gpa, bad, &log)) == null);
}
/// A builder over `n` paths, each changed by a few check-ins, with a rename
/// edge every tenth path and every seventh rid unknown: large enough that
/// each section spans several blocks.
fn buildWideForTest(gpa: std.mem.Allocator, n: usize) !Builder {
var b = Builder.init(gpa);
errdefer b.deinit();
const s = b.sink();
var rid: u32 = 1;
for (0..n) |i| {
var name_buf: [64]u8 = undefined;
const name = try std.fmt.bufPrint(&name_buf, "dir{d:0>3}/file{d:0>5}.txt", .{ i % 200, i });
var old_buf: [64]u8 = undefined;
const old = try std.fmt.bufPrint(&old_buf, "old/file{d:0>5}.txt", .{i});
try s.emit(s.ctx, rid, &.{.{ .disp = .added, .path = name, .hash = repeat("1", 64), .prior = if (i % 10 == 0) old else null }});
try s.emit(s.ctx, rid + 1, &.{.{ .disp = .modified, .path = name, .hash = repeat("2", 64) }});
if (i % 7 == 0) try s.emit(s.ctx, rid + 2, null);
rid += 3;
}
return b;
}
fn pathNameForTest(buf: []u8, i: usize) []const u8 {
return std.fmt.bufPrint(buf, "dir{d:0>3}/file{d:0>5}.txt", .{ i % 200, i }) catch unreachable;
}
/// Every answer `idx` gives for path `i` and its rename, or `error.Corrupt`.
fn expectAnswersForTest(gpa: std.mem.Allocator, idx: *Index, i: usize) ReadError!void {
var buf: [64]u8 = undefined;
const name = pathNameForTest(&buf, i);
var out: std.ArrayListUnmanaged(u32) = .empty;
defer out.deinit(gpa);
try idx.changedBy(name, &out, gpa);
const first: u32 = @intCast(i * 3 + 1);
std.testing.expectEqualSlices(u32, &.{ first, first + 1 }, out.items) catch unreachable;
var edges: std.ArrayListUnmanaged(Edge) = .empty;
defer edges.deinit(gpa);
try idx.renamesInto(name, &edges, gpa);
std.testing.expectEqual(@as(usize, if (i % 10 == 0) 1 else 0), edges.items.len) catch unreachable;
if (edges.items.len == 1) std.testing.expectEqual(first, edges.items[0].rid) catch unreachable;
}
fn testLog(tmp: *std.testing.TmpDir, gpa: std.mem.Allocator, name: []const u8, fill: u8) !struct { fs: @import("storage.zig").FileStorage, raw: std.Io.File } {
const io = std.testing.io;
const raw = try tmp.dir.createFile(io, name, .{ .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);
_ = try log.put(&(@as([32]u8, @splat(fill))), "one frame, so the key names it");
try log.commit();
return .{ .fs = fs, .raw = raw };
}
test "fileindex: a lookup checks the blocks it reads, and any flipped byte is refused or caught, never answered" {
const gpa = std.testing.allocator;
const io = std.testing.io;
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
var t = try testLog(&tmp, gpa, "log", 0x41);
defer t.raw.close(io);
t.fs = @import("storage.zig").FileStorage.init(io, t.raw, try t.raw.length(io));
var log = try logstore.LogStore.openReadOnly(gpa, t.fs.storageFile());
defer log.deinit(gpa);
const n = 3000;
var b = try buildWideForTest(gpa, n);
defer b.deinit();
const blob = (try serialize(gpa, &log, &b, n * 3)).?;
defer gpa.free(blob);
const body_len: usize = @intCast(std.mem.readInt(u64, blob[body_len_at..][0..8], .little));
const blocks = blockcrc.blockCount(body_len);
try std.testing.expect(blocks > 30);
// One path's lookup bisects: a few blocks, not the file. Each probe
// reads one offset-table block and one record block, and the rename
// lookup bisects its own table.
{
const wide_n = 40000;
var wide = try buildWideForTest(gpa, wide_n);
defer wide.deinit();
const wide_blob = (try serialize(gpa, &log, &wide, wide_n * 3)).?;
defer gpa.free(wide_blob);
var wide_idx = (try parse(gpa, wide_blob, &log)).?;
defer wide_idx.deinit(gpa);
const wide_blocks = blockcrc.blockCount(@intCast(std.mem.readInt(u64, wide_blob[body_len_at..][0..8], .little)));
const before = blockcrc.blocks_checked.load(.monotonic);
try expectAnswersForTest(gpa, &wide_idx, 31234);
const touched = blockcrc.blocks_checked.load(.monotonic) - before;
try std.testing.expect(touched > 0 and touched <= 4 * (std.math.log2_int_ceil(usize, wide_n) + 1));
try std.testing.expect(touched * 10 < wide_blocks);
}
{
var idx = (try parse(gpa, blob, &log)).?;
defer idx.deinit(gpa);
// A full read checks everything, and agrees.
var again = Builder.init(gpa);
defer again.deinit();
try again.absorb(&idx);
try std.testing.expectEqual(@as(usize, n), again.map.count());
try std.testing.expectEqual(blocks, idx.verifier.verifiedCount());
}
// A flip in each block of the body: parse succeeds, and every lookup
// either answers exactly or reports the damage. The probes walk paths
// across the whole sorted range, so each block is read by some probe.
var k: usize = 0;
while (k < blocks) : (k += 1) {
const flip = try gpa.dupe(u8, blob);
defer gpa.free(flip);
flip[header_len + k * blockcrc.block_len + 7] ^= 0x04;
var idx = (try parse(gpa, flip, &log)).?;
defer idx.deinit(gpa);
var caught = false;
var i: usize = 0;
while (i < n) : (i += 1) {
expectAnswersForTest(gpa, &idx, i) catch |e| switch (e) {
error.Corrupt => {
caught = true;
break;
},
error.OutOfMemory => return e,
};
}
// Unknown rids and the edges not reached by name are read here.
if (!caught) {
var u: usize = 0;
while (u < idx.unknownCount()) : (u += 1) _ = idx.unknownAt(u) catch {
caught = true;
break;
};
}
if (!caught) {
var edges: std.ArrayListUnmanaged(Edge) = .empty;
defer edges.deinit(gpa);
idx.renamesFrom("nowhere", &edges, gpa) catch {
caught = true;
};
}
try std.testing.expect(caught);
// A damaged index cannot seed a builder.
var seed = Builder.init(gpa);
defer seed.deinit();
var fresh_idx = (try parse(gpa, flip, &log)).?;
defer fresh_idx.deinit(gpa);
try std.testing.expectError(error.Corrupt, seed.absorb(&fresh_idx));
}
// Any flip in the header or the block table is refused at parse, as is
// a torn file and an old version.
for ([_]usize{ 0, 9, 20, 40, 44, 52, 60, 67, 72, 80, 88, 92, blob.len - 1, blob.len - 5 }) |at| {
const flip = try gpa.dupe(u8, blob);
defer gpa.free(flip);
flip[at] ^= 1;
try std.testing.expect((try parse(gpa, flip, &log)) == null);
}
try std.testing.expect((try parse(gpa, blob[0 .. header_len + blockcrc.block_len + 9], &log)) == null);
const old = try gpa.dupe(u8, blob);
defer gpa.free(old);
std.mem.writeInt(u16, old[8..10], version - 1, .little);
std.mem.writeInt(u32, old[header_crc_at..][0..4], crc32.Crc32.hash(old[0..header_crc_at]), .little);
try std.testing.expect((try parse(gpa, old, &log)) == null);
}
test "fileindex: an index keyed to another log is refused before any block is read" {
const gpa = std.testing.allocator;
const io = std.testing.io;
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
var a = try testLog(&tmp, gpa, "a", 0x41);
defer a.raw.close(io);
var other = try testLog(&tmp, gpa, "b", 0x42);
defer other.raw.close(io);
a.fs = @import("storage.zig").FileStorage.init(io, a.raw, try a.raw.length(io));
other.fs = @import("storage.zig").FileStorage.init(io, other.raw, try other.raw.length(io));
var log_a = try logstore.LogStore.openReadOnly(gpa, a.fs.storageFile());
defer log_a.deinit(gpa);
var log_b = try logstore.LogStore.openReadOnly(gpa, other.fs.storageFile());
defer log_b.deinit(gpa);
var b = try buildWideForTest(gpa, 500);
defer b.deinit();
const blob = (try serialize(gpa, &log_a, &b, 1500)).?;
defer gpa.free(blob);
const body_len: usize = @intCast(std.mem.readInt(u64, blob[body_len_at..][0..8], .little));
// Every body byte damaged too; the key refuses first, reading none.
for (blob[header_len..][0..body_len]) |*x| x.* ^= 0xff;
const before = blockcrc.blocks_checked.load(.monotonic);
try std.testing.expect((try parse(gpa, blob, &log_b)) == null);
try std.testing.expectEqual(before, blockcrc.blocks_checked.load(.monotonic));
}