//! 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 repostate = @import("../repostate.zig");
const repository = @import("../repository.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);
}