Skip to content
zit Artifact [8c91a006b5]
Login

Artifact [8c91a006b5]

Check-ins Using Download Hex

Artifact 8c91a006b50ffc126a6b91794c73baf1f184579e103e83dc0d2d63ae57f4f4b1:

//! The `.zit-precedent` sidecar — remembered conflict resolutions, replayed
//! when the same conflict recurs (`zit precedent`, alias `zit rerere`; #103).
//!
//! Local by construction: never an artifact, never synced, invisible to fossil.
//! Nothing here touches artifact bytes or wire bytes, so the compatibility test
//! ("does fossil ever see this?") answers no for the whole module.
//!
//! Container, mirroring `.zit-stash`:
//!   magic "ZITPREC" | version u16 = 1 | reserved u16 = 0 | count u32 |
//!   count x entry | crc32 u32
//!
//! # Why this degrades where stash surfaces
//!
//! `stash` holds work that exists nowhere else, so a damaged sidecar is an
//! error: losing it silently would lose the user's only copy. A precedent holds
//! a resolution the user already authored and committed, so a damaged sidecar
//! costs one hand-resolution and destroys nothing. It therefore degrades to
//! "no precedents" rather than failing the merge that was only asking whether
//! a shortcut existed.
//!
//! Degrading is not the same as hiding: `load` reports damage through
//! `Loaded.damaged` so the verb layer can say the sidecar was reset. The
//! failure mode this module exists to avoid is a cache that answers
//! confidently and wrongly; a cache that answers "nothing" is safe, and a
//! cache that quietly resets itself without saying so is how the first one
//! starts.
//!
//! # Why the key is the whole conflicted file
//!
//! `merge3` writes diff3 envelopes carrying all three sides — current, base
//! (`||||||| base`), other — so the conflicted bytes fully determine the
//! conflict. Hashing them is exact: no segmentation, no normalization, no
//! guess about what "the same conflict" means.
//!
//! The granularity is deliberately the FILE, not the hunk. A file with two
//! conflicts where only one recurs will not replay, because its conflicted
//! bytes differ. That is under-firing, and it is the direction to err in: a
//! precedent that declines to apply costs a hand-resolution, while one that
//! splices a remembered hunk into a changed neighbourhood writes a plausible
//! wrong answer into the working tree without saying so. Hunk granularity is a
//! later decision that needs its own evidence, not a v1 default.
//!
//! The path is part of the key for the same reason: identical conflicting text
//! in two files is two conflicts, and a resolution authored for one of them was
//! authored knowing which file it was in.

const std = @import("std");
const assert = std.debug.assert;

pub const precedent_filename: []const u8 = ".zit-precedent";
const magic = "ZITPREC";
const version: u16 = 1;

/// Bounds, stated rather than grown into (TigerStyle). Whichever binds first
/// evicts oldest-first, and the eviction is reported: a cache that silently
/// forgets is indistinguishable from one that never learned.
pub const max_entries: usize = 256;
pub const max_bytes: usize = 8 << 20;

/// A resolution's identity: sha256 over the path and the conflicted bytes.
pub const Key = [32]u8;

/// Derive a precedent key. Pure: no allocator, no I/O, no ambient state, so
/// the same conflict keys identically on every machine and in every test.
///
/// The path length is mixed in before the path itself so that
/// ("ab", "c...") and ("a", "bc...") cannot collide by concatenation.
pub fn key(path: []const u8, conflicted: []const u8) Key {
    var h = std.crypto.hash.sha2.Sha256.init(.{});
    var len_buf: [8]u8 = undefined;
    std.mem.writeInt(u64, &len_buf, @intCast(path.len), .little);
    h.update(&len_buf);
    h.update(path);
    h.update(conflicted);
    var out: Key = undefined;
    h.final(&out);
    return out;
}

/// One remembered resolution. `conflicted` is retained so `list` can show what
/// a precedent would fire on, and so a replay can be explained after the fact
/// rather than only counted.
pub const Entry = struct {
    key: Key,
    path: []const u8,
    conflicted: []const u8,
    resolved: []const u8,
    /// True between the merge that produced this conflict and the commit that
    /// resolves it. A pending entry has no resolution yet, so it can never be
    /// replayed — `find` skips it. Recording the conflict at merge time is what
    /// lets `commit` pair it with the bytes the operator actually settled on.
    pending: bool = false,

    fn bytes(self: Entry) usize {
        return self.path.len + self.conflicted.len + self.resolved.len;
    }
};

