Skip to content
zit Artifact [c74c17bae9]
Login

Artifact [c74c17bae9]

Check-ins Using Download Hex

Artifact c74c17bae94083057c28457e8e6e1d167a94b5e0563225b7cf927ab53f8fed23:

//! zit#188 — the file-history index: which check-ins changed which path.
//!
//! `zit log CHECKIN PATH` names the check-ins whose effective content for PATH
//! differs from their primary parent's. Answering that by reconstructing two
//! manifests per visited check-in made one file's history on a mirror of
//! SQLite take minutes: the cost grew with how much history sat behind the
//! walk rather than with the answer's size.
//!
//! Fossil answers the same question from `mlink`, an index. zit already
//! computes the identical fact — `repoview.ChangedFile` is documented as
//! Fossil's mlink row, and `captureFileFacts` produces one check-in's change
//! set against its primary parent — but only streams it to the `crosslink`
//! feed. This module persists it, inverted by path, so the predicate becomes a
//! lookup instead of a reconstruction.
//!
//! Advisory, like every other member of the `.zit-cache` tier: keyed to the
//! log prefix and the shun fingerprint, rebuilt by one pass on any refusal,
//! and deleting it can only cost time. The answer stays derivable from the log
//! without it, which is what lets the reader fall back.
//!
//! **Unknown is recorded, not guessed.** `captureFileFacts` returns "files
//! unknown" for a tree manifest, an absent or shunned parent, or an
//! unresolvable baseline. Those check-ins are listed in `unknown`, and a
//! consumer that finds any of them in the ancestry it is asking about must
//! fall back to the reconstructing predicate. An empty change set is a claim;
//! silence is not the same as "changed nothing".

const std = @import("std");
const logstore = @import("logstore.zig");
const repoview = @import("repoview.zig");
const crc32 = @import("crc32.zig");

/// Rids are stored as u32: a log with more than 4 billion frames is past
/// several other limits first, and the index refuses to claim coverage it
/// cannot address rather than truncating one.
pub const max_rid: u64 = std.math.maxInt(u32);

/// Accumulates `repoview.eachChangeSet` into the path -> rids inversion.
pub const Builder = struct {
    gpa: std.mem.Allocator,
    arena: std.heap.ArenaAllocator,
    map: std.StringArrayHashMapUnmanaged(std.ArrayListUnmanaged(u32)) = .empty,
    unknown: std.ArrayListUnmanaged(u32) = .empty,
    /// Set when a rid exceeds `max_rid`; the caller must not persist a blob
    /// that silently covers less than the log.
    overflow: bool = false,

    pub fn init(gpa: std.mem.Allocator) Builder {
        return .{ .gpa = gpa, .arena = std.heap.ArenaAllocator.init(gpa) };
    }

    pub fn deinit(self: *Builder) void {
        for (self.map.values()) |*list| list.deinit(self.gpa);
        self.map.deinit(self.gpa);
        self.unknown.deinit(self.gpa);
        self.arena.deinit();
    }

    pub fn sink(self: *Builder) repoview.ChangeSetSink {
        return .{ .ctx = self, .emit = emit };
    }

    /// Seed this builder with an adopted index, so a tail walk extends it
    /// rather than replacing it. Paths are copied into the builder's arena;
    /// the blob may be freed afterwards.
    pub fn absorb(self: *Builder, idx: *const Index) error{OutOfMemory}!void {
        var u: usize = 0;
        while (u < idx.unknownCount()) : (u += 1) try self.unknown.append(self.gpa, idx.unknownAt(u));
        var pos = idx.first;
        var i: u32 = 0;
        while (i < idx.n_paths) : (i += 1) {
            const len = std.mem.readInt(u16, idx.blob[pos..][0..2], .little);
            pos += 2;
            const name = idx.blob[pos..][0..len];
            pos += len;
            const count = std.mem.readInt(u32, idx.blob[pos..][0..4], .little);
            pos += 4;
            const gop = try self.map.getOrPut(self.gpa, name);
            if (!gop.found_existing) {
                gop.value_ptr.* = .empty; // before the copy can fail; see `emit`
                gop.key_ptr.* = self.arena.allocator().dupe(u8, name) catch |e| {
                    self.map.swapRemoveAt(gop.index);
                    return e;
                };
            }
            var k: u32 = 0;
            while (k < count) : (k += 1) {
                try gop.value_ptr.append(self.gpa, std.mem.readInt(u32, idx.blob[pos + k * 4 ..][0..4], .little));
            }
            pos += count * 4;
        }
    }

    fn emit(ctx: *anyopaque, rid: logstore.Rid, files: ?[]const repoview.ChangedFile) error{OutOfMemory}!void {
        const self: *Builder = @ptrCast(@alignCast(ctx));
        if (rid > max_rid) {
            self.overflow = true;
            return;
        }
        const small: u32 = @intCast(rid);
        const changed = files orelse {
            try self.unknown.append(self.gpa, small);
            return;
        };
        for (changed) |f| {
            const gop = try self.map.getOrPut(self.gpa, f.path);
            if (!gop.found_existing) {
                // The value is initialized BEFORE the key copy can fail, and a
                // failed copy removes the slot: otherwise an allocation failure
                // here left a slot holding a borrowed key and an undefined list
                // for `deinit` to free. The change set is freed per check-in,
                // so the key is copied.
                gop.value_ptr.* = .empty;
                gop.key_ptr.* = self.arena.allocator().dupe(u8, f.path) catch |e| {
                    self.map.swapRemoveAt(gop.index);
                    return e;
                };
            }
            // One check-in reports a path at most once, so a rid never repeats
            // in a path's list. The list is NOT guaranteed ascending: the
            // on-query build walks rids in order, but the derive walks frames
            // in persisted order, and a phantom filled after later frames has a
            // low rid at a high offset. Consumers treat the list as a set.
            try gop.value_ptr.append(self.gpa, small);
        }
    }
};

