//! The Git import map: DEST's durable record of which Git commit became which
//! zit check-in, written beside the published store as DEST/.zit-import-map.
//! A later import that adds new upstream commits to an existing DEST reads it
//! to find where the previous run stopped, which settings it pinned, and
//! whether the SOURCE it is offered is the same history at all.
//!
//! The container follows `git_export_state.zig` and `repocache.zig`: magic,
//! version, a self-checksum over every earlier byte, a validated HIT or a
//! total failure, and no claimed length trusted before it is bounded by the
//! bytes that remain. Unlike those two files the map is NOT disposable.
//! Check-in manifests carry no Git OID, so nothing in the store can rebuild
//! the Git-to-zit correspondence; losing the map costs a full re-import. That
//! is why `write` reports failure as an error the caller must handle rather
//! than a best-effort bool, and why it refuses to publish any contents `load`
//! would reject.
//!
//! This is a different file from `.zit-import-map.jsonl`, the per-object
//! provenance log published only under `--provenance`.
//!
//! On-disk layout, every integer little-endian, `len8`/`len16` a u8/u16 byte
//! count followed by that many bytes:
//!
//! magic "ZITGIMAP" | version u16
//! object_format u8 (0 sha1, 1 sha256)
//! submanifest u8 (0 flat, 1 tree) | k u8 (0 when flat, else 1..12)
//! attribution u8 (0 committer, 1 author)
//! refuse_signed u8 (0|1) | mirror_classifier_fired u8 (0|1) | artifact_count u64
//! default_branch len16
//! root_count u64, then root_count x oid len8 (strictly ascending)
//! commit_count u64, then commit_count x
//! oid len8 | checkin len8 | branch len16 | depth u64 | height u8
//! ref_count u64, then ref_count x name len16 | oid len8
//! crc32 u32 over every byte before it
const std = @import("std");
const crc32 = @import("../crc32.zig");
const artifact = @import("../artifact.zig");
const storage = @import("../storage.zig");
/// The map's name inside DEST, beside the published `.zit` store and the
/// checkout record.
pub const map_filename: []const u8 = ".zit-import-map";
const magic: [8]u8 = "ZITGIMAP".*;
const format_version: u16 = 1;
/// The accepted file-size ceiling, checked against the file's stat before any
/// allocation. Large enough for several million commits at roughly 150 bytes
/// a record; every count inside the file is bounded again by the bytes that
/// actually remain.
pub const max_map_bytes: u64 = 1 << 32;
/// The fixed prefix: magic, version, six setting bytes, the default-branch
/// length, three counts, and the trailing checksum.
const min_file_bytes: usize = 8 + 2 + 6 + 8 + 2 + 3 * 8 + 4;
pub const ObjectFormat = enum(u8) {
sha1 = 0,
sha256 = 1,
/// The hex length of every OID in a repository of this format.
pub fn hexLen(self: ObjectFormat) usize {
return switch (self) {
.sha1 => 40,
.sha256 => 64,
};
}
};
/// Which identity a check-in's user and date come from.
pub const Attribution = enum(u8) { committer = 0, author = 1 };
/// The sub-manifest choice the first import resolved. Recorded resolved, not
/// as the user's request: a later import must keep the k the store already
/// uses, whatever an analysis would pick for the grown history.
pub const SubManifest = union(enum) {
flat,
tree: u4,
};
pub const Settings = struct {
submanifest: SubManifest,
attribution: Attribution,
refuse_signed: bool,
/// The Git branch whose history became `trunk`.
default_branch: []const u8,
};
pub const CommitRecord = struct {
/// The Git commit OID, lowercase hex of the source's object format.
oid: []const u8,
/// The zit check-in name, lowercase hex (40 or 64).
checkin: []const u8,
/// The branch label the check-in carries.
branch: []const u8,
/// Steps from the parentless root along first parents.
depth: u64,
/// The check-in's sub-manifest tree height.
height: u8,
};
pub const RefRecord = struct {
/// The full ref name, e.g. `refs/heads/main` or `refs/tags/v1`.
name: []const u8,
/// The OID it pointed at when last imported, lowercase hex.
oid: []const u8,
};
/// Everything the file holds, as borrowed slices. `write` serializes this;
/// a loaded `Map` exposes its own copy as `contents`, so a load followed by
/// a write round-trips without conversion.
pub const Contents = struct {
object_format: ObjectFormat,
/// The commits with no parents. Stable across clones and fetches, so a
/// later import compares these to refuse a different source. `write`
/// sorts them; `load` returns them strictly ascending.
roots: []const []const u8,
settings: Settings,
/// True when the first import retained or dropped any commit under the
/// Fossil-mirror classifier. Adding to such a DEST is refused, because
/// the classifier's decisions cannot be replayed against new commits.
mirror_classifier_fired: bool,
/// How many artifacts the destination's store held when this map was
/// written. A store that holds a different number has been written to
/// since, by a commit or a sync, and no longer matches the map.
artifact_count: u64,
commits: []const CommitRecord,
refs: []const RefRecord,
};
pub const LoadError = error{
Absent,
WrongMagic,
WrongVersion,
Truncated,
TooLarge,
LyingLength,
ChecksumMismatch,
/// An OID or check-in name that is not lowercase hex of an accepted
/// length, or a Git OID whose length disagrees with the object format.
BadHex,
/// A pinned sub-manifest k outside 1..12, or a nonzero k beside `flat`.
KOutOfRange,
/// An enum or boolean byte with no defined meaning.
UnknownEnum,
/// Roots not strictly ascending, or the same commit OID or ref name
/// recorded twice. The writer never produces either.
NotCanonical,
OutOfMemory,
};
pub const WriteError = error{
/// The contents would not load back; nothing was written.
InvalidContents,
OutOfMemory,
WriteFailed,
/// The map is in place but the directory could not be synced, so whether
/// the rename survives a power loss is unknown. The caller must not undo
/// anything on this error: the map already names the new state.
DurabilityUncertain,
};
/// A loaded map. Owns every slice; `deinit` frees them.
pub const Map = struct {
arena_state: std.heap.ArenaAllocator,
contents: Contents,
/// Git OID -> index into `contents.commits`.
by_oid: std.StringHashMapUnmanaged(usize),
/// Ref name -> index into `contents.refs`.
by_ref: std.StringHashMapUnmanaged(usize),
pub fn deinit(self: *Map) void {
self.arena_state.deinit();
self.* = undefined;
}
pub fn lookupOid(self: *const Map, oid: []const u8) ?*const CommitRecord {
const index = self.by_oid.get(oid) orelse return null;
return &self.contents.commits[index];
}
pub fn lookupRef(self: *const Map, name: []const u8) ?*const RefRecord {
const index = self.by_ref.get(name) orelse return null;
return &self.contents.refs[index];
}
};
/// Load and validate DEST's map. An absent file is `Absent`, the ordinary
/// state of a DEST no import has recorded, kept distinct from damage. Every
/// other failure is a distinct error and never a partial load.
pub fn load(gpa: std.mem.Allocator, io: std.Io, dest_dir: std.Io.Dir) LoadError!Map {
var file = dest_dir.openFile(io, map_filename, .{}) catch return error.Absent;
defer file.close(io);
const st = file.stat(io) catch return error.Absent;
if (st.size > max_map_bytes) return error.TooLarge;
const size = std.math.cast(usize, st.size) orelse return error.TooLarge;
var arena_state = std.heap.ArenaAllocator.init(gpa);
errdefer arena_state.deinit();
const arena = arena_state.allocator();
const bytes = arena.alloc(u8, size) catch return error.OutOfMemory;
const n = file.readPositionalAll(io, bytes, 0) catch return error.Truncated;
if (n != size) return error.Truncated;
const parsed = try parse(arena, bytes);
return .{
.arena_state = arena_state,
.contents = parsed.contents,
.by_oid = parsed.by_oid,
.by_ref = parsed.by_ref,
};
}
/// Serialize and atomically publish the map: a temp sibling, synced, renamed
/// over the member. The serialized bytes are parsed back first, so a map
/// `load` would reject is never published; the old file stays in place.
pub fn write(gpa: std.mem.Allocator, io: std.Io, dest_dir: std.Io.Dir, contents: Contents) WriteError!void {
var body: std.ArrayList(u8) = .empty;
defer body.deinit(gpa);
try serialize(gpa, &body, contents);
{
var scratch = std.heap.ArenaAllocator.init(gpa);
defer scratch.deinit();
_ = parse(scratch.allocator(), body.items) catch |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
else => return error.InvalidContents,
};
}
var af = dest_dir.createFileAtomic(io, map_filename, .{ .replace = true }) catch return error.WriteFailed;
defer af.deinit(io);
af.file.writePositionalAll(io, body.items, 0) catch return error.WriteFailed;
af.file.sync(io) catch return error.WriteFailed;
af.replace(io) catch return error.WriteFailed;
// The rename is durable only once the directory is: a power loss after
// the rename but before this would hand the next run the old map against
// a log that already holds the new frames.
storage.syncDirectory(io, dest_dir) catch return error.DurabilityUncertain;
}
const Parsed = struct {
contents: Contents,
by_oid: std.StringHashMapUnmanaged(usize),
by_ref: std.StringHashMapUnmanaged(usize),
};
/// Validate `bytes` and build the contents and indexes in `arena`. Slices
/// point into `bytes`, which the caller keeps alive alongside them.
fn parse(arena: std.mem.Allocator, bytes: []const u8) LoadError!Parsed {
var r = Cursor{ .bytes = bytes };
const got_magic = r.take(magic.len) orelse return error.Truncated;
if (!std.mem.eql(u8, got_magic, &magic)) return error.WrongMagic;
const version = r.int(u16) orelse return error.Truncated;
if (version != format_version) return error.WrongVersion;
if (bytes.len < min_file_bytes) return error.Truncated;
// The checksum covers every byte before it; validate it BEFORE trusting
// any length field the body carries.
const declared_crc = std.mem.readInt(u32, bytes[bytes.len - 4 ..][0..4], .little);
var crc = crc32.Crc32.init();
crc.update(bytes[0 .. bytes.len - 4]);
if (crc.final() != declared_crc) return error.ChecksumMismatch;
// From here every read stops short of the checksum.
r.bytes = bytes[0 .. bytes.len - 4];
const object_format: ObjectFormat = switch (r.int(u8) orelse return error.Truncated) {
0 => .sha1,
1 => .sha256,
else => return error.UnknownEnum,
};
const submanifest_tag = r.int(u8) orelse return error.Truncated;
const k = r.int(u8) orelse return error.Truncated;
const submanifest: SubManifest = switch (submanifest_tag) {
0 => if (k == 0) .flat else return error.KOutOfRange,
1 => if (k >= artifact.min_k and k <= artifact.max_k) .{ .tree = @intCast(k) } else return error.KOutOfRange,
else => return error.UnknownEnum,
};
const attribution: Attribution = switch (r.int(u8) orelse return error.Truncated) {
0 => .committer,
1 => .author,
else => return error.UnknownEnum,
};
const refuse_signed = try readBool(&r);
const mirror_classifier_fired = try readBool(&r);
const artifact_count = r.int(u64) orelse return error.Truncated;
const default_branch = r.lenPrefixed(u16) orelse return error.Truncated;
const oid_len = object_format.hexLen();
// Each count is bounded by the bytes that remain at the smallest legal
// record size before it may drive an allocation. The bound uses the
// smallest FRAMING, not the smallest valid field, so a short OID reports
// as BadHex rather than as a lying count.
const root_count = try boundedCount(&r, 1);
const roots = arena.alloc([]const u8, root_count) catch return error.OutOfMemory;
for (roots, 0..) |*root, i| {
root.* = r.lenPrefixed(u8) orelse return error.Truncated;
try checkHex(root.*, oid_len);
if (i > 0 and std.mem.order(u8, roots[i - 1], root.*) != .lt) return error.NotCanonical;
}
const commit_count = try boundedCount(&r, 1 + 1 + 2 + 8 + 1);
const commits = arena.alloc(CommitRecord, commit_count) catch return error.OutOfMemory;
var by_oid: std.StringHashMapUnmanaged(usize) = .empty;
by_oid.ensureTotalCapacity(arena, @intCast(commit_count)) catch return error.OutOfMemory;
for (commits, 0..) |*commit, index| {
commit.* = .{
.oid = r.lenPrefixed(u8) orelse return error.Truncated,
.checkin = r.lenPrefixed(u8) orelse return error.Truncated,
.branch = r.lenPrefixed(u16) orelse return error.Truncated,
.depth = r.int(u64) orelse return error.Truncated,
.height = r.int(u8) orelse return error.Truncated,
};
try checkHex(commit.oid, oid_len);
try checkHex(commit.checkin, null);
const slot = by_oid.getOrPutAssumeCapacity(commit.oid);
if (slot.found_existing) return error.NotCanonical;
slot.value_ptr.* = index;
}
const ref_count = try boundedCount(&r, 2 + 1);
const refs = arena.alloc(RefRecord, ref_count) catch return error.OutOfMemory;
var by_ref: std.StringHashMapUnmanaged(usize) = .empty;
by_ref.ensureTotalCapacity(arena, @intCast(ref_count)) catch return error.OutOfMemory;
for (refs, 0..) |*ref, index| {
ref.* = .{
.name = r.lenPrefixed(u16) orelse return error.Truncated,
.oid = r.lenPrefixed(u8) orelse return error.Truncated,
};
try checkHex(ref.oid, oid_len);
const slot = by_ref.getOrPutAssumeCapacity(ref.name);
if (slot.found_existing) return error.NotCanonical;
slot.value_ptr.* = index;
}
if (r.pos != r.bytes.len) return error.LyingLength; // exact accounting
return .{
.contents = .{
.object_format = object_format,
.roots = roots,
.settings = .{
.submanifest = submanifest,
.attribution = attribution,
.refuse_signed = refuse_signed,
.default_branch = default_branch,
},
.mirror_classifier_fired = mirror_classifier_fired,
.artifact_count = artifact_count,
.commits = commits,
.refs = refs,
},
.by_oid = by_oid,
.by_ref = by_ref,
};
}
fn readBool(r: *Cursor) LoadError!bool {
return switch (r.int(u8) orelse return error.Truncated) {
0 => false,
1 => true,
else => error.UnknownEnum,
};
}
/// Read a u64 count and refuse it unless that many records of at least
/// `min_record_bytes` each fit in what remains.
fn boundedCount(r: *Cursor, comptime min_record_bytes: usize) LoadError!usize {
const count = r.int(u64) orelse return error.Truncated;
if (count > (r.bytes.len - r.pos) / min_record_bytes) return error.LyingLength;
return std.math.cast(usize, count) orelse error.LyingLength;
}
/// Lowercase hex of exactly `len` digits, or of 40 or 64 when `len` is null.
fn checkHex(text: []const u8, len: ?usize) LoadError!void {
if (len) |want| {
if (text.len != want) return error.BadHex;
} else if (text.len != 40 and text.len != 64) return error.BadHex;
for (text) |c| switch (c) {
'0'...'9', 'a'...'f' => {},
else => return error.BadHex,
};
}
fn serialize(gpa: std.mem.Allocator, out: *std.ArrayList(u8), contents: Contents) WriteError!void {
const settings = contents.settings;
try out.appendSlice(gpa, &magic);
try appendInt(gpa, out, u16, format_version);
try out.append(gpa, @backingInt(contents.object_format));
switch (settings.submanifest) {
.flat => try out.appendSlice(gpa, &.{ 0, 0 }),
.tree => |k| try out.appendSlice(gpa, &.{ 1, @as(u8, k) }),
}
try out.append(gpa, @backingInt(settings.attribution));
try out.append(gpa, @intFromBool(settings.refuse_signed));
try out.append(gpa, @intFromBool(contents.mirror_classifier_fired));
try appendInt(gpa, out, u64, contents.artifact_count);
try appendLenPrefixed(gpa, out, u16, settings.default_branch);
// Roots go out sorted so the identity comparison is order-free and the
// file is canonical; the caller's slice is left as it was.
const roots = try gpa.dupe([]const u8, contents.roots);
defer gpa.free(roots);
std.mem.sort([]const u8, roots, {}, lessThan);
try appendInt(gpa, out, u64, roots.len);
for (roots) |root| try appendLenPrefixed(gpa, out, u8, root);
try appendInt(gpa, out, u64, contents.commits.len);
for (contents.commits) |commit| {
try appendLenPrefixed(gpa, out, u8, commit.oid);
try appendLenPrefixed(gpa, out, u8, commit.checkin);
try appendLenPrefixed(gpa, out, u16, commit.branch);
try appendInt(gpa, out, u64, commit.depth);
try out.append(gpa, commit.height);
}
try appendInt(gpa, out, u64, contents.refs.len);
for (contents.refs) |ref| {
try appendLenPrefixed(gpa, out, u16, ref.name);
try appendLenPrefixed(gpa, out, u8, ref.oid);
}
var crc = crc32.Crc32.init();
crc.update(out.items);
try appendInt(gpa, out, u32, crc.final());
}
fn lessThan(_: void, a: []const u8, b: []const u8) bool {
return std.mem.order(u8, a, b) == .lt;
}
fn appendInt(gpa: std.mem.Allocator, out: *std.ArrayList(u8), comptime T: type, v: T) error{OutOfMemory}!void {
var buf: [@sizeOf(T)]u8 = undefined;
std.mem.writeInt(T, &buf, v, .little);
try out.appendSlice(gpa, &buf);
}
/// A field too long for its prefix is the caller's error, not an assertion:
/// branch and ref names come from the source repository.
fn appendLenPrefixed(gpa: std.mem.Allocator, out: *std.ArrayList(u8), comptime L: type, bytes: []const u8) WriteError!void {
const len = std.math.cast(L, bytes.len) orelse return error.InvalidContents;
try appendInt(gpa, out, L, len);
try out.appendSlice(gpa, bytes);
}
/// Bounds-checked cursor: every read validates the remaining bytes first, so
/// a truncated or lying body yields null rather than an out-of-bounds slice.
const Cursor = struct {
bytes: []const u8,
pos: usize = 0,
fn take(self: *Cursor, n: usize) ?[]const u8 {
if (n > self.bytes.len - self.pos) return null;
const out = self.bytes[self.pos..][0..n];
self.pos += n;
return out;
}
fn int(self: *Cursor, comptime T: type) ?T {
const raw = self.take(@sizeOf(T)) orelse return null;
return std.mem.readInt(T, raw[0..@sizeOf(T)], .little);
}
fn lenPrefixed(self: *Cursor, comptime L: type) ?[]const u8 {
const len: usize = self.int(L) orelse return null;
return self.take(len);
}
};