Artifact [f49f9de3c1]

Artifact f49f9de3c16b86120fe3fc1f15197ea0347b946ad21768f297248c375a6e0adb:

• File src/graveyard.zig — part of check-in [8536f59fba] at 2026-08-17 19:00:15 on branch trunk — zit purge: recoverable removal of leaf check-ins (#87)

  Removes a check-in and the blobs only it introduced, into a local graveyard that purge undo restores and purge obliterate empties.

  The drop set is (seed + reachable(seed)) minus reachable(everything retained), so a blob a surviving check-in still names is never freed -- dropping it would create a phantom rather than reclaim anything. Only leaves go, judged over the whole named set: purging a parent alongside its child is accepted, purging it alone is refused.

  Reuses shun's rewriteAndSwap and records no tombstone: a purge is local, so content that already synced comes back from a peer. The help says so and points at shun. (user: dmestas, size: 10112) [annotate] [blame] [check-ins using]

//! #87 — the purge graveyard: removed artifacts, kept recoverable.
//!
//! `zit shun` is permanent and PROPAGATES — its table travels to clones so a
//! peer can never re-offer what an operator ordered removed. That is the right
//! tool once content has escaped, and the wrong one for the ordinary accident:
//! a `zit add .` that swept in a build tree, noticed before anyone else has it.
//!
//! Fossil draws exactly that line with `fossil purge`, whose removed content
//! goes to a graveyard that `purge undo` can restore and `purge obliterate`
//! empties for good. This is that graveyard.
//!
//! It is LOCAL and DISPOSABLE, like the stash and the undo journal: never an
//! artifact, never synced, and losing it costs recoverability rather than data
//! — the purge itself already happened. That locality is also what makes purge
//! honest about its limits: a purge says nothing to a peer that already holds
//! the content, which is why the help points at `shun` for that case.
//!
//! Format: `magic(8) | fmt(1) | count u32 | event... | crc32 le(4)`, crc over
//! all preceding bytes. An event is
//! `id u32 | when i64 | reason_len u16 | reason | artifact_count u32 | artifact...`,
//! and an artifact is `hash_len u8 | hash | bytes_len u32 | bytes`. Every length
//! is bounds-checked against the remaining input before use, consumption must be
//! exact, and the crc must match; any violation is `error.Corrupt` and leaves
//! the file untouched — the undo journal's discipline, for the same reason.

const std = @import("std");

pub const filename: []const u8 = ".zit-graveyard";

const magic: [8]u8 = .{ 'z', 'i', 't', 'g', 'r', 'a', 'v', 'e' };
const fmt_version: u8 = 1;

/// TigerStyle bounds. A purge that names more artifacts than this is a repack,
/// not an accident recovery, and the operator should reach for `shun`.
pub const max_events: usize = 256;
pub const max_artifacts_per_event: usize = 1 << 20;
pub const max_reason_len: usize = 256;
/// The whole graveyard is read into memory to rewrite it, so it carries a
/// stated ceiling rather than growing until a read fails.
pub const max_file_bytes: usize = 2 << 30;

pub const Error = error{ Storage, Corrupt, OutOfMemory, NotFound, Full };

pub const Artifact = struct {
    hash: []const u8,
    bytes: []const u8,
};

pub const Event = struct {
    id: u32,
    when: i64,
    reason: []const u8,
    artifacts: []const Artifact,

    /// Total bytes this event is holding, for `list` — the number an operator
    /// weighs when deciding whether to obliterate.
    pub fn size(self: Event) u64 {
        var total: u64 = 0;
        for (self.artifacts) |a| total += a.bytes.len;
        return total;
    }
};

/// Every event currently held. Arena-owned; the caller frees the arena.
pub fn read(a: std.mem.Allocator, io: std.Io, root: std.Io.Dir) Error![]Event {
    const raw = root.readFileAlloc(io, filename, a, .limited(max_file_bytes)) catch |e| switch (e) {
        error.FileNotFound => return &.{},
        error.OutOfMemory => return error.OutOfMemory,
        else => return error.Storage,
    };
    if (raw.len == 0) return &.{};
    return parse(a, raw);
}

fn parse(a: std.mem.Allocator, raw: []const u8) Error![]Event {
    if (raw.len < magic.len + 1 + 4 + 4) return error.Corrupt;
    if (!std.mem.eql(u8, raw[0..magic.len], &magic)) return error.Corrupt;
    if (raw[magic.len] != fmt_version) return error.Corrupt;

    const body = raw[0 .. raw.len - 4];
    const want = std.mem.readInt(u32, raw[raw.len - 4 ..][0..4], .little);
    if (std.hash.Crc32.hash(body) != want) return error.Corrupt;

    var at: usize = magic.len + 1;
    const count = std.mem.readInt(u32, body[at..][0..4], .little);
    at += 4;
    if (count > max_events) return error.Corrupt;

    const events = try a.alloc(Event, count);
    var i: usize = 0;
    while (i < count) : (i += 1) {
        if (body.len - at < 4 + 8 + 2) return error.Corrupt;
        const id = std.mem.readInt(u32, body[at..][0..4], .little);
        at += 4;
        const when = std.mem.readInt(i64, body[at..][0..8], .little);
        at += 8;
        const rlen = std.mem.readInt(u16, body[at..][0..2], .little);
        at += 2;
        if (rlen > max_reason_len or body.len - at < rlen) return error.Corrupt;
        const reason = body[at..][0..rlen];
        at += rlen;

        if (body.len - at < 4) return error.Corrupt;
        const acount = std.mem.readInt(u32, body[at..][0..4], .little);
        at += 4;
        if (acount > max_artifacts_per_event) return error.Corrupt;
        const arts = try a.alloc(Artifact, acount);
        var j: usize = 0;
        while (j < acount) : (j += 1) {
            if (body.len - at < 1) return error.Corrupt;
            const hlen = body[at];
            at += 1;
            if (hlen == 0 or body.len - at < hlen) return error.Corrupt;
            const hash = body[at..][0..hlen];
            at += hlen;
            if (body.len - at < 4) return error.Corrupt;
            const blen = std.mem.readInt(u32, body[at..][0..4], .little);
            at += 4;
            if (body.len - at < blen) return error.Corrupt;
            arts[j] = .{ .hash = hash, .bytes = body[at..][0..blen] };
            at += blen;
        }
        events[i] = .{ .id = id, .when = when, .reason = reason, .artifacts = arts };
    }
    // Consumption must be exact: trailing bytes mean this is not the file we
    // think it is, and guessing about a recovery store is how recovery fails.
    if (at != body.len) return error.Corrupt;
    return events;
}

/// Rewrite the graveyard to exactly `events`. Atomic (write-temp, fsync,
/// rename), the same sequence every durable control record here uses; an empty
/// set removes the file so a repository with nothing buried carries nothing.
pub fn write(gpa: std.mem.Allocator, io: std.Io, root: std.Io.Dir, events: []const Event) Error!void {
    if (events.len > max_events) return error.Full;
    if (events.len == 0) {
        root.deleteFile(io, filename) catch {};
        return;
    }
    var buf: std.ArrayList(u8) = .empty;
    defer buf.deinit(gpa);

    try buf.appendSlice(gpa, &magic);
    try buf.append(gpa, fmt_version);
    try appendInt(gpa, &buf, u32, @intCast(events.len));
    for (events) |ev| {
        try appendInt(gpa, &buf, u32, ev.id);
        try appendInt(gpa, &buf, i64, ev.when);
        try appendInt(gpa, &buf, u16, @intCast(@min(ev.reason.len, max_reason_len)));
        try buf.appendSlice(gpa, ev.reason[0..@min(ev.reason.len, max_reason_len)]);
        try appendInt(gpa, &buf, u32, @intCast(ev.artifacts.len));
        for (ev.artifacts) |art| {
            try buf.append(gpa, @intCast(art.hash.len));
            try buf.appendSlice(gpa, art.hash);
            try appendInt(gpa, &buf, u32, @intCast(art.bytes.len));
            try buf.appendSlice(gpa, art.bytes);
        }
    }
    try appendInt(gpa, &buf, u32, std.hash.Crc32.hash(buf.items));

    var af = root.createFileAtomic(io, filename, .{ .replace = true }) catch return error.Storage;
    defer af.deinit(io);
    af.file.writePositionalAll(io, buf.items, 0) catch return error.Storage;
    af.file.sync(io) catch return error.Storage; // fsync before the rename
    af.replace(io) catch return error.Storage;
}

fn appendInt(gpa: std.mem.Allocator, buf: *std.ArrayList(u8), comptime T: type, v: T) Error!void {
    var tmp: [@sizeOf(T)]u8 = undefined;
    std.mem.writeInt(T, &tmp, v, .little);
    try buf.appendSlice(gpa, &tmp);
}

/// The next unused event id: one past the highest held, so an id is never
/// reused even after the event bearing it is obliterated. `purge undo 3` must
/// never mean a different purge than it did yesterday.
pub fn nextId(events: []const Event) u32 {
    var high: u32 = 0;
    for (events) |ev| high = @max(high, ev.id);
    return high + 1;
}

test "graveyard: an event round-trips through write and read" {
    const gpa = std.testing.allocator;
    const io = std.testing.io;
    var tmp = std.testing.tmpDir(.{});
    defer tmp.cleanup();

    const arts = [_]Artifact{
        .{ .hash = "aa" ** 32, .bytes = "the first buried artifact" },
        .{ .hash = "bb" ** 32, .bytes = "" }, // an empty artifact is legal
    };
    const evs = [_]Event{.{ .id = 7, .when = 1234567890, .reason = "swept in a build tree", .artifacts = &arts }};
    try write(gpa, io, tmp.dir, &evs);

    var arena = std.heap.ArenaAllocator.init(gpa);
    defer arena.deinit();
    const back = try read(arena.allocator(), io, tmp.dir);
    try std.testing.expectEqual(@as(usize, 1), back.len);
    try std.testing.expectEqual(@as(u32, 7), back[0].id);
    try std.testing.expectEqualStrings("swept in a build tree", back[0].reason);
    try std.testing.expectEqual(@as(usize, 2), back[0].artifacts.len);
    try std.testing.expectEqualStrings("the first buried artifact", back[0].artifacts[0].bytes);
    try std.testing.expectEqual(@as(u64, 25), back[0].size());
    // Ids never reuse, so the next one clears the highest held.
    try std.testing.expectEqual(@as(u32, 8), nextId(back));
}

test "graveyard: an absent file is empty, and a damaged one is Corrupt not empty" {
    const gpa = std.testing.allocator;
    const io = std.testing.io;
    var tmp = std.testing.tmpDir(.{});
    defer tmp.cleanup();

    var arena = std.heap.ArenaAllocator.init(gpa);
    defer arena.deinit();
    // Nothing buried: an empty set, never an error — the state of every
    // repository that has not purged.
    try std.testing.expectEqual(@as(usize, 0), (try read(arena.allocator(), io, tmp.dir)).len);

    // A damaged graveyard must NOT read as "nothing buried": that would turn a
    // recovery store into a silent loss exactly when it is needed.
    const evs = [_]Event{.{ .id = 1, .when = 0, .reason = "r", .artifacts = &.{} }};
    try write(gpa, io, tmp.dir, &evs);
    var f = try tmp.dir.openFile(io, filename, .{ .mode = .read_write });
    defer f.close(io);
    try f.writePositionalAll(io, "X", magic.len + 1); // corrupt the count
    try std.testing.expectError(error.Corrupt, read(arena.allocator(), io, tmp.dir));
}