//! zit — the `Repository` facade: one deep module for opening a repository and
//! answering the derived and content questions every read verb asks.
//!
//! The north star names this the public repo surface. It folds the open
//! sequence that each read verb used to hand-wire — open `.zit`, take the O(1)
//! `.zit-cache` fast path (repo-state §1 memo) or derive the crosslinked
//! `RepoState` from the log, close the file — behind `open`, and serves the
//! derived queries (`resolve`, `branchOf`, `state`, `currentCheckoutRid`) plus
//! the lazily-opened content path (`manifest`, `blob`) that `ls`/`cat` lean on.
//!
//! Determinism seam (design-seams rule): this module touches no clock, RNG,
//! ambient cwd, or network. Discovery of the checkout root — which reads the
//! process cwd — stays in the CLI; `open` operates on an already-discovered
//! `root_dir` and the injected `std.Io`. The log is reopened lazily only when a
//! content request arrives, so view-only verbs keep the O(1) cache fast path.
//!
//! Pinning: `state` (inside the loaded `RepoView`) borrows the view's own
//! `MemStore`, and a lazily-opened `LogStore` borrows this struct's inline
//! `FileStorage`. `open` therefore fills the caller's `Repository` in place
//! (`self: *Repository`); a filled `Repository` must not be moved.
const std = @import("std");
const artifact = @import("artifact.zig");
const repostate = @import("repostate.zig");
const logstore = @import("logstore.zig");
const storage = @import("storage.zig");
const checkout = @import("checkout.zig");
const repoview = @import("repoview.zig");
const repoimage = @import("repoimage.zig");
const repocache = @import("repocache.zig");
const checkpoint = @import("checkpoint.zig");
const cone_mod = @import("cone.zig");
/// The repository file, beside `.zit-checkout` in the checkout root. Shared with
/// the CLI (re-exported from root.zig) so the one name has a single home.
pub const repo_filename: []const u8 = ".zit";
/// draft-fossil-submanifests-00 §6.3/§8.1 — the writer-side sub-manifest
/// settings, and the two decisions they determine: whether a commit emits a
/// tree, and with which k.
///
/// It lives beside the repository facade rather than inside `RepoView` on
/// purpose. `RepoView`'s fields are exactly what the `.zit-cache` fast path
/// must reproduce without reading the log, so putting a setting there means
/// widening the cache record format; and no DERIVED query — leaf table, branch
/// tags, ancestry — reads these. They are read once, by the writer, at the
/// moment it decides what to emit, straight from the config frame it already
/// holds. `main_branch` is threaded through the view because `branchOf` needs it
/// on every derived answer; this does not.
pub const submanifest = struct {
/// The settings as stored, before any range judgement.
pub const Settings = struct {
/// §8.1's `enable-submanifests` — "a project-scope boolean, default false".
enabled: bool,
/// §6.3's pinned `submanifest-k`, exactly as stored. 0 means unpinned.
k: u8,
/// The state of a repository that has never been opted in — what every
/// repository predating this draft decodes to.
pub const off: Settings = .{ .enabled = false, .k = 0 };
pub fn of(cfg: logstore.Config) Settings {
return .{ .enabled = cfg.enable_submanifests, .k = cfg.submanifest_k };
}
/// §8.1: "an implementation MUST NOT enable emission on a repository
/// with no pinned parameter." The predicate an enable surface checks
/// BEFORE writing the setting, so the refusal is stated once.
pub fn pinned(self: Settings) bool {
return self.k != 0;
}
};
/// §6.3's range test: "a writer ... MUST support every value from 1 to 12
/// inclusive (the pinned value MUST lie in that range)". The one place the
/// bound is spelled; both the pin surface and the emission decision read it.
pub fn inRange(k: u8) bool {
return k >= artifact.min_k and k <= artifact.max_k;
}
/// What a commit does about sub-manifests, given the repository's settings.
///
/// Three outcomes, not two, because §6.3's out-of-range fallback is NOT the
/// same event as the setting being off: "on receiving a value outside 1..12
/// it MUST fall back to emitting flat manifests rather than substitute a
/// parameter of its own, and SHOULD report the fallback to the operator."
/// Off is silent and is what every repository does; the fallback is a
/// misconfiguration the operator is told about. Collapsing them into one
/// `?u4` would lose exactly the distinction the SHOULD asks for.
pub const Emission = union(enum) {
/// §8.1 — the setting is false. The default, and silent.
off,
/// §6.3 — enabled, but the pinned value is outside 1..12 (0 included,
/// which is "enabled with nothing pinned", a state §8.1 forbids
/// creating and this reports rather than repairs). Payload is the
/// offending value, for the operator report.
out_of_range: u8,
/// §6.2/§6.3 — emit the canonical tree, partitioned at this k.
tree: u4,
/// The k a writer partitions at, or null when this commit emits a flat
/// manifest. One accessor so a call site reads the decision once (the
/// report in the `out_of_range` arm is a side effect of PRODUCING the
/// decision, so evaluating it twice would print it twice).
pub fn treeK(self: Emission) ?u4 {
return switch (self) {
.tree => |k| k,
.off, .out_of_range => null,
};
}
};
/// The §8.1 + §6.3 emission decision. Pure; the writer's only input beyond
/// the file list.
///
/// §8.1's second conjunct — "MUST NOT emit one in a commit against a server
/// from which it has received the avoid-submanifests pragma in the current
/// sync session" — is deliberately NOT folded in here. A zit commit is a
/// purely local act against no server (`sync.clientMayEmitSCards` is where
/// that conjunct lives, on the Client that received the pragma), so there is
/// no session for this call to consult. If a commit-against-a-server verb is
/// ever added, it reads both.
pub fn emission(s: Settings) Emission {
if (!s.enabled) return .off;
if (!inRange(s.k)) return .{ .out_of_range = s.k };
return .{ .tree = @intCast(s.k) };
}
/// §6.3's operator report for the out-of-range fallback ("SHOULD report the
/// fallback to the operator"). Named here so the writer and any future
/// status surface print one text.
pub const out_of_range_report_prefix = "sub-manifests: pinned submanifest-k is out of range";
// -----------------------------------------------------------------------
// §6.3/§6.4 — the analysis pass.
// -----------------------------------------------------------------------
/// draft-fossil-submanifests-00 §6.3 defines C(k) from serialized leaf
/// bytes and S cards naming leaves. This fixed-width SHA-256 cache key
/// records every F-card property that can change that cost. Hash values
/// themselves are deliberately excluded: only their token width affects
/// serialized F and S card sizes.
///
/// The digest is a local optimization, not an RFC artifact or setting.
pub const CostShapeDigest = [32]u8;
/// Hash the framed draft-fossil-submanifests-00 §6.3 cost inputs in
/// canonical F-card order. Every variable field carries its length, so
/// adjacent values cannot alias a different sequence of fields. Callers
/// own `out` and may persist it as a settled analysis memo.
pub fn costShapeDigest(
entries: []const artifact.FCard,
out: *CostShapeDigest,
) []const u8 {
var hasher = std.crypto.hash.sha2.Sha256.init(.{});
hashShapeLength(&hasher, entries.len);
for (entries) |entry| {
hashShapeEntry(&hasher, entry);
}
hasher.final(out);
std.debug.assert(out.len == 32);
return out;
}
fn hashShapeEntry(hasher: *std.crypto.hash.sha2.Sha256, entry: artifact.FCard) void {
hashShapeBytes(hasher, entry.filename);
hashShapeOptionalBytes(hasher, entry.perm, false);
hashShapeOptionalBytes(hasher, entry.old_name, true);
hashShapeLength(hasher, if (entry.hash) |hash| hash.len else 0);
}
fn hashShapeOptionalBytes(
hasher: *std.crypto.hash.sha2.Sha256,
value: ?[]const u8,
canonical: bool,
) void {
const present: [1]u8 = .{@intFromBool(value != null)};
hasher.update(&present);
const bytes = value orelse return;
const encoded_len = if (canonical) canonicalLen(bytes) else bytes.len;
hashShapeLength(hasher, encoded_len);
hasher.update(bytes);
}
fn hashShapeBytes(hasher: *std.crypto.hash.sha2.Sha256, bytes: []const u8) void {
hashShapeLength(hasher, bytes.len);
hasher.update(bytes);
}
fn hashShapeLength(hasher: *std.crypto.hash.sha2.Sha256, len: usize) void {
std.debug.assert(@as(u128, len) <= std.math.maxInt(u64));
var buf: [8]u8 = undefined;
std.mem.writeInt(u64, &buf, @intCast(len), .little);
hasher.update(&buf);
}
/// §6.3's cost for one candidate k over one name set: "choose the value
/// minimizing the S card bytes referencing the leaves plus the size-weighted
/// mean leaf bytes".
pub const Cost = struct {
/// The candidate.
k: u4,
/// §6.2 step 2's flat outcome — fewer than two groups, so there are no
/// leaves and no S cards. `total` is 0 and the value never wins a
/// comparison against a real tree (see `best`).
flat: bool,
/// Number of height-0 groups (leaf sub-manifests).
leaves: usize,
/// Total tree depth in sub-manifest artifacts, leaf counted (0 if flat).
heights: usize,
/// "the S card bytes referencing the leaves" — the serialized bytes of
/// every S card whose hash token names a LEAF, wherever that card lives
/// (an interior sub-manifest, or the manifest's own S run for a
/// depth-one tree). A total, as the wording says.
s_bytes: usize,
/// "the size-weighted mean leaf bytes" — sum(size^2)/sum(size) over the
/// leaf artifacts. Read literally: the weight IS the size, so this is
/// the expected leaf size seen by a uniformly-chosen leaf BYTE. (The
/// neighbouring reading — weight by member count, the expected leaf size
/// seen by a uniformly-chosen FILE — differs only where leaf size and
/// member count diverge, and the draft names size, not membership.)
weighted_mean_leaf_bytes: f64,
/// The §6.3 objective: `s_bytes + weighted_mean_leaf_bytes`.
total: f64,
/// Flat F-card bytes for the same entries, for the §6.5 comparison. Not
/// part of the objective; reported so a table shows what the tree costs
/// against.
flat_bytes: usize,
};
/// Run §6.3's cost function for one k over `entries` (the same canonical,
/// hashed, sorted F-card list `buildTree` takes). Advisory only: "The
/// selection is advisory rather than canonical -- any pinned k yields
/// conforming artifacts".
pub fn cost(
gpa: std.mem.Allocator,
entries: []const artifact.FCard,
k: u4,
algo: artifact.HashAlgo,
) std.mem.Allocator.Error!Cost {
std.debug.assert(inRange(k));
var flat_bytes: usize = 0;
for (entries) |e| flat_bytes += flatFCardBytes(e);
var built = try artifact.buildTree(gpa, entries, k, algo);
defer built.deinit();
if (built.isFlat()) {
return .{
.k = k,
.flat = true,
.leaves = 0,
.heights = 0,
.s_bytes = 0,
.weighted_mean_leaf_bytes = 0,
.total = 0,
.flat_bytes = flat_bytes,
};
}
// A leaf sub-manifest's first card is F, an interior's is S (§6.2 steps
// 2 and 3, and the card order the serializer emits). `subs` is height-0
// first, so the leaves are the run at the front — but keying on the card
// letter rather than on a position the caller cannot see keeps this
// independent of `TreeBuild`'s internal layout.
var leaves: usize = 0;
var size_sum: f64 = 0;
var sq_sum: f64 = 0;
for (built.subs) |sub| {
std.debug.assert(sub.bytes.len != 0);
const is_leaf = sub.bytes[0] == 'F';
std.debug.assert(is_leaf or sub.bytes[0] == 'S');
if (!is_leaf) continue;
leaves += 1;
const sz: f64 = @floatFromInt(sub.bytes.len);
size_sum += sz;
sq_sum += sz * sz;
}
std.debug.assert(leaves >= 2); // a non-flat build partitions at least in two
// "the S card bytes referencing the leaves": walk every S card the tree
// emits — the manifest's own run plus every interior sub-manifest's run
// — and count the bytes of those whose hash token names a leaf. Bounded
// by the tree's total card count.
var s_bytes: usize = 0;
for (built.s) |card| {
if (namesLeaf(built.subs, card.hash)) s_bytes += sCardBytes(card);
}
for (built.subs) |sub| {
if (sub.bytes[0] != 'S') continue;
var it = std.mem.splitScalar(u8, sub.bytes, '\n');
while (it.next()) |line| {
if (line.len < 2 or line[0] != 'S' or line[1] != ' ') continue;
const sp = std.mem.lastIndexOfScalar(u8, line, ' ') orelse continue;
if (namesLeaf(built.subs, line[sp + 1 ..])) s_bytes += line.len + 1; // + the card's LF
}
}
const mean: f64 = if (size_sum == 0) 0 else sq_sum / size_sum;
const heights = treeDepth(built.subs, built.s);
return .{
.k = k,
.flat = false,
.leaves = leaves,
.heights = heights,
.s_bytes = s_bytes,
.weighted_mean_leaf_bytes = mean,
.total = @as(f64, @floatFromInt(s_bytes)) + mean,
.flat_bytes = flat_bytes,
};
}
/// §6.3's selection over the whole supported range: the k minimizing
/// `Cost.total`, or null when no k yields a tree at all (a name set too
/// small to partition, §6.2 step 2). Ties go to the smaller k — arbitrary,
/// but fixed, so the pass is deterministic.
///
/// Advisory ONLY. §6.4: "A re-tune MUST be manual and operator-initiated; an
/// implementation MAY advise of drift from the analyzed optimum but MUST NOT
/// re-tune automatically". Nothing calls this from a commit path.
/// §6.3: "The implementation SHOULD choose the candidate with the lowest
/// C(k), and MUST choose the lowest k among candidates with equal minimum
/// cost." The tie-break is the MUST, so the comparison is strict `<` and
/// `costs` is walked in ascending k: an equal total never displaces the
/// incumbent, which is the lower k. A tie is not a free choice — the pin is
/// the repository's identity for content sharing (§6.4), so two writers
/// breaking ties differently would silently stop sharing sub-manifests.
pub fn best(costs: []const Cost) ?Cost {
var winner: ?Cost = null;
for (costs) |c| {
if (c.flat) continue;
if (winner) |w| {
std.debug.assert(c.k > w.k); // ascending order: what makes `<` the tie-break
if (c.total < w.total) winner = c;
} else winner = c;
}
return winner;
}
/// One candidate k's replayed outcome over the window (#41). Both cost
/// axes, with the bootstrap — the one-time first-emission of the whole
/// forest — split from the steady state, so the verdict does not become a
/// monotone function of the window length.
pub const ReplayArm = struct {
k: u4,
/// Every window commit built flat at this k (§6.2 step 2): the arm is
/// byte-identical to the flat history and carries no evidence either way.
all_flat: bool,
/// Sub-arm stored bytes charged to the window's FIRST commit — the
/// forest bootstrap plus that commit's root.
bootstrap_store: u64,
/// Sub-arm stored bytes over the remaining commits: new/changed nodes
/// at the writer's real choice of full-vs-delta container, plus roots.
steady_store: u64,
/// Sub-arm materialization bytes (plaintext a derive must produce):
/// roots plus first-appearance nodes — memo hits are free, which is
/// the §7.4 mechanism the whole bet rests on.
bootstrap_full: u64,
steady_full: u64,
};
/// The #41 materiality reference: average flat-arm materialization per
/// commit below which the F-card wall sits inside the format's own
/// documented design envelope (~20k files, ~1.5 MB manifests — the load
/// its designer said it was built for). NEVER a gate term: the evidence
/// verdict is the operator's history versus itself, and an informed
/// operator outranks this tool's opinion of what is worth caring about.
/// It is printed beside a positive verdict so the operator weighs the
/// ABSOLUTE cost — a 90% saving on 85 KB/commit is a different decision
/// than 98% of 5 MB/commit — with the one-way door's price in view.
pub const replay_materiality_reference: u64 = 1 << 20;
/// The #41 replay: the operator's own last-`window` check-ins run through
/// the real tree builder and the real delta encoder, per candidate k,
/// against the flat arm's REAL, already-paid bytes. History predicts, it
/// does not guarantee — but this is the strongest evidence the
/// intertemporal structure of the enable decision permits.
pub const Replay = struct {
/// Check-ins actually replayed (≤ the requested window; capped by
/// history, and commits whose file set cannot be enumerated are
/// skipped and uncounted).
commits: usize,
/// The flat arm: real stored frame bytes of those manifests.
flat_store: u64,
/// The flat arm's materialization bytes (manifest plaintexts).
flat_full: u64,
/// The same two, excluding the first replayed commit — the steady
/// state the sub arms' steady figures compare against.
flat_store_steady: u64,
flat_full_steady: u64,
arms: []ReplayArm,
pub fn deinit(self: *Replay, gpa: std.mem.Allocator) void {
gpa.free(self.arms);
self.* = undefined;
}
/// Average flat-arm materialization per steady-state commit — the
/// absolute cost the materiality note reports.
pub fn flatFullSteadyPerCommit(self: *const Replay) u64 {
if (self.commits < 2) return 0;
return self.flat_full_steady / @as(u64, @intCast(self.commits - 1));
}
/// Whether this history sits inside the format's design envelope —
/// report-only context beside a positive verdict, never a refusal.
pub fn insideDesignEnvelope(self: *const Replay) bool {
return self.flatFullSteadyPerCommit() < replay_materiality_reference;
}
/// The evidence verdict: the arm with the lowest steady-state
/// materialization cost, or null when every arm stayed flat.
pub fn bestArm(self: *const Replay) ?ReplayArm {
var winner: ?ReplayArm = null;
for (self.arms) |a| {
if (a.all_flat) continue;
if (winner == null or a.steady_full < winner.?.steady_full) winner = a;
}
return winner;
}
};
/// Run the replay over the last `window` check-ins (walk order — the
/// order they were persisted) for each candidate in `ks`. See `Replay`.
/// The flat arm is measured, never simulated: stored frame spans and
/// manifest plaintext lengths from the live log. The sub arm runs
/// `artifact.buildTree` per commit per k, credits content-addressed
/// dedupe (an unchanged node costs nothing), and costs a changed node at
/// the writer's REAL choice — the §4.1 container of the full form or of a
/// [FossilDelta] against the same-position previous version, whichever is
/// smaller — so the delta win the whole question turns on is neither
/// assumed nor denied. Roots are re-serialized with the real writer (the
/// S run replacing the F run) and costed the same two-way way.
pub fn replay(
gpa: std.mem.Allocator,
repo: *Repository,
window: usize,
ks: []const u4,
) error{ OutOfMemory, Storage, Corrupt }!Replay {
const codec = @import("container.zig");
const delta_mod = @import("delta.zig");
const all = repo.view.state.events.keys();
if (all.len == 0 or window == 0) return .{
.commits = 0,
.flat_store = 0,
.flat_full = 0,
.flat_store_steady = 0,
.flat_full_steady = 0,
.arms = try gpa.alloc(ReplayArm, 0),
};
const start_at = all.len -| window;
const rids = all[start_at..];
// The repository's identity space names the algorithm: 40-hex is SHA-1.
const algo: artifact.HashAlgo = if (repo.hashOf(rids[rids.len - 1]).len == 40) .sha1 else .sha3_256;
const log = repo.logStore(gpa) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.Storage,
};
var out: Replay = .{
.commits = 0,
.flat_store = 0,
.flat_full = 0,
.flat_store_steady = 0,
.flat_full_steady = 0,
.arms = try gpa.alloc(ReplayArm, ks.len),
};
errdefer gpa.free(out.arms);
for (out.arms, ks) |*a, k| a.* = .{ .k = k, .all_flat = true, .bootstrap_store = 0, .steady_store = 0, .bootstrap_full = 0, .steady_full = 0 };
// Per-arm cross-commit memory: node names ever stored (dedupe), the
// previous version of every (height, key) position (delta bases), and
// the previous root. All owned copies — a build's arena dies with its
// commit.
const ArmState = struct {
seen: std.StringHashMapUnmanaged(void) = .empty,
prev_by_pos: std.StringHashMapUnmanaged([]u8) = .empty,
prev_root: ?[]u8 = null,
};
const arm_states = try gpa.alloc(ArmState, ks.len);
defer {
for (arm_states) |*st| {
var kit = st.seen.keyIterator();
while (kit.next()) |kk| gpa.free(kk.*);
st.seen.deinit(gpa);
var pit = st.prev_by_pos.iterator();
while (pit.next()) |e| {
gpa.free(e.key_ptr.*);
gpa.free(e.value_ptr.*);
}
st.prev_by_pos.deinit(gpa);
if (st.prev_root) |r| gpa.free(r);
}
gpa.free(arm_states);
}
for (arm_states) |*st| st.* = .{};
const raw_hash_len: u64 = if (algo == .sha1) 20 else 32;
for (rids) |rid| {
// The flat arm, measured.
const c_hex = repo.hashOf(rid);
var digest_buf: [logstore.max_hash_len]u8 = undefined;
const c_raw = digest_buf[0 .. c_hex.len / 2];
_ = std.fmt.hexToBytes(c_raw, c_hex) catch continue;
const c_logrid = log.lookup(c_raw) orelse continue;
var owned = (repo.manifest(gpa, rid) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => continue,
}) orelse continue;
defer owned.deinit(gpa);
var fl = (repo.files(gpa, rid) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => continue,
}) orelse continue;
defer fl.deinit(gpa);
var entries: std.ArrayList(artifact.FCard) = .empty;
defer entries.deinit(gpa);
var it = fl.iterator();
while (it.next()) |f| try entries.append(gpa, f);
const first = out.commits == 0;
out.commits += 1;
const flat_span = log.frameSpanOf(c_logrid);
// The full-form axis charges what producing this commit's FILE
// SET actually materializes. For a baseline manifest that is its
// own plaintext; for a B-card DELTA manifest it is the delta PLUS
// its baseline — "resolving a delta manifest requires loading,
// parsing, and holding its full baseline in memory" (the reason
// delta manifests never rescued the F-card wall), and `files`
// above really did read both (`FileList.baseline`). Charging the
// delta's own bytes alone hid a ~400x cost on a fossil-style
// delta-manifest history and mis-verdicted the one corpus the
// S-card design was written for.
const flat_materialized: u64 = owned.bytes.len +
(if (fl.baseline) |b| b.bytes.len else 0);
out.flat_store += flat_span;
out.flat_full += flat_materialized;
if (!first) {
out.flat_store_steady += flat_span;
out.flat_full_steady += flat_materialized;
}
// The sub arms.
for (out.arms, arm_states) |*arm, *st| {
var build = try artifact.buildTree(gpa, entries.items, arm.k, algo);
defer build.deinit();
if (build.isFlat()) {
// §6.2 step 2: this commit stays flat at this k — the arm
// pays exactly what the flat history paid.
if (first) {
arm.bootstrap_store += flat_span;
arm.bootstrap_full += owned.bytes.len;
} else {
arm.steady_store += flat_span;
arm.steady_full += owned.bytes.len;
}
continue;
}
arm.all_flat = false;
var store_bytes: u64 = 0;
var full_bytes: u64 = 0;
// The root, with the real writer: S run in, F run out.
var root_manifest = owned.manifest;
root_manifest.f = &.{};
root_manifest.s = build.s;
// A tree manifest is a BASELINE by construction (§4.4: never
// both B and S): a replayed commit whose real manifest was a
// delta still emits its tree root over the flattened set.
root_manifest.b = null;
const root_bytes = artifact.create(&root_manifest, gpa) catch return error.OutOfMemory;
defer gpa.free(root_bytes);
full_bytes += root_bytes.len;
store_bytes += try replayFrameCost(gpa, codec, delta_mod, raw_hash_len, root_bytes, st.prev_root);
if (st.prev_root) |r| gpa.free(r);
st.prev_root = try gpa.dupe(u8, root_bytes);
for (build.subs) |sub| {
if (st.seen.contains(sub.name)) continue; // content-addressed dedupe: free
full_bytes += sub.bytes.len;
var poskey_buf: [8]u8 = undefined;
const pos_prefix = std.fmt.bufPrint(&poskey_buf, "{d}:", .{sub.height}) catch unreachable;
const poskey = try std.mem.concat(gpa, u8, &.{ pos_prefix, sub.key });
defer gpa.free(poskey);
const prev = st.prev_by_pos.get(poskey);
store_bytes += try replayFrameCost(gpa, codec, delta_mod, raw_hash_len, sub.bytes, prev);
// Update cross-commit memory.
const name_owned = try gpa.dupe(u8, sub.name);
st.seen.put(gpa, name_owned, {}) catch |e| {
gpa.free(name_owned);
return e;
};
const bytes_owned = try gpa.dupe(u8, sub.bytes);
const gop = st.prev_by_pos.getOrPut(gpa, poskey) catch |e| {
gpa.free(bytes_owned);
return e;
};
if (gop.found_existing) {
gpa.free(gop.value_ptr.*);
gop.value_ptr.* = bytes_owned;
} else {
gop.key_ptr.* = try gpa.dupe(u8, poskey);
gop.value_ptr.* = bytes_owned;
}
}
if (first) {
arm.bootstrap_store += store_bytes;
arm.bootstrap_full += full_bytes;
} else {
arm.steady_store += store_bytes;
arm.steady_full += full_bytes;
}
}
}
return out;
}
/// The stored-frame cost of one replayed artifact: the writer's real
/// choice between the full-form §4.1 container and a [FossilDelta]
/// container against `prev` (when a previous same-position version
/// exists), plus the log's frame overhead for the winner.
fn replayFrameCost(
gpa: std.mem.Allocator,
comptime codec: type,
comptime delta_mod: type,
raw_hash_len: u64,
bytes: []const u8,
prev: ?[]const u8,
) error{OutOfMemory}!u64 {
const full = codec.encode(gpa, bytes, .default) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return logstore.frameSpan(raw_hash_len, bytes.len), // uncodable: charge plaintext
};
defer gpa.free(full);
var best_len: usize = full.len;
if (prev) |p| {
if (delta_mod.create(gpa, p, bytes)) |d| {
defer gpa.free(d);
const dc = codec.encode(gpa, d, .default) catch null;
if (dc) |c| {
defer gpa.free(c);
if (c.len < best_len) best_len = c.len;
}
} else |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => {},
}
}
return logstore.frameSpan(raw_hash_len, best_len);
}
/// §6.5's informative prediction: "the analyzed optimum tracks roughly half
/// the base-2 logarithm of the file count". Reported beside the measurement
/// so a table shows predicted against measured; never an input to a default.
pub fn predictedK(file_count: usize) f64 {
if (file_count < 2) return 0;
return 0.5 * @log2(@as(f64, @floatFromInt(file_count)));
}
/// draft-fossil-submanifests-00 §6.4's relative margin `m`, expressed as a
/// percentage of the pinned value's own §6.3 objective: "The writer MUST
/// retain the current value unless the candidate is distinct and
/// C_candidate < (1 - m) * C_current, where m is a documented,
/// implementation-defined relative margin satisfying 0 < m < 1." This
/// comment is that documentation. Grounded in two measurements: a real
/// "fossil" project corpus (983 files) shows k=4 vs k=5 within ~5% of
/// each other -- "close to arbitrary on cost grounds", and MUST be
/// refused; a zit-repo-shaped synthetic set (112 files) shows the pinned
/// k=1 vs the true k=3 optimum at ~57.8% -- real drift, and MUST be
/// recommended. 15% clears the first case with room to spare while still
/// catching the second (every measured real-drift case lands far
/// larger). §6.4 leaves m implementation-defined and calls the selection
/// objective and margin "advisory rather than canonical": an
/// implementation choice, not a canonical value.
///
/// §6.4 requires m to be DOCUMENTED, and a source comment an operator
/// never reads does not discharge that. The normative operator-facing
/// statement of this value is the sub-manifest advisory paragraph of
/// `commit_help` (`main.zig`), which `zit commit --help` prints; `e2e.zig`
/// holds an independent transcription of that block.
///
/// Two separate gates keep the three in agreement, because the pair of them
/// is what the first draft of this comment wrongly claimed of one: the e2e
/// help comparison pins `commit_help` against the `e2e.zig` transcription,
/// and the unit test "commit help states the live §6.4 margin, not a copy
/// of it" (`main.zig`) renders THIS constant and requires `commit_help` to
/// contain it. Without the second, both help texts could keep saying "15%"
/// after this line changed and every lane would stay green.
pub const drift_margin_pct: f64 = 15.0;
/// The result of a drift check that recommends a re-tune: the winning
/// `Cost` (so the caller has the candidate k and its measurements
/// without a second pass) and the margin by which it beats the pinned
/// value's own objective, as a percentage of the pinned objective.
pub const DriftCheck = struct {
recommended: Cost,
margin_pct: f64,
};
/// draft-fossil-submanifests-00 §6.4's drift-check core: whether
/// `pinned_k`'s current §6.3 objective has drifted far enough from the
/// analyzed optimum to RECOMMEND a re-tune. Pure and side-effect-free --
/// it does not retune, write config, or prompt anyone; the caller
/// decides what to do with the answer. §6.4: "An implementation MAY advise
/// of drift from the analyzed optimum at any time." It is also the margin
/// gate §6.4 requires of a writer comparing the deterministic candidate
/// against the current pinned value, so the automatic re-tune path -- which
/// §6.4 permits only while `submanifest-auto-retune` is true -- consults
/// this same answer instead of computing a second one.
///
/// Costs every k in 1..12 (exactly 12 `cost` calls -- §6.3's whole
/// supported range, the same "operator-invoked measurement, not a
/// commit-path cost" `namesLeaf` already accepts) and returns null when:
/// - no k partitions at all (§6.2 step 2 -- nothing to compare against),
/// - the pinned k itself does not partition (out of this check's
/// scope -- that is §6.3's flat-fallback case, not a re-tune),
/// - the pinned k already IS the analyzed optimum (nothing to
/// recommend), or
/// - the pinned k's margin against the optimum does not EXCEED
/// `drift_margin_pct` (an exact-margin case is refused, not accepted:
/// §6.4's gate is the strict "C_candidate < (1 - m) * C_current", so
/// equality leaves the current pin in place).
///
/// Confirmed contract decision, not a unilateral shortcut: this always
/// runs the full 1..12 §6.3 cost scan and never gates on `predictedK`.
/// A cheap tier keyed on round(predictedK(file_count)) == pinned_k was
/// considered and rejected -- it would return null without computing a
/// single real cost whenever file count alone happened to imply the
/// pinned k, which is a false negative in the one thing this check
/// exists to catch: the real §6.3 objective depends on leaf SIZE
/// distribution, not just count, so a count-matching k can still carry
/// real, margin-clearing drift. This is evidenced, not asserted -- the
/// test "submanifests §6.4: predictedK never gates the check -- a
/// count-matching k with real drift still recommends" exhibits a real
/// (n, pinned_k) pair where exactly that happens. The scan stays cheap
/// in absolute terms regardless -- exactly 12 `cost` calls, the same
/// "operator-invoked measurement, not a commit-path cost" `namesLeaf`
/// already accepts -- so there is no efficiency case left for accepting
/// the false-negative risk.
pub fn driftCheck(
gpa: std.mem.Allocator,
entries: []const artifact.FCard,
pinned_k: u4,
algo: artifact.HashAlgo,
) std.mem.Allocator.Error!?DriftCheck {
std.debug.assert(inRange(pinned_k));
var costs: [artifact.max_k - artifact.min_k + 1]Cost = undefined;
var n: usize = 0;
var pinned_cost: ?Cost = null;
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
const c = try cost(gpa, entries, k, algo);
if (k == pinned_k) pinned_cost = c;
costs[n] = c;
n += 1;
if (k == artifact.max_k) break;
}
const winner = best(costs[0..n]) orelse return null;
const pinned = pinned_cost.?; // pinned_k in 1..12, scanned above
if (pinned.flat) return null;
if (winner.k == pinned.k) return null;
const margin_pct = marginGate(pinned.total, winner.total) orelse return null;
return .{ .recommended = winner, .margin_pct = margin_pct };
}
/// The exact boundary arithmetic `driftCheck` gates on, pulled out as its
/// own pure function so the strict (not `>=`) exact-margin-percent
/// comparison is unit-testable with a manufactured exact value -- real
/// hash-derived costs essentially never land on exactly
/// `drift_margin_pct` by chance, so a test built only from real `cost()`
/// output could never exercise this boundary. Returns null when the
/// margin does not EXCEED `drift_margin_pct` (an exact-margin case is
/// refused, not accepted: §6.4's gate is the strict "C_candidate <
/// (1 - m) * C_current", so equality leaves the current pin in place),
/// else the margin percentage.
///
/// `winner_total` is always `<= pinned_total` at every call site (`best`
/// minimizes `.total` over the same non-flat scan `pinned` is drawn
/// from), so the division below can never go negative or by zero --
/// asserted, not merely assumed.
fn marginGate(pinned_total: f64, winner_total: f64) ?f64 {
std.debug.assert(pinned_total > 0.0);
std.debug.assert(winner_total <= pinned_total);
const margin_pct = (pinned_total - winner_total) / pinned_total * 100.0;
std.debug.assert(margin_pct >= 0.0);
if (margin_pct <= drift_margin_pct) return null;
return margin_pct;
}
/// Serialized byte length of one S card including its LF: `S <name> <hash>\n`
/// under §6.2's canonical (minimal) escaping.
fn sCardBytes(card: artifact.SCard) usize {
return 1 + 1 + canonicalLen(card.filename) + 1 + card.hash.len + 1;
}
/// Serialized byte length of one flat manifest F card including its LF, for
/// the §6.5 comparison baseline. Same shape the manifest writer emits.
fn flatFCardBytes(f: artifact.FCard) usize {
var n: usize = 1 + 1 + canonicalLen(f.filename); // "F" SP name
if (f.hash) |h| n += 1 + h.len;
if (f.perm) |p| n += 1 + p.len;
if (f.old_name) |o| n += 1 + canonicalLen(o);
return n + 1; // LF
}
/// §6.2's canonical encoding is minimal escaping — SP, LF and backslash
/// each become two bytes, every other octet is emitted raw — so the encoded
/// length is countable without materializing the encoding.
fn canonicalLen(name: []const u8) usize {
var n: usize = 0;
for (name) |c| n += if (c == ' ' or c == '\n' or c == '\\') @as(usize, 2) else 1;
return n;
}
/// Whether `hash` names one of the tree's LEAF sub-manifests. Linear over
/// `subs`; the analysis pass is an operator-invoked measurement, not a
/// commit-path cost, so the simple scan is the right trade.
fn namesLeaf(subs: []const artifact.SubArtifact, hash: []const u8) bool {
for (subs) |sub| {
if (std.mem.eql(u8, sub.name, hash)) return sub.bytes[0] == 'F';
}
return false;
}
/// Artifacts on the longest root-to-leaf path — what §5.1's depth bound
/// counts, the leaf included and the manifest excluded.
///
/// The construction is uniform in height, so every path has the same length
/// and descending the FIRST child of each level is the whole answer: start
/// at the manifest's own S run, and step down while the node it names is
/// interior. Bounded by `artifact.max_construct_height`, the height cap
/// §6.2 step 3 enforces.
fn treeDepth(subs: []const artifact.SubArtifact, s: []const artifact.SCard) usize {
std.debug.assert(s.len >= 2);
var name: []const u8 = s[0].hash;
var depth: usize = 0;
while (depth < artifact.max_construct_height) {
const sub = findSub(subs, name) orelse break;
depth += 1;
if (sub.bytes[0] != 'S') break; // a leaf ends the path
const first = firstSCardHash(sub.bytes) orelse break;
name = first;
}
std.debug.assert(depth >= 1 and depth <= artifact.max_construct_height);
return depth;
}
fn findSub(subs: []const artifact.SubArtifact, name: []const u8) ?artifact.SubArtifact {
for (subs) |sub| {
if (std.mem.eql(u8, sub.name, name)) return sub;
}
return null;
}
/// The hash token of the first S card in an interior sub-manifest's bytes.
/// An S card is `S <name> <hash>` and SP delimits tokens, so the hash is the
/// text after the LAST SP of the line (§5.6 makes exactly this argument for
/// the shell walk).
fn firstSCardHash(bytes: []const u8) ?[]const u8 {
const nl = std.mem.indexOfScalar(u8, bytes, '\n') orelse return null;
const line = bytes[0..nl];
if (line.len < 2 or line[0] != 'S' or line[1] != ' ') return null;
const sp = std.mem.lastIndexOfScalar(u8, line, ' ') orelse return null;
return line[sp + 1 ..];
}
};
/// The lazily-opened content channel: the reopened `.zit` handle, the
/// `FileStorage` binding over it (pinned — the `LogStore` borrows it), and the
/// scanned read-only log. Absent until the first `manifest`/`blob`/`logStore`.
const Content = struct {
file: std.Io.File,
fs: storage.FileStorage,
log: logstore.LogStore,
};
pub const Repository = struct {
io: std.Io,
/// The checkout root, discovered and owned by the caller (the caller closes
/// it after `deinit`). Borrowed here to reopen `.zit` for lazy content.
root_dir: std.Io.Dir,
/// The crosslinked derived view, loaded in place by `open`. `state` borrows
/// `&view.store`, so this whole struct is caller-pinned.
view: repoview.RepoView,
/// The content channel, opened lazily on the first content request. Held
/// inline (pinned) because the `LogStore` borrows `&content.?.fs`.
content: ?Content,
/// The `open` call's `bypass_cache`, retained so the LAZY surfaces opened
/// after `open` returns — the content channel and its persisted scan index
/// — honor the same "trust nothing derived" promise (`--no-cache` is one
/// flag with one meaning, not a per-sidecar toggle).
bypass_cache: bool,
/// submanifests §7.4 — "Implementations SHOULD cache per-sub-manifest
/// enumeration results keyed by artifact name: unchanged subtrees are shared
/// by hash across check-ins ... A naive implementation obtains the byte
/// reduction of this format but not the parse-count reduction that motivated
/// it."
///
/// Repository-lifetime, not per-call, because ACROSS CHECK-INS is where the
/// sharing is: §5.1's repeated-artifact check forbids one enumeration from
/// visiting the same sub-manifest twice, and §4.4 makes B and S exclusive so
/// a single `files` call flattens either a target or a baseline, never both.
/// The parse-count reduction therefore only exists for a caller that
/// enumerates several check-ins from one open repository — the merge path
/// (`cmd/checkout`, three `files` calls over a base, a current and an other)
/// being the standing case. Opened lazily: a repository with no tree
/// manifest never allocates it.
///
/// Safe because content addressing makes a POSITIVE answer immutable, and
/// the memo caches nothing else; see `repostate.SubManifestMemo`.
sub_memo: ?repostate.SubManifestMemo,
/// The derived-query identity space: a `RepoState` rid (the view's store).
pub const Rid = repostate.Rid;
/// Options for `open`. `bypass_cache` bypasses BOTH derived sidecars —
/// the O(1) `.zit-cache` fast path (and its extension) AND the
/// `.zit-cache/checkpoint` prefix resume — forcing the authoritative full
/// `openReadOnly` scan + derive (the `--no-cache` escape hatch: one flag,
/// one meaning — trust nothing derived); the derived view still rewrites
/// a fresh cache afterward.
pub const OpenOptions = struct {
bypass_cache: bool = false,
/// Which cache representation to serve. Defaults to `.full` (derive the
/// complete `RepoState` — every query answerable), so every existing
/// caller keeps today's behavior. The hot read verbs (`leaves` and the
/// mtime-ordered listings) pass `.fast_read` to take the zero-parse
/// image path, which answers their freed queries without re-deriving;
/// the cold verbs (`info` ancestry, `branch`, `tag`, `ls`, `cat`) stay
/// `.full` because they read adjacency and the full tag tables.
mode: repocache.LoadMode = .full,
};
/// Every failure the content-and-open surface can surface, as a single
/// closed set the CLI switches exhaustively. `NotARepo`: no `.zit` under the
/// given root. `CannotRead`: an I/O error opening/reading it. `Corrupt`: a
/// structurally invalid log or a stored artifact whose content does not
/// match its name (artifact §7.2). `OutOfMemory`: allocation failure.
pub const OpenError = error{ NotARepo, CannotRead, Corrupt, OutOfMemory };
/// Name resolution failure (repo-state §8.3), forwarded unchanged from
/// `RepoState.resolve` so the CLI keeps one exhaustive switch.
/// `OutOfMemory` rides along because settling an equal-`event.mtime` tie by
/// DAG ancestry allocates (repo-state `MtimeMaxPick`).
pub const ResolveError = error{ NotFound, Ambiguous, OutOfMemory };
/// Discoverless open: `root_dir` is the already-found checkout root. Opens
/// `.zit`, serves the view from the `.zit-cache` fast path or derives it
/// from the log, then closes the file (the view is self-contained). On
/// success the caller owns the value and must `deinit` it; on any error
/// nothing is retained and `deinit` must not be called.
pub fn open(
self: *Repository,
gpa: std.mem.Allocator,
io: std.Io,
root_dir: std.Io.Dir,
opts: OpenOptions,
) OpenError!void {
self.io = io;
self.root_dir = root_dir;
self.content = null;
self.bypass_cache = opts.bypass_cache;
self.sub_memo = null; // submanifests §7.4 — opened on the first tree walk
// Cleared per attempt, not per view: `Repository` is declared `undefined`
// by its callers, so a stale stack value here would name an artifact
// this open never looked at.
self.view.fault = null;
var file = root_dir.openFile(io, repo_filename, .{}) catch |e| return openFileError(e);
defer file.close(io);
const st = file.stat(io) catch return error.CannotRead;
if (st.kind != .file) return error.CannotRead;
var fs = storage.FileStorage.init(io, file, st.size);
// Fast path (repo-state §1 memo): a `.zit-cache` still valid against the
// live log's tail serves the whole view in O(1), no full scan. A miss
// is never an error — fall through to the authoritative derive.
if (!opts.bypass_cache and repocache.tryLoad(gpa, io, root_dir, fs.storageFile(), &self.view, opts.mode)) return;
var log = logstore.LogStore.openReadOnly(gpa, fs.storageFile()) catch |e| return openReadOnlyError(e);
defer log.deinit(gpa);
// Extension path: the cache missed on its exact tail, but if the log
// merely GREW past it -- commit, pull -- the stored record body is
// still a faithful distillate of the prefix, and only the tail needs
// deriving. Replay the body, fold the new frames, rewrite the cache.
// This is what keeps the full-store derive a once-per-repository cost
// instead of a once-per-write one: every append is healed by the next
// read at O(tail), not O(store).
//
// Refused whenever the fold could be wrong rather than merely stale:
// a shun-table change (the body may carry a record the mask must now
// hide) or a rewritten log (pack, shun --force -- the old tail no
// longer verifies at its offset). Both fall through to the
// authoritative full derive below.
if (!opts.bypass_cache) {
if (repocache.loadForExtension(gpa, io, root_dir)) |raw_const| {
var raw = raw_const;
defer raw.deinit(gpa);
if (raw.shun_fp == log.shunFingerprint() and
logstore.LogStore.validatePrefix(fs.storageFile(), raw.key) and
self.extendFromPrefix(gpa, io, root_dir, &log, &raw))
{
checkpoint.advance(gpa, io, self, root_dir);
return;
}
}
}
// Checkpoint path (hybrid-history DESIGN §4): no serviceable cache,
// but a validated `.zit-cache/checkpoint` lets the derive REPLAY the
// flat prefix's record body and walk only the frames past it. Guards,
// each a silent fall-through to the full derive: the container and
// prefix key validate (`checkpoint.tryLoad`), the shun table has not
// moved since capture, and the anchor check-in still resolves in the
// store under the §5.2 hard-failure discipline.
if (!opts.bypass_cache) {
if (checkpoint.tryLoad(gpa, io, root_dir, fs.storageFile())) |loaded_const| {
var loaded = loaded_const;
defer loaded.deinit(gpa);
if (loaded.claim.shun_fp == log.shunFingerprint() and
checkpointAnchorsResolve(gpa, &log, &loaded.claim) and
self.resumeFromCheckpoint(gpa, io, root_dir, &log, &loaded))
{
checkpoint.advance(gpa, io, self, root_dir);
return;
}
}
}
// Derive from the log, capturing the crosslink records, then materialize
// the zero-parse image from the fresh derived state and rewrite the
// cache atomically (best-effort — the derived view is correct either
// way; a failed image serialize just stores an empty image section, so
// the next `.fast_read` falls back to a derive rather than erroring).
var body: std.ArrayList(u8) = .empty;
defer body.deinit(gpa);
self.view.loadCapturing(gpa, &log, &body) catch |e| return loadError(e);
storeCache(gpa, io, root_dir, &log, &self.view, body.items);
// The healing paths keep an existing checkpoint fresh (sidecar-only,
// behind growth and anchor-progress gates — see `checkpoint.advance`),
// and the full derive PLANTS one where none exists — this is the one
// event that proves a checkpoint would have paid for itself, and the
// one place its payload is already in hand. The O(1) cache fast path
// above never pays either: a stale checkpoint implies a
// stale-or-missing cache, so staleness always surfaces here.
if (!opts.bypass_cache) {
checkpoint.autoCreate(gpa, io, self, root_dir, &log, body.items);
checkpoint.advance(gpa, io, self, root_dir);
}
}
/// §5.2 hard-failure discipline on the claim's anchor: C must be present,
/// non-phantom, verify as its own name, and parse as a check-in manifest.
/// Absent, unverifiable, unparseable and wrong-type all collapse to one
/// refusal, exactly the shape `update.TreeStore.resolve` holds tree
/// resolution to.
fn checkpointAnchorsResolve(gpa: std.mem.Allocator, log: *logstore.LogStore, claim: *const checkpoint.Claim) bool {
return anchorResolves(gpa, log, claim.checkin_hash, .manifest);
}
fn anchorResolves(gpa: std.mem.Allocator, log: *logstore.LogStore, hex: []const u8, want: artifact.ArtifactType) bool {
var digest: [logstore.max_hash_len]u8 = undefined;
if (hex.len == 0 or hex.len / 2 > digest.len) return false;
const raw = digest[0 .. hex.len / 2];
_ = std.fmt.hexToBytes(raw, hex) catch return false;
const rid = log.lookup(raw) orelse return false;
const bytes = (log.content(gpa, rid) catch return false) orelse return false; // phantom
defer gpa.free(bytes);
if (!artifact.verify(hex, bytes)) return false;
var im = artifact.parseForImport(gpa, bytes) catch return false;
defer im.deinit(gpa);
return im.manifest.kind == want;
}
/// The checkpointed derive: replay the prefix record body, walk only the
/// tail, rewrite the `.zit-cache` from the combined body — which
/// `RepoView.resumeFrom` guarantees is byte-identical to a full derive's,
/// so the checkpoint stays invisible to every downstream consumer.
/// Returns false on any failure with the view torn down, so `open` falls
/// through to the full derive: the checkpoint is an optimization and must
/// never be a new way to fail.
fn resumeFromCheckpoint(
self: *Repository,
gpa: std.mem.Allocator,
io: std.Io,
root_dir: std.Io.Dir,
log: *logstore.LogStore,
loaded: *const checkpoint.Loaded,
) bool {
var combined: std.ArrayList(u8) = .empty;
defer combined.deinit(gpa);
self.view.resumeFrom(gpa, log, loaded.body, loaded.claim.prefix_key.end, &combined) catch return false;
storeCache(gpa, io, root_dir, log, &self.view, combined.items);
return true;
}
/// The extension itself: replay the prefix body, fold the tail, store the
/// combined cache. Returns false on any failure with the view torn back
/// down, so `open` falls through to the full derive -- extension is an
/// optimization and must never be a new way to fail.
fn extendFromPrefix(
self: *Repository,
gpa: std.mem.Allocator,
io: std.Io,
root_dir: std.Io.Dir,
log: *logstore.LogStore,
raw: *const repocache.RawCache,
) bool {
// The CURRENT config's main branch, not the cached one: a config frame
// in the tail may have renamed it, and the fold itself never depends
// on the name -- it only labels queries.
var oc = log.readConfig(gpa) catch return false;
defer if (oc) |*c| c.deinit(gpa);
const main_branch = if (oc) |c|
(if (c.config.default_branch.len != 0) c.config.default_branch else raw.main_branch)
else
raw.main_branch;
self.view.buildFromRecordBody(gpa, raw.body, main_branch) catch return false;
var tail: std.ArrayList(u8) = .empty;
defer tail.deinit(gpa);
self.view.extendCapturing(gpa, log, raw.key.end, &tail) catch {
self.view.deinit(gpa);
return false;
};
const combined = std.mem.concat(gpa, u8, &.{ raw.body, tail.items }) catch {
// The view is complete and correct; only the cache rewrite is
// lost. Serve the view and let the next reader try again.
return true;
};
defer gpa.free(combined);
storeCache(gpa, io, root_dir, log, &self.view, combined);
return true;
}
/// Frees the derived view and closes the lazy content channel if it was
/// opened. Does NOT close `root_dir` — the caller that discovered it owns
/// its lifetime. Call only on a `Repository` that `open` returned `ok`.
pub fn deinit(self: *Repository, gpa: std.mem.Allocator) void {
if (self.content) |*c| {
c.log.deinit(gpa);
c.file.close(self.io);
}
if (self.sub_memo) |*m| m.deinit();
self.view.deinit(gpa);
self.* = undefined;
}
/// Eagerly materialize the `.zit-cache` for the repository at `root_dir` so
/// the first read verb after a fresh clone takes the zero-parse image fast
/// path instead of paying the full cold derive. It runs `open`'s own
/// read-miss path purely for its cache-writing side effect, then discards the
/// view. The cache is disposable, so all failures are deliberately ignored.
pub fn warmCache(gpa: std.mem.Allocator, io: std.Io, root_dir: std.Io.Dir) void {
var repo: Repository = undefined;
repo.open(gpa, io, root_dir, .{}) catch return;
repo.deinit(gpa);
}
/// Best-effort cache warming from a caller-owned, already-open log. This is
/// for write paths that have committed their log and must not reopen it just
/// to derive the cache. It uses the same capture, image, and cache writer as
/// `open`; cache-write or derivation failures leave the repository unchanged.
pub fn warmCacheFromLog(
gpa: std.mem.Allocator,
io: std.Io,
root_dir: std.Io.Dir,
log: *logstore.LogStore,
) void {
var view: repoview.RepoView = undefined;
var body: std.ArrayList(u8) = .empty;
defer body.deinit(gpa);
view.loadCapturing(gpa, log, &body) catch return;
defer view.deinit(gpa);
storeCache(gpa, io, root_dir, log, &view, body.items);
// The derive body is in hand — the same free-plant moment `open`'s
// full-derive path exploits — so a clone (or any warmed write path)
// ends fully warm: cache, checkpoint, and the content-scan index the
// fingerprint pays for, which a first read would have paid anyway.
// The facade reopen takes the just-written cache's fast path.
var repo: Repository = undefined;
repo.open(gpa, io, root_dir, .{}) catch return;
defer repo.deinit(gpa);
checkpoint.autoCreate(gpa, io, &repo, root_dir, log, body.items);
}
fn storeCache(
gpa: std.mem.Allocator,
io: std.Io,
root_dir: std.Io.Dir,
log: *const logstore.LogStore,
view: *const repoview.RepoView,
records: []const u8,
) void {
if (log.logKey()) |key| {
var image: std.ArrayList(u8) = .empty;
defer image.deinit(gpa);
repoimage.serialize(gpa, &view.state, view.main_branch, &image) catch image.clearRetainingCapacity();
repocache.store(gpa, io, root_dir, key, log.shunFingerprint(), view.main_branch, records, image.items);
} else |_| {}
}
/// The derived `RepoState` — the leaf table, branch/tag derivations, event
/// times, and ancestry (repo-state §6-9). The view already hides the derive;
/// exposing the query surface directly keeps this facade from becoming a
/// shallow pass-through over a dozen `RepoState` methods.
pub fn state(self: *const Repository) *const repostate.RepoState {
return &self.view.state;
}
/// The repo-state §6.1 default-branch name (config `main-branch` when set,
/// else `"trunk"`) — the fallback `branchOf` threads.
pub fn mainBranch(self: *const Repository) []const u8 {
return self.view.main_branch;
}
/// The lowercase-hex artifact name of a derived rid — what a verb prints and
/// compares against the current checkout.
pub fn hashOf(self: *Repository, rid: Rid) []const u8 {
return self.view.hashOf(rid);
}
/// The derived rid for a lowercase-hex artifact name, or null when the name
/// was never interned in this view.
pub fn lookup(self: *Repository, hash: []const u8) ?Rid {
return self.view.lookup(hash);
}
/// Resolve a symbolic name / id / prefix to a rid via the repo-state §8.3
/// procedure (recency-based, §8.2 — closed-ness and leaf-ness never filter
/// the candidate). Errors forwarded unchanged so the CLI switches once.
pub fn resolve(self: *const Repository, name: []const u8, want: repostate.RepoState.NameType) ResolveError!Rid {
return self.view.state.resolve(name, want);
}
/// The active-tag branch of `rid` (repo-state §6.1), config `main-branch` as
/// the fallback. Folds the fallback so callers never pass it — precondition:
/// `rid` bears an event (`state.mtimeOf(rid) != null`).
pub fn branchOf(self: *const Repository, rid: Rid) []const u8 {
return self.view.state.branchOf(rid, self.view.main_branch);
}
/// The active display-override value of tag `name` on `rid` (repo-state
/// §5.2), or `fallback` when no override is live. A `zit amend` control
/// artifact's singleton override lands in `tagxref` on the target rid at the
/// next read (repo-state §4/§5), so the render sites read it here without any
/// override-precedence logic of their own. General over the tag name — one
/// accessor serves the comment/user/date overrides.
pub fn override(self: *const Repository, rid: Rid, name: []const u8, fallback: []const u8) []const u8 {
return self.view.state.activeTagValue(rid, name) orelse fallback;
}
/// Merge base of `a` and `b` over full ancestry: the common ancestor with the
/// greatest event mtime, ties broken by the least artifact hash, or null when
/// they share no ancestor (repo-state `mergeBaseOf`; ambiguities.md
/// `merge-base`). A thin pass-through over the one general-purpose query.
pub fn mergeBaseOf(self: *const Repository, gpa: std.mem.Allocator, a: Rid, b: Rid) error{OutOfMemory}!?Rid {
return self.view.state.mergeBaseOf(gpa, a, b);
}
/// Full-ancestry membership: whether `ancestor` is in the full ancestry of
/// `descendant` (§3.3, merge parents included, self-inclusive). mtime-
/// independent, unlike `mergeBaseOf` — the authoritative up-to-date test the
/// `merge` verb keys the B-merge-16 refusal on. A thin pass-through.
pub fn isAncestorOf(self: *const Repository, gpa: std.mem.Allocator, ancestor: Rid, descendant: Rid) error{OutOfMemory}!bool {
return self.view.state.isAncestorOf(gpa, ancestor, descendant);
}
/// The full ancestry of `rid` as a slice (§3.3, merge parents included,
/// self-inclusive), the general-purpose query `annotate` builds its version
/// chain over. A thin pass-through over the one shared ancestry walk — the
/// verb owns no ancestry traversal of its own. Caller frees the slice.
pub fn ancestorsOf(self: *const Repository, gpa: std.mem.Allocator, rid: Rid) error{OutOfMemory}![]Rid {
return self.view.state.ancestorsOf(gpa, rid);
}
/// The full ancestry of `rid` (§3.3, merge parents included, self-inclusive)
/// linearized into the annotate engine's processing order — a topological
/// order in which every parent precedes its child (oldest first), so
/// same-mtime and non-monotone parent/child pairs never invert. A thin
/// pass-through over the one shared linearization; the verb owns no ancestry
/// ordering of its own. Caller frees the slice.
pub fn ancestryLinearized(self: *const Repository, gpa: std.mem.Allocator, rid: Rid) error{OutOfMemory}![]Rid {
return self.view.state.ancestryLinearized(gpa, rid);
}
/// The bisect candidate span and next probe over full ancestry (repo-state
/// `bisectSpan`; ambiguities.md `bisect-midpoint`): candidate set =
/// ancestors(bad-anchor) minus every good's ancestry minus skipped; probe =
/// lower median of untested candidates by ascending mtime, ties least hash;
/// culprit = mtime-earliest marked-bad. Refuses `InvertedMarks` /
/// `UnrelatedHistories`. A thin pass-through over the one general-purpose
/// query — the bisect verb owns no ancestry walk of its own.
pub fn bisectSpan(
self: *const Repository,
gpa: std.mem.Allocator,
bad: []const Rid,
good: []const Rid,
skipped: []const Rid,
) repostate.RepoState.BisectError!repostate.RepoState.BisectOutcome {
return self.view.state.bisectSpan(gpa, bad, good, skipped);
}
/// The current checkout's crosslinked rid, or null when there is nothing to
/// mark: no `.zit-checkout`, an unborn checkout, a version this view never
/// interned, or an interned-but-eventless phantom (repo-state §7.5). The
/// `mtimeOf != null` guard is the postcondition `branchOf`'s callers lean on
/// — a returned rid always bears an event.
pub fn currentCheckoutRid(self: *Repository) ?Rid {
var ck_buf: [checkout.max_ck_payload + 1]u8 = undefined;
const ck = (checkout.read(self.io, self.root_dir, &ck_buf) catch return null) orelse return null;
if (ck.version.len == 0) return null;
const rid = self.view.lookup(ck.version) orelse return null;
if (self.view.state.mtimeOf(rid) == null) return null;
return rid;
}
/// The lazily-opened read-only log for content reads. Reopens `.zit` (closed
/// after the view derive) on first use and memoizes it for the repository's
/// lifetime; subsequent calls return the same store.
pub fn logStore(self: *Repository, gpa: std.mem.Allocator) OpenError!*logstore.LogStore {
if (self.content) |*c| return &c.log;
var file = self.root_dir.openFile(self.io, repo_filename, .{}) catch |e| return openFileError(e);
errdefer file.close(self.io);
const st = file.stat(self.io) catch return error.CannotRead;
if (st.kind != .file) return error.CannotRead;
self.content = .{
.file = file,
.fs = storage.FileStorage.init(self.io, file, st.size),
.log = undefined,
};
const sf = self.content.?.fs.storageFile();
// Indexed fast path: adopt the persisted scan index instead of
// re-walking every frame header (O(index) vs O(store)). Any refusal —
// absent, stale, corrupt — falls through to the authoritative scan;
// `--no-cache` never consults it at all. A grown log resumes the walk
// over the tail alone, and the sidecar is refreshed so the next open
// is O(index) again.
if (!self.bypass_cache) blk: {
const idx = repocache.tryLoadLogIndex(gpa, self.io, self.root_dir) orelse break :blk;
defer gpa.free(idx);
var extended = false;
const adopted = (logstore.LogStore.openReadOnlyIndexed(gpa, sf, idx, &extended) catch break :blk) orelse break :blk;
self.content.?.log = adopted;
if (extended) refreshLogIndex(gpa, self.io, self.root_dir, &self.content.?.log);
return &self.content.?.log;
}
self.content.?.log = logstore.LogStore.openReadOnly(gpa, sf) catch |e| {
self.content = null; // discard the half-built channel; errdefer closes `file`
return openReadOnlyError(e);
};
// Write-on-miss: the scan just paid for the product the index persists.
if (!self.bypass_cache) refreshLogIndex(gpa, self.io, self.root_dir, &self.content.?.log);
return &self.content.?.log;
}
/// Serialize and atomically store the content log's scan index.
/// Best-effort end to end: a failure costs the next open one scan.
fn refreshLogIndex(gpa: std.mem.Allocator, io: std.Io, root_dir: std.Io.Dir, log: *const logstore.LogStore) void {
const idx = log.serializeIndex(gpa) catch return;
defer gpa.free(idx);
repocache.storeLogIndex(io, root_dir, idx);
}
/// The uncompressed content of the artifact named `name` (a lowercase-hex
/// id), or null when no artifact of that name is stored. The bytes are
/// verified to hash to `name` (artifact §7.2, hash-over-uncompressed) — a
/// content/name mismatch or an undecodable frame is `Corrupt`. Caller frees
/// the returned slice.
pub fn blob(self: *Repository, gpa: std.mem.Allocator, name: []const u8) OpenError!?[]u8 {
var digest_buf: [logstore.max_hash_len]u8 = undefined;
const digest = decodeName(name, &digest_buf) orelse return null; // undecodable ⇒ never stored
const log = try self.logStore(gpa);
const rid = log.lookup(digest) orelse return null;
const bytes = (log.content(gpa, rid) catch |e| return contentError(e)) orelse return null;
errdefer gpa.free(bytes);
if (!hashMatches(digest, bytes)) return error.Corrupt; // §7.2
return bytes;
}
/// Resolving an artifact-name prefix: the open set plus `Ambiguous` (a
/// prefix matching more than one stored artifact — repo-state §8.3 item 8,
/// never silently narrowed). A prefix matching nothing is `null`, not an
/// error — the not-found family the CLI renders as a plain refusal.
pub const ResolveArtifactError = OpenError || error{Ambiguous};
/// Resolve a lowercase-hex artifact-name prefix (full or abbreviated) to
/// the unique full lowercase-hex name of the stored artifact it addresses,
/// written into `out` and returned as a sub-slice. Queries the LogStore —
/// the one store holding EVERY stored artifact, file blobs included (the
/// derived `repostate` interns only check-in/parent phantoms, which carry
/// no content), so a blob prefix resolves here where a check-in-scoped name
/// lookup would miss it. `null` = no match (not-found); `error.Ambiguous` =
/// the §8.3-item-8 multi-match refusal. Hides the LogStore rid space from
/// the caller, who sees only hashes. Precondition on `prefix` is the
/// LogStore's: 4..64 lowercase-hex bytes (the CLI canonicalizes first).
pub fn resolveArtifactPrefix(
self: *Repository,
gpa: std.mem.Allocator,
prefix: []const u8,
out: *[2 * logstore.max_hash_len]u8,
) ResolveArtifactError!?[]const u8 {
const log = try self.logStore(gpa);
const maybe_rid = log.resolveHexPrefix(prefix) catch |e| switch (e) {
error.Ambiguous => return error.Ambiguous,
};
const rid = maybe_rid orelse return null;
const raw = log.hashOf(rid);
std.debug.assert(raw.len <= logstore.max_hash_len);
const lower = "0123456789abcdef";
for (raw, 0..) |b, i| {
out[i * 2] = lower[b >> 4];
out[i * 2 + 1] = lower[b & 0x0f];
}
return out[0 .. raw.len * 2];
}
/// A parsed manifest bundled with the uncompressed bytes its cards borrow —
/// the parser slices its source rather than duping it, so that source must
/// outlive the manifest. `bytes` is the reconstructed artifact (always
/// owned); `normalized` is non-null only when the read-path legacy
/// trailing-separator tolerance fired, in which case the manifest's cards
/// borrow `normalized` instead of `bytes` (§4.2 read-interop). `deinit`
/// frees all held allocations.
pub const OwnedManifest = struct {
bytes: []u8,
normalized: ?[]u8 = null,
manifest: artifact.Manifest,
pub fn deinit(self: *OwnedManifest, gpa: std.mem.Allocator) void {
self.manifest.deinit();
if (self.normalized) |n| gpa.free(n);
gpa.free(self.bytes);
self.* = undefined;
}
};
/// The parsed manifest of the check-in `rid`, or null when its content is
/// missing. `Corrupt` when the stored bytes are not a parseable artifact.
/// Parses through `parseForImport`, not the strict reference `parse`, so a
/// fossil-origin check-in carrying the legacy dangling F-card separator
/// (fossil's own 2008 cvs2fossil history) reads instead of being rejected —
/// the same read-path interop the diff baseline already relies on. Caller
/// `deinit`s the returned `OwnedManifest`.
pub fn manifest(self: *Repository, gpa: std.mem.Allocator, rid: Rid) OpenError!?OwnedManifest {
const bytes = (try self.blob(gpa, self.view.hashOf(rid))) orelse return null;
errdefer gpa.free(bytes);
const im = artifact.parseForImport(gpa, bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.Corrupt,
};
return .{ .bytes = bytes, .normalized = im.normalized, .manifest = im.manifest };
}
/// Every failure `files` can surface: the open/content set plus the three
/// §8 enumeration faults. `NotManifest`: the resolved artifact is not a
/// check-in manifest (artifact §5.1). `BaselineUnresolvable` (§8.3): a delta
/// check-in whose B-card baseline cannot be located, is not a manifest, or
/// is unparseable — the hard-failure discipline §8.3 mandates for the
/// file-enumeration entry points. `BaselineIsDelta` (§4.7.3): the resolved
/// baseline is itself a delta manifest (delta-of-delta, rejected).
pub const FilesError = OpenError || error{ NotManifest, BaselineUnresolvable, BaselineIsDelta };
/// The effective file set of one check-in, retaining every manifest whose
/// F cards the walk borrows. A baseline check-in keeps only its own manifest
/// (`baseline` null); a delta check-in additionally keeps the eagerly-read
/// baseline, since the §8.2 merge walk borrows both card lists. Build it with
/// `files`, read it with `iterator`, free it with `deinit`.
pub const FileList = struct {
target: OwnedManifest,
baseline: ?OwnedManifest = null,
/// The two pre-sorted (§8.1) F-card lists the §8.2 merge walk consumes:
/// `base_files` is the baseline's set (the target's own set for a
/// baseline check-in), `delta_files` the delta's authored cards (empty
/// for a baseline check-in). Both borrow the retained manifests above,
/// so they stay valid exactly as long as this `FileList`.
base_files: []const artifact.FCard,
delta_files: []const artifact.FCard,
pub fn deinit(self: *FileList, gpa: std.mem.Allocator) void {
if (self.baseline) |*b| b.deinit(gpa);
self.target.deinit(gpa);
self.* = undefined;
}
/// A fresh §8.2 merge walk over the retained card lists — allocation-free
/// and repeatable, so a caller may enumerate more than once.
pub fn iterator(self: *const FileList) EffectiveFiles {
return .{ .walk = .{ .baseline = self.base_files, .delta = self.delta_files } };
}
};
/// A §8.2 merge walk narrowed to the effective set: `next` yields each merged
/// F card in canonical filename order (§4.5.3), suppressing the delete markers
/// the raw walk emits verbatim (§8.2 step 3 / tail, §4.7.6) so every yielded
/// card carries a hash.
pub const EffectiveFiles = struct {
walk: artifact.MergeWalk,
pub fn next(self: *EffectiveFiles) ?artifact.FCard {
while (self.walk.next()) |f| {
if (f.hash != null) return f; // §4.7.6: a hash-less card is a delete marker
}
return null;
}
};
/// The effective file set of the check-in `rid` (artifact §8.2): its own F
/// cards for a baseline manifest, or the §8.2 merge of the eagerly-resolved
/// baseline with the delta's cards for a delta manifest. Returns null when the
/// check-in's own content is missing (an interned phantom). The §8.3/§4.7.3
/// baseline policy stays in `artifact.enumerate`: this pre-reads only the one
/// baseline the B card names and hands `enumerate` a resolver over it. Caller
/// `deinit`s the returned `FileList`.
pub fn files(self: *Repository, gpa: std.mem.Allocator, rid: Rid) FilesError!?FileList {
var target = (try self.manifest(gpa, rid)) orelse return null;
errdefer target.deinit(gpa);
if (target.manifest.kind != .manifest) return error.NotManifest; // §5.1
// submanifests §5.1: a tree check-in's file set lives behind its S
// cards, so walk it into a flat card list before §8 ever looks. §4.4
// makes this exclusive with the B-card branch below — a manifest never
// carries both B and S — so a check-in is walked or resolved, never both.
try flattenIfTree(self, gpa, &target.manifest);
// Eagerly resolve the one baseline the B card names (a delta manifest
// only). A located, parseable check-in manifest becomes the resolver's
// view; anything else leaves it null, so `enumerate` raises
// BaselineUnresolvable under the §8.3 hard-failure discipline.
var baseline: ?OwnedManifest = null;
errdefer if (baseline) |*b| b.deinit(gpa);
var view: ?artifact.ManifestFiles = null;
if (target.manifest.b) |b| {
if (try self.blob(gpa, b.hash)) |bytes| {
if (parseBaseline(gpa, bytes)) |bm| {
baseline = bm;
// submanifests §5.4: "a delta manifest MAY name a tree
// manifest in its B card ... the baseline cursor of the
// merge-walk ... is the enumeration of Section 5.1."
// Flattening here makes that composition free.
try flattenIfTree(self, gpa, &baseline.?.manifest);
view = manifestFilesOf(&baseline.?.manifest);
} else |e| switch (e) {
error.OutOfMemory => {
gpa.free(bytes);
return error.OutOfMemory;
},
error.NotManifest => gpa.free(bytes), // §8.3: not a manifest ⇒ unresolvable
}
}
}
var eager = EagerBaseline{
.hash = if (target.manifest.b) |b| b.hash else null,
.view = view,
};
const walk = artifact.enumerate(manifestFilesOf(&target.manifest), .{
.ctx = &eager,
.resolveFn = EagerBaseline.resolve,
}) catch |e| switch (e) {
error.BaselineUnresolvable => return error.BaselineUnresolvable, // §8.3
error.BaselineIsDelta => return error.BaselineIsDelta, // §4.7.3
};
// Postcondition: a delta check-in retained its baseline (else `enumerate`
// would have raised BaselineUnresolvable above); a baseline check-in did
// not read one.
std.debug.assert((target.manifest.b != null) == (baseline != null));
return FileList{
.target = target,
.baseline = baseline,
.base_files = walk.baseline,
.delta_files = walk.delta,
};
}
/// Every failure `verifyChecksum` can surface: `files`' set plus the two
/// gaps that only matter once the R aggregate is actually recomputed.
/// `NoChecksum`: the check-in carries no R card, so there is nothing to
/// verify against. `FileContentMissing`: a tracked file's blob is absent,
/// so the §6.3.2 input cannot be formed at all.
pub const VerifyChecksumError = FilesError || error{ NoChecksum, FileContentMissing };
/// Recompute the R-card aggregate over the check-in's effective file set and
/// report whether it matches the R card the manifest carries (artifact
/// §6.3.2; submanifests §5.5). Null when the check-in's own content is
/// missing, exactly as `files` reports it.
///
/// The enumeration comes from `files`, so one path covers a flat manifest, a
/// tree manifest (§5.5: "the R card MUST be computed over the walk
/// enumeration of Section 5.1"), and a delta over either (§6.3.3) — §9.3's
/// "one shared enumeration interface", not a second file-set walk that could
/// drift from it. Contents stream through the aggregator one blob at a time,
/// so verifying a large check-in never holds the whole tree in memory.
pub fn verifyChecksum(self: *Repository, gpa: std.mem.Allocator, rid: Rid) VerifyChecksumError!?bool {
var list = (try self.files(gpa, rid)) orelse return null;
defer list.deinit(gpa);
const r = list.target.manifest.r orelse return error.NoChecksum;
var agg: artifact.ChecksumAggregator = .{};
var it = list.iterator();
while (it.next()) |f| {
// `EffectiveFiles` already suppressed the §4.7.6 delete markers, so
// every yielded card names stored content.
const content = (try self.blob(gpa, f.hash.?)) orelse return error.FileContentMissing;
defer gpa.free(content);
agg.update(f.filename, content);
}
var out: [32]u8 = undefined;
return std.mem.eql(u8, r.checksum, agg.final(&out));
}
/// The effective F card for `name` in the check-in `rid` (artifact §8.4
/// single-name lookup), or null when `name` is not in the effective set —
/// either never present, or a delta delete marker (§4.7.6) suppresses it.
/// Exact-name only: §8.4's best-match (closest-name) form is deliberately
/// not offered, so it is never a candidate to suppress here.
///
/// §8.4's discipline — search the delta's own cards first, a delta delete
/// marker reports not-found without consulting the baseline, and the
/// baseline is searched only when the name is absent from the delta — is
/// exactly the §8.2 merge the `files` walk already performs. This narrows
/// that walk to one name rather than re-deriving the rules, so the §8.3/
/// §4.7.3 baseline faults surface unchanged. The returned card's slices are
/// duplicated into `gpa` (independent of the walk's scratch, which is freed
/// before returning); release it with `freeFileCard`.
pub fn fileAt(self: *Repository, gpa: std.mem.Allocator, rid: Rid, name: []const u8) FilesError!?artifact.FCard {
var list = (try self.files(gpa, rid)) orelse return null;
defer list.deinit(gpa);
var it = list.iterator();
while (it.next()) |f| {
std.debug.assert(f.hash != null); // §4.7.6: the walk suppresses delete markers
if (std.mem.eql(u8, f.filename, name)) return try dupFileCard(gpa, f);
}
return null;
}
/// Release a card returned by `fileAt` — its present slices were each
/// duplicated into `gpa`. A no-op-safe companion: every field that was
/// null in the source stays null and is skipped.
pub fn freeFileCard(gpa: std.mem.Allocator, f: artifact.FCard) void {
gpa.free(f.filename);
if (f.hash) |h| gpa.free(h);
if (f.perm) |p| gpa.free(p);
if (f.old_name) |o| gpa.free(o);
}
/// draft-fossil-submanifests-00 §§5.1 and 5.2: enumerate a tree manifest's
/// complete F-set through an already-open source, before any caller writes.
pub fn flattenTreeFromLog(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
tree_manifest: *artifact.Manifest,
) TreeFlattenError!void {
return flattenTreeFromLogImpl(gpa, log, tree_manifest);
}
/// `flattenTreeFromLog` with a caller-owned memo. See the file-scope
/// function for why a run of check-ins needs one.
pub fn flattenTreeFromLogMemo(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
tree_manifest: *artifact.Manifest,
slot: *?repostate.SubManifestMemo,
) TreeFlattenError!void {
return flattenTreeFromLogMemoImpl(gpa, log, tree_manifest, slot);
}
};
/// Duplicate every present slice of `f` into `gpa`, yielding a card whose bytes
/// outlive the merge walk's scratch. Partial-failure-safe: an OOM after any dup
/// frees the slices already taken (`errdefer`), so no leak escapes. `mode` is a
/// value, copied for free. Freed by `Repository.freeFileCard`.
fn dupFileCard(gpa: std.mem.Allocator, f: artifact.FCard) error{OutOfMemory}!artifact.FCard {
const filename = try gpa.dupe(u8, f.filename);
errdefer gpa.free(filename);
const hash = if (f.hash) |h| try gpa.dupe(u8, h) else null;
errdefer if (hash) |h| gpa.free(h);
const perm = if (f.perm) |p| try gpa.dupe(u8, p) else null;
errdefer if (perm) |p| gpa.free(p);
const old_name = if (f.old_name) |o| try gpa.dupe(u8, o) else null;
return .{ .filename = filename, .hash = hash, .perm = perm, .old_name = old_name, .mode = f.mode };
}
/// The §8.2 `ManifestFiles` view of a parsed manifest: its B-card hash (null for
/// a baseline manifest, §8-p1) and its file set — its own F-card list (sorted at
/// parse time), or, for a tree manifest, the walked enumeration `flattenIfTree`
/// derived (submanifests §5.1). §5.1: downstream consumers "MUST NOT distinguish
/// a walked enumeration from a flat or delta one", which is exactly what this
/// substitution buys — the §8 machinery below never learns trees exist.
///
/// `pub` so `update.zig` builds its §8.2 view through this one seam assertion
/// rather than a second copy of it — the same reason its §5.2 walk routes
/// through `flattenTreeFromLog`.
pub fn manifestFilesOf(m: *const artifact.Manifest) artifact.ManifestFiles {
// submanifests §9.3 seam assertion: a tree manifest conveys its file set
// entirely by S cards, so its `f` run is empty and a view built before the
// walk would silently enumerate nothing — precisely the bypass §9.3 requires
// implementations to route rather than tolerate.
std.debug.assert(m.s.len == 0 or m.flattened != null);
return .{
.baseline_hash = if (m.b) |b| b.hash else null,
.files = m.flattened orelse m.f,
};
}
/// draft-fossil-submanifests-00 §§5.1–5.2: tree-walk resolution distinguishes
/// an absent or wrong-type S target from unreadable/corrupt storage before a
/// caller writes.
pub const TreeFlattenError = artifact.TreeError || error{
OutOfMemory,
CannotRead,
Corrupt,
};
const TreeSource = union(enum) {
repository: *Repository,
log: *logstore.LogStore,
fn blob(self: TreeSource, gpa: std.mem.Allocator, name: []const u8) TreeFlattenError!?[]u8 {
return switch (self) {
.repository => |repo| repo.blob(gpa, name) catch |err| switch (err) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => error.Corrupt,
error.CannotRead, error.NotARepo => error.CannotRead,
},
.log => |log| treeLogBlob(gpa, log, name),
};
}
};
fn treeLogBlob(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
name: []const u8,
) TreeFlattenError!?[]u8 {
var digest_buf: [logstore.max_hash_len]u8 = undefined;
const digest = decodeName(name, &digest_buf) orelse return null;
const rid = log.lookup(digest) orelse return null;
const bytes = (log.content(gpa, rid) catch |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => return error.Corrupt,
error.Storage => return error.CannotRead,
}) orelse return null;
errdefer gpa.free(bytes);
if (!hashMatches(digest, bytes)) return error.Corrupt;
return bytes;
}
/// Shared resolver owner for both a Repository's lazy content channel and an
/// already-open LogStore. It owns bytes and parsed cards until a completed walk
/// copies them into the target manifest's arena.
const TreeResolver = struct {
source: TreeSource,
gpa: std.mem.Allocator,
scratch: std.ArrayList(Repository.OwnedManifest) = .empty,
fault: ?TreeFlattenError = null,
fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.SubManifestView {
const self: *TreeResolver = @ptrCast(@alignCast(ctx));
if (self.fault != null) return null;
const bytes = (self.source.blob(self.gpa, hash) catch |err| {
self.fault = err;
return null;
}) orelse return null;
var im = artifact.parseForImport(self.gpa, bytes) catch |err| {
self.gpa.free(bytes);
if (err == error.OutOfMemory) self.fault = error.OutOfMemory;
return null;
};
if (im.manifest.kind != .submanifest) {
im.deinit(self.gpa);
self.gpa.free(bytes);
return null;
}
var owned = Repository.OwnedManifest{
.bytes = bytes,
.normalized = im.normalized,
.manifest = im.manifest,
};
self.scratch.append(self.gpa, owned) catch {
owned.deinit(self.gpa);
self.fault = error.OutOfMemory;
return null;
};
const stored = &self.scratch.items[self.scratch.items.len - 1];
return .{ .files = stored.manifest.f, .subs = stored.manifest.s };
}
fn resolver(self: *TreeResolver) artifact.SubResolver {
return .{ .ctx = self, .resolveFn = resolve };
}
fn deinit(self: *TreeResolver) void {
for (self.scratch.items) |*manifest| manifest.deinit(self.gpa);
self.scratch.deinit(self.gpa);
self.* = undefined;
}
};
/// Flatten an S-bearing manifest through an already-open LogStore. Commit uses
/// this before capture so a resolver fault cannot leave any newly captured blob
/// or manifest frame behind.
/// `flattenTreeFromLog` with a memo the CALLER owns, so it survives between
/// calls. A sub-manifest tree shares nearly all of its nodes with its parent's
/// -- that is the premise of the format -- so a caller flattening many
/// check-ins in a row re-resolves the same nodes once per check-in, and a node
/// near the root is re-fetched, re-inflated and re-parsed by every descendant.
/// `Repository` avoids that with its own lifetime memo (`flattenIfTree`); a
/// log-only caller had no way to, because the resolver here is scratch that
/// dies with the call.
///
/// Pass the same `slot` across a run of check-ins and the walk keeps §7.4's
/// distinct-artifact cost instead of paying the naive one. The memo answers
/// from deep copies in its own arena and rebinds `inner` to each call's fresh
/// scratch resolver, which is what makes reuse across walks sound; it is
/// keyed by artifact name, so a hit is the same artifact by content address,
/// never a positional guess.
fn flattenTreeFromLogMemoImpl(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
manifest: *artifact.Manifest,
slot: *?repostate.SubManifestMemo,
) TreeFlattenError!void {
if (manifest.s.len == 0) return;
var owner = TreeResolver{ .source = .{ .log = log }, .gpa = gpa };
defer owner.deinit();
const seam = owner.resolver();
if (slot.* == null) slot.* = repostate.SubManifestMemo.init(gpa, seam);
const memo = &slot.*.?;
// Rebind AND trim in one call: `owner` above is this walk's scratch
// resolver, and the previous walk's has already been destroyed, so nothing
// the memo handed out is still live. That is the only moment eviction is
// safe (see `beginWalk`), which is why the seam is not assigned directly.
memo.beginWalk(seam);
manifest.flattenTree(memo.resolver()) catch |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
else => {
if (owner.fault) |fault| return fault;
return err;
},
};
std.debug.assert(owner.fault == null);
std.debug.assert(manifest.flattened != null);
}
fn flattenTreeFromLogImpl(
gpa: std.mem.Allocator,
log: *logstore.LogStore,
manifest: *artifact.Manifest,
) TreeFlattenError!void {
if (manifest.s.len == 0) return;
var owner = TreeResolver{ .source = .{ .log = log }, .gpa = gpa };
defer owner.deinit();
manifest.flattenTree(owner.resolver()) catch |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
else => {
if (owner.fault) |fault| return fault;
return err;
},
};
std.debug.assert(owner.fault == null);
std.debug.assert(manifest.flattened != null);
}
/// submanifests §5.1/§5.4: derive `m`'s complete file set when it is a tree
/// manifest, leaving a flat or delta manifest untouched. The Repository keeps
/// its lifetime memo while sharing the same parser/retention owner as LogStore.
fn flattenIfTree(
repo: *Repository,
gpa: std.mem.Allocator,
manifest: *artifact.Manifest,
) Repository.FilesError!void {
if (manifest.s.len == 0) return;
var owner = TreeResolver{ .source = .{ .repository = repo }, .gpa = gpa };
defer owner.deinit();
const seam = owner.resolver();
if (repo.sub_memo == null) repo.sub_memo = repostate.SubManifestMemo.init(gpa, seam);
const memo = &repo.sub_memo.?;
memo.beginWalk(seam); // rebind + trim; see `beginWalk` on why they are one call
manifest.flattenTree(memo.resolver()) catch |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
else => {
if (owner.fault) |fault| return switch (fault) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => error.Corrupt,
error.CannotRead => error.CannotRead,
else => unreachable,
};
return error.BaselineUnresolvable;
},
};
std.debug.assert(owner.fault == null);
std.debug.assert(manifest.flattened != null);
}
/// Parse `bytes` (borrowed) as the eagerly-read baseline of a delta check-in
/// (§8.3). Parses through `parseForImport`, not the strict reference `parse`, so
/// a fossil-origin baseline carrying the legacy dangling F-card separator
/// (fossil's own 2008 cvs2fossil history) is read instead of being rejected —
/// the same read-path interop the target manifest already relies on. A
/// successful parse of a check-in manifest becomes an `OwnedManifest` that takes
/// ownership of `bytes` (and the tolerance's `normalized` copy, if any); a parse
/// OOM propagates; any other outcome — a syntactically invalid artifact or one
/// that is not a manifest — is `NotManifest`, the §8.3 "located artifact is not a
/// manifest" case (the caller frees `bytes` and lets `enumerate` raise
/// `BaselineUnresolvable`).
fn parseBaseline(gpa: std.mem.Allocator, bytes: []u8) error{ OutOfMemory, NotManifest }!Repository.OwnedManifest {
var im = artifact.parseForImport(gpa, bytes) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.NotManifest,
};
if (im.manifest.kind != .manifest) {
im.deinit(gpa); // frees the manifest and any `normalized`; caller frees `bytes`
return error.NotManifest;
}
return .{ .bytes = bytes, .normalized = im.normalized, .manifest = im.manifest };
}
/// The §8.3 baseline resolver for `files`: the baseline was already located and
/// parsed (eagerly, exactly once), so `resolve` just hands back the pre-built
/// view — null when the baseline was unresolvable, which `enumerate` turns into
/// `BaselineUnresolvable`. `enumerate` calls it only for a delta manifest, always
/// with that manifest's single B-card hash — asserted here as negative space.
const EagerBaseline = struct {
hash: ?[]const u8,
view: ?artifact.ManifestFiles,
fn resolve(ctx: *anyopaque, hash: []const u8) ?artifact.ManifestFiles {
const self: *EagerBaseline = @ptrCast(@alignCast(ctx));
std.debug.assert(self.hash != null and std.mem.eql(u8, hash, self.hash.?));
return self.view;
}
};
/// Maps a `root_dir.openFile` failure: a missing `.zit` is "not a repository",
/// every other open error is an I/O read failure.
fn openFileError(e: anyerror) Repository.OpenError {
return switch (e) {
error.FileNotFound => error.NotARepo,
error.OutOfMemory => error.OutOfMemory,
else => error.CannotRead,
};
}
/// Maps `LogStore.openReadOnly`'s closed error set into the facade's set.
fn openReadOnlyError(e: logstore.OpenError) Repository.OpenError {
return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => error.Corrupt,
error.Storage => error.CannotRead,
};
}
/// Maps `RepoView.load`'s closed error set into the facade's set.
fn loadError(e: repoview.RepoView.LoadError) Repository.OpenError {
return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => error.Corrupt,
error.Storage => error.CannotRead,
};
}
/// Maps `LogStore.content`'s closed error set into the facade's set.
fn contentError(e: logstore.ContentError) Repository.OpenError {
return switch (e) {
error.OutOfMemory => error.OutOfMemory,
error.Corrupt => error.Corrupt,
error.Storage => error.CannotRead,
};
}
/// Decode a lowercase-hex artifact name to its raw digest into `out`. Returns
/// null for anything that cannot be a stored name — an odd length, a length
/// past `max_hash_len*2`, or a non-hex digit — so the caller treats it as "not
/// present" rather than trapping on wire input.
fn decodeName(name: []const u8, out: *[logstore.max_hash_len]u8) ?[]const u8 {
if (name.len == 0 or name.len % 2 != 0) return null;
const bytes = name.len / 2;
if (bytes > logstore.max_hash_len) return null;
_ = std.fmt.hexToBytes(out[0..bytes], name) catch return null;
return out[0..bytes];
}
/// Whether `content` hashes to `digest` under the algorithm the digest length
/// selects (artifact §7.2: 20 bytes ⇒ sha1, 32 bytes ⇒ sha3-256). A digest of
/// any other length is not a name this build mints, so it cannot match.
fn hashMatches(digest: []const u8, content: []const u8) bool {
switch (digest.len) {
20 => {
var out: [20]u8 = undefined;
std.crypto.hash.Sha1.hash(content, &out, .{});
return std.mem.eql(u8, &out, digest);
},
32 => {
var out: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(content, &out, .{});
return std.mem.eql(u8, &out, digest);
},
else => return false,
}
}
// ===========================================================================
// Tests — draft-fossil-submanifests-00 §6.3/§6.5/§8.1, the settings semantics
// and the analysis pass. Pure over F-card lists; no repository is opened.
// ===========================================================================
test "submanifests §8.1: emission is off by default and off is the whole default state" {
// The acceptance claim, stated where it cannot drift: a `Settings` with
// nothing named is off and unpinned, and yields `.off`.
const s: submanifest.Settings = .off;
try std.testing.expect(!s.enabled);
try std.testing.expect(!s.pinned());
try std.testing.expectEqual(submanifest.Emission.off, submanifest.emission(s));
try std.testing.expect(submanifest.emission(s).treeK() == null);
// And the same from a config carrying no submanifest fields at all — the
// shape every repository predating this draft decodes to.
const from_cfg: submanifest.Settings = .of(.{ .hash_policy = 0, .default_branch = "trunk", .project_id = "" });
try std.testing.expectEqual(submanifest.Emission.off, submanifest.emission(from_cfg));
}
test "submanifests §8.1: the setting off pins nothing on — even with a valid k" {
// §8.1's conjunction is not symmetric: a pinned parameter is necessary for
// enabling, never sufficient. A repository that was enabled, ran, and was
// disabled again keeps its pin (so re-enabling is not a re-tune) and must
// still emit flat manifests.
const s: submanifest.Settings = .{ .enabled = false, .k = 3 };
try std.testing.expect(s.pinned());
try std.testing.expectEqual(submanifest.Emission.off, submanifest.emission(s));
}
test "submanifests §6.3: every value 1..12 is supported and yields that exact k" {
// "MUST support every value from 1 to 12 inclusive". Walked, not sampled:
// the range is the requirement.
var k: u8 = artifact.min_k;
while (k <= artifact.max_k) : (k += 1) {
try std.testing.expect(submanifest.inRange(k));
const d = submanifest.emission(.{ .enabled = true, .k = k });
try std.testing.expectEqual(@as(?u4, @intCast(k)), d.treeK());
}
}
test "submanifests §6.3: a k outside 1..12 falls back to flat and is reported, never substituted" {
// "on receiving a value outside 1..12 it MUST fall back to emitting flat
// manifests rather than substitute a parameter of its own, and SHOULD report
// the fallback to the operator." Both halves: no tree (`treeK` is null) and
// a distinguishable outcome carrying the offending value (so the report can
// name it). 0 is included — "enabled with nothing pinned", the state §8.1
// forbids creating, which must fall back rather than silently pick a value.
for ([_]u8{ 0, 13, 14, 100, 255 }) |k| {
try std.testing.expect(!submanifest.inRange(k));
const d = submanifest.emission(.{ .enabled = true, .k = k });
try std.testing.expect(d.treeK() == null); // no substituted parameter
switch (d) {
.out_of_range => |v| try std.testing.expectEqual(k, v), // reportable
else => return error.TestUnexpectedResult,
}
}
try std.testing.expect(submanifest.out_of_range_report_prefix.len != 0);
}
/// A canonical, hashed, strictly-ascending F-card list of `n` entries on
/// `arena` — the shape `buildTree` and `submanifest.cost` both require. Names
/// are fixed-width so ordering is lexicographic and the byte accounting is
/// uniform; hashes are distinct 64-hex (the SHA3-256 width) but never read by
/// the partition, which §6.1 fixes to the filename alone.
fn testEntries(arena: std.mem.Allocator, n: usize) ![]const artifact.FCard {
var list: std.ArrayList(artifact.FCard) = .empty;
for (0..n) |i| {
const name = try std.fmt.allocPrint(arena, "src/file{d:0>5}.zig", .{i});
var digest: [32]u8 = undefined;
std.mem.writeInt(u64, digest[0..8], i + 1, .little);
@memset(digest[8..], 0);
const hex = try arena.alloc(u8, 64);
_ = try std.fmt.bufPrint(hex, "{x}", .{&digest});
try list.append(arena, .{ .filename = name, .hash = hex, .perm = null, .old_name = null, .mode = .regular });
}
return list.items;
}
/// Every S card the tree emits, counted the way `submanifest.cost` counts them
/// but WITHOUT the leaf filter — the manifest's own run plus each interior
/// sub-manifest's run. The difference against `Cost.s_bytes` is exactly the
/// bytes of the cards that name interior nodes.
fn allSCardBytes(built: *const artifact.TreeBuild) usize {
var total: usize = 0;
for (built.s) |card| total += submanifest.sCardBytes(card);
for (built.subs) |sub| {
if (sub.bytes[0] != 'S') continue;
var it = std.mem.splitScalar(u8, sub.bytes, '\n');
while (it.next()) |line| {
if (line.len < 2 or line[0] != 'S' or line[1] != ' ') continue;
total += line.len + 1; // + the card's LF, as `cost` counts it
}
}
return total;
}
// §6.3's objective is "the S card bytes referencing THE LEAVES" plus the
// weighted mean leaf — not every S card the tree emits. The two coincide on a
// depth-1 tree and diverge the moment there is an interior node, so a cost that
// stopped telling them apart would still look self-consistent: `total` is
// recomputed from whatever `s_bytes` holds, and the pass would keep returning a
// plausible optimum for the wrong objective. Sum the tree both ways.
test "submanifests §6.3: the objective counts only the S cards that name leaves" {
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 400);
var saw_interior = false;
var saw_depth1 = false;
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
const c = try submanifest.cost(gpa, entries, k, .sha3_256);
if (!c.flat) {
var built = try artifact.buildTree(gpa, entries, k, .sha3_256);
defer built.deinit();
const all = allSCardBytes(&built);
try std.testing.expect(all > 0);
if (c.heights >= 2) {
// Interior nodes exist, so some card names one. Those bytes are
// not part of the objective — strictly fewer than every card.
try std.testing.expect(c.s_bytes < all);
saw_interior = true;
} else {
// Depth 1: every card names a leaf, so the filter drops nothing
// and the two agree to the byte.
try std.testing.expectEqual(all, c.s_bytes);
saw_depth1 = true;
}
}
if (k == artifact.max_k) break;
}
// Both arms are load-bearing. Without an interior tree the strict
// inequality never runs; without a depth-1 tree the equality never pins
// that the filter drops nothing BUT the interior cards.
try std.testing.expect(saw_interior);
try std.testing.expect(saw_depth1);
}
test "submanifests §6.3: the analysis pass costs every k and its optimum is a real tree" {
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 400);
var costs: [artifact.max_k - artifact.min_k + 1]submanifest.Cost = undefined;
var n: usize = 0;
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
costs[n] = try submanifest.cost(gpa, entries, k, .sha3_256);
try std.testing.expectEqual(k, costs[n].k);
// The objective is exactly §6.3's sum, not a proxy.
try std.testing.expectEqual(
@as(f64, @floatFromInt(costs[n].s_bytes)) + costs[n].weighted_mean_leaf_bytes,
costs[n].total,
);
// Flat F-card bytes do not depend on k — the same baseline every row.
try std.testing.expectEqual(costs[0].flat_bytes, costs[n].flat_bytes);
n += 1;
if (k == artifact.max_k) break;
}
try std.testing.expectEqual(@as(usize, artifact.max_k - artifact.min_k + 1), n);
const winner = submanifest.best(costs[0..n]) orelse return error.TestUnexpectedResult;
try std.testing.expect(!winner.flat);
try std.testing.expect(winner.leaves >= 2); // §6.2 step 2 — a tree partitions at least in two
try std.testing.expect(winner.heights >= 1 and winner.heights <= artifact.max_construct_height);
try std.testing.expect(winner.s_bytes > 0);
// It really is the minimum over the analyzed range.
for (costs[0..n]) |c| {
if (c.flat) continue;
try std.testing.expect(winner.total <= c.total);
}
}
// §6.3: "The implementation SHOULD choose the candidate with the lowest C(k),
// and MUST choose the lowest k among candidates with equal minimum cost." The
// SHOULD is the objective; the tie-break is the MUST, and it is the half a real
// name set is unlikely to exercise — so it is pinned directly on `best` rather
// than left to whichever corpus happens to tie. Built as literals because a tie
// is what is under test, not the arithmetic that produced one.
test "submanifests §6.3: an equal minimum cost selects the lowest k" {
const at = struct {
fn c(k: u4, total: f64) submanifest.Cost {
return .{
.k = k,
.flat = false,
.leaves = 2,
.heights = 1,
.s_bytes = 100,
.weighted_mean_leaf_bytes = total - 100.0,
.total = total,
.flat_bytes = 1000,
};
}
};
// Three-way tie at the minimum: the lowest k takes it.
{
const costs = [_]submanifest.Cost{ at.c(1, 500.0), at.c(2, 500.0), at.c(3, 500.0) };
const w = submanifest.best(&costs) orelse return error.TestUnexpectedResult;
try std.testing.expectEqual(@as(u4, 1), w.k);
}
// A tie at the minimum that is NOT the first entry: a strictly cheaper k=2
// wins, and k=3's equal cost must not displace it.
{
const costs = [_]submanifest.Cost{ at.c(1, 900.0), at.c(2, 500.0), at.c(3, 500.0) };
const w = submanifest.best(&costs) orelse return error.TestUnexpectedResult;
try std.testing.expectEqual(@as(u4, 2), w.k);
}
// The tie-break never overrides the objective: a strictly lower cost at a
// higher k still wins.
{
const costs = [_]submanifest.Cost{ at.c(1, 500.0), at.c(2, 499.0) };
const w = submanifest.best(&costs) orelse return error.TestUnexpectedResult;
try std.testing.expectEqual(@as(u4, 2), w.k);
}
// A flat candidate is not a candidate at all, even at cost 0 — §6.2 step 2.
{
var flat = at.c(1, 0.0);
flat.flat = true;
const costs = [_]submanifest.Cost{ flat, at.c(2, 500.0) };
const w = submanifest.best(&costs) orelse return error.TestUnexpectedResult;
try std.testing.expectEqual(@as(u4, 2), w.k);
}
}
test "submanifests §6.3: the leaf count falls and the mean leaf grows as k rises" {
// The tradeoff §6.5 describes — "group sizes follow the geometric
// distribution of the boundary test, mean 2^k members" — is what makes the
// objective have an interior minimum at all. If either side were flat the
// pass would just pick an endpoint, so pin the monotone shape rather than a
// measured number (which is a MEASUREMENT, never a test input).
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 600);
const c1 = try submanifest.cost(gpa, entries, 1, .sha3_256);
const c3 = try submanifest.cost(gpa, entries, 3, .sha3_256);
const c5 = try submanifest.cost(gpa, entries, 5, .sha3_256);
try std.testing.expect(c1.leaves > c3.leaves);
try std.testing.expect(c3.leaves > c5.leaves);
try std.testing.expect(c1.weighted_mean_leaf_bytes < c3.weighted_mean_leaf_bytes);
try std.testing.expect(c3.weighted_mean_leaf_bytes < c5.weighted_mean_leaf_bytes);
try std.testing.expect(c1.s_bytes > c3.s_bytes);
try std.testing.expect(c3.s_bytes > c5.s_bytes);
}
test "submanifests §6.2 step 2: a name set too small to partition costs as flat at every k" {
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 1);
var costs: [artifact.max_k - artifact.min_k + 1]submanifest.Cost = undefined;
var n: usize = 0;
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
costs[n] = try submanifest.cost(gpa, entries, k, .sha3_256);
try std.testing.expect(costs[n].flat);
try std.testing.expectEqual(@as(usize, 0), costs[n].leaves);
try std.testing.expect(costs[n].flat_bytes > 0);
n += 1;
if (k == artifact.max_k) break;
}
// `best` never proposes a k that would not produce a tree.
try std.testing.expect(submanifest.best(costs[0..n]) == null);
}
test "submanifests §6.5: the prediction is half the base-2 log of the file count" {
// Informative, and reported beside the measurement — so pin the formula
// rather than any measured optimum.
try std.testing.expectApproxEqAbs(@as(f64, 5.0), submanifest.predictedK(1024), 1e-9);
try std.testing.expectApproxEqAbs(@as(f64, 8.0), submanifest.predictedK(65536), 1e-9);
try std.testing.expectEqual(@as(f64, 0), submanifest.predictedK(0));
try std.testing.expectEqual(@as(f64, 0), submanifest.predictedK(1));
}
test "submanifests §6.3: the analysis pass is advisory and writes nothing — it is pure over its input" {
// "The selection is advisory rather than canonical -- any pinned k yields
// conforming artifacts", and §6.4 "MUST NOT re-tune automatically". The
// structural guarantee behind both is that `cost` takes no repository and
// no settings: it cannot pin anything. Repeat it and get the same answer.
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 300);
const a = try submanifest.cost(gpa, entries, 3, .sha3_256);
const b = try submanifest.cost(gpa, entries, 3, .sha3_256);
try std.testing.expectEqual(a.leaves, b.leaves);
try std.testing.expectEqual(a.s_bytes, b.s_bytes);
try std.testing.expectEqual(a.total, b.total);
}
test "submanifests §6.3: S-card and F-card byte counts follow §6.2's canonical minimal escaping" {
// §6.2: "Canonical emission is minimal escaping: exactly SP (0x20) as \\s,
// LF (0x0A) as \\n, and backslash (0x5C) as \\\; every other octet ... is
// emitted raw". A byte count that escaped more (or less) would misprice
// every name set carrying one of those three octets.
const hash = "0" ** 64;
// `S ` + name + ` ` + hash + LF, with `a b` encoding as `a\sb` (4 bytes).
try std.testing.expectEqual(
@as(usize, 2 + 4 + 1 + 64 + 1),
submanifest.sCardBytes(.{ .filename = "a b", .hash = hash }),
);
// A TAB is one of the decoder's other escape octets and stays RAW (3 bytes).
try std.testing.expectEqual(
@as(usize, 2 + 3 + 1 + 64 + 1),
submanifest.sCardBytes(.{ .filename = "a\tb", .hash = hash }),
);
// `F ` + name + ` ` + hash + ` ` + perm + LF.
try std.testing.expectEqual(
@as(usize, 2 + 3 + 1 + 64 + 1 + 1 + 1),
submanifest.flatFCardBytes(.{ .filename = "a.z", .hash = hash, .perm = "x", .old_name = null, .mode = .executable }),
);
}
// ===========================================================================
// Tests — draft-fossil-submanifests-00 §6.4's drift-check core. Pure over
// F-card lists, same as the §6.3 analysis pass above; `driftCheck` itself
// writes nothing and decides nothing about WHETHER to retune -- it only
// answers whether a retune would be recommended.
// ===========================================================================
test "submanifests §6.4: a tie-zone drift is refused — margin search over testEntries" {
// §6.4 makes the writer "retain the current value unless the candidate is
// distinct and C_candidate < (1 - m) * C_current", so a drift that does not
// clear the margin leaves the pin alone. The real grounding case is the "fossil" project
// corpus (983 files, k=4 vs k=5 ~5% apart) but that corpus isn't
// available to this test -- so search synthetic `testEntries` sizes for a
// REAL near-tie pair (computed here, not asserted from thin air), pin
// driftCheck to the worse of that pair, and confirm it refuses.
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const arena = arena_state.allocator();
var found = false;
var found_n: usize = 0;
var found_pinned_k: u4 = 0;
var found_margin: f64 = 0;
var n: usize = 50;
search: while (n <= 2000) : (n += 63) {
const entries = try testEntries(arena, n);
var costs: [artifact.max_k - artifact.min_k + 1]submanifest.Cost = undefined;
var cn: usize = 0;
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
costs[cn] = try submanifest.cost(gpa, entries, k, .sha3_256);
cn += 1;
if (k == artifact.max_k) break;
}
const winner = submanifest.best(costs[0..cn]) orelse continue;
for (costs[0..cn]) |c| {
if (c.flat or c.k == winner.k) continue;
// Same formula driftCheck uses: the pinned (candidate) objective
// is the denominator, matching "margin over the pinned value's
// objective" (§6.4).
const margin = (c.total - winner.total) / c.total * 100.0;
if (margin > 0 and margin < submanifest.drift_margin_pct) {
found = true;
found_n = n;
found_pinned_k = c.k;
found_margin = margin;
break :search;
}
}
}
// The search must have actually found a real near-tie pair -- otherwise
// this test would be vacuous.
try std.testing.expect(found);
try std.testing.expect(found_margin > 0 and found_margin < submanifest.drift_margin_pct);
const entries = try testEntries(arena, found_n);
const result = try submanifest.driftCheck(gpa, entries, found_pinned_k, .sha3_256);
try std.testing.expect(result == null);
}
test "submanifests §6.4: real drift past the margin is recommended — pinned k=1 vs testEntries(112)'s optimum" {
// Measured this session on a zit-repo-shaped synthetic set: pinned to
// k=1 totals ~5903.1, the true optimum (k=3) totals ~2490.9 -- about
// 57.8%, comfortably past the 15% margin. Assert the SHAPE (which k wins,
// that the margin clears the gate by a wide berth), not the exact floats
// -- those are a measurement, not a test input.
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 112);
const result = try submanifest.driftCheck(gpa, entries, 1, .sha3_256);
const dc = result orelse return error.TestUnexpectedResult;
try std.testing.expectEqual(@as(u4, 3), dc.recommended.k);
try std.testing.expect(dc.margin_pct > 45.0 and dc.margin_pct < 70.0);
}
test "submanifests §6.4: predictedK never gates the check — a count-matching k with real drift still recommends" {
// Design-review erratum: `predictedK` is documented (see its doc comment
// above) as informative-only, "never an input to a default", because it
// depends on file count alone while the real §6.3 objective depends on
// leaf SIZE distribution too. A cheap-tier short-circuit that skipped the
// expensive scan whenever round(predictedK(n)) == pinned_k would silently
// swallow real drift whenever count alone happened to agree with the
// pin -- a false negative in the one thing this check exists to catch,
// and a repurposing of predictedK as a decision input. Search for a real
// (n, pinned_k) pair where the count-only proxy agrees with pinned_k but
// the real, size-aware objective still clears the margin, and confirm
// driftCheck recommends anyway -- proving the expensive tier always runs.
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const arena = arena_state.allocator();
var found: ?submanifest.DriftCheck = null;
var n: usize = 50;
search: while (n <= 2000) : (n += 37) {
const predicted = submanifest.predictedK(n);
const rounded = @as(i64, @intFromFloat(@round(predicted)));
if (rounded < artifact.min_k or rounded > artifact.max_k) continue;
const pinned_k: u4 = @intCast(rounded);
const entries = try testEntries(arena, n);
const result = try submanifest.driftCheck(gpa, entries, pinned_k, .sha3_256);
if (result) |dc| {
if (dc.margin_pct > submanifest.drift_margin_pct) {
found = dc;
break :search;
}
}
}
const dc = found orelse return error.TestUnexpectedResult;
try std.testing.expect(dc.margin_pct > submanifest.drift_margin_pct);
}
test "submanifests §6.4: an exact-margin case is refused, not accepted — the strict boundary" {
// Real hash-derived costs essentially never land on exactly
// `drift_margin_pct` by chance, so this exercises the boundary arithmetic
// directly with manufactured totals rather than searching for a
// coincidence. 100.0 -> 85.0 is exactly 15% -- must be refused (the
// margin does not EXCEED the gate) -- and one float ULP past it, on
// either side, flips the outcome.
try std.testing.expect(submanifest.marginGate(100.0, 85.0) == null);
const just_over = submanifest.marginGate(100.0, std.math.nextAfter(f64, 85.0, 0.0));
try std.testing.expect(just_over != null);
try std.testing.expect(just_over.? > submanifest.drift_margin_pct);
try std.testing.expect(submanifest.marginGate(100.0, std.math.nextAfter(f64, 85.0, 100.0)) == null);
}
test "submanifests §6.4: pinned k already at the optimum is never flagged" {
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 400);
var costs: [artifact.max_k - artifact.min_k + 1]submanifest.Cost = undefined;
var n: usize = 0;
var k: u4 = artifact.min_k;
while (true) : (k += 1) {
costs[n] = try submanifest.cost(gpa, entries, k, .sha3_256);
n += 1;
if (k == artifact.max_k) break;
}
const winner = submanifest.best(costs[0..n]) orelse return error.TestUnexpectedResult;
// Pinning exactly to the analyzed optimum leaves nothing to recommend --
// margin against yourself is 0, which does not exceed the gate.
const result = try submanifest.driftCheck(gpa, entries, winner.k, .sha3_256);
try std.testing.expect(result == null);
}
test "submanifests §6.2 step 2 / §6.4: a name set too small to partition never crashes and never recommends" {
// Every k costs flat (see the sibling §6.2 step 2 test above), so `best`
// returns null and driftCheck has nothing to compare against -- null, not
// a crash or a spurious recommendation.
const gpa = std.testing.allocator;
var arena_state = std.heap.ArenaAllocator.init(gpa);
defer arena_state.deinit();
const entries = try testEntries(arena_state.allocator(), 1);
const result = try submanifest.driftCheck(gpa, entries, 1, .sha3_256);
try std.testing.expect(result == null);
}