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;
}
/// 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;
}