//! The structural graph of a store, independent of any horizon or cone: for
//! every held artifact that parses as structural, its kind and the rids its
//! P, B, S, F and A cards name. Classifying a store under a horizon
//! (draft-fossil-horizon section 4) needs exactly this and nothing else from
//! the artifacts, and reading it is where the whole cost of a first
//! classification goes: every structural artifact inflated and parsed once,
//! minutes on a store of a few hundred thousand check-ins. The graph is read
//! once per store, extended by the artifacts appended since (the log is
//! append-only, so rids below the recorded count never change), and kept in
//! a `.zit-cache` sidecar keyed to the log prefix it covers. A classification
//! over the graph is a walk over arrays.
//!
//! What it does NOT carry: filenames, and F-card targets. A cone with path
//! members needs filenames for `covers`, and such a classification parses
//! as before; the horizon alone, which is what a structural clone and the
//! CI loop over it use, never does. F-card targets are the bulk of a store's
//! references (a sub-manifest store of a few hundred thousand check-ins has
//! tens of millions) and the classification needs them for exactly two
//! things: the blobs of the check-ins K reaches, read from those few
//! artifacts on demand, and whether a blob is cited by ANY held structural
//! artifact, which is one bitset kept here.
const std = @import("std");
const artifact = @import("artifact.zig");
const repostate = @import("repostate.zig");
const logstore = @import("logstore.zig");
const repocache = @import("repocache.zig");
const codec = @import("container.zig");
const crc32 = @import("crc32.zig");
const delta_mod = @import("delta.zig");
const Rid = repostate.Rid;
const native_le = @import("builtin").cpu.arch.endian() == .little;
pub const Kind = enum(u8) {
/// Not structural: a content blob, or not held.
blob = 0,
manifest = 1,
submanifest = 2,
cluster = 3,
/// Control, wiki, ticket, technote, forum, attachment: kept whatever
/// the horizon says.
other = 4,
};
/// One structural artifact's graph references, as rids. Slices borrow the
/// graph and stay valid until it is extended or freed.
pub const Record = struct {
kind: Kind,
parents: []const u32,
baseline: ?u32,
nodes: []const u32,
attachment_source: ?u32,
};
pub const Graph = struct {
/// Rids covered: every held rid in 1..=n has a record (possibly `blob`).
n: u32 = 0,
/// `kind[rid]` for rid in 0..=n (index 0 unused).
kind: std.ArrayListUnmanaged(u8) = .empty,
/// `start[rid]`..`start[rid+1]` is rid's span in `refs`; len n+2.
start: std.ArrayListUnmanaged(u32) = .empty,
/// Spans: n_p, p..., baseline-or-0, n_s, s..., attachment-or-0.
refs: std.ArrayListUnmanaged(u32) = .empty,
/// Rids some held structural artifact's F card names (held targets only).
/// A held blob not in here is referenced by nothing and is kept whatever
/// the horizon; one in here is kept only when a kept manifest names it.
cited: std.DynamicBitSetUnmanaged = .{},
/// P, B and S names cited by a held artifact that the store did not hold
/// when it was read, each with the `refs` slots that cite it, 0 until the
/// name arrives. `extend` fills the slots when it does, so a parent that
/// arrives after its children leaves them connected rather than orphaned
/// for good. Such an arrival also changes what older check-ins mean (see
/// sparse.ClassifyState), so a classifier that extended from an older
/// state must start over. Keys and lists owned.
dangling: std.StringHashMapUnmanaged(std.ArrayListUnmanaged(u32)) = .empty,
pub fn deinit(self: *Graph, gpa: std.mem.Allocator) void {
self.kind.deinit(gpa);
self.start.deinit(gpa);
self.refs.deinit(gpa);
self.cited.deinit(gpa);
var it = self.dangling.iterator();
while (it.next()) |kv| {
gpa.free(kv.key_ptr.*);
kv.value_ptr.deinit(gpa);
}
self.dangling.deinit(gpa);
self.* = .{};
}
/// A 0 among `parents` or `nodes` is a citation the store did not hold
/// when the artifact was read and has not held since; readers skip it.
pub fn record(self: *const Graph, rid: Rid) ?Record {
if (rid == 0 or rid > self.n) return null;
const r: usize = @intCast(rid);
const kind: Kind = @fromBackingInt(@intCast(self.kind.items[r]));
if (kind == .blob) return null;
var pos: usize = self.start.items[r];
const refs = self.refs.items;
const n_p = refs[pos];
pos += 1;
const parents = refs[pos .. pos + n_p];
pos += n_p;
const b = refs[pos];
pos += 1;
const n_s = refs[pos];
pos += 1;
const nodes = refs[pos .. pos + n_s];
pos += n_s;
const a = refs[pos];
return .{
.kind = kind,
.parents = parents,
.baseline = if (b == 0) null else b,
.nodes = nodes,
.attachment_source = if (a == 0) null else a,
};
}
fn dangle(self: *Graph, gpa: std.mem.Allocator, name: []const u8, slot: ?u32) error{OutOfMemory}!void {
const gop = try self.dangling.getOrPut(gpa, name);
if (!gop.found_existing) {
gop.value_ptr.* = .empty;
gop.key_ptr.* = gpa.dupe(u8, name) catch |e| {
self.dangling.removeByPtr(gop.key_ptr);
return e;
};
}
if (slot) |s| try gop.value_ptr.append(gpa, s);
}
/// Append one P/B/S citation as a `refs` slot: the held rid it names, or
/// 0 recorded under the name for `extend` to fill when it arrives. Never
/// interns: the graph describes what is held.
fn appendRef(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore, name: []const u8) error{OutOfMemory}!void {
const slot: u32 = @intCast(self.refs.items.len);
try self.refs.append(gpa, 0);
if (store.lookup(name)) |rid| {
if (store.held(rid)) {
self.refs.items[slot] = @intCast(rid);
return;
}
}
try self.dangle(gpa, name, slot);
}
/// Fill every slot that cited `rid`'s name before it was held.
fn resolveArrival(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore, rid: Rid) void {
if (self.dangling.count() == 0) return;
var kv = self.dangling.fetchRemove(store.hashOf(rid)) orelse return;
for (kv.value.items) |slot| self.refs.items[slot] = @intCast(rid);
kv.value.deinit(gpa);
gpa.free(kv.key);
}
/// Does an artifact in `from..=count` carry a name a held artifact cited
/// before it arrived?
pub fn arrivalWasCited(self: *const Graph, store: repostate.ArtifactStore, from: Rid) bool {
if (self.dangling.count() == 0) return false;
const n = store.count();
var rid = from;
while (rid <= n) : (rid += 1) {
if (!store.held(rid)) continue;
if (self.dangling.contains(store.hashOf(rid))) return true;
}
return false;
}
/// Read the held rids in `n+1..=count()` into the graph. Rids must fit
/// 32 bits.
pub fn extend(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore) error{OutOfMemory}!void {
const count = store.count();
if (count >= std.math.maxInt(u32)) return error.OutOfMemory;
const n_new: u32 = @intCast(count);
if (self.cited.capacity() < count + 1) try self.cited.resize(gpa, count + 1, false);
if (self.kind.items.len == 0) {
try self.kind.append(gpa, 0);
try self.start.append(gpa, 0);
try self.start.append(gpa, 0);
}
try self.kind.ensureTotalCapacity(gpa, n_new + 1);
try self.start.ensureTotalCapacity(gpa, n_new + 2);
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
var memo = try PrefixMemo.init(gpa, n_new);
defer memo.deinit(gpa);
var rid: Rid = self.n + 1;
while (rid <= n_new) : (rid += 1) {
// Every rid gets a kind and a (possibly empty) span, so `record`
// indexes by rid alone.
const span_start: u32 = @intCast(self.refs.items.len);
var kind: Kind = .blob;
if (store.held(rid)) self.resolveArrival(gpa, store, rid);
if (store.held(rid) and mayBeStructuralMemo(gpa, store, rid, &memo)) {
if (store.content(rid)) |plain| {
if (looksStructural(plain)) {
_ = arena_state.reset(.retain_capacity);
const aa = arena_state.allocator();
if (artifact.parseForImport(aa, plain)) |im| {
kind = switch (im.manifest.kind) {
.manifest => .manifest,
.submanifest => .submanifest,
.cluster => .cluster,
else => .other,
};
try self.appendRefs(gpa, store, &im.manifest);
} else |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => {}, // a content blob that began like a card
}
}
}
}
self.kind.appendAssumeCapacity(@backingInt(kind));
// start[rid] was appended as the previous span's end; append this
// span's end as start[rid+1].
std.debug.assert(self.start.items[@intCast(rid)] == span_start);
self.start.appendAssumeCapacity(@intCast(self.refs.items.len));
}
self.n = n_new;
}
fn appendRefs(self: *Graph, gpa: std.mem.Allocator, store: repostate.ArtifactStore, m: *const artifact.Manifest) error{OutOfMemory}!void {
const refs = &self.refs;
const n_p_at = refs.items.len;
try refs.append(gpa, 0);
var n_p: u32 = 0;
for (m.p) |pc| {
var it = pc.hashes();
while (it.next()) |ph| {
try self.appendRef(gpa, store, ph);
n_p += 1;
}
}
refs.items[n_p_at] = n_p;
if (m.b) |b| try self.appendRef(gpa, store, b.hash) else try refs.append(gpa, 0);
const n_s_at = refs.items.len;
try refs.append(gpa, 0);
var n_s: u32 = 0;
for (m.s) |sc| {
try self.appendRef(gpa, store, sc.hash);
n_s += 1;
}
refs.items[n_s_at] = n_s;
for (m.f) |fc| {
const h = fc.hash orelse continue;
const rid = store.lookup(h) orelse continue;
if (!store.held(rid)) continue;
if (rid >= self.cited.capacity()) try self.cited.resize(gpa, rid + 1, false);
self.cited.set(rid);
}
var a: u32 = 0;
if (m.a) |ac| {
if (ac.source) |src| {
if (store.lookup(src)) |rid| {
if (store.held(rid)) a = @intCast(rid);
}
}
}
try refs.append(gpa, a);
}
// -- sidecar --------------------------------------------------------------
const magic: *const [8]u8 = "ZITSGRPH";
/// 2: a dangling name carries the slots that cite it; a cited name that
/// was unresolved holds a 0 slot instead of being dropped.
const version: u16 = 2;
pub const member = "graph";
fn putInt(out: *std.ArrayListUnmanaged(u8), gpa: std.mem.Allocator, comptime T: type, v: T) error{OutOfMemory}!void {
var buf: [@sizeOf(T)]u8 = undefined;
std.mem.writeInt(T, &buf, v, .little);
try out.appendSlice(gpa, &buf);
}
fn putU32s(out: *std.ArrayListUnmanaged(u8), gpa: std.mem.Allocator, items: []const u32) error{OutOfMemory}!void {
try putInt(out, gpa, u64, items.len);
const bytes = std.mem.sliceAsBytes(items);
if (native_le) {
try out.appendSlice(gpa, bytes);
} else {
for (items) |v| try putInt(out, gpa, u32, v);
}
}
/// The graph for a store whose first `n` rids are the log's frames under
/// `key`. Null when the graph covers more than the log (session rids).
pub fn serialize(self: *const Graph, gpa: std.mem.Allocator, key: logstore.LogStore.LogKey, n_log: u64) error{OutOfMemory}!?[]u8 {
if (self.n != n_log) return null;
var out: std.ArrayListUnmanaged(u8) = .empty;
errdefer out.deinit(gpa);
try out.appendSlice(gpa, magic);
try putInt(&out, gpa, u16, version);
try putInt(&out, gpa, u64, key.end);
try putInt(&out, gpa, u64, key.frame_count);
try putInt(&out, gpa, u64, key.last_frame_offset);
try putInt(&out, gpa, u32, key.last_header_crc);
try putInt(&out, gpa, u32, self.n);
try putInt(&out, gpa, u64, self.kind.items.len);
try out.appendSlice(gpa, self.kind.items);
try putU32s(&out, gpa, self.start.items);
try putU32s(&out, gpa, self.refs.items);
// The cited set, as 64-bit words over 0..=n.
const n_bits: usize = @as(usize, self.n) + 1;
try putInt(&out, gpa, u64, n_bits);
var w: usize = 0;
if (native_le and @bitSizeOf(std.DynamicBitSetUnmanaged.MaskInt) == 64) {
// Whole words straight from the masks, up to the last one the
// set holds in full; the loop below finishes the tail.
const full_words = @min(n_bits, self.cited.capacity()) / 64;
try out.appendSlice(gpa, std.mem.sliceAsBytes(self.cited.masks[0..full_words]));
w = full_words;
}
while (w * 64 < n_bits) : (w += 1) {
var word: u64 = 0;
var i: usize = 0;
while (i < 64 and w * 64 + i < n_bits) : (i += 1) {
const bit = w * 64 + i;
if (bit < self.cited.capacity() and self.cited.isSet(bit)) word |= @as(u64, 1) << @intCast(i);
}
try putInt(&out, gpa, u64, word);
}
try putInt(&out, gpa, u32, @intCast(self.dangling.count()));
var it = self.dangling.iterator();
while (it.next()) |kv| {
if (kv.key_ptr.len > 255) return null;
try out.append(gpa, @intCast(kv.key_ptr.len));
try out.appendSlice(gpa, kv.key_ptr.*);
try putU32s(&out, gpa, kv.value_ptr.items);
}
var crc = crc32.Crc32.init();
crc.update(out.items);
try putInt(&out, gpa, u32, crc.final());
return try out.toOwnedSlice(gpa);
}
const Reader = struct {
buf: []const u8,
pos: usize = 0,
fn int(self: *Reader, comptime T: type) ?T {
if (self.pos + @sizeOf(T) > self.buf.len) return null;
const v = std.mem.readInt(T, self.buf[self.pos..][0..@sizeOf(T)], .little);
self.pos += @sizeOf(T);
return v;
}
fn bytes(self: *Reader, len: usize) ?[]const u8 {
if (self.pos + len > self.buf.len) return null;
const s = self.buf[self.pos..][0..len];
self.pos += len;
return s;
}
fn u32s(self: *Reader, gpa: std.mem.Allocator, out: *std.ArrayListUnmanaged(u32)) error{OutOfMemory}!bool {
const len: usize = std.math.cast(usize, self.int(u64) orelse return false) orelse return false;
const raw = self.bytes(std.math.mul(usize, len, 4) catch return false) orelse return false;
try out.ensureTotalCapacityPrecise(gpa, out.items.len + len);
const dst = out.addManyAsSliceAssumeCapacity(len);
if (native_le) {
@memcpy(std.mem.sliceAsBytes(dst), raw);
} else {
for (dst, 0..) |*v, i| v.* = std.mem.readInt(u32, raw[i * 4 ..][0..4], .little);
}
return true;
}
};
pub const Parsed = struct { key: logstore.LogStore.LogKey, graph: Graph };
/// Parse a sidecar: magic, version and CRC must hold, or null.
pub fn parse(gpa: std.mem.Allocator, blob: []const u8) error{OutOfMemory}!?Parsed {
if (blob.len < 8 + 2 + 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 r: Reader = .{ .buf = blob[0 .. blob.len - 4], .pos = 8 };
if ((r.int(u16) orelse return null) != version) return null;
const key = logstore.LogStore.LogKey{
.end = r.int(u64) orelse return null,
.frame_count = r.int(u64) orelse return null,
.last_frame_offset = r.int(u64) orelse return null,
.last_header_crc = r.int(u32) orelse return null,
};
var g: Graph = .{};
errdefer g.deinit(gpa);
g.n = r.int(u32) orelse return null;
const kind_len: usize = std.math.cast(usize, r.int(u64) orelse return null) orelse return null;
try g.kind.appendSlice(gpa, r.bytes(kind_len) orelse return null);
if (!try r.u32s(gpa, &g.start)) return null;
if (!try r.u32s(gpa, &g.refs)) return null;
if (g.kind.items.len != @as(usize, g.n) + 1 or g.start.items.len != @as(usize, g.n) + 2) return null;
if (g.start.items[g.start.items.len - 1] != g.refs.items.len) return null;
const n_bits: usize = std.math.cast(usize, r.int(u64) orelse return null) orelse return null;
if (n_bits != @as(usize, g.n) + 1) return null;
try g.cited.resize(gpa, n_bits, false);
const n_words = (n_bits + 63) / 64;
const words = r.bytes(n_words * 8) orelse return null;
if (native_le and @bitSizeOf(std.DynamicBitSetUnmanaged.MaskInt) == 64) {
// The bitset's masks are these words, bit i of word w being bit
// 64w+i; the bits past n_bits must stay clear.
const masks = g.cited.masks[0..n_words];
@memcpy(std.mem.sliceAsBytes(masks), words);
const tail: u6 = @intCast(n_bits % 64);
if (tail != 0) masks[n_words - 1] &= (@as(u64, 1) << tail) - 1;
} else {
var w: usize = 0;
while (w < n_words) : (w += 1) {
const word = std.mem.readInt(u64, words[w * 8 ..][0..8], .little);
var i: usize = 0;
while (i < 64 and w * 64 + i < n_bits) : (i += 1) {
if ((word >> @intCast(i)) & 1 != 0) g.cited.set(w * 64 + i);
}
}
}
const n_dangling = r.int(u32) orelse return null;
var i: u32 = 0;
while (i < n_dangling) : (i += 1) {
const len = (r.bytes(1) orelse return null)[0];
const nm = r.bytes(len) orelse return null;
var slots: std.ArrayListUnmanaged(u32) = .empty;
defer slots.deinit(gpa);
if (!try r.u32s(gpa, &slots)) return null;
try g.dangle(gpa, nm, null);
for (slots.items) |slot| {
if (slot >= g.refs.items.len) return null;
try g.dangle(gpa, nm, slot);
}
}
if (r.pos != r.buf.len) return null;
return .{ .key = key, .graph = g };
}
/// Load the graph sidecar for `log` when it is still a prefix, extend it
/// over `store` (reading only the rids appended since), and write it back
/// when the extension read anything. Any sidecar trouble is a fresh read
/// of the whole store.
pub fn loadOrBuild(gpa: std.mem.Allocator, io: std.Io, cache_dir: std.Io.Dir, log: *const logstore.LogStore, store: repostate.ArtifactStore) error{OutOfMemory}!Graph {
var g: ?Graph = null;
errdefer if (g) |*x| x.deinit(gpa);
const n_log: u64 = log.entryCount();
var adopted_n: ?u32 = null;
if (try repocache.loadMember(gpa, io, cache_dir, member)) |blob| {
defer gpa.free(blob);
if (try parse(gpa, blob)) |p_const| {
var p = p_const;
if (p.graph.n <= n_log and logstore.LogStore.validatePrefix(log.file, p.key)) {
g = p.graph;
adopted_n = p.graph.n;
} else {
p.graph.deinit(gpa);
}
}
}
if (g == null) g = .{};
try g.?.extend(gpa, store);
// Rewriting an unchanged sidecar is a whole serialization, write and
// fsync of it, paid by every fresh server on its first request.
if (adopted_n == g.?.n) return g.?;
if (log.logKey()) |key| {
if (try g.?.serialize(gpa, key, n_log)) |blob| {
defer gpa.free(blob);
repocache.storeNamedMember(io, cache_dir, member, blob);
}
} else |_| {}
return g.?;
}
};
/// The cheap half of `looksStructural`: for an artifact the store holds as a
/// FULL container, inflate only the first two bytes and apply the same test;
/// for a delta whose first segment is a literal, test the literal. Anything
/// else (a store with no wire form, a delta that begins by copying) answers
/// true and falls through to the full read.
pub fn mayBeStructural(gpa: std.mem.Allocator, store: repostate.ArtifactStore, rid: Rid) bool {
return peekStructural(gpa, store, rid, null, 0);
}
/// `mayBeStructural`'s answers so far in one sweep, by rid. With it a delta
/// whose first segment copies the start of its base takes the base's answer,
/// asked once per base: a sweep in rid order meets every base first, so each
/// artifact costs one short inflate. A sweep that answered by reading would
/// reconstruct every delta-stored blob in the store to look at two bytes,
/// which on a large store is most of what building the graph costs.
const PrefixMemo = struct {
known: std.DynamicBitSetUnmanaged,
maybe: std.DynamicBitSetUnmanaged,
fn init(gpa: std.mem.Allocator, n: usize) error{OutOfMemory}!PrefixMemo {
var known = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1);
errdefer known.deinit(gpa);
return .{ .known = known, .maybe = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n + 1) };
}
fn deinit(self: *PrefixMemo, gpa: std.mem.Allocator) void {
self.known.deinit(gpa);
self.maybe.deinit(gpa);
}
};
/// `mayBeStructural` over a sweep's memo (see `PrefixMemo`).
fn mayBeStructuralMemo(gpa: std.mem.Allocator, store: repostate.ArtifactStore, rid: Rid, memo: *PrefixMemo) bool {
return peekStructural(gpa, store, rid, memo, max_peek_chain);
}
/// How many copy-first bases a peek follows: the store's delta chain bound.
const max_peek_chain: u8 = 32;
/// Enough of a raw delta for its length line and one segment's header (each
/// integer at most six digits) and two literal bytes.
const delta_peek_len: usize = 32;
fn peekStructural(gpa: std.mem.Allocator, store: repostate.ArtifactStore, rid: Rid, memo: ?*PrefixMemo, depth: u8) bool {
if (memo) |m| {
if (rid < m.known.capacity() and m.known.isSet(rid)) return m.maybe.isSet(rid);
}
const verdict = peekUnmemoized(gpa, store, rid, memo, depth);
if (memo) |m| {
if (rid < m.known.capacity()) {
m.known.set(rid);
m.maybe.setValue(rid, verdict);
}
}
return verdict;
}
fn peekUnmemoized(gpa: std.mem.Allocator, store: repostate.ArtifactStore, rid: Rid, memo: ?*PrefixMemo, depth: u8) bool {
const wf = store.wire(rid) orelse return true;
const d = wf.delta orelse {
const head = codec.decodePrefix(gpa, wf.container, 2) catch return true;
defer gpa.free(head);
return looksStructural(head);
};
const head = codec.decodePrefix(gpa, wf.container, delta_peek_len) catch return true;
defer gpa.free(head);
// The wire form is borrowed until the store's next `wire`, which the
// base's peek is: keep the base's name.
var src_buf: [64]u8 = undefined;
if (d.src_hash.len > src_buf.len) return true;
@memcpy(src_buf[0..d.src_hash.len], d.src_hash);
const src = src_buf[0..d.src_hash.len];
switch (firstSegment(head)) {
.short => return false,
.literal => |b| return looksStructural(&b),
.copy_from_start => {
if (depth == 0) return true;
const base = store.lookup(src) orelse return true;
if (base == rid or !store.held(base)) return true;
return peekStructural(gpa, store, base, memo, depth - 1);
},
.unknown => return true,
}
}
/// What a raw delta's first segment says about the target's first two bytes
/// (delta format: a length line, then `N@O,` copies and `N:` literals). A
/// malformed delta is `unknown`, and its full read reports it.
const FirstSegment = union(enum) {
/// The target is shorter than two bytes.
short,
/// The target begins with these bytes.
literal: [2]u8,
/// The target begins with its base's first two bytes.
copy_from_start,
unknown,
};
fn firstSegment(raw: []const u8) FirstSegment {
const size = delta_mod.decodeInt(raw) catch return .unknown;
if (size.len == 0 or size.len >= raw.len or raw[size.len] != '\n') return .unknown;
if (size.value < 2) return .short;
const p = size.len + 1;
const count = delta_mod.decodeInt(raw[p..]) catch return .unknown;
const q = p + count.len;
if (count.len == 0 or q >= raw.len or count.value < 2) return .unknown;
switch (raw[q]) {
':' => {
if (q + 3 > raw.len) return .unknown;
return .{ .literal = raw[q + 1 ..][0..2].* };
},
'@' => {
const off = delta_mod.decodeInt(raw[q + 1 ..]) catch return .unknown;
const r = q + 1 + off.len;
if (off.len == 0 or r >= raw.len or raw[r] != ',') return .unknown;
return if (off.value == 0) .copy_from_start else .unknown;
},
else => return .unknown,
}
}
/// Could these bytes be a structural artifact at all? Every artifact begins
/// with a card -- an upper-case letter, a space -- or with the PGP or SSH
/// signature envelope the format admits around one, which begins with `-`.
pub fn looksStructural(plain: []const u8) bool {
if (plain.len < 2) return false;
if (plain[0] == '-') return true;
return std.ascii.isUpper(plain[0]) and plain[1] == ' ';
}
test "graph: records round-trip through the sidecar and extend reads only the tail" {
const gpa = std.testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
const s = ms.store();
const blob_a = "1111111111111111111111111111111111111111111111111111111111111111";
_ = try s.put(blob_a, "hello");
// A minimal check-in manifest naming blob_a.
var m = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.b = null,
.c = .{ .comment = "c" },
.d = .{ .timestamp = "2026-01-01T00:00:00" },
.a = null,
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{.{ .filename = "a.txt", .hash = blob_a, .perm = null, .old_name = null, .mode = .regular }},
.j = &.{},
.m = &.{},
.p = &.{},
.q = &.{},
.s = &.{},
.t = &.{},
};
defer m.deinit();
const bytes = try artifact.create(&m, gpa);
defer gpa.free(bytes);
var name: [64]u8 = undefined;
const nm = artifact.artifactName(.sha3_256, bytes, &name);
var g: Graph = .{};
defer g.deinit(gpa);
try g.extend(gpa, s);
try std.testing.expectEqual(@as(u32, 1), g.n);
try std.testing.expect(g.record(1) == null); // the blob
_ = try s.put(nm, bytes);
try g.extend(gpa, s);
const rec = g.record(2).?;
try std.testing.expectEqual(Kind.manifest, rec.kind);
try std.testing.expect(g.cited.isSet(1));
try std.testing.expectEqual(@as(usize, 0), rec.parents.len);
const key = logstore.LogStore.LogKey{ .end = 1, .frame_count = 2, .last_frame_offset = 3, .last_header_crc = 4 };
const blob = (try g.serialize(gpa, key, 2)).?;
defer gpa.free(blob);
var p = (try Graph.parse(gpa, blob)).?;
defer p.graph.deinit(gpa);
try std.testing.expectEqual(key, p.key);
try std.testing.expectEqual(g.n, p.graph.n);
try std.testing.expectEqualSlices(u32, g.refs.items, p.graph.refs.items);
try std.testing.expect(p.graph.cited.isSet(1));
try std.testing.expect(!p.graph.cited.isSet(2));
try std.testing.expectEqual(Kind.manifest, p.graph.record(2).?.kind);
}
test "graph: a parent that arrives after its child fills the child's slot, through the sidecar too" {
const gpa = std.testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
const s = ms.store();
const blob_a = "1111111111111111111111111111111111111111111111111111111111111111";
_ = try s.put(blob_a, "hello");
var parent = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.b = null,
.c = .{ .comment = "parent" },
.d = .{ .timestamp = "2026-01-01T00:00:00" },
.a = null,
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{.{ .filename = "a.txt", .hash = blob_a, .perm = null, .old_name = null, .mode = .regular }},
.j = &.{},
.m = &.{},
.p = &.{},
.q = &.{},
.s = &.{},
.t = &.{},
};
defer parent.deinit();
const parent_bytes = try artifact.create(&parent, gpa);
defer gpa.free(parent_bytes);
var parent_name: [64]u8 = undefined;
const pn = artifact.artifactName(.sha3_256, parent_bytes, &parent_name);
var child = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.b = null,
.c = .{ .comment = "child" },
.d = .{ .timestamp = "2026-01-02T00:00:00" },
.a = null,
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{.{ .filename = "a.txt", .hash = blob_a, .perm = null, .old_name = null, .mode = .regular }},
.j = &.{},
.m = &.{},
.p = &.{.{ .parents = pn, .count = 1 }},
.q = &.{},
.s = &.{},
.t = &.{},
};
defer child.deinit();
const child_bytes = try artifact.create(&child, gpa);
defer gpa.free(child_bytes);
var child_name: [64]u8 = undefined;
const cn = artifact.artifactName(.sha3_256, child_bytes, &child_name);
// The child arrives first: its one parent slot is 0 and the name dangles.
_ = try s.put(cn, child_bytes);
var g: Graph = .{};
defer g.deinit(gpa);
try g.extend(gpa, s);
try std.testing.expectEqualSlices(u32, &.{0}, g.record(2).?.parents);
try std.testing.expectEqual(@as(usize, 1), g.dangling.count());
// Through the sidecar the slot survives.
const key = logstore.LogStore.LogKey{ .end = 1, .frame_count = 2, .last_frame_offset = 3, .last_header_crc = 4 };
const blob = (try g.serialize(gpa, key, 2)).?;
defer gpa.free(blob);
var p = (try Graph.parse(gpa, blob)).?;
defer p.graph.deinit(gpa);
try std.testing.expectEqual(@as(usize, 1), p.graph.dangling.count());
try std.testing.expectEqualSlices(u32, g.dangling.get(pn).?.items, p.graph.dangling.get(pn).?.items);
// The parent arrives: both graphs link the child to it and nothing dangles.
_ = try s.put(pn, parent_bytes);
try g.extend(gpa, s);
try p.graph.extend(gpa, s);
try std.testing.expectEqualSlices(u32, &.{3}, g.record(2).?.parents);
try std.testing.expectEqualSlices(u32, &.{3}, p.graph.record(2).?.parents);
try std.testing.expectEqual(@as(usize, 0), g.dangling.count());
try std.testing.expectEqual(@as(usize, 0), p.graph.dangling.count());
try std.testing.expect(!g.arrivalWasCited(s, 3));
}
/// A check-in manifest naming `blob` as `a.txt`, with `parent` as its P card
/// when given. Caller frees.
fn testManifest(gpa: std.mem.Allocator, comment: []const u8, blob: []const u8, parent: ?[]const u8) ![]u8 {
var m = artifact.Manifest{
.arena_state = std.heap.ArenaAllocator.init(gpa),
.kind = .manifest,
.b = null,
.c = .{ .comment = comment },
.d = .{ .timestamp = "2026-01-01T00:00:00" },
.a = null,
.e = null,
.g = null,
.h = null,
.i = null,
.k = null,
.l = null,
.n = null,
.r = null,
.u = .{ .login = "u" },
.z = null,
.w = null,
.f = &.{.{ .filename = "a.txt", .hash = blob, .perm = null, .old_name = null, .mode = .regular }},
.j = &.{},
.m = &.{},
.p = if (parent) |p| &.{.{ .parents = p, .count = 1 }} else &.{},
.q = &.{},
.s = &.{},
.t = &.{},
};
defer m.deinit();
return artifact.create(&m, gpa);
}
test "graph: a delta-stored blob is told apart by its first delta segment, never reconstructed, and the graph is the one read by content" {
const gpa = std.testing.allocator;
const delta = delta_mod;
// Store each artifact as a wire store holds it: full containers and
// deltas against an earlier artifact. The same artifacts put as plain
// bytes give the graph by content to compare with.
var wired = repostate.MemStore.init(gpa);
defer wired.deinit();
var plain = repostate.MemStore.init(gpa);
defer plain.deinit();
const Art = struct { name: []const u8, bytes: []const u8, base: ?usize };
var arts: std.ArrayListUnmanaged(Art) = .empty;
defer arts.deinit(gpa);
var owned: std.ArrayListUnmanaged([]u8) = .empty;
defer {
for (owned.items) |b| gpa.free(b);
owned.deinit(gpa);
}
const line = "the quick brown fox jumps over the lazy dog, again and again\n";
const text = line ++ line ++ line ++ line;
try arts.append(gpa, .{ .name = "1111111111111111111111111111111111111111111111111111111111111111", .bytes = text, .base = null });
// Copy-first: the blob begins with its base's bytes.
try arts.append(gpa, .{ .name = "2222222222222222222222222222222222222222222222222222222222222222", .bytes = text ++ "one more line\n", .base = 0 });
// Literal-first: the blob begins with bytes the base does not have.
try arts.append(gpa, .{ .name = "3333333333333333333333333333333333333333333333333333333333333333", .bytes = "zz" ++ text, .base = 0 });
// A chain: copy-first against a delta.
try arts.append(gpa, .{ .name = "4444444444444444444444444444444444444444444444444444444444444444", .bytes = text ++ "one more line\nand another\n", .base = 1 });
// A blob that begins like a card: a delta that must be read in full.
try arts.append(gpa, .{ .name = "5555555555555555555555555555555555555555555555555555555555555555", .bytes = "Q " ++ text, .base = 0 });
// Check-in manifests, the child stored as a delta of its parent.
const parent_bytes = try testManifest(gpa, "parent", arts.items[1].name, null);
try owned.append(gpa, parent_bytes);
var parent_name: [64]u8 = undefined;
const pn = artifact.artifactName(.sha3_256, parent_bytes, &parent_name);
try arts.append(gpa, .{ .name = pn, .bytes = parent_bytes, .base = null });
const child_bytes = try testManifest(gpa, "parent", arts.items[3].name, pn);
try owned.append(gpa, child_bytes);
var child_name: [64]u8 = undefined;
try arts.append(gpa, .{ .name = artifact.artifactName(.sha3_256, child_bytes, &child_name), .bytes = child_bytes, .base = 5 });
var first_ops: [7]u8 = @splat(0);
for (arts.items, 0..) |a, i| {
_ = try plain.store().put(a.name, a.bytes);
if (a.base) |bi| {
const raw = try delta.create(gpa, arts.items[bi].bytes, a.bytes);
defer gpa.free(raw);
// The op of the first segment, past the header line and count.
const nl = std.mem.indexOfScalar(u8, raw, '\n').?;
first_ops[i] = raw[nl + 1 + (try delta.decodeInt(raw[nl + 1 ..])).len];
const c = try codec.encode(gpa, raw, .default);
defer gpa.free(c);
_ = try wired.putWireDelta(a.name, c, arts.items[bi].name, a.bytes.len);
} else {
const c = try codec.encode(gpa, a.bytes, .default);
defer gpa.free(c);
_ = try wired.putWire(a.name, c);
}
}
// The fixture exercises both segment kinds.
try std.testing.expectEqual(@as(u8, '@'), first_ops[1]);
try std.testing.expectEqual(@as(u8, ':'), first_ops[2]);
try std.testing.expectEqual(@as(u8, '@'), first_ops[3]);
var by_wire: Graph = .{};
defer by_wire.deinit(gpa);
try by_wire.extend(gpa, wired.store());
var by_content: Graph = .{};
defer by_content.deinit(gpa);
try by_content.extend(gpa, plain.store());
// No blob behind a delta was reconstructed; the card-like one and the
// manifests were.
for ([_]usize{ 1, 2, 3 }) |i| try std.testing.expect(wired.entries.items[i].bytes == null);
try std.testing.expect(wired.entries.items[4].bytes != null);
try std.testing.expect(wired.entries.items[6].bytes != null);
try std.testing.expectEqual(by_content.n, by_wire.n);
try std.testing.expectEqualSlices(u8, by_content.kind.items, by_wire.kind.items);
try std.testing.expectEqualSlices(u32, by_content.start.items, by_wire.start.items);
try std.testing.expectEqualSlices(u32, by_content.refs.items, by_wire.refs.items);
var rid: usize = 0;
while (rid <= by_content.n) : (rid += 1) try std.testing.expectEqual(by_content.cited.isSet(rid), by_wire.cited.isSet(rid));
try std.testing.expectEqual(Kind.manifest, by_wire.record(7).?.kind);
try std.testing.expectEqualSlices(u32, &.{6}, by_wire.record(7).?.parents);
}
fn expectSameGraph(want: *const Graph, got: *const Graph) !void {
try std.testing.expectEqual(want.n, got.n);
try std.testing.expectEqualSlices(u8, want.kind.items, got.kind.items);
try std.testing.expectEqualSlices(u32, want.start.items, got.start.items);
try std.testing.expectEqualSlices(u32, want.refs.items, got.refs.items);
try std.testing.expectEqual(want.dangling.count(), got.dangling.count());
var rid: usize = 0;
while (rid <= want.n) : (rid += 1) try std.testing.expectEqual(want.cited.isSet(rid), got.cited.isSet(rid));
}
test "graph sidecar: adopted while it describes the log, rewritten only when extended, rebuilt when stale or damaged" {
const gpa = std.testing.allocator;
const io = std.testing.io;
const storage = @import("storage.zig");
var tmp = std.testing.tmpDir(.{});
defer tmp.cleanup();
const raw = try tmp.dir.createFile(io, "log", .{ .read = true });
defer raw.close(io);
var fs = storage.FileStorage.init(io, raw, 0);
var log = try logstore.LogStore.open(gpa, fs.storageFile(), 0);
defer log.deinit(gpa);
// The graph reads the store; the log supplies only the key and the count
// (the holdings adapters' rid contract: the first rids are its frames).
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
const s = ms.store();
const blob = "1111111111111111111111111111111111111111111111111111111111111111";
const parent = try testManifest(gpa, "parent", blob, null);
defer gpa.free(parent);
var pn_buf: [64]u8 = undefined;
const pn = artifact.artifactName(.sha3_256, parent, &pn_buf);
const child = try testManifest(gpa, "child", blob, pn);
defer gpa.free(child);
var cn_buf: [64]u8 = undefined;
const cn = artifact.artifactName(.sha3_256, child, &cn_buf);
const member_path = repocache.cache_dirname ++ "/" ++ Graph.member;
_ = try s.put(blob, "hello");
_ = try log.put(&@as([32]u8, @splat(1)), "hello");
_ = try s.put(pn, parent);
_ = try log.put(&@as([32]u8, @splat(2)), parent);
try log.commit();
var built = try Graph.loadOrBuild(gpa, io, tmp.dir, &log, s);
defer built.deinit(gpa);
const written = try tmp.dir.statFile(io, member_path, .{});
// A sidecar that still describes the log is adopted as it is: nothing
// was learned, so nothing is written.
var adopted = try Graph.loadOrBuild(gpa, io, tmp.dir, &log, s);
defer adopted.deinit(gpa);
try expectSameGraph(&built, &adopted);
try std.testing.expectEqual(written.inode, (try tmp.dir.statFile(io, member_path, .{})).inode);
// Grown: extended over the new frame, equal to a graph read from
// scratch, and written back.
_ = try s.put(cn, child);
_ = try log.put(&@as([32]u8, @splat(3)), child);
try log.commit();
var fresh: Graph = .{};
defer fresh.deinit(gpa);
try fresh.extend(gpa, s);
var grown = try Graph.loadOrBuild(gpa, io, tmp.dir, &log, s);
defer grown.deinit(gpa);
try expectSameGraph(&fresh, &grown);
const rewritten = try tmp.dir.statFile(io, member_path, .{});
try std.testing.expect(rewritten.inode != written.inode);
// Damaged: one flipped byte is a rebuild, never a wrong graph.
{
const f = try tmp.dir.openFile(io, member_path, .{ .mode = .read_write });
defer f.close(io);
var b: [1]u8 = undefined;
_ = try f.readPositionalAll(io, &b, 40);
b[0] ^= 0x55;
try f.writePositionalAll(io, &b, 40);
}
var repaired = try Graph.loadOrBuild(gpa, io, tmp.dir, &log, s);
defer repaired.deinit(gpa);
try expectSameGraph(&fresh, &repaired);
const after_damage = try tmp.dir.statFile(io, member_path, .{});
try std.testing.expect(after_damage.inode != rewritten.inode);
// Stale: a sidecar keyed to another log of the same length is a
// rebuild over this one.
const raw2 = try tmp.dir.createFile(io, "log2", .{ .read = true });
defer raw2.close(io);
var fs2 = storage.FileStorage.init(io, raw2, 0);
var other = try logstore.LogStore.open(gpa, fs2.storageFile(), 0);
defer other.deinit(gpa);
var i: u8 = 0;
while (i < 3) : (i += 1) _ = try other.put(&@as([32]u8, @splat(0x40 + i)), "other bytes");
try other.commit();
var ms2 = repostate.MemStore.init(gpa);
defer ms2.deinit();
_ = try ms2.store().put(blob, "hello");
_ = try ms2.store().put("2222222222222222222222222222222222222222222222222222222222222222", "other bytes");
_ = try ms2.store().put("3333333333333333333333333333333333333333333333333333333333333333", "more bytes");
var fresh2: Graph = .{};
defer fresh2.deinit(gpa);
try fresh2.extend(gpa, ms2.store());
var rebuilt = try Graph.loadOrBuild(gpa, io, tmp.dir, &other, ms2.store());
defer rebuilt.deinit(gpa);
try expectSameGraph(&fresh2, &rebuilt);
try std.testing.expect(rebuilt.record(3) == null);
}
test "graph sidecar: the cited set round-trips across whole words and a partial last one" {
const gpa = std.testing.allocator;
var ms = repostate.MemStore.init(gpa);
defer ms.deinit();
const s = ms.store();
// 130 blobs, so the set spans two whole 64-bit words and part of a third,
// and manifests citing blobs in each.
var names: [130][64]u8 = undefined;
for (&names, 0..) |*nm, i| {
var digest: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(std.mem.asBytes(&i), &digest, .{});
nm.* = std.fmt.bytesToHex(digest, .lower);
_ = try s.put(nm, std.mem.asBytes(&i));
}
for ([_]usize{ 0, 63, 64, 127, 129 }) |i| {
const m = try testManifest(gpa, "m", &names[i], null);
defer gpa.free(m);
var mn: [64]u8 = undefined;
_ = try s.put(artifact.artifactName(.sha3_256, m, &mn), m);
}
var g: Graph = .{};
defer g.deinit(gpa);
try g.extend(gpa, s);
const key = logstore.LogStore.LogKey{ .end = 1, .frame_count = 2, .last_frame_offset = 3, .last_header_crc = 4 };
const blob = (try g.serialize(gpa, key, g.n)).?;
defer gpa.free(blob);
var p = (try Graph.parse(gpa, blob)).?;
defer p.graph.deinit(gpa);
try expectSameGraph(&g, &p.graph);
for ([_]usize{ 1, 64, 65, 128, 130 }) |rid| try std.testing.expect(p.graph.cited.isSet(rid));
try std.testing.expectEqual(@as(usize, 5), p.graph.cited.count());
}