pub const Precedents = struct {
    gpa: std.mem.Allocator,
    entries: std.ArrayList(Entry) = .empty,

    pub fn deinit(self: *Precedents) void {
        for (self.entries.items) |e| {
            self.gpa.free(e.path);
            self.gpa.free(e.conflicted);
            self.gpa.free(e.resolved);
        }
        self.entries.deinit(self.gpa);
        self.* = undefined;
    }

    /// The resolution for a conflict, or null. Const: a lookup never mutates,
    /// so a replay cannot renumber or reorder what `list` just showed.
    pub fn find(self: *const Precedents, k: Key) ?*const Entry {
        for (self.entries.items) |*e| {
            if (e.pending) continue; // no resolution yet: nothing to replay
            if (std.mem.eql(u8, &e.key, &k)) return e;
        }
        return null;
    }

    /// Total retained bytes, the quantity `max_bytes` bounds.
    pub fn byteLen(self: *const Precedents) usize {
        var n: usize = 0;
        for (self.entries.items) |e| n += e.bytes();
        return n;
    }

    /// Remember a resolution, replacing any entry with the same key. Returns
    /// the number of entries evicted to stay inside the bounds, so the caller
    /// can report it.
    ///
    /// Re-recording an existing key moves it to the newest position: a
    /// resolution the user just re-authored is the one worth keeping when the
    /// bound bites.
    pub fn record(
        self: *Precedents,
        path: []const u8,
        conflicted: []const u8,
        resolved: []const u8,
    ) error{OutOfMemory}!usize {
        return self.put(path, conflicted, resolved, false);
    }

    /// Remember a conflict whose resolution is not known yet. `commit` turns it
    /// into a replayable precedent via `resolve`; until then it is inert.
    pub fn recordPending(
        self: *Precedents,
        path: []const u8,
        conflicted: []const u8,
    ) error{OutOfMemory}!usize {
        return self.put(path, conflicted, "", true);
    }

    /// Attach a resolution to a pending precedent. False when the key is absent
    /// or already resolved, so a second commit cannot silently rewrite one.
    pub fn resolve(
        self: *Precedents,
        k: Key,
        resolved: []const u8,
    ) error{OutOfMemory}!bool {
        for (self.entries.items) |*e| {
            if (!e.pending) continue;
            if (!std.mem.eql(u8, &e.key, &k)) continue;
            const owned = try self.gpa.dupe(u8, resolved);
            self.gpa.free(e.resolved);
            e.resolved = owned;
            e.pending = false;
            return true;
        }
        return false;
    }

    fn put(
        self: *Precedents,
        path: []const u8,
        conflicted: []const u8,
        resolved: []const u8,
        pending: bool,
    ) error{OutOfMemory}!usize {
        const k = key(path, conflicted);
        _ = self.forget(k);

        const owned_path = try self.gpa.dupe(u8, path);
        errdefer self.gpa.free(owned_path);
        const owned_conf = try self.gpa.dupe(u8, conflicted);
        errdefer self.gpa.free(owned_conf);
        const owned_res = try self.gpa.dupe(u8, resolved);
        errdefer self.gpa.free(owned_res);

        try self.entries.append(self.gpa, .{
            .key = k,
            .path = owned_path,
            .conflicted = owned_conf,
            .resolved = owned_res,
            .pending = pending,
        });

        var evicted: usize = 0;
        while (self.entries.items.len > max_entries or
            (self.byteLen() > max_bytes and self.entries.items.len > 1))
        {
            self.dropIndex(0);
            evicted += 1;
        }
        return evicted;
    }

    /// Drop one precedent. True when something was removed.
    pub fn forget(self: *Precedents, k: Key) bool {
        for (self.entries.items, 0..) |e, i| {
            if (std.mem.eql(u8, &e.key, &k)) {
                self.dropIndex(i);
                return true;
            }
        }
        return false;
    }

    /// Drop every precedent, returning how many there were.
    pub fn forgetAll(self: *Precedents) usize {
        const n = self.entries.items.len;
        while (self.entries.items.len != 0) self.dropIndex(0);
        return n;
    }

    fn dropIndex(self: *Precedents, i: usize) void {
        const e = self.entries.orderedRemove(i);
        self.gpa.free(e.path);
        self.gpa.free(e.conflicted);
        self.gpa.free(e.resolved);
    }
};

