tiny.sql.History

1pub const History = struct {2    pub const ByteRange = struct {3        pub const Count = u64;4        pub const unit_precision_bytes: Count = 1;5        pub const maximum_units_per_second: Count = 512 * 1024 * 1024;6        pub const maximum_seconds_per_year: Count = 366 * 24 * 60 * 60;7        pub const service_lifetime_years: Count = 1_000;8        pub const service_lifetime_seconds: Count =9            maximum_seconds_per_year * service_lifetime_years;10        pub const maximum_append_bytes: Count =11            @as(Count, record_mod.record_header_size) + std.math.maxInt(u32);12        pub const budget_bytes: Count = total(13            maximum_units_per_second,14            service_lifetime_seconds,15        ).?;1617        pub fn total(18            units_per_second: Count,19            lifetime_seconds: Count,20        ) ?Count {21            const bytes_per_second = std.math.mul(22                Count,23                unit_precision_bytes,24                units_per_second,25            ) catch return null;26            return std.math.mul(Count, bytes_per_second, lifetime_seconds) catch null;27        }28    };2930    comptime {31        std.debug.assert(32            @as(u128, ByteRange.budget_bytes) +33                @as(u128, ByteRange.maximum_append_bytes) <=34                std.math.maxInt(ByteRange.Count),35        );36        std.debug.assert(@bitSizeOf(usize) >= @bitSizeOf(ByteRange.Count));37    }3839    allocator: Allocator,40    io: std.Io,41    file: ?std.Io.File = null,42    read_only: bool = false,43    sidecar_dir: ?std.Io.Dir = null,44    sidecar_path: ?[]u8 = null,45    /// The length of the history file once pending records are written.46    /// The file holds every byte before the pending records and nothing47    /// after them, so writing them ends the file where the write stops.48    bytes_written: usize = 0,49    recovery: Recovery = .clean,50    needs_sync: bool = false,51    write_batch_depth: usize = 0,52    pending_write: std.ArrayList(u8) = .empty,53    write_io: WriteIo = .{},54    fast_forward: ?FastForwardRecovery = null,55    recovery_required: bool = false,56    database_roots: std.ArrayList(record_mod.DatabaseRootRecord) = .empty,57    relation_roots: std.ArrayList(record_mod.RelationRootRecord) = .empty,58    materialized_relation_roots: std.ArrayList(record_mod.MaterializedRelationRoot) = .empty,59    relation_rows: std.ArrayList(record_mod.RelationRowsRecord) = .empty,60    relation_spans: std.ArrayList(record_mod.RelationSpansRecord) = .empty,61    row_chunks: std.ArrayList(record_mod.RowChunkRecord) = .empty,62    index_pages: std.ArrayList(record_mod.IndexPageRecord) = .empty,63    tree_nodes: std.ArrayList(record_mod.TreeNodeRecord) = .empty,64    commits: std.ArrayList(record_mod.CommitRecord) = .empty,65    refs: std.ArrayList(record_mod.RefRecord) = .empty,66    conflicts: std.ArrayList(record_mod.ConflictRecord) = .empty,67    conflict_roots: std.ArrayList(record_mod.ConflictRootRecord) = .empty,68    lookup: RecordLookup = .{},6970    pub const SuffixPlan = struct {71        reused: usize,72        boundary: i64,73    };7475    pub const RowsNeed = union(enum) {76        none,77        full,78        suffix: SuffixPlan,79    };8081    pub fn open(allocator: Allocator, dir: std.Io.Dir, options: Options) Error!History {82        var history = History{83            .allocator = allocator,84            .io = options.io,85            .read_only = options.read_only,86        };87        errdefer history.deinit();8889        const recorded_length: ?usize = if (dir.statFile(options.io, options.path, .{})) |stat|90            @intCast(stat.size)91        else |err| switch (err) {92            error.FileNotFound => if (options.create) null else return error.HistoryNotFound,93            else => return err,94        };9596        history.file = if (options.read_only)97            try dir.openFile(options.io, options.path, .{})98        else99            try dir.createFile(options.io, options.path, .{ .read = true, .truncate = false });100        if (!options.read_only) {101            if (dir.openDir(options.io, ".", .{})) |owned_dir| {102                history.sidecar_dir = owned_dir;103                history.sidecar_path = try allocator.dupe(u8, options.path);104            } else |_| {}105        }106        if (recorded_length) |length| {107            history.bytes_written = try recover_mod.replayFile(108                &history,109                length,110                options.replay_instrumentation,111                options.control,112            );113            if (length != history.bytes_written) {114                if (options.read_only or options.recovery == .reject) return error.TruncatedHistory;115                try history.file.?.setLength(options.io, history.bytes_written);116                try history.file.?.sync(options.io);117                history.recovery = .{ .truncated = .{118                    .original_length = length,119                    .valid_length = history.bytes_written,120                } };121            }122            history.refreshRefsSidecar();123        }124        return history;125    }126127    pub fn deinit(self: *History) void {128        if (self.file) |*file| {129            if (!self.recovery_required) {130                if (self.pending_write.items.len != 0) self.flushPendingWrite() catch {};131                if (self.needs_sync) file.sync(self.io) catch {};132            }133            file.close(self.io);134        }135        if (self.sidecar_dir) |*dir| dir.close(self.io);136        if (self.sidecar_path) |path| self.allocator.free(path);137        for (self.database_roots.items) |*record| record.deinit();138        for (self.materialized_relation_roots.items) |*record| record.deinit();139        for (self.relation_rows.items) |*record| record.deinit(self.allocator);140        for (self.relation_spans.items) |*record| record.deinit(self.allocator);141        for (self.index_pages.items) |*record| record.deinit(self.allocator);142        for (self.commits.items) |*record| record.deinit(self.allocator);143        for (self.refs.items) |*record| record.deinit(self.allocator);144        for (self.conflicts.items) |*record| record.deinit(self.allocator);145        for (self.conflict_roots.items) |*record| record.deinit(self.allocator);146        self.database_roots.deinit(self.allocator);147        self.relation_roots.deinit(self.allocator);148        self.materialized_relation_roots.deinit(self.allocator);149        self.relation_rows.deinit(self.allocator);150        self.relation_spans.deinit(self.allocator);151        self.row_chunks.deinit(self.allocator);152        self.index_pages.deinit(self.allocator);153        self.tree_nodes.deinit(self.allocator);154        self.commits.deinit(self.allocator);155        self.refs.deinit(self.allocator);156        self.conflicts.deinit(self.allocator);157        self.conflict_roots.deinit(self.allocator);158        self.lookup.deinit(self.allocator);159        self.pending_write.deinit(self.allocator);160        self.* = undefined;161    }162163    pub fn putDatabaseRoot(self: *History, root: version.DatabaseRoot) Error!void {164        try self.ensureUsable();165        if (self.findDatabaseRoot(root.hash) != null) return;166        var owned = try root.clone(self.allocator);167        errdefer owned.deinit();168        try self.database_roots.ensureUnusedCapacity(self.allocator, 1);169        try self.lookup.database_roots.ensureUnusedCapacity(self.allocator, 1);170        try self.appendDatabaseRootRecord(owned);171        self.lookup.database_roots.putAssumeCapacity(owned.hash, self.database_roots.items.len);172        self.database_roots.appendAssumeCapacity(.{ .root = owned });173        try self.flushSync();174    }175176    pub fn putRelationRoot(self: *History, root: version.RelationRoot) Error!void {177        try self.ensureUsable();178        if (self.hasRelationRoot(root.hash)) return;179        var owned = try root.clone(self.allocator);180        var owned_transferred = false;181        errdefer if (!owned_transferred) owned.deinit();182        var stage = NodeStage.init(self);183        defer stage.deinit();184        const index_keys = try self.allocator.alloc(?version.Hash, owned.indexes.len);185        var index_keys_owned = true;186        errdefer if (index_keys_owned) self.allocator.free(index_keys);187        const table_key = try stage.mapKey(&owned.table);188        for (owned.indexes, index_keys) |*index, *index_key| index_key.* = try stage.mapKey(&index.map);189        try stage.flush();190        try self.relation_roots.ensureUnusedCapacity(self.allocator, 1);191        try self.materialized_relation_roots.ensureUnusedCapacity(self.allocator, 1);192        try self.lookup.relation_roots.ensureUnusedCapacity(self.allocator, 1);193        try self.appendRelationRootRecord(owned, table_key, index_keys);194        materialize_mod.shrinkRelationRootMaps(self.allocator, &owned);195        self.lookup.relation_roots.putAssumeCapacity(owned.hash, self.relation_roots.items.len);196        self.relation_roots.appendAssumeCapacity(.{197            .hash = owned.hash,198            .storage = .{ .materialized = self.materialized_relation_roots.items.len },199        });200        self.materialized_relation_roots.appendAssumeCapacity(.{201            .root = owned,202            .table_key = table_key,203            .index_keys = index_keys,204        });205        owned_transferred = true;206        index_keys_owned = false;207        try self.flushSync();208    }209210    pub fn putRelationRows(self: *History, root: version.Hash, rows: []const version.RelationRow) Error!void {211        try self.ensureUsable();212        if (self.hasRelationRows(root)) return;213        const sorted = try self.allocator.dupe(version.RelationRow, rows);214        defer if (sorted.len != 0) self.allocator.free(sorted);215        std.mem.sort(version.RelationRow, sorted, {}, version.relationRowLessThan);216        var writer = try self.beginRelationRows(root);217        defer writer.deinit();218        for (sorted) |row_value| try writer.append(row_value.rowid, row_value.bytes);219        try writer.finish();220    }221222    pub fn beginRelationRows(self: *History, root: version.Hash) Error!RelationRowsWriter {223        try self.ensureMutable();224        std.debug.assert(!self.hasRelationRows(root));225        return .{ .history = self, .root = root, .boundary = null };226    }227228    pub fn beginRelationRowsSuffix(229        self: *History,230        root: version.Hash,231        base: IncrementalBase,232        plan: SuffixPlan,233    ) Error!RelationRowsWriter {234        try self.ensureUsable();235        std.debug.assert(!self.hasRelationRows(root));236        var base_pages = (try self.relationRowsPages(self.allocator, base.root)) orelse return error.InvalidHistory;237        defer base_pages.deinit();238        var base_spans = (try self.relationSpans(self.allocator, base.root)) orelse return error.InvalidHistory;239        defer base_spans.deinit();240        if (plan.reused == 0 or plan.reused >= base_spans.items.len) return error.InvalidHistory;241        if (base_spans.items[plan.reused - 1].last != plan.boundary) return error.InvalidHistory;242243        const base_chunks = try self.baseChunkList(self.allocator, base_pages.items);244        defer if (base_chunks.len != 0) self.allocator.free(base_chunks);245        if (base_chunks.len != base_spans.items.len) return error.InvalidHistory;246247        var writer = RelationRowsWriter{ .history = self, .root = root, .boundary = plan.boundary };248        errdefer writer.deinit();249        try writer.chunks.appendSlice(self.allocator, base_chunks[0..plan.reused]);250        try writer.spans.appendSlice(self.allocator, base_spans.items[0..plan.reused]);251        return writer;252    }253254    pub fn relationRowsNeed(self: *const History, allocator: Allocator, root: version.Hash, base: ?IncrementalBase) Error!RowsNeed {255        try self.ensureUsable();256        if (self.hasRelationRows(root)) return .none;257        const info = base orelse return .full;258        var base_pages = (try self.relationRowsPages(allocator, info.root)) orelse return .full;259        defer base_pages.deinit();260        var base_spans = (try self.relationSpans(allocator, info.root)) orelse return .full;261        defer base_spans.deinit();262        if (base_spans.items.len == 0) return .full;263        const base_chunks = try self.baseChunkList(allocator, base_pages.items);264        defer allocator.free(base_chunks);265        if (base_chunks.len != base_spans.items.len) return .full;266267        const first_affected = firstAffectedSpan(base_spans.items, info.edited);268        if (first_affected == 0) return .full;269        return .{ .suffix = .{270            .reused = first_affected,271            .boundary = base_spans.items[first_affected - 1].last,272        } };273    }274275    pub fn putRelationRowsSuffix(self: *History, root: version.Hash, base: IncrementalBase, plan: SuffixPlan, tail: []const version.RelationRow) Error!void {276        try self.ensureUsable();277        if (self.hasRelationRows(root)) return;278        if (!relationRowsSorted(tail)) return error.InvalidHistory;279        var writer = try self.beginRelationRowsSuffix(root, base, plan);280        defer writer.deinit();281        for (tail) |row_value| try writer.append(row_value.rowid, row_value.bytes);282        try writer.finish();283    }284285    pub fn finishRelationRows(self: *History, root: version.Hash, chunks: []const version.Hash, spans: []const record_mod.ChunkSpan) Error!void {286        try self.ensureUsable();287        const page_bounds = try chunk_mod.pageBoundaries(self.allocator, chunks);288        defer if (page_bounds.len != 0) self.allocator.free(page_bounds);289        const pages = try self.allocator.alloc(version.Hash, page_bounds.len);290        errdefer if (pages.len != 0) self.allocator.free(pages);291        for (page_bounds, pages) |bound, *digest| {292            const slice = chunks[bound.start..bound.end];293            digest.* = chunk_mod.pageDigest(slice);294            try self.putIndexPage(digest.*, slice);295        }296        try self.relation_rows.ensureUnusedCapacity(self.allocator, 1);297        try self.lookup.relation_rows.ensureUnusedCapacity(self.allocator, 1);298        try self.appendRelationRowsRecord(root, pages);299        self.lookup.relation_rows.putAssumeCapacity(root, self.relation_rows.items.len);300        self.relation_rows.appendAssumeCapacity(.{301            .root = root,302            .storage = .{ .materialized = pages },303        });304        try self.putRelationSpans(root, spans);305        try self.flushSync();306    }307308    pub fn relationSpans(self: *const History, allocator: Allocator, hash: version.Hash) Error!?record_mod.ChunkSpanView {309        try self.ensureUsable();310        const index = self.lookup.relation_spans.get(hash) orelse return null;311        const record = &self.relation_spans.items[index];312        return try materialize_mod.readRelationSpansRecord(self, allocator, record.root, record.storage);313    }314315    pub fn putRelationSpans(self: *History, root: version.Hash, spans: []const record_mod.ChunkSpan) Error!void {316        try self.ensureUsable();317        if (self.lookup.relation_spans.get(root) != null) return;318        const owned = try self.allocator.dupe(record_mod.ChunkSpan, spans);319        errdefer self.allocator.free(owned);320        try self.relation_spans.ensureUnusedCapacity(self.allocator, 1);321        try self.lookup.relation_spans.ensureUnusedCapacity(self.allocator, 1);322        try self.appendRelationSpansRecord(root, owned);323        self.lookup.relation_spans.putAssumeCapacity(root, self.relation_spans.items.len);324        self.relation_spans.appendAssumeCapacity(.{325            .root = root,326            .storage = .{ .materialized = owned },327        });328    }329330    pub fn appendRelationSpansRecord(self: *History, root: version.Hash, spans: []const record_mod.ChunkSpan) Error!void {331        try self.ensureUsable();332        if (spans.len > std.math.maxInt(u32)) return error.InvalidHistory;333        var payload: std.ArrayList(u8) = .empty;334        defer payload.deinit(self.allocator);335        try record_mod.appendHash(self.allocator, &payload, root);336        try record_mod.appendU32(self.allocator, &payload, @intCast(spans.len));337        for (spans) |span| {338            try record_mod.appendU64(self.allocator, &payload, @as(u64, @bitCast(span.first)));339            try record_mod.appendU64(self.allocator, &payload, @as(u64, @bitCast(span.last)));340        }341        try self.appendRecord(.relation_spans, payload.items);342    }343344    pub fn baseChunkList(self: *const History, allocator: Allocator, pages: []const version.Hash) Error![]version.Hash {345        try self.ensureUsable();346        var chunks: std.ArrayList(version.Hash) = .empty;347        errdefer chunks.deinit(allocator);348        for (pages) |page_digest| {349            var page = (try self.indexPageChunks(allocator, page_digest)) orelse return error.InvalidHistory;350            defer page.deinit();351            try chunks.appendSlice(allocator, page.items);352        }353        return try chunks.toOwnedSlice(allocator);354    }355356    pub fn putRowChunk(self: *History, digest: version.Hash, rows: []const version.RelationRow) Error!void {357        try self.ensureUsable();358        if (self.findRowChunk(digest) != null) return;359        var payload: std.ArrayList(u8) = .empty;360        defer payload.deinit(self.allocator);361        try record_mod.appendHash(self.allocator, &payload, digest);362        try record_mod.appendRelationRows(self.allocator, &payload, rows);363        try self.row_chunks.ensureUnusedCapacity(self.allocator, 1);364        try self.lookup.row_chunks.ensureUnusedCapacity(self.allocator, 1);365        const payload_offset = self.bytes_written + record_mod.record_header_size;366        const expected = record_mod.recordHash(@backingInt(record_mod.RecordKind.row_chunk), payload.items);367        try self.appendRecord(.row_chunk, payload.items);368        self.lookup.row_chunks.putAssumeCapacity(digest, self.row_chunks.items.len);369        self.row_chunks.appendAssumeCapacity(.{370            .digest = digest,371            .payload = .{372                .expected = expected,373                .offset = payload_offset,374                .len = payload.items.len,375            },376        });377    }378379    pub fn putIndexPage(self: *History, digest: version.Hash, chunks: []const version.Hash) Error!void {380        try self.ensureUsable();381        if (self.hasIndexPage(digest)) return;382        const owned = try self.allocator.dupe(version.Hash, chunks);383        errdefer self.allocator.free(owned);384        try self.index_pages.ensureUnusedCapacity(self.allocator, 1);385        try self.lookup.index_pages.ensureUnusedCapacity(self.allocator, 1);386        try self.appendChunkIndexPageRecord(digest, owned);387        self.lookup.index_pages.putAssumeCapacity(digest, self.index_pages.items.len);388        self.index_pages.appendAssumeCapacity(.{389            .digest = digest,390            .storage = .{ .materialized = owned },391        });392    }393394    pub fn putDatabaseValue(self: *History, value: *const version.DatabaseValue) Error!void {395        try self.ensureUsable();396        var batch = try self.beginWriteBatch();397        errdefer batch.deinit();398        for (value.relations) |relation| {399            try self.putRelationRoot(relation.root);400            try self.putRelationRows(relation.root.hash, relation.rows);401        }402        try self.putDatabaseRoot(value.root);403        try batch.finish();404    }405406    pub fn putCommit(self: *History, commit: version.Commit) Error!void {407        try self.ensureUsable();408        const canonical = version.Commit.init(commit.root, commit.parents);409        if (self.findCommit(canonical.hash) != null) return;410        const parents = try self.allocator.dupe(version.Hash, commit.parents);411        errdefer self.allocator.free(parents);412        try self.commits.ensureUnusedCapacity(self.allocator, 1);413        try self.lookup.commits.ensureUnusedCapacity(self.allocator, 1);414        try self.appendCommitRecord(canonical.root, parents);415        try self.flushSync();416        self.lookup.commits.putAssumeCapacity(canonical.hash, self.commits.items.len);417        self.commits.appendAssumeCapacity(.{418            .parents = parents,419            .commit = .{420                .root = canonical.root,421                .parents = parents,422                .hash = canonical.hash,423            },424        });425    }426427    pub fn putRef(self: *History, ref_value: version.Ref) Error!void {428        try self.ensureUsable();429        if (self.findCommit(ref_value.target) == null) return error.CommitNotFound;430        if (self.findRef(ref_value.name)) |record| {431            try self.appendRefRecord(ref_value.name, ref_value.target);432            try self.flushSync();433            record.ref.target = ref_value.target;434            self.refreshRefsSidecar();435            return;436        }437438        const name = try self.allocator.dupe(u8, ref_value.name);439        errdefer self.allocator.free(name);440        try self.refs.ensureUnusedCapacity(self.allocator, 1);441        try self.appendRefRecord(name, ref_value.target);442        try self.flushSync();443        self.refs.appendAssumeCapacity(.{444            .name = name,445            .ref = .{446                .name = name,447                .target = ref_value.target,448            },449        });450        self.refreshRefsSidecar();451    }452453    pub fn putRefIfMatches(self: *History, ref_value: version.Ref, expected: ?version.Hash) Error!void {454        try self.ensureUsable();455        if (self.findCommit(ref_value.target) == null) return error.CommitNotFound;456        if (self.findRef(ref_value.name)) |record| {457            const expected_hash = expected orelse return error.RefChanged;458            if (!version.same(record.ref.target, expected_hash)) return error.RefChanged;459        } else if (expected != null) {460            return error.RefChanged;461        }462        try self.putRef(ref_value);463    }464465    pub fn beginFastForward(466        self: *History,467        name: []const u8,468        expected: version.Hash,469        target: version.Hash,470    ) Error!FastForwardUpdate {471        try self.ensureUsable();472        if (self.fast_forward != null) return error.RecoveryRequired;473        if (self.pending_write.items.len != 0 or474            self.needs_sync or475            self.write_batch_depth != 0)476        {477            self.poison();478            return error.RecoveryRequired;479        }480        const ref_record = self.findRef(name) orelse return error.RefNotFound;481        if (!version.same(ref_record.ref.target, expected)) return error.RefChanged;482        if (self.findCommit(expected) == null or self.findCommit(target) == null) {483            return error.CommitNotFound;484        }485        var payload: std.ArrayList(u8) = .empty;486        defer payload.deinit(self.allocator);487        try record_mod.appendBytes(self.allocator, &payload, name);488        try record_mod.appendHash(self.allocator, &payload, expected);489        try record_mod.appendHash(self.allocator, &payload, target);490        const id = record_mod.recordHash(491            @backingInt(record_mod.RecordKind.fast_forward_prepare),492            payload.items,493        );494        try self.appendCoordinatorRecord(.fast_forward_prepare, payload.items);495        self.fast_forward = .{496            .id = id,497            .name = ref_record.name,498            .expected = expected,499            .target = target,500        };501        return .{ .history = self, .id = id };502    }503504    pub fn fastForwardRecovery(self: *const History) ?*const FastForwardRecovery {505        return if (self.fast_forward) |*recovery| recovery else null;506    }507508    pub fn poison(self: *History) void {509        self.recovery_required = true;510    }511512    pub fn requiresRecovery(self: *const History) bool {513        return self.recovery_required;514    }515516    fn decideFastForward(517        self: *History,518        id: version.Hash,519        decision: FastForwardDecision,520    ) Error!void {521        try self.ensureUsable();522        const recovery = if (self.fast_forward) |*active| active else return error.InvalidHistory;523        if (!version.same(recovery.id, id) or recovery.decision != .pending) {524            return error.InvalidHistory;525        }526        const ref_record = self.findRef(recovery.name) orelse return error.InvalidHistory;527        if (!version.same(ref_record.ref.target, recovery.expected)) return error.InvalidHistory;528        const kind: record_mod.RecordKind = switch (decision) {529            .pending => return error.InvalidHistory,530            .baseline => .fast_forward_abort,531            .target => .fast_forward_commit,532        };533        try self.appendCoordinatorHashRecord(kind, id);534        if (decision == .target) ref_record.ref.target = recovery.target;535        recovery.decision = decision;536    }537538    fn completeFastForward(self: *History, id: version.Hash) Error!void {539        try self.ensureUsable();540        const recovery = if (self.fast_forward) |*active| active else return error.InvalidHistory;541        if (!version.same(recovery.id, id) or recovery.decision == .pending) {542            return error.InvalidHistory;543        }544        const ref_record = self.findRef(recovery.name) orelse return error.InvalidHistory;545        const selected = switch (recovery.decision) {546            .pending => unreachable,547            .baseline => recovery.expected,548            .target => recovery.target,549        };550        if (!version.same(ref_record.ref.target, selected)) return error.InvalidHistory;551        try self.appendCoordinatorHashRecord(.fast_forward_complete, id);552        self.fast_forward = null;553        self.refreshRefsSidecar();554    }555556    fn ensureUsable(self: *const History) Error!void {557        if (self.recovery_required) return error.RecoveryRequired;558    }559560    fn ensureMutable(self: *const History) Error!void {561        try self.ensureUsable();562        if (self.read_only) return error.ReadOnly;563        if (self.fast_forward != null) return error.RecoveryRequired;564    }565566    pub fn deleteRef(self: *History, name: []const u8) Error!void {567        try self.ensureUsable();568        const index = self.findRefIndex(name) orelse return error.RefNotFound;569        try self.appendRefDeleteRecord(name);570        try self.flushSync();571        var removed = self.refs.orderedRemove(index);572        removed.deinit(self.allocator);573        self.refreshRefsSidecar();574    }575576    pub fn createBranch(self: *History, name: []const u8, target: version.Hash) Error!version.Ref {577        try self.ensureUsable();578        if (self.findRef(name) != null) return error.RefExists;579        if (self.findCommit(target) == null) return error.CommitNotFound;580        const ref_value = version.Ref{581            .name = name,582            .target = target,583        };584        try self.putRef(ref_value);585        return (try self.ref(name)).?;586    }587588    pub fn checkoutBranch(self: *const History, name: []const u8) Error!branch.Checkout {589        try self.ensureUsable();590        const record = self.findRef(name) orelse return error.RefNotFound;591        const commit = self.findCommit(record.ref.target) orelse return error.CommitNotFound;592        return branch.checkout(record.ref, commit.commit.root);593    }594595    pub fn fastForwardBranch(self: *History, allocator: Allocator, name: []const u8, target: version.Hash) Error!void {596        try self.ensureUsable();597        const record = self.findRef(name) orelse return error.RefNotFound;598        var ref_value = record.ref;599        const entries = try self.commitEntries(allocator);600        defer allocator.free(entries);601        try branch.fastForwardRef(allocator, entries, &ref_value, target);602        try self.putRef(ref_value);603    }604605    pub fn commitBranch(self: *History, name: []const u8, root: version.Hash) Error!version.Hash {606        try self.ensureUsable();607        const record = self.findRef(name) orelse return error.RefNotFound;608        if (self.findCommit(record.ref.target) == null) return error.CommitNotFound;609        var parents = [_]version.Hash{record.ref.target};610        const commit = version.Commit.init(root, parents[0..]);611        try self.putCommitAndRef(commit, record, commit.hash);612        return commit.hash;613    }614615    pub fn mergeCommitBranch(self: *History, name: []const u8, root: version.Hash, theirs: version.Hash) Error!version.Hash {616        try self.ensureUsable();617        const record = self.findRef(name) orelse return error.RefNotFound;618        if (self.findCommit(record.ref.target) == null) return error.CommitNotFound;619        if (self.findCommit(theirs) == null) return error.CommitNotFound;620        var parents = [_]version.Hash{ record.ref.target, theirs };621        const commit = version.Commit.init(root, parents[0..]);622        try self.putCommitAndRef(commit, record, commit.hash);623        return commit.hash;624    }625626    pub fn putCommitAndRef(self: *History, commit: version.Commit, ref_record: *record_mod.RefRecord, target: version.Hash) Error!void {627        try self.ensureUsable();628        const canonical = version.Commit.init(commit.root, commit.parents);629        const append_commit = self.findCommit(canonical.hash) == null;630        var parents: []version.Hash = &.{};631        if (append_commit) parents = try self.allocator.dupe(version.Hash, canonical.parents);632        var parents_live = append_commit;633        errdefer if (parents_live) self.allocator.free(parents);634        if (append_commit) {635            try self.commits.ensureUnusedCapacity(self.allocator, 1);636            try self.lookup.commits.ensureUnusedCapacity(self.allocator, 1);637            try self.appendCommitRecord(canonical.root, parents);638        }639        try self.appendRefRecord(ref_record.name, target);640        try self.flushSync();641        if (append_commit) {642            self.lookup.commits.putAssumeCapacity(canonical.hash, self.commits.items.len);643            self.commits.appendAssumeCapacity(.{644                .parents = parents,645                .commit = .{646                    .root = canonical.root,647                    .parents = parents,648                    .hash = canonical.hash,649                },650            });651            parents_live = false;652        }653        ref_record.ref.target = target;654        self.refreshRefsSidecar();655    }656657    pub fn putConflict(self: *History, artifact: version.ConflictArtifact) Error!void {658        try self.ensureUsable();659        const canonical = conflict_mod.canonicalConflictArtifact(artifact);660        if (self.findConflict(canonical.hash) != null) return;661        var owned = try conflict_mod.cloneConflictArtifact(self.allocator, artifact);662        errdefer conflict_mod.deinitConflictArtifact(self.allocator, &owned);663        try self.conflicts.ensureUnusedCapacity(self.allocator, 1);664        try self.lookup.conflicts.ensureUnusedCapacity(self.allocator, 1);665        try self.appendConflictRecord(canonical);666        try self.flushSync();667        self.lookup.conflicts.putAssumeCapacity(canonical.hash, self.conflicts.items.len);668        self.conflicts.appendAssumeCapacity(.{ .artifact = owned });669    }670671    pub fn putConflictRoot(self: *History, entries: []const version.ConflictEntry) Error!version.ConflictRoot {672        try self.ensureUsable();673        if (entries.len == 0) return version.ConflictRoot.empty();674        const owned = try conflict_mod.cloneConflictEntriesSorted(self.allocator, entries);675        var owned_live = true;676        errdefer if (owned_live) conflict_mod.deinitConflictEntries(self.allocator, owned);677        try self.validateConflictEntries(owned);678        const root = version.ConflictRoot.init(owned);679        if (self.findConflictRoot(root.hash) != null) {680            try self.validateConflictRoot(root.hash);681            conflict_mod.deinitConflictEntries(self.allocator, owned);682            owned_live = false;683            return root;684        }685        try self.conflict_roots.ensureUnusedCapacity(self.allocator, 1);686        try self.lookup.conflict_roots.ensureUnusedCapacity(self.allocator, 1);687        try self.appendConflictRootRecord(owned);688        try self.flushSync();689        self.lookup.conflict_roots.putAssumeCapacity(root.hash, self.conflict_roots.items.len);690        self.conflict_roots.appendAssumeCapacity(.{691            .root = root,692            .entries = owned,693        });694        owned_live = false;695        return root;696    }697698    pub fn ref(self: *const History, name: []const u8) Error!?version.Ref {699        try self.ensureUsable();700        for (self.refs.items) |record| {701            if (std.mem.eql(u8, record.name, name)) return record.ref;702        }703        return null;704    }705706    pub fn refList(self: *const History, allocator: Allocator) Error![]version.Ref {707        try self.ensureUsable();708        const refs = try allocator.alloc(version.Ref, self.refs.items.len);709        var count: usize = 0;710        errdefer freeRefList(allocator, refs[0..count]);711        for (self.refs.items, refs) |record, *target| {712            const name = try allocator.dupe(u8, record.name);713            target.* = .{714                .name = name,715                .target = record.ref.target,716            };717            count += 1;718        }719        return refs;720    }721722    pub fn conflict(self: *const History, hash: version.Hash) ?version.ConflictArtifact {723        if (self.findConflict(hash)) |record| return record.artifact;724        return null;725    }726727    pub fn hasCommit(self: *const History, hash: version.Hash) bool {728        return self.findCommit(hash) != null;729    }730731    pub fn hasDatabaseRoot(self: *const History, hash: version.Hash) bool {732        return self.findDatabaseRoot(hash) != null;733    }734735    pub fn hasConflict(self: *const History, hash: version.Hash) bool {736        return self.findConflict(hash) != null;737    }738739    pub fn hasConflictRoot(self: *const History, hash: version.Hash) Error!bool {740        self.validateConflictRoot(hash) catch |err| switch (err) {741            error.ConflictRootNotFound => return false,742            else => return err,743        };744        return true;745    }746747    pub fn validateConflictRoot(self: *const History, hash: version.Hash) Error!void {748        try self.ensureUsable();749        if (version.same(hash, version.ConflictRoot.empty().hash)) return;750        const record = self.findConflictRoot(hash) orelse return error.ConflictRootNotFound;751        const derived = version.ConflictRoot.init(record.entries);752        if (!version.same(record.root.hash, hash) or753            !version.same(derived.hash, hash) or754            derived.count != record.root.count)755        {756            return error.InvalidHistory;757        }758        try self.validateConflictEntries(record.entries);759    }760761    pub fn validateConflictEntries(762        self: *const History,763        entries: []const version.ConflictEntry,764    ) error{ InvalidHistory, ConflictArtifactNotFound }!void {765        var previous: ?version.ConflictEntry = null;766        for (entries) |entry| {767            if (previous) |prior| {768                if (prior.sameSlot(entry) or769                    !version.ConflictEntry.lessThan({}, prior, entry))770                {771                    return error.InvalidHistory;772                }773            }774            const artifact_record = self.findConflict(entry.hash) orelse {775                return error.ConflictArtifactNotFound;776            };777            if (!entry.eql(artifact_record.artifact.entry())) {778                return error.InvalidHistory;779            }780            previous = entry;781        }782    }783784    pub fn conflictEntries(self: *const History, allocator: Allocator, root: version.Hash) Error!conflict_mod.ConflictEntries {785        try self.ensureUsable();786        if (version.same(root, version.ConflictRoot.empty().hash)) {787            return .{788                .allocator = allocator,789                .root = version.ConflictRoot.empty(),790                .entries = &.{},791            };792        }793        try self.validateConflictRoot(root);794        const record = self.findConflictRoot(root) orelse return error.ConflictRootNotFound;795        const entries = try conflict_mod.cloneConflictEntries(allocator, record.entries);796        errdefer conflict_mod.deinitConflictEntries(allocator, entries);797        return .{798            .allocator = allocator,799            .root = record.root,800            .entries = entries,801        };802    }803804    pub fn conflictArtifacts(self: *const History, allocator: Allocator, root: version.Hash) Error!conflict_mod.ConflictArtifacts {805        try self.ensureUsable();806        var entries = try self.conflictEntries(allocator, root);807        defer entries.deinit();808        if (entries.entries.len == 0) {809            return .{810                .allocator = allocator,811                .root = entries.root,812                .artifacts = &.{},813            };814        }815816        const artifacts = try allocator.alloc(version.ConflictArtifact, entries.entries.len);817        var count: usize = 0;818        errdefer {819            for (artifacts[0..count]) |*artifact| conflict_mod.deinitConflictArtifact(allocator, artifact);820            allocator.free(artifacts);821        }822        for (entries.entries, artifacts) |entry, *target| {823            const record = self.findConflict(entry.hash) orelse return error.ConflictArtifactNotFound;824            target.* = try conflict_mod.cloneConflictArtifact(allocator, record.artifact);825            count += 1;826        }827        return .{828            .allocator = allocator,829            .root = entries.root,830            .artifacts = artifacts,831        };832    }833834    pub fn commitValue(self: *const History, hash: version.Hash) Error!version.Commit {835        try self.ensureUsable();836        const record = self.findCommit(hash) orelse return error.CommitNotFound;837        return record.commit;838    }839840    pub fn databaseRoot(self: *const History, allocator: Allocator, root: version.Hash) Error!version.DatabaseRoot {841        try self.ensureUsable();842        const record = self.findDatabaseRoot(root) orelse return error.DatabaseRootNotFound;843        return try record.root.clone(allocator);844    }845846    pub fn databaseValue(self: *const History, allocator: Allocator, root: version.Hash) Error!version.DatabaseValue {847        try self.ensureUsable();848        var database_root = try self.databaseRoot(allocator, root);849        defer database_root.deinit();850851        const relations = try allocator.alloc(version.RelationValue, database_root.entries.len);852        var relation_count: usize = 0;853        var relations_owned = true;854        errdefer {855            if (relations_owned) {856                for (relations[0..relation_count]) |*relation| relation.deinit(allocator);857                if (relations.len != 0) allocator.free(relations);858            }859        }860861        for (database_root.entries, relations) |entry, *relation| {862            var relation_root = try self.relationRoot(allocator, entry.hash);863            errdefer relation_root.deinit();864            const rows = try self.relationRows(allocator, entry.hash);865            errdefer version.freeRelationRows(allocator, rows);866            relation.* = .{867                .root = relation_root,868                .rows = rows,869            };870            relation_count += 1;871        }872873        var value = try version.databaseValueFromOwnedRelations(allocator, relations, database_root.conflicts);874        relations_owned = false;875        errdefer value.deinit();876        if (!version.same(value.root.hash, database_root.hash)) return error.InvalidHistory;877        return value;878    }879880    pub fn relationRoot(self: *const History, allocator: Allocator, root: version.Hash) Error!version.RelationRoot {881        try self.ensureUsable();882        const record = self.findRelationRoot(root) orelse return error.RelationRootNotFound;883        var out: version.RelationRoot = undefined;884        var table_key: ?version.Hash = null;885        var index_keys: []const ?version.Hash = &.{};886        var owned_index_keys: ?[]?version.Hash = null;887        defer if (owned_index_keys) |owned| allocator.free(owned);888        switch (record.storage) {889            .materialized => |index| {890                const materialized = &self.materialized_relation_roots.items[index];891                out = try materialized.root.clone(allocator);892                table_key = materialized.table_key;893                index_keys = materialized.index_keys;894            },895            .indexed => |location| {896                const decoded = try materialize_mod.readIndexedRelationRoot(self, allocator, record.hash, location);897                out = decoded.root;898                table_key = decoded.table_key;899                index_keys = decoded.index_keys;900                owned_index_keys = decoded.index_keys;901            },902        }903        errdefer out.deinit();904        const table = try materialize_mod.merkleMapRoot(self, allocator, out.table.summary, out.table.hash, out.table.subtree, table_key);905        var table_swapped = out.table;906        out.table = table;907        table_swapped.deinit();908        for (out.indexes, index_keys) |*index, index_key| {909            const map = try materialize_mod.merkleMapRoot(self, allocator, index.map.summary, index.map.hash, index.map.subtree, index_key);910            var map_swapped = index.map;911            index.map = map;912            map_swapped.deinit();913        }914        return out;915    }916917    pub fn relationRows(self: *const History, allocator: Allocator, root: version.Hash) Error![]version.RelationRow {918        try self.ensureUsable();919        var pages = (try self.relationRowsPages(allocator, root)) orelse return error.RelationRowsNotFound;920        defer pages.deinit();921        var rows: std.ArrayList(version.RelationRow) = .empty;922        errdefer {923            for (rows.items) |row_value| allocator.free(row_value.bytes);924            rows.deinit(allocator);925        }926        for (pages.items) |page_digest| {927            var chunks = (try self.indexPageChunks(allocator, page_digest)) orelse return error.RelationRowsNotFound;928            defer chunks.deinit();929            for (chunks.items) |digest| {930                const chunk_record = self.findRowChunk(digest) orelse return error.RelationRowsNotFound;931                try self.chunkRowsInto(allocator, chunk_record, &rows);932            }933        }934        return try rows.toOwnedSlice(allocator);935    }936937    pub fn chunkRowsInto(self: *const History, allocator: Allocator, record: *const record_mod.RowChunkRecord, rows: *std.ArrayList(version.RelationRow)) Error!void {938        try self.ensureUsable();939        const payload = try materialize_mod.readPayload(self, allocator, .row_chunk, record.payload);940        defer allocator.free(payload);941        var reader = record_mod.PayloadReader.init(payload);942        const digest = try reader.hash();943        if (!version.same(digest, record.digest)) return error.InvalidHistory;944        const row_count = try reader.readU32();945        try rows.ensureUnusedCapacity(allocator, row_count);946        var read_rows: u32 = 0;947        while (read_rows < row_count) : (read_rows += 1) {948            const rowid = try reader.readI64();949            const bytes = try allocator.dupe(u8, try reader.readBytes());950            rows.appendAssumeCapacity(.{951                .rowid = rowid,952                .bytes = bytes,953            });954        }955        try reader.finish();956    }957958    pub fn commitDatabaseRoot(self: *const History, allocator: Allocator, commit_hash: version.Hash) Error!version.DatabaseRoot {959        try self.ensureUsable();960        const commit_value = try self.commitValue(commit_hash);961        return try self.databaseRoot(allocator, commit_value.root);962    }963964    pub fn commitEntries(self: *const History, allocator: Allocator) Error![]branch.CommitEntry {965        try self.ensureUsable();966        const entries = try allocator.alloc(branch.CommitEntry, self.commits.items.len);967        for (self.commits.items, entries) |record, *entry| {968            entry.* = branch.commitEntry(record.commit);969        }970        return entries;971    }972973    pub fn len(self: *const History) usize {974        return self.bytes_written;975    }976977    pub fn hasRelationRoot(self: *const History, hash: version.Hash) bool {978        return self.lookup.relation_roots.get(hash) != null;979    }980981    pub fn hasRelationRows(self: *const History, root: version.Hash) bool {982        return self.lookup.relation_rows.get(root) != null;983    }984985    pub fn hasIndexPage(self: *const History, digest: version.Hash) bool {986        return self.lookup.index_pages.get(digest) != null;987    }988989    pub fn hasRowChunk(self: *const History, digest: version.Hash) bool {990        return self.findRowChunk(digest) != null;991    }992993    pub fn hasTreeNode(self: *const History, key: version.Hash) bool {994        return self.findTreeNode(key) != null;995    }996997    pub fn databaseRootView(self: *const History, hash: version.Hash) ?DatabaseRootView {998        const record = self.findDatabaseRoot(hash) orelse return null;999        return .{1000            .conflicts = record.root.conflicts,1001            .entries = record.root.entries,1002        };1003    }10041005    pub fn relationKeysView(self: *const History, allocator: Allocator, hash: version.Hash) Error!?RelationKeysView {1006        try self.ensureUsable();1007        const record = self.findRelationRoot(hash) orelse return null;1008        switch (record.storage) {1009            .materialized => |index| {1010                const materialized = &self.materialized_relation_roots.items[index];1011                return .{1012                    .allocator = allocator,1013                    .table_key = materialized.table_key,1014                    .index_keys = materialized.index_keys,1015                };1016            },1017            .indexed => |location| {1018                var decoded = try materialize_mod.readIndexedRelationRoot(self, allocator, record.hash, location);1019                defer decoded.root.deinit();1020                return .{1021                    .allocator = allocator,1022                    .owned = decoded.index_keys,1023                    .table_key = decoded.table_key,1024                    .index_keys = decoded.index_keys,1025                };1026            },1027        }1028    }10291030    pub fn relationRowsPages(self: *const History, allocator: Allocator, root: version.Hash) Error!?record_mod.HashListView {1031        try self.ensureUsable();1032        const index = self.lookup.relation_rows.get(root) orelse return null;1033        const record = &self.relation_rows.items[index];1034        return try materialize_mod.readHashListRecord(self, allocator, .relation_rows, record.root, record.storage);1035    }10361037    pub fn indexPageChunks(self: *const History, allocator: Allocator, digest: version.Hash) Error!?record_mod.HashListView {1038        try self.ensureUsable();1039        const index = self.lookup.index_pages.get(digest) orelse return null;1040        const record = &self.index_pages.items[index];1041        return try materialize_mod.readHashListRecord(self, allocator, .chunk_index_page, record.digest, record.storage);1042    }10431044    pub fn treeNodeChildren(self: *const History, allocator: Allocator, key: version.Hash) Error![]version.Hash {1045        try self.ensureUsable();1046        const index = self.lookup.tree_nodes.get(key) orelse return error.InvalidHistory;1047        const node = try materialize_mod.readTreeNodeRecord(self, allocator, &self.tree_nodes.items[index]);1048        allocator.free(node.node.lower);1049        if (node.node.upper) |upper| allocator.free(upper);1050        return node.children;1051    }10521053    pub fn appendPackRecordPayload(self: *const History, allocator: Allocator, target: *std.ArrayList(u8), kind: record_mod.PackRecordKind, hash: version.Hash) Error!void {1054        try self.ensureUsable();1055        switch (kind) {1056            .row_chunk => try pack_mod.appendRowChunkPackPayload(self, allocator, target, hash),1057            .chunk_index_page => try pack_mod.appendChunkIndexPagePackPayload(self, allocator, target, hash),1058            .tree_node => try pack_mod.appendTreeNodePackPayload(self, allocator, target, hash),1059            .relation_rows => try pack_mod.appendRelationRowsPackPayload(self, allocator, target, hash),1060            .relation_root => try pack_mod.appendRelationRootPackPayload(self, allocator, target, hash),1061            .database_root => try pack_mod.appendDatabaseRootPackPayload(self, allocator, target, hash),1062            .conflict => try pack_mod.appendConflictPackPayload(self, allocator, target, hash),1063            .conflict_root => try pack_mod.appendConflictRootPackPayload(self, allocator, target, hash),1064        }1065    }10661067    pub fn packRecordPresent(self: *const History, kind: record_mod.PackRecordKind, payload: []const u8) Error!bool {1068        try self.ensureUsable();1069        var reader = record_mod.PayloadReader.init(payload);1070        switch (kind) {1071            .row_chunk => return self.findRowChunk(try reader.hash()) != null,1072            .chunk_index_page => return self.hasIndexPage(try reader.hash()),1073            .tree_node => {1074                if (try reader.readU32() != 1) return error.InvalidHistory;1075                return self.findTreeNode(try reader.hash()) != null;1076            },1077            .relation_rows => return self.hasRelationRows(try reader.hash()),1078            .relation_root => {1079                var decoded = try materialize_mod.readRelationRootShallow(self.allocator, &reader);1080                defer decoded.root.deinit();1081                defer self.allocator.free(decoded.index_keys);1082                return self.findRelationRoot(decoded.root.hash) != null;1083            },1084            .database_root => {1085                const conflicts = try reader.hash();1086                const entry_count = try reader.readU32();1087                const entries = try self.allocator.alloc(version.RelationEntry, entry_count);1088                defer self.allocator.free(entries);1089                for (entries) |*entry| {1090                    const name = try reader.readBytes();1091                    const hash = try reader.hash();1092                    entry.* = .{1093                        .name = name,1094                        .hash = hash,1095                    };1096                }1097                var root = try version.DatabaseRoot.initSorted(self.allocator, entries, .{ .hash = conflicts });1098                const hash = root.hash;1099                root.deinit();1100                return self.findDatabaseRoot(hash) != null;1101            },1102            .conflict => {1103                const decoded = try conflict_mod.decodeConflictArtifactPayload(&reader);1104                return self.findConflict(decoded.hash) != null;1105            },1106            .conflict_root => {1107                const entries = try conflict_mod.readConflictEntries(self.allocator, &reader);1108                defer conflict_mod.deinitConflictEntries(self.allocator, entries);1109                try reader.finish();1110                self.validateConflictEntries(entries) catch {1111                    return error.InvalidHistory;1112                };1113                const root = version.ConflictRoot.init(entries);1114                if (self.findConflictRoot(root.hash) == null) return false;1115                try self.validateConflictRoot(root.hash);1116                return true;1117            },1118        }1119    }11201121    pub fn importPackRecord(self: *History, kind: record_mod.PackRecordKind, payload: []const u8) Error!bool {1122        try self.ensureUsable();1123        return switch (kind) {1124            .row_chunk => try pack_mod.importRowChunkPayload(self, payload),1125            .chunk_index_page => try pack_mod.importChunkIndexPagePayload(self, payload),1126            .tree_node => try pack_mod.importTreeNodePayload(self, payload),1127            .relation_rows => try pack_mod.importRelationRowsPayload(self, payload),1128            .relation_root => try pack_mod.importRelationRootPayload(self, payload),1129            .database_root => try pack_mod.importDatabaseRootPayload(self, payload),1130            .conflict => try pack_mod.importConflictPayload(self, payload),1131            .conflict_root => try pack_mod.importConflictRootPayload(self, payload),1132        };1133    }11341135    pub fn importPackCommit(self: *History, root: version.Hash, parents: []const version.Hash) Error!bool {1136        try self.ensureUsable();1137        const canonical = version.Commit.init(root, parents);1138        if (self.findCommit(canonical.hash) != null) return false;1139        if (self.findDatabaseRoot(root) == null) return error.InvalidHistory;1140        const owned = try self.allocator.dupe(version.Hash, parents);1141        errdefer self.allocator.free(owned);1142        try self.commits.ensureUnusedCapacity(self.allocator, 1);1143        try self.lookup.commits.ensureUnusedCapacity(self.allocator, 1);1144        try self.appendCommitRecord(canonical.root, owned);1145        self.lookup.commits.putAssumeCapacity(canonical.hash, self.commits.items.len);1146        self.commits.appendAssumeCapacity(.{1147            .parents = owned,1148            .commit = .{1149                .root = canonical.root,1150                .parents = owned,1151                .hash = canonical.hash,1152            },1153        });1154        return true;1155    }11561157    fn appendDatabaseRootRecord(self: *History, root: version.DatabaseRoot) Error!void {1158        var payload: std.ArrayList(u8) = .empty;1159        defer payload.deinit(self.allocator);1160        try record_mod.appendDatabaseRootValue(self.allocator, &payload, root);1161        try self.appendRecord(.database_root, payload.items);1162    }11631164    fn appendRelationRootRecord(self: *History, root: version.RelationRoot, table_key: ?version.Hash, index_keys: []const ?version.Hash) Error!void {1165        var payload: std.ArrayList(u8) = .empty;1166        defer payload.deinit(self.allocator);1167        try record_mod.appendRelationRootMerkle(self.allocator, &payload, root, table_key, index_keys);1168        try self.appendRecord(.relation_root, payload.items);1169    }11701171    fn appendRelationRowsRecord(self: *History, root: version.Hash, pages: []const version.Hash) Error!void {1172        if (pages.len > std.math.maxInt(u32)) return error.InvalidHistory;1173        var payload: std.ArrayList(u8) = .empty;1174        defer payload.deinit(self.allocator);1175        try record_mod.appendHash(self.allocator, &payload, root);1176        try record_mod.appendU32(self.allocator, &payload, @intCast(pages.len));1177        for (pages) |digest| try record_mod.appendHash(self.allocator, &payload, digest);1178        try self.appendRecord(.relation_rows, payload.items);1179    }11801181    fn appendChunkIndexPageRecord(self: *History, digest: version.Hash, chunks: []const version.Hash) Error!void {1182        if (chunks.len > std.math.maxInt(u32)) return error.InvalidHistory;1183        var payload: std.ArrayList(u8) = .empty;1184        defer payload.deinit(self.allocator);1185        try record_mod.appendHash(self.allocator, &payload, digest);1186        try record_mod.appendU32(self.allocator, &payload, @intCast(chunks.len));1187        for (chunks) |chunk_digest| try record_mod.appendHash(self.allocator, &payload, chunk_digest);1188        try self.appendRecord(.chunk_index_page, payload.items);1189    }11901191    fn appendCommitRecord(self: *History, root: version.Hash, parents: []const version.Hash) Error!void {1192        if (parents.len > std.math.maxInt(u32)) return error.InvalidHistory;1193        var payload: std.ArrayList(u8) = .empty;1194        defer payload.deinit(self.allocator);1195        try record_mod.appendHash(self.allocator, &payload, root);1196        try record_mod.appendU32(self.allocator, &payload, @intCast(parents.len));1197        for (parents) |parent| try record_mod.appendHash(self.allocator, &payload, parent);1198        try self.appendRecord(.commit, payload.items);1199    }12001201    fn appendRefRecord(self: *History, name: []const u8, target: version.Hash) Error!void {1202        var payload: std.ArrayList(u8) = .empty;1203        defer payload.deinit(self.allocator);1204        try record_mod.appendHash(self.allocator, &payload, target);1205        try record_mod.appendBytes(self.allocator, &payload, name);1206        try self.appendRecord(.ref, payload.items);1207    }12081209    fn appendRefDeleteRecord(self: *History, name: []const u8) Error!void {1210        var payload: std.ArrayList(u8) = .empty;1211        defer payload.deinit(self.allocator);1212        try record_mod.appendBytes(self.allocator, &payload, name);1213        try self.appendRecord(.ref_delete, payload.items);1214    }12151216    fn appendConflictRecord(self: *History, artifact: version.ConflictArtifact) Error!void {1217        var payload: std.ArrayList(u8) = .empty;1218        defer payload.deinit(self.allocator);1219        try conflict_mod.appendConflictArtifactRecordPayload(self.allocator, &payload, artifact);1220        try self.appendRecord(.conflict, payload.items);1221    }12221223    fn appendConflictRootRecord(self: *History, entries: []const version.ConflictEntry) Error!void {1224        var payload: std.ArrayList(u8) = .empty;1225        defer payload.deinit(self.allocator);1226        try conflict_mod.appendConflictEntries(self.allocator, &payload, entries);1227        try self.appendRecord(.conflict_root, payload.items);1228    }12291230    pub fn appendRecord(self: *History, kind: record_mod.RecordKind, payload: []const u8) Error!void {1231        try self.ensureMutable();1232        const record = try encodeRecord(self.allocator, kind, payload);1233        defer self.allocator.free(record);12341235        const next_bytes_written = std.math.add(1236            usize,1237            self.bytes_written,1238            record.len,1239        ) catch return error.InvalidHistory;1240        try self.pending_write.appendSlice(self.allocator, record);1241        self.bytes_written = next_bytes_written;1242        self.needs_sync = true;1243        if (self.write_batch_depth == 0) {1244            try self.flushPendingWrite();1245            try self.flushSync();1246        }1247    }12481249    fn appendCoordinatorRecord(self: *History, kind: record_mod.RecordKind, payload: []const u8) Error!void {1250        if (self.write_batch_depth != 0 or1251            self.pending_write.items.len != 0 or1252            self.needs_sync)1253        {1254            return error.InvalidHistory;1255        }1256        const record = try encodeRecord(self.allocator, kind, payload);1257        defer self.allocator.free(record);1258        try self.pending_write.ensureUnusedCapacity(self.allocator, record.len);1259        try self.persistCoordinatorRecord(record);1260    }12611262    fn appendCoordinatorHashRecord(self: *History, kind: record_mod.RecordKind, id: version.Hash) Error!void {1263        if (self.write_batch_depth != 0 or1264            self.pending_write.items.len != 0 or1265            self.needs_sync)1266        {1267            return error.InvalidHistory;1268        }1269        var record: [record_mod.record_header_size + version.hash_bytes]u8 = undefined;1270        std.mem.writeInt(u32, record[0..4], record_mod.magic, .big);1271        std.mem.writeInt(u32, record[4..8], record_mod.format_version, .big);1272        std.mem.writeInt(u32, record[8..12], @backingInt(kind), .big);1273        std.mem.writeInt(u32, record[12..16], version.hash_bytes, .big);1274        const digest = record_mod.recordHash(@backingInt(kind), id[0..]);1275        @memcpy(record[16..record_mod.record_header_size], digest[0..]);1276        @memcpy(record[record_mod.record_header_size..], id[0..]);1277        try self.pending_write.ensureUnusedCapacity(self.allocator, record.len);1278        try self.persistCoordinatorRecord(record[0..]);1279    }12801281    fn persistCoordinatorRecord(self: *History, record: []const u8) Error!void {1282        if (self.read_only) return error.ReadOnly;1283        const start = self.bytes_written;1284        self.pending_write.appendSliceAssumeCapacity(record);1285        self.bytes_written = std.math.add(usize, start, record.len) catch {1286            self.pending_write.clearRetainingCapacity();1287            return error.InvalidHistory;1288        };1289        self.needs_sync = true;1290        self.flushPendingWrite() catch |err| {1291            self.restorePreparedAppend(start) catch {1292                self.poison();1293                return error.RecoveryRequired;1294            };1295            return err;1296        };1297        self.flushSync() catch |err| {1298            self.restorePreparedAppend(start) catch {1299                self.poison();1300                return error.RecoveryRequired;1301            };1302            return err;1303        };1304    }13051306    pub fn flushSync(self: *History) Error!void {1307        try self.ensureUsable();1308        if (!self.needs_sync) return;1309        if (self.write_batch_depth != 0) return;1310        try self.flushPendingWrite();1311        const file = self.file orelse return error.InvalidHistory;1312        try file.sync(self.io);1313        self.write_io.syncs += 1;1314        self.needs_sync = false;1315    }13161317    fn refreshRefsSidecar(self: *History) void {1318        if (self.fast_forward != null or self.recovery_required) return;1319        const dir = self.sidecar_dir orelse return;1320        const path = self.sidecar_path orelse return;1321        if (self.needs_sync or self.write_batch_depth != 0) return;1322        if (self.pending_write.items.len != 0) return;1323        if (self.refs.items.len > refs_mod.max_entries) return;1324        const entries = self.allocator.alloc(refs_mod.Entry, self.refs.items.len) catch return;1325        defer self.allocator.free(entries);1326        for (self.refs.items, 0..) |record, index| {1327            std.debug.assert(record.ref.name.len != 0);1328            const commit = self.findCommit(record.ref.target) orelse return;1329            const root = self.findDatabaseRoot(commit.commit.root) orelse return;1330            entries[index] = .{1331                .name = record.ref.name,1332                .head = record.ref.target,1333                .root = commit.commit.root,1334                .conflicts = root.root.conflicts,1335            };1336        }1337        refs_mod.store(self.allocator, self.io, dir, path, self.bytes_written, entries) catch return;1338    }13391340    fn flushPendingWrite(self: *History) Error!void {1341        if (self.pending_write.items.len == 0) return;1342        const file = self.file orelse return error.InvalidHistory;1343        const start = self.bytes_written - self.pending_write.items.len;1344        errdefer if (file.setLength(self.io, start)) {1345            self.write_io.resizes += 1;1346        } else |_| {};1347        try file.writePositionalAll(self.io, self.pending_write.items, start);1348        self.write_io.writes += 1;1349        self.pending_write.clearRetainingCapacity();1350    }13511352    fn restorePreparedAppend(self: *History, bytes_written: usize) Error!void {1353        const file = self.file orelse return error.InvalidHistory;1354        try file.setLength(self.io, bytes_written);1355        self.write_io.resizes += 1;1356        self.pending_write.clearRetainingCapacity();1357        self.bytes_written = bytes_written;1358        self.needs_sync = false;1359        try file.sync(self.io);1360    }13611362    pub fn beginWriteBatch(self: *History) Error!WriteBatch {1363        try self.ensureMutable();1364        self.write_batch_depth += 1;1365        return .{ .history = self };1366    }13671368    pub fn findCommit(self: *const History, hash: version.Hash) ?*record_mod.CommitRecord {1369        const index = self.lookup.commits.get(hash) orelse return null;1370        return &self.commits.items[index];1371    }13721373    pub fn findDatabaseRoot(self: *const History, hash: version.Hash) ?*record_mod.DatabaseRootRecord {1374        const index = self.lookup.database_roots.get(hash) orelse return null;1375        return &self.database_roots.items[index];1376    }13771378    pub fn findRelationRoot(self: *const History, hash: version.Hash) ?*record_mod.RelationRootRecord {1379        const index = self.lookup.relation_roots.get(hash) orelse return null;1380        return &self.relation_roots.items[index];1381    }13821383    pub fn findRowChunk(self: *const History, digest: version.Hash) ?*record_mod.RowChunkRecord {1384        const index = self.lookup.row_chunks.get(digest) orelse return null;1385        return &self.row_chunks.items[index];1386    }13871388    pub fn findTreeNode(self: *const History, key: version.Hash) ?*record_mod.TreeNodeRecord {1389        const index = self.lookup.tree_nodes.get(key) orelse return null;1390        return &self.tree_nodes.items[index];1391    }13921393    pub fn findRef(self: *const History, name: []const u8) ?*record_mod.RefRecord {1394        for (self.refs.items) |*record| {1395            if (std.mem.eql(u8, record.name, name)) return record;1396        }1397        return null;1398    }13991400    pub fn findRefIndex(self: *const History, name: []const u8) ?usize {1401        for (self.refs.items, 0..) |record, index| {1402            if (std.mem.eql(u8, record.name, name)) return index;1403        }1404        return null;1405    }14061407    pub fn findConflict(self: *const History, hash: version.Hash) ?*record_mod.ConflictRecord {1408        const index = self.lookup.conflicts.get(hash) orelse return null;1409        return &self.conflicts.items[index];1410    }14111412    pub fn findConflictRoot(self: *const History, hash: version.Hash) ?*record_mod.ConflictRootRecord {1413        const index = self.lookup.conflict_roots.get(hash) orelse return null;1414        return &self.conflict_roots.items[index];1415    }1416};

1pub const History = history.History;