//! The cone index: what the sparse-cone classifier learns by reading every
//! held artifact, kept so a cone-scoped request does not read them again.
//!
//! `sparse.classifyKeepRids` answers "which blobs do in-cone F cards name" by
//! parsing every artifact the store holds. On a sub-manifest store that is
//! every tree node of every check-in in history -- NetBSD src is ~2.5M
//! artifacts, and the reading pass did not finish in a quarter of an hour of
//! CPU per cone. The answer is a function of the artifacts' bytes, and the
//! bytes never change: a content-addressed log only grows. So the facts the
//! classifier reads are distilled once, in one ordered pass, and a later
//! append is folded in by visiting only the frames past the covered prefix.
//!
//! Each held artifact is read once. A tree node shared by many check-ins is
//! one artifact, so this pass already does what a node-by-node tree diff's
//! prune of unchanged subtrees buys, and it needs no reachability argument:
//! an orphan node, a delta manifest, an attachment and a blob that happens to
//! parse as a manifest all contribute exactly what the reading classifier
//! sees, because they are read the same way.
//!
//! What is kept, per held artifact, is exactly what the classifier reads:
//! - whether it parses as structural (one bit per log rid);
//! - the distinct (path, target) pairs its F cards name, inverted by path,
//! so a cone's paths are found without touching anything else;
//! - its attachment source, if any;
//! - any S-card child that is not held -- the one input the index does not
//! reduce. A store with such a hole has absent nodes for the slot walk to
//! classify, and the caller falls back to reading.
//!
//! Targets are LOG rids: stable across appends (a phantom filled later keeps
//! its rid), four bytes each. An F card whose target the log does not carry
//! at all, or carries under a spelling a store lookup would miss, is kept as
//! text and resolved at classification time, so a later arrival is seen.
//!
//! Advisory, like every `.zit-cache` member: keyed to a log prefix and the
//! shun fingerprint, extended over an appended tail, rebuilt on any refusal,
//! and deleting it only costs time.
const std = @import("std");
const artifact = @import("artifact.zig");
const logstore = @import("logstore.zig");
const crc32 = @import("crc32.zig");
const repocache = @import("repocache.zig");
const repeat = @import("repeat.zig").repeat;
/// Targets and structural bits are addressed by u32 log rid; a log past that
/// is refused rather than truncated.
pub const max_rid: u64 = std.math.maxInt(u32);
/// The `.zit-cache` member this index is stored in.
pub const member: []const u8 = "coneidx";
pub const Error = error{
OutOfMemory,
/// A held frame could not be read. The reading classifier would skip it
/// and classify around the gap; an index that recorded the gap would keep
/// answering that way after the fault cleared, so nothing is recorded.
Unreadable,
/// The log has more rids than the index can address.
Overflow,
};
pub const Builder = struct {
gpa: std.mem.Allocator,
/// Owns path and hash text.
arena: std.heap.ArenaAllocator,
/// Log rid -> parses as structural.
structural: std.DynamicBitSetUnmanaged = .{},
/// Path -> distinct target log rids, in first-seen order.
paths: std.StringArrayHashMapUnmanaged(std.ArrayListUnmanaged(u32)) = .empty,
/// (path index << 32 | target) for every pair already recorded.
pairs: std.AutoHashMapUnmanaged(u64, void) = .empty,
/// "path\x00hash" for F cards the log cannot resolve by rid.
dangling: std.StringArrayHashMapUnmanaged(void) = .empty,
/// Attachment source log rids, and the sources named only as text.
attach: std.AutoArrayHashMapUnmanaged(u32, void) = .empty,
attach_dangling: std.StringArrayHashMapUnmanaged(void) = .empty,
/// Lowercase S-card children not held when last checked.
absent: std.StringArrayHashMapUnmanaged(void) = .empty,
pub fn init(gpa: std.mem.Allocator) Builder {
return .{ .gpa = gpa, .arena = std.heap.ArenaAllocator.init(gpa) };
}
pub fn deinit(self: *Builder) void {
const gpa = self.gpa;
self.structural.deinit(gpa);
for (self.paths.values()) |*list| list.deinit(gpa);
self.paths.deinit(gpa);
self.pairs.deinit(gpa);
self.dangling.deinit(gpa);
self.attach.deinit(gpa);
self.attach_dangling.deinit(gpa);
self.absent.deinit(gpa);
self.arena.deinit();
self.* = undefined;
}
/// Read every frame at or past `from_offset`, in persisted order, and
/// record its facts. Zero-from-header is the whole log; an adopted
/// index's `key.end` is its tail. A phantom filled after the prefix was
/// written has its frame in the tail, so it is visited here.
pub fn sweep(self: *Builder, log: *logstore.LogStore, from_offset: u64) Error!void {
const gpa = self.gpa;
if (log.entryCount() > max_rid) return error.Overflow;
try self.structural.resize(gpa, log.entryCount() + 1, false);
const rids = try log.ridsInPersistedOrder(gpa);
defer gpa.free(rids);
// Persisted order keeps each delta's base hot in this memo, so a
// chain costs about one reconstruction rather than its depth.
var cache = logstore.PlaintextCache.init();
defer cache.deinit(gpa);
for (rids) |rid| {
if (log.offsetOf(rid) < from_offset) continue;
try self.noteFrame(log, rid, &cache);
}
// A child recorded absent may have arrived later in this sweep, or in
// this tail; only the ones still missing are kept.
var i: usize = 0;
while (i < self.absent.count()) {
if (heldInLog(log, self.absent.keys()[i])) {
self.absent.swapRemoveAt(i);
} else i += 1;
}
}
fn noteFrame(self: *Builder, log: *logstore.LogStore, rid: logstore.Rid, cache: *logstore.PlaintextCache) Error!void {
const gpa = self.gpa;
// Two bytes decide most frames before any reconstruction: a file blob
// stored whole almost never starts like a card. Null (a delta frame)
// and a read error both fall through to the full read, so nothing
// that would parse is skipped. The bytes reach no one.
if (log.contentPrefixUnmasked(gpa, rid, 2) catch null) |prefix| {
defer gpa.free(prefix);
if (!couldStartStructural(prefix)) return;
}
// The masked read, as the classifier's store reads: a shunned frame is
// not held there and contributes nothing here.
const bytes = (log.contentCached(gpa, rid, cache) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.Unreadable,
}) orelse return;
defer gpa.free(bytes);
var im = artifact.parseForImport(gpa, bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return, // a content blob
};
defer im.deinit(gpa);
const m = &im.manifest;
self.structural.set(@intCast(rid));
for (m.f) |fc| {
const h = fc.hash orelse continue; // a delete marker names nothing
try self.notePair(log, fc.filename, h);
}
for (m.s) |sc| {
var buf: [64]u8 = undefined;
if (sc.hash.len > buf.len) continue; // the S grammar admits 40 or 64
const lower = std.ascii.lowerString(buf[0..sc.hash.len], sc.hash);
if (heldInLog(log, lower)) continue;
const gop = try self.absent.getOrPut(gpa, lower);
if (!gop.found_existing) gop.key_ptr.* = try self.arena.allocator().dupe(u8, lower);
}
if (m.a) |a| {
if (a.source) |src| {
if (resolve(log, src)) |t| {
try self.attach.put(gpa, t, {});
} else {
const gop = try self.attach_dangling.getOrPut(gpa, src);
if (!gop.found_existing) gop.key_ptr.* = try self.arena.allocator().dupe(u8, src);
}
}
}
}
fn notePair(self: *Builder, log: *logstore.LogStore, path: []const u8, hash: []const u8) error{OutOfMemory}!void {
const gpa = self.gpa;
const target = resolve(log, hash) orelse {
const key = try std.mem.concat(gpa, u8, &.{ path, "\x00", hash });
defer gpa.free(key);
const gop = try self.dangling.getOrPut(gpa, key);
if (!gop.found_existing) gop.key_ptr.* = try self.arena.allocator().dupe(u8, key);
return;
};
const p = try self.pathIndex(path);
const pair = (@as(u64, p) << 32) | target;
const gop = try self.pairs.getOrPut(gpa, pair);
if (gop.found_existing) return;
self.paths.values()[p].append(gpa, target) catch |e| {
_ = self.pairs.remove(pair);
return e;
};
}
fn pathIndex(self: *Builder, path: []const u8) error{OutOfMemory}!u32 {
const gop = try self.paths.getOrPut(self.gpa, path);
if (!gop.found_existing) {
// The value is set before the key copy can fail, and a failed copy
// removes the slot, so `deinit` never sees an undefined list.
gop.value_ptr.* = .empty;
gop.key_ptr.* = self.arena.allocator().dupe(u8, path) catch |e| {
self.paths.swapRemoveAt(gop.index);
return e;
};
}
return @intCast(gop.index);
}
/// Seed this builder with an adopted index, so a tail sweep extends it.
pub fn absorb(self: *Builder, idx: *const Index) error{OutOfMemory}!void {
const gpa = self.gpa;
const aa = self.arena.allocator();
try self.structural.resize(gpa, idx.n_bits, false);
var r: usize = 0;
while (r < idx.n_bits) : (r += 1) {
if (idx.isStructural(r)) self.structural.set(r);
}
var ai: usize = 0;
while (ai < idx.n_attach) : (ai += 1) try self.attach.put(gpa, idx.attachAt(ai), {});
var it = idx.texts(.attach_dangling);
while (it.next()) |s| try self.attach_dangling.put(gpa, try aa.dupe(u8, s), {});
it = idx.texts(.absent);
while (it.next()) |s| try self.absent.put(gpa, try aa.dupe(u8, s), {});
it = idx.texts(.dangling);
while (it.next()) |s| try self.dangling.put(gpa, try aa.dupe(u8, s), {});
var pit = idx.pathRecords();
while (pit.next()) |rec| {
const p = try self.pathIndex(rec.path);
var k: u32 = 0;
while (k < rec.count) : (k += 1) {
const t = rec.target(k);
const pair = (@as(u64, p) << 32) | t;
const gop = try self.pairs.getOrPut(gpa, pair);
if (gop.found_existing) continue;
try self.paths.values()[p].append(gpa, t);
}
}
}
};
/// A card's first byte is its type letter and its second delimits it, and a
/// signed artifact opens with its armor line; anything else cannot parse.
fn couldStartStructural(prefix: []const u8) bool {
if (prefix.len < 2) return true;
if (prefix[0] == '-') return true; // "-----BEGIN ..." signature wrapper
if (prefix[0] < 'A' or prefix[0] > 'Z') return false;
return prefix[1] == ' ' or prefix[1] == '\n';
}
/// The log rid a store lookup by this exact text would find, or null. The
/// stores the classifier runs over key names by lowercase hex, so any other
/// spelling misses there and is kept as text here, to miss the same way.
fn resolve(log: *const logstore.LogStore, hex: []const u8) ?u32 {
var digest: [logstore.max_hash_len]u8 = undefined;
if (!logstore.isCompleteDigest(hex.len / 2) or hex.len % 2 != 0) return null;
for (hex) |c| if (!std.ascii.isDigit(c) and !(c >= 'a' and c <= 'f')) return null;
const raw = std.fmt.hexToBytes(digest[0 .. hex.len / 2], hex) catch return null;
const rid = log.lookup(raw) orelse return null;
if (rid > max_rid) return null;
return @intCast(rid);
}
/// Whether the log holds `lower_hex` with a frame (not a phantom) that the
/// shun table does not mask -- what a store over this log answers as held.
fn heldInLog(log: *const logstore.LogStore, lower_hex: []const u8) bool {
const rid = resolve(log, lower_hex) orelse return false;
if (log.isPhantom(rid)) return false;
const digest = log.hashOf(rid);
return !(logstore.isCompleteDigest(digest.len) and log.isShunned(digest));
}
// ---------------------------------------------------------------------------
// Codec. magic | version | LogKey | shun | n_bits | n_paths | n_attach
// | n_attach_dangling | n_absent | n_dangling | structural bitmap
// | attach rids | (len u16, text)* x3 | (len, path, count, rids)* | crc
// Paths are sorted, and each path's targets ascending, so equal facts
// serialize to equal bytes.
// ---------------------------------------------------------------------------
const magic = "ZITCONE\x00";
const version: u16 = 1;
const header_len = 8 + 2 + 8 + 8 + 8 + 4 + 4 + 8 + 4 + 4 + 4 + 4 + 4;
pub fn serialize(gpa: std.mem.Allocator, log: *const logstore.LogStore, b: *const Builder) error{OutOfMemory}!?[]u8 {
const key = log.logKey() catch return null;
const n_bits: u64 = b.structural.bit_length;
const order = try gpa.alloc(u32, b.paths.count());
defer gpa.free(order);
for (order, 0..) |*o, i| o.* = @intCast(i);
const keys = b.paths.keys();
std.mem.sort(u32, order, keys, struct {
fn less(ks: []const []const u8, x: u32, y: u32) bool {
return std.mem.lessThan(u8, ks[x], ks[y]);
}
}.less);
var body: usize = (n_bits + 7) / 8 + b.attach.count() * 4;
for ([_][]const []const u8{ b.attach_dangling.keys(), b.absent.keys(), b.dangling.keys() }) |list| {
for (list) |s| {
if (s.len > std.math.maxInt(u16)) return null;
body += 2 + s.len;
}
}
for (keys, b.paths.values()) |k, v| {
if (k.len > std.math.maxInt(u16)) return null;
body += 2 + k.len + 4 + v.items.len * 4;
}
const blob = try gpa.alloc(u8, header_len + body + 4);
errdefer gpa.free(blob);
@memset(blob, 0);
@memcpy(blob[0..8], magic);
var pos: usize = 8;
put(u16, blob, &pos, version);
put(u64, blob, &pos, key.end);
put(u64, blob, &pos, key.frame_count);
put(u64, blob, &pos, key.last_frame_offset);
put(u32, blob, &pos, key.last_header_crc);
put(u32, blob, &pos, log.shunFingerprint());
put(u64, blob, &pos, n_bits);
put(u32, blob, &pos, @intCast(b.paths.count()));
put(u32, blob, &pos, @intCast(b.attach.count()));
put(u32, blob, &pos, @intCast(b.attach_dangling.count()));
put(u32, blob, &pos, @intCast(b.absent.count()));
put(u32, blob, &pos, @intCast(b.dangling.count()));
std.debug.assert(pos == header_len);
const bitmap = blob[pos..][0..@intCast((n_bits + 7) / 8)];
var r: usize = 0;
while (r < n_bits) : (r += 1) {
if (b.structural.isSet(r)) bitmap[r / 8] |= @as(u8, 1) << @intCast(r % 8);
}
pos += bitmap.len;
const attach = try gpa.dupe(u32, b.attach.keys());
defer gpa.free(attach);
std.mem.sort(u32, attach, {}, std.sort.asc(u32));
for (attach) |t| put(u32, blob, &pos, t);
for ([_][]const []const u8{ b.attach_dangling.keys(), b.absent.keys(), b.dangling.keys() }) |list| {
const sorted = try gpa.dupe([]const u8, list);
defer gpa.free(sorted);
std.mem.sort([]const u8, sorted, {}, struct {
fn less(_: void, x: []const u8, y: []const u8) bool {
return std.mem.lessThan(u8, x, y);
}
}.less);
for (sorted) |s| {
put(u16, blob, &pos, @intCast(s.len));
@memcpy(blob[pos..][0..s.len], s);
pos += s.len;
}
}
for (order) |i| {
const k = keys[i];
put(u16, blob, &pos, @intCast(k.len));
@memcpy(blob[pos..][0..k.len], k);
pos += k.len;
const targets = try gpa.dupe(u32, b.paths.values()[i].items);
defer gpa.free(targets);
std.mem.sort(u32, targets, {}, std.sort.asc(u32));
put(u32, blob, &pos, @intCast(targets.len));
for (targets) |t| put(u32, blob, &pos, t);
}
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;
}
fn put(comptime T: type, blob: []u8, pos: *usize, v: T) void {
std.mem.writeInt(T, blob[pos.*..][0..@sizeOf(T)], v, .little);
pos.* += @sizeOf(T);
}
/// A parsed index, borrowing the blob it was adopted from. Every section was
/// bounds-checked by `parse`, so the readers below cannot run off the blob.
pub const Index = struct {
blob: []const u8,
key: logstore.LogStore.LogKey,
n_bits: u64,
n_paths: u32,
n_attach: u32,
counts: [3]u32,
bitmap: []const u8,
attach: []const u8,
/// Offsets of the three text sections and of the first path record.
text_at: [3]usize,
paths_at: usize,
pub const Text = enum(u2) { attach_dangling = 0, absent = 1, dangling = 2 };
/// Whether the index covers the whole live log, not just a prefix of it.
pub fn coversAll(self: *const Index, log: *const logstore.LogStore) bool {
return logstore.LogStore.validateTail(log.file, self.key);
}
pub fn isStructural(self: *const Index, rid: usize) bool {
if (rid >= self.n_bits) return false;
return (self.bitmap[rid / 8] >> @intCast(rid % 8)) & 1 == 1;
}
pub fn attachAt(self: *const Index, i: usize) u32 {
return std.mem.readInt(u32, self.attach[i * 4 ..][0..4], .little);
}
pub const TextIterator = struct {
blob: []const u8,
pos: usize,
left: u32,
pub fn next(self: *TextIterator) ?[]const u8 {
if (self.left == 0) return null;
self.left -= 1;
const len = std.mem.readInt(u16, self.blob[self.pos..][0..2], .little);
const s = self.blob[self.pos + 2 ..][0..len];
self.pos += 2 + len;
return s;
}
};
pub fn texts(self: *const Index, which: Text) TextIterator {
const i = @backingInt(which);
return .{ .blob = self.blob, .pos = self.text_at[i], .left = self.counts[i] };
}
pub const PathRecord = struct {
path: []const u8,
count: u32,
rids: []const u8,
pub fn target(self: PathRecord, k: u32) u32 {
return std.mem.readInt(u32, self.rids[k * 4 ..][0..4], .little);
}
};
pub const PathIterator = struct {
blob: []const u8,
pos: usize,
left: u32,
pub fn next(self: *PathIterator) ?PathRecord {
if (self.left == 0) return null;
self.left -= 1;
const len = std.mem.readInt(u16, self.blob[self.pos..][0..2], .little);
const path = self.blob[self.pos + 2 ..][0..len];
const count = std.mem.readInt(u32, self.blob[self.pos + 2 + len ..][0..4], .little);
const rids = self.blob[self.pos + 6 + len ..][0 .. @as(usize, count) * 4];
self.pos += 6 + len + rids.len;
return .{ .path = path, .count = count, .rids = rids };
}
};
pub fn pathRecords(self: *const Index) PathIterator {
return .{ .blob = self.blob, .pos = self.paths_at, .left = self.n_paths };
}
};
/// Adopt a blob against `log`: magic, version, CRC, a still-intact log
/// prefix, the shun fingerprint and every section's bounds must 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;
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;
var pos: usize = 8;
if (get(u16, blob, &pos) != version) return null;
const key = logstore.LogStore.LogKey{
.end = get(u64, blob, &pos),
.frame_count = get(u64, blob, &pos),
.last_frame_offset = get(u64, blob, &pos),
.last_header_crc = get(u32, blob, &pos),
};
// A prefix match: an append is folded in as a tail, never a rebuild.
if (!logstore.LogStore.validatePrefix(log.file, key)) return null;
if (get(u32, blob, &pos) != log.shunFingerprint()) return null;
const n_bits = get(u64, blob, &pos);
const n_paths = get(u32, blob, &pos);
const n_attach = get(u32, blob, &pos);
const counts = [3]u32{ get(u32, blob, &pos), get(u32, blob, &pos), get(u32, blob, &pos) };
std.debug.assert(pos == header_len);
const end = blob.len - 4;
if (n_bits > max_rid + 1) return null;
const bitmap_len: usize = @intCast((n_bits + 7) / 8);
if (end - pos < bitmap_len) return null;
const bitmap = blob[pos..][0..bitmap_len];
pos += bitmap_len;
if ((end - pos) / 4 < n_attach) return null;
const attach = blob[pos..][0 .. @as(usize, n_attach) * 4];
pos += attach.len;
var text_at: [3]usize = undefined;
for (counts, 0..) |count, i| {
text_at[i] = pos;
var k: u32 = 0;
while (k < count) : (k += 1) {
if (end - pos < 2) return null;
const len = std.mem.readInt(u16, blob[pos..][0..2], .little);
if (end - pos - 2 < len) return null;
pos += 2 + len;
}
}
const paths_at = pos;
var k: u32 = 0;
while (k < n_paths) : (k += 1) {
if (end - pos < 2) return null;
const len = std.mem.readInt(u16, blob[pos..][0..2], .little);
if (end - pos - 2 < @as(usize, len) + 4) return null;
const count = std.mem.readInt(u32, blob[pos + 2 + len ..][0..4], .little);
pos += 6 + len;
if ((end - pos) / 4 < count) return null;
pos += @as(usize, count) * 4;
}
if (pos != end) return null;
return .{
.blob = blob,
.key = key,
.n_bits = n_bits,
.n_paths = n_paths,
.n_attach = n_attach,
.counts = counts,
.bitmap = bitmap,
.attach = attach,
.text_at = text_at,
.paths_at = paths_at,
};
}
fn get(comptime T: type, blob: []const u8, pos: *usize) T {
const v = std.mem.readInt(T, blob[pos.*..][0..@sizeOf(T)], .little);
pos.* += @sizeOf(T);
return v;
}
/// The stored index brought up to date with `log`, as an owned blob: adopted
/// as it stands when it covers the whole log, extended over the appended
/// tail when it covers a prefix, built by one full sweep otherwise, and
/// stored back when it changed. Null when no trustworthy index can be had
/// (a frame would not read, the log is past `max_rid`, the key would not
/// compute); the caller then classifies by reading.
pub fn loadOrBuild(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, log: *logstore.LogStore) error{OutOfMemory}!?[]u8 {
const stored = try repocache.loadMember(gpa, io, dir, member);
var keep_stored = false;
defer if (stored) |s| if (!keep_stored) gpa.free(s);
const adopted: ?Index = if (stored) |s| parse(s, log) else null;
if (adopted) |*idx| {
if (idx.coversAll(log)) {
keep_stored = true;
return stored;
}
}
var b = Builder.init(gpa);
defer b.deinit();
var from: u64 = 0;
if (adopted) |*idx| {
try b.absorb(idx);
from = idx.key.end;
}
b.sweep(log, from) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Unreadable, error.Overflow => return null,
};
const blob = (try serialize(gpa, log, &b)) orelse return null;
repocache.storeNamedMember(io, dir, member, blob);
return blob;
}
// ---------------------------------------------------------------------------
// Tests. Goal: the codec carries every fact a sweep records and refuses a
// damaged blob; folding a tail into an adopted index gives the same bytes as
// sweeping the grown log whole. Method: a small log of blobs and a manifest,
// grown by a second manifest. The classifier-level equality lives with
// `LogIndexStore`, which owns the rid map the classifier needs.
// ---------------------------------------------------------------------------
const testing = std.testing;
fn testPut(gpa: std.mem.Allocator, log: *logstore.LogStore, bytes: []const u8, name_out: []u8) !logstore.Rid {
var buf: [64]u8 = undefined;
const name = artifact.artifactName(.sha3_256, bytes, &buf);
@memcpy(name_out[0..name.len], name);
var digest: [32]u8 = undefined;
_ = try std.fmt.hexToBytes(&digest, name);
_ = gpa;
return log.put(&digest, bytes);
}
fn testManifest(gpa: std.mem.Allocator, cards: []const [2][]const u8) ![]u8 {
var body: std.ArrayListUnmanaged(u8) = .empty;
errdefer body.deinit(gpa);
try body.appendSlice(gpa, "C c\nD 2026-10-21T12:00:00.000\n");
for (cards) |c| try body.print(gpa, "F {s} {s}\n", .{ c[0], c[1] });
try body.appendSlice(gpa, "U u\n");
var digest: [16]u8 = undefined;
std.crypto.hash.Md5.hash(body.items, &digest, .{});
try body.print(gpa, "Z {x}\n", .{&digest});
return body.toOwnedSlice(gpa);
}
test "coneindex: a swept index round-trips, and a tail fold equals a whole sweep" {
const gpa = testing.allocator;
const io = testing.io;
var tmp = 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 a: [64]u8 = undefined;
var b2: [64]u8 = undefined;
var m: [64]u8 = undefined;
_ = try testPut(gpa, &log, "alpha\n", &a);
_ = try testPut(gpa, &log, "beta\n", &b2);
const missing = repeat("ab", 32); // a target the log never sees
const m1 = try testManifest(gpa, &.{ .{ "src/a", &a }, .{ "src/b", &b2 }, .{ "src/gone", missing } });
defer gpa.free(m1);
const m1_rid = try testPut(gpa, &log, m1, &m);
try log.commit();
var first = Builder.init(gpa);
defer first.deinit();
try first.sweep(&log, 0);
const blob1 = (try serialize(gpa, &log, &first)).?;
defer gpa.free(blob1);
const idx1 = parse(blob1, &log).?;
try testing.expect(idx1.coversAll(&log));
try testing.expect(idx1.isStructural(@intCast(m1_rid)));
try testing.expect(!idx1.isStructural(1));
try testing.expectEqual(@as(u32, 2), idx1.n_paths);
var dang = idx1.texts(.dangling);
try testing.expectEqualStrings("src/gone\x00" ++ missing, dang.next().?);
try testing.expect(dang.next() == null);
// Grow the log: the second check-in renames src/a and keeps src/b.
const m2 = try testManifest(gpa, &.{ .{ "lib/a", &a }, .{ "src/b", &b2 } });
defer gpa.free(m2);
_ = try testPut(gpa, &log, m2, &m);
try log.commit();
try testing.expect(!idx1.coversAll(&log));
var folded = Builder.init(gpa);
defer folded.deinit();
const reparsed = parse(blob1, &log).?;
try folded.absorb(&reparsed);
try folded.sweep(&log, idx1.key.end);
const blob_folded = (try serialize(gpa, &log, &folded)).?;
defer gpa.free(blob_folded);
var whole = Builder.init(gpa);
defer whole.deinit();
try whole.sweep(&log, 0);
const blob_whole = (try serialize(gpa, &log, &whole)).?;
defer gpa.free(blob_whole);
try testing.expectEqualSlices(u8, blob_whole, blob_folded);
try testing.expectEqual(@as(u32, 3), parse(blob_whole, &log).?.n_paths);
// A flipped byte is refused rather than adopted.
const bad = try gpa.dupe(u8, blob_whole);
defer gpa.free(bad);
bad[header_len + 1] ^= 1;
try testing.expect(parse(bad, &log) == null);
}