//! 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). 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);
}
// 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),
// so content is never null. 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,
};
}
/// `contentCached` narrowed to pack's error set.
fn srcContent(gpa: std.mem.Allocator, src: *logstore.LogStore, rid: logstore.Rid, cache: *logstore.PlaintextCache) PackError!?[]u8 {
return src.contentCached(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);
const maybe_wire = src.wire(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,
};
}
/// 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];
}