// ---------------------------------------------------------------------------
// Codec. magic | version | LogKey | shun | n_paths | n_unknown
//        | unknown rids | (path len, path, count, rids)* sorted by path | crc
//
// Paths are written in sorted order so a reader sweeps record headers and
// stops early on a miss, without building a map it would use once (logstore's
// #145 sorted directory, same reasoning).
// ---------------------------------------------------------------------------

const magic = "ZITFIDX\x00";
/// v2 records `n_rids`, the log entry count the index covers, so a later
/// append is walked as a TAIL instead of rebuilding the whole index. A v1
/// blob is refused and rebuilt once; it could not say where its coverage
/// ended, so it could not be extended.
///
/// v3 (zit#192) is the same layout: the bump refuses a v2 blob built before
/// tree manifests were diffed, which recorded every tree check-in as UNKNOWN.
/// Such a blob is valid, adopted, and never rebuilt — so without the bump the
/// fix would never take effect on a store that already carried one.
///
/// v4 adds `key_entries`: how many log entries existed when the index was
/// written. An index is COMPLETE when `n_rids == key_entries`, and only a
/// complete index may be adopted by a derive extending a checkpoint over a
/// tail. The on-query build checkpoints partial indexes mid-walk under the
/// live log's key — that is what makes it resumable — and without this field
/// a partial index whose key matched the checkpoint's was adopted as complete,
/// which claimed coverage over the gap and silently omitted history.
const version: u16 = 4;
const header_len = 8 + 2 + 8 + 8 + 8 + 4 + 4 + 4 + 4 + 8 + 8;

