indexed.zig (29006B)
1 //! Indexed Arboricx codec. No paths, permissions, compiler policy or IO actions. 2 //! Physical IDs accelerate traversal; exact constructor/child keys define bytes. 3 const std = @import("std"); 4 const Arena = @import("arena.zig").Arena; 5 const Node = @import("tree.zig").Node; 6 const reduce = @import("reduce.zig"); 7 pub const domain = "arboricx.indexed-tree.v1"; 8 const fields = [_][]const u8{ "arboricx.bundle.manifest.v1", "tree-calculus-executable-object", "tree-calculus.v1", "indexed", "arboricx.indexed.node.v1", "arboricx.indexed.payload.v1", "tree-calculus.v1", "normal-order", "arboricx.abi.tree.v1" }; 9 const Key = struct { tag: u8, left: u32 = 0, right: u32 = 0 }; 10 const Writer = struct { 11 allocator: std.mem.Allocator, 12 bytes: std.ArrayList(u8) = .empty, 13 pub fn writeAll(w: *Writer, data: []const u8) !void { 14 try w.raw(data); 15 } 16 fn raw(w: *Writer, data: []const u8) !void { 17 try w.bytes.appendSlice(w.allocator, data); 18 } 19 fn int(w: *Writer, comptime T: type, n: T) !void { 20 var data: [@sizeOf(T)]u8 = undefined; 21 std.mem.writeInt(T, &data, n, .big); 22 try w.raw(&data); 23 } 24 fn text(w: *Writer, data: []const u8) !void { 25 try w.int(u32, @intCast(data.len)); 26 try w.raw(data); 27 } 28 fn deinit(w: *Writer) void { 29 w.bytes.deinit(w.allocator); 30 } 31 }; 32 fn intern(nodes: *std.ArrayList(Key), keys: *std.AutoHashMap(Key, u32), key: Key) !u32 { 33 if (keys.get(key)) |id| return id; 34 if (nodes.items.len >= std.math.maxInt(u32)) return error.OutOfMemory; 35 const id: u32 = @intCast(nodes.items.len); 36 try nodes.append(keys.allocator, key); 37 try keys.put(key, id); 38 return id; 39 } 40 41 pub fn prepare(arena: *Arena, root: u32) !Plan { 42 const allocator = arena.allocator; 43 const base = arena.roots.items.len; 44 defer arena.roots.shrinkRetainingCapacity(base); 45 try arena.roots.append(allocator, root); 46 var memo = std.AutoHashMap(u32, ?u32).init(allocator); 47 defer memo.deinit(); 48 var keys = std.AutoHashMap(Key, u32).init(allocator); 49 defer keys.deinit(); 50 var nodes: std.ArrayList(Key) = .empty; 51 errdefer nodes.deinit(allocator); 52 const Frame = union(enum) { visit: u32, finish: struct { id: u32, node: Node } }; 53 var stack: std.ArrayList(Frame) = .empty; 54 defer stack.deinit(allocator); 55 try stack.append(allocator, .{ .visit = root }); 56 while (stack.pop()) |frame| switch (frame) { 57 .visit => |id| { 58 if (memo.get(id)) |entry| { 59 if (entry == null) return error.CyclicTree; 60 continue; 61 } 62 const forced = try reduce.reduce(id, arena, 1_000_000); 63 const node = arena.get(forced).*; 64 // Hold memoized IDs through later reductions, even if updates cut 65 // old graph edges. Collection must not recycle a memo's identity. 66 try arena.roots.appendSlice(allocator, &.{ id, forced }); 67 try memo.put(id, null); 68 try stack.append(allocator, .{ .finish = .{ .id = id, .node = node } }); 69 switch (node) { 70 .leaf => {}, 71 .stem => |s| try stack.append(allocator, .{ .visit = s.child }), 72 .fork => |f| { 73 try stack.append(allocator, .{ .visit = f.right }); 74 try stack.append(allocator, .{ .visit = f.left }); 75 }, 76 .app => unreachable, 77 } 78 }, 79 .finish => |f| { 80 const key: Key = switch (f.node) { 81 .leaf => .{ .tag = 0 }, 82 .stem => |s| .{ .tag = 1, .left = memo.get(s.child).?.? }, 83 .fork => |p| .{ .tag = 2, .left = memo.get(p.left).?.?, .right = memo.get(p.right).?.? }, 84 .app => unreachable, 85 }; 86 try memo.put(f.id, try intern(&nodes, &keys, key)); 87 }, 88 }; 89 const root_index = memo.get(root).?.?; 90 var manifest = Writer{ .allocator = allocator }; 91 defer manifest.deinit(); 92 try manifest.raw("ARBMNFST"); 93 try manifest.int(u16, 1); 94 try manifest.int(u16, 1); 95 for (fields) |field| try manifest.text(field); 96 try manifest.int(u32, 0); 97 try manifest.int(u8, 0); 98 try manifest.int(u32, 1); 99 try manifest.int(u32, root_index); 100 try manifest.text("default"); 101 try manifest.int(u32, 1); 102 try manifest.text("root"); 103 try manifest.int(u32, root_index); 104 try manifest.text("term"); 105 try manifest.text(fields[8]); 106 try manifest.int(u32, 1); 107 try manifest.int(u16, 5); 108 try manifest.text("arboricx"); 109 try manifest.int(u32, 0); 110 var payload_length: u64 = 8; 111 for (nodes.items) |key| payload_length += 5 + 4 * @as(u64, key.tag); 112 const manifest_bytes = try manifest.bytes.toOwnedSlice(allocator); 113 errdefer allocator.free(manifest_bytes); 114 return .{ .allocator = allocator, .nodes = try nodes.toOwnedSlice(allocator), .manifest = manifest_bytes, .payload_length = payload_length }; 115 } 116 117 /// Graph-proportional canonical plan. It contains no encoded payload and no arena 118 /// IDs; emission can be repeated without retaining a previous byte stream. 119 pub const Plan = struct { 120 allocator: std.mem.Allocator, 121 nodes: []Key, 122 manifest: []u8, 123 payload_length: u64, 124 pub fn deinit(self: *Plan) void { 125 self.allocator.free(self.nodes); 126 self.allocator.free(self.manifest); 127 self.* = undefined; 128 } 129 pub fn encodedLength(self: *const Plan) u64 { 130 return 96 + @as(u64, self.manifest.len) + self.payload_length; 131 } 132 /// Sink.writeAll consumes borrowed chunks synchronously; <=4096 bytes each. 133 /// A failing sink is never retried by this emitter. 134 pub fn emit(self: *const Plan, sink: anytype) !void { 135 var output = ChunkWriter(@TypeOf(sink)){ .sink = sink }; 136 try output.raw("ARBORICX"); 137 try output.int(u16, 1); 138 try output.int(u16, 0); 139 try output.int(u32, 2); 140 try output.int(u64, 0); 141 try output.int(u64, 32); 142 var offset: u64 = 96; 143 for ([_]u64{ self.manifest.len, self.payload_length }, 1..) |length, kind| { 144 try output.int(u32, @intCast(kind)); 145 try output.int(u16, 1); 146 try output.int(u16, 1); 147 try output.int(u16, 0); 148 try output.int(u16, 0); 149 try output.int(u64, offset); 150 try output.int(u64, length); 151 try output.int(u32, 0); 152 offset += length; 153 } 154 try output.raw(self.manifest); 155 try output.int(u64, self.nodes.len); 156 for (self.nodes) |key| { 157 try output.int(u32, 1 + 4 * @as(u32, key.tag)); 158 try output.int(u8, key.tag); 159 if (key.tag >= 1) try output.int(u32, key.left); 160 if (key.tag == 2) try output.int(u32, key.right); 161 } 162 try output.flush(); 163 } 164 pub fn hash(self: *const Plan) ![64]u8 { 165 var sink = HashSink{}; 166 sink.context.update(domain ++ "\x00"); 167 try self.emit(&sink); 168 var raw: [32]u8 = undefined; 169 sink.context.final(&raw); 170 return std.fmt.bytesToHex(raw, .lower); 171 } 172 }; 173 const HashSink = struct { 174 context: std.crypto.hash.sha2.Sha256 = .init(.{}), 175 pub fn writeAll(self: *HashSink, bytes: []const u8) !void { 176 self.context.update(bytes); 177 } 178 }; 179 fn ChunkWriter(comptime Sink: type) type { 180 return struct { 181 sink: Sink, 182 buffer: [4096]u8 = undefined, 183 used: usize = 0, 184 fn flush(self: *@This()) !void { 185 if (self.used == 0) return; 186 try self.sink.writeAll(self.buffer[0..self.used]); 187 self.used = 0; 188 } 189 fn raw(self: *@This(), data: []const u8) !void { 190 var offset: usize = 0; 191 while (offset < data.len) { 192 const count = @min(data.len - offset, self.buffer.len - self.used); 193 @memcpy(self.buffer[self.used..][0..count], data[offset..][0..count]); 194 self.used += count; 195 offset += count; 196 if (self.used == self.buffer.len) try self.flush(); 197 } 198 } 199 fn int(self: *@This(), comptime T: type, value: T) !void { 200 var bytes: [@sizeOf(T)]u8 = undefined; 201 std.mem.writeInt(T, &bytes, value, .big); 202 try self.raw(&bytes); 203 } 204 }; 205 } 206 207 /// Compatibility whole-value encoder; bounded transports use Plan.emit instead. 208 pub fn encode(arena: *Arena, root: u32) ![]u8 { 209 var plan = try prepare(arena, root); 210 defer plan.deinit(); 211 var output = Writer{ .allocator = arena.allocator }; 212 errdefer output.deinit(); 213 try plan.emit(&output); 214 return output.bytes.toOwnedSlice(arena.allocator); 215 } 216 217 pub fn digest(bytes: []const u8) [64]u8 { 218 var hash = std.crypto.hash.sha2.Sha256.init(.{}); 219 hash.update(domain ++ "\x00"); 220 hash.update(bytes); 221 var raw: [32]u8 = undefined; 222 hash.final(&raw); 223 return std.fmt.bytesToHex(raw, .lower); 224 } 225 226 const Reader = struct { 227 bytes: []const u8, 228 pos: usize = 0, 229 fn take(r: *Reader, n: usize) ![]const u8 { 230 if (n > r.bytes.len - r.pos) return error.InvalidData; 231 const data = r.bytes[r.pos..][0..n]; 232 r.pos += n; 233 return data; 234 } 235 fn int(r: *Reader, comptime T: type) !T { 236 return std.mem.readInt(T, (try r.take(@sizeOf(T)))[0..@sizeOf(T)], .big); 237 } 238 fn text(r: *Reader) ![]const u8 { 239 const data = try r.take(try r.int(u32)); 240 if (!std.unicode.utf8ValidateSlice(data)) return error.InvalidData; 241 return data; 242 } 243 fn expect(r: *Reader, data: []const u8) !void { 244 if (!std.mem.eql(u8, try r.take(data.len), data)) return error.InvalidData; 245 } 246 fn remaining(r: *const Reader) usize { 247 return r.bytes.len - r.pos; 248 } 249 fn end(r: *Reader) !void { 250 if (r.pos != r.bytes.len) return error.InvalidData; 251 } 252 }; 253 fn section(bytes: []const u8, start: u64, len: u64) ![]const u8 { 254 if (start > bytes.len or len > bytes.len - start) return error.InvalidData; 255 return bytes[@intCast(start)..][0..@intCast(len)]; 256 } 257 258 /// General validated bundle reader, also shared by the C ABI. Single-tree IO 259 /// additionally requires exactly one root/export named "root". Like Haskell, 260 /// read accepts valid noncanonical layouts; only encode defines canonical bytes. 261 pub fn load(arena: *Arena, bytes: []const u8, name: ?[]const u8, single: bool) !u32 { 262 var header = Reader{ .bytes = bytes }; 263 try header.expect("ARBORICX"); 264 if (try header.int(u16) != 1) return error.InvalidData; 265 _ = try header.int(u16); 266 const count = try header.int(u32); 267 _ = try header.int(u64); 268 const start = try header.int(u64); 269 var directory = Reader{ .bytes = try section(bytes, start, @as(u64, count) * 32) }; 270 var manifest: ?[]const u8 = null; 271 var payload: ?[]const u8 = null; 272 for (0..count) |_| { 273 const kind = try directory.int(u32); 274 _ = try directory.int(u16); 275 const flags = try directory.int(u16); 276 const compression = try directory.int(u16); 277 _ = try directory.int(u16); 278 const offset = try directory.int(u64); 279 const len = try directory.int(u64); 280 _ = try directory.int(u32); 281 if (kind == 1 or kind == 2) { 282 if (compression != 0) return error.InvalidData; 283 const data = try section(bytes, offset, len); 284 if (kind == 1) { 285 if (manifest != null) return error.InvalidData; 286 manifest = data; 287 } else { 288 if (payload != null) return error.InvalidData; 289 payload = data; 290 } 291 } else if (flags & 1 != 0) return error.InvalidData; 292 } 293 const selection = try parseManifest(arena, manifest orelse return error.InvalidData, name, single); 294 var n = Reader{ .bytes = payload orelse return error.InvalidData }; 295 return loadNodes(arena, &n, selection); 296 } 297 const Selection = struct { max_root: u32, selected: ?u32 }; 298 fn parseManifest(arena: *Arena, bytes: []const u8, name: ?[]const u8, single: bool) !Selection { 299 var m = Reader{ .bytes = bytes }; 300 try m.expect("ARBMNFST"); 301 if (try m.int(u16) != 1 or try m.int(u16) != 1) return error.InvalidData; 302 for (fields) |field| if (!std.mem.eql(u8, try m.text(), field)) return error.InvalidData; 303 if (try m.int(u32) != 0 or try m.int(u8) != 0) return error.InvalidData; 304 const root_count = try m.int(u32); 305 if (root_count == 0 or root_count > (m.bytes.len - m.pos) / 8 or (single and root_count != 1)) return error.InvalidData; 306 var max_root: u32 = 0; 307 var first: u32 = 0; 308 for (0..root_count) |i| { 309 const root = try m.int(u32); 310 _ = try m.text(); 311 if (i == 0) first = root; 312 max_root = @max(max_root, root); 313 } 314 const export_count = try m.int(u32); 315 if (export_count == 0 or export_count > (m.bytes.len - m.pos) / 16 or (single and export_count != 1)) return error.InvalidData; 316 var names = std.StringHashMap(void).init(arena.allocator); 317 defer names.deinit(); 318 var selected: ?u32 = if (name == null) first else null; 319 for (0..export_count) |_| { 320 const exported = try m.text(); 321 const root = try m.int(u32); 322 if (exported.len == 0 or names.contains(exported)) return error.InvalidData; 323 try names.put(exported, {}); 324 if (!std.mem.eql(u8, try m.text(), "term") or !std.mem.eql(u8, try m.text(), fields[8])) return error.InvalidData; 325 if (single and (!std.mem.eql(u8, exported, "root") or root != first)) return error.InvalidData; 326 if (name) |requested| { 327 if (std.mem.eql(u8, requested, exported)) selected = root; 328 } 329 max_root = @max(max_root, root); 330 } 331 var known_metadata: u8 = 0; 332 for (0..2) |group| { 333 const tlvs = try m.int(u32); 334 if (tlvs > (m.bytes.len - m.pos) / 6) return error.InvalidData; 335 for (0..tlvs) |_| { 336 const tag = try m.int(u16); 337 const value = try m.take(try m.int(u32)); 338 if (group == 0 and tag >= 1 and tag <= 5) { 339 const mask = @as(u8, 1) << @as(u3, @intCast(tag)); 340 if (known_metadata & mask == 0 and !std.unicode.utf8ValidateSlice(value)) return error.InvalidData; 341 known_metadata |= mask; 342 } 343 } 344 } 345 try m.end(); 346 return .{ .max_root = max_root, .selected = selected }; 347 } 348 fn loadNodes(arena: *Arena, n: anytype, selection: Selection) !u32 { 349 const node_count = try n.int(u64); 350 if (node_count == 0 or node_count > std.math.maxInt(u32) or node_count > n.remaining() / 5 or selection.max_root >= node_count) return error.InvalidData; 351 const ids = try arena.allocator.alloc(u32, @intCast(node_count)); 352 defer arena.allocator.free(ids); 353 var keys = std.AutoHashMap(Key, void).init(arena.allocator); 354 defer keys.deinit(); 355 for (ids, 0..) |*id, i| { 356 const size = try n.int(u32); 357 const tag = try n.int(u8); 358 if (tag > 2 or size != 1 + 4 * @as(u32, tag)) return error.InvalidData; 359 var key = Key{ .tag = tag }; 360 if (tag >= 1) { 361 key.left = try n.int(u32); 362 if (key.left >= i) return error.InvalidData; 363 } 364 if (tag == 2) { 365 key.right = try n.int(u32); 366 if (key.right >= i) return error.InvalidData; 367 } 368 if (keys.contains(key)) return error.InvalidData; 369 try keys.put(key, {}); 370 id.* = try arena.alloc(switch (tag) { 371 0 => .leaf, 372 1 => .{ .stem = .{ .child = ids[key.left] } }, 373 2 => .{ .fork = .{ .left = ids[key.left], .right = ids[key.right] } }, 374 else => unreachable, 375 }); 376 } 377 try n.end(); 378 return ids[selection.selected orelse return error.ExportNotFound]; 379 } 380 381 /// Decode only an already-authenticated stable snapshot. The source exposes a 382 /// length and exact bounded positional reads; neither original-input rereading 383 /// nor whole encoded-payload allocation occurs here. External padding is allowed. 384 pub fn loadSnapshot(arena: *Arena, source: anytype) !u32 { 385 var header_bytes: [32]u8 = undefined; 386 if (source.length < header_bytes.len) return error.InvalidData; 387 try source.readAt(0, &header_bytes); 388 var header = Reader{ .bytes = &header_bytes }; 389 try header.expect("ARBORICX"); 390 if (try header.int(u16) != 1) return error.InvalidData; 391 _ = try header.int(u16); 392 const count = try header.int(u32); 393 if (count > 64) return error.InvalidData; 394 _ = try header.int(u64); 395 const start = try header.int(u64); 396 try snapshotRange(source.length, start, @as(u64, count) * 32); 397 const Section = struct { offset: u64, length: u64 }; 398 var manifest: ?Section = null; 399 var payload: ?Section = null; 400 for (0..count) |i| { 401 var raw: [32]u8 = undefined; 402 try source.readAt(start + @as(u64, i) * 32, &raw); 403 var entry = Reader{ .bytes = &raw }; 404 const kind = try entry.int(u32); 405 _ = try entry.int(u16); 406 const flags = try entry.int(u16); 407 const compression = try entry.int(u16); 408 _ = try entry.int(u16); 409 const offset = try entry.int(u64); 410 const length = try entry.int(u64); 411 _ = try entry.int(u32); 412 if (kind == 1 or kind == 2) { 413 if (compression != 0) return error.InvalidData; 414 try snapshotRange(source.length, offset, length); 415 if (kind == 1) { 416 if (manifest != null or length > 65536) return error.InvalidData; 417 manifest = .{ .offset = offset, .length = length }; 418 } else { 419 if (payload != null) return error.InvalidData; 420 payload = .{ .offset = offset, .length = length }; 421 } 422 } else if (flags & 1 != 0) return error.InvalidData; 423 } 424 const m = manifest orelse return error.InvalidData; 425 const bytes = try arena.allocator.alloc(u8, @intCast(m.length)); 426 defer arena.allocator.free(bytes); 427 var at: usize = 0; 428 while (at < bytes.len) { 429 const size = @min(4096, bytes.len - at); 430 try source.readAt(m.offset + at, bytes[at..][0..size]); 431 at += size; 432 } 433 const selection = try parseManifest(arena, bytes, "root", true); 434 const p = payload orelse return error.InvalidData; 435 var nodes = SnapshotReader(@TypeOf(source)){ .source = source, .start = p.offset, .length = p.length }; 436 return loadNodes(arena, &nodes, selection); 437 } 438 fn snapshotRange(length: u64, offset: u64, count: u64) !void { 439 if (offset > length or count > length - offset) return error.InvalidData; 440 } 441 fn SnapshotReader(comptime Source: type) type { 442 return struct { 443 source: Source, 444 start: u64, 445 length: u64, 446 pos: u64 = 0, 447 cache: [4096]u8 = undefined, 448 used: usize = 0, 449 available: usize = 0, 450 fn remaining(self: *const @This()) u64 { 451 return self.length - self.pos; 452 } 453 fn int(self: *@This(), comptime T: type) !T { 454 if (self.remaining() < @sizeOf(T)) return error.InvalidData; 455 var bytes: [@sizeOf(T)]u8 = undefined; 456 for (&bytes) |*byte| { 457 if (self.used == self.available) { 458 self.available = @intCast(@min(self.remaining(), self.cache.len)); 459 try self.source.readAt(self.start + self.pos, self.cache[0..self.available]); 460 self.used = 0; 461 } 462 byte.* = self.cache[self.used]; 463 self.used += 1; 464 self.pos += 1; 465 } 466 return std.mem.readInt(T, &bytes, .big); 467 } 468 fn end(self: *const @This()) !void { 469 if (self.remaining() != 0) return error.InvalidData; 470 } 471 }; 472 } 473 474 test "canonical leaf matches independent writer profile and domain digest" { 475 var arena = Arena.init(std.testing.allocator); 476 defer arena.deinit(); 477 const bytes = try encode(&arena, try arena.alloc(.leaf)); 478 defer arena.allocator.free(bytes); 479 try std.testing.expectEqual(@as(usize, 431), bytes.len); 480 // Independently assembled by test/executable_object.py's wire profile. 481 try std.testing.expectEqualStrings("6f93378feaa8bf5ab7cefc071175a654c871bfd53f165d7d96795fb2b38483f1", &digest(bytes)); 482 const decoded = try load(&arena, bytes, "root", true); 483 try std.testing.expect(arena.get(decoded).* == .leaf); 484 } 485 486 test "physical sharing is only an acceleration hint, and lazy children are serialized" { 487 var arena = Arena.init(std.testing.allocator); 488 defer arena.deinit(); 489 const leaf = try arena.alloc(.leaf); 490 const child = try arena.alloc(.{ .stem = .{ .child = leaf } }); 491 const shared = try arena.alloc(.{ .fork = .{ .left = child, .right = child } }); 492 const other_leaf = try arena.alloc(.leaf); 493 const other_child = try arena.alloc(.{ .stem = .{ .child = other_leaf } }); 494 const constant = try arena.alloc(.{ .fork = .{ .left = other_leaf, .right = other_child } }); 495 const delayed = try arena.alloc(.{ .app = .{ .func = constant, .arg = other_leaf } }); 496 const copied = try arena.alloc(.{ .fork = .{ .left = child, .right = delayed } }); 497 const a = try encode(&arena, shared); 498 defer arena.allocator.free(a); 499 arena.gc_enabled = true; 500 try arena.setGcPolicy(1, 1); 501 const b = try encode(&arena, copied); 502 defer arena.allocator.free(b); 503 try std.testing.expectEqualSlices(u8, a, b); 504 try std.testing.expectEqual(@as(usize, 0), arena.roots.items.len); 505 const decoded = try load(&arena, a, "root", true); 506 try std.testing.expectEqual(arena.get(decoded).fork.left, arena.get(decoded).fork.right); 507 } 508 509 test "deep exponentially expanded trees use iterative DAG traversal" { 510 var arena = Arena.init(std.testing.allocator); 511 defer arena.deinit(); 512 var root = try arena.alloc(.leaf); 513 for (0..100000) |_| root = try arena.alloc(.{ .fork = .{ .left = root, .right = root } }); 514 const bytes = try encode(&arena, root); 515 defer arena.allocator.free(bytes); 516 try std.testing.expectEqual(@as(usize, 431 + 13 * 100000), bytes.len); 517 const copied = try load(&arena, bytes, "root", true); 518 const again = try encode(&arena, copied); 519 defer arena.allocator.free(again); 520 try std.testing.expectEqualSlices(u8, bytes, again); 521 } 522 523 test "bundle parser rejects every truncated prefix and safely handles byte mutations" { 524 var arena = Arena.init(std.testing.allocator); 525 defer arena.deinit(); 526 const bytes = try encode(&arena, try arena.alloc(.leaf)); 527 defer arena.allocator.free(bytes); 528 for (0..bytes.len) |len| try std.testing.expectError(error.InvalidData, load(&arena, bytes[0..len], "root", true)); 529 for (bytes) |*byte| { 530 byte.* ^= 0xff; 531 _ = load(&arena, bytes, "root", true) catch |err| switch (err) { 532 error.InvalidData, error.ExportNotFound => 0, 533 else => return err, 534 }; 535 byte.* ^= 0xff; 536 } 537 // Section count, offset and size arithmetic must not overflow or slice 538 // outside input, even when the supplied bytes themselves are authenticated. 539 for ([_]usize{ 24, 44, 52, 76, 84 }) |offset| { 540 const old = std.mem.readInt(u64, bytes[offset..][0..8], .big); 541 std.mem.writeInt(u64, bytes[offset..][0..8], std.math.maxInt(u64), .big); 542 try std.testing.expectError(error.InvalidData, load(&arena, bytes, "root", true)); 543 std.mem.writeInt(u64, bytes[offset..][0..8], old, .big); 544 } 545 } 546 547 fn allocationProbe(allocator: std.mem.Allocator) !void { 548 var arena = Arena.init(allocator); 549 defer arena.deinit(); 550 const leaf = try arena.alloc(.leaf); 551 const root = try arena.alloc(.{ .fork = .{ .left = leaf, .right = leaf } }); 552 const bytes = try encode(&arena, root); 553 defer allocator.free(bytes); 554 _ = try load(&arena, bytes, "root", true); 555 } 556 557 test "indexed codec allocation failures unwind all scratch storage" { 558 try std.testing.checkAllAllocationFailures(std.testing.allocator, allocationProbe, .{}); 559 } 560 561 test "reader rejects duplicate constructors, forward edges and mismatched single roots" { 562 var arena = Arena.init(std.testing.allocator); 563 defer arena.deinit(); 564 const leaf = try arena.alloc(.leaf); 565 const root = try arena.alloc(.{ .stem = .{ .child = leaf } }); 566 const bytes = try encode(&arena, root); 567 defer arena.allocator.free(bytes); 568 const node_offset: usize = @intCast(std.mem.readInt(u64, bytes[76..84], .big)); 569 const child_offset = node_offset + 8 + 5 + 5; 570 std.mem.writeInt(u32, bytes[child_offset..][0..4], 1, .big); 571 try std.testing.expectError(error.InvalidData, load(&arena, bytes, "root", true)); 572 std.mem.writeInt(u32, bytes[child_offset..][0..4], 0, .big); 573 // Valid general bundle with unequal root/export indices is not a valid 574 // name-neutral single-tree object, even when both indices are in bounds. 575 const export_offset = std.mem.indexOf(u8, bytes, "root").? + 4; 576 std.mem.writeInt(u32, bytes[export_offset..][0..4], 0, .big); 577 try std.testing.expectError(error.InvalidData, load(&arena, bytes, "root", true)); 578 _ = try load(&arena, bytes, "root", false); 579 const one = try encode(&arena, leaf); 580 defer arena.allocator.free(one); 581 const duplicate = try arena.allocator.alloc(u8, one.len + 5); 582 defer arena.allocator.free(duplicate); 583 @memcpy(duplicate[0..one.len], one); 584 @memcpy(duplicate[one.len..], "\x00\x00\x00\x01\x00"); 585 std.mem.writeInt(u64, duplicate[84..92], 18, .big); 586 std.mem.writeInt(u64, duplicate[node_offset..][0..8], 2, .big); 587 try std.testing.expectError(error.InvalidData, load(&arena, duplicate, "root", true)); 588 } 589 590 test "canonical plan streams bounded repeatable chunks and stops at sink failure" { 591 const t = std.testing; 592 var arena = Arena.init(t.allocator); 593 defer arena.deinit(); 594 var root = try arena.alloc(.leaf); 595 for (0..10000) |_| root = try arena.alloc(.{ .fork = .{ .left = root, .right = root } }); 596 var plan = try prepare(&arena, root); 597 defer plan.deinit(); 598 try t.expectEqual(@as(u64, 130431), plan.encodedLength()); 599 const Sink = struct { 600 count: u64 = 0, 601 calls: usize = 0, 602 fail_at: ?usize = null, 603 pub fn writeAll(self: *@This(), bytes: []const u8) !void { 604 try t.expect(bytes.len > 0 and bytes.len <= 4096); 605 self.calls += 1; 606 if (self.fail_at == self.calls) return error.InjectedFailure; 607 self.count += bytes.len; 608 } 609 }; 610 var sink = Sink{}; 611 try plan.emit(&sink); 612 try t.expectEqual(plan.encodedLength(), sink.count); 613 const calls = sink.calls; 614 for (1..calls + 1) |step| { 615 var failing = Sink{ .fail_at = step }; 616 try t.expectError(error.InjectedFailure, plan.emit(&failing)); 617 try t.expectEqual(step, failing.calls); 618 } 619 // Independent Python wire profile: io_v2_indexed_write.dag(10000, True). 620 try t.expectEqualStrings("9039b73aff5b088b972a22e41728147bda274d1af9ca01a92afa747a930722b9", &(try plan.hash())); 621 const whole = try encode(&arena, root); 622 defer t.allocator.free(whole); 623 try t.expectEqualSlices(u8, &digest(whole), &(try plan.hash())); 624 var second = Writer{ .allocator = t.allocator }; 625 defer second.deinit(); 626 try plan.emit(&second); 627 try t.expectEqualSlices(u8, whole, second.bytes.items); 628 try t.expectEqual(@as(usize, 0), arena.roots.items.len); 629 } 630 631 const MemorySnapshot = struct { 632 bytes: []const u8, 633 length: u64, 634 pub fn readAt(self: *@This(), offset: u64, target: []u8) !void { 635 try std.testing.expect(target.len <= 4096); 636 if (offset > self.length or target.len > self.length - offset) return error.InvalidData; 637 @memcpy(target, self.bytes[@intCast(offset)..][0..target.len]); 638 } 639 }; 640 test "bounded snapshot decoder rejects every truncation and mutation without unchecked ranges" { 641 var arena = Arena.init(std.testing.allocator); 642 defer arena.deinit(); 643 const bytes = try encode(&arena, try arena.alloc(.leaf)); 644 defer arena.allocator.free(bytes); 645 for (0..bytes.len) |len| { 646 var source = MemorySnapshot{ .bytes = bytes, .length = len }; 647 try std.testing.expectError(error.InvalidData, loadSnapshot(&arena, &source)); 648 } 649 var source = MemorySnapshot{ .bytes = bytes, .length = bytes.len }; 650 for (bytes) |*byte| { 651 byte.* ^= 0xff; 652 _ = loadSnapshot(&arena, &source) catch |err| switch (err) { 653 error.InvalidData, error.ExportNotFound => 0, 654 else => return err, 655 }; 656 byte.* ^= 0xff; 657 } 658 const root = try loadSnapshot(&arena, &source); 659 try std.testing.expect(arena.get(root).* == .leaf); 660 for ([_]usize{ 24, 44, 52, 76, 84 }) |offset| { 661 const old = std.mem.readInt(u64, bytes[offset..][0..8], .big); 662 std.mem.writeInt(u64, bytes[offset..][0..8], std.math.maxInt(u64), .big); 663 try std.testing.expectError(error.InvalidData, loadSnapshot(&arena, &source)); 664 std.mem.writeInt(u64, bytes[offset..][0..8], old, .big); 665 } 666 }