//! The importer's per-object tables, shaped for a history of millions of
//! commits and tens of millions of blobs, where a hash map entry per object is
//! most of what an import retains.
const std = @import("std");
/// What a `git fast-export` mark names: a kind and a position in the record
/// list of that kind, packed into four bytes.
///
/// `git fast-export` numbers marks from 1 in stream order, so the table is an
/// array indexed by mark. A mark the array cannot reach without growing far
/// past the marks it holds -- a hand-written stream is free to number them
/// any way it likes -- goes to a hash map instead, which keeps the array's
/// size proportional to the marks actually seen.
pub const MarkTable = struct {
/// Index is the mark; 0 is "no mark".
dense: std.ArrayList(u32) = .empty,
sparse: std.AutoHashMapUnmanaged(u64, u32) = .empty,
entries: usize = 0,
pub const Kind = enum(u2) { blob = 1, commit = 2, tagged = 3 };
pub const Entry = struct { kind: Kind, index: u32 };
pub const max_index: u32 = (1 << 30) - 1;
/// How far past twice the marks held the array may grow to reach a mark.
const dense_reach: u64 = 1 << 16;
pub fn deinit(self: *MarkTable, gpa: std.mem.Allocator) void {
self.dense.deinit(gpa);
self.sparse.deinit(gpa);
self.* = undefined;
}
pub fn count(self: *const MarkTable) usize {
return self.entries;
}
pub fn contains(self: *const MarkTable, mark: u64) bool {
return self.get(mark) != null;
}
pub fn get(self: *const MarkTable, mark: u64) ?Entry {
// A mark first seen out of the array's reach stays in `sparse` after
// the array grows past it.
if (mark < self.dense.items.len) {
if (unpack(self.dense.items[mark])) |entry| return entry;
}
return unpack(self.sparse.get(mark) orelse return null);
}
/// Make room for `mark`, so `putAssumeReserved` cannot fail. Reserving
/// without putting leaves the table as it was.
pub fn reserve(self: *MarkTable, gpa: std.mem.Allocator, mark: u64) !void {
if (mark < self.dense.items.len) return;
if (!self.reachable(mark)) return self.sparse.ensureUnusedCapacity(gpa, 1);
const len: usize = @intCast(mark + 1);
try self.dense.ensureTotalCapacity(gpa, len);
self.dense.appendNTimesAssumeCapacity(0, len - self.dense.items.len);
}
/// `mark` must be reserved and absent; `index` at most `max_index`.
pub fn putAssumeReserved(self: *MarkTable, mark: u64, kind: Kind, index: usize) void {
std.debug.assert(index <= max_index);
std.debug.assert(!self.contains(mark));
const packed_entry = (@as(u32, @backingInt(kind)) << 30) | @as(u32, @intCast(index));
if (mark < self.dense.items.len) {
self.dense.items[mark] = packed_entry;
} else {
self.sparse.putAssumeCapacityNoClobber(mark, packed_entry);
}
self.entries += 1;
}
fn reachable(self: *const MarkTable, mark: u64) bool {
return mark <= 2 * @as(u64, self.entries) + dense_reach;
}
fn unpack(value: u32) ?Entry {
if (value == 0) return null;
return .{ .kind = @fromBackingInt(@intCast(value >> 30)), .index = value & max_index };
}
};
/// An append-only list whose elements never move, so a record may lend out
/// slices of itself. Growth allocates one more fixed chunk rather than copying
/// the list, which also keeps a large list from briefly needing twice its size.
pub fn StableList(comptime T: type, comptime chunk_len: usize) type {
return struct {
const Self = @This();
chunks: std.ArrayList(*[chunk_len]T) = .empty,
len: usize = 0,
pub fn deinit(self: *Self, gpa: std.mem.Allocator) void {
for (self.chunks.items) |chunk| gpa.destroy(chunk);
self.chunks.deinit(gpa);
self.* = undefined;
}
pub fn at(self: anytype, index: usize) switch (@TypeOf(self)) {
*Self => *T,
*const Self => *const T,
else => unreachable,
} {
std.debug.assert(index < self.len);
return &self.chunks.items[index / chunk_len][index % chunk_len];
}
pub fn ensureUnusedCapacity(self: *Self, gpa: std.mem.Allocator, n: usize) !void {
const want = std.math.divCeil(usize, self.len + n, chunk_len) catch unreachable;
if (want <= self.chunks.items.len) return;
try self.chunks.ensureTotalCapacity(gpa, want);
while (self.chunks.items.len < want) {
self.chunks.appendAssumeCapacity(try gpa.create([chunk_len]T));
}
}
/// Forget the last element. Its chunk stays for the next append.
pub fn pop(self: *Self) void {
std.debug.assert(self.len != 0);
self.len -= 1;
}
pub fn appendAssumeCapacity(self: *Self, value: T) void {
std.debug.assert(self.len < self.chunks.items.len * chunk_len);
self.len += 1;
self.at(self.len - 1).* = value;
}
};
}
test "marks in stream order land in the array" {
const gpa = std.testing.allocator;
var table: MarkTable = .{};
defer table.deinit(gpa);
for (1..1001) |mark| {
try table.reserve(gpa, mark);
table.putAssumeReserved(mark, if (mark % 3 == 0) .commit else .blob, mark * 2);
}
try std.testing.expectEqual(@as(usize, 1000), table.count());
try std.testing.expectEqual(@as(usize, 0), table.sparse.count());
try std.testing.expectEqual(MarkTable.Entry{ .kind = .commit, .index = 600 }, table.get(300).?);
try std.testing.expectEqual(MarkTable.Entry{ .kind = .blob, .index = 2000 }, table.get(1000).?);
try std.testing.expect(table.get(0) == null);
try std.testing.expect(table.get(1001) == null);
}
test "sparse and out-of-order marks resolve wherever they were stored" {
const gpa = std.testing.allocator;
var table: MarkTable = .{};
defer table.deinit(gpa);
const marks = [_]u64{ 500_000, 7, 3, 1 << 40, 2, 70_000, 1 };
for (marks, 0..) |mark, index| {
try std.testing.expect(!table.contains(mark));
try table.reserve(gpa, mark);
table.putAssumeReserved(mark, .tagged, index);
}
// The far marks went to the map; filling the gap below one later grows
// the array past it, and it must still resolve.
try std.testing.expect(table.sparse.count() >= 2);
for (8..300_000) |mark| {
try table.reserve(gpa, mark);
if (mark != 70_000) table.putAssumeReserved(mark, .blob, 0);
}
try table.reserve(gpa, 600_000);
table.putAssumeReserved(600_000, .commit, 3);
try std.testing.expect(table.dense.items.len > 500_000);
for (marks, 0..) |mark, index| {
try std.testing.expectEqual(MarkTable.Entry{ .kind = .tagged, .index = @intCast(index) }, table.get(mark).?);
}
try std.testing.expect(table.get(4) == null);
try std.testing.expect(table.get(499_999) == null);
}
test "a reused mark is seen as present" {
const gpa = std.testing.allocator;
var table: MarkTable = .{};
defer table.deinit(gpa);
try table.reserve(gpa, 5);
table.putAssumeReserved(5, .blob, 9);
try std.testing.expect(table.contains(5));
try table.reserve(gpa, 1 << 50);
table.putAssumeReserved(1 << 50, .commit, 1);
try std.testing.expect(table.contains(1 << 50));
// Reserving an existing mark changes nothing.
try table.reserve(gpa, 5);
try std.testing.expectEqual(MarkTable.Entry{ .kind = .blob, .index = 9 }, table.get(5).?);
try std.testing.expectEqual(@as(usize, 2), table.count());
}
test "the largest mark and the largest index round-trip" {
const gpa = std.testing.allocator;
var table: MarkTable = .{};
defer table.deinit(gpa);
const top = std.math.maxInt(u64);
try table.reserve(gpa, top);
table.putAssumeReserved(top, .commit, MarkTable.max_index);
try std.testing.expectEqual(MarkTable.Entry{ .kind = .commit, .index = MarkTable.max_index }, table.get(top).?);
try std.testing.expect(table.get(top - 1) == null);
try std.testing.expect(table.dense.items.len == 0);
}
test "a reservation that is never used leaves no entry" {
const gpa = std.testing.allocator;
var table: MarkTable = .{};
defer table.deinit(gpa);
try table.reserve(gpa, 40);
try std.testing.expectEqual(@as(usize, 0), table.count());
for (0..41) |mark| try std.testing.expect(table.get(mark) == null);
}
test "stable list elements keep their address across growth" {
const gpa = std.testing.allocator;
var list: StableList(u64, 4) = .{};
defer list.deinit(gpa);
try list.ensureUnusedCapacity(gpa, 1);
list.appendAssumeCapacity(10);
const first = list.at(0);
for (1..100) |value| {
try list.ensureUnusedCapacity(gpa, 1);
list.appendAssumeCapacity(value);
}
try std.testing.expectEqual(first, list.at(0));
try std.testing.expectEqual(@as(u64, 10), first.*);
try std.testing.expectEqual(@as(u64, 99), list.at(99).*);
try std.testing.expectEqual(@as(usize, 100), list.len);
}