/// A load result. `damaged` is true when a sidecar existed but could not be
/// read as one; `precedents` is then empty, and the caller is expected to say
/// so rather than proceed as if the file had never been there.
pub const Loaded = struct {
    precedents: Precedents,
    damaged: bool = false,
};

/// Load the checkout's precedents. An absent sidecar yields an empty set; a
/// damaged one yields an empty set AND `damaged = true`. There is no error
/// path: a merge asking whether a shortcut exists must never fail because the
/// answer was unreadable.
pub fn load(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) error{OutOfMemory}!Loaded {
    const bytes = dir.readFileAlloc(io, precedent_filename, gpa, .limited(1 << 30)) catch |err| switch (err) {
        error.FileNotFound => return .{ .precedents = .{ .gpa = gpa } },
        error.OutOfMemory => return error.OutOfMemory,
        else => return .{ .precedents = .{ .gpa = gpa }, .damaged = true },
    };
    defer gpa.free(bytes);

    var p: Precedents = .{ .gpa = gpa };
    errdefer p.deinit();
    parse(&p, bytes) catch {
        p.deinit();
        return .{ .precedents = .{ .gpa = gpa }, .damaged = true };
    };
    return .{ .precedents = p };
}

fn parse(p: *Precedents, bytes: []const u8) error{ OutOfMemory, Corrupt }!void {
    if (bytes.len < magic.len + 2 + 2 + 4 + 4) return error.Corrupt;
    if (!std.mem.eql(u8, bytes[0..magic.len], magic)) return error.Corrupt;
    var crc = std.hash.Crc32.init();
    crc.update(bytes[0 .. bytes.len - 4]);
    if (crc.final() != std.mem.readInt(u32, bytes[bytes.len - 4 ..][0..4], .little)) return error.Corrupt;

    var r = Reader{ .bytes = bytes[0 .. bytes.len - 4], .pos = magic.len };
    if (try r.int(u16) != version) return error.Corrupt;
    if (try r.int(u16) != 0) return error.Corrupt;
    const count = try r.int(u32);
    if (count > max_entries) return error.Corrupt;

    var i: u32 = 0;
    while (i < count) : (i += 1) {
        var k: Key = undefined;
        @memcpy(&k, try r.slice(k.len));
        const path = try r.slice(try r.int(u16));
        const conflicted = try r.slice(try r.int(u32));
        const resolved = try r.slice(try r.int(u32));
        const pending_raw = try r.int(u8);
        if (pending_raw > 1) return error.Corrupt;
        // A stored key that does not match its own content is damage that a
        // crc cannot see (a correctly-checksummed write of the wrong bytes).
        // Refusing it keeps `find` from ever answering for a conflict it does
        // not actually describe.
        if (!std.mem.eql(u8, &k, &key(path, conflicted))) return error.Corrupt;
        try p.entries.append(p.gpa, .{
            .key = k,
            .path = try p.gpa.dupe(u8, path),
            .conflicted = try p.gpa.dupe(u8, conflicted),
            .resolved = try p.gpa.dupe(u8, resolved),
            .pending = pending_raw == 1,
        });
    }
    if (r.pos != r.bytes.len) return error.Corrupt;
}

