lib/sql/src/history/materialize.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const sql = @import("../root.zig");
3 const record_mod = @import("record.zig");
4 const store_mod = @import("store.zig");
5 const row = sql.row;
6 const tree = sql.tree;
7 const version = sql.version;
8
9 const Allocator = std.mem.Allocator;
10 const Error = store_mod.Error;
11 const History = store_mod.History;
12
13 pub fn readRelationRootShallow(allocator: Allocator, reader: *record_mod.PayloadReader) Error!store_mod.ShallowRelationRoot {
14 const format = try reader.readU32();
15 const name_bytes = try reader.readBytes();
16 const name = try allocator.dupe(u8, name_bytes);
17 errdefer allocator.free(name);
18 const catalog_format = try reader.readU32();
19 const catalog_version = try reader.readU64();
20 const schema = try reader.hash();
21 var schema_descriptor = try record_mod.readRelationSchema(allocator, reader);
22 errdefer schema_descriptor.deinit();
23 const table_header = try readMapRootHeader(reader);
24 const stats = try record_mod.readStatsRoot(reader);
25 const index_count = try reader.readU32();
26 const indexes = try allocator.alloc(version.IndexRoot, index_count);
27 errdefer allocator.free(indexes);
28 const index_keys = try allocator.alloc(?version.Hash, index_count);
29 errdefer allocator.free(index_keys);
30 for (indexes, index_keys) |*index, *index_key| {
31 const fields = try reader.hash();
32 const map_header = try readMapRootHeader(reader);
33 index_key.* = map_header.root_key;
34 index.* = .{
35 .fields = fields,
36 .map = emptyMapRoot(allocator, map_header),
37 .stats = try reader.hash(),
38 .hash = try reader.hash(),
39 };
40 }
41 return .{
42 .root = .{
43 .allocator = allocator,
44 .format = format,
45 .name = name,
46 .catalog = .{
47 .format = catalog_format,
48 .version = catalog_version,
49 },
50 .schema = schema,
51 .schema_descriptor = schema_descriptor,
52 .table = emptyMapRoot(allocator, table_header),
53 .indexes = indexes,
54 .stats = stats,
55 .hash = try reader.hash(),
56 },
57 .table_key = table_header.root_key,
58 .index_keys = index_keys,
59 };
60 }
61
62 pub fn readIndexedRelationRoot(self: *const History, allocator: Allocator, hash: version.Hash, location: record_mod.PayloadLocation) Error!store_mod.ShallowRelationRoot {
63 const payload = try readPayload(self, allocator, .relation_root, location);
64 defer allocator.free(payload);
65 var reader = record_mod.PayloadReader.init(payload);
66 var decoded = try readRelationRootShallow(allocator, &reader);
67 errdefer decoded.root.deinit();
68 errdefer allocator.free(decoded.index_keys);
69 try reader.finish();
70 if (!version.same(hash, decoded.root.hash)) return error.InvalidHistory;
71 return decoded;
72 }
73
74 pub fn readMapRootHeader(reader: *record_mod.PayloadReader) Error!store_mod.MapRootHeader {
75 return .{
76 .summary = try record_mod.readSummary(reader),
77 .hash = try reader.hash(),
78 .subtree = try reader.hash(),
79 .root_key = try reader.optionalHash(),
80 };
81 }
82
83 pub fn emptyMapRoot(allocator: Allocator, header: store_mod.MapRootHeader) version.MapRoot {
84 return .{
85 .allocator = allocator,
86 .summary = header.summary,
87 .hash = header.hash,
88 .subtree = header.subtree,
89 .nodes = &.{},
90 .edges = &.{},
91 };
92 }
93
94 pub fn shallowMapRoot(allocator: Allocator, source: *const version.MapRoot) version.MapRoot {
95 return .{
96 .allocator = allocator,
97 .summary = source.summary,
98 .hash = source.hash,
99 .subtree = source.subtree,
100 .nodes = &.{},
101 .edges = &.{},
102 };
103 }
104
105 pub fn shrinkRelationRootMaps(allocator: Allocator, root: *version.RelationRoot) void {
106 const table = shallowMapRoot(allocator, &root.table);
107 root.table.deinit();
108 root.table = table;
109 for (root.indexes) |*index| {
110 const map = shallowMapRoot(allocator, &index.map);
111 index.map.deinit();
112 index.map = map;
113 }
114 }
115
116 pub fn merkleMapRoot(self: *const History, allocator: Allocator, summary: tree.Summary, hash: version.Hash, subtree: version.Hash, root_key: ?version.Hash) Error!version.MapRoot {
117 var nodes: std.ArrayList(tree.Node) = .empty;
118 var edges: std.ArrayList(usize) = .empty;
119 var sources: std.ArrayList(store_mod.MaterializedTreeSource) = .empty;
120 var materialized: store_mod.HashIndex = .empty;
121 defer {
122 for (sources.items) |source| allocator.free(source.children);
123 sources.deinit(allocator);
124 }
125 defer materialized.deinit(allocator);
126 errdefer {
127 for (nodes.items) |node| {
128 allocator.free(node.lower);
129 if (node.upper) |upper| allocator.free(upper);
130 }
131 nodes.deinit(allocator);
132 edges.deinit(allocator);
133 }
134
135 if (root_key) |key| {
136 _ = try materializeTreeNode(self, allocator, &nodes, &sources, &materialized, key);
137 var cursor: usize = 0;
138 while (cursor < nodes.items.len) : (cursor += 1) {
139 const source = sources.items[cursor];
140 const children_start = edges.items.len;
141 try edges.ensureUnusedCapacity(allocator, source.children.len);
142 for (source.children) |child_key| {
143 const child_index = try materializeTreeNode(self, allocator, &nodes, &sources, &materialized, child_key);
144 edges.appendAssumeCapacity(child_index);
145 }
146 if (source.children.len != 0) {
147 nodes.items[cursor].children_start = children_start;
148 nodes.items[cursor].children_len = source.children.len;
149 }
150 }
151 }
152
153 const owned_nodes = try nodes.toOwnedSlice(allocator);
154 errdefer {
155 for (owned_nodes) |node| {
156 allocator.free(node.lower);
157 if (node.upper) |upper| allocator.free(upper);
158 }
159 allocator.free(owned_nodes);
160 }
161 const owned_edges = try edges.toOwnedSlice(allocator);
162 return .{
163 .allocator = allocator,
164 .summary = summary,
165 .hash = hash,
166 .subtree = subtree,
167 .nodes = owned_nodes,
168 .edges = owned_edges,
169 };
170 }
171
172 pub fn materializeTreeNode(self: *const History, allocator: Allocator, nodes: *std.ArrayList(tree.Node), sources: *std.ArrayList(store_mod.MaterializedTreeSource), materialized: *store_mod.HashIndex, key: version.Hash) Error!usize {
173 if (materialized.get(key)) |index| return index;
174 const source = self.lookup.tree_nodes.get(key) orelse return error.InvalidHistory;
175 const record = &self.tree_nodes.items[source];
176 var node = try readTreeNodeRecord(self, allocator, record);
177 errdefer node.deinit(allocator);
178 try nodes.ensureUnusedCapacity(allocator, 1);
179 try sources.ensureUnusedCapacity(allocator, 1);
180 try materialized.ensureUnusedCapacity(allocator, 1);
181 const index = nodes.items.len;
182 nodes.appendAssumeCapacity(node.node);
183 sources.appendAssumeCapacity(.{ .children = node.children });
184 materialized.putAssumeCapacity(key, index);
185 return index;
186 }
187
188 pub fn readTreeNodeRecord(self: *const History, allocator: Allocator, record: *const record_mod.TreeNodeRecord) Error!store_mod.MaterializedTreeNode {
189 const payload = try readPayload(self, allocator, .tree_nodes, record.payload);
190 defer allocator.free(payload);
191 var reader = record_mod.PayloadReader.init(payload);
192 const count = try reader.readU32();
193 var index: u32 = 0;
194 while (index < count) : (index += 1) {
195 const key = try reader.hash();
196 const kind = try record_mod.nodeKind(try reader.readU8());
197 const lower_bytes = try reader.readBytes();
198 const upper_bytes = try reader.optionalBytes();
199 const depth = try record_mod.readUsize(&reader);
200 const summary = try record_mod.readSummary(&reader);
201 const hash = try reader.hash();
202 const child_count = try reader.readU32();
203 if (!version.same(key, record.key)) {
204 var skipped: u32 = 0;
205 while (skipped < child_count) : (skipped += 1) _ = try reader.hash();
206 continue;
207 }
208 const lower = try allocator.dupe(u8, lower_bytes);
209 errdefer allocator.free(lower);
210 const upper = if (upper_bytes) |bytes| try allocator.dupe(u8, bytes) else null;
211 errdefer if (upper) |bytes| allocator.free(bytes);
212 const children = try allocator.alloc(version.Hash, child_count);
213 var child_index: usize = 0;
214 errdefer allocator.free(children);
215 while (child_index < children.len) : (child_index += 1) children[child_index] = try reader.hash();
216 return .{
217 .node = .{
218 .kind = kind,
219 .lower = lower,
220 .upper = upper,
221 .depth = depth,
222 .summary = summary,
223 .hash = hash,
224 },
225 .children = children,
226 };
227 }
228 try reader.finish();
229 return error.InvalidHistory;
230 }
231
232 pub fn readHashListRecord(self: *const History, allocator: Allocator, kind: record_mod.RecordKind, key: version.Hash, storage: record_mod.HashListStorage) Error!record_mod.HashListView {
233 switch (storage) {
234 .materialized => |items| return .{ .allocator = allocator, .items = items },
235 .indexed => |location| {
236 const payload = try readPayload(self, allocator, kind, location);
237 defer allocator.free(payload);
238 var reader = record_mod.PayloadReader.init(payload);
239 if (!version.same(key, try reader.hash())) return error.InvalidHistory;
240 const count = try reader.readU32();
241 const items = try allocator.alloc(version.Hash, count);
242 errdefer allocator.free(items);
243 for (items) |*item| item.* = try reader.hash();
244 try reader.finish();
245 return .{ .allocator = allocator, .owned = items, .items = items };
246 },
247 }
248 }
249
250 pub fn readRelationSpansRecord(self: *const History, allocator: Allocator, root: version.Hash, storage: record_mod.ChunkSpanStorage) Error!record_mod.ChunkSpanView {
251 switch (storage) {
252 .materialized => |items| return .{ .allocator = allocator, .items = items },
253 .indexed => |location| return readIndexedRelationSpans(self, allocator, root, location),
254 }
255 }
256
257 fn readIndexedRelationSpans(self: *const History, allocator: Allocator, root: version.Hash, location: record_mod.PayloadLocation) Error!record_mod.ChunkSpanView {
258 const payload = try readPayload(self, allocator, .relation_spans, location);
259 defer allocator.free(payload);
260 var reader = record_mod.PayloadReader.init(payload);
261 if (!version.same(root, try reader.hash())) return error.InvalidHistory;
262 const count = try reader.readU32();
263 const spans = try allocator.alloc(record_mod.ChunkSpan, count);
264 errdefer allocator.free(spans);
265 for (spans) |*span| {
266 span.first = @bitCast(try reader.readU64());
267 span.last = @bitCast(try reader.readU64());
268 }
269 try reader.finish();
270 return .{ .allocator = allocator, .owned = spans, .items = spans };
271 }
272
273 pub fn readPayload(self: *const History, allocator: Allocator, kind: record_mod.RecordKind, location: record_mod.PayloadLocation) Error![]u8 {
274 const file = self.file orelse return error.InvalidHistory;
275 const payload = try allocator.alloc(u8, location.len);
276 errdefer allocator.free(payload);
277 if (try file.readPositionalAll(self.io, payload, location.offset) != location.len) return error.InvalidHistory;
278 const actual = record_mod.recordHash(@backingInt(kind), payload);
279 if (!version.same(location.expected, actual)) return error.InvalidHistory;
280 return payload;
281 }