lib/sql/src/version.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const simd = @import("simd");
3 const catalog_mod = @import("catalog.zig");
4 const key = @import("key.zig");
5 const page = @import("page.zig");
6 const relation_mod = @import("relation.zig");
7 const row = @import("row.zig");
8 const tree = @import("tree.zig");
9 const wal = @import("wal.zig");
10
11 const Bytes = simd.ScalableTag(u8);
12
13 const Allocator = std.mem.Allocator;
14
15 pub const hash_bytes = 32;
16 pub const format_version: u32 = 1;
17
18 pub const Hash = [hash_bytes]u8;
19
20 pub const Error = Allocator.Error || tree.Error || row.Error || key.Error || relation_mod.Error || catalog_mod.Error;
21
22 pub const MapRoot = tree.Root;
23
24 pub const IndexRoot = struct {
25 fields: Hash,
26 map: MapRoot,
27 stats: Hash,
28 hash: Hash,
29
30 pub fn deinit(self: *IndexRoot) void {
31 self.map.deinit();
32 self.* = undefined;
33 }
34
35 pub fn clone(self: *const IndexRoot, allocator: Allocator) Allocator.Error!IndexRoot {
36 return .{
37 .fields = self.fields,
38 .map = try self.map.clone(allocator),
39 .stats = self.stats,
40 .hash = self.hash,
41 };
42 }
43 };
44
45 pub const StatsRoot = struct {
46 table: ?tree.Summary = null,
47 indexes: usize = 0,
48 hash: Hash,
49 };
50
51 pub const RelationSchema = struct {
52 allocator: Allocator,
53 columns: []catalog_mod.ColumnDefinition,
54 indexes: []catalog_mod.IndexDefinition,
55
56 pub fn init(allocator: Allocator, columns: []const catalog_mod.ColumnDefinition, indexes: []const catalog_mod.IndexDefinition) Allocator.Error!RelationSchema {
57 const owned_columns = try allocator.alloc(catalog_mod.ColumnDefinition, columns.len);
58 var column_count: usize = 0;
59 errdefer {
60 for (owned_columns[0..column_count]) |*column| deinitColumn(allocator, column);
61 allocator.free(owned_columns);
62 }
63 for (columns, owned_columns) |column, *target| {
64 target.* = try cloneColumn(allocator, column);
65 column_count += 1;
66 }
67
68 const owned_indexes = try allocator.alloc(catalog_mod.IndexDefinition, indexes.len);
69 var index_count: usize = 0;
70 errdefer {
71 for (owned_indexes[0..index_count]) |*index| deinitIndex(allocator, index);
72 allocator.free(owned_indexes);
73 }
74 for (indexes, owned_indexes) |index, *target| {
75 target.* = try cloneIndex(allocator, index);
76 index_count += 1;
77 }
78
79 return .{
80 .allocator = allocator,
81 .columns = owned_columns,
82 .indexes = owned_indexes,
83 };
84 }
85
86 pub fn deinit(self: *RelationSchema) void {
87 for (self.columns) |*column| deinitColumn(self.allocator, column);
88 for (self.indexes) |*index| deinitIndex(self.allocator, index);
89 self.allocator.free(self.columns);
90 self.allocator.free(self.indexes);
91 self.* = undefined;
92 }
93
94 pub fn clone(self: *const RelationSchema, allocator: Allocator) Allocator.Error!RelationSchema {
95 return try RelationSchema.init(allocator, self.columns, self.indexes);
96 }
97 };
98
99 pub const RelationRoot = struct {
100 allocator: Allocator,
101 format: u32 = format_version,
102 name: []u8,
103 catalog: catalog_mod.Schema,
104 schema: Hash,
105 schema_descriptor: RelationSchema,
106 table: MapRoot,
107 indexes: []IndexRoot,
108 stats: StatsRoot,
109 hash: Hash,
110
111 pub fn deinit(self: *RelationRoot) void {
112 self.table.deinit();
113 for (self.indexes) |*index| index.deinit();
114 self.allocator.free(self.indexes);
115 self.schema_descriptor.deinit();
116 self.allocator.free(self.name);
117 self.* = undefined;
118 }
119
120 pub fn clone(self: *const RelationRoot, allocator: Allocator) Allocator.Error!RelationRoot {
121 const name = try allocator.dupe(u8, self.name);
122 errdefer allocator.free(name);
123 var table = try self.table.clone(allocator);
124 errdefer table.deinit();
125 const indexes = try allocator.alloc(IndexRoot, self.indexes.len);
126 var index_count: usize = 0;
127 errdefer {
128 for (indexes[0..index_count]) |*index| index.deinit();
129 allocator.free(indexes);
130 }
131 for (self.indexes, indexes) |index, *target| {
132 target.* = try index.clone(allocator);
133 index_count += 1;
134 }
135 var schema_descriptor = try self.schema_descriptor.clone(allocator);
136 errdefer schema_descriptor.deinit();
137 return .{
138 .allocator = allocator,
139 .format = self.format,
140 .name = name,
141 .catalog = self.catalog,
142 .schema = self.schema,
143 .schema_descriptor = schema_descriptor,
144 .table = table,
145 .indexes = indexes,
146 .stats = self.stats,
147 .hash = self.hash,
148 };
149 }
150 };
151
152 pub const RelationEntry = struct {
153 name: []const u8,
154 hash: Hash,
155 };
156
157 pub const RelationRow = struct {
158 rowid: i64,
159 bytes: []u8,
160 };
161
162 pub const RelationValue = struct {
163 root: RelationRoot,
164 rows: []RelationRow,
165
166 pub fn deinit(self: *RelationValue, allocator: Allocator) void {
167 self.root.deinit();
168 freeRelationRows(allocator, self.rows);
169 self.* = undefined;
170 }
171
172 pub fn clone(self: *const RelationValue, allocator: Allocator) Allocator.Error!RelationValue {
173 var root = try self.root.clone(allocator);
174 errdefer root.deinit();
175 const rows = try cloneRelationRows(allocator, self.rows);
176 return .{
177 .root = root,
178 .rows = rows,
179 };
180 }
181 };
182
183 pub const ConflictKind = enum(u8) {
184 row,
185 relation,
186 };
187
188 pub const ConflictValue = union(ConflictKind) {
189 row: []const u8,
190 relation: Hash,
191 };
192
193 pub const ConflictEntry = struct {
194 kind: ConflictKind = .row,
195 relation: []const u8,
196 rowid: i64 = 0,
197 hash: Hash,
198
199 pub fn eql(left: ConflictEntry, right: ConflictEntry) bool {
200 return left.kind == right.kind and
201 std.mem.eql(u8, left.relation, right.relation) and
202 (left.kind == .relation or left.rowid == right.rowid) and
203 same(left.hash, right.hash);
204 }
205
206 pub fn sameSlot(left: ConflictEntry, right: ConflictEntry) bool {
207 return left.kind == right.kind and
208 std.mem.eql(u8, left.relation, right.relation) and
209 (left.kind == .relation or left.rowid == right.rowid);
210 }
211
212 pub fn lessThan(_: void, left: ConflictEntry, right: ConflictEntry) bool {
213 const relation_order = simd.order(Bytes, left.relation, right.relation);
214 if (relation_order != .eq) return relation_order == .lt;
215 if (left.kind != right.kind) return @backingInt(left.kind) < @backingInt(right.kind);
216 if (left.kind == .row and left.rowid != right.rowid) return left.rowid < right.rowid;
217 return simd.order(Bytes, left.hash[0..], right.hash[0..]) == .lt;
218 }
219 };
220
221 pub const ConflictRoot = struct {
222 hash: Hash,
223 count: usize = 0,
224
225 pub fn empty() ConflictRoot {
226 return .{
227 .hash = emptyHash("sql.conflicts.empty"),
228 };
229 }
230
231 pub fn init(entries: []const ConflictEntry) ConflictRoot {
232 var builder = Builder.init("sql.conflicts");
233 builder.writeU64(entries.len);
234 for (entries) |entry| {
235 builder.writeU8(@backingInt(entry.kind));
236 builder.bytes(entry.relation);
237 if (entry.kind == .row) builder.writeI64(entry.rowid);
238 builder.hash(entry.hash);
239 }
240 return .{
241 .hash = builder.finish(),
242 .count = entries.len,
243 };
244 }
245
246 pub fn initSorted(allocator: Allocator, entries: []const ConflictEntry) Allocator.Error!ConflictRoot {
247 const sorted = try allocator.dupe(ConflictEntry, entries);
248 defer allocator.free(sorted);
249 std.mem.sort(ConflictEntry, sorted, {}, ConflictEntry.lessThan);
250 return init(sorted);
251 }
252 };
253
254 pub const ConflictArtifact = struct {
255 kind: ConflictKind = .row,
256 relation: []const u8,
257 rowid: i64 = 0,
258 base: ?ConflictValue = null,
259 ours: ?ConflictValue = null,
260 theirs: ?ConflictValue = null,
261 hash: Hash,
262
263 pub fn init(relation: []const u8, rowid: i64, base: ?[]const u8, ours: ?[]const u8, theirs: ?[]const u8) ConflictArtifact {
264 return initRow(relation, rowid, base, ours, theirs);
265 }
266
267 pub fn initRow(relation: []const u8, rowid: i64, base: ?[]const u8, ours: ?[]const u8, theirs: ?[]const u8) ConflictArtifact {
268 var builder = Builder.init("sql.conflict");
269 builder.writeU8(@backingInt(ConflictKind.row));
270 builder.bytes(relation);
271 builder.writeI64(rowid);
272 builder.optionalConflictValue(.row, if (base) |value| ConflictValue{ .row = value } else null);
273 builder.optionalConflictValue(.row, if (ours) |value| ConflictValue{ .row = value } else null);
274 builder.optionalConflictValue(.row, if (theirs) |value| ConflictValue{ .row = value } else null);
275 return .{
276 .kind = .row,
277 .relation = relation,
278 .rowid = rowid,
279 .base = if (base) |value| .{ .row = value } else null,
280 .ours = if (ours) |value| .{ .row = value } else null,
281 .theirs = if (theirs) |value| .{ .row = value } else null,
282 .hash = builder.finish(),
283 };
284 }
285
286 pub fn initRelation(relation: []const u8, base: ?Hash, ours: ?Hash, theirs: ?Hash) ConflictArtifact {
287 var builder = Builder.init("sql.conflict");
288 builder.writeU8(@backingInt(ConflictKind.relation));
289 builder.bytes(relation);
290 builder.optionalConflictValue(.relation, if (base) |value| ConflictValue{ .relation = value } else null);
291 builder.optionalConflictValue(.relation, if (ours) |value| ConflictValue{ .relation = value } else null);
292 builder.optionalConflictValue(.relation, if (theirs) |value| ConflictValue{ .relation = value } else null);
293 return .{
294 .kind = .relation,
295 .relation = relation,
296 .base = if (base) |value| .{ .relation = value } else null,
297 .ours = if (ours) |value| .{ .relation = value } else null,
298 .theirs = if (theirs) |value| .{ .relation = value } else null,
299 .hash = builder.finish(),
300 };
301 }
302
303 pub fn entry(self: ConflictArtifact) ConflictEntry {
304 return .{
305 .kind = self.kind,
306 .relation = self.relation,
307 .rowid = self.rowid,
308 .hash = self.hash,
309 };
310 }
311 };
312
313 pub const DatabaseRoot = struct {
314 allocator: ?Allocator = null,
315 format: u32 = format_version,
316 feature: u32 = 0,
317 entries: []const RelationEntry = &.{},
318 conflicts: Hash,
319 hash: Hash,
320
321 pub fn init(entries: []const RelationEntry, conflicts: ConflictRoot) DatabaseRoot {
322 var builder = Builder.init("sql.database");
323 builder.writeU32(format_version);
324 builder.writeU32(0);
325 builder.hash(conflicts.hash);
326 builder.writeU64(entries.len);
327 for (entries) |entry| {
328 builder.bytes(entry.name);
329 builder.hash(entry.hash);
330 }
331 return .{
332 .entries = entries,
333 .conflicts = conflicts.hash,
334 .hash = builder.finish(),
335 };
336 }
337
338 pub fn initSorted(allocator: Allocator, entries: []const RelationEntry, conflicts: ConflictRoot) Allocator.Error!DatabaseRoot {
339 const sorted = try allocator.alloc(RelationEntry, entries.len);
340 var copied: usize = 0;
341 errdefer {
342 for (sorted[0..copied]) |entry| allocator.free(entry.name);
343 allocator.free(sorted);
344 }
345 for (entries, sorted) |entry, *target| {
346 target.* = .{
347 .name = try allocator.dupe(u8, entry.name),
348 .hash = entry.hash,
349 };
350 copied += 1;
351 }
352 std.mem.sort(RelationEntry, sorted, {}, relationEntryLessThan);
353 var root = init(sorted, conflicts);
354 root.allocator = allocator;
355 return root;
356 }
357
358 pub fn clone(self: *const DatabaseRoot, allocator: Allocator) Allocator.Error!DatabaseRoot {
359 return try self.withConflicts(allocator, self.conflicts);
360 }
361
362 pub fn withConflicts(
363 self: *const DatabaseRoot,
364 allocator: Allocator,
365 conflicts: Hash,
366 ) Allocator.Error!DatabaseRoot {
367 return try initSorted(allocator, self.entries, .{ .hash = conflicts });
368 }
369
370 pub fn deinit(self: *DatabaseRoot) void {
371 if (self.allocator) |allocator| {
372 for (self.entries) |entry| allocator.free(entry.name);
373 allocator.free(self.entries);
374 }
375 self.* = undefined;
376 }
377 };
378
379 pub const DatabaseValue = struct {
380 allocator: Allocator,
381 root: DatabaseRoot,
382 relations: []RelationValue,
383
384 pub fn deinit(self: *DatabaseValue) void {
385 self.root.deinit();
386 for (self.relations) |*relation| relation.deinit(self.allocator);
387 if (self.relations.len != 0) self.allocator.free(self.relations);
388 self.* = undefined;
389 }
390
391 pub fn intoRoot(self: *DatabaseValue) DatabaseRoot {
392 const root = self.root;
393 for (self.relations) |*relation| relation.deinit(self.allocator);
394 if (self.relations.len != 0) self.allocator.free(self.relations);
395 self.* = undefined;
396 return root;
397 }
398
399 pub fn clone(self: *const DatabaseValue, allocator: Allocator) Allocator.Error!DatabaseValue {
400 var root = try self.root.clone(allocator);
401 errdefer root.deinit();
402 const relations = try allocator.alloc(RelationValue, self.relations.len);
403 var relation_count: usize = 0;
404 errdefer {
405 for (relations[0..relation_count]) |*relation| relation.deinit(allocator);
406 if (relations.len != 0) allocator.free(relations);
407 }
408 for (self.relations, relations) |relation, *target| {
409 target.* = try relation.clone(allocator);
410 relation_count += 1;
411 }
412 return .{
413 .allocator = allocator,
414 .root = root,
415 .relations = relations,
416 };
417 }
418
419 pub fn findRelation(self: *const DatabaseValue, name: []const u8) ?*const RelationValue {
420 for (self.relations) |*relation_value| {
421 if (std.mem.eql(u8, relation_value.root.name, name)) return relation_value;
422 }
423 return null;
424 }
425 };
426
427 pub const Commit = struct {
428 root: Hash,
429 parents: []const Hash = &.{},
430 hash: Hash,
431
432 pub fn init(root: Hash, parents: []const Hash) Commit {
433 var builder = Builder.init("sql.commit");
434 builder.hash(root);
435 builder.writeU64(parents.len);
436 for (parents) |parent| builder.hash(parent);
437 return .{
438 .root = root,
439 .parents = parents,
440 .hash = builder.finish(),
441 };
442 }
443 };
444
445 pub const Ref = struct {
446 name: []const u8,
447 target: Hash,
448 };
449
450 pub const WorkingSet = struct {
451 base: Hash,
452 working: Hash,
453 staged: Hash,
454
455 pub fn init(base: Hash) WorkingSet {
456 return .{
457 .base = base,
458 .working = base,
459 .staged = base,
460 };
461 }
462
463 pub fn withWorking(self: WorkingSet, working: Hash) WorkingSet {
464 return .{
465 .base = self.base,
466 .working = working,
467 .staged = self.staged,
468 };
469 }
470
471 pub fn stage(self: WorkingSet) WorkingSet {
472 return .{
473 .base = self.base,
474 .working = self.working,
475 .staged = self.working,
476 };
477 }
478
479 pub fn advance(self: WorkingSet, base: Hash) WorkingSet {
480 _ = self;
481 return WorkingSet.init(base);
482 }
483
484 pub fn dirty(self: WorkingSet) bool {
485 return !same(self.base, self.working);
486 }
487
488 pub fn hasStaged(self: WorkingSet) bool {
489 return !same(self.base, self.staged);
490 }
491 };
492
493 pub fn emptyHash(kind: []const u8) Hash {
494 var builder = Builder.init(kind);
495 return builder.finish();
496 }
497
498 pub fn same(left: Hash, right: Hash) bool {
499 return std.mem.eql(u8, left[0..], right[0..]);
500 }
501
502 pub fn relationRoot(allocator: Allocator, name: []const u8, catalog_schema: catalog_mod.Schema, handle: *const catalog_mod.RelationHandle, stats: ?*const catalog_mod.RelationStats) Error!RelationRoot {
503 const owned_name = try allocator.dupe(u8, name);
504 errdefer allocator.free(owned_name);
505
506 var table_root = try mapRoot(allocator, &handle.relation.table.rows);
507 errdefer table_root.deinit();
508 var schema_descriptor = try RelationSchema.init(allocator, handle.definitions, handle.index_definitions);
509 errdefer schema_descriptor.deinit();
510 const schema_hash = schemaHash(schema_descriptor.columns, schema_descriptor.indexes);
511 const stats_root = relationStatsRoot(stats);
512 const indexes = try allocator.alloc(IndexRoot, handle.specs.len);
513 var index_count: usize = 0;
514 errdefer {
515 for (indexes[0..index_count]) |*index| index.deinit();
516 allocator.free(indexes);
517 }
518
519 for (handle.specs, indexes) |spec, *target| {
520 var index_tree = try handle.relation.space.tree(spec.root_page);
521 var map = try mapRoot(allocator, &index_tree);
522 var map_assigned = false;
523 errdefer if (!map_assigned) map.deinit();
524 const index_stats = findIndexStats(stats, spec.root_page);
525 const index_stats_hash = indexStatsHash(index_stats);
526 target.* = .{
527 .fields = fieldsHash(spec.fields, spec.columns),
528 .map = map,
529 .stats = index_stats_hash,
530 .hash = indexHash(spec.fields, spec.columns, map.hash, index_stats_hash),
531 };
532 map_assigned = true;
533 index_count += 1;
534 }
535
536 var builder = Builder.init("sql.relation");
537 builder.writeU32(format_version);
538 builder.bytes(name);
539 builder.hash(schema_hash);
540 builder.hash(table_root.hash);
541 builder.hash(stats_root.hash);
542 builder.writeU64(indexes.len);
543 for (indexes) |index| builder.hash(index.hash);
544
545 return .{
546 .allocator = allocator,
547 .name = owned_name,
548 .catalog = .{
549 .format = catalog_schema.format,
550 .version = catalog_schema.version,
551 },
552 .schema = schema_hash,
553 .schema_descriptor = schema_descriptor,
554 .table = table_root,
555 .indexes = indexes,
556 .stats = stats_root,
557 .hash = builder.finish(),
558 };
559 }
560
561 pub fn relationRootMaintained(
562 allocator: Allocator,
563 name: []const u8,
564 catalog_schema: catalog_mod.Schema,
565 handle: *const catalog_mod.RelationHandle,
566 stats: ?*const catalog_mod.RelationStats,
567 ) Error!RelationRoot {
568 return try relationRootMaintainedFrom(allocator, name, catalog_schema, handle, stats);
569 }
570
571 pub fn readRelationRootMaintained(
572 allocator: Allocator,
573 name: []const u8,
574 catalog_schema: catalog_mod.Schema,
575 handle: *const catalog_mod.ReadRelationHandle,
576 stats: ?*const catalog_mod.RelationStats,
577 ) Error!RelationRoot {
578 return try relationRootMaintainedFrom(allocator, name, catalog_schema, handle, stats);
579 }
580
581 fn relationRootMaintainedFrom(
582 allocator: Allocator,
583 name: []const u8,
584 catalog_schema: catalog_mod.Schema,
585 handle: anytype,
586 stats: ?*const catalog_mod.RelationStats,
587 ) Error!RelationRoot {
588 const owned_name = try allocator.dupe(u8, name);
589 errdefer allocator.free(owned_name);
590
591 var table_root = try mapRootFromIdentity(allocator, &handle.relation.table.rows);
592 errdefer table_root.deinit();
593 var schema_descriptor = try RelationSchema.init(allocator, handle.definitions, handle.index_definitions);
594 errdefer schema_descriptor.deinit();
595 const schema_hash = schemaHash(schema_descriptor.columns, schema_descriptor.indexes);
596 const stats_root = relationStatsRoot(stats);
597 const indexes = try allocator.alloc(IndexRoot, handle.specs.len);
598 var index_count: usize = 0;
599 errdefer {
600 for (indexes[0..index_count]) |*index| index.deinit();
601 allocator.free(indexes);
602 }
603
604 for (handle.specs, indexes) |spec, *target| {
605 var index_tree = try handle.relation.space.tree(spec.root_page);
606 var map = try mapRootFromIdentity(allocator, &index_tree);
607 var map_assigned = false;
608 errdefer if (!map_assigned) map.deinit();
609 const index_stats = findIndexStats(stats, spec.root_page);
610 const index_stats_hash = indexStatsHash(index_stats);
611 target.* = .{
612 .fields = fieldsHash(spec.fields, spec.columns),
613 .map = map,
614 .stats = index_stats_hash,
615 .hash = indexHash(spec.fields, spec.columns, map.hash, index_stats_hash),
616 };
617 map_assigned = true;
618 index_count += 1;
619 }
620
621 var builder = Builder.init("sql.relation");
622 builder.writeU32(format_version);
623 builder.bytes(name);
624 builder.hash(schema_hash);
625 builder.hash(table_root.hash);
626 builder.hash(stats_root.hash);
627 builder.writeU64(indexes.len);
628 for (indexes) |index| builder.hash(index.hash);
629
630 return .{
631 .allocator = allocator,
632 .name = owned_name,
633 .catalog = .{
634 .format = catalog_schema.format,
635 .version = catalog_schema.version,
636 },
637 .schema = schema_hash,
638 .schema_descriptor = schema_descriptor,
639 .table = table_root,
640 .indexes = indexes,
641 .stats = stats_root,
642 .hash = builder.finish(),
643 };
644 }
645
646 pub const RelationKey = struct {
647 schema: Hash,
648 table: Hash,
649 stats: Hash,
650 hash: Hash,
651 };
652
653 pub fn relationKey(
654 name: []const u8,
655 handle: *const catalog_mod.RelationHandle,
656 stats: ?*const catalog_mod.RelationStats,
657 ) Error!RelationKey {
658 const schema_hash = schemaHash(handle.definitions, handle.index_definitions);
659 const table_identity = try handle.relation.table.rows.identity();
660 const table_hash = handle.relation.table.rows.digestIdentity(&table_identity);
661 const stats_hash = relationStatsRoot(stats).hash;
662 var builder = Builder.init("sql.relation");
663 builder.writeU32(format_version);
664 builder.bytes(name);
665 builder.hash(schema_hash);
666 builder.hash(table_hash);
667 builder.hash(stats_hash);
668 builder.writeU64(handle.specs.len);
669 for (handle.specs) |spec| {
670 var index_tree = try handle.relation.space.tree(spec.root_page);
671 const index_identity = try index_tree.identity();
672 const map_hash = index_tree.digestIdentity(&index_identity);
673 const index_stats_hash = indexStatsHash(findIndexStats(stats, spec.root_page));
674 builder.hash(indexHash(spec.fields, spec.columns, map_hash, index_stats_hash));
675 }
676 return .{
677 .schema = schema_hash,
678 .table = table_hash,
679 .stats = stats_hash,
680 .hash = builder.finish(),
681 };
682 }
683
684 fn mapRootFromIdentity(allocator: Allocator, stored: anytype) Error!MapRoot {
685 const identity = try stored.identity();
686 const nodes = try allocator.alloc(tree.Node, 0);
687 errdefer allocator.free(nodes);
688 const edges = try allocator.alloc(usize, 0);
689 errdefer allocator.free(edges);
690 return .{
691 .allocator = allocator,
692 .summary = .{
693 .entries = @intCast(identity.entries),
694 .key_bytes = @intCast(identity.key_bytes),
695 .record_bytes = @intCast(identity.value_bytes),
696 .value_bytes = @intCast(identity.value_bytes),
697 },
698 .hash = stored.digestIdentity(&identity),
699 .subtree = std.mem.zeroes(Hash),
700 .nodes = nodes,
701 .edges = edges,
702 };
703 }
704
705 pub fn relationRows(allocator: Allocator, handle: *const catalog_mod.RelationHandle) Error![]RelationRow {
706 var rows: std.ArrayList(RelationRow) = .empty;
707 errdefer {
708 for (rows.items) |row_value| allocator.free(row_value.bytes);
709 rows.deinit(allocator);
710 }
711
712 var scan: relation_mod.Scan = undefined;
713 try handle.relation.scan(&scan, allocator, null, null);
714 defer scan.deinit();
715 while (try scan.next()) |entry| {
716 const bytes = try allocator.dupe(u8, entry.bytes);
717 errdefer allocator.free(bytes);
718 try rows.append(allocator, .{
719 .rowid = entry.rowid,
720 .bytes = bytes,
721 });
722 }
723 return try rows.toOwnedSlice(allocator);
724 }
725
726 pub fn cloneRelationRows(allocator: Allocator, rows: []const RelationRow) Allocator.Error![]RelationRow {
727 const cloned = try allocator.alloc(RelationRow, rows.len);
728 var count: usize = 0;
729 errdefer {
730 for (cloned[0..count]) |row_value| allocator.free(row_value.bytes);
731 allocator.free(cloned);
732 }
733 for (rows, cloned) |row_value, *target| {
734 target.* = .{
735 .rowid = row_value.rowid,
736 .bytes = try allocator.dupe(u8, row_value.bytes),
737 };
738 count += 1;
739 }
740 std.mem.sort(RelationRow, cloned, {}, relationRowLessThan);
741 return cloned;
742 }
743
744 pub fn freeRelationRows(allocator: Allocator, rows: []RelationRow) void {
745 for (rows) |row_value| allocator.free(row_value.bytes);
746 if (rows.len != 0) allocator.free(rows);
747 }
748
749 pub fn relationValue(allocator: Allocator, name: []const u8, catalog_schema: catalog_mod.Schema, handle: *const catalog_mod.RelationHandle, stats: ?*const catalog_mod.RelationStats) Error!RelationValue {
750 var root = try relationRootMaintained(allocator, name, catalog_schema, handle, stats);
751 defer root.deinit();
752 return try relationValueFromRoot(allocator, &root, handle);
753 }
754
755 pub fn relationValueFromRoot(allocator: Allocator, root: *const RelationRoot, handle: *const catalog_mod.RelationHandle) Error!RelationValue {
756 var owned_root = try root.clone(allocator);
757 errdefer owned_root.deinit();
758 const rows = try relationRows(allocator, handle);
759 errdefer freeRelationRows(allocator, rows);
760 return .{
761 .root = owned_root,
762 .rows = rows,
763 };
764 }
765
766 pub fn relationRootFromRows(allocator: Allocator, source: *const RelationRoot, rows: []const RelationRow) Error!RelationRoot {
767 return try relationRootFromRowsWithOptionalStats(allocator, source, rows, null);
768 }
769
770 pub fn relationRootFromRowsWithStats(
771 allocator: Allocator,
772 source: *const RelationRoot,
773 rows: []const RelationRow,
774 stats: *const catalog_mod.RelationStats,
775 ) Error!RelationRoot {
776 return try relationRootFromRowsWithOptionalStats(allocator, source, rows, stats);
777 }
778
779 fn relationRootFromRowsWithOptionalStats(
780 allocator: Allocator,
781 source: *const RelationRoot,
782 rows: []const RelationRow,
783 stats: ?*const catalog_mod.RelationStats,
784 ) Error!RelationRoot {
785 const owned_name = try allocator.dupe(u8, source.name);
786 errdefer allocator.free(owned_name);
787
788 var table_root = try tableRootFromRows(allocator, rows);
789 errdefer table_root.deinit();
790 var schema_descriptor = try source.schema_descriptor.clone(allocator);
791 errdefer schema_descriptor.deinit();
792 const schema_hash = schemaHash(schema_descriptor.columns, schema_descriptor.indexes);
793 if (stats) |relation_stats| {
794 if (relation_stats.indexes.len != schema_descriptor.indexes.len) {
795 return error.CatalogCorrupt;
796 }
797 if (!logicalSummaryEqual(table_root.summary, relation_stats.table)) {
798 return error.CatalogCorrupt;
799 }
800 }
801 const stats_root = relationStatsRoot(stats);
802 const indexes = try relationIndexesFromRows(
803 allocator,
804 rows,
805 schema_descriptor.indexes,
806 stats,
807 );
808 errdefer freeIndexRoots(allocator, indexes);
809
810 var builder = Builder.init("sql.relation");
811 builder.writeU32(format_version);
812 builder.bytes(source.name);
813 builder.hash(schema_hash);
814 builder.hash(table_root.hash);
815 builder.hash(stats_root.hash);
816 builder.writeU64(indexes.len);
817 for (indexes) |index| builder.hash(index.hash);
818
819 return .{
820 .allocator = allocator,
821 .name = owned_name,
822 .catalog = source.catalog,
823 .schema = schema_hash,
824 .schema_descriptor = schema_descriptor,
825 .table = table_root,
826 .indexes = indexes,
827 .stats = stats_root,
828 .hash = builder.finish(),
829 };
830 }
831
832 fn relationIndexesFromRows(
833 allocator: Allocator,
834 rows: []const RelationRow,
835 definitions: []const catalog_mod.IndexDefinition,
836 stats: ?*const catalog_mod.RelationStats,
837 ) Error![]IndexRoot {
838 const indexes = try allocator.alloc(IndexRoot, definitions.len);
839 var index_count: usize = 0;
840 errdefer {
841 for (indexes[0..index_count]) |*index| index.deinit();
842 allocator.free(indexes);
843 }
844
845 for (definitions, indexes, 0..) |definition, *target, index_offset| {
846 var map = try indexRootFromRows(
847 allocator,
848 rows,
849 definition.fields,
850 definition.columns,
851 );
852 var map_assigned = false;
853 errdefer if (!map_assigned) map.deinit();
854 const index_stats = if (stats) |relation_stats|
855 &relation_stats.indexes[index_offset]
856 else
857 null;
858 if (index_stats) |prepared| {
859 if (!std.mem.eql(u8, prepared.name, definition.name)) {
860 return error.CatalogCorrupt;
861 }
862 if (!logicalSummaryEqual(map.summary, prepared.summary)) {
863 return error.CatalogCorrupt;
864 }
865 }
866 const stats_hash = indexStatsHash(index_stats);
867 target.* = .{
868 .fields = fieldsHash(definition.fields, definition.columns),
869 .map = map,
870 .stats = stats_hash,
871 .hash = indexHash(
872 definition.fields,
873 definition.columns,
874 map.hash,
875 stats_hash,
876 ),
877 };
878 map_assigned = true;
879 index_count += 1;
880 }
881 return indexes;
882 }
883
884 fn freeIndexRoots(allocator: Allocator, indexes: []IndexRoot) void {
885 for (indexes) |*index| index.deinit();
886 allocator.free(indexes);
887 }
888
889 pub fn relationValueApplyingMaterializedEdits(allocator: Allocator, base: *const RelationValue, edits: []const relation_mod.Edit) Error!RelationValue {
890 const rows = try relationRowsApplyingEdits(allocator, base.rows, edits);
891 errdefer freeRelationRows(allocator, rows);
892 var root = try relationRootFromRows(allocator, &base.root, rows);
893 errdefer root.deinit();
894 return .{
895 .root = root,
896 .rows = rows,
897 };
898 }
899
900 pub fn databaseValue(
901 allocator: Allocator,
902 catalog: *const catalog_mod.Catalog,
903 conflicts: Hash,
904 ) Error!DatabaseValue {
905 return try databaseValueReplacingRelations(allocator, catalog, &.{}, conflicts);
906 }
907
908 pub fn databaseValueReplacingRelations(
909 allocator: Allocator,
910 catalog: *const catalog_mod.Catalog,
911 replacements: []const RelationValue,
912 conflicts: Hash,
913 ) Error!DatabaseValue {
914 var names = try catalog.relationNames(allocator);
915 defer names.deinit();
916
917 const relations = try allocator.alloc(RelationValue, names.names.len);
918 var relation_count: usize = 0;
919 var relations_owned = true;
920 errdefer {
921 if (relations_owned) {
922 for (relations[0..relation_count]) |*relation| relation.deinit(allocator);
923 if (relations.len != 0) allocator.free(relations);
924 }
925 }
926
927 for (names.names, relations) |name, *relation| {
928 if (replacementRelation(replacements, name)) |replacement| {
929 relation.* = try replacement.clone(allocator);
930 } else {
931 var state = try catalog.readRelation(allocator, name);
932 defer state.deinit();
933 relation.* = try relationValue(
934 allocator,
935 name,
936 state.schema,
937 &state.handle,
938 state.relationStats(),
939 );
940 }
941 relation_count += 1;
942 }
943
944 const value = try databaseValueFromOwnedRelations(allocator, relations, conflicts);
945 relations_owned = false;
946 return value;
947 }
948
949 pub fn databaseValueFromOwnedRelations(allocator: Allocator, relations: []RelationValue, conflicts: Hash) Allocator.Error!DatabaseValue {
950 const entries = try allocator.alloc(RelationEntry, relations.len);
951 defer allocator.free(entries);
952
953 for (relations, entries) |relation, *entry| {
954 entry.* = .{
955 .name = relation.root.name,
956 .hash = relation.root.hash,
957 };
958 }
959
960 var root = try DatabaseRoot.initSorted(allocator, entries, .{ .hash = conflicts });
961 errdefer root.deinit();
962 return .{
963 .allocator = allocator,
964 .root = root,
965 .relations = relations,
966 };
967 }
968
969 fn replacementRelation(replacements: []const RelationValue, name: []const u8) ?*const RelationValue {
970 for (replacements) |*replacement| {
971 if (std.mem.eql(u8, replacement.root.name, name)) return replacement;
972 }
973 return null;
974 }
975
976 pub fn databaseRoot(
977 allocator: Allocator,
978 catalog: *const catalog_mod.Catalog,
979 conflicts: Hash,
980 ) Error!DatabaseRoot {
981 var names = try catalog.relationNames(allocator);
982 defer names.deinit();
983
984 const entries = try allocator.alloc(RelationEntry, names.names.len);
985 defer allocator.free(entries);
986
987 for (names.names, entries) |name, *entry| {
988 var state = try catalog.readRelation(allocator, name);
989 defer state.deinit();
990 var root = try relationRoot(
991 allocator,
992 name,
993 state.schema,
994 &state.handle,
995 state.relationStats(),
996 );
997 defer root.deinit();
998 entry.* = .{
999 .name = name,
1000 .hash = root.hash,
1001 };
1002 }
1003
1004 return try DatabaseRoot.initSorted(allocator, entries, .{ .hash = conflicts });
1005 }
1006
1007 pub fn databaseRootMaintained(
1008 allocator: Allocator,
1009 catalog: *const catalog_mod.Catalog,
1010 conflicts: Hash,
1011 ) Error!DatabaseRoot {
1012 return try databaseRootMaintainedFrom(allocator, catalog, conflicts);
1013 }
1014
1015 pub fn readDatabaseRootMaintained(
1016 allocator: Allocator,
1017 catalog: *const catalog_mod.Reader,
1018 conflicts: Hash,
1019 ) Error!DatabaseRoot {
1020 return try databaseRootMaintainedFrom(allocator, catalog, conflicts);
1021 }
1022
1023 fn databaseRootMaintainedFrom(
1024 allocator: Allocator,
1025 catalog: anytype,
1026 conflicts: Hash,
1027 ) Error!DatabaseRoot {
1028 var names = try catalog.relationNames(allocator);
1029 defer names.deinit();
1030
1031 const entries = try allocator.alloc(RelationEntry, names.names.len);
1032 defer allocator.free(entries);
1033
1034 for (names.names, entries) |name, *entry| {
1035 var state = try catalog.readRelation(allocator, name);
1036 defer state.deinit();
1037 var root = try relationRootMaintainedFrom(
1038 allocator,
1039 name,
1040 state.schema,
1041 &state.handle,
1042 state.relationStats(),
1043 );
1044 defer root.deinit();
1045 entry.* = .{
1046 .name = name,
1047 .hash = root.hash,
1048 };
1049 }
1050
1051 return try DatabaseRoot.initSorted(allocator, entries, .{ .hash = conflicts });
1052 }
1053
1054 pub fn databaseRootReplacingEntries(allocator: Allocator, base: *const DatabaseRoot, replacements: []const RelationEntry) Allocator.Error!DatabaseRoot {
1055 const entries = try allocator.alloc(RelationEntry, base.entries.len);
1056 defer allocator.free(entries);
1057 for (base.entries, entries) |entry, *target| {
1058 target.* = entry;
1059 for (replacements) |replacement| {
1060 if (std.mem.eql(u8, replacement.name, entry.name)) {
1061 target.hash = replacement.hash;
1062 break;
1063 }
1064 }
1065 }
1066 return try DatabaseRoot.initSorted(allocator, entries, .{ .hash = base.conflicts });
1067 }
1068
1069 pub fn mapRoot(allocator: Allocator, source: *const tree.Tree) Error!MapRoot {
1070 return try source.root(allocator);
1071 }
1072
1073 fn tableRootFromRows(allocator: Allocator, rows: []const RelationRow) Error!MapRoot {
1074 const keys = try allocator.alloc([key.rowid_size]u8, rows.len);
1075 defer allocator.free(keys);
1076 const entries = try allocator.alloc(tree.RootEntry, rows.len);
1077 defer allocator.free(entries);
1078
1079 for (rows, entries, 0..) |row_value, *entry, offset| {
1080 _ = try row.View.init(row_value.bytes);
1081 entry.* = .{
1082 .key = try key.encodeRowId(keys[offset][0..], row_value.rowid),
1083 .value = row_value.bytes,
1084 };
1085 }
1086 std.mem.sort(tree.RootEntry, entries, {}, rootEntryLessThan);
1087 return try tree.rootFromSortedEntries(allocator, entries);
1088 }
1089
1090 fn indexRootFromRows(allocator: Allocator, rows: []const RelationRow, fields: []const usize, columns: []const row.Column) Error!MapRoot {
1091 if (fields.len > relation_mod.max_index_fields) return error.TooManyIndexFields;
1092 var key_bytes: usize = 0;
1093 for (rows) |row_value| {
1094 const view = try row.View.init(row_value.bytes);
1095 var projected: [relation_mod.max_index_fields]row.Value = undefined;
1096 const values = try view.project(fields, projected[0..]);
1097 var buffer: [page.size]u8 = undefined;
1098 const encoded = try key.encodeIndex(&buffer, values, columns, row_value.rowid);
1099 key_bytes = std.math.add(usize, key_bytes, encoded.len) catch
1100 return error.OutputTooSmall;
1101 }
1102
1103 const keys = if (key_bytes == 0)
1104 @as([]u8, &.{})
1105 else
1106 try allocator.alloc(u8, key_bytes);
1107 defer if (keys.len != 0) allocator.free(keys);
1108 const entries = try allocator.alloc(tree.RootEntry, rows.len);
1109 defer allocator.free(entries);
1110
1111 var cursor: usize = 0;
1112 for (rows, entries) |row_value, *entry| {
1113 const view = try row.View.init(row_value.bytes);
1114 var projected: [relation_mod.max_index_fields]row.Value = undefined;
1115 const values = try view.project(fields, projected[0..]);
1116 const encoded = try key.encodeIndex(
1117 keys[cursor..],
1118 values,
1119 columns,
1120 row_value.rowid,
1121 );
1122 entry.* = .{
1123 .key = encoded,
1124 .value = "",
1125 };
1126 cursor += encoded.len;
1127 }
1128 std.debug.assert(cursor == keys.len);
1129 std.mem.sort(tree.RootEntry, entries, {}, rootEntryLessThan);
1130 return try tree.rootFromSortedEntries(allocator, entries);
1131 }
1132
1133 pub fn schemaHash(definitions: []const catalog_mod.ColumnDefinition, indexes: []const catalog_mod.IndexDefinition) Hash {
1134 var builder = Builder.init("sql.schema");
1135 builder.writeU64(definitions.len);
1136 for (definitions) |definition| {
1137 builder.bytes(definition.name);
1138 builder.writeU8(@backingInt(definition.column.collation));
1139 builder.rowValue(definition.default);
1140 }
1141 builder.writeU64(indexes.len);
1142 for (indexes) |index| {
1143 builder.bytes(index.name);
1144 builder.writeU64(index.fields.len);
1145 for (index.fields) |field| builder.writeU64(field);
1146 builder.writeU64(index.columns.len);
1147 for (index.columns) |column| builder.writeU8(@backingInt(column.collation));
1148 }
1149 return builder.finish();
1150 }
1151
1152 fn cloneColumn(allocator: Allocator, column: catalog_mod.ColumnDefinition) Allocator.Error!catalog_mod.ColumnDefinition {
1153 const name = try allocator.dupe(u8, column.name);
1154 errdefer allocator.free(name);
1155 const default = try cloneValue(allocator, column.default);
1156 errdefer deinitValue(allocator, default);
1157 return .{
1158 .name = name,
1159 .column = column.column,
1160 .default = default,
1161 };
1162 }
1163
1164 fn deinitColumn(allocator: Allocator, column: *catalog_mod.ColumnDefinition) void {
1165 allocator.free(column.name);
1166 deinitValue(allocator, column.default);
1167 column.* = undefined;
1168 }
1169
1170 fn cloneIndex(allocator: Allocator, index: catalog_mod.IndexDefinition) Allocator.Error!catalog_mod.IndexDefinition {
1171 const name = try allocator.dupe(u8, index.name);
1172 errdefer allocator.free(name);
1173 const fields = try allocator.dupe(usize, index.fields);
1174 errdefer allocator.free(fields);
1175 const columns = try allocator.dupe(row.Column, index.columns);
1176 errdefer allocator.free(columns);
1177 return .{
1178 .name = name,
1179 .fields = fields,
1180 .columns = columns,
1181 };
1182 }
1183
1184 fn deinitIndex(allocator: Allocator, index: *catalog_mod.IndexDefinition) void {
1185 allocator.free(index.name);
1186 allocator.free(index.fields);
1187 allocator.free(index.columns);
1188 index.* = undefined;
1189 }
1190
1191 fn cloneValue(allocator: Allocator, value: row.Value) Allocator.Error!row.Value {
1192 return switch (value) {
1193 .nil => .nil,
1194 .integer => |integer| .{ .integer = integer },
1195 .text => |text| .{ .text = try allocator.dupe(u8, text) },
1196 .blob => |blob| .{ .blob = try allocator.dupe(u8, blob) },
1197 };
1198 }
1199
1200 fn deinitValue(allocator: Allocator, value: row.Value) void {
1201 switch (value) {
1202 .nil, .integer => {},
1203 .text => |text| allocator.free(text),
1204 .blob => |blob| allocator.free(blob),
1205 }
1206 }
1207
1208 fn indexHash(fields: []const usize, columns: []const row.Column, map_hash: Hash, stats_hash: Hash) Hash {
1209 var builder = Builder.init("sql.index");
1210 builder.hash(fieldsHash(fields, columns));
1211 builder.hash(map_hash);
1212 builder.hash(stats_hash);
1213 return builder.finish();
1214 }
1215
1216 fn fieldsHash(fields: []const usize, columns: []const row.Column) Hash {
1217 var builder = Builder.init("sql.index.fields");
1218 builder.writeU64(fields.len);
1219 for (fields) |field| builder.writeU64(field);
1220 builder.writeU64(columns.len);
1221 for (columns) |column| builder.writeU8(@backingInt(column.collation));
1222 return builder.finish();
1223 }
1224
1225 fn relationStatsRoot(stats: ?*const catalog_mod.RelationStats) StatsRoot {
1226 const relation_stats = stats orelse return .{
1227 .hash = emptyHash("sql.stats.none"),
1228 };
1229 var builder = Builder.init("sql.stats.relation");
1230 builder.logicalSummary(relation_stats.table);
1231 builder.writeU64(relation_stats.indexes.len);
1232 for (relation_stats.indexes) |index| builder.hash(indexStatsHash(&index));
1233 return .{
1234 .table = relation_stats.table,
1235 .indexes = relation_stats.indexes.len,
1236 .hash = builder.finish(),
1237 };
1238 }
1239
1240 fn logicalSummaryEqual(left: tree.Summary, right: tree.Summary) bool {
1241 return left.entries == right.entries and
1242 left.key_bytes == right.key_bytes and
1243 left.value_bytes == right.value_bytes;
1244 }
1245
1246 fn findIndexStats(stats: ?*const catalog_mod.RelationStats, root_page: u32) ?*const catalog_mod.IndexStats {
1247 const relation_stats = stats orelse return null;
1248 for (relation_stats.indexes) |*index_stats| {
1249 if (index_stats.root_page == root_page) return index_stats;
1250 }
1251 return null;
1252 }
1253
1254 fn indexStatsHash(stats: ?*const catalog_mod.IndexStats) Hash {
1255 const index_stats = stats orelse return emptyHash("sql.stats.index.none");
1256 var builder = Builder.init("sql.stats.index");
1257 builder.bytes(index_stats.name);
1258 builder.logicalSummary(index_stats.summary);
1259 builder.distribution(index_stats.distribution);
1260 return builder.finish();
1261 }
1262
1263 fn relationEntryLessThan(_: void, left: RelationEntry, right: RelationEntry) bool {
1264 return simd.order(Bytes, left.name, right.name) == .lt;
1265 }
1266
1267 fn rootEntryLessThan(_: void, left: tree.RootEntry, right: tree.RootEntry) bool {
1268 return simd.order(Bytes, left.key, right.key) == .lt;
1269 }
1270
1271 pub fn relationRowLessThan(_: void, left: RelationRow, right: RelationRow) bool {
1272 return left.rowid < right.rowid;
1273 }
1274
1275 fn relationRowsApplyingEdits(allocator: Allocator, source: []const RelationRow, edits: []const relation_mod.Edit) Error![]RelationRow {
1276 var rows: std.ArrayList(RelationRow) = .empty;
1277 errdefer {
1278 for (rows.items) |row_value| allocator.free(row_value.bytes);
1279 rows.deinit(allocator);
1280 }
1281 for (source) |row_value| {
1282 const bytes = try allocator.dupe(u8, row_value.bytes);
1283 errdefer allocator.free(bytes);
1284 try rows.append(allocator, .{
1285 .rowid = row_value.rowid,
1286 .bytes = bytes,
1287 });
1288 }
1289 for (edits) |edit| try applyRelationRowEdit(allocator, &rows, edit);
1290 return try rows.toOwnedSlice(allocator);
1291 }
1292
1293 fn applyRelationRowEdit(allocator: Allocator, rows: *std.ArrayList(RelationRow), edit: relation_mod.Edit) Error!void {
1294 switch (edit) {
1295 .put => |put_edit| {
1296 _ = try row.View.init(put_edit.bytes);
1297 const bytes = try allocator.dupe(u8, put_edit.bytes);
1298 errdefer allocator.free(bytes);
1299 const target = relationRowPosition(rows.items, put_edit.rowid);
1300 if (target.found) {
1301 allocator.free(rows.items[target.index].bytes);
1302 rows.items[target.index].bytes = bytes;
1303 } else {
1304 try rows.insert(allocator, target.index, .{
1305 .rowid = put_edit.rowid,
1306 .bytes = bytes,
1307 });
1308 }
1309 },
1310 .update => |update_edit| {
1311 const target = relationRowPosition(rows.items, update_edit.rowid);
1312 if (!target.found) return error.KeyNotFound;
1313 const merged = try relation_mod.applyUpdate(allocator, rows.items[target.index].bytes, update_edit.assignments);
1314 allocator.free(rows.items[target.index].bytes);
1315 rows.items[target.index].bytes = merged;
1316 },
1317 .delete => |rowid| {
1318 const target = relationRowPosition(rows.items, rowid);
1319 if (!target.found) return error.KeyNotFound;
1320 const removed = rows.orderedRemove(target.index);
1321 allocator.free(removed.bytes);
1322 },
1323 }
1324 }
1325
1326 const RelationRowPosition = struct {
1327 index: usize,
1328 found: bool,
1329 };
1330
1331 fn relationRowPosition(rows: []const RelationRow, rowid: i64) RelationRowPosition {
1332 var low: usize = 0;
1333 var high: usize = rows.len;
1334 while (low < high) {
1335 const mid = low + (high - low) / 2;
1336 if (rows[mid].rowid < rowid) {
1337 low = mid + 1;
1338 } else {
1339 high = mid;
1340 }
1341 }
1342 return .{
1343 .index = low,
1344 .found = low < rows.len and rows[low].rowid == rowid,
1345 };
1346 }
1347
1348 const Builder = struct {
1349 hasher: std.crypto.hash.sha2.Sha256,
1350
1351 fn init(tag: []const u8) Builder {
1352 var builder = Builder{ .hasher = std.crypto.hash.sha2.Sha256.init(.{}) };
1353 builder.bytes(tag);
1354 return builder;
1355 }
1356
1357 fn finish(self: *Builder) Hash {
1358 var digest: Hash = undefined;
1359 self.hasher.final(&digest);
1360 return digest;
1361 }
1362
1363 fn hash(self: *Builder, value: Hash) void {
1364 self.hasher.update(value[0..]);
1365 }
1366
1367 fn bytes(self: *Builder, value: []const u8) void {
1368 self.writeU64(value.len);
1369 self.hasher.update(value);
1370 }
1371
1372 fn optionalBytes(self: *Builder, value: ?[]const u8) void {
1373 if (value) |bytes_value| {
1374 self.writeU8(1);
1375 self.bytes(bytes_value);
1376 } else {
1377 self.writeU8(0);
1378 }
1379 }
1380
1381 fn optionalConflictValue(self: *Builder, kind: ConflictKind, value: ?ConflictValue) void {
1382 if (value) |conflict_value| {
1383 self.writeU8(1);
1384 switch (conflict_value) {
1385 .row => |bytes_value| {
1386 std.debug.assert(kind == .row);
1387 self.bytes(bytes_value);
1388 },
1389 .relation => |hash_value| {
1390 std.debug.assert(kind == .relation);
1391 self.hash(hash_value);
1392 },
1393 }
1394 } else {
1395 self.writeU8(0);
1396 }
1397 }
1398
1399 fn rowValue(self: *Builder, row_value: row.Value) void {
1400 self.writeU8(@backingInt(std.meta.activeTag(row_value)));
1401 switch (row_value) {
1402 .nil => {},
1403 .integer => |integer| self.writeI64(integer),
1404 .text => |text| self.bytes(text),
1405 .blob => |blob| self.bytes(blob),
1406 }
1407 }
1408
1409 fn distribution(self: *Builder, value: catalog_mod.IndexDistribution) void {
1410 self.writeU64(value.distinct_values);
1411 self.writeU64(value.max_equal);
1412 self.writeU64(value.samples.len);
1413 for (value.samples) |entry_sample| self.sample(entry_sample);
1414 self.bytes(value.sample_keys);
1415 self.writeU64(value.prefixes.len);
1416 for (value.prefixes) |prefix| {
1417 self.writeU64(prefix.field_count);
1418 self.writeU64(prefix.distinct_values);
1419 self.writeU64(prefix.max_equal);
1420 self.writeU64(prefix.samples.len);
1421 for (prefix.samples) |entry_sample| self.sample(entry_sample);
1422 self.bytes(prefix.sample_keys);
1423 }
1424 }
1425
1426 fn sample(self: *Builder, value: catalog_mod.IndexSample) void {
1427 self.bytes(value.key);
1428 self.writeU64(value.less_than);
1429 self.writeU64(value.equal_count);
1430 self.writeU64(value.less_distinct);
1431 }
1432
1433 fn logicalSummary(self: *Builder, value: tree.Summary) void {
1434 self.writeU64(value.entries);
1435 self.writeU64(value.key_bytes);
1436 self.writeU64(value.value_bytes);
1437 }
1438
1439 fn writeU8(self: *Builder, value: u8) void {
1440 self.hasher.update(&.{value});
1441 }
1442
1443 fn writeU32(self: *Builder, value: u32) void {
1444 var encoded: [4]u8 = undefined;
1445 std.mem.writeInt(u32, encoded[0..], value, .big);
1446 self.hasher.update(&encoded);
1447 }
1448
1449 fn writeU64(self: *Builder, value: anytype) void {
1450 var encoded: [8]u8 = undefined;
1451 std.mem.writeInt(u64, encoded[0..], @intCast(value), .big);
1452 self.hasher.update(&encoded);
1453 }
1454
1455 fn writeI64(self: *Builder, value: i64) void {
1456 var encoded: [8]u8 = undefined;
1457 std.mem.writeInt(i64, encoded[0..], value, .big);
1458 self.hasher.update(&encoded);
1459 }
1460 };
1461
1462 test "database root hash depends on relation root hashes and names" {
1463 const empty = emptyHash("empty");
1464 var changed = empty;
1465 changed[0] +%= 1;
1466
1467 const conflicts = ConflictRoot.empty();
1468 const left = DatabaseRoot.init(&.{
1469 .{ .name = "items", .hash = empty },
1470 }, conflicts);
1471 const same_left = DatabaseRoot.init(&.{
1472 .{ .name = "items", .hash = empty },
1473 }, conflicts);
1474 const renamed = DatabaseRoot.init(&.{
1475 .{ .name = "users", .hash = empty },
1476 }, conflicts);
1477 const modified = DatabaseRoot.init(&.{
1478 .{ .name = "items", .hash = changed },
1479 }, conflicts);
1480
1481 try std.testing.expect(same(left.hash, same_left.hash));
1482 try std.testing.expect(!same(left.hash, renamed.hash));
1483 try std.testing.expect(!same(left.hash, modified.hash));
1484 }
1485
1486 test "database root sorted hash is independent of relation entry order" {
1487 const items = emptyHash("items");
1488 const users = emptyHash("users");
1489 const conflicts = ConflictRoot.empty();
1490 var first = try DatabaseRoot.initSorted(std.testing.allocator, &.{
1491 .{ .name = "items", .hash = items },
1492 .{ .name = "users", .hash = users },
1493 }, conflicts);
1494 defer first.deinit();
1495 var second = try DatabaseRoot.initSorted(std.testing.allocator, &.{
1496 .{ .name = "users", .hash = users },
1497 .{ .name = "items", .hash = items },
1498 }, conflicts);
1499 defer second.deinit();
1500
1501 try std.testing.expect(same(first.hash, second.hash));
1502 try std.testing.expectEqualStrings("items", first.entries[0].name);
1503 try std.testing.expectEqualStrings("users", first.entries[1].name);
1504 }
1505
1506 test "database root hash depends on conflict root" {
1507 const relation = emptyHash("relation");
1508 const artifact = ConflictArtifact.init("items", 7, "base", "ours", "theirs");
1509 const conflicts = ConflictRoot.init(&.{artifact.entry()});
1510 const clean = DatabaseRoot.init(&.{.{ .name = "items", .hash = relation }}, ConflictRoot.empty());
1511 const conflicted = DatabaseRoot.init(&.{.{ .name = "items", .hash = relation }}, conflicts);
1512
1513 try std.testing.expect(!same(clean.hash, conflicted.hash));
1514 try std.testing.expect(same(conflicts.hash, conflicted.conflicts));
1515 }
1516
1517 test "conflict artifact hash distinguishes row and relation values" {
1518 const ours = emptyHash("conflict.ours");
1519 const theirs = emptyHash("conflict.theirs");
1520 const row_artifact = ConflictArtifact.init("items", 0, null, "ours", "theirs");
1521 const relation_artifact = ConflictArtifact.initRelation("items", null, ours, theirs);
1522
1523 try std.testing.expectEqual(ConflictKind.row, row_artifact.kind);
1524 try std.testing.expectEqual(ConflictKind.relation, relation_artifact.kind);
1525 try std.testing.expect(!same(row_artifact.hash, relation_artifact.hash));
1526 try std.testing.expect(same(ours, relation_artifact.ours.?.relation));
1527 try std.testing.expect(same(theirs, relation_artifact.theirs.?.relation));
1528 const conflicts = ConflictRoot.init(&.{relation_artifact.entry()});
1529 try std.testing.expectEqual(@as(usize, 1), conflicts.count);
1530 }
1531
1532 test "schema hash includes index descriptor names" {
1533 const columns = [_]catalog_mod.ColumnDefinition{.{ .name = "value" }};
1534 const fields = [_]usize{0};
1535 const index_columns = [_]row.Column{.{}};
1536 const first = [_]catalog_mod.IndexDefinition{.{
1537 .name = "items_value",
1538 .fields = fields[0..],
1539 .columns = index_columns[0..],
1540 }};
1541 const second = [_]catalog_mod.IndexDefinition{.{
1542 .name = "items_value_alt",
1543 .fields = fields[0..],
1544 .columns = index_columns[0..],
1545 }};
1546
1547 try std.testing.expect(!same(schemaHash(columns[0..], first[0..]), schemaHash(columns[0..], second[0..])));
1548 }
1549
1550 test "conflict root sorted hash is independent of artifact order" {
1551 const first = ConflictArtifact.init("items", 1, "base", "ours", "theirs");
1552 const second = ConflictArtifact.init("users", 2, null, "ours", "theirs");
1553 const left = try ConflictRoot.initSorted(std.testing.allocator, &.{ first.entry(), second.entry() });
1554 const right = try ConflictRoot.initSorted(std.testing.allocator, &.{ second.entry(), first.entry() });
1555
1556 try std.testing.expect(same(left.hash, right.hash));
1557 try std.testing.expectEqual(@as(usize, 2), left.count);
1558 }
1559
1560 test "relation stats hash ignores physical table shape" {
1561 var no_indexes = [_]catalog_mod.IndexStats{};
1562 const left = catalog_mod.RelationStats{
1563 .allocator = std.testing.allocator,
1564 .table_root_page = 17,
1565 .table = .{
1566 .branch_pages = 1,
1567 .leaf_pages = 2,
1568 .overflow_pages = 3,
1569 .entries = 11,
1570 .inline_records = 9,
1571 .overflow_records = 2,
1572 .max_depth = 2,
1573 .key_bytes = 44,
1574 .record_bytes = 99,
1575 .value_bytes = 180,
1576 },
1577 .indexes = no_indexes[0..],
1578 };
1579 const same_logical = catalog_mod.RelationStats{
1580 .allocator = std.testing.allocator,
1581 .table_root_page = 91,
1582 .table = .{
1583 .branch_pages = 8,
1584 .leaf_pages = 13,
1585 .overflow_pages = 21,
1586 .entries = 11,
1587 .inline_records = 4,
1588 .overflow_records = 7,
1589 .max_depth = 5,
1590 .key_bytes = 44,
1591 .record_bytes = 24,
1592 .value_bytes = 180,
1593 },
1594 .indexes = no_indexes[0..],
1595 };
1596 const different_logical = catalog_mod.RelationStats{
1597 .allocator = std.testing.allocator,
1598 .table_root_page = 91,
1599 .table = .{
1600 .branch_pages = 8,
1601 .leaf_pages = 13,
1602 .overflow_pages = 21,
1603 .entries = 12,
1604 .inline_records = 4,
1605 .overflow_records = 7,
1606 .max_depth = 5,
1607 .key_bytes = 44,
1608 .record_bytes = 24,
1609 .value_bytes = 180,
1610 },
1611 .indexes = no_indexes[0..],
1612 };
1613
1614 const first = relationStatsRoot(&left);
1615 const second = relationStatsRoot(&same_logical);
1616 const changed = relationStatsRoot(&different_logical);
1617 try std.testing.expect(same(first.hash, second.hash));
1618 try std.testing.expect(!same(first.hash, changed.hash));
1619 }
1620
1621 test "index stats hash ignores physical root and shape" {
1622 var left_name = [_]u8{ 'b', 'y', '_', 'v', 'a', 'l', 'u', 'e' };
1623 var right_name = [_]u8{ 'b', 'y', '_', 'v', 'a', 'l', 'u', 'e' };
1624 var changed_name = [_]u8{ 'b', 'y', '_', 'v', 'a', 'l', 'u', 'e' };
1625 const left = catalog_mod.IndexStats{
1626 .name = left_name[0..],
1627 .root_page = 19,
1628 .summary = .{
1629 .branch_pages = 1,
1630 .leaf_pages = 3,
1631 .overflow_pages = 5,
1632 .entries = 7,
1633 .inline_records = 6,
1634 .overflow_records = 1,
1635 .max_depth = 2,
1636 .key_bytes = 33,
1637 .record_bytes = 120,
1638 .value_bytes = 88,
1639 },
1640 .distribution = .{
1641 .distinct_values = 6,
1642 .max_equal = 2,
1643 },
1644 };
1645 const same_logical = catalog_mod.IndexStats{
1646 .name = right_name[0..],
1647 .root_page = 71,
1648 .summary = .{
1649 .branch_pages = 11,
1650 .leaf_pages = 13,
1651 .overflow_pages = 17,
1652 .entries = 7,
1653 .inline_records = 2,
1654 .overflow_records = 5,
1655 .max_depth = 4,
1656 .key_bytes = 33,
1657 .record_bytes = 60,
1658 .value_bytes = 88,
1659 },
1660 .distribution = .{
1661 .distinct_values = 6,
1662 .max_equal = 2,
1663 },
1664 };
1665 const different_distribution = catalog_mod.IndexStats{
1666 .name = changed_name[0..],
1667 .root_page = 71,
1668 .summary = .{
1669 .branch_pages = 11,
1670 .leaf_pages = 13,
1671 .overflow_pages = 17,
1672 .entries = 7,
1673 .inline_records = 2,
1674 .overflow_records = 5,
1675 .max_depth = 4,
1676 .key_bytes = 33,
1677 .record_bytes = 60,
1678 .value_bytes = 88,
1679 },
1680 .distribution = .{
1681 .distinct_values = 7,
1682 .max_equal = 2,
1683 },
1684 };
1685
1686 try std.testing.expect(same(indexStatsHash(&left), indexStatsHash(&same_logical)));
1687 try std.testing.expect(!same(indexStatsHash(&left), indexStatsHash(&different_distribution)));
1688 }
1689
1690 test "commit hash depends on root and parents" {
1691 const root = emptyHash("root");
1692 const parent = emptyHash("parent");
1693 const other_parent = emptyHash("other-parent");
1694 const first = Commit.init(root, &.{parent});
1695 const second = Commit.init(root, &.{parent});
1696 const other = Commit.init(root, &.{other_parent});
1697
1698 try std.testing.expect(same(first.hash, second.hash));
1699 try std.testing.expect(!same(first.hash, other.hash));
1700 }
1701
1702 test "working set tracks explicit base working and staged roots" {
1703 const base = emptyHash("base");
1704 const working = emptyHash("working");
1705 const next = emptyHash("next");
1706
1707 const clean = WorkingSet.init(base);
1708 try std.testing.expect(same(clean.base, base));
1709 try std.testing.expect(!clean.dirty());
1710 try std.testing.expect(!clean.hasStaged());
1711
1712 const changed = clean.withWorking(working);
1713 try std.testing.expect(changed.dirty());
1714 try std.testing.expect(!changed.hasStaged());
1715
1716 const staged = changed.stage();
1717 try std.testing.expect(staged.dirty());
1718 try std.testing.expect(staged.hasStaged());
1719 try std.testing.expect(same(staged.staged, working));
1720
1721 const advanced = staged.advance(next);
1722 try std.testing.expect(!advanced.dirty());
1723 try std.testing.expect(!advanced.hasStaged());
1724 try std.testing.expect(same(advanced.base, next));
1725 }
1726
1727 test "relation root ignores unrelated catalog schema version bumps" {
1728 var tmp = std.testing.tmpDir(.{});
1729 defer tmp.cleanup();
1730
1731 var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{
1732 .paths = .{ .database = "version-schema.db", .wal = "version-schema.wal" },
1733 .header = testingHeader(),
1734 });
1735 defer database.deinit();
1736 try database.reserve(.{ .wal_frames = 256 });
1737
1738 var catalog = try catalog_mod.Catalog.open(&database, .{});
1739 const first = try catalog.createRelation(std.testing.allocator, .{
1740 .name = "items",
1741 .columns = &.{.{ .name = "value" }},
1742 }, .{ .durability = .buffered });
1743
1744 var handle = try catalog.openRelation(std.testing.allocator, "items");
1745 defer handle.deinit();
1746 _ = try handle.relation.put(std.testing.allocator, 1, &.{.{ .text = "one" }}, .{ .durability = .buffered });
1747 var before = try relationRoot(std.testing.allocator, "items", first.schema, &handle, null);
1748 defer before.deinit();
1749
1750 const second = try catalog.createRelation(std.testing.allocator, .{
1751 .name = "users",
1752 }, .{ .durability = .buffered });
1753 try std.testing.expect(second.schema.version > first.schema.version);
1754
1755 var after = try relationRoot(std.testing.allocator, "items", second.schema, &handle, null);
1756 defer after.deinit();
1757 try std.testing.expect(same(before.hash, after.hash));
1758 }
1759
1760 test "database root from catalog tracks all relation roots" {
1761 var tmp = std.testing.tmpDir(.{});
1762 defer tmp.cleanup();
1763
1764 var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{
1765 .paths = .{ .database = "database-root.db", .wal = "database-root.wal" },
1766 .header = testingHeader(),
1767 });
1768 defer database.deinit();
1769 try database.reserve(.{ .wal_frames = 512 });
1770
1771 var catalog = try catalog_mod.Catalog.open(&database, .{});
1772 _ = try catalog.createRelation(std.testing.allocator, .{
1773 .name = "items",
1774 .columns = &.{.{ .name = "value" }},
1775 }, .{ .durability = .buffered });
1776 _ = try catalog.createRelation(std.testing.allocator, .{
1777 .name = "users",
1778 .columns = &.{.{ .name = "name" }},
1779 }, .{ .durability = .buffered });
1780
1781 var before = try databaseRoot(
1782 std.testing.allocator,
1783 &catalog,
1784 ConflictRoot.empty().hash,
1785 );
1786 defer before.deinit();
1787 var users = try catalog.openRelation(std.testing.allocator, "users");
1788 defer users.deinit();
1789 _ = try users.relation.put(std.testing.allocator, 1, &.{.{ .text = "ada" }}, .{ .durability = .buffered });
1790 var after = try databaseRoot(
1791 std.testing.allocator,
1792 &catalog,
1793 ConflictRoot.empty().hash,
1794 );
1795 defer after.deinit();
1796
1797 try std.testing.expect(!same(before.hash, after.hash));
1798 try std.testing.expectEqual(@as(usize, 2), after.entries.len);
1799 try std.testing.expectEqualStrings("items", after.entries[0].name);
1800 try std.testing.expectEqualStrings("users", after.entries[1].name);
1801 }
1802
1803 test "database value accepts replacement relation values" {
1804 var tmp = std.testing.tmpDir(.{});
1805 defer tmp.cleanup();
1806
1807 var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{
1808 .paths = .{ .database = "database-value-replacement.db", .wal = "database-value-replacement.wal" },
1809 .header = testingHeader(),
1810 });
1811 defer database.deinit();
1812 try database.reserve(.{ .wal_frames = 512 });
1813
1814 var catalog = try catalog_mod.Catalog.open(&database, .{});
1815 _ = try catalog.createRelation(std.testing.allocator, .{
1816 .name = "items",
1817 .columns = &.{.{ .name = "value" }},
1818 }, .{ .durability = .buffered });
1819 _ = try catalog.createRelation(std.testing.allocator, .{
1820 .name = "users",
1821 .columns = &.{.{ .name = "name" }},
1822 }, .{ .durability = .buffered });
1823
1824 var live = try databaseValue(
1825 std.testing.allocator,
1826 &catalog,
1827 ConflictRoot.empty().hash,
1828 );
1829 defer live.deinit();
1830 var replacement = try live.relations[0].clone(std.testing.allocator);
1831 defer replacement.deinit(std.testing.allocator);
1832 replacement.root.hash = emptyHash("sql.test.replacement");
1833
1834 var replaced = try databaseValueReplacingRelations(
1835 std.testing.allocator,
1836 &catalog,
1837 &.{replacement},
1838 ConflictRoot.empty().hash,
1839 );
1840 defer replaced.deinit();
1841 try std.testing.expect(same(replaced.relations[0].root.hash, replacement.root.hash));
1842 try std.testing.expect(same(replaced.root.entries[0].hash, replacement.root.hash));
1843 try std.testing.expect(same(replaced.relations[1].root.hash, live.relations[1].root.hash));
1844 }
1845
1846 test "relation value applies row edits from an immutable base" {
1847 var tmp = std.testing.tmpDir(.{});
1848 defer tmp.cleanup();
1849
1850 var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{
1851 .paths = .{ .database = "relation-value-edits.db", .wal = "relation-value-edits.wal" },
1852 .header = testingHeader(),
1853 });
1854 defer database.deinit();
1855 try database.reserve(.{ .wal_frames = 512 });
1856
1857 var catalog = try catalog_mod.Catalog.open(&database, .{});
1858 _ = try catalog.createRelation(std.testing.allocator, .{
1859 .name = "items",
1860 .columns = &.{.{ .name = "value" }},
1861 }, .{ .durability = .buffered });
1862
1863 var handle = try catalog.openRelation(std.testing.allocator, "items");
1864 defer handle.deinit();
1865 _ = try handle.relation.put(std.testing.allocator, 1, &.{.{ .text = "one" }}, .{ .durability = .buffered });
1866 _ = try handle.relation.put(std.testing.allocator, 3, &.{.{ .text = "three" }}, .{ .durability = .buffered });
1867
1868 var base = try databaseValue(
1869 std.testing.allocator,
1870 &catalog,
1871 ConflictRoot.empty().hash,
1872 );
1873 defer base.deinit();
1874 const base_items = base.findRelation("items").?;
1875
1876 var two_buffer: [128]u8 = undefined;
1877 const two = try row.encode(&two_buffer, &.{.{ .text = "two" }});
1878 var updated_buffer: [128]u8 = undefined;
1879 const updated = try row.encode(&updated_buffer, &.{.{ .text = "updated" }});
1880 var applied = try relationValueApplyingMaterializedEdits(std.testing.allocator, base_items, &.{
1881 .{ .put = .{ .rowid = 2, .bytes = two } },
1882 .{ .put = .{ .rowid = 3, .bytes = updated } },
1883 .{ .update = .{ .rowid = 2, .assignments = &.{.{ .column = 0, .value = .{ .text = "two-edited" } }} } },
1884 .{ .delete = 1 },
1885 });
1886 defer applied.deinit(std.testing.allocator);
1887
1888 try std.testing.expectEqual(@as(usize, 2), applied.rows.len);
1889 try std.testing.expectEqual(@as(i64, 2), applied.rows[0].rowid);
1890 try std.testing.expectEqual(@as(i64, 3), applied.rows[1].rowid);
1891 const inserted = try row.View.init(applied.rows[0].bytes);
1892 const replaced = try row.View.init(applied.rows[1].bytes);
1893 try std.testing.expectEqualStrings("two-edited", (try inserted.column(0)).text);
1894 try std.testing.expectEqualStrings("updated", (try replaced.column(0)).text);
1895 try std.testing.expectError(error.KeyNotFound, relationValueApplyingMaterializedEdits(std.testing.allocator, base_items, &.{.{ .delete = 99 }}));
1896 try std.testing.expectError(error.KeyNotFound, relationValueApplyingMaterializedEdits(std.testing.allocator, base_items, &.{.{ .update = .{ .rowid = 99, .assignments = &.{.{ .column = 0, .value = .nil }} } }}));
1897 }
1898
1899 test "relation root from materialized rows matches live logical maps" {
1900 var tmp = std.testing.tmpDir(.{});
1901 defer tmp.cleanup();
1902
1903 var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{
1904 .paths = .{ .database = "relation-root-rows.db", .wal = "relation-root-rows.wal" },
1905 .header = testingHeader(),
1906 });
1907 defer database.deinit();
1908 try database.reserve(.{ .wal_frames = 512 });
1909
1910 var catalog = try catalog_mod.Catalog.open(&database, .{});
1911 _ = try catalog.createRelation(std.testing.allocator, .{
1912 .name = "items",
1913 .columns = &.{
1914 .{ .name = "name" },
1915 .{ .name = "score" },
1916 },
1917 .indexes = &.{.{
1918 .name = "items_score",
1919 .fields = &.{1},
1920 .columns = &.{.{}},
1921 }},
1922 }, .{ .durability = .buffered });
1923
1924 var handle = try catalog.openRelation(std.testing.allocator, "items");
1925 defer handle.deinit();
1926 _ = try handle.relation.put(std.testing.allocator, 3, &.{ .{ .text = "Ada" }, .{ .integer = 7 } }, .{ .durability = .buffered });
1927 _ = try handle.relation.put(std.testing.allocator, 1, &.{ .{ .text = "Bea" }, .{ .integer = 4 } }, .{ .durability = .buffered });
1928
1929 const schema = try catalog.schemaState(std.testing.allocator);
1930 var live_root = try relationRoot(std.testing.allocator, "items", schema, &handle, null);
1931 defer live_root.deinit();
1932 const rows = try relationRows(std.testing.allocator, &handle);
1933 defer freeRelationRows(std.testing.allocator, rows);
1934 var materialized_root = try relationRootFromRows(std.testing.allocator, &live_root, rows);
1935 defer materialized_root.deinit();
1936
1937 try std.testing.expect(same(live_root.hash, materialized_root.hash));
1938 try std.testing.expect(same(live_root.table.hash, materialized_root.table.hash));
1939 try std.testing.expectEqual(@as(usize, 1), materialized_root.indexes.len);
1940 try std.testing.expect(same(live_root.indexes[0].map.hash, materialized_root.indexes[0].map.hash));
1941 }
1942
1943 test "index root from rows retains exact encoded key storage" {
1944 const row_count = 512;
1945 var row_buffer: [64]u8 = undefined;
1946 const encoded = try row.encode(&row_buffer, &.{.{ .text = "compact" }});
1947 var rows: [row_count]RelationRow = undefined;
1948 for (&rows, 0..) |*row_value, index| {
1949 row_value.* = .{
1950 .rowid = @intCast(index + 1),
1951 .bytes = @constCast(encoded),
1952 };
1953 }
1954
1955 var storage: [256 * 1024]u8 = undefined;
1956 var fixed = std.heap.FixedBufferAllocator.init(&storage);
1957 var root = try indexRootFromRows(
1958 fixed.allocator(),
1959 &rows,
1960 &.{0},
1961 &.{.{}},
1962 );
1963 defer root.deinit();
1964 try std.testing.expectEqual(@as(usize, row_count), root.summary.entries);
1965 try std.testing.expect(fixed.end_index < storage.len);
1966 }
1967
1968 test "relation root hash is stable across reopen and changes after row write" {
1969 var tmp = std.testing.tmpDir(.{});
1970 defer tmp.cleanup();
1971
1972 {
1973 var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{
1974 .paths = .{ .database = "version.db", .wal = "version.wal" },
1975 .header = testingHeader(),
1976 });
1977 defer database.deinit();
1978 try database.reserve(.{ .wal_frames = 256 });
1979
1980 var catalog = try catalog_mod.Catalog.open(&database, .{});
1981 _ = try catalog.createRelation(std.testing.allocator, .{
1982 .name = "items",
1983 .columns = &.{.{ .name = "value" }},
1984 }, .{ .durability = .buffered });
1985
1986 var handle = try catalog.openRelation(std.testing.allocator, "items");
1987 defer handle.deinit();
1988 _ = try handle.relation.put(std.testing.allocator, 1, &.{.{ .text = "one" }}, .{ .durability = .buffered });
1989 const schema = try catalog.schemaState(std.testing.allocator);
1990 var stats = try catalog.relationStats(std.testing.allocator, "items");
1991 defer if (stats) |*s| s.deinit();
1992 var root = try relationRoot(std.testing.allocator, "items", schema, &handle, if (stats) |*s| s else null);
1993 defer root.deinit();
1994 try std.testing.expect(root.table.summary.entries == 1);
1995 try std.testing.expectEqual(@as(usize, 1), root.schema_descriptor.columns.len);
1996 try std.testing.expectEqualStrings("value", root.schema_descriptor.columns[0].name);
1997 try std.testing.expectEqual(@as(usize, 0), root.schema_descriptor.indexes.len);
1998 try database.syncWal();
1999 }
2000
2001 var reopened = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{
2002 .paths = .{ .database = "version.db", .wal = "version.wal" },
2003 .header = recoveredHeader(),
2004 });
2005 defer reopened.deinit();
2006 try reopened.reserve(.{ .wal_frames = 256 });
2007
2008 var catalog = try catalog_mod.Catalog.open(&reopened, .{});
2009 var handle = try catalog.openRelation(std.testing.allocator, "items");
2010 defer handle.deinit();
2011 const schema = try catalog.schemaState(std.testing.allocator);
2012 var stats = try catalog.relationStats(std.testing.allocator, "items");
2013 defer if (stats) |*s| s.deinit();
2014 var before = try relationRoot(std.testing.allocator, "items", schema, &handle, if (stats) |*s| s else null);
2015 defer before.deinit();
2016 var again = try relationRoot(std.testing.allocator, "items", schema, &handle, if (stats) |*s| s else null);
2017 defer again.deinit();
2018 try std.testing.expect(same(before.hash, again.hash));
2019
2020 _ = try handle.relation.put(std.testing.allocator, 2, &.{.{ .text = "two" }}, .{ .durability = .buffered });
2021 var after = try relationRoot(std.testing.allocator, "items", schema, &handle, if (stats) |*s| s else null);
2022 defer after.deinit();
2023 try std.testing.expect(!same(before.hash, after.hash));
2024 }
2025
2026 fn testingHeader() wal.Header {
2027 return .{
2028 .sequence = 1801,
2029 .salt = .{ .first = 0xabcd_0101, .second = 0xdcba_0202 },
2030 };
2031 }
2032
2033 fn recoveredHeader() wal.Header {
2034 return .{
2035 .sequence = 1802,
2036 .salt = .{ .first = 0x0101_abcd, .second = 0x0202_dcba },
2037 };
2038 }
2039
2040 test "relation key matches the maintained root identity across the fixture matrix" {
2041 const testing = std.testing;
2042 var tmp = testing.tmpDir(.{});
2043 defer tmp.cleanup();
2044
2045 var database = try @import("file.zig").Database.openForTesting(testing.allocator, tmp.dir, .{
2046 .paths = .{ .database = "key.db", .wal = "key.wal" },
2047 .header = .{
2048 .sequence = 3101,
2049 .salt = .{ .first = 0x1a2b_0101, .second = 0x2b1a_0202 },
2050 },
2051 });
2052 defer database.deinit();
2053 try database.reserve(.{ .wal_frames = 512 });
2054
2055 var catalog = try catalog_mod.Catalog.open(&database, .{});
2056 _ = try catalog.createRelation(testing.allocator, .{
2057 .name = "bare",
2058 .columns = &.{},
2059 }, .{ .durability = .buffered });
2060 _ = try catalog.createRelation(testing.allocator, .{
2061 .name = "items",
2062 .columns = &.{ .{ .name = "value" }, .{ .name = "grade" } },
2063 }, .{ .durability = .buffered });
2064
2065 try expectKeyMatchesRoot(&catalog, "bare");
2066 try expectKeyMatchesRoot(&catalog, "items");
2067
2068 var relation = try catalog.openRelation(testing.allocator, "items");
2069 _ = try relation.relation.put(testing.allocator, 1, &.{ .{ .text = "one" }, .{ .integer = 7 } }, .{ .durability = .buffered });
2070 _ = try relation.relation.put(testing.allocator, 2, &.{ .{ .text = "two" }, .{ .integer = 9 } }, .{ .durability = .buffered });
2071 relation.deinit();
2072 try expectKeyMatchesRoot(&catalog, "items");
2073
2074 _ = try catalog.createIndex(testing.allocator, "items", .{
2075 .name = "items_by_grade",
2076 .fields = &.{1},
2077 }, .{ .durability = .buffered });
2078 try expectKeyMatchesRoot(&catalog, "items");
2079
2080 _ = try catalog.analyzeRelation(testing.allocator, "items", .{ .durability = .buffered });
2081 try expectKeyMatchesRoot(&catalog, "items");
2082 try expectKeyMatchesRoot(&catalog, "bare");
2083 }
2084
2085 fn expectKeyMatchesRoot(catalog: *const catalog_mod.Catalog, name: []const u8) !void {
2086 const testing = std.testing;
2087 const schema = try catalog.schemaState(testing.allocator);
2088 var handle = try catalog.openRelation(testing.allocator, name);
2089 defer handle.deinit();
2090 var stats = try catalog.relationStats(testing.allocator, name);
2091 defer if (stats) |*relation_stats| relation_stats.deinit();
2092 const stats_pointer: ?*const catalog_mod.RelationStats =
2093 if (stats) |*relation_stats| relation_stats else null;
2094
2095 const derived = try relationKey(name, &handle, stats_pointer);
2096
2097 var root = try relationRootMaintained(testing.allocator, name, schema, &handle, stats_pointer);
2098 defer root.deinit();
2099
2100 try testing.expect(same(derived.schema, root.schema));
2101 try testing.expect(same(derived.table, root.table.hash));
2102 try testing.expect(same(derived.stats, root.stats.hash));
2103 try testing.expect(same(derived.hash, root.hash));
2104
2105 var lease = try catalog.database.beginRead();
2106 defer lease.deinit();
2107 const reader = try catalog_mod.Reader.open(lease.snapshot(), .{
2108 .meta_page = catalog.meta_page,
2109 .root_page = catalog.root_page,
2110 });
2111 var read_handle = try reader.openRelation(testing.allocator, name);
2112 defer read_handle.deinit();
2113 var read_root = try readRelationRootMaintained(
2114 testing.allocator,
2115 name,
2116 schema,
2117 &read_handle,
2118 stats_pointer,
2119 );
2120 defer read_root.deinit();
2121 try testing.expect(same(root.hash, read_root.hash));
2122 }