bundle.zig (12469B)
1 const std = @import("std"); 2 const tree = @import("tree.zig"); 3 const Arena = @import("arena.zig").Arena; 4 5 pub const Error = error{ 6 InvalidMagic, 7 InvalidVersion, 8 Truncated, 9 InvalidManifest, 10 InvalidNodePayload, 11 ExportNotFound, 12 MissingChild, 13 UnexpectedFormat, 14 OutOfMemory, 15 }; 16 17 const Parser = struct { 18 bytes: []const u8, 19 pos: usize, 20 21 fn init(bytes: []const u8) Parser { 22 return .{ .bytes = bytes, .pos = 0 }; 23 } 24 25 fn remaining(self: *const Parser) usize { 26 return self.bytes.len - self.pos; 27 } 28 29 fn expect(self: *Parser, n: usize) Error![]const u8 { 30 if (self.remaining() < n) return error.Truncated; 31 const result = self.bytes[self.pos .. self.pos + n]; 32 self.pos += n; 33 return result; 34 } 35 36 fn readU8(self: *Parser) Error!u8 { 37 const b = try self.expect(1); 38 return b[0]; 39 } 40 41 fn readU16(self: *Parser) Error!u16 { 42 const b = try self.expect(2); 43 return std.mem.readInt(u16, b[0..2], .big); 44 } 45 46 fn readU32(self: *Parser) Error!u32 { 47 const b = try self.expect(4); 48 return std.mem.readInt(u32, b[0..4], .big); 49 } 50 51 fn readU64(self: *Parser) Error!u64 { 52 const b = try self.expect(8); 53 return std.mem.readInt(u64, b[0..8], .big); 54 } 55 56 fn readLengthPrefixedBytes(self: *Parser, allocator: std.mem.Allocator) Error![]const u8 { 57 const len = try self.readU32(); 58 const bytes = try self.expect(len); 59 const copy = try allocator.alloc(u8, bytes.len); 60 @memcpy(copy, bytes); 61 return copy; 62 } 63 }; 64 65 const SectionEntry = struct { 66 section_type: u32, 67 offset: u64, 68 length: u64, 69 }; 70 71 fn parseHeader(p: *Parser) Error!struct { major: u16, minor: u16, section_count: u32, dir_offset: u64 } { 72 const magic = try p.expect(8); 73 if (!std.mem.eql(u8, magic, "ARBORICX")) return error.InvalidMagic; 74 75 const major = try p.readU16(); 76 const minor = try p.readU16(); 77 const section_count = try p.readU32(); 78 _ = try p.readU64(); // flags 79 const dir_offset = try p.readU64(); 80 81 if (major != 1) return error.InvalidVersion; 82 83 return .{ .major = major, .minor = minor, .section_count = section_count, .dir_offset = dir_offset }; 84 } 85 86 fn parseSectionEntries(p: *Parser, count: u32, allocator: std.mem.Allocator) Error![]SectionEntry { 87 const entries = try allocator.alloc(SectionEntry, count); 88 errdefer allocator.free(entries); 89 90 for (entries) |*entry| { 91 entry.section_type = try p.readU32(); 92 _ = try p.readU16(); // section_version 93 _ = try p.readU16(); // section_flags 94 const compression = try p.readU16(); 95 _ = try p.readU16(); // reserved (was digest_alg) 96 entry.offset = try p.readU64(); 97 entry.length = try p.readU64(); 98 _ = try p.readU32(); // reserved padding 99 100 if (compression != 0) return error.UnexpectedFormat; 101 } 102 return entries; 103 } 104 105 fn parseManifest(p: *Parser, allocator: std.mem.Allocator) Error!struct { exports: []Export, roots: []Root } { 106 const magic = try p.expect(8); 107 if (!std.mem.eql(u8, magic, "ARBMNFST")) return error.InvalidManifest; 108 109 const major = try p.readU16(); 110 _ = try p.readU16(); // minor 111 if (major != 1) return error.InvalidVersion; 112 113 const schema = try p.readLengthPrefixedBytes(allocator); 114 defer allocator.free(schema); 115 if (!std.mem.eql(u8, schema, "arboricx.bundle.manifest.v1")) return error.UnexpectedFormat; 116 117 const bundle_type = try p.readLengthPrefixedBytes(allocator); 118 defer allocator.free(bundle_type); 119 if (!std.mem.eql(u8, bundle_type, "tree-calculus-executable-object")) return error.UnexpectedFormat; 120 121 const calc = try p.readLengthPrefixedBytes(allocator); 122 defer allocator.free(calc); 123 if (!std.mem.eql(u8, calc, "tree-calculus.v1")) return error.UnexpectedFormat; 124 125 const hash_alg = try p.readLengthPrefixedBytes(allocator); 126 defer allocator.free(hash_alg); 127 if (!std.mem.eql(u8, hash_alg, "indexed")) return error.UnexpectedFormat; 128 129 const hash_domain = try p.readLengthPrefixedBytes(allocator); 130 defer allocator.free(hash_domain); 131 if (!std.mem.eql(u8, hash_domain, "arboricx.indexed.node.v1")) return error.UnexpectedFormat; 132 133 const payload_type = try p.readLengthPrefixedBytes(allocator); 134 defer allocator.free(payload_type); 135 if (!std.mem.eql(u8, payload_type, "arboricx.indexed.payload.v1")) return error.UnexpectedFormat; 136 137 const sem = try p.readLengthPrefixedBytes(allocator); 138 defer allocator.free(sem); 139 if (!std.mem.eql(u8, sem, "tree-calculus.v1")) return error.UnexpectedFormat; 140 141 const eval_mode = try p.readLengthPrefixedBytes(allocator); 142 defer allocator.free(eval_mode); 143 if (!std.mem.eql(u8, eval_mode, "normal-order")) return error.UnexpectedFormat; 144 145 const abi = try p.readLengthPrefixedBytes(allocator); 146 defer allocator.free(abi); 147 if (!std.mem.eql(u8, abi, "arboricx.abi.tree.v1")) return error.UnexpectedFormat; 148 149 const cap_count = try p.readU32(); 150 var i: u32 = 0; 151 while (i < cap_count) : (i += 1) { 152 const cap = try p.readLengthPrefixedBytes(allocator); 153 defer allocator.free(cap); 154 if (cap.len != 0) return error.UnexpectedFormat; 155 } 156 157 const closure = try p.readU8(); 158 if (closure != 0) return error.UnexpectedFormat; 159 160 const root_count = try p.readU32(); 161 const roots = try allocator.alloc(Root, root_count); 162 errdefer allocator.free(roots); 163 for (roots) |*r| { 164 r.index = try p.readU32(); 165 r.role = try p.readLengthPrefixedBytes(allocator); 166 } 167 168 const export_count = try p.readU32(); 169 const exports = try allocator.alloc(Export, export_count); 170 errdefer { 171 for (exports) |*e| { 172 allocator.free(e.name); 173 allocator.free(e.kind); 174 allocator.free(e.abi); 175 } 176 allocator.free(exports); 177 } 178 for (exports) |*e| { 179 e.name = try p.readLengthPrefixedBytes(allocator); 180 e.root = try p.readU32(); 181 e.kind = try p.readLengthPrefixedBytes(allocator); 182 e.abi = try p.readLengthPrefixedBytes(allocator); 183 if (!std.mem.eql(u8, e.abi, "arboricx.abi.tree.v1")) return error.UnexpectedFormat; 184 } 185 186 const metadata_count = try p.readU32(); 187 var m: u32 = 0; 188 while (m < metadata_count) : (m += 1) { 189 _ = try p.readU16(); // tag 190 const len = try p.readU32(); 191 _ = try p.expect(len); 192 } 193 194 const ext_count = try p.readU32(); 195 var e_idx: u32 = 0; 196 while (e_idx < ext_count) : (e_idx += 1) { 197 _ = try p.readU16(); // tag 198 const len = try p.readU32(); 199 _ = try p.expect(len); 200 } 201 202 return .{ .exports = exports, .roots = roots }; 203 } 204 205 const Export = struct { 206 name: []const u8, 207 root: u32, 208 kind: []const u8, 209 abi: []const u8, 210 }; 211 212 const Root = struct { 213 index: u32, 214 role: []const u8, 215 }; 216 217 /// Parse the node section and build nodes directly into the arena. 218 /// Returns a slice mapping node-section index -> arena index. 219 /// The caller owns the returned slice and must free it with the arena's allocator. 220 fn parseNodeSection(p: *Parser, arena: *Arena) Error![]u32 { 221 const node_count = try p.readU64(); 222 const indices = try arena.allocator.alloc(u32, node_count); 223 errdefer arena.allocator.free(indices); 224 225 var i: u64 = 0; 226 while (i < node_count) : (i += 1) { 227 const plen = try p.readU32(); 228 const payload = try p.expect(plen); 229 230 if (payload.len == 0) return error.InvalidNodePayload; 231 232 const idx: u32 = switch (payload[0]) { 233 0x00 => blk: { 234 if (plen != 1) return error.InvalidNodePayload; 235 break :blk try arena.alloc(.leaf); 236 }, 237 0x01 => blk: { 238 if (plen != 5) return error.InvalidNodePayload; 239 const child_idx = std.mem.readInt(u32, payload[1..5], .big); 240 if (child_idx >= i) return error.InvalidNodePayload; 241 break :blk try arena.alloc(.{ .stem = .{ .child = indices[child_idx] } }); 242 }, 243 0x02 => blk: { 244 if (plen != 9) return error.InvalidNodePayload; 245 const left_idx = std.mem.readInt(u32, payload[1..5], .big); 246 const right_idx = std.mem.readInt(u32, payload[5..9], .big); 247 if (left_idx >= i or right_idx >= i) return error.InvalidNodePayload; 248 break :blk try arena.alloc(.{ .fork = .{ .left = indices[left_idx], .right = indices[right_idx] } }); 249 }, 250 else => return error.InvalidNodePayload, 251 }; 252 indices[i] = idx; 253 } 254 255 return indices; 256 } 257 258 fn findSection(entries: []SectionEntry, section_type: u32) ?SectionEntry { 259 for (entries) |entry| { 260 if (entry.section_type == section_type) return entry; 261 } 262 return null; 263 } 264 265 /// Parse an Arboricx bundle and load the named export into the arena. 266 /// Returns the arena index of the exported term tree. 267 pub fn loadBundleExport( 268 arena: *Arena, 269 bundle_bytes: []const u8, 270 export_name: []const u8, 271 ) Error!u32 { 272 var p = Parser.init(bundle_bytes); 273 274 const header = try parseHeader(&p); 275 276 p.pos = @intCast(header.dir_offset); 277 const allocator = arena.allocator; 278 const entries = try parseSectionEntries(&p, header.section_count, allocator); 279 defer allocator.free(entries); 280 281 const manifest_section = findSection(entries, 1) orelse return error.InvalidManifest; 282 const nodes_section = findSection(entries, 2) orelse return error.InvalidNodePayload; 283 284 const manifest_bytes = bundle_bytes[@intCast(manifest_section.offset)..@intCast(manifest_section.offset + manifest_section.length)]; 285 const nodes_bytes = bundle_bytes[@intCast(nodes_section.offset)..@intCast(nodes_section.offset + nodes_section.length)]; 286 287 var mp = Parser.init(manifest_bytes); 288 const manifest = try parseManifest(&mp, allocator); 289 defer { 290 for (manifest.exports) |e| { 291 allocator.free(e.name); 292 allocator.free(e.kind); 293 allocator.free(e.abi); 294 } 295 allocator.free(manifest.exports); 296 for (manifest.roots) |r| { 297 allocator.free(r.role); 298 } 299 allocator.free(manifest.roots); 300 } 301 302 var export_root: ?u32 = null; 303 for (manifest.exports) |e| { 304 if (std.mem.eql(u8, e.name, export_name)) { 305 export_root = e.root; 306 break; 307 } 308 } 309 const root_index = export_root orelse return error.ExportNotFound; 310 311 var np = Parser.init(nodes_bytes); 312 const node_indices = try parseNodeSection(&np, arena); 313 defer allocator.free(node_indices); 314 315 if (root_index >= node_indices.len) return error.InvalidNodePayload; 316 return node_indices[root_index]; 317 } 318 319 /// Parse an Arboricx bundle and load the default (first) root into the arena. 320 pub fn loadBundleDefaultRoot( 321 arena: *Arena, 322 bundle_bytes: []const u8, 323 ) Error!u32 { 324 var p = Parser.init(bundle_bytes); 325 326 const header = try parseHeader(&p); 327 328 p.pos = @intCast(header.dir_offset); 329 const allocator = arena.allocator; 330 const entries = try parseSectionEntries(&p, header.section_count, allocator); 331 defer allocator.free(entries); 332 333 const manifest_section = findSection(entries, 1) orelse return error.InvalidManifest; 334 const nodes_section = findSection(entries, 2) orelse return error.InvalidNodePayload; 335 336 const manifest_bytes = bundle_bytes[@intCast(manifest_section.offset)..@intCast(manifest_section.offset + manifest_section.length)]; 337 const nodes_bytes = bundle_bytes[@intCast(nodes_section.offset)..@intCast(nodes_section.offset + nodes_section.length)]; 338 339 var mp = Parser.init(manifest_bytes); 340 const manifest = try parseManifest(&mp, allocator); 341 defer { 342 for (manifest.exports) |e| { 343 allocator.free(e.name); 344 allocator.free(e.kind); 345 allocator.free(e.abi); 346 } 347 allocator.free(manifest.exports); 348 for (manifest.roots) |r| { 349 allocator.free(r.role); 350 } 351 allocator.free(manifest.roots); 352 } 353 354 if (manifest.roots.len == 0) return error.ExportNotFound; 355 const root_index = manifest.roots[0].index; 356 357 var np = Parser.init(nodes_bytes); 358 const node_indices = try parseNodeSection(&np, arena); 359 defer allocator.free(node_indices); 360 361 if (root_index >= node_indices.len) return error.InvalidNodePayload; 362 return node_indices[root_index]; 363 }