/// Write the sidecar, deleting it when empty so "no precedents" is the absence
/// of a file rather than a file that says nothing.
pub fn store(
    p: *const Precedents,
    gpa: std.mem.Allocator,
    io: std.Io,
    dir: std.Io.Dir,
) error{ OutOfMemory, Storage }!void {
    if (p.entries.items.len == 0) {
        dir.deleteFile(io, precedent_filename) catch {};
        return;
    }
    var buf: std.ArrayList(u8) = .empty;
    defer buf.deinit(gpa);
    try buf.appendSlice(gpa, magic);
    try appendInt(gpa, &buf, u16, version);
    try appendInt(gpa, &buf, u16, 0);
    try appendInt(gpa, &buf, u32, @intCast(p.entries.items.len));
    for (p.entries.items) |e| {
        try buf.appendSlice(gpa, &e.key);
        try appendInt(gpa, &buf, u16, @intCast(e.path.len));
        try buf.appendSlice(gpa, e.path);
        try appendInt(gpa, &buf, u32, @intCast(e.conflicted.len));
        try buf.appendSlice(gpa, e.conflicted);
        try appendInt(gpa, &buf, u32, @intCast(e.resolved.len));
        try buf.appendSlice(gpa, e.resolved);
        try appendInt(gpa, &buf, u8, @intFromBool(e.pending));
    }
    var crc = std.hash.Crc32.init();
    crc.update(buf.items);
    try appendInt(gpa, &buf, u32, crc.final());

    var af = dir.createFileAtomic(io, precedent_filename, .{ .replace = true }) catch return error.Storage;
    defer af.deinit(io);
    af.file.writePositionalAll(io, buf.items, 0) catch return error.Storage;
    af.replace(io) catch return error.Storage;
}

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

const Reader = struct {
    bytes: []const u8,
    pos: usize,

    fn int(self: *Reader, comptime T: type) error{Corrupt}!T {
        const n = @sizeOf(T);
        if (self.pos + n > self.bytes.len) return error.Corrupt;
        const v = std.mem.readInt(T, self.bytes[self.pos..][0..n], .little);
        self.pos += n;
        return v;
    }

    fn slice(self: *Reader, len: usize) error{Corrupt}![]const u8 {
        if (self.pos + len > self.bytes.len) return error.Corrupt;
        const out = self.bytes[self.pos..][0..len];
        self.pos += len;
        return out;
    }
};

const t = std.testing;

test "precedent key: pure, and distinguishes path from content" {
    const a = key("a.txt", "<<<<<<< current\nx\n");
    try t.expectEqualSlices(u8, &a, &key("a.txt", "<<<<<<< current\nx\n"));
    try t.expect(!std.mem.eql(u8, &a, &key("b.txt", "<<<<<<< current\nx\n")));
    // Concatenation ambiguity: ("ab","c") must not collide with ("a","bc").
    try t.expect(!std.mem.eql(u8, &key("ab", "c"), &key("a", "bc")));
}

test "precedent: record/store/load round-trips, and find answers by key" {
    var tmp = t.tmpDir(.{});
    defer tmp.cleanup();
    const io = t.io;

    var p: Precedents = .{ .gpa = t.allocator };
    defer p.deinit();
    try t.expectEqual(@as(usize, 0), try p.record("a.txt", "CONFLICTED\n", "RESOLVED\n"));
    try store(&p, t.allocator, io, tmp.dir);

    var got = try load(t.allocator, io, tmp.dir);
    defer got.precedents.deinit();
    try t.expect(!got.damaged);
    const hit = got.precedents.find(key("a.txt", "CONFLICTED\n")) orelse return error.TestExpectedHit;
    try t.expectEqualStrings("RESOLVED\n", hit.resolved);
    try t.expectEqualStrings("a.txt", hit.path);
    // A different conflict in the same file does not fire.
    try t.expect(got.precedents.find(key("a.txt", "OTHER\n")) == null);
}

test "precedent: an absent sidecar loads empty and is not damage" {
    var tmp = t.tmpDir(.{});
    defer tmp.cleanup();
    var got = try load(t.allocator, t.io, tmp.dir);
    defer got.precedents.deinit();
    try t.expectEqual(@as(usize, 0), got.precedents.entries.items.len);
    try t.expect(!got.damaged);
}

test "precedent: an empty set deletes the sidecar" {
    var tmp = t.tmpDir(.{});
    defer tmp.cleanup();
    const io = t.io;
    var p: Precedents = .{ .gpa = t.allocator };
    defer p.deinit();
    _ = try p.record("a.txt", "C\n", "R\n");
    try store(&p, t.allocator, io, tmp.dir);
    try t.expectEqual(@as(usize, 1), p.forgetAll());
    try store(&p, t.allocator, io, tmp.dir);
    try t.expectError(error.FileNotFound, tmp.dir.statFile(io, precedent_filename, .{}));
}

