indexed.zig (18168B)
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 fn raw(w: *Writer, data: []const u8) !void { 14 try w.bytes.appendSlice(w.allocator, data); 15 } 16 fn int(w: *Writer, comptime T: type, n: T) !void { 17 var data: [@sizeOf(T)]u8 = undefined; 18 std.mem.writeInt(T, &data, n, .big); 19 try w.raw(&data); 20 } 21 fn text(w: *Writer, data: []const u8) !void { 22 try w.int(u32, @intCast(data.len)); 23 try w.raw(data); 24 } 25 fn deinit(w: *Writer) void { 26 w.bytes.deinit(w.allocator); 27 } 28 }; 29 fn intern(nodes: *std.ArrayList(Key), keys: *std.AutoHashMap(Key, u32), key: Key) !u32 { 30 if (keys.get(key)) |id| return id; 31 if (nodes.items.len >= std.math.maxInt(u32)) return error.OutOfMemory; 32 const id: u32 = @intCast(nodes.items.len); 33 try nodes.append(keys.allocator, key); 34 try keys.put(key, id); 35 return id; 36 } 37 38 pub fn encode(arena: *Arena, root: u32) ![]u8 { 39 const allocator = arena.allocator; 40 const base = arena.roots.items.len; 41 defer arena.roots.shrinkRetainingCapacity(base); 42 try arena.roots.append(allocator, root); 43 var memo = std.AutoHashMap(u32, ?u32).init(allocator); 44 defer memo.deinit(); 45 var keys = std.AutoHashMap(Key, u32).init(allocator); 46 defer keys.deinit(); 47 var nodes: std.ArrayList(Key) = .empty; 48 defer nodes.deinit(allocator); 49 const Frame = union(enum) { visit: u32, finish: struct { id: u32, node: Node } }; 50 var stack: std.ArrayList(Frame) = .empty; 51 defer stack.deinit(allocator); 52 try stack.append(allocator, .{ .visit = root }); 53 while (stack.pop()) |frame| switch (frame) { 54 .visit => |id| { 55 if (memo.get(id)) |entry| { 56 if (entry == null) return error.CyclicTree; 57 continue; 58 } 59 const forced = try reduce.reduce(id, arena, 1_000_000); 60 const node = arena.get(forced).*; 61 // Hold memoized IDs through later reductions, even if updates cut 62 // old graph edges. Collection must not recycle a memo's identity. 63 try arena.roots.appendSlice(allocator, &.{ id, forced }); 64 try memo.put(id, null); 65 try stack.append(allocator, .{ .finish = .{ .id = id, .node = node } }); 66 switch (node) { 67 .leaf => {}, 68 .stem => |s| try stack.append(allocator, .{ .visit = s.child }), 69 .fork => |f| { 70 try stack.append(allocator, .{ .visit = f.right }); 71 try stack.append(allocator, .{ .visit = f.left }); 72 }, 73 .app => unreachable, 74 } 75 }, 76 .finish => |f| { 77 const key: Key = switch (f.node) { 78 .leaf => .{ .tag = 0 }, 79 .stem => |s| .{ .tag = 1, .left = memo.get(s.child).?.? }, 80 .fork => |p| .{ .tag = 2, .left = memo.get(p.left).?.?, .right = memo.get(p.right).?.? }, 81 .app => unreachable, 82 }; 83 try memo.put(f.id, try intern(&nodes, &keys, key)); 84 }, 85 }; 86 const root_index = memo.get(root).?.?; 87 var manifest = Writer{ .allocator = allocator }; 88 defer manifest.deinit(); 89 try manifest.raw("ARBMNFST"); 90 try manifest.int(u16, 1); 91 try manifest.int(u16, 1); 92 for (fields) |field| try manifest.text(field); 93 try manifest.int(u32, 0); 94 try manifest.int(u8, 0); 95 try manifest.int(u32, 1); 96 try manifest.int(u32, root_index); 97 try manifest.text("default"); 98 try manifest.int(u32, 1); 99 try manifest.text("root"); 100 try manifest.int(u32, root_index); 101 try manifest.text("term"); 102 try manifest.text(fields[8]); 103 try manifest.int(u32, 1); 104 try manifest.int(u16, 5); 105 try manifest.text("arboricx"); 106 try manifest.int(u32, 0); 107 var node_bytes = Writer{ .allocator = allocator }; 108 defer node_bytes.deinit(); 109 try node_bytes.int(u64, nodes.items.len); 110 for (nodes.items) |key| { 111 try node_bytes.int(u32, 1 + 4 * @as(u32, key.tag)); 112 try node_bytes.int(u8, key.tag); 113 if (key.tag >= 1) try node_bytes.int(u32, key.left); 114 if (key.tag == 2) try node_bytes.int(u32, key.right); 115 } 116 var output = Writer{ .allocator = allocator }; 117 errdefer output.deinit(); 118 try output.raw("ARBORICX"); 119 try output.int(u16, 1); 120 try output.int(u16, 0); 121 try output.int(u32, 2); 122 try output.int(u64, 0); 123 try output.int(u64, 32); 124 var offset: u64 = 96; 125 for ([_][]const u8{ manifest.bytes.items, node_bytes.bytes.items }, 1..) |data, kind| { 126 try output.int(u32, @intCast(kind)); 127 try output.int(u16, 1); 128 try output.int(u16, 1); 129 try output.int(u16, 0); 130 try output.int(u16, 0); 131 try output.int(u64, offset); 132 try output.int(u64, data.len); 133 try output.int(u32, 0); 134 offset += data.len; 135 } 136 try output.raw(manifest.bytes.items); 137 try output.raw(node_bytes.bytes.items); 138 return output.bytes.toOwnedSlice(allocator); 139 } 140 141 pub fn digest(bytes: []const u8) [64]u8 { 142 var hash = std.crypto.hash.sha2.Sha256.init(.{}); 143 hash.update(domain ++ "\x00"); 144 hash.update(bytes); 145 var raw: [32]u8 = undefined; 146 hash.final(&raw); 147 return std.fmt.bytesToHex(raw, .lower); 148 } 149 150 const Reader = struct { 151 bytes: []const u8, 152 pos: usize = 0, 153 fn take(r: *Reader, n: usize) ![]const u8 { 154 if (n > r.bytes.len - r.pos) return error.InvalidData; 155 const data = r.bytes[r.pos..][0..n]; 156 r.pos += n; 157 return data; 158 } 159 fn int(r: *Reader, comptime T: type) !T { 160 return std.mem.readInt(T, (try r.take(@sizeOf(T)))[0..@sizeOf(T)], .big); 161 } 162 fn text(r: *Reader) ![]const u8 { 163 const data = try r.take(try r.int(u32)); 164 if (!std.unicode.utf8ValidateSlice(data)) return error.InvalidData; 165 return data; 166 } 167 fn expect(r: *Reader, data: []const u8) !void { 168 if (!std.mem.eql(u8, try r.take(data.len), data)) return error.InvalidData; 169 } 170 fn end(r: *Reader) !void { 171 if (r.pos != r.bytes.len) return error.InvalidData; 172 } 173 }; 174 fn section(bytes: []const u8, start: u64, len: u64) ![]const u8 { 175 if (start > bytes.len or len > bytes.len - start) return error.InvalidData; 176 return bytes[@intCast(start)..][0..@intCast(len)]; 177 } 178 179 /// General validated bundle reader, also shared by the C ABI. Single-tree IO 180 /// additionally requires exactly one root/export named "root". Like Haskell, 181 /// read accepts valid noncanonical layouts; only encode defines canonical bytes. 182 pub fn load(arena: *Arena, bytes: []const u8, name: ?[]const u8, single: bool) !u32 { 183 var header = Reader{ .bytes = bytes }; 184 try header.expect("ARBORICX"); 185 if (try header.int(u16) != 1) return error.InvalidData; 186 _ = try header.int(u16); 187 const count = try header.int(u32); 188 _ = try header.int(u64); 189 const start = try header.int(u64); 190 var directory = Reader{ .bytes = try section(bytes, start, @as(u64, count) * 32) }; 191 var manifest: ?[]const u8 = null; 192 var payload: ?[]const u8 = null; 193 for (0..count) |_| { 194 const kind = try directory.int(u32); 195 _ = try directory.int(u16); 196 const flags = try directory.int(u16); 197 const compression = try directory.int(u16); 198 _ = try directory.int(u16); 199 const offset = try directory.int(u64); 200 const len = try directory.int(u64); 201 _ = try directory.int(u32); 202 if (kind == 1 or kind == 2) { 203 if (compression != 0) return error.InvalidData; 204 const data = try section(bytes, offset, len); 205 if (kind == 1) { 206 if (manifest != null) return error.InvalidData; 207 manifest = data; 208 } else { 209 if (payload != null) return error.InvalidData; 210 payload = data; 211 } 212 } else if (flags & 1 != 0) return error.InvalidData; 213 } 214 var m = Reader{ .bytes = manifest orelse return error.InvalidData }; 215 try m.expect("ARBMNFST"); 216 if (try m.int(u16) != 1 or try m.int(u16) != 1) return error.InvalidData; 217 for (fields) |field| if (!std.mem.eql(u8, try m.text(), field)) return error.InvalidData; 218 if (try m.int(u32) != 0 or try m.int(u8) != 0) return error.InvalidData; 219 const root_count = try m.int(u32); 220 if (root_count == 0 or root_count > (m.bytes.len - m.pos) / 8 or (single and root_count != 1)) return error.InvalidData; 221 var max_root: u32 = 0; 222 var first: u32 = 0; 223 for (0..root_count) |i| { 224 const root = try m.int(u32); 225 _ = try m.text(); 226 if (i == 0) first = root; 227 max_root = @max(max_root, root); 228 } 229 const export_count = try m.int(u32); 230 if (export_count == 0 or export_count > (m.bytes.len - m.pos) / 16 or (single and export_count != 1)) return error.InvalidData; 231 var names = std.StringHashMap(void).init(arena.allocator); 232 defer names.deinit(); 233 var selected: ?u32 = if (name == null) first else null; 234 for (0..export_count) |_| { 235 const exported = try m.text(); 236 const root = try m.int(u32); 237 if (exported.len == 0 or names.contains(exported)) return error.InvalidData; 238 try names.put(exported, {}); 239 if (!std.mem.eql(u8, try m.text(), "term") or !std.mem.eql(u8, try m.text(), fields[8])) return error.InvalidData; 240 if (single and (!std.mem.eql(u8, exported, "root") or root != first)) return error.InvalidData; 241 if (name) |requested| { 242 if (std.mem.eql(u8, requested, exported)) selected = root; 243 } 244 max_root = @max(max_root, root); 245 } 246 var known_metadata: u8 = 0; 247 for (0..2) |group| { 248 const tlvs = try m.int(u32); 249 if (tlvs > (m.bytes.len - m.pos) / 6) return error.InvalidData; 250 for (0..tlvs) |_| { 251 const tag = try m.int(u16); 252 const value = try m.take(try m.int(u32)); 253 if (group == 0 and tag >= 1 and tag <= 5) { 254 const mask = @as(u8, 1) << @as(u3, @intCast(tag)); 255 if (known_metadata & mask == 0 and !std.unicode.utf8ValidateSlice(value)) return error.InvalidData; 256 known_metadata |= mask; 257 } 258 } 259 } 260 try m.end(); 261 var n = Reader{ .bytes = payload orelse return error.InvalidData }; 262 const node_count = try n.int(u64); 263 if (node_count == 0 or node_count > std.math.maxInt(u32) or node_count > (n.bytes.len - n.pos) / 5 or max_root >= node_count) return error.InvalidData; 264 const ids = try arena.allocator.alloc(u32, @intCast(node_count)); 265 defer arena.allocator.free(ids); 266 var keys = std.AutoHashMap(Key, void).init(arena.allocator); 267 defer keys.deinit(); 268 for (ids, 0..) |*id, i| { 269 const size = try n.int(u32); 270 const tag = try n.int(u8); 271 if (tag > 2 or size != 1 + 4 * @as(u32, tag)) return error.InvalidData; 272 var key = Key{ .tag = tag }; 273 if (tag >= 1) { 274 key.left = try n.int(u32); 275 if (key.left >= i) return error.InvalidData; 276 } 277 if (tag == 2) { 278 key.right = try n.int(u32); 279 if (key.right >= i) return error.InvalidData; 280 } 281 if (keys.contains(key)) return error.InvalidData; 282 try keys.put(key, {}); 283 id.* = try arena.alloc(switch (tag) { 284 0 => .leaf, 285 1 => .{ .stem = .{ .child = ids[key.left] } }, 286 2 => .{ .fork = .{ .left = ids[key.left], .right = ids[key.right] } }, 287 else => unreachable, 288 }); 289 } 290 try n.end(); 291 return ids[selected orelse return error.ExportNotFound]; 292 } 293 294 test "canonical leaf matches independent writer profile and domain digest" { 295 var arena = Arena.init(std.testing.allocator); 296 defer arena.deinit(); 297 const bytes = try encode(&arena, try arena.alloc(.leaf)); 298 defer arena.allocator.free(bytes); 299 try std.testing.expectEqual(@as(usize, 431), bytes.len); 300 // Independently assembled by test/executable_object.py's wire profile. 301 try std.testing.expectEqualStrings("6f93378feaa8bf5ab7cefc071175a654c871bfd53f165d7d96795fb2b38483f1", &digest(bytes)); 302 const decoded = try load(&arena, bytes, "root", true); 303 try std.testing.expect(arena.get(decoded).* == .leaf); 304 } 305 306 test "physical sharing is only an acceleration hint, and lazy children are serialized" { 307 var arena = Arena.init(std.testing.allocator); 308 defer arena.deinit(); 309 const leaf = try arena.alloc(.leaf); 310 const child = try arena.alloc(.{ .stem = .{ .child = leaf } }); 311 const shared = try arena.alloc(.{ .fork = .{ .left = child, .right = child } }); 312 const other_leaf = try arena.alloc(.leaf); 313 const other_child = try arena.alloc(.{ .stem = .{ .child = other_leaf } }); 314 const constant = try arena.alloc(.{ .fork = .{ .left = other_leaf, .right = other_child } }); 315 const delayed = try arena.alloc(.{ .app = .{ .func = constant, .arg = other_leaf } }); 316 const copied = try arena.alloc(.{ .fork = .{ .left = child, .right = delayed } }); 317 const a = try encode(&arena, shared); 318 defer arena.allocator.free(a); 319 arena.gc_enabled = true; 320 try arena.setGcPolicy(1, 1); 321 const b = try encode(&arena, copied); 322 defer arena.allocator.free(b); 323 try std.testing.expectEqualSlices(u8, a, b); 324 try std.testing.expectEqual(@as(usize, 0), arena.roots.items.len); 325 const decoded = try load(&arena, a, "root", true); 326 try std.testing.expectEqual(arena.get(decoded).fork.left, arena.get(decoded).fork.right); 327 } 328 329 test "deep exponentially expanded trees use iterative DAG traversal" { 330 var arena = Arena.init(std.testing.allocator); 331 defer arena.deinit(); 332 var root = try arena.alloc(.leaf); 333 for (0..100000) |_| root = try arena.alloc(.{ .fork = .{ .left = root, .right = root } }); 334 const bytes = try encode(&arena, root); 335 defer arena.allocator.free(bytes); 336 try std.testing.expectEqual(@as(usize, 431 + 13 * 100000), bytes.len); 337 const copied = try load(&arena, bytes, "root", true); 338 const again = try encode(&arena, copied); 339 defer arena.allocator.free(again); 340 try std.testing.expectEqualSlices(u8, bytes, again); 341 } 342 343 test "bundle parser rejects every truncated prefix and safely handles byte mutations" { 344 var arena = Arena.init(std.testing.allocator); 345 defer arena.deinit(); 346 const bytes = try encode(&arena, try arena.alloc(.leaf)); 347 defer arena.allocator.free(bytes); 348 for (0..bytes.len) |len| try std.testing.expectError(error.InvalidData, load(&arena, bytes[0..len], "root", true)); 349 for (bytes) |*byte| { 350 byte.* ^= 0xff; 351 _ = load(&arena, bytes, "root", true) catch |err| switch (err) { 352 error.InvalidData, error.ExportNotFound => 0, 353 else => return err, 354 }; 355 byte.* ^= 0xff; 356 } 357 // Section count, offset and size arithmetic must not overflow or slice 358 // outside input, even when the supplied bytes themselves are authenticated. 359 for ([_]usize{ 24, 44, 52, 76, 84 }) |offset| { 360 const old = std.mem.readInt(u64, bytes[offset..][0..8], .big); 361 std.mem.writeInt(u64, bytes[offset..][0..8], std.math.maxInt(u64), .big); 362 try std.testing.expectError(error.InvalidData, load(&arena, bytes, "root", true)); 363 std.mem.writeInt(u64, bytes[offset..][0..8], old, .big); 364 } 365 } 366 367 fn allocationProbe(allocator: std.mem.Allocator) !void { 368 var arena = Arena.init(allocator); 369 defer arena.deinit(); 370 const leaf = try arena.alloc(.leaf); 371 const root = try arena.alloc(.{ .fork = .{ .left = leaf, .right = leaf } }); 372 const bytes = try encode(&arena, root); 373 defer allocator.free(bytes); 374 _ = try load(&arena, bytes, "root", true); 375 } 376 377 test "indexed codec allocation failures unwind all scratch storage" { 378 try std.testing.checkAllAllocationFailures(std.testing.allocator, allocationProbe, .{}); 379 } 380 381 test "reader rejects duplicate constructors, forward edges and mismatched single roots" { 382 var arena = Arena.init(std.testing.allocator); 383 defer arena.deinit(); 384 const leaf = try arena.alloc(.leaf); 385 const root = try arena.alloc(.{ .stem = .{ .child = leaf } }); 386 const bytes = try encode(&arena, root); 387 defer arena.allocator.free(bytes); 388 const node_offset: usize = @intCast(std.mem.readInt(u64, bytes[76..84], .big)); 389 const child_offset = node_offset + 8 + 5 + 5; 390 std.mem.writeInt(u32, bytes[child_offset..][0..4], 1, .big); 391 try std.testing.expectError(error.InvalidData, load(&arena, bytes, "root", true)); 392 std.mem.writeInt(u32, bytes[child_offset..][0..4], 0, .big); 393 // Valid general bundle with unequal root/export indices is not a valid 394 // name-neutral single-tree object, even when both indices are in bounds. 395 const export_offset = std.mem.indexOf(u8, bytes, "root").? + 4; 396 std.mem.writeInt(u32, bytes[export_offset..][0..4], 0, .big); 397 try std.testing.expectError(error.InvalidData, load(&arena, bytes, "root", true)); 398 _ = try load(&arena, bytes, "root", false); 399 const one = try encode(&arena, leaf); 400 defer arena.allocator.free(one); 401 const duplicate = try arena.allocator.alloc(u8, one.len + 5); 402 defer arena.allocator.free(duplicate); 403 @memcpy(duplicate[0..one.len], one); 404 @memcpy(duplicate[one.len..], "\x00\x00\x00\x01\x00"); 405 std.mem.writeInt(u64, duplicate[84..92], 18, .big); 406 std.mem.writeInt(u64, duplicate[node_offset..][0..8], 2, .big); 407 try std.testing.expectError(error.InvalidData, load(&arena, duplicate, "root", true)); 408 }