//! The crosslink line counts: for each check-in, the lines each changed file
//! added and removed against the primary parent, in the order the record
//! lists the files.
//!
//! A check-in's counts are fixed by its name: the name fixes the manifest,
//! the manifest fixes the primary parent, and both fix every blob. So an
//! entry never goes stale as the log grows, and the only thing that can
//! invalidate one is a shun, which removes content the counts were read
//! from. The stored blob carries the shun fingerprint it was written under;
//! when the table has moved, the caller counts again only the check-ins a
//! shunned blob could have reached.
//!
//! Only counts that were fully computed are stored. A check-in with a file
//! whose content the store could not produce is stored as a placeholder, so
//! the entries stay in stream order. Content arrives only by appending to
//! the log, so the blob records how many log entries there were when it was
//! written, and a placeholder is counted again only once the log has grown.
//!
//! Entries are written in stream order, so a read walks them with a cursor
//! beside the records and builds no map; an index is built only if the two
//! orders ever part.
//!
//! Layout, little-endian: `magic[8] | version u16 | shun_fp u32 |
//! log_entries u64 |` then per
//! entry `name_len u8 | name | n u32 | n * (added u32, removed u32)`, where
//! `n` = 0xFFFFFFFF is the placeholder and carries no counts.
const std = @import("std");
const magic = "ZITLINES";
const format_version: u16 = 2;
pub const header_len = magic.len + 2 + 4 + 8;
const shun_fp_at = magic.len + 2;
const log_entries_at = shun_fp_at + 4;
const placeholder: u32 = std.math.maxInt(u32);
/// One file's counts. `binary` is `- -`; `unknown` is a side the store could
/// not produce, which prints nothing and is never stored.
pub const Count = struct {
added: u32,
removed: u32,
pub const binary: Count = .{ .added = std.math.maxInt(u32), .removed = std.math.maxInt(u32) };
pub const unknown: Count = .{ .added = std.math.maxInt(u32) - 1, .removed = std.math.maxInt(u32) - 1 };
/// Largest count a text file can carry; anything larger is clamped so it
/// can never read as a sentinel.
const max_text: u32 = std.math.maxInt(u32) - 2;
pub fn text(added: usize, removed: usize) Count {
return .{
.added = @intCast(@min(added, max_text)),
.removed = @intCast(@min(removed, max_text)),
};
}
pub fn eql(a: Count, b: Count) bool {
return a.added == b.added and a.removed == b.removed;
}
};
/// Builds a stored blob, entry by entry, in the order they are appended.
pub const Writer = struct {
out: std.ArrayList(u8) = .empty,
pub fn init(gpa: std.mem.Allocator, shun_fp: u32, log_entries: u64) error{OutOfMemory}!Writer {
var w: Writer = .{};
errdefer w.out.deinit(gpa);
try w.out.appendSlice(gpa, magic);
try appendInt(gpa, &w.out, u16, format_version);
try appendInt(gpa, &w.out, u32, shun_fp);
try appendInt(gpa, &w.out, u64, log_entries);
return w;
}
pub fn deinit(self: *Writer, gpa: std.mem.Allocator) void {
self.out.deinit(gpa);
}
/// Append `name`'s counts, or a placeholder when any is unknown. A name
/// too long for the layout is not stored and is counted on every read.
pub fn append(self: *Writer, gpa: std.mem.Allocator, name: []const u8, counts: []const Count) error{OutOfMemory}!void {
if (name.len > std.math.maxInt(u8)) return;
const complete = counts.len < placeholder and for (counts) |c| {
if (c.eql(Count.unknown)) break false;
} else true;
if (!complete) {
try self.out.ensureUnusedCapacity(gpa, 1 + name.len + 4);
self.out.appendAssumeCapacity(@intCast(name.len));
self.out.appendSliceAssumeCapacity(name);
appendIntAssumeCapacity(&self.out, u32, placeholder);
return;
}
try self.out.ensureUnusedCapacity(gpa, 1 + name.len + 4 + counts.len * 8);
self.out.appendAssumeCapacity(@intCast(name.len));
self.out.appendSliceAssumeCapacity(name);
appendIntAssumeCapacity(&self.out, u32, @intCast(counts.len));
for (counts) |c| {
appendIntAssumeCapacity(&self.out, u32, c.added);
appendIntAssumeCapacity(&self.out, u32, c.removed);
}
}
};
/// Reads a stored blob. `find` is answered from the cursor when the next
/// entry is the one asked for, which it is whenever the records come in the
/// order they were stored, and from an index built on first need otherwise.
/// A malformed entry ends the reading: every later `find` misses.
pub const Reader = struct {
bytes: []const u8,
at: usize = header_len,
/// Name to entry offset, built on the first out-of-order `find`.
index: ?std.StringHashMapUnmanaged(usize) = null,
broken: bool = false,
/// A reader over `bytes`, or null when they are not a blob of this
/// version.
pub fn open(bytes: []const u8) ?Reader {
if (bytes.len < header_len) return null;
if (!std.mem.eql(u8, bytes[0..magic.len], magic)) return null;
if (std.mem.readInt(u16, bytes[magic.len..][0..2], .little) != format_version) return null;
return .{ .bytes = bytes };
}
/// The shun fingerprint the blob was written under.
pub fn shunFp(self: *const Reader) u32 {
return std.mem.readInt(u32, self.bytes[shun_fp_at..][0..4], .little);
}
/// How many log entries there were when the blob was written.
pub fn logEntries(self: *const Reader) u64 {
return std.mem.readInt(u64, self.bytes[log_entries_at..][0..8], .little);
}
/// The same blob restamped with `shun_fp` and `log_entries`. Caller frees.
pub fn restamped(self: *const Reader, gpa: std.mem.Allocator, shun_fp: u32, log_entries: u64) error{OutOfMemory}![]u8 {
const copy = try gpa.dupe(u8, self.bytes);
std.mem.writeInt(u32, copy[shun_fp_at..][0..4], shun_fp, .little);
std.mem.writeInt(u64, copy[log_entries_at..][0..8], log_entries, .little);
return copy;
}
pub fn deinit(self: *Reader, gpa: std.mem.Allocator) void {
if (self.index) |*idx| idx.deinit(gpa);
}
pub const Found = enum { hit, recount, miss };
/// Whether the reader still walks entries in order, so that everything
/// before `at` is exactly what was found so far.
pub fn inOrder(self: *const Reader) bool {
return self.index == null and !self.broken;
}
/// Fill `out` with `name`'s counts: `hit`, or `recount` for a
/// placeholder, or `miss` when there is no entry.
pub fn find(self: *Reader, gpa: std.mem.Allocator, name: []const u8, out: *std.ArrayList(Count)) error{OutOfMemory}!Found {
if (self.broken) return .miss;
if (self.index == null) {
if (self.at < self.bytes.len) {
const e = self.entryAt(self.at) orelse return self.breakOff();
if (std.mem.eql(u8, e.name, name)) {
self.at = e.end;
return self.decode(gpa, e, out);
}
}
try self.buildIndex(gpa);
if (self.broken) return .miss;
}
const off = self.index.?.get(name) orelse return .miss;
return self.decode(gpa, self.entryAt(off).?, out);
}
const Entry = struct { name: []const u8, n: ?usize, counts_at: usize, end: usize };
fn entryAt(self: *const Reader, at: usize) ?Entry {
const b = self.bytes;
if (b.len - at < 1) return null;
const name_len: usize = b[at];
if (b.len - at - 1 < name_len + 4) return null;
const name = b[at + 1 ..][0..name_len];
const n_at = at + 1 + name_len;
const raw_n = std.mem.readInt(u32, b[n_at..][0..4], .little);
const counts_at = n_at + 4;
if (raw_n == placeholder) return .{ .name = name, .n = null, .counts_at = counts_at, .end = counts_at };
const n: usize = raw_n;
if (n > (b.len - counts_at) / 8) return null;
return .{ .name = name, .n = n, .counts_at = counts_at, .end = counts_at + n * 8 };
}
fn decode(self: *Reader, gpa: std.mem.Allocator, e: Entry, out: *std.ArrayList(Count)) error{OutOfMemory}!Found {
const n = e.n orelse return .recount;
out.clearRetainingCapacity();
try out.ensureTotalCapacity(gpa, n);
var p = e.counts_at;
for (0..n) |_| {
const c: Count = .{
.added = std.mem.readInt(u32, self.bytes[p..][0..4], .little),
.removed = std.mem.readInt(u32, self.bytes[p + 4 ..][0..4], .little),
};
if (c.eql(Count.unknown)) return self.breakOff();
out.appendAssumeCapacity(c);
p += 8;
}
return .hit;
}
fn buildIndex(self: *Reader, gpa: std.mem.Allocator) error{OutOfMemory}!void {
var idx: std.StringHashMapUnmanaged(usize) = .empty;
errdefer idx.deinit(gpa);
var at: usize = header_len;
while (at < self.bytes.len) {
const e = self.entryAt(at) orelse {
idx.deinit(gpa);
_ = self.breakOff();
return;
};
try idx.put(gpa, e.name, at);
at = e.end;
}
self.index = idx;
}
fn breakOff(self: *Reader) Found {
self.broken = true;
return .miss;
}
};
fn appendInt(gpa: std.mem.Allocator, out: *std.ArrayList(u8), comptime T: type, v: T) error{OutOfMemory}!void {
try out.ensureUnusedCapacity(gpa, @sizeOf(T));
appendIntAssumeCapacity(out, T, v);
}
fn appendIntAssumeCapacity(out: *std.ArrayList(u8), comptime T: type, v: T) void {
var buf: [@sizeOf(T)]u8 = undefined;
std.mem.writeInt(T, &buf, v, .little);
out.appendSliceAssumeCapacity(&buf);
}
const testing = std.testing;
fn sample(gpa: std.mem.Allocator, shun_fp: u32) ![]u8 {
var w = try Writer.init(gpa, shun_fp, 42);
errdefer w.deinit(gpa);
try w.append(gpa, "aa11", &.{ Count.text(12, 3), Count.binary });
try w.append(gpa, "bb22", &.{});
try w.append(gpa, "cc33", &.{ Count.text(1, 0), Count.unknown }); // a placeholder
try w.append(gpa, "dd44", &.{Count.text(0, 7)});
return w.out.toOwnedSlice(gpa);
}
test "linestats: entries read back in order, out of order, and not at all" {
const gpa = testing.allocator;
const bytes = try sample(gpa, 0xfeed);
defer gpa.free(bytes);
var out: std.ArrayList(Count) = .empty;
defer out.deinit(gpa);
var seq = Reader.open(bytes).?;
defer seq.deinit(gpa);
try testing.expectEqual(@as(u64, 42), seq.logEntries());
try testing.expectEqual(@as(u32, 0xfeed), seq.shunFp());
const later = try seq.restamped(gpa, 0xbeef, 43);
defer gpa.free(later);
try testing.expectEqual(@as(u64, 43), Reader.open(later).?.logEntries());
try testing.expectEqual(@as(u32, 0xbeef), Reader.open(later).?.shunFp());
try testing.expectEqual(Reader.Found.hit, try seq.find(gpa, "aa11", &out));
try testing.expectEqualSlices(Count, &.{ Count.text(12, 3), Count.binary }, out.items);
try testing.expectEqual(Reader.Found.hit, try seq.find(gpa, "bb22", &out));
try testing.expectEqual(@as(usize, 0), out.items.len);
try testing.expectEqual(Reader.Found.recount, try seq.find(gpa, "cc33", &out));
try testing.expectEqual(Reader.Found.hit, try seq.find(gpa, "dd44", &out));
try testing.expectEqualSlices(Count, &.{Count.text(0, 7)}, out.items);
try testing.expect(seq.inOrder()); // in order: no index was needed
try testing.expectEqual(Reader.Found.miss, try seq.find(gpa, "ee55", &out));
try testing.expectEqual(Reader.Found.hit, try seq.find(gpa, "aa11", &out)); // back again, by index
try testing.expectEqualSlices(Count, &.{ Count.text(12, 3), Count.binary }, out.items);
try testing.expect(!seq.inOrder());
}
test "linestats: a cut or foreign blob misses" {
const gpa = testing.allocator;
const bytes = try sample(gpa, 7);
defer gpa.free(bytes);
try testing.expect(Reader.open("not a blob") == null);
var out: std.ArrayList(Count) = .empty;
defer out.deinit(gpa);
// Cut anywhere inside the last entry: the entries before it still read,
// and the cut one is a miss rather than garbage.
const last = std.mem.lastIndexOf(u8, bytes, "dd44").? - 1;
var cut = last + 1;
while (cut < bytes.len) : (cut += 1) {
var r = Reader.open(bytes[0..cut]).?;
defer r.deinit(gpa);
try testing.expectEqual(Reader.Found.hit, try r.find(gpa, "aa11", &out));
try testing.expectEqual(Reader.Found.miss, try r.find(gpa, "dd44", &out));
}
}
test "linestats: text counts never collide with the sentinels" {
const huge = std.math.maxInt(usize);
try testing.expect(!Count.text(huge, huge).eql(Count.binary));
try testing.expect(!Count.text(huge, huge).eql(Count.unknown));
}
test "linestats: an out-of-order read is leak-free under allocation failure" {
const gpa = testing.allocator;
const bytes = try sample(gpa, 1);
defer gpa.free(bytes);
try testing.checkAllAllocationFailures(gpa, struct {
fn run(a: std.mem.Allocator, b: []const u8) !void {
var r = Reader.open(b).?;
defer r.deinit(a);
var out: std.ArrayList(Count) = .empty;
defer out.deinit(a);
if (try r.find(a, "dd44", &out) != .hit) return error.TestUnexpectedResult;
}
}.run, .{bytes});
}