Artifact bb8e8c24f69b80e537dbcc685fe79c9374a4304a532a7f3b87a37315c050f5f4:
- File
src/pack.zig
— part of check-in
[3e5895dfb7]
at
2026-07-29 21:21:21
on branch shun-implementation
— shun S1: a shunned artifact reads as absent
content, contentCached and wire return null for a name in the shun table even while its frame is on disk, so reclaiming the bytes later never changes what a verb prints. The guard sits in the one shared read body behind a ReadMask the call site names, so 'the masked set is exactly these three' is compiler-checked rather than asserted in prose.
It deliberately does NOT sit in contentAtOffset. sync SS7.7 L1445-1450 lets a held-but-shunned DELTASRC serve as a delta basis, and zit satisfies that for free because delta_of is a byte offset -- base resolution never re-enters the rid-keyed doors. A test pins it so a future tidy-up downward fails loudly.
pack reads through an unmasked maintenance door: in this slice a shunned frame still copies forward, since dropping it is the S2 filter. pickBase probes through the masked door, so a shunned frame never roots a new delta. (user: dmestas, size: 44682) [annotate] [blame] [check-ins using]
//! The `zit pack` re-deltification pass — the fossil `extra_deltification` //! analog (storage-delta-base-selection.md §6). A whole-store generational //! rewrite that reconstructs every content artifact and re-stores it through //! the `pickBase` best-of-N policy (logstore.zig), so a source frame's stored //! encoding — including a verbatim wire delta whose sender chose the base — is //! never trusted at rest. This is the pure store-to-store core, reached both by //! the CLI wiring in main.zig (`runPack`) and by the DST/fuzz harnesses that //! exercise the transform in-process; the CLI-layer temp-file/rename plumbing //! stays in main.zig. //! //! In-module file: it reaches `logstore`/`artifact` through relative sibling //! imports (the same way logstore.zig reaches delta/container), not through the //! public `zit` module — a relative import here shares the one module-local copy //! of each dependency rather than pulling a second into a foreign root. const std = @import("std"); const logstore = @import("logstore.zig"); const artifact = @import("artifact.zig"); /// The binary digest width the pack hex helpers round-trip (sha256/sha3-256). const digest_len = 32; /// pack's closed error set: memory, a destination write fault, or a source /// artifact whose reconstructed content does not hash to its name (§7.7) or /// whose frame is otherwise corrupt. pub const PackError = error{ OutOfMemory, Storage, Corrupt }; /// One repack's tally: the artifact count (== the source's content frames), how /// many landed as deltas in the new log, and the on-disk sizes before/after. pub const PackStats = struct { artifacts: usize, deltas: usize, bytes_before: u64, bytes_after: u64, }; /// A source artifact's ordered, bounded base-candidate hints for the repack — a /// check-in manifest's lineage parent (§6.1) or a file blob's same-path /// predecessors (§6.2, nearest first), fed to `putArtifactPacked` ahead of the /// chronological window. Inline fixed buffer (≤ `max_base_candidates`), so the /// hint map holds no per-entry allocation and every fill is bounded. const PriorityHints = struct { buf: [logstore.max_base_candidates]logstore.Rid = undefined, len: u8 = 0, /// The recorded hints in priority order. fn slice(self: *const PriorityHints) []const logstore.Rid { return self.buf[0..self.len]; } /// Append `rid` unless the buffer is full or already holds it (bounded dedup /// — a base offered by two lanes, or a path listing the same blob twice, /// costs no slot). Priority order is preserved: earlier pushes rank higher. fn push(self: *PriorityHints, rid: logstore.Rid) void { std.debug.assert(rid >= 1); // a valid log rid is 1-based if (self.len >= self.buf.len) return; for (self.buf[0..self.len]) |r| if (r == rid) return; self.buf[self.len] = rid; self.len += 1; } }; /// Repack every artifact from `src` into the fresh, empty `dst` (same /// `hash_kind`), choosing each frame's delta base by OUR size-minimizing policy /// instead of trusting the source's stored encoding (§6.1, the fossil /// `extra_deltification` analog). Every content artifact — including a verbatim /// wire delta (`putDeltaContainer`), decoded to full bytes first — is run /// through `pickBase` against its priority hints (a check-in manifest's lineage /// parent §6.1; a file blob's same-path predecessors §6.2, fossil's mlink analog) /// plus the chronological window of already-packed frames, so the sender's base /// choice stops being trusted at rest. Iteration is source offset order, which /// guarantees a chosen base is already present in `dst` before its dependents /// (candidates are always earlier frames, and `delta_of` is a byte offset in the /// NEW file, assigned at write time). The live config survives as exactly one /// frame; superseded config records are dropped (§E). The repository shun table /// survives whole, in persisted order — dropping it would make the set's /// durability claim false the first time anyone packs. Two integrity gates /// bracket the writes: each SOURCE frame is §7.7-verified before it is /// re-encoded, and — MANDATORY (§3) — after the final write every PACKED /// artifact is reconstructed through its NEW chain and re-hashed; any mismatch /// aborts before `commit`, leaving `dst` a discarded temp and `src` untouched. /// `dst` MUST be a just-opened empty log; `src` is never written. Deterministic: /// fixed offset-order iteration and a deterministic `pickBase` make the packed /// bytes a pure function of the source content — so `pack∘pack` reproduces the /// same log. pub fn packLog(gpa: std.mem.Allocator, src: *logstore.LogStore, dst: *logstore.LogStore) PackError!PackStats { // §6.1 base-availability precondition (load-bearing): `dst` MUST be a // just-opened empty log. If it already held frames, the hint translation // `dst.lookup(src.hashOf(sb))` below could resolve a pre-existing unrelated // frame and silently mis-base a re-delta. Assert it before the first write. std.debug.assert(dst.entryCount() == 0); // The live config survives as exactly one frame; every superseded config // record is dropped (the whole of pack's "dead frame" reclaim, §E). if (try readSrcConfig(gpa, src)) |oc_val| { var owned = oc_val; defer owned.deinit(gpa); dst.putConfig(owned.config) catch |e| return storagePutError(e); } // The repository shun table carries across verbatim, in persisted order. // Shun rows are the second never-interned frame kind, so — exactly like the // config record above — they are in neither `ridsInPersistedOrder` nor any // content path below, and a pack that did not re-emit them would silently // DROP the whole set. That is fail-OPEN on the one predicate the set exists // to make durable: the tombstones vanish while the artifacts they name may // survive the repack. Preserving is not the §5 pack FILTER (dropping // shunned content is a separate, later decision) — it is what makes the set // durable across the repo's own compaction at all. That "later decision" is // still later: the artifact loop below reads through the maintenance reader, // so a shunned artifact's FRAME survives this repack exactly like any other, // and only the row travels with it. // // ORDERING IS LOAD-BEARING — this loop MUST precede the artifact loop, and // moving it after would silently change packed OUTPUT rather than fail. // `dst.putArtifactPacked` → `pickBase` probes candidates through // `dst.content`, which is masked, so with the rows already in place a // shunned frame is never chosen as a fresh delta basis in the new // generation (the right answer: a basis whose bytes a reclaim is about to // drop must not acquire new dependents). Copy the rows afterwards and // `pickBase` would happily root new deltas on it. Nothing downstream // notices, which is exactly why the dependency is stated here. for (src.shunList()) |row| { dst.putShun(row.hash, row.reason, row.epoch) catch |e| return storageShunError(e); } // The whole set is in place before the first artifact lands — the ordering // above, checked rather than merely described. std.debug.assert(dst.shunList().len == src.shunList().len); // Artifacts in offset order: every candidate base a frame picks precedes it // in the source, so it is already written into `dst` (its NEW offset known) // before the dependent that names it. const rids = try src.ridsInPersistedOrder(gpa); defer gpa.free(rids); // Priority base hints (source rid → ordered source base rids), from a first // pass over the manifests: a check-in manifest against its primary parent // manifest (§6.1), plus each file blob's same-path predecessors — the §6.2 // mlink analog. These are `pickBase`'s highest-priority candidates; the // chronological window (added by `putArtifactPacked`) fills the rest. Absent ⇒ // the window alone decides. var hints: std.AutoHashMapUnmanaged(logstore.Rid, PriorityHints) = .empty; defer hints.deinit(gpa); try deriveCandidateHints(gpa, src, rids, &hints); var cache = logstore.PlaintextCache.init(); defer cache.deinit(gpa); var deltas: usize = 0; for (rids) |src_rid| { // Non-phantom by construction (`ridsInPersistedOrder` filters phantoms) // and read through the MAINTENANCE reader (`srcContent` — see its note // on why a repack must not read through the shun mask), so content is // never null and the `orelse` is unreachable defensive code rather than // a silent drop. A verbatim wire delta is decoded to full bytes here, // then re-deltified like everything else — its stored base is not // preserved. const content = (try srcContent(gpa, src, src_rid, &cache)) orelse continue; defer gpa.free(content); const digest = src.hashOf(src_rid); // §7.7 L1332/L1336-1338 — the reconstructed bytes MUST hash to the // artifact's name, recomputed BEFORE any frame is written. A lying frame // aborts the pack with the original store untouched. var name_buf: [2 * logstore.max_hash_len]u8 = undefined; const name = digestToWireName(digest, &name_buf); if (!artifact.verify(name, content)) return error.Corrupt; // Priority base hints translated to their NEW dst rids (every hint is an // earlier-offset frame, so it is already written into `dst`). An unheld // hint is dropped. Absent/all-unheld ⇒ the chronological window alone // decides. `putArtifactPacked` owns best-of-N + the accept threshold + // chain-depth policy — pack only offers the ordered hints and the §6.1 // monotonic floor. var pri_buf: [logstore.max_base_candidates]logstore.Rid = undefined; var pri_len: usize = 0; if (hints.get(src_rid)) |ph| { for (ph.slice()) |sb| { if (pri_len >= pri_buf.len) break; if (dst.lookup(src.hashOf(sb))) |db| { pri_buf[pri_len] = db; pri_len += 1; } } } // §6.1 monotonic-shrink guard: the new encoding is written only if it is // strictly smaller than the existing source frame; otherwise pack keeps // that frame verbatim (a compact wire delta fossil chose well is never // replaced by a larger re-encoding). This makes pack non-worsening // frame-by-frame with ONE acknowledged exception: `copySrcFrame`'s §3.3 // deep-chain fallback re-stores a KEPT delta as a full zlib frame when its // base's dst depth reaches the read cap, which can exceed the source // delta's span — reachable only once chains approach `max_delta_chain`. const floor_span = src.frameSpanOf(src_rid); const new_rid = switch (dst.putArtifactPacked(digest, content, pri_buf[0..pri_len], floor_span) catch |e| return storagePutError(e)) { .rewrote => |rid| rid, .kept => try copySrcFrame(gpa, src, dst, src_rid, content), }; if (dst.kindOf(new_rid) == .delta) deltas += 1; } // MANDATORY invariant sweep (§3): reconstruct EVERY packed artifact through // its NEW (possibly re-based) delta chain and re-hash it; a mismatch aborts // before the commit, so the source is never replaced by a store that fails // round-trip. `dst` is a discarded temp on this path. try packVerifyPacked(gpa, dst); dst.commit() catch return error.Storage; // fsync the new log before the caller renames it return .{ .artifacts = rids.len, .deltas = deltas, .bytes_before = src.size(), .bytes_after = dst.size(), }; } /// The §3 post-write invariant sweep: reconstruct every content artifact in the /// freshly written `dst` through its (possibly re-based) delta chain and confirm /// it hashes to its own name. A single mismatch is `error.Corrupt`, aborting the /// pack before its atomic rename — the source store is never replaced by a pack /// that fails byte-exact round-trip. A shared `PlaintextCache` bounds the /// re-reconstruction cost over deep chains. fn packVerifyPacked(gpa: std.mem.Allocator, dst: *logstore.LogStore) PackError!void { var cache = logstore.PlaintextCache.init(); defer cache.deinit(gpa); const rids = try dst.ridsInPersistedOrder(gpa); defer gpa.free(rids); for (rids) |rid| { const content = (try srcContent(gpa, dst, rid, &cache)) orelse continue; defer gpa.free(content); var name_buf: [2 * logstore.max_hash_len]u8 = undefined; const name = digestToWireName(dst.hashOf(rid), &name_buf); if (!artifact.verify(name, content)) return error.Corrupt; } } /// `src.readConfig` narrowed to pack's error set (a config frame that will not /// decode is `Corrupt`, mirroring §7.7's abort-on-corrupt discipline). fn readSrcConfig(gpa: std.mem.Allocator, src: *logstore.LogStore) PackError!?logstore.OwnedConfig { return src.readConfig(gpa) catch |e| switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, error.Corrupt => error.Corrupt, }; } /// `contentUnmasked` (the cached shape) narrowed to pack's error set — the /// MAINTENANCE reader, deliberately, not `contentCached`. /// /// A repack is not a read: it relocates frames inside one repository and shows /// nobody the bytes. The repository shun table masks the rid-keyed readers, so a /// repack that went through `contentCached` would see null for every /// shunned-but-held frame and — via `packLog`'s `orelse continue` — DROP it, /// erasing the artifact and its interned name from the new generation. `lookup` /// and `resolveHexPrefix` would then answer null where they answered a rid, i.e. /// `zit pack` would change what an unrelated verb prints. That is the exact /// invariant the mask exists to protect, and dropping shunned content is a /// separate reclamation decision (§5 pack FILTER) that no draft states and this /// slice has not made. Until it is made deliberately, shunned frames flow /// through the repack untouched, exactly like every other frame. fn srcContent(gpa: std.mem.Allocator, src: *logstore.LogStore, rid: logstore.Rid, cache: *logstore.PlaintextCache) PackError!?[]u8 { return src.contentUnmasked(gpa, rid, cache) catch |e| switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, error.Corrupt => error.Corrupt, }; } /// Re-store `src_rid`'s EXISTING frame into `dst` verbatim — the §6.1 "kept" /// path, taken when no re-encoding beat the source frame's on-disk size. A full /// zlib container is copied byte-for-byte; a wire delta is copied byte-for-byte /// and re-pointed at its base's NEW dst frame (same base content, so the delta /// still reconstructs the same artifact); a raw frame re-stores its plaintext. /// Preserves fossil's compact base choice unbeaten where pack's re-deltify could /// not improve it. Offset order guarantees a delta's base is already packed; a /// base unexpectedly absent falls back to a full zlib store (§3.3 — never a /// dangling delta) rather than corrupt the packed store. fn copySrcFrame( gpa: std.mem.Allocator, src: *logstore.LogStore, dst: *logstore.LogStore, src_rid: logstore.Rid, content: []const u8, ) PackError!logstore.Rid { std.debug.assert(src_rid >= 1); // a valid 1-based source log rid std.debug.assert(content.len <= logstore.max_payload); // reconstructed artifact bytes const digest = src.hashOf(src_rid); // `wireUnmasked` for the same reason `srcContent` reads unmasked: a kept // frame is COPIED, not served. Through the masked `wire` a shunned-but-held // `.zlib`/`.delta` frame would look container-less and be re-stored as a raw // frame — silently inflating the packed log and voiding the §6.1 // monotonic-shrink guarantee for that frame. const maybe_wire = src.wireUnmasked(gpa, src_rid) catch |e| switch (e) { error.OutOfMemory => return error.OutOfMemory, error.Storage => return error.Storage, error.Corrupt => return error.Corrupt, }; // A `.raw` frame carries no stored container: re-store the plaintext as raw. var w = maybe_wire orelse return dst.put(digest, content) catch |e| return storagePutError(e); defer w.deinit(gpa); switch (w) { .full => |c| return dst.putContainer(digest, c) catch |e| return storagePutError(e), .delta => |d| { const base_rid = dst.lookup(d.baseHash()) orelse return dst.putZlib(digest, content) catch |e| return storagePutError(e); // Chain-depth safety: a verbatim copy re-links to the base's NEW rid, // whose dst depth can EXCEED the source's — pack may re-deltify a // source-full base into a delta (depth up to `delta_chain_write_max`), // so a kept delta stacked on it lands deeper than it was at the source. // Copy only while the base stays below the READ bound so the packed // chain still resolves within `max_delta_chain`; a base at/over the // bound falls back to full form, exactly as the clone persist path does // for a retained foreign chain (§3.3). Without this the post-write // invariant sweep (§3) would reject an over-deep chain as corrupt. if (dst.depthOf(base_rid) >= logstore.max_delta_chain) { return dst.putZlib(digest, content) catch |e| return storagePutError(e); } return dst.putDeltaContainer(digest, base_rid, d.container) catch |e| return storagePutError(e); }, } } /// Map a `putArtifact`/`putConfig` failure into pack's error set. fn storagePutError(e: logstore.PutError) PackError { return switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, }; } /// Map a `putShun` failure into pack's error set. Every row re-emitted here came /// out of `src.shunList()`, so it has already satisfied both of `putShun`'s /// input rules — `scan` rejects a shun frame whose key is not a complete digest, /// and `parseShun` caps the reason at `max_shun_reason` — which makes `BadKey` /// and `ReasonTooLong` reachable only if the source's set disagrees with the /// rules its own reader enforces. That is source corruption, and it fails the /// repack rather than quietly dropping a tombstone. fn storageShunError(e: logstore.ShunError) PackError { return switch (e) { error.OutOfMemory => error.OutOfMemory, error.Storage => error.Storage, error.BadKey, error.ReasonTooLong => error.Corrupt, }; } /// Walk the source manifests once, filling `hints` with each artifact's ordered /// base candidates: /// * a check-in manifest → its primary parent manifest (§6.1 lineage); /// * a file blob → its same-path predecessors, nearest first (§6.2, fossil's /// mlink-biased `N_NEIGHBOR` analog — rebuild.c:501,508). /// Same-path knowledge is derived HERE, inside pack (the manifest-parsing layer), /// and handed to `pickBase` as plain `[]Rid`: no path concept leaks into the /// logstore policy. Every recorded predecessor precedes its blob in offset order /// (the two-pass offset sort guarantees it), so a chosen base is always already /// written into `dst` before its dependent. A non-manifest / unparseable artifact /// contributes no lineage hint. Only memory/storage/corrupt frame faults escape. fn deriveCandidateHints( gpa: std.mem.Allocator, src: *logstore.LogStore, rids: []const logstore.Rid, hints: *std.AutoHashMapUnmanaged(logstore.Rid, PriorityHints), ) PackError!void { // Fresh map in, filled here: the caller hands a just-initialized `.empty` // hint map so every entry below is this walk's own. std.debug.assert(hints.count() == 0); // path → the distinct file-blob rids ever stored at that path, accumulated in // manifest-walk order (re-sorted to offset order in pass 2). Keys are gpa-owned // dups of the manifest arena's filename bytes; freed with the map below. var paths: std.StringHashMapUnmanaged(std.ArrayListUnmanaged(logstore.Rid)) = .empty; defer { var it = paths.iterator(); while (it.next()) |e| { e.value_ptr.deinit(gpa); gpa.free(e.key_ptr.*); } paths.deinit(gpa); } // Pass 1: manifest → lineage parent, and accumulate path → blob rids. var cache = logstore.PlaintextCache.init(); defer cache.deinit(gpa); for (rids) |m_rid| { const bytes = (try srcContent(gpa, src, m_rid, &cache)) orelse continue; defer gpa.free(bytes); // Only a check-in manifest carries F/P lineage; a blob (or a control // artifact) fails the parse or is a different kind and contributes none. // Read path: pack reads stored (fossil-origin) manifests, so it tolerates // the legacy F-card trailing separator. var loaded = artifact.parseForImport(gpa, bytes) catch |e| switch (e) { error.OutOfMemory => return error.OutOfMemory, else => continue, }; defer loaded.deinit(gpa); const m = &loaded.manifest; if (m.kind != .manifest) continue; // manifest → primary parent manifest (§6.1). The parent frame precedes // this one in offset order, so it is packed before it. if (primaryParentRid(src, m)) |parent_rid| { try pushHint(gpa, hints, m_rid, parent_rid); } // §6.2: record each F-card's blob under its path. A delete F-card (no // hash), an unresolvable hash, or a phantom blob contributes nothing — // a phantom is skipped so pass 2's offset sort never queries a frameless // rid. for (m.f) |fc| { const bh = fc.hash orelse continue; const digest = hexToDigest(bh) orelse continue; const blob_rid = src.lookup(&digest) orelse continue; if (src.isPhantom(blob_rid)) continue; try recordPathBlob(gpa, &paths, fc.filename, blob_rid); } } // Pass 2: per path, sort its versions by offset and give each blob its nearest // same-path predecessors (offset below), nearest first — ahead of whatever the // chronological window later adds. var vit = paths.valueIterator(); while (vit.next()) |list| { std.mem.sort(logstore.Rid, list.items, src, blobOffsetLessThan); // A path that reverts to a byte-identical earlier blob (A→B→A) records the // SAME content-addressed rid more than once, non-consecutively — // `recordPathBlob` dedups only the consecutive run, so a revert slips a // duplicate past it. The offset sort makes those duplicates adjacent (an // identical rid has an identical offset), so one linear pass compacts // `versions` to its DISTINCT rids. Without it the predecessor walk below // would offer a blob as its OWN same-path base: equal offsets fail the // strict offset-below invariant (:362) and `pushHint`'s `rid != base` // assert (:379) — a blob is never its own predecessor. const versions = dedupSortedRids(list.items); for (versions, 0..) |blob_rid, k| { // Nearest predecessor first: k-1, k-2, … (all offset-below `blob_rid`). // Bounded to `max_base_candidates`: only that many hints are ever kept // (`PriorityHints.push` no-ops past the buffer), so a deep same-path // history costs O(N·5), never O(N²). var j: usize = k; var taken: usize = 0; while (j > 0 and taken < logstore.max_base_candidates) { j -= 1; taken += 1; // Load-bearing invariant: an offset-sorted `versions` puts every // predecessor (index below `k`) strictly earlier in the log than // `blob_rid`, so a chosen base is always already packed into `dst` // before its dependent. Assert it at the point of use. std.debug.assert(src.offsetOf(versions[j]) < src.offsetOf(blob_rid)); try pushHint(gpa, hints, blob_rid, versions[j]); } } } } /// Append `base` to `rid`'s ordered hint list (creating it on first use). The /// list is bounded and self-deduping (`PriorityHints.push`), so this is a no-op /// once the buffer is full — the loops that call it need no separate cap. fn pushHint( gpa: std.mem.Allocator, hints: *std.AutoHashMapUnmanaged(logstore.Rid, PriorityHints), rid: logstore.Rid, base: logstore.Rid, ) PackError!void { std.debug.assert(rid >= 1 and base >= 1); // both are valid 1-based log rids std.debug.assert(rid != base); // a frame is never its own base hint const gop = hints.getOrPut(gpa, rid) catch return error.OutOfMemory; if (!gop.found_existing) gop.value_ptr.* = .{}; gop.value_ptr.push(base); } /// Record `blob_rid` under `path` in `paths`, owning a dup of the filename bytes /// on first sight of a path. A file unchanged across consecutive check-ins /// references the same blob; that run is deduped here (only a change from the /// last-recorded version appends), and `PriorityHints.push` dedups any residual /// repeat. Only OOM escapes. fn recordPathBlob( gpa: std.mem.Allocator, paths: *std.StringHashMapUnmanaged(std.ArrayListUnmanaged(logstore.Rid)), path: []const u8, blob_rid: logstore.Rid, ) PackError!void { std.debug.assert(path.len > 0); // an F-card filename is never empty std.debug.assert(blob_rid >= 1); // a valid 1-based log rid const gop = paths.getOrPut(gpa, path) catch return error.OutOfMemory; if (!gop.found_existing) { // The slot's key is still the caller's borrowed `path`. Own it before any // later free can touch it; on a dupe OOM, drop the half-inserted slot so // the map's teardown never frees borrowed bytes or reads an undefined list. const owned = gpa.dupe(u8, path) catch { std.debug.assert(paths.remove(path)); return error.OutOfMemory; }; gop.key_ptr.* = owned; gop.value_ptr.* = .empty; } const list = gop.value_ptr; if (list.items.len > 0 and list.items[list.items.len - 1] == blob_rid) return; list.append(gpa, blob_rid) catch return error.OutOfMemory; } /// Compact an offset-sorted rid slice to its DISTINCT rids IN PLACE, returning /// the leading distinct prefix. A same-path history that reverts to a /// byte-identical earlier blob (A→B→A) records one content-addressed rid more /// than once; the offset sort makes those duplicates adjacent (an identical rid /// has an identical offset), so a single linear pass drops them. Keeps the pass-2 /// predecessor walk from ever offering a blob as its own same-path base — a blob /// is never its own predecessor. fn dedupSortedRids(sorted: []logstore.Rid) []logstore.Rid { if (sorted.len == 0) return sorted; var w: usize = 1; // count of distinct rids kept in the leading prefix var i: usize = 1; while (i < sorted.len) : (i += 1) { std.debug.assert(sorted[i] >= 1); // a valid 1-based log rid if (sorted[i] != sorted[w - 1]) { sorted[w] = sorted[i]; w += 1; } } return sorted[0..w]; } /// Offset order over two non-phantom blob rids — pass 2's sort key. Ascending /// offset means earlier-written first, so a blob's predecessors (positions below /// it) are exactly the same-path versions already packed when it is reached. fn blobOffsetLessThan(src: *logstore.LogStore, a: logstore.Rid, b: logstore.Rid) bool { // Contract: two non-phantom blob rids. `offsetOf` re-asserts range and // non-phantom internally; state the boundary contract here explicitly. std.debug.assert(a >= 1 and b >= 1); std.debug.assert(!src.isPhantom(a) and !src.isPhantom(b)); return src.offsetOf(a) < src.offsetOf(b); } /// The log rid of a manifest's primary (first) parent, or null when it is a /// root or the parent is not held. `parents` is the space-separated P-card /// argument (artifact §4.7.13); the first token is the merge-primary parent. fn primaryParentRid(src: *logstore.LogStore, m: *const artifact.Manifest) ?logstore.Rid { if (m.p.len == 0) return null; var it = m.p[0].hashes(); const first = it.next() orelse return null; const digest = hexToDigest(first) orelse return null; return src.lookup(&digest); } /// Decodes a 64-hex artifact name into its 32-byte binary digest — the log-frame /// key. Returns null for a non-64-hex string, so a caller maps it to a corrupt /// diagnostic rather than trapping. Byte-identical to main.zig's `hexToDigest`; /// pack keeps its own copy so it needs no import above the store layer. fn hexToDigest(hex: []const u8) ?[digest_len]u8 { if (hex.len != digest_len * 2) return null; var d: [digest_len]u8 = undefined; _ = std.fmt.hexToBytes(&d, hex) catch return null; return d; } /// Lowercase-hex-encodes a raw binary `digest` into `out`, returning the used /// prefix — the log-frame key's wire NAME (sync §3.3). Byte-identical to /// main.zig's `digestToWireName`. fn digestToWireName(digest: []const u8, out: *[2 * digest_len]u8) []const u8 { std.debug.assert(digest.len <= digest_len); const hexdigits = "0123456789abcdef"; for (digest, 0..) |b, i| { out[2 * i] = hexdigits[b >> 4]; out[2 * i + 1] = hexdigits[b & 0x0f]; } return out[0 .. 2 * digest.len]; } // --------------------------------------------------------------------------- // Tests. The broad pack-transform coverage (content equality, re-deltification, // config survival) lives with the CLI wiring in cmd/sync.zig; what belongs HERE // is the property that has no other home — that pack preserves the frame kinds // it does not rewrite. // --------------------------------------------------------------------------- const storage = @import("storage.zig"); test "pack: the repository shun table survives a repack" { // Shun rows are never interned, so they are in neither `readSrcConfig` nor // `ridsInPersistedOrder` — the two sources `packLog` rebuilds `dst` from. // A pack that did not re-emit them would silently DROP the entire durable // set: `zit pack` writes a new generation and swaps it in, so the // tombstones would be gone for good while the artifacts they name may // survive the repack. Fail-open on exactly the predicate the set exists to // make durable, with no error and no warning. const gpa = std.testing.allocator; var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); const io = std.testing.io; const first = "s" ** 32; const second = "t" ** 20; // the other complete-name width const sfile = try tmp.dir.createFile(io, "src", .{ .read = true }); defer sfile.close(io); var sfs = storage.FileStorage.init(io, sfile, 0); var src = try logstore.LogStore.open(gpa, sfs.storageFile(), 0); defer src.deinit(gpa); // A real content-addressed artifact: `packLog` §7.7-verifies every source // frame, so the store must hold a genuinely named one for the shun rows to // be preserved ALONGSIDE content rather than in a degenerate empty pack. const held = "held content that the pack will reconstruct and re-hash"; var held_digest: [digest_len]u8 = undefined; std.crypto.hash.sha3.Sha3_256.hash(held, &held_digest, .{}); _ = try src.putArtifact(&held_digest, held, null); try src.putShun(first, "takedown notice 4711", 1753000000); try src.putShun(second, "", 1753000001); try src.commit(); const dfile = try tmp.dir.createFile(io, "packed", .{ .read = true, .truncate = true }); defer dfile.close(io); var dfs = storage.FileStorage.init(io, dfile, 0); var dst = try logstore.LogStore.open(gpa, dfs.storageFile(), src.hash_kind); defer dst.deinit(gpa); _ = try packLog(gpa, &src, &dst); // Present in the packed generation, in persisted order, fields intact. try std.testing.expect(dst.isShunned(first)); try std.testing.expect(dst.isShunned(second)); const list = dst.shunList(); try std.testing.expectEqual(@as(usize, 2), list.len); try std.testing.expectEqualStrings(first, list[0].hash); try std.testing.expectEqualStrings("takedown notice 4711", list[0].reason); try std.testing.expectEqual(@as(i64, 1753000000), list[0].epoch); try std.testing.expectEqualStrings(second, list[1].hash); try std.testing.expectEqual(@as(i64, 1753000001), list[1].epoch); // ...and still there once the packed file is reopened from its bytes. var rfs = storage.FileStorage.init(io, dfile, dst.size()); var reopened = try logstore.LogStore.open(gpa, rfs.storageFile(), 0); defer reopened.deinit(gpa); try std.testing.expectEqual(@as(usize, 2), reopened.shunList().len); try std.testing.expect(reopened.isShunned(first)); // A tombstone is still not content: it takes no rid in the packed log. try std.testing.expect(reopened.lookup(first) == null); } test "pack: a shunned artifact the store still HOLDS survives the repack" { // The sibling test above shuns two names the store does not hold, so it // says nothing about the case that actually has a frame to lose. This one // does, and it is the case where the read mask nearly turned `zit pack` // into a reclaimer by accident. // // `ridsInPersistedOrder` filters phantoms, and a shunned artifact is NOT a // phantom (its frame exists) — so a shunned-but-held rid is in the list // `packLog` walks. Had that walk read through the masked `contentCached`, // the `orelse continue` would have skipped it and neither its frame nor its // interned NAME would reach the packed generation: `lookup` and // `resolveHexPrefix` would start answering null where they answered a rid, // i.e. `zit pack` would change what an unrelated verb prints. That is the // invariant the mask exists to protect, inverted. Dropping shunned content // IS a decision someone may make later (the §5 pack filter); it is not one a // read guard gets to make silently, so pack reads unmasked and this pins it. const gpa = std.testing.allocator; var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); const io = std.testing.io; const sfile = try tmp.dir.createFile(io, "src", .{ .read = true }); defer sfile.close(io); var sfs = storage.FileStorage.init(io, sfile, 0); var src = try logstore.LogStore.open(gpa, sfs.storageFile(), 0); defer src.deinit(gpa); // Two artifacts: one shunned, one not, so a pack that dropped EVERYTHING // could not pass by accident. Both long enough that `putArtifact` stores a // zlib container rather than a raw frame — the masked `wire` would answer // null for the shunned one and `copySrcFrame` would silently downgrade it. const shunned_body = "content an operator was ordered to stop serving, still physically present in the log " ** 4; const kept_body = "ordinary content with no tombstone against it, packed the same way it always was " ** 4; var shunned_digest: [digest_len]u8 = undefined; var kept_digest: [digest_len]u8 = undefined; std.crypto.hash.sha3.Sha3_256.hash(shunned_body, &shunned_digest, .{}); std.crypto.hash.sha3.Sha3_256.hash(kept_body, &kept_digest, .{}); const shunned_rid = try src.putArtifact(&shunned_digest, shunned_body, null); _ = try src.putArtifact(&kept_digest, kept_body, null); try src.putShun(&shunned_digest, "takedown notice 4712", 1753000002); try src.commit(); // The premise: the frame IS there and the mask IS on, or the assertions // below would hold for an uninteresting reason. try std.testing.expect(!src.isPhantom(shunned_rid)); try std.testing.expectEqual(@as(?[]u8, null), try src.content(gpa, shunned_rid)); const dfile = try tmp.dir.createFile(io, "packed", .{ .read = true, .truncate = true }); defer dfile.close(io); var dfs = storage.FileStorage.init(io, dfile, 0); var dst = try logstore.LogStore.open(gpa, dfs.storageFile(), src.hash_kind); defer dst.deinit(gpa); const stats = try packLog(gpa, &src, &dst); var rfs = storage.FileStorage.init(io, dfile, dst.size()); var reopened = try logstore.LogStore.open(gpa, rfs.storageFile(), 0); defer reopened.deinit(gpa); // The count pack REPORTS and the count it WROTE are the same number. // `stats.artifacts` alone cannot say that: it is `rids.len`, captured from // the SOURCE before the loop runs, so it stays 2 even if the loop dropped // both. Read the written count back out of the packed generation and compare // the two. const packed_rids = try reopened.ridsInPersistedOrder(gpa); defer gpa.free(packed_rids); try std.testing.expectEqual(@as(usize, 2), packed_rids.len); try std.testing.expectEqual(packed_rids.len, stats.artifacts); // THE PIN: the name still resolves in the packed generation... const packed_rid = reopened.lookup(&shunned_digest) orelse return error.ShunnedArtifactDroppedByPack; try std.testing.expect(!reopened.isPhantom(packed_rid)); // ...as a CONTAINER, not a raw frame. The bodies above are long enough that // `putArtifact` stored zlib; had `copySrcFrame` read the masked `wire` it // would have seen a container-less frame and re-stored the plaintext raw — // a silent inflation that voids §6.1 monotonic-shrink for this frame and // that every other assertion in this test survives. try std.testing.expectEqual(logstore.FrameKind.zlib, reopened.kindOf(packed_rid)); // ...the tombstone travelled with it, so the artifact still reads as // absent (reclamation stays invisible — pack changed no verb's answer)... try std.testing.expect(reopened.isShunned(&shunned_digest)); try std.testing.expectEqual(@as(?[]u8, null), try reopened.content(gpa, packed_rid)); // ...and the BYTES are genuinely in the packed file, not merely a name: the // maintenance reader reconstructs them and they still hash to their name. const carried = (try reopened.contentUnmasked(gpa, packed_rid, null)).?; defer gpa.free(carried); try std.testing.expectEqualStrings(shunned_body, carried); // The unshunned neighbour is untouched, through the ordinary reader. const kept_rid = reopened.lookup(&kept_digest).?; const kept_out = (try reopened.content(gpa, kept_rid)).?; defer gpa.free(kept_out); try std.testing.expectEqualStrings(kept_body, kept_out); } test "pack: a delta chain ROOTED ON a shunned base survives the repack" { // The sibling test above packs two INDEPENDENT artifacts, so it never // exercises the interaction this one is about: what a repack does to a // delta whose basis is shunned. Three mechanisms have to cooperate, and // none of them is exercised anywhere else. // // 1. `packLog` copies the shun rows into `dst` BEFORE the artifact loop, // so `dst.putArtifactPacked` → `pickBase` — which probes candidates // through the masked `dst.content` — cannot pick the shunned base for // a FRESH delta. It reads null and is skipped like a phantom. // 2. Because no re-encoding beat the source's compact delta frame, the // §6.1 monotonic-shrink guard answers `.kept` and `copySrcFrame` copies // the delta container verbatim, RELINKING it through the unmasked // `dst.lookup(d.baseHash())` — which resolves, because `lookup` is not // masked and the base's frame was packed. // 3. The packed delta then reconstructs through `contentAtOffset`, which // reaches its basis by BYTE OFFSET and so never re-enters the rid-keyed // mask — sync §7.7 L1444-1450's "content still held locally MAY serve // as the delta basis", holding across a whole-store rewrite. // // Break any one of the three and this test fails; the isolated `pickBase` // pin in logstore_test.zig catches none of them. const gpa = std.testing.allocator; var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); const io = std.testing.io; const sfile = try tmp.dir.createFile(io, "src", .{ .read = true }); defer sfile.close(io); var sfs = storage.FileStorage.init(io, sfile, 0); var src = try logstore.LogStore.open(gpa, sfs.storageFile(), 0); defer src.deinit(gpa); // Deliberately incompressible bodies: a delta of the derived body against // the base is a handful of bytes, while a zlib re-encoding of it is larger // than the whole source delta FRAME. That is what forces the §6.1 guard down // the `.kept` → `copySrcFrame` path — the one under test. Compressible text // would let the repack re-encode the derived body as a full zlib frame and // the delta chain would never reach `copySrcFrame` at all. var base_body: [1024]u8 = undefined; var seed: u32 = 0x2545f491; for (&base_body) |*b| { seed = seed *% 1664525 +% 1013904223; b.* = @truncate(seed >> 24); } var derived_body: [1024]u8 = base_body; derived_body[1000] ^= 0xff; // one byte apart: a tiny delta, a big zlib var base_digest: [digest_len]u8 = undefined; var derived_digest: [digest_len]u8 = undefined; std.crypto.hash.sha3.Sha3_256.hash(&base_body, &base_digest, .{}); std.crypto.hash.sha3.Sha3_256.hash(&derived_body, &derived_digest, .{}); const base_rid = try src.putArtifact(&base_digest, &base_body, null); const derived_rid = try src.putArtifact(&derived_digest, &derived_body, base_rid); // The shun row goes in LAST, on purpose: shunning first would mask the base // from the source store's own `pickBase` and there would be no delta to // carry. This is the real-world order anyway — an operator shuns content the // repository has already been storing and deltifying for some time. try src.putShun(&base_digest, "takedown notice 4713", 1753000003); try src.commit(); // The premises, or the assertions below would hold for uninteresting // reasons: the derived frame really is a delta, the base really is held and // masked, and the delta really does still reconstruct over a masked basis. try std.testing.expectEqual(logstore.FrameKind.delta, src.kindOf(derived_rid)); try std.testing.expect(!src.isPhantom(base_rid)); try std.testing.expectEqual(@as(?[]u8, null), try src.content(gpa, base_rid)); const src_derived = (try src.content(gpa, derived_rid)).?; defer gpa.free(src_derived); try std.testing.expectEqualSlices(u8, &derived_body, src_derived); const dfile = try tmp.dir.createFile(io, "packed", .{ .read = true, .truncate = true }); defer dfile.close(io); var dfs = storage.FileStorage.init(io, dfile, 0); var dst = try logstore.LogStore.open(gpa, dfs.storageFile(), src.hash_kind); defer dst.deinit(gpa); _ = try packLog(gpa, &src, &dst); var rfs = storage.FileStorage.init(io, dfile, dst.size()); var reopened = try logstore.LogStore.open(gpa, rfs.storageFile(), 0); defer reopened.deinit(gpa); // The base survived as a frame, still masked, still tombstoned. const packed_base = reopened.lookup(&base_digest) orelse return error.ShunnedBasisDroppedByPack; try std.testing.expect(!reopened.isPhantom(packed_base)); try std.testing.expect(reopened.isShunned(&base_digest)); try std.testing.expectEqual(@as(?[]u8, null), try reopened.content(gpa, packed_base)); // THE PIN: the dependent is STILL A DELTA — the chain was relinked, not // flattened into a full frame — and it still reconstructs byte-for-byte // through a basis that reads as absent by name. const packed_derived = reopened.lookup(&derived_digest) orelse return error.DeltaOnShunnedBasisDroppedByPack; try std.testing.expectEqual(logstore.FrameKind.delta, reopened.kindOf(packed_derived)); const out = (try reopened.content(gpa, packed_derived)).?; defer gpa.free(out); try std.testing.expectEqualSlices(u8, &derived_body, out); }