Artifact 03abd778bac67d692d51e067835af36634358622b3b566ef0f9116c08bb2688c:
- File
src/checkpoint.zig
— part of check-in
[2a8fdcff60]
at
2026-08-12 09:04:13
on branch sub-manifest
— checkpoint: retire the tree shape — sidecar only, structurally
The tree shape minted permanent SUBMANIFEST artifacts for benefits already had elsewhere: the rebuild win lives in the prefix record, verify's §6.2 oracle runs buildTree in memory, and the subtree-sharing bytes re-materialize at the first real S-emitting commit at identical cost. Minting early only created unreferenced permanent artifacts and the allow-tree/demotion/gate apparatus needed to keep automation from doing it by accident — all deleted with it. build no longer opens the log for writing or reads the emission settings at all; sidecar layout v3 (old sidecars miss and rebuild in seconds). Proven at scale: SHA-256 of pkgsrc's 593MB store is byte-identical across a full build; cold 4:12, rebuild 3.4s. (user: dmestas, size: 25386) [annotate] [blame] [check-ins using]
//! The durable rebuild checkpoint (hybrid-history acceleration). //! //! A `.zit-cache/checkpoint` sidecar records one prefix-anchored claim: "as of //! check-in C, whose frame closes the log prefix `[0, prefix_key.end)`, the //! fully-verified file set fingerprints to this value" — plus the crosslink //! record body for that prefix, so `Repository.open`'s miss path can //! `RepoView.resumeFrom` the prefix instead of re-parsing a permanently flat //! F-card segment on every from-scratch derive (submanifests §7.4 applied to //! the segment §7.4 cannot reach). //! //! SIDECAR ONLY, by design: a checkpoint never writes the log. An earlier //! revision had a `tree` shape that pinned the anchor's file set as stored //! SUBMANIFEST artifacts; it was retired because everything it bought is had //! for free elsewhere — the rebuild win lives entirely in the prefix record, //! `verify` recomputes the canonical tree in memory as its oracle, and the //! §6.2 subtree-sharing bytes re-materialize at the first real S-emitting //! commit at identical cost, attributed to a commit somebody actually made. //! Minting them early only created permanent, unreferenced artifacts and the //! policy apparatus to keep automation from doing it by accident. //! //! Advisory-tier all the way down, exactly like `repocache.zig`, on which the //! container is modelled: deleting the file changes no answer, every //! validation failure is a MISS (never an error), `--no-cache` bypasses it, //! and the claim is independently re-derivable (`verify`). Strictly local, //! never synced, never history: the sidecar appears in no artifact and //! crosses no wire. const std = @import("std"); const artifact = @import("artifact.zig"); const logstore = @import("logstore.zig"); const repocache = @import("repocache.zig"); const repository = @import("repository.zig"); const repostate = @import("repostate.zig"); const repoview = @import("repoview.zig"); const storage = @import("storage.zig"); const crc32 = @import("crc32.zig"); /// The sidecar's member inside the advisory `.zit-cache/` directory (the home /// the consolidation reserved for it). Ignore-glob'd and never committed; /// disposable by construction. pub const checkpoint_filename: []const u8 = repocache.cache_dirname ++ "/checkpoint"; const magic = "ZITCKPNT"; // v2 carried the retired `tree` shape's fields; v3 is witness-only and drops // them from the layout. An old sidecar misses and is rebuilt (or advanced) // on the next explicit build or healing open. const format_version: u16 = 3; /// The sidecar's identity claim, exactly what the header stores. The hash /// slice borrows the load's backing buffer (`Loaded.buf`). pub const Claim = struct { /// The check-in whose frame closes the prefix. checkin_hash: []const u8, /// `artifact.fileSetFingerprint` over C's complete file set — the cheap /// structural witness `verify` re-derives from real history. fileset_fingerprint: [32]u8, /// The log prefix the record body distills; `logstore.validatePrefix` is /// the O(1) revalidation on every load. prefix_key: logstore.LogStore.LogKey, /// The shun-table fingerprint at capture: a record body distilled under an /// old mask may carry a record the mask must now hide, so any difference /// is a MISS (the same rule `.zit-cache` extension follows). shun_fp: u32, }; /// Bytes before the variable spans: /// `magic(8) | format_version(2) | reserved(2) | prefix_end(8) | /// prefix_frame_count(8) | prefix_last_frame_offset(8) | /// prefix_last_header_crc(4) | shun_fp(4) | checkin_hash_len(1) | /// fileset_fingerprint(32) | main_branch_len(2) | body_len(4)`. const fixed_prefix_len: usize = 8 + 2 + 2 + 8 + 8 + 8 + 4 + 4 + 1 + 32 + 2 + 4; // = 83 const checksum_len: usize = 4; /// A validated load: `claim`, `main_branch` and `body` slice into `buf`. pub const Loaded = struct { buf: []u8, claim: Claim, main_branch: []const u8, body: []const u8, pub fn deinit(self: *Loaded, gpa: std.mem.Allocator) void { gpa.free(self.buf); self.* = undefined; } }; /// Evidence seam for the paranoid-bypass tests: every `tryLoad` entry counts, /// BEFORE the sidecar is opened. `--no-cache` must leave this untouched — the /// promise is "trust nothing derived", and a bypass that still consults the /// sidecar is not one. Single-threaded like every derive path. pub var tryload_consults: u64 = 0; /// Read and fully validate the sidecar against the LIVE log: magic, version, /// self-checksum over every pre-checksum byte, structural spans that exactly /// account for the file size, and a prefix key that still validates /// (`validatePrefix` — the log may have GROWN, which is the whole point; /// truncation or a rewritten boundary is a miss). Returns null on ANY failure /// — a checkpoint is advisory, so an unreadable one just means "derive from /// the log". The caller still owns the shun-fingerprint compare (it needs an /// open scan) and the anchor-resolution check. pub fn tryLoad(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, log_file: storage.StorageFile) ?Loaded { tryload_consults += 1; var file = dir.openFile(io, checkpoint_filename, .{}) catch return null; defer file.close(io); const st = file.stat(io) catch return null; const size = std.math.cast(usize, st.size) orelse return null; if (size < fixed_prefix_len + checksum_len) return null; const buf = gpa.alloc(u8, size) catch return null; const n = file.readPositionalAll(io, buf, 0) catch { gpa.free(buf); return null; }; if (n != size) { gpa.free(buf); return null; } const loaded = parse(buf) orelse { gpa.free(buf); return null; }; if (!logstore.LogStore.validatePrefix(log_file, loaded.claim.prefix_key)) { gpa.free(buf); return null; } return loaded; } /// The pure structural half of `tryLoad`, split out so corruption tests can /// drive it byte-by-byte. `buf` is the whole file; the returned slices borrow /// it. Null on any framing violation — never partial trust. fn parse(buf: []u8) ?Loaded { if (buf.len < fixed_prefix_len + checksum_len) return null; if (!std.mem.eql(u8, buf[0..8], magic)) return null; if (std.mem.readInt(u16, buf[8..10], .little) != format_version) return null; // The whole-file checksum first: no declared length below is trusted // before the bytes carrying it prove intact. const stored_crc = std.mem.readInt(u32, buf[buf.len - checksum_len ..][0..4], .little); var crc = crc32.Crc32.init(); crc.update(buf[0 .. buf.len - checksum_len]); if (crc.final() != stored_crc) return null; if (std.mem.readInt(u16, buf[10..12], .little) != 0) return null; // reserved const key: logstore.LogStore.LogKey = .{ .end = std.mem.readInt(u64, buf[12..20], .little), .frame_count = std.mem.readInt(u64, buf[20..28], .little), .last_frame_offset = std.mem.readInt(u64, buf[28..36], .little), .last_header_crc = std.mem.readInt(u32, buf[36..40], .little), }; const shun_fp = std.mem.readInt(u32, buf[40..44], .little); const ckh_len: usize = buf[44]; var fp: [32]u8 = undefined; @memcpy(&fp, buf[45..77]); const mb_len: usize = std.mem.readInt(u16, buf[77..79], .little); const body_len: usize = std.mem.readInt(u32, buf[79..83], .little); // Artifact names are 40 or 64 lowercase hex. if (ckh_len != 40 and ckh_len != 64) return null; if (mb_len == 0) return null; // Exact byte accounting: the declared spans plus framing must equal the // file, so neither truncation nor trailing garbage survives. const want = fixed_prefix_len + ckh_len + mb_len + body_len + checksum_len; if (want != buf.len) return null; var pos: usize = fixed_prefix_len; const ckh = buf[pos..][0..ckh_len]; pos += ckh_len; const mb = buf[pos..][0..mb_len]; pos += mb_len; const body = buf[pos..][0..body_len]; return .{ .buf = buf, .claim = .{ .checkin_hash = ckh, .fileset_fingerprint = fp, .prefix_key = key, .shun_fp = shun_fp, }, .main_branch = mb, .body = body, }; } /// Atomically materialize the sidecar (temp + fsync + rename, the sequence /// every sibling writer uses). Every failure is swallowed: a checkpoint is an /// optimization, never a correctness dependency, so the worst outcome of a /// failed write is the derive it would have skipped. pub fn store( gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, claim: Claim, main_branch: []const u8, body: []const u8, ) void { std.debug.assert(claim.checkin_hash.len == 40 or claim.checkin_hash.len == 64); std.debug.assert(main_branch.len != 0); if (!repocache.ensureCacheDir(io, dir)) return; var out: std.ArrayList(u8) = .empty; defer out.deinit(gpa); appendAll(gpa, &out, claim, main_branch, body) catch return; var af = dir.createFileAtomic(io, checkpoint_filename, .{ .replace = true }) catch return; defer af.deinit(io); af.file.writePositionalAll(io, out.items, 0) catch return; af.file.sync(io) catch return; af.replace(io) catch return; } fn appendAll( gpa: std.mem.Allocator, out: *std.ArrayList(u8), claim: Claim, main_branch: []const u8, body: []const u8, ) error{OutOfMemory}!void { try out.appendSlice(gpa, magic); try appendInt(gpa, out, u16, format_version); try appendInt(gpa, out, u16, 0); // reserved try appendInt(gpa, out, u64, claim.prefix_key.end); try appendInt(gpa, out, u64, claim.prefix_key.frame_count); try appendInt(gpa, out, u64, claim.prefix_key.last_frame_offset); try appendInt(gpa, out, u32, claim.prefix_key.last_header_crc); try appendInt(gpa, out, u32, claim.shun_fp); try out.append(gpa, @intCast(claim.checkin_hash.len)); try out.appendSlice(gpa, &claim.fileset_fingerprint); try appendInt(gpa, out, u16, @intCast(main_branch.len)); try appendInt(gpa, out, u32, @intCast(body.len)); try out.appendSlice(gpa, claim.checkin_hash); try out.appendSlice(gpa, main_branch); try out.appendSlice(gpa, body); var crc = crc32.Crc32.init(); crc.update(out.items); try appendInt(gpa, out, u32, crc.final()); std.debug.assert(out.items.len == fixed_prefix_len + claim.checkin_hash.len + main_branch.len + body.len + checksum_len); } fn appendInt(gpa: std.mem.Allocator, out: *std.ArrayList(u8), comptime T: type, v: T) error{OutOfMemory}!void { var b: [@sizeOf(T)]u8 = undefined; std.mem.writeInt(T, &b, v, .little); try out.appendSlice(gpa, &b); } /// Delete the sidecar. A missing file is success, not an error — the file is /// disposable by construction (`zit checkpoint drop`). pub fn drop(io: std.Io, dir: std.Io.Dir) void { dir.deleteFile(io, checkpoint_filename) catch {}; } // --------------------------------------------------------------------------- // The builder. One pass, sidecar only: enumerate C's file set through the // §9.3 seam, fingerprint it, capture the prefix record body (reusing an // existing sidecar's body and its delta-free attestation when possible), and // atomically write the sidecar. The log is opened READ-ONLY — a checkpoint // build cannot write history, structurally. // --------------------------------------------------------------------------- pub const BuildError = error{ OutOfMemory, Storage, Corrupt, /// `C` is absent from the log, interned only as a phantom, or (for the /// null-checkin default) the repository has no leaves to anchor on. CheckinNotFound, /// `C` names an artifact that is not a check-in manifest. NotACheckin, /// A checkpoint off the mainline is refused: `C` must be an ancestor of /// every open leaf (merge-base fold when no check-in was named). CheckinNotAncestorOfAllLeaves, /// The prefix contains a delta manifest — out of scope (zit's writer /// emits none; this guards imported history). DeltaManifestInPrefix, }; pub const BuildReport = struct { checkin_hash_buf: [64]u8, checkin_hash_len: u8, files: usize, prefix_frames: u64, pub fn checkinHash(self: *const BuildReport) []const u8 { return self.checkin_hash_buf[0..self.checkin_hash_len]; } }; /// Build (or rebuild) the checkpoint for `repo` anchored at `checkin` (a full /// lowercase-hex check-in name), or at the merge-base fold of every open leaf /// when null. Idempotent: rebuilding over unchanged history rewrites an /// identical sidecar and touches nothing else. pub fn build( gpa: std.mem.Allocator, io: std.Io, repo: *repository.Repository, dir: std.Io.Dir, checkin: ?[]const u8, ) BuildError!BuildReport { const state = &repo.view.state; // 1. Every open leaf, then C: named, or the merge-base fold of the leaves. var leaf_list: std.ArrayList(repostate.Rid) = .empty; defer leaf_list.deinit(gpa); var it = state.leaves(); while (it.next()) |rid| try leaf_list.append(gpa, rid); const c_rid: repostate.Rid = blk: { if (checkin) |hex| break :blk repo.view.lookup(hex) orelse return error.CheckinNotFound; if (leaf_list.items.len == 0) return error.CheckinNotFound; var anchor = leaf_list.items[0]; for (leaf_list.items[1..]) |leaf| { anchor = (try state.mergeBaseOf(gpa, anchor, leaf)) orelse return error.CheckinNotAncestorOfAllLeaves; // disjoint roots have no mainline } break :blk anchor; }; // 2. Mainline rule: C must be an ancestor of every open leaf. for (leaf_list.items) |leaf| { if (!(try state.isAncestorOf(gpa, c_rid, leaf))) return error.CheckinNotAncestorOfAllLeaves; } // 3. C's file set, through the one §9.3 seam (`Repository.files` walks // trees via `flattenIfTree`; no raw F-card iteration here). var fl = (repo.files(gpa, c_rid) catch |e| return mapFilesError(e)) orelse return error.CheckinNotFound; // interned phantom: no content to enumerate defer fl.deinit(gpa); var entries: std.ArrayList(artifact.FCard) = .empty; defer entries.deinit(gpa); var files_it = fl.iterator(); while (files_it.next()) |f| try entries.append(gpa, f); const fingerprint = try artifact.fileSetFingerprint(gpa, entries.items); // 4. The log, read-only: a checkpoint build cannot write history. var file = dir.openFile(io, repository.repo_filename, .{}) catch return error.Storage; defer file.close(io); const st = file.stat(io) catch return error.Storage; var fs = storage.FileStorage.init(io, file, st.size); var log = logstore.LogStore.openReadOnly(gpa, fs.storageFile()) catch |e| return switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, error.Corrupt => error.Corrupt, }; defer log.deinit(gpa); // 5. C's frame closes the prefix. const c_hex = repo.view.hashOf(c_rid); var digest: [logstore.max_hash_len]u8 = undefined; const c_raw = digest[0 .. c_hex.len / 2]; _ = std.fmt.hexToBytes(c_raw, c_hex) catch return error.Corrupt; const c_logrid = log.lookup(c_raw) orelse return error.CheckinNotFound; const key = log.logKeyAt(c_logrid) catch |e| return switch (e) { error.Storage => error.Storage, error.Corrupt => error.Corrupt, }; // 6. The prefix record body and the delta refusal, in ONE walk, from the // cheapest source. ADVANCE: a valid existing sidecar whose prefix is a // prefix of ours already carries [0, L0) — and its existence attests // that span delta-free, because this builder refuses delta prefixes, // so a sidecar it wrote proves the property for everything it covers. // Only the tail (L0, L) is parsed. COLD: capture the whole prefix // view-free; the capture IS the delta scan. var body: std.ArrayList(u8) = .empty; defer body.deinit(gpa); var facts: repoview.CaptureFacts = .{}; var advanced_from: ?u64 = null; reuse: { var old = tryLoad(gpa, io, dir, fs.storageFile()) orelse break :reuse; defer old.deinit(gpa); if (old.claim.shun_fp != log.shunFingerprint()) break :reuse; if (old.claim.prefix_key.end > key.end) break :reuse; // anchor moved backward: rebuild cold body.appendSlice(gpa, old.body) catch return error.OutOfMemory; advanced_from = old.claim.prefix_key.end; } const capture_from: u64 = advanced_from orelse logstore.header_len; repoview.captureRecords(gpa, &log, capture_from, key.end, &body, &facts) catch |e| return switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, error.Corrupt => error.Corrupt, }; if (facts.saw_delta_manifest) return error.DeltaManifestInPrefix; var report: BuildReport = .{ .checkin_hash_buf = undefined, .checkin_hash_len = @intCast(c_hex.len), .files = entries.items.len, .prefix_frames = key.frame_count, }; @memcpy(report.checkin_hash_buf[0..c_hex.len], c_hex); // 7. The sidecar, last. `store` swallows failures: the checkpoint is an // optimization, and nothing durable preceded it. store(gpa, io, dir, .{ .checkin_hash = c_hex, .fileset_fingerprint = fingerprint, .prefix_key = key, .shun_fp = log.shunFingerprint(), }, repo.view.main_branch, body.items); return report; } /// How many bytes the log must have grown past a checkpoint's prefix before /// the open path bothers advancing it. Below this, the resume already covers /// the tail cheaply and an advance would spend more than it saves; above it, /// the one-time advance cost (a tail parse plus one file-set fingerprint) /// keeps the checkpoint from drifting toward a full re-derive. pub const advance_min_growth_bytes: u64 = 4 << 20; /// Opportunistically ADVANCE an existing checkpoint to the current mainline /// anchor. Called from `Repository.open`'s healing paths behind the growth /// and anchor-progress gates. Sidecar-only like every build, so there is /// nothing an automatic act could make permanent. Best-effort end to end: /// every refusal or failure is silent, and the worst outcome is the /// checkpoint staying where it was. No-op when no checkpoint exists — the /// operator opts in by building once; this only keeps that choice fresh. pub fn advance(gpa: std.mem.Allocator, io: std.Io, repo: *repository.Repository, dir: std.Io.Dir) void { var file = dir.openFile(io, repository.repo_filename, .{}) catch return; defer file.close(io); const st = file.stat(io) catch return; var fs = storage.FileStorage.init(io, file, st.size); var loaded = tryLoad(gpa, io, dir, fs.storageFile()) orelse return; defer loaded.deinit(gpa); if (st.size < loaded.claim.prefix_key.end) return; // tryLoad validated, but stat raced if (st.size - loaded.claim.prefix_key.end < advance_min_growth_bytes) return; // Progress gate: the growth above may be blobs alone, with the mainline // anchor unmoved — advancing then would rewrite the same prefix forever. // The would-be anchor is the same merge-base fold `build` performs, // compared by hash so no frame walk is paid to discover there is nothing // to do. { const state = &repo.view.state; var it = state.leaves(); var anchor: ?repostate.Rid = null; while (it.next()) |leaf| { anchor = if (anchor) |a| (state.mergeBaseOf(gpa, a, leaf) catch return) orelse return else leaf; } const a = anchor orelse return; if (std.mem.eql(u8, repo.view.hashOf(a), loaded.claim.checkin_hash)) return; } _ = build(gpa, io, repo, dir, null) catch return; } // --------------------------------------------------------------------------- // The verifier (DESIGN §6): re-derive every claim from real history alone. // The sidecar's record body and fingerprint are COMPARANDS here, never // inputs — the derivation and the file set are rebuilt independently and the // sidecar must match them byte for byte. The §6.2 canonical-tree oracle runs // entirely IN MEMORY: `buildTree` over the independently derived file set // exercises the canonical construction without storing a byte. // --------------------------------------------------------------------------- pub const Verdict = union(enum) { ok: BuildReport, no_checkpoint, /// The sidecar does not validate against the live log (unparseable, or a /// prefix key the log no longer backs) — the same conditions the open /// path treats as a silent miss, named for the operator. stale, /// §6.1: an independently captured prefix record body differs from the /// sidecar's — a resume from this sidecar would not equal a full derive. derivation_mismatch, /// The independently derived file set at C fingerprints differently — /// the deep check the open path deliberately never pays for. fileset_mismatch, }; /// Verify the sidecar against real history: open the repository with BOTH /// derived sidecars bypassed, re-capture the prefix record body, re-enumerate /// C's file set through the §9.3 seam, and compare. Reads the sidecar only to /// know what is being claimed; changes nothing. pub fn verify(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) BuildError!Verdict { // The claim (comparand). Absence is its own verdict; any validation // failure — container or prefix key — is `stale`. var probe = dir.openFile(io, checkpoint_filename, .{}) catch return .no_checkpoint; probe.close(io); var file = dir.openFile(io, repository.repo_filename, .{}) catch return error.Storage; defer file.close(io); const st = file.stat(io) catch return error.Storage; var fs = storage.FileStorage.init(io, file, st.size); var loaded = tryLoad(gpa, io, dir, fs.storageFile()) orelse return .stale; defer loaded.deinit(gpa); // The paranoid derivation: trust nothing derived. var repo: repository.Repository = undefined; repository.Repository.open(&repo, gpa, io, dir, .{ .bypass_cache = true }) catch |e| return switch (e) { error.OutOfMemory => error.OutOfMemory, error.NotARepo, error.CannotRead => error.Storage, error.Corrupt => error.Corrupt, }; defer repo.deinit(gpa); var log = logstore.LogStore.openReadOnly(gpa, fs.storageFile()) catch |e| return switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, error.Corrupt => error.Corrupt, }; defer log.deinit(gpa); if (loaded.claim.shun_fp != log.shunFingerprint()) return .stale; // §6.1: the prefix record body, re-captured from the log alone. { var body: std.ArrayList(u8) = .empty; defer body.deinit(gpa); var facts: repoview.CaptureFacts = .{}; repoview.captureRecords(gpa, &log, logstore.header_len, loaded.claim.prefix_key.end, &body, &facts) catch |e| return switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, error.Corrupt => error.Corrupt, }; if (!std.mem.eql(u8, body.items, loaded.body)) return .derivation_mismatch; } // C's file set, independently, through the seam. const c_rid = repo.view.lookup(loaded.claim.checkin_hash) orelse return .stale; var fl = (repo.files(gpa, c_rid) catch |e| return mapFilesError(e)) orelse return .stale; defer fl.deinit(gpa); var entries: std.ArrayList(artifact.FCard) = .empty; defer entries.deinit(gpa); var fit = fl.iterator(); while (fit.next()) |f| try entries.append(gpa, f); const fingerprint = try artifact.fileSetFingerprint(gpa, entries.items); if (!std.mem.eql(u8, &fingerprint, &loaded.claim.fileset_fingerprint)) return .fileset_mismatch; // The in-memory canonical-tree oracle: batch construction over the // independently derived set exercises the §6.2 construction end to end // (its own invariants assert the canonical shape); nothing is stored, so // this proves without adding. { var built = try artifact.buildTree(gpa, entries.items, artifact.min_k, .sha3_256); built.deinit(); } var report: BuildReport = .{ .checkin_hash_buf = undefined, .checkin_hash_len = @intCast(loaded.claim.checkin_hash.len), .files = entries.items.len, .prefix_frames = loaded.claim.prefix_key.frame_count, }; @memcpy(report.checkin_hash_buf[0..loaded.claim.checkin_hash.len], loaded.claim.checkin_hash); return .{ .ok = report }; } fn mapFilesError(e: repository.Repository.FilesError) BuildError { return switch (e) { error.OutOfMemory => error.OutOfMemory, error.NotManifest => error.NotACheckin, // The check-in's own history is unreadable through the seam — the // repository, not the request, is at fault. error.NotARepo, error.CannotRead => error.Storage, error.Corrupt, error.BaselineUnresolvable, error.BaselineIsDelta => error.Corrupt, }; }