pub fn serialize(
    gpa: std.mem.Allocator,
    log: *const logstore.LogStore,
    b: *Builder,
    /// Log entries this index covers; the next open resumes after it.
    n_rids: u64,
) error{OutOfMemory}!?[]u8 {
    if (b.overflow) return null;
    const key = log.logKey() catch return null;

    const order = try gpa.alloc(usize, b.map.count());
    defer gpa.free(order);
    for (order, 0..) |*o, i| o.* = i;
    const keys = b.map.keys();
    std.mem.sort(usize, order, keys, struct {
        fn less(ks: []const []const u8, x: usize, y: usize) bool {
            return std.mem.lessThan(u8, ks[x], ks[y]);
        }
    }.less);

    var body: usize = @as(usize, b.unknown.items.len) * 4;
    for (keys) |k| {
        if (k.len > std.math.maxInt(u16)) return null;
        body += 2 + k.len + 4;
    }
    for (b.map.values()) |v| body += v.items.len * 4;

    const blob = try gpa.alloc(u8, header_len + body + 4);
    errdefer gpa.free(blob);
    @memcpy(blob[0..8], magic);
    std.mem.writeInt(u16, blob[8..10], version, .little);
    std.mem.writeInt(u64, blob[10..18], key.end, .little);
    std.mem.writeInt(u64, blob[18..26], key.frame_count, .little);
    std.mem.writeInt(u64, blob[26..34], key.last_frame_offset, .little);
    std.mem.writeInt(u32, blob[34..38], key.last_header_crc, .little);
    std.mem.writeInt(u32, blob[38..42], log.shunFingerprint(), .little);
    std.mem.writeInt(u32, blob[42..46], @intCast(b.map.count()), .little);
    std.mem.writeInt(u32, blob[46..50], @intCast(b.unknown.items.len), .little);
    std.mem.writeInt(u64, blob[50..58], n_rids, .little);
    std.mem.writeInt(u64, blob[58..66], @intCast(log.entryCount()), .little);

    var pos: usize = header_len;
    for (b.unknown.items) |r| {
        std.mem.writeInt(u32, blob[pos..][0..4], r, .little);
        pos += 4;
    }
    for (order) |i| {
        const k = keys[i];
        const rids = b.map.values()[i].items;
        std.mem.writeInt(u16, blob[pos..][0..2], @intCast(k.len), .little);
        pos += 2;
        @memcpy(blob[pos..][0..k.len], k);
        pos += k.len;
        std.mem.writeInt(u32, blob[pos..][0..4], @intCast(rids.len), .little);
        pos += 4;
        for (rids) |r| {
            std.mem.writeInt(u32, blob[pos..][0..4], r, .little);
            pos += 4;
        }
    }
    std.debug.assert(pos == blob.len - 4);
    var crc = crc32.Crc32.init();
    crc.update(blob[0 .. blob.len - 4]);
    std.mem.writeInt(u32, blob[blob.len - 4 ..][0..4], crc.final(), .little);
    return blob;
}

/// A parsed index, borrowing the blob it was adopted from.
pub const Index = struct {
    blob: []const u8,
    n_paths: u32,
    /// Rids whose change set could not be known; a query whose candidate set
    /// touches one of these must fall back to reconstruction.
    unknown: []const u8,
    /// Offset of the first path record.
    first: usize,
    /// Log entries this index covers. A log that has grown past it is walked
    /// from here rather than from the beginning.
    n_rids: u64,
    /// The log key's frame count at build time — the same unit a cache
    /// checkpoint records, so a derive extending a checkpoint over a tail can
    /// tell whether this index stops at exactly that checkpoint. Entries and
    /// frames are not the same count (a header frame is not an entry), so
    /// `n_rids` cannot be compared against a checkpoint directly.
    key_frame_count: u64,
    /// Log entries that existed when this index was written. The index is
    /// COMPLETE — covers every entry up to its key — when `n_rids` equals it;
    /// a mid-walk checkpoint of the on-query build has `n_rids` below it.
    key_entries: u64,

    /// Whether this index covers every entry up to its key. Only a complete
    /// index may be extended over a checkpoint's tail; a partial one is
    /// resumed from `n_rids` by the on-query build, which walks the gap.
    pub fn complete(self: *const Index) bool {
        return self.n_rids == self.key_entries;
    }

    /// The check-ins that changed `path`, ascending. Empty is a real answer —
    /// "no check-in changed it" — distinct from `unknown`.
    pub fn changedBy(self: *const Index, path: []const u8, out: *std.ArrayListUnmanaged(u32), gpa: std.mem.Allocator) error{OutOfMemory}!void {
        // Records are variable-width, so this sweeps rather than bisects: it
        // reads each record's header and steps over its rid block, so the cost
        // is one iteration per PATH (a few thousand), not per rid (hundreds of
        // thousands). Sorted order lets it stop early on a miss. A bisect would
        // need a second offset table for a lookup that is already microseconds.
        var pos = self.first;
        var i: u32 = 0;
        while (i < self.n_paths) : (i += 1) {
            const len = std.mem.readInt(u16, self.blob[pos..][0..2], .little);
            pos += 2;
            const name = self.blob[pos..][0..len];
            pos += len;
            const count = std.mem.readInt(u32, self.blob[pos..][0..4], .little);
            pos += 4;
            if (std.mem.eql(u8, name, path)) {
                var k: u32 = 0;
                while (k < count) : (k += 1) {
                    try out.append(gpa, std.mem.readInt(u32, self.blob[pos + k * 4 ..][0..4], .little));
                }
                return;
            }
            // Sorted: once past the name, it is absent.
            if (std.mem.order(u8, name, path) == .gt) return;
            pos += count * 4;
        }
    }

    pub fn unknownCount(self: *const Index) usize {
        return self.unknown.len / 4;
    }

    pub fn unknownAt(self: *const Index, i: usize) u32 {
        return std.mem.readInt(u32, self.unknown[i * 4 ..][0..4], .little);
    }
};

