executable_object.py (3623B)
1 """Independent complete-object audits for flat and canonical indexed producers. 2 3 This is the canonical native writer profile, not the broader host bundle reader. 4 No evaluator, executable expansion, or host codec is used. 5 """ 6 import struct 7 8 FLAT = 'arboricx.tree-term.v1' 9 INDEXED = 'arboricx.indexed-tree.v1' 10 KINDS = (FLAT, INDEXED) 11 12 13 def text(value): 14 data = value.encode('utf-8') 15 return struct.pack('>I', len(data)) + data 16 17 18 def indexed_manifest(root): 19 fields = ['arboricx.bundle.manifest.v1', 'tree-calculus-executable-object', 20 'tree-calculus.v1', 'indexed', 'arboricx.indexed.node.v1', 21 'arboricx.indexed.payload.v1', 'tree-calculus.v1', 'normal-order', 22 'arboricx.abi.tree.v1'] 23 return (b'ARBMNFST' + struct.pack('>HH', 1, 1) + b''.join(map(text, fields)) 24 + struct.pack('>IBII', 0, 0, 1, root) + text('default') 25 + struct.pack('>I', 1) + text('root') + struct.pack('>I', root) 26 + text('term') + text('arboricx.abi.tree.v1') 27 + struct.pack('>IH', 1, 5) + text('arboricx') + struct.pack('>I', 0)) 28 29 30 def verify_payload(kind, payload): 31 if kind == FLAT: 32 slots = 1 33 for tag in payload: 34 assert slots > 0 and tag <= 2, 'invalid flat tree' 35 slots += tag - 1 36 assert slots == 0, 'truncated flat tree' 37 return 38 assert kind == INDEXED, 'unsupported executable kind' 39 assert len(payload) >= 96 and payload[:8] == b'ARBORICX', 'invalid indexed header' 40 assert struct.unpack_from('>HHIQQ', payload, 8) == (1, 0, 2, 0, 32) 41 sections, end = {}, 96 42 for at, expected_id in [(32, 1), (64, 2)]: 43 identity, major, minor, flags, offset, size, reserved = struct.unpack_from('>IHHIQQI', payload, at) 44 assert (identity, major, minor, flags, reserved) == (expected_id, 1, 1, 0, 0) 45 assert offset == end and offset + size <= len(payload), 'noncanonical section layout' 46 end = offset + size 47 sections[identity] = payload[offset:end] 48 assert end == len(payload), 'trailing indexed bytes' 49 raw = sections[2] 50 assert len(raw) >= 8, 'missing indexed nodes' 51 count = struct.unpack_from('>Q', raw)[0] 52 assert 0 < count <= (len(raw) - 8) // 5, 'invalid node count' 53 nodes, keys, offset = [], set(), 8 54 for index in range(count): 55 assert offset + 4 <= len(raw), 'truncated node length' 56 size = struct.unpack_from('>I', raw, offset)[0] 57 offset += 4 58 assert size and offset + size <= len(raw), 'truncated node' 59 tag = raw[offset] 60 assert tag in (0, 1, 2) and size == 1 + 4 * tag, 'invalid node payload' 61 children = struct.unpack_from('>' + 'I' * tag, raw, offset + 1) 62 assert all(child < index for child in children), 'non-backward edge' 63 node = (tag, *children) 64 assert node not in keys, 'duplicate node' 65 nodes.append(node) 66 keys.add(node) 67 offset += size 68 assert offset == len(raw), 'trailing node bytes' 69 assert sections[1] == indexed_manifest(count - 1), 'noncanonical indexed manifest' 70 # Exact first-occurrence postorder and reachability, without expanding DAGs. 71 visited, order, todo = set(), [], [(count - 1, False)] 72 while todo: 73 index, finish = todo.pop() 74 if index in visited: 75 continue 76 if finish: 77 visited.add(index) 78 order.append(index) 79 else: 80 todo.append((index, True)) 81 todo.extend((child, False) for child in reversed(nodes[index][1:])) 82 assert order == list(range(count)), 'noncanonical traversal or unreachable nodes'