Artifact 5bacebff321c914fb3955f5b4774fb2a6a7143ed4910dc6c1ed6036ac7acc154:
- File
src/submanifest_partition.zig
— part of check-in
[db4b2573e7]
at
2026-08-15 12:10:03
on branch trunk
— import-git: O(changes) per-commit cost and live progress (#65)
Tree edits adopt untouched sibling leaves, the tree witness digest is structural over the root S-run (flat digests unchanged), and log reads go through a primed plaintext cache. Ingest reports strided progress with pack/verify phase markers. (user: dmestas, size: 6080) [annotate] [blame] [check-ins using]
const std = @import("std"); /// Streaming implementation of draft-fossil-submanifests-00 §6.2 grouping. /// /// The partitioner retains only boundaries and final-group state. Callers own /// the ordered values; no filename or node slice is retained after `push`. pub const CanonicalPartitioner = struct { allocator: std.mem.Allocator, threshold: u16, min: usize, max: usize, count: usize = 0, bounds: std.ArrayList(usize) = .empty, /// A cursor into a surviving suffix plus the delayed final-group decision. /// Absolute input positions deliberately do not participate in equivalence: /// insertions and deletes shift them while leaving canonical continuation /// unchanged. pub const Checkpoint = struct { next_key: ?[]const u8, open_members: usize, predecessor_members: usize, final_merge_pending: bool, pub fn equivalent(a: Checkpoint, b: Checkpoint) bool { return std.mem.eql(u8, a.next_key orelse "", b.next_key orelse "") and (a.next_key == null) == (b.next_key == null) and a.open_members == b.open_members and a.predecessor_members == b.predecessor_members and a.final_merge_pending == b.final_merge_pending; } }; pub fn init( allocator: std.mem.Allocator, threshold: u16, min: usize, max: usize, ) CanonicalPartitioner { std.debug.assert(max >= 1); return .{ .allocator = allocator, .threshold = threshold, .min = min, .max = max, }; } pub fn deinit(self: *CanonicalPartitioner) void { self.bounds.deinit(self.allocator); self.* = undefined; } /// Add the next ordered key. `zero_bits` is supplied by the caller so this /// internal module remains independent of artifact parsing and hashing. pub fn push(self: *CanonicalPartitioner, zero_bits: u16) std.mem.Allocator.Error!bool { if (self.count == 0) { try self.bounds.append(self.allocator, 0); self.count = 1; return false; } const open = self.count - self.bounds.items[self.bounds.items.len - 1]; std.debug.assert(open >= 1 and open <= self.max); const boundary = open == self.max or (zero_bits >= self.threshold and open >= self.min); if (boundary) try self.bounds.append(self.allocator, self.count); self.count += 1; return boundary; } /// #65 — splice one already-partitioned group (an adopted old leaf) into /// the sequence WITHOUT replaying its members: close whatever group is /// open at the current position and account `members` keys to the /// adopted group. Sound because nothing ever reads a group's interior — /// later boundary decisions consult only the OPEN group's size, and the /// checkpoint/finish logic consults only the last two bounds — so the /// one count that must be true is the LAST adopted group's (the next /// streamed push's boundary decision reads it); callers pass a /// placeholder for earlier groups in a run. Precondition: the caller has /// proven (checkpoint equivalence) that the current position is a /// boundary of the adopted sequence. pub fn adoptGroup(self: *CanonicalPartitioner, members: usize) std.mem.Allocator.Error!void { std.debug.assert(members >= 1); std.debug.assert(self.count > 0); // adoption always follows a streamed region if (self.bounds.items[self.bounds.items.len - 1] != self.count) { try self.bounds.append(self.allocator, self.count); } self.count += members; } /// Capture the state needed to prove that a suffix can be reused. `next_key` /// names the next surviving item (or null at EOF), never an absolute ordinal. pub fn checkpoint(self: *const CanonicalPartitioner, next_key: ?[]const u8) Checkpoint { if (self.count == 0) return .{ .next_key = next_key, .open_members = 0, .predecessor_members = 0, .final_merge_pending = false, }; const start = self.bounds.items[self.bounds.items.len - 1]; const predecessor_start = if (self.bounds.items.len >= 2) self.bounds.items[self.bounds.items.len - 2] else start; const open = self.count - start; return .{ .next_key = next_key, .open_members = open, .predecessor_members = if (self.bounds.items.len >= 2) start - predecessor_start else 0, .final_merge_pending = self.bounds.items.len >= 2 and open < self.min, }; } /// Finalization is the sole home of final-short-group merging. pub fn finish(self: *CanonicalPartitioner) std.mem.Allocator.Error![]const usize { if (self.count == 0) return &.{}; if (self.bounds.items.len >= 2) { const last = self.bounds.items[self.bounds.items.len - 1]; const prev = self.bounds.items[self.bounds.items.len - 2]; if (self.count - last < self.min and self.count - prev <= self.max) { self.bounds.items.len -= 1; } } try self.bounds.append(self.allocator, self.count); const result = try self.bounds.toOwnedSlice(self.allocator); self.bounds = .empty; return result; } }; /// Partition an already sorted list of keys at one tree height. pub fn groups( allocator: std.mem.Allocator, keys: []const []const u8, threshold: u16, min: usize, max: usize, zero_bits: *const fn ([]const u8) u16, ) std.mem.Allocator.Error![]const usize { var partitioner = CanonicalPartitioner.init(allocator, threshold, min, max); defer partitioner.deinit(); for (keys) |key| _ = try partitioner.push(zero_bits(key)); return partitioner.finish(); } pub fn groupCount(bounds: []const usize) usize { std.debug.assert(bounds.len >= 2); return bounds.len - 1; }