lib/sql/src/history/record.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const sql = @import("../root.zig");
3 const conflict_mod = @import("conflict.zig");
4 const store_mod = @import("store.zig");
5 const catalog_mod = sql.catalog;
6 const row = sql.row;
7 const tree = sql.tree;
8 const version = sql.version;
9
10 const Allocator = std.mem.Allocator;
11
12 pub const PackRecordKind = enum(u32) {
13 row_chunk = 1,
14 chunk_index_page = 2,
15 tree_node = 3,
16 relation_rows = 4,
17 relation_root = 5,
18 database_root = 6,
19 conflict = 7,
20 conflict_root = 8,
21 };
22
23 pub const DatabaseRootRecord = struct {
24 root: version.DatabaseRoot,
25
26 pub fn deinit(self: *DatabaseRootRecord) void {
27 self.root.deinit();
28 self.* = undefined;
29 }
30 };
31
32 pub const RelationRootRecord = struct {
33 hash: version.Hash,
34 storage: RelationRootStorage,
35 };
36
37 pub const RelationRootStorage = union(enum) {
38 indexed: PayloadLocation,
39 materialized: usize,
40 };
41
42 pub const MaterializedRelationRoot = struct {
43 root: version.RelationRoot,
44 table_key: ?version.Hash,
45 index_keys: []?version.Hash,
46
47 pub fn deinit(self: *MaterializedRelationRoot) void {
48 self.root.allocator.free(self.index_keys);
49 self.root.deinit();
50 self.* = undefined;
51 }
52 };
53
54 pub const ChunkSpan = struct {
55 first: i64,
56 last: i64,
57 };
58
59 pub const PayloadLocation = struct {
60 expected: version.Hash,
61 offset: usize,
62 len: usize,
63 };
64
65 pub const HashListStorage = union(enum) {
66 indexed: PayloadLocation,
67 materialized: []version.Hash,
68 };
69
70 pub const ChunkSpanStorage = union(enum) {
71 indexed: PayloadLocation,
72 materialized: []ChunkSpan,
73 };
74
75 pub const HashListView = struct {
76 allocator: Allocator,
77 owned: ?[]version.Hash = null,
78 items: []const version.Hash,
79
80 pub fn deinit(self: *HashListView) void {
81 if (self.owned) |owned| self.allocator.free(owned);
82 self.* = undefined;
83 }
84 };
85
86 pub const ChunkSpanView = struct {
87 allocator: Allocator,
88 owned: ?[]ChunkSpan = null,
89 items: []const ChunkSpan,
90
91 pub fn deinit(self: *ChunkSpanView) void {
92 if (self.owned) |owned| self.allocator.free(owned);
93 self.* = undefined;
94 }
95 };
96
97 pub const RelationRowsRecord = struct {
98 root: version.Hash,
99 storage: HashListStorage,
100
101 pub fn deinit(self: *RelationRowsRecord, allocator: Allocator) void {
102 switch (self.storage) {
103 .indexed => {},
104 .materialized => |pages| allocator.free(pages),
105 }
106 self.* = undefined;
107 }
108 };
109
110 pub const RelationSpansRecord = struct {
111 root: version.Hash,
112 storage: ChunkSpanStorage,
113
114 pub fn deinit(self: *RelationSpansRecord, allocator: Allocator) void {
115 switch (self.storage) {
116 .indexed => {},
117 .materialized => |spans| allocator.free(spans),
118 }
119 self.* = undefined;
120 }
121 };
122
123 pub const IndexPageRecord = struct {
124 digest: version.Hash,
125 storage: HashListStorage,
126
127 pub fn deinit(self: *IndexPageRecord, allocator: Allocator) void {
128 switch (self.storage) {
129 .indexed => {},
130 .materialized => |chunks| allocator.free(chunks),
131 }
132 self.* = undefined;
133 }
134 };
135
136 pub const RowChunkRecord = struct {
137 digest: version.Hash,
138 payload: PayloadLocation,
139 };
140
141 pub const TreeNodeRecord = struct {
142 key: version.Hash,
143 payload: PayloadLocation,
144 };
145
146 pub const CommitRecord = struct {
147 parents: []version.Hash,
148 commit: version.Commit,
149
150 pub fn deinit(self: *CommitRecord, allocator: Allocator) void {
151 allocator.free(self.parents);
152 self.* = undefined;
153 }
154 };
155
156 pub const RefRecord = struct {
157 name: []u8,
158 ref: version.Ref,
159
160 pub fn deinit(self: *RefRecord, allocator: Allocator) void {
161 allocator.free(self.name);
162 self.* = undefined;
163 }
164 };
165
166 pub const ConflictRecord = struct {
167 artifact: version.ConflictArtifact,
168
169 pub fn deinit(self: *ConflictRecord, allocator: Allocator) void {
170 conflict_mod.deinitConflictArtifact(allocator, &self.artifact);
171 self.* = undefined;
172 }
173 };
174
175 pub const ConflictRootRecord = struct {
176 root: version.ConflictRoot,
177 entries: []version.ConflictEntry,
178
179 pub fn deinit(self: *ConflictRootRecord, allocator: Allocator) void {
180 conflict_mod.deinitConflictEntries(allocator, self.entries);
181 self.* = undefined;
182 }
183 };
184
185 pub const RecordKind = enum(u32) {
186 commit = 1,
187 ref = 2,
188 conflict = 3,
189 database_root = 4,
190 relation_root = 5,
191 relation_rows = 6,
192 conflict_root = 7,
193 ref_delete = 8,
194 row_chunk = 9,
195 chunk_index_page = 10,
196 tree_nodes = 11,
197 relation_spans = 12,
198 fast_forward_prepare = 13,
199 fast_forward_commit = 14,
200 fast_forward_abort = 15,
201 fast_forward_complete = 16,
202 };
203
204 pub const PayloadReader = struct {
205 bytes_value: []const u8,
206 cursor: usize = 0,
207
208 pub fn init(payload: []const u8) PayloadReader {
209 return .{ .bytes_value = payload };
210 }
211
212 pub fn finish(self: *const PayloadReader) store_mod.Error!void {
213 if (self.cursor != self.bytes_value.len) return error.InvalidHistory;
214 }
215
216 pub fn remaining(self: *const PayloadReader) usize {
217 std.debug.assert(self.cursor <= self.bytes_value.len);
218 return self.bytes_value.len - self.cursor;
219 }
220
221 pub fn hash(self: *PayloadReader) store_mod.Error!version.Hash {
222 if (version.hash_bytes > self.bytes_value.len - self.cursor) return error.InvalidHistory;
223 const value = self.bytes_value[self.cursor..][0..version.hash_bytes].*;
224 self.cursor += version.hash_bytes;
225 return value;
226 }
227
228 pub fn readBytes(self: *PayloadReader) store_mod.Error![]const u8 {
229 const len = try self.readU32();
230 if (len > self.bytes_value.len - self.cursor) return error.InvalidHistory;
231 const value = self.bytes_value[self.cursor..][0..len];
232 self.cursor += len;
233 return value;
234 }
235
236 pub fn optionalBytes(self: *PayloadReader) store_mod.Error!?[]const u8 {
237 const tag = try self.readU8();
238 return switch (tag) {
239 0 => null,
240 1 => try self.readBytes(),
241 else => error.InvalidHistory,
242 };
243 }
244
245 pub fn optionalHash(self: *PayloadReader) store_mod.Error!?version.Hash {
246 const tag = try self.readU8();
247 return switch (tag) {
248 0 => null,
249 1 => try self.hash(),
250 else => error.InvalidHistory,
251 };
252 }
253
254 pub fn readU8(self: *PayloadReader) store_mod.Error!u8 {
255 if (self.cursor >= self.bytes_value.len) return error.InvalidHistory;
256 const value = self.bytes_value[self.cursor];
257 self.cursor += 1;
258 return value;
259 }
260
261 pub fn readU32(self: *PayloadReader) store_mod.Error!u32 {
262 if (4 > self.bytes_value.len - self.cursor) return error.InvalidHistory;
263 const value = readIntU32(self.bytes_value[self.cursor..][0..4]);
264 self.cursor += 4;
265 return value;
266 }
267
268 pub fn readU64(self: *PayloadReader) store_mod.Error!u64 {
269 if (8 > self.bytes_value.len - self.cursor) return error.InvalidHistory;
270 const value = std.mem.readInt(u64, self.bytes_value[self.cursor..][0..8], .big);
271 self.cursor += 8;
272 return value;
273 }
274
275 pub fn readI64(self: *PayloadReader) store_mod.Error!i64 {
276 if (8 > self.bytes_value.len - self.cursor) return error.InvalidHistory;
277 const value = std.mem.readInt(i64, self.bytes_value[self.cursor..][0..8], .big);
278 self.cursor += 8;
279 return value;
280 }
281 };
282
283 pub const magic: u32 = 0x7473_6869;
284
285 pub const format_version: u32 = 4;
286
287 pub const record_header_size: usize = 48;
288
289 /// The header shared by replay, streaming verification, and positional reads.
290 pub const Header = struct {
291 kind: RecordKind,
292 payload_len: u32,
293 envelope_hash: version.Hash,
294
295 pub fn decode(bytes: *const [record_header_size]u8) error{InvalidHistory}!Header {
296 if (readIntU32(bytes[0..4]) != magic) return error.InvalidHistory;
297 if (readIntU32(bytes[4..8]) != format_version) return error.InvalidHistory;
298 const kind = recordKind(readIntU32(bytes[8..12])) orelse
299 return error.InvalidHistory;
300 const payload_len = readIntU32(bytes[12..16]);
301 if (kind == .row_chunk and payload_len < version.hash_bytes) {
302 return error.InvalidHistory;
303 }
304 return .{
305 .kind = kind,
306 .payload_len = payload_len,
307 .envelope_hash = bytes[16..][0..version.hash_bytes].*,
308 };
309 }
310
311 pub fn encodedLen(self: Header) usize {
312 return record_header_size + @as(usize, self.payload_len);
313 }
314 };
315
316 pub const node_batch_max: usize = 256;
317
318 pub const tree_node_domain = "tiny.sql.history.tree_node";
319
320 pub fn appendHash(allocator: Allocator, target: *std.ArrayList(u8), hash: version.Hash) Allocator.Error!void {
321 try target.appendSlice(allocator, hash[0..]);
322 }
323
324 pub fn appendBytes(allocator: Allocator, target: *std.ArrayList(u8), bytes: []const u8) store_mod.Error!void {
325 if (bytes.len > std.math.maxInt(u32)) return error.InvalidHistory;
326 try appendU32(allocator, target, @intCast(bytes.len));
327 try target.appendSlice(allocator, bytes);
328 }
329
330 pub fn appendOptionalBytes(allocator: Allocator, target: *std.ArrayList(u8), bytes: ?[]const u8) store_mod.Error!void {
331 if (bytes) |value| {
332 try target.append(allocator, 1);
333 try appendBytes(allocator, target, value);
334 } else {
335 try target.append(allocator, 0);
336 }
337 }
338
339 pub fn appendOptionalHash(allocator: Allocator, target: *std.ArrayList(u8), hash: ?version.Hash) Allocator.Error!void {
340 if (hash) |value| {
341 try target.append(allocator, 1);
342 try appendHash(allocator, target, value);
343 } else {
344 try target.append(allocator, 0);
345 }
346 }
347
348 pub fn appendDatabaseRootValue(allocator: Allocator, target: *std.ArrayList(u8), root: version.DatabaseRoot) store_mod.Error!void {
349 if (root.entries.len > std.math.maxInt(u32)) return error.InvalidHistory;
350 try appendHash(allocator, target, root.conflicts);
351 try appendU32(allocator, target, @intCast(root.entries.len));
352 for (root.entries) |entry| {
353 try appendBytes(allocator, target, entry.name);
354 try appendHash(allocator, target, entry.hash);
355 }
356 }
357
358 pub fn readDatabaseRootValue(allocator: Allocator, reader: *PayloadReader) store_mod.Error!version.DatabaseRoot {
359 const conflicts = try reader.hash();
360 const entry_count = try reader.readU32();
361 const entries = try allocator.alloc(version.RelationEntry, entry_count);
362 defer allocator.free(entries);
363 for (entries) |*entry| {
364 const name = try reader.readBytes();
365 const hash = try reader.hash();
366 entry.* = .{
367 .name = name,
368 .hash = hash,
369 };
370 }
371 return try version.DatabaseRoot.initSorted(allocator, entries, .{ .hash = conflicts });
372 }
373
374 pub fn appendRelationRoot(allocator: Allocator, target: *std.ArrayList(u8), root: version.RelationRoot) store_mod.Error!void {
375 if (root.indexes.len > std.math.maxInt(u32)) return error.InvalidHistory;
376 try appendU32(allocator, target, root.format);
377 try appendBytes(allocator, target, root.name);
378 try appendU32(allocator, target, root.catalog.format);
379 try appendU64(allocator, target, root.catalog.version);
380 try appendHash(allocator, target, root.schema);
381 try appendRelationSchema(allocator, target, root.schema_descriptor);
382 try appendMapRoot(allocator, target, root.table);
383 try appendStatsRoot(allocator, target, root.stats);
384 try appendU32(allocator, target, @intCast(root.indexes.len));
385 for (root.indexes) |index| {
386 try appendHash(allocator, target, index.fields);
387 try appendMapRoot(allocator, target, index.map);
388 try appendHash(allocator, target, index.stats);
389 try appendHash(allocator, target, index.hash);
390 }
391 try appendHash(allocator, target, root.hash);
392 }
393
394 pub fn readRelationRoot(allocator: Allocator, reader: *PayloadReader) store_mod.Error!version.RelationRoot {
395 const format = try reader.readU32();
396 const name_bytes = try reader.readBytes();
397 const name = try allocator.dupe(u8, name_bytes);
398 errdefer allocator.free(name);
399 const catalog_format = try reader.readU32();
400 const catalog_version = try reader.readU64();
401 const schema = try reader.hash();
402 var schema_descriptor = try readRelationSchema(allocator, reader);
403 errdefer schema_descriptor.deinit();
404 var table = try readMapRoot(allocator, reader);
405 errdefer table.deinit();
406 const stats = try readStatsRoot(reader);
407 const index_count = try reader.readU32();
408 const indexes = try allocator.alloc(version.IndexRoot, index_count);
409 var read_indexes: usize = 0;
410 errdefer {
411 for (indexes[0..read_indexes]) |*index| index.deinit();
412 allocator.free(indexes);
413 }
414 for (indexes) |*index| {
415 const fields = try reader.hash();
416 var map = try readMapRoot(allocator, reader);
417 errdefer map.deinit();
418 index.* = .{
419 .fields = fields,
420 .map = map,
421 .stats = try reader.hash(),
422 .hash = try reader.hash(),
423 };
424 read_indexes += 1;
425 }
426 return .{
427 .allocator = allocator,
428 .format = format,
429 .name = name,
430 .catalog = .{
431 .format = catalog_format,
432 .version = catalog_version,
433 },
434 .schema = schema,
435 .schema_descriptor = schema_descriptor,
436 .table = table,
437 .indexes = indexes,
438 .stats = stats,
439 .hash = try reader.hash(),
440 };
441 }
442
443 pub fn appendRelationSchema(allocator: Allocator, target: *std.ArrayList(u8), schema: version.RelationSchema) store_mod.Error!void {
444 if (schema.columns.len > std.math.maxInt(u32) or schema.indexes.len > std.math.maxInt(u32)) return error.InvalidHistory;
445 try appendU32(allocator, target, @intCast(schema.columns.len));
446 for (schema.columns) |column| {
447 try appendBytes(allocator, target, column.name);
448 try appendU8(allocator, target, @backingInt(column.column.collation));
449 try appendValue(allocator, target, column.default);
450 }
451 try appendU32(allocator, target, @intCast(schema.indexes.len));
452 for (schema.indexes) |index| {
453 if (index.fields.len > std.math.maxInt(u32) or index.columns.len > std.math.maxInt(u32)) return error.InvalidHistory;
454 try appendBytes(allocator, target, index.name);
455 try appendU32(allocator, target, @intCast(index.fields.len));
456 for (index.fields) |field| try appendU64(allocator, target, field);
457 try appendU32(allocator, target, @intCast(index.columns.len));
458 for (index.columns) |column| try appendU8(allocator, target, @backingInt(column.collation));
459 }
460 }
461
462 pub fn readRelationSchema(allocator: Allocator, reader: *PayloadReader) store_mod.Error!version.RelationSchema {
463 const column_count = try reader.readU32();
464 const columns = try allocator.alloc(catalog_mod.ColumnDefinition, column_count);
465 var read_columns: usize = 0;
466 errdefer {
467 for (columns[0..read_columns]) |*column| deinitColumn(allocator, column);
468 allocator.free(columns);
469 }
470 for (columns) |*column| {
471 const name = try allocator.dupe(u8, try reader.readBytes());
472 errdefer allocator.free(name);
473 const column_collation = try collation(try reader.readU8());
474 const default = try readValue(allocator, reader);
475 errdefer deinitValue(allocator, default);
476 column.* = .{
477 .name = name,
478 .column = .{ .collation = column_collation },
479 .default = default,
480 };
481 read_columns += 1;
482 }
483
484 const index_count = try reader.readU32();
485 const indexes = try allocator.alloc(catalog_mod.IndexDefinition, index_count);
486 var read_indexes: usize = 0;
487 errdefer {
488 for (indexes[0..read_indexes]) |*index| deinitIndex(allocator, index);
489 allocator.free(indexes);
490 }
491 for (indexes) |*index| {
492 const name = try allocator.dupe(u8, try reader.readBytes());
493 errdefer allocator.free(name);
494 const fields = try allocator.alloc(usize, try readUsize32(reader));
495 errdefer allocator.free(fields);
496 for (fields) |*field| field.* = try readUsize(reader);
497 const columns_value = try allocator.alloc(row.Column, try readUsize32(reader));
498 errdefer allocator.free(columns_value);
499 for (columns_value) |*column| column.* = .{ .collation = try collation(try reader.readU8()) };
500 index.* = .{
501 .name = name,
502 .fields = fields,
503 .columns = columns_value,
504 };
505 read_indexes += 1;
506 }
507
508 return .{
509 .allocator = allocator,
510 .columns = columns,
511 .indexes = indexes,
512 };
513 }
514
515 pub fn appendValue(allocator: Allocator, target: *std.ArrayList(u8), value: row.Value) store_mod.Error!void {
516 try appendU8(allocator, target, @backingInt(std.meta.activeTag(value)));
517 switch (value) {
518 .nil => {},
519 .integer => |integer| try appendI64(allocator, target, integer),
520 .text => |text| try appendBytes(allocator, target, text),
521 .blob => |blob| try appendBytes(allocator, target, blob),
522 }
523 }
524
525 pub fn readValue(allocator: Allocator, reader: *PayloadReader) store_mod.Error!row.Value {
526 return switch (try reader.readU8()) {
527 @backingInt(row.Storage.nil) => .nil,
528 @backingInt(row.Storage.integer) => .{ .integer = try reader.readI64() },
529 @backingInt(row.Storage.text) => .{ .text = try allocator.dupe(u8, try reader.readBytes()) },
530 @backingInt(row.Storage.blob) => .{ .blob = try allocator.dupe(u8, try reader.readBytes()) },
531 else => error.InvalidHistory,
532 };
533 }
534
535 pub fn deinitColumn(allocator: Allocator, column: *catalog_mod.ColumnDefinition) void {
536 allocator.free(column.name);
537 deinitValue(allocator, column.default);
538 column.* = undefined;
539 }
540
541 pub fn deinitIndex(allocator: Allocator, index: *catalog_mod.IndexDefinition) void {
542 allocator.free(index.name);
543 allocator.free(index.fields);
544 allocator.free(index.columns);
545 index.* = undefined;
546 }
547
548 pub fn deinitValue(allocator: Allocator, value: row.Value) void {
549 switch (value) {
550 .nil, .integer => {},
551 .text => |text| allocator.free(text),
552 .blob => |blob| allocator.free(blob),
553 }
554 }
555
556 pub fn collation(value: u8) store_mod.Error!row.Collation {
557 return switch (value) {
558 @backingInt(row.Collation.binary) => .binary,
559 @backingInt(row.Collation.nocase) => .nocase,
560 @backingInt(row.Collation.rtrim) => .rtrim,
561 else => error.InvalidHistory,
562 };
563 }
564
565 pub fn appendRelationRows(allocator: Allocator, target: *std.ArrayList(u8), rows: []const version.RelationRow) store_mod.Error!void {
566 if (rows.len > std.math.maxInt(u32)) return error.InvalidHistory;
567 try appendU32(allocator, target, @intCast(rows.len));
568 for (rows) |row_value| {
569 try appendI64(allocator, target, row_value.rowid);
570 try appendBytes(allocator, target, row_value.bytes);
571 }
572 }
573
574 pub fn readRelationRows(allocator: Allocator, reader: *PayloadReader) store_mod.Error![]version.RelationRow {
575 const row_count = try reader.readU32();
576 const rows = try allocator.alloc(version.RelationRow, row_count);
577 var read_rows: usize = 0;
578 errdefer {
579 for (rows[0..read_rows]) |row_value| allocator.free(row_value.bytes);
580 allocator.free(rows);
581 }
582 for (rows) |*row_value| {
583 const rowid = try reader.readI64();
584 const bytes = try allocator.dupe(u8, try reader.readBytes());
585 errdefer allocator.free(bytes);
586 row_value.* = .{
587 .rowid = rowid,
588 .bytes = bytes,
589 };
590 read_rows += 1;
591 }
592 return rows;
593 }
594
595 pub fn appendRelationRootMerkle(allocator: Allocator, target: *std.ArrayList(u8), root: version.RelationRoot, table_key: ?version.Hash, index_keys: []const ?version.Hash) store_mod.Error!void {
596 if (root.indexes.len > std.math.maxInt(u32) or root.indexes.len != index_keys.len) return error.InvalidHistory;
597 try appendU32(allocator, target, root.format);
598 try appendBytes(allocator, target, root.name);
599 try appendU32(allocator, target, root.catalog.format);
600 try appendU64(allocator, target, root.catalog.version);
601 try appendHash(allocator, target, root.schema);
602 try appendRelationSchema(allocator, target, root.schema_descriptor);
603 try appendMerkleMapRoot(allocator, target, root.table, table_key);
604 try appendStatsRoot(allocator, target, root.stats);
605 try appendU32(allocator, target, @intCast(root.indexes.len));
606 for (root.indexes, index_keys) |index, index_key| {
607 try appendHash(allocator, target, index.fields);
608 try appendMerkleMapRoot(allocator, target, index.map, index_key);
609 try appendHash(allocator, target, index.stats);
610 try appendHash(allocator, target, index.hash);
611 }
612 try appendHash(allocator, target, root.hash);
613 }
614
615 pub fn appendMerkleMapRoot(allocator: Allocator, target: *std.ArrayList(u8), root: version.MapRoot, root_key: ?version.Hash) store_mod.Error!void {
616 try appendSummary(allocator, target, root.summary);
617 try appendHash(allocator, target, root.hash);
618 try appendHash(allocator, target, root.subtree);
619 try appendOptionalHash(allocator, target, root_key);
620 }
621
622 pub fn appendTreeNodeContent(allocator: Allocator, target: *std.ArrayList(u8), node: *const tree.Node, children: []const version.Hash) store_mod.Error!void {
623 if (children.len > std.math.maxInt(u32)) return error.InvalidHistory;
624 try appendU8(allocator, target, @backingInt(node.kind));
625 try appendBytes(allocator, target, node.lower);
626 try appendOptionalBytes(allocator, target, node.upper);
627 try appendU64(allocator, target, node.depth);
628 try appendSummary(allocator, target, node.summary);
629 try appendHash(allocator, target, node.hash);
630 try appendU32(allocator, target, @intCast(children.len));
631 for (children) |child| try appendHash(allocator, target, child);
632 }
633
634 pub fn treeNodeKey(content: []const u8) version.Hash {
635 var hasher = std.crypto.hash.sha2.Sha256.init(.{});
636 hasher.update(tree_node_domain);
637 hasher.update(content);
638 var key: version.Hash = undefined;
639 hasher.final(&key);
640 return key;
641 }
642
643 pub fn appendMapRoot(allocator: Allocator, target: *std.ArrayList(u8), root: version.MapRoot) store_mod.Error!void {
644 if (root.nodes.len > std.math.maxInt(u32) or root.edges.len > std.math.maxInt(u32)) return error.InvalidHistory;
645 try appendSummary(allocator, target, root.summary);
646 try appendHash(allocator, target, root.hash);
647 try appendHash(allocator, target, root.subtree);
648 try appendU32(allocator, target, @intCast(root.nodes.len));
649 for (root.nodes) |node| {
650 try appendU8(allocator, target, @backingInt(node.kind));
651 try appendBytes(allocator, target, node.lower);
652 try appendOptionalBytes(allocator, target, node.upper);
653 try appendU64(allocator, target, node.depth);
654 try appendSummary(allocator, target, node.summary);
655 try appendHash(allocator, target, node.hash);
656 try appendU64(allocator, target, node.children_start);
657 try appendU64(allocator, target, node.children_len);
658 }
659 try appendU32(allocator, target, @intCast(root.edges.len));
660 for (root.edges) |edge| try appendU64(allocator, target, edge);
661 }
662
663 pub fn readMapRoot(allocator: Allocator, reader: *PayloadReader) store_mod.Error!version.MapRoot {
664 const summary = try readSummary(reader);
665 const hash = try reader.hash();
666 const subtree = try reader.hash();
667 const node_count = try reader.readU32();
668 const nodes = try allocator.alloc(tree.Node, node_count);
669 var read_nodes: usize = 0;
670 errdefer {
671 for (nodes[0..read_nodes]) |node| {
672 allocator.free(node.lower);
673 if (node.upper) |upper| allocator.free(upper);
674 }
675 allocator.free(nodes);
676 }
677 for (nodes) |*node| {
678 const kind = try nodeKind(try reader.readU8());
679 const lower = try allocator.dupe(u8, try reader.readBytes());
680 errdefer allocator.free(lower);
681 const upper_bytes = try reader.optionalBytes();
682 const upper = if (upper_bytes) |bytes| try allocator.dupe(u8, bytes) else null;
683 errdefer if (upper) |bytes| allocator.free(bytes);
684 node.* = .{
685 .kind = kind,
686 .lower = lower,
687 .upper = upper,
688 .depth = try readUsize(reader),
689 .summary = try readSummary(reader),
690 .hash = try reader.hash(),
691 .children_start = try readUsize(reader),
692 .children_len = try readUsize(reader),
693 };
694 read_nodes += 1;
695 }
696
697 const edge_count = try reader.readU32();
698 const edges = try allocator.alloc(usize, edge_count);
699 errdefer allocator.free(edges);
700 for (edges) |*edge| edge.* = try readUsize(reader);
701 return .{
702 .allocator = allocator,
703 .summary = summary,
704 .hash = hash,
705 .subtree = subtree,
706 .nodes = nodes,
707 .edges = edges,
708 };
709 }
710
711 pub fn appendStatsRoot(allocator: Allocator, target: *std.ArrayList(u8), root: version.StatsRoot) store_mod.Error!void {
712 if (root.table) |summary| {
713 try appendU8(allocator, target, 1);
714 try appendSummary(allocator, target, summary);
715 } else {
716 try appendU8(allocator, target, 0);
717 }
718 try appendU64(allocator, target, root.indexes);
719 try appendHash(allocator, target, root.hash);
720 }
721
722 pub fn readStatsRoot(reader: *PayloadReader) store_mod.Error!version.StatsRoot {
723 const table = switch (try reader.readU8()) {
724 0 => null,
725 1 => try readSummary(reader),
726 else => return error.InvalidHistory,
727 };
728 return .{
729 .table = table,
730 .indexes = try readUsize(reader),
731 .hash = try reader.hash(),
732 };
733 }
734
735 pub fn appendSummary(allocator: Allocator, target: *std.ArrayList(u8), summary: tree.Summary) Allocator.Error!void {
736 try appendU64(allocator, target, summary.branch_pages);
737 try appendU64(allocator, target, summary.leaf_pages);
738 try appendU64(allocator, target, summary.overflow_pages);
739 try appendU64(allocator, target, summary.entries);
740 try appendU64(allocator, target, summary.inline_records);
741 try appendU64(allocator, target, summary.overflow_records);
742 try appendU64(allocator, target, summary.max_depth);
743 try appendU64(allocator, target, summary.key_bytes);
744 try appendU64(allocator, target, summary.record_bytes);
745 try appendU64(allocator, target, summary.value_bytes);
746 }
747
748 pub fn readSummary(reader: *PayloadReader) store_mod.Error!tree.Summary {
749 return .{
750 .branch_pages = try readUsize(reader),
751 .leaf_pages = try readUsize(reader),
752 .overflow_pages = try readUsize(reader),
753 .entries = try readUsize(reader),
754 .inline_records = try readUsize(reader),
755 .overflow_records = try readUsize(reader),
756 .max_depth = try readUsize(reader),
757 .key_bytes = try readUsize(reader),
758 .record_bytes = try readUsize(reader),
759 .value_bytes = try readUsize(reader),
760 };
761 }
762
763 pub fn readUsize(reader: *PayloadReader) store_mod.Error!usize {
764 const value = try reader.readU64();
765 if (value > std.math.maxInt(usize)) return error.InvalidHistory;
766 return @intCast(value);
767 }
768
769 pub fn readUsize32(reader: *PayloadReader) store_mod.Error!usize {
770 return @intCast(try reader.readU32());
771 }
772
773 pub fn nodeKind(value: u8) store_mod.Error!tree.NodeKind {
774 return switch (value) {
775 @backingInt(tree.NodeKind.leaf) => .leaf,
776 @backingInt(tree.NodeKind.branch) => .branch,
777 else => error.InvalidHistory,
778 };
779 }
780
781 pub fn appendU8(allocator: Allocator, target: *std.ArrayList(u8), value: u8) Allocator.Error!void {
782 try target.append(allocator, value);
783 }
784
785 pub fn appendU32(allocator: Allocator, target: *std.ArrayList(u8), value: u32) Allocator.Error!void {
786 var encoded: [4]u8 = undefined;
787 std.mem.writeInt(u32, encoded[0..], value, .big);
788 try target.appendSlice(allocator, encoded[0..]);
789 }
790
791 pub fn appendU64(allocator: Allocator, target: *std.ArrayList(u8), value: anytype) Allocator.Error!void {
792 var encoded: [8]u8 = undefined;
793 std.mem.writeInt(u64, encoded[0..], @intCast(value), .big);
794 try target.appendSlice(allocator, encoded[0..]);
795 }
796
797 pub fn appendI64(allocator: Allocator, target: *std.ArrayList(u8), value: i64) Allocator.Error!void {
798 var encoded: [8]u8 = undefined;
799 std.mem.writeInt(i64, encoded[0..], value, .big);
800 try target.appendSlice(allocator, encoded[0..]);
801 }
802
803 pub fn readIntU32(bytes: []const u8) u32 {
804 return std.mem.readInt(u32, bytes[0..4], .big);
805 }
806
807 pub fn recordKind(value: u32) ?RecordKind {
808 return switch (value) {
809 @backingInt(RecordKind.database_root) => .database_root,
810 @backingInt(RecordKind.relation_root) => .relation_root,
811 @backingInt(RecordKind.relation_rows) => .relation_rows,
812 @backingInt(RecordKind.commit) => .commit,
813 @backingInt(RecordKind.ref) => .ref,
814 @backingInt(RecordKind.conflict) => .conflict,
815 @backingInt(RecordKind.conflict_root) => .conflict_root,
816 @backingInt(RecordKind.ref_delete) => .ref_delete,
817 @backingInt(RecordKind.row_chunk) => .row_chunk,
818 @backingInt(RecordKind.chunk_index_page) => .chunk_index_page,
819 @backingInt(RecordKind.tree_nodes) => .tree_nodes,
820 @backingInt(RecordKind.relation_spans) => .relation_spans,
821 @backingInt(RecordKind.fast_forward_prepare) => .fast_forward_prepare,
822 @backingInt(RecordKind.fast_forward_commit) => .fast_forward_commit,
823 @backingInt(RecordKind.fast_forward_abort) => .fast_forward_abort,
824 @backingInt(RecordKind.fast_forward_complete) => .fast_forward_complete,
825 else => null,
826 };
827 }
828
829 pub fn recordHash(kind: u32, payload: []const u8) version.Hash {
830 var builder = envelopeHasher(kind, @intCast(payload.len));
831 builder.update(payload);
832 var digest: version.Hash = undefined;
833 builder.final(&digest);
834 return digest;
835 }
836
837 /// Starts the v4 envelope hash for a payload streamed in fixed-size pieces.
838 pub fn envelopeHasher(kind: u32, payload_len: u32) std.crypto.hash.sha2.Sha256 {
839 var builder = std.crypto.hash.sha2.Sha256.init(.{});
840 writeHashU32(&builder, magic);
841 writeHashU32(&builder, format_version);
842 writeHashU32(&builder, kind);
843 writeHashU32(&builder, payload_len);
844 return builder;
845 }
846
847 pub fn writeHashU32(builder: *std.crypto.hash.sha2.Sha256, value: u32) void {
848 var encoded: [4]u8 = undefined;
849 std.mem.writeInt(u32, encoded[0..], value, .big);
850 builder.update(encoded[0..]);
851 }