//! Export planning and enumeration: the topological frontier over
//! `RepoState` (every parent before every child, the §8.3 timeline order as
//! the deterministic tiebreak among ready check-ins, mark-mapped prefixes
//! excluded), and the ONE seam through which the exporter consumes file
//! sets. Translation to fast-import commands builds on these (Task 5).
const std = @import("std");
const artifact = @import("../artifact.zig");
const repostate = @import("../repostate.zig");
const repository = @import("../repository.zig");
const fast_export = @import("git_fast_export.zig");
/// The "already exported" predicate the planner consults — a `MirrorState`
/// in production, a seeded set or nothing in tests. An interface rather than
/// the concrete state so planning stays pure over `RepoState`.
pub const AlreadyExported = struct {
context: ?*const anyopaque,
containsFn: *const fn (context: ?*const anyopaque, hash: []const u8) bool,
pub fn contains(self: AlreadyExported, hash: []const u8) bool {
return self.containsFn(self.context, hash);
}
};
/// Nothing exported yet — the full-export predicate.
pub const NoneExported = struct {
fn never(_: ?*const anyopaque, _: []const u8) bool {
return false;
}
pub fn predicate(_: *NoneExported) AlreadyExported {
return .{ .context = null, .containsFn = never };
}
};
/// A hash-set-backed predicate (tests, and the state adapter's shape).
pub const SetExported = struct {
hashes: std.StringHashMapUnmanaged(void) = .empty,
pub fn deinit(self: *SetExported, gpa: std.mem.Allocator) void {
self.hashes.deinit(gpa);
}
fn containsImpl(context: ?*const anyopaque, hash: []const u8) bool {
const self: *const SetExported = @ptrCast(@alignCast(context.?));
return self.hashes.contains(hash);
}
pub fn predicate(self: *SetExported) AlreadyExported {
return .{ .context = self, .containsFn = containsImpl };
}
};
/// Plan the export: every UNEXPORTED check-in, ordered so each parent
/// precedes each child (Kahn over `parentsOf` restricted to check-ins), with
/// the §8.3 timeline order (oldest first) breaking ties among ready nodes —
/// so two runs over one repository plan identically. A parent that is
/// already exported, or is a phantom the state never crosslinked, counts as
/// satisfied rather than blocking. Every structure is bounded by the
/// check-in count. Caller frees the returned slice.
pub fn plan(
gpa: std.mem.Allocator,
rs: *const repostate.RepoState,
already: AlreadyExported,
) error{OutOfMemory}![]repostate.Rid {
// Timeline rank: position in OLDEST-first order — the deterministic
// tiebreak. `checkinsByMtime` is newest-first, so rank reverses it.
const timeline = try rs.checkinsByMtime(gpa);
defer gpa.free(timeline);
var rank_of: std.AutoHashMapUnmanaged(repostate.Rid, u32) = .empty;
defer rank_of.deinit(gpa);
try rank_of.ensureTotalCapacity(gpa, @intCast(timeline.len));
for (timeline, 0..) |rid, newest_first_index| {
const rank: u32 = @intCast(timeline.len - 1 - newest_first_index);
rank_of.putAssumeCapacity(rid, rank);
}
// Indegree over UNEXPORTED planned nodes, and a local children multimap
// (repostate's adjacency serves parent walks; the planner needs the
// other direction only transiently).
var indegree: std.AutoHashMapUnmanaged(repostate.Rid, u32) = .empty;
defer indegree.deinit(gpa);
var children: std.AutoHashMapUnmanaged(repostate.Rid, std.ArrayListUnmanaged(repostate.Rid)) = .empty;
defer {
var it = children.valueIterator();
while (it.next()) |list| list.deinit(gpa);
children.deinit(gpa);
}
for (timeline) |rid| {
if (already.contains(rs.store.hashOf(rid))) continue;
var degree: u32 = 0;
var it = rs.parentsOf(rid);
while (it.next()) |parent| {
if (rs.mtimeOf(parent) == null) continue; // phantom: never planned
if (already.contains(rs.store.hashOf(parent))) continue; // satisfied
degree += 1;
const gop = try children.getOrPut(gpa, parent);
if (!gop.found_existing) gop.value_ptr.* = .empty;
try gop.value_ptr.append(gpa, rid);
}
try indegree.put(gpa, rid, degree);
}
const Ready = struct {
fn lessThan(context: *const std.AutoHashMapUnmanaged(repostate.Rid, u32), a: repostate.Rid, b: repostate.Rid) std.math.Order {
return std.math.order(context.get(a).?, context.get(b).?);
}
};
var ready = std.PriorityQueue(repostate.Rid, *const std.AutoHashMapUnmanaged(repostate.Rid, u32), Ready.lessThan).initContext(&rank_of);
defer ready.deinit(gpa);
var degrees = indegree.iterator();
while (degrees.next()) |entry| {
if (entry.value_ptr.* == 0) try ready.push(gpa, entry.key_ptr.*);
}
var out: std.ArrayList(repostate.Rid) = .empty;
errdefer out.deinit(gpa);
while (ready.pop()) |rid| {
try out.append(gpa, rid);
const kids = children.getPtr(rid) orelse continue;
for (kids.items) |child| {
const degree = indegree.getPtr(child).?;
degree.* -= 1;
if (degree.* == 0) try ready.push(gpa, child);
}
}
// A hash DAG cannot cycle, so the plan covers every unexported check-in.
std.debug.assert(out.items.len == indegree.count());
return out.toOwnedSlice(gpa);
}
/// The §9.3 seam, named once: the exporter's ONLY file-set source is
/// `Repository.files` — the same flatten-behind-a-resolver,
/// memoized-sub-manifest, baseline-merging enumeration every verb reads
/// (flat, S-card tree, and delta manifests alike; §5.2 hard failures
/// propagate as the fail-closed export errors they are). Kept as a named
/// wrapper so the seam-discipline sweep has a single site to audit.
pub fn enumerate(
repo: *repository.Repository,
gpa: std.mem.Allocator,
rid: repostate.Rid,
) repository.Repository.FilesError!?repository.Repository.FileList {
return repo.files(gpa, rid);
}
// ---------------------------------------------------------------------------
// Translation: check-ins to fast-import events (Task 5).
// ---------------------------------------------------------------------------
pub const TranslateError = error{
OutOfMemory,
/// §5.2 hard failure or an unreadable artifact — the fail-closed export
/// posture: the error NAMES the check-in (see `Translator.fault`).
EnumerationFailed,
/// A file path no Git tree may carry: `.git`, `.`, `..`, or an empty
/// segment. Named in `Translator.fault`.
ForbiddenPath,
/// A parent this commit references was neither planned before it nor
/// recorded in the mark map — a planner/state invariant violation.
ParentUnmapped,
/// A file card whose blob content the store cannot produce.
BlobUnreadable,
/// The primary parent's manifest content is missing (a phantom — an
/// incomplete clone, shunned or private upstream content): the diff has
/// nothing to diff against, so the lineage cannot export. Named with the
/// parent's hash in .
ParentUnreadable,
};
/// What a refused translation names: the artifact and (when path-shaped) the
/// offending path. The translator has no output channel; the CLI formats.
pub const Fault = struct {
hash: [64]u8 = undefined,
hash_len: u8 = 0,
path: [512]u8 = undefined,
path_len: usize = 0,
fn setHash(self: *Fault, hash: []const u8) void {
const n = @min(hash.len, self.hash.len);
@memcpy(self.hash[0..n], hash[0..n]);
self.hash_len = @intCast(n);
}
fn setPath(self: *Fault, path: []const u8) void {
const n = @min(path.len, self.path.len);
@memcpy(self.path[0..n], path[0..n]);
self.path_len = n;
}
pub fn hashText(self: *const Fault) []const u8 {
return self.hash[0..self.hash_len];
}
pub fn pathText(self: *const Fault) []const u8 {
return self.path[0..self.path_len];
}
};
/// One translated commit: the blob and commit events to stream, arena-owned.
/// Draining and deiniting this is the caller's ONLY retention — the
/// translator itself keeps one (hash, mark) per commit and one mark per
/// distinct blob, never a file list or card slice (the importer's
/// `CommitMarkState` discipline, mirrored).
pub const TranslatedCommit = struct {
arena_state: std.heap.ArenaAllocator,
events: []const fast_export.Event,
/// The mark assigned to this commit — the caller records it against the
/// check-in hash once the session confirms the stream landed.
mark: u64,
pub fn deinit(self: *TranslatedCommit) void {
self.arena_state.deinit();
self.* = undefined;
}
};
pub const Translator = struct {
gpa: std.mem.Allocator,
/// The synthesized-identity email domain (`login@DOMAIN`).
email_domain: []const u8 = "zit.invalid",
/// Marks handed out, monotonically. Mark 0 is never used (fast-import
/// reserves the meaning "no mark").
next_mark: u64 = 1,
/// Distinct blob content hash -> mark. Global by content addressing —
/// exactly the reuse the stream needs to emit each blob once.
blob_marks: std.StringHashMapUnmanaged(u64) = .empty,
/// Exported check-in hash -> ObjectRef text: a mark from THIS run, or a
/// recorded OID from the state file on incremental runs.
commit_refs: std.StringHashMapUnmanaged(fast_export.ObjectRef) = .empty,
/// Owned copies backing the two maps' keys (and recorded OIDs).
owned: std.ArrayListUnmanaged([]const u8) = .empty,
/// The refusal detail for the most recent error return.
fault: Fault = .{},
pub fn init(gpa: std.mem.Allocator) Translator {
return .{ .gpa = gpa };
}
pub fn deinit(self: *Translator) void {
self.blob_marks.deinit(self.gpa);
self.commit_refs.deinit(self.gpa);
for (self.owned.items) |bytes| self.gpa.free(bytes);
self.owned.deinit(self.gpa);
self.* = undefined;
}
/// The constant-state observable: entries retained across commits. One
/// per exported commit plus one per distinct blob — never proportional
/// to file-set width.
pub fn retainedStateEntries(self: *const Translator) usize {
return self.blob_marks.count() + self.commit_refs.count();
}
fn retain(self: *Translator, bytes: []const u8) error{OutOfMemory}![]const u8 {
const copy = try self.gpa.dupe(u8, bytes);
errdefer self.gpa.free(copy);
try self.owned.append(self.gpa, copy);
return copy;
}
/// Seed a commit's ref from the state file (incremental runs): parents
/// exported by a PRIOR run resolve by recorded OID instead of a mark.
pub fn seedExported(self: *Translator, hash: []const u8, oid: []const u8) error{OutOfMemory}!void {
const owned_hash = try self.retain(hash);
const owned_oid = try self.retain(oid);
try self.commit_refs.put(self.gpa, owned_hash, .{ .oid = owned_oid });
}
/// Translate one planned check-in into its blob + commit events. The
/// file-set diff runs against the PRIMARY parent's seam enumeration
/// (re-read, never retained); a parentless check-in emits `deleteall`
/// plus its full set. Fail-closed: any §8 refusal names the check-in and
/// path in `fault` and returns its precise error.
pub fn translateCommit(
self: *Translator,
repo: *repository.Repository,
rid: repostate.Rid,
) TranslateError!TranslatedCommit {
const gpa = self.gpa;
const hash = repo.hashOf(rid);
self.fault = .{};
self.fault.setHash(hash);
var arena_state = std.heap.ArenaAllocator.init(gpa);
errdefer arena_state.deinit();
const arena = arena_state.allocator();
var events: std.ArrayList(fast_export.Event) = .empty;
var owned_manifest = (repo.manifest(gpa, rid) catch return error.EnumerationFailed) orelse return error.EnumerationFailed;
defer owned_manifest.deinit(gpa);
const m = &owned_manifest.manifest;
// Primary parent (first hash of the first P card), if any.
var parent_hash_buf: [64]u8 = undefined;
var primary_parent: ?[]const u8 = null;
if (m.p.len > 0) {
var it = m.p[0].hashes();
if (it.next()) |first| {
@memcpy(parent_hash_buf[0..first.len], first);
primary_parent = parent_hash_buf[0..first.len];
}
}
// Both enumerations, filename-ordered by §8.1; a single merge walk
// yields adds/changes/deletes.
var current = (enumerate(repo, gpa, rid) catch return error.EnumerationFailed) orelse return error.EnumerationFailed;
defer current.deinit(gpa);
var commands: std.ArrayList(fast_export.FileCommand) = .empty;
if (primary_parent) |parent_hex| {
const parent_rid = repo.lookup(parent_hex) orelse return error.ParentUnmapped;
var parent_files = (enumerate(repo, gpa, parent_rid) catch {
self.fault.setPath(parent_hex);
return error.ParentUnreadable;
}) orelse {
self.fault.setPath(parent_hex);
return error.ParentUnreadable;
};
defer parent_files.deinit(gpa);
try self.diffInto(arena, repo, &events, &commands, &parent_files, ¤t);
} else {
try commands.append(arena, .delete_all);
var it = current.iterator();
while (it.next()) |card| {
try self.modifyFor(arena, repo, &events, &commands, card);
}
}
// Parent refs in P-run order: `from` is the primary, the rest merge.
var from: ?fast_export.ObjectRef = null;
var merges: std.ArrayList(fast_export.ObjectRef) = .empty;
for (m.p) |pcard| {
var it = pcard.hashes();
while (it.next()) |parent| {
const ref = self.commit_refs.get(parent) orelse {
self.fault.setPath(parent);
return error.ParentUnmapped;
};
const duped: fast_export.ObjectRef = switch (ref) {
.mark => |mk| .{ .mark = mk },
.oid => |oid| .{ .oid = try arena.dupe(u8, oid) },
};
if (from == null) from = duped else try merges.append(arena, duped);
}
}
// C/D/U -> message, timestamp, synthesized identity.
const login: []const u8 = if (m.u) |u| u.login else "unknown";
const email = try std.fmt.allocPrint(arena, "{s}@{s}", .{ login, self.email_domain });
const seconds: i64 = blk: {
const d = m.d orelse break :blk 0;
const ms = repostate.parseMtime(d.timestamp) orelse break :blk 0;
break :blk @intCast(@divTrunc(ms, 1000));
};
const identity: fast_export.Identity = .{
.name = try arena.dupe(u8, login),
.email = email,
.timestamp = seconds,
.timezone_offset_minutes = 0,
};
const message: []const u8 = if (m.c) |c| try arena.dupe(u8, c.comment) else "";
const branch = repo.state().branchOf(rid, repo.mainBranch());
const ref_name = try refForBranch(arena, branch);
const mark = self.next_mark;
self.next_mark += 1;
try events.append(arena, .{ .commit = .{
.ref = ref_name,
.mark = mark,
.original_oid = null,
.author = identity,
.committer = identity,
.message = message,
.from = from,
.merges = merges.items,
.commands = commands.items,
} });
// Retain exactly one (hash, mark) for this commit.
const owned_hash = try self.retain(hash);
try self.commit_refs.put(gpa, owned_hash, .{ .mark = mark });
return .{
.arena_state = arena_state,
.events = events.items,
.mark = mark,
};
}
fn diffInto(
self: *Translator,
arena: std.mem.Allocator,
repo: *repository.Repository,
events: *std.ArrayList(fast_export.Event),
commands: *std.ArrayList(fast_export.FileCommand),
parent_files: *const repository.Repository.FileList,
current: *const repository.Repository.FileList,
) TranslateError!void {
var old_it = parent_files.iterator();
var new_it = current.iterator();
var old = old_it.next();
var new = new_it.next();
while (old != null or new != null) {
const order: std.math.Order = if (old == null)
.gt
else if (new == null)
.lt
else
artifact.compareBytes(old.?.filename, new.?.filename);
switch (order) {
.lt => {
// Present in the parent only: deleted.
try commands.append(arena, .{ .delete = try arena.dupe(u8, old.?.filename) });
old = old_it.next();
},
.gt => {
try self.modifyFor(arena, repo, events, commands, new.?);
new = new_it.next();
},
.eq => {
const same_hash = std.mem.eql(u8, old.?.hash orelse "", new.?.hash orelse "");
const same_mode = old.?.mode == new.?.mode;
if (!same_hash or !same_mode) {
try self.modifyFor(arena, repo, events, commands, new.?);
}
old = old_it.next();
new = new_it.next();
},
}
}
}
fn modifyFor(
self: *Translator,
arena: std.mem.Allocator,
repo: *repository.Repository,
events: *std.ArrayList(fast_export.Event),
commands: *std.ArrayList(fast_export.FileCommand),
card: artifact.FCard,
) TranslateError!void {
try validatePathForGit(&self.fault, card.filename);
const content_hash = card.hash orelse {
self.fault.setPath(card.filename);
return error.BlobUnreadable;
};
const mark = try self.blobMarkFor(arena, repo, events, content_hash, card.filename);
try commands.append(arena, .{ .modify = .{
.mode = switch (card.mode) {
.regular => .regular,
.executable => .executable,
.symlink => .symlink,
},
.data = .{ .mark = mark },
.path = try arena.dupe(u8, card.filename),
} });
}
/// The blob's mark: existing on content-hash reuse, else read the bytes
/// through the store, emit the blob event, and record the new mark.
fn blobMarkFor(
self: *Translator,
arena: std.mem.Allocator,
repo: *repository.Repository,
events: *std.ArrayList(fast_export.Event),
content_hash: []const u8,
path: []const u8,
) TranslateError!u64 {
if (self.blob_marks.get(content_hash)) |existing| return existing;
const bytes = (repo.blob(arena, content_hash) catch {
self.fault.setPath(path);
return error.BlobUnreadable;
}) orelse {
self.fault.setPath(path);
return error.BlobUnreadable;
};
const mark = self.next_mark;
self.next_mark += 1;
try events.append(arena, .{ .blob = .{ .mark = mark, .original_oid = null, .data = bytes } });
const owned_hash = try self.retain(content_hash);
try self.blob_marks.put(self.gpa, owned_hash, mark);
return mark;
}
};
/// §8 path policing: a Git tree may not carry `.git` (case-insensitive), `.`,
/// `..`, or an empty segment. The seam already excluded reserved Fossil
/// names; these are Git's own refusals, checked per exported path.
pub fn validatePathForGit(fault: *Fault, path: []const u8) TranslateError!void {
if (path.len == 0) {
fault.setPath(path);
return error.ForbiddenPath;
}
var it = std.mem.splitScalar(u8, path, '/');
while (it.next()) |segment| {
const forbidden = segment.len == 0 or
std.mem.eql(u8, segment, ".") or
std.mem.eql(u8, segment, "..") or
std.ascii.eqlIgnoreCase(segment, ".git");
if (forbidden) {
fault.setPath(path);
return error.ForbiddenPath;
}
}
}
/// `refs/heads/<sanitized branch>`, sanitized per git-check-ref-format's
/// component rules, locally (no `git` subprocess): control bytes, space,
/// `~ ^ : ? * [ \` and DEL become `-`; a leading `.` or `-`, a trailing
/// `.`, and the sequences `..` and `@{` are broken with `-`; `.lock` at the
/// end is suffixed. Deterministic, total, and never empty.
pub fn refForBranch(arena: std.mem.Allocator, branch: []const u8) error{OutOfMemory}![]const u8 {
var name: std.ArrayList(u8) = .empty;
try name.appendSlice(arena, "refs/heads/");
const base = name.items.len;
for (branch) |byte| {
const bad = byte < 0x20 or byte == 0x7f or byte == ' ' or byte == '~' or
byte == '^' or byte == ':' or byte == '?' or byte == '*' or byte == '[' or byte == '\\';
var next: u8 = if (bad) '-' else byte;
const n = name.items.len;
if (next == '.' and (n == base or name.items[n - 1] == '.' or name.items[n - 1] == '/')) next = '-';
if (next == '{' and n > base and name.items[n - 1] == '@') next = '-';
if (next == '-' and n == base) {
try name.append(arena, '_');
continue;
}
try name.append(arena, next);
}
if (name.items.len == base) try name.appendSlice(arena, "unnamed");
if (name.items[name.items.len - 1] == '.') name.items[name.items.len - 1] = '-';
if (std.mem.endsWith(u8, name.items, ".lock")) try name.append(arena, '-');
return name.toOwnedSlice(arena);
}