//! The thinned list: the names of file versions `zit purge artifacts` removed
//! from this store on purpose.
//!
//! A thinned version is not damage and not a takedown. It was dropped because
//! the operator chose not to keep it, so three things need to know its name
//! after the bytes are gone:
//!
//! * the readers (`cat`, `diff`, `annotate`), which say "purged" and exit 8
//! instead of calling the absence missing;
//! * pull, which must not ask a peer for it again, nor count it among the
//! artifacts a pull did not obtain;
//! * serve, which must not beg a pushing peer for it nor store a copy one
//! sends.
//!
//! LOCAL by design, like the graveyard: it is never an artifact, never in the
//! shun configuration group, never in a clone reply. Thinning is a retention
//! choice of THIS store; a peer that thins nothing keeps every version. It sits
//! beside the store (`.zit-thinned`), so a pack, which rewrites only the store
//! file, and an obliterate, which rewrites only the graveyard, both leave it as
//! it was: the bytes are gone for good after an obliterate, and the name must
//! go on being refused.
//!
//! Format: one lowercase-hex artifact name per line, ascending, each 40 or 64
//! characters. Plain text so an operator can read it; any other line is
//! `error.Corrupt` rather than being skipped, because a name skipped here is a
//! version the next pull silently fetches back.
const std = @import("std");
pub const filename: []const u8 = ".zit-thinned";
/// TigerStyle bound: a list longer than this is not a retention schedule this
/// format was sized for. Each line is at most 65 bytes, so the file stays
/// under 70 MiB.
pub const max_names: usize = 1 << 20;
const max_line: usize = 65;
pub const Error = error{ Storage, Corrupt, OutOfMemory, Full };
/// The thinned names, owned. Empty is the common case and allocates nothing.
pub const Set = struct {
names: std.StringHashMapUnmanaged(void) = .empty,
pub fn deinit(self: *Set, gpa: std.mem.Allocator) void {
var it = self.names.keyIterator();
while (it.next()) |k| gpa.free(k.*);
self.names.deinit(gpa);
self.* = undefined;
}
/// Whether `name` (any case, complete width) is thinned here.
pub fn contains(self: *const Set, name: []const u8) bool {
if (self.names.count() == 0) return false;
if (!completeWidth(name.len)) return false;
var buf: [64]u8 = undefined;
return self.names.contains(std.ascii.lowerString(buf[0..name.len], name));
}
pub fn count(self: *const Set) usize {
return self.names.count();
}
fn put(self: *Set, gpa: std.mem.Allocator, name: []const u8) Error!void {
if (self.contains(name)) return;
if (self.names.count() >= max_names) return error.Full;
const owned = try gpa.alloc(u8, name.len);
errdefer gpa.free(owned);
_ = std.ascii.lowerString(owned, name);
try self.names.put(gpa, owned, {});
}
fn drop(self: *Set, gpa: std.mem.Allocator, name: []const u8) void {
if (!completeWidth(name.len)) return;
var buf: [64]u8 = undefined;
const kv = self.names.fetchRemove(std.ascii.lowerString(buf[0..name.len], name)) orelse return;
gpa.free(kv.key);
}
};
fn completeWidth(len: usize) bool {
return len == 40 or len == 64;
}
fn isName(s: []const u8) bool {
if (!completeWidth(s.len)) return false;
for (s) |c| switch (c) {
'0'...'9', 'a'...'f' => {},
else => return false,
};
return true;
}
/// Every thinned name beside the store in `dir`. An absent file is the empty
/// set; a damaged one is `Corrupt`, never empty.
pub fn load(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir) Error!Set {
const raw = dir.readFileAlloc(io, filename, gpa, .limited(max_names * max_line)) catch |e| switch (e) {
error.FileNotFound => return .{},
error.OutOfMemory => return error.OutOfMemory,
error.StreamTooLong => return error.Corrupt,
else => return error.Storage,
};
defer gpa.free(raw);
var set: Set = .{};
errdefer set.deinit(gpa);
var lines = std.mem.splitScalar(u8, raw, '\n');
while (lines.next()) |line| {
if (line.len == 0) continue;
if (!isName(line)) return error.Corrupt;
try set.put(gpa, line);
}
return set;
}
/// Whether `name` is thinned beside the store in `dir`. A list that cannot be
/// read answers false: this is the readers' question, and a reader that cannot
/// tell why content is absent says it is missing, which is still true.
pub fn contains(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, name: []const u8) bool {
var set = load(gpa, io, dir) catch return false;
defer set.deinit(gpa);
return set.contains(name);
}
/// Record `names` as thinned. Idempotent per name.
pub fn add(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, names: []const []const u8) Error!void {
var set = try load(gpa, io, dir);
defer set.deinit(gpa);
for (names) |n| {
if (!isNameAnyCase(n)) return error.Corrupt;
try set.put(gpa, n);
}
try write(gpa, io, dir, &set);
}
/// Forget `names`: `purge undo` restored their content. Names not in the list
/// are ignored, so an undo of a `purge checkins` event changes nothing here.
pub fn remove(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, names: []const []const u8) Error!void {
var set = try load(gpa, io, dir);
defer set.deinit(gpa);
const before = set.count();
for (names) |n| set.drop(gpa, n);
if (set.count() == before) return;
try write(gpa, io, dir, &set);
}
fn isNameAnyCase(s: []const u8) bool {
if (!completeWidth(s.len)) return false;
for (s) |c| if (!std.ascii.isHex(c)) return false;
return true;
}
fn lessThan(_: void, a: []const u8, b: []const u8) bool {
return std.mem.lessThan(u8, a, b);
}
/// Rewrite the list to exactly `set`: write-temp, fsync, rename, the graveyard's
/// sequence. An empty set removes the file.
fn write(gpa: std.mem.Allocator, io: std.Io, dir: std.Io.Dir, set: *const Set) Error!void {
if (set.count() == 0) {
dir.deleteFile(io, filename) catch |e| switch (e) {
error.FileNotFound => {},
else => return error.Storage,
};
return;
}
const sorted = try gpa.alloc([]const u8, set.count());
defer gpa.free(sorted);
var it = set.names.keyIterator();
var i: usize = 0;
while (it.next()) |k| : (i += 1) sorted[i] = k.*;
std.mem.sort([]const u8, sorted, {}, lessThan);
var buf: std.ArrayList(u8) = .empty;
defer buf.deinit(gpa);
for (sorted) |n| {
try buf.appendSlice(gpa, n);
try buf.append(gpa, '\n');
}
var af = dir.createFileAtomic(io, filename, .{ .replace = true }) catch return error.Storage;
defer af.deinit(io);
af.file.writePositionalAll(io, buf.items, 0) catch return error.Storage;
af.file.sync(io) catch return error.Storage;
af.replace(io) catch return error.Storage;
}
const testing = std.testing;
const repeat = @import("repeat.zig").repeat;
test "thinned: names round-trip, add is idempotent, remove forgets only what it names" {
const gpa = testing.allocator;
const io = testing.io;
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
const a = repeat("ab", 32);
const b = repeat("cd", 20);
try add(gpa, io, tmp.dir, &.{ a, b });
try add(gpa, io, tmp.dir, &.{a});
{
var set = try load(gpa, io, tmp.dir);
defer set.deinit(gpa);
try testing.expectEqual(@as(usize, 2), set.count());
try testing.expect(set.contains(a));
try testing.expect(set.contains(b));
// Case does not bypass the list: the wire may spell a name in upper case.
var upper: [64]u8 = undefined;
try testing.expect(set.contains(std.ascii.upperString(&upper, a)));
try testing.expect(!set.contains(repeat("ef", 32)));
// A prefix is never a hit.
try testing.expect(!set.contains(a[0..12]));
}
try remove(gpa, io, tmp.dir, &.{ a, repeat("ef", 32) });
try testing.expect(!contains(gpa, io, tmp.dir, a));
try testing.expect(contains(gpa, io, tmp.dir, b));
// Emptied, the file goes, so a store with nothing thinned carries nothing.
try remove(gpa, io, tmp.dir, &.{b});
try testing.expectError(error.FileNotFound, tmp.dir.statFile(io, filename, .{}));
}
test "thinned: a damaged list is Corrupt, never empty" {
const gpa = testing.allocator;
const io = testing.io;
var tmp = testing.tmpDir(.{});
defer tmp.cleanup();
var empty = try load(gpa, io, tmp.dir);
empty.deinit(gpa);
try tmp.dir.writeFile(io, .{ .sub_path = filename, .data = "not a name\n" });
try testing.expectError(error.Corrupt, load(gpa, io, tmp.dir));
// The readers' question answers false rather than failing.
try testing.expect(!contains(gpa, io, tmp.dir, repeat("ab", 32)));
}