/// Adopt a blob against `log`: magic, version, CRC, the log prefix it was
/// keyed to, and the shun fingerprint must all hold, or the answer is null and
/// the caller rebuilds.
pub fn parse(blob: []const u8, log: *const logstore.LogStore) ?Index {
    if (blob.len < header_len + 4) return null;
    if (!std.mem.eql(u8, blob[0..8], magic)) return null;
    if (std.mem.readInt(u16, blob[8..10], .little) != version) return null;
    var crc = crc32.Crc32.init();
    crc.update(blob[0 .. blob.len - 4]);
    if (std.mem.readInt(u32, blob[blob.len - 4 ..][0..4], .little) != crc.final()) return null;
    const key = logstore.LogStore.LogKey{
        .end = std.mem.readInt(u64, blob[10..18], .little),
        .frame_count = std.mem.readInt(u64, blob[18..26], .little),
        .last_frame_offset = std.mem.readInt(u64, blob[26..34], .little),
        .last_header_crc = std.mem.readInt(u32, blob[34..38], .little),
    };
    // A PREFIX match, not an exact tail: an append adds check-ins the index
    // never saw, and those are walked as a tail (`n_rids` says where to
    // resume). Refusing the whole index on any append is what made every
    // commit cost a full rebuild.
    if (!logstore.LogStore.validatePrefix(log.file, key)) return null;
    if (std.mem.readInt(u32, blob[38..42], .little) != log.shunFingerprint()) return null;
    const n_paths = std.mem.readInt(u32, blob[42..46], .little);
    const n_unknown = std.mem.readInt(u32, blob[46..50], .little);
    const ubytes = @as(usize, n_unknown) * 4;
    if (header_len + ubytes > blob.len - 4) return null;
    return .{
        .blob = blob,
        .n_paths = n_paths,
        .unknown = blob[header_len..][0..ubytes],
        .first = header_len + ubytes,
        .n_rids = std.mem.readInt(u64, blob[50..58], .little),
        .key_frame_count = key.frame_count,
        .key_entries = std.mem.readInt(u64, blob[58..66], .little),
    };
}

test "fileindex: a built index answers by path and round-trips through the codec" {
    const gpa = std.testing.allocator;
    const io = std.testing.io;
    var tmp = std.testing.tmpDir(.{});
    defer tmp.cleanup();
    const raw = try tmp.dir.createFile(io, "log", .{ .read = true });
    var fs = @import("storage.zig").FileStorage.init(io, raw, 0);
    var log = try logstore.LogStore.open(gpa, fs.storageFile(), 0);
    defer log.deinit(gpa);

    var b = Builder.init(gpa);
    defer b.deinit();
    const s = b.sink();
    // Two check-ins touching overlapping paths, and one unknown.
    try s.emit(s.ctx, 1, &.{
        .{ .disp = .added, .path = "src/a.zig", .hash = "1" ** 64 },
        .{ .disp = .added, .path = "README.md", .hash = "2" ** 64 },
    });
    try s.emit(s.ctx, 2, &.{.{ .disp = .modified, .path = "README.md", .hash = "3" ** 64 }});
    try s.emit(s.ctx, 3, null); // a tree manifest: unknown, never "changed nothing"

    const blob = (try serialize(gpa, &log, &b, 3)).?;
    defer gpa.free(blob);
    const idx = parse(blob, &log).?;

    var out: std.ArrayListUnmanaged(u32) = .empty;
    defer out.deinit(gpa);
    try idx.changedBy("README.md", &out, gpa);
    try std.testing.expectEqualSlices(u32, &.{ 1, 2 }, out.items);
    out.clearRetainingCapacity();
    try idx.changedBy("src/a.zig", &out, gpa);
    try std.testing.expectEqualSlices(u32, &.{1}, out.items);
    out.clearRetainingCapacity();
    // A path no check-in touched is an empty ANSWER, not an absence of one.
    try idx.changedBy("never.txt", &out, gpa);
    try std.testing.expectEqual(@as(usize, 0), out.items.len);
    try std.testing.expectEqual(@as(u64, 3), idx.n_rids);
    try std.testing.expectEqual(@as(usize, 1), idx.unknownCount());
    try std.testing.expectEqual(@as(u32, 3), idx.unknownAt(0));

    // A flipped byte is refused rather than adopted.
    const bad = try gpa.dupe(u8, blob);
    defer gpa.free(bad);
    bad[header_len + 2] ^= 1;
    try std.testing.expect(parse(bad, &log) == null);
}