test "precedent: a damaged sidecar degrades to empty and says so" {
    var tmp = t.tmpDir(.{});
    defer tmp.cleanup();
    const io = t.io;

    var p: Precedents = .{ .gpa = t.allocator };
    defer p.deinit();
    _ = try p.record("a.txt", "C\n", "R\n");
    try store(&p, t.allocator, io, tmp.dir);

    const raw = try tmp.dir.readFileAlloc(io, precedent_filename, t.allocator, .limited(1 << 20));
    defer t.allocator.free(raw);
    raw[raw.len - 8] ^= 0xff;
    var af = try tmp.dir.createFileAtomic(io, precedent_filename, .{ .replace = true });
    defer af.deinit(io);
    try af.file.writePositionalAll(io, raw, 0);
    try af.replace(io);

    var got = try load(t.allocator, io, tmp.dir);
    defer got.precedents.deinit();
    try t.expectEqual(@as(usize, 0), got.precedents.entries.items.len);
    try t.expect(got.damaged); // degraded, but not silently
}

test "precedent: re-recording a key replaces rather than duplicates" {
    var p: Precedents = .{ .gpa = t.allocator };
    defer p.deinit();
    _ = try p.record("a.txt", "C\n", "FIRST\n");
    _ = try p.record("a.txt", "C\n", "SECOND\n");
    try t.expectEqual(@as(usize, 1), p.entries.items.len);
    const hit = p.find(key("a.txt", "C\n")) orelse return error.TestExpectedHit;
    try t.expectEqualStrings("SECOND\n", hit.resolved);
}

test "precedent: the entry bound evicts oldest-first and reports it" {
    var p: Precedents = .{ .gpa = t.allocator };
    defer p.deinit();
    var i: usize = 0;
    while (i < max_entries) : (i += 1) {
        var buf: [32]u8 = undefined;
        const path = try std.fmt.bufPrint(&buf, "f{d}.txt", .{i});
        try t.expectEqual(@as(usize, 0), try p.record(path, "C\n", "R\n"));
    }
    try t.expectEqual(max_entries, p.entries.items.len);
    // The oldest goes, and the caller is told.
    try t.expectEqual(@as(usize, 1), try p.record("overflow.txt", "C\n", "R\n"));
    try t.expectEqual(max_entries, p.entries.items.len);
    try t.expect(p.find(key("f0.txt", "C\n")) == null);
    try t.expect(p.find(key("overflow.txt", "C\n")) != null);
}

test "precedent: forget removes exactly one, forgetAll counts" {
    var p: Precedents = .{ .gpa = t.allocator };
    defer p.deinit();
    _ = try p.record("a.txt", "C\n", "R\n");
    _ = try p.record("b.txt", "C\n", "R\n");
    try t.expect(p.forget(key("a.txt", "C\n")));
    try t.expect(!p.forget(key("a.txt", "C\n"))); // idempotent
    try t.expectEqual(@as(usize, 1), p.entries.items.len);
    try t.expectEqual(@as(usize, 1), p.forgetAll());
}

test "precedent: a key that disagrees with its content is refused as damage" {
    var tmp = t.tmpDir(.{});
    defer tmp.cleanup();
    const io = t.io;

    var p: Precedents = .{ .gpa = t.allocator };
    defer p.deinit();
    _ = try p.record("a.txt", "C\n", "R\n");
    try store(&p, t.allocator, io, tmp.dir);

    // Rewrite the stored key to one that does not describe the stored bytes,
    // then re-checksum so the crc still passes. Only the key/content
    // cross-check can catch this.
    const raw = try tmp.dir.readFileAlloc(io, precedent_filename, t.allocator, .limited(1 << 20));
    defer t.allocator.free(raw);
    const key_off = magic.len + 2 + 2 + 4;
    raw[key_off] ^= 0xff;
    var crc = std.hash.Crc32.init();
    crc.update(raw[0 .. raw.len - 4]);
    std.mem.writeInt(u32, raw[raw.len - 4 ..][0..4], crc.final(), .little);
    var af = try tmp.dir.createFileAtomic(io, precedent_filename, .{ .replace = true });
    defer af.deinit(io);
    try af.file.writePositionalAll(io, raw, 0);
    try af.replace(io);

    var got = try load(t.allocator, io, tmp.dir);
    defer got.precedents.deinit();
    try t.expect(got.damaged);
    try t.expectEqual(@as(usize, 0), got.precedents.entries.items.len);
}