arboricx-bundle-format.md (14924B)

Arboricx Portable Bundle Format Specification

Container: 1.0. Manifest: 1.1. Indexed nodes.

The Arboricx Portable Bundle is a self-contained binary format for distributing Tree Calculus programs. Nodes are identified by their positions in a topologically ordered array. Pure Tree Calculus programs can write bundles, and readers verify them through structural inspection.

Design Principles
Top-Level Container Layout
Header
Section Directory
Section: Manifest (type 1)
Section: Nodes (type 2)
Node Payload Format
Tree Calculus Reduction Semantics
Binary Primitives
Bundle Verification
Canonicalization
Known Section Types

1. Design Principles

Indexed nodes. Each node is identified by its array position; child references point to earlier entries.
Self-contained. A bundle includes all nodes reachable from its exports.
Deterministic. Canonical writers produce identical bytes for identical ordered named roots and metadata.
Compact. Leaf, Stem, and Fork records occupy 5, 9, and 13 bytes, respectively, including their length prefix.
Structurally verifiable. Readers check record layouts, reference bounds, and acyclicity.

Distribution systems establish artifact identity and integrity using a digest of the complete canonical bundle file. Registries, lockfiles, and content-addressed caches use this file-level identity.

2. Top-Level Container Layout

+------------------+------------------+------------------+------------------+
| Header           | Section Directory| Manifest Section | Nodes Section    |
| (32 bytes)       | (N × 32 bytes)   | (variable)       | (variable)       |
+------------------+------------------+------------------+------------------+

Total bundle size = 32 + (sectionCount × 32) + manifestSize + nodesSize

All multi-byte integers use big-endian byte order.

3. Header

Offset	Size	Field	Description
0	8 bytes	Magic	ASCII `"ARBORICX"`
8	2 bytes	Major version	`u16` BE. Currently `1`
10	2 bytes	Minor version	`u16` BE. Currently `0`
12	4 bytes	Section count	`u32` BE. Number of entries in the section directory
16	8 bytes	Flags	`u64` BE. Reserved; currently all zeros
24	8 bytes	Directory offset	`u64` BE. Byte offset to the section directory (always `32`)

4. Section Directory

Array of N entries, each exactly 32 bytes.

Offset (within entry)	Size	Field	Description
0	4 bytes	Type	`u32` BE. Section type identifier
4	2 bytes	Version	`u16` BE. Section-specific version
6	2 bytes	Flags	`u16` BE. Bit 0 (`0x0001`) = critical section
8	2 bytes	Compression	`u16` BE. `0` = none (currently the only value)
10	2 bytes	Reserved	`u16` BE. Padding; must be zero
12	8 bytes	Offset	`u64` BE. Byte offset from bundle start to section data
20	8 bytes	Length	`u64` BE. Length of section data in bytes
28	4 bytes	Reserved	Padding; must be zero

Verification:

Unknown critical sections are rejected.
Compression must be 0 (none).
Reserved fields must be zero.

5. Section: Manifest (type 1)

Binary encoding of bundle metadata. Fixed-order core layout followed by optional TLV tail.

Manifest =
  magic            8 bytes    "ARBMNFST"
  major            u16 BE     Manifest major version (1)
  minor            u16 BE     Manifest minor version (1)

  schema           string     "arboricx.bundle.manifest.v1"
  bundleType       string     "tree-calculus-executable-object"

  treeCalculus     string     "tree-calculus.v1"
  treeHashAlgorithm string    "indexed"
  treeHashDomain   string     "arboricx.indexed.node.v1"
  treeNodePayload  string     "arboricx.indexed.payload.v1"

  runtimeSemantics string     "tree-calculus.v1"
  runtimeEvaluation string    "normal-order"
  runtimeAbi       string     "arboricx.abi.tree.v1"
  capabilityCount  u32 BE     Number of capability strings (currently 0)
  capabilities     string[]   Array of length-prefixed UTF-8 strings

  closure          u8         0 = complete
  rootCount        u32 BE     Number of root entries
  roots            Root[]     Array of root entries
  exportCount      u32 BE     Number of export entries
  exports          Export[]   Array of export entries

  metadataFieldCount u32 BE   Number of metadata TLV entries
  metadataFields   TLV[]      Metadata tag-value entries
  extensionFieldCount u32 BE  Number of extension TLV entries (currently 0)
  extensionFields  TLV[]      Extension entries (skipped by parsers)

String Format

string =
  length      u32 BE    Number of UTF-8 bytes
  bytes       byte[length]  UTF-8 content

Root Entry

Root =
  index       u32 BE     Node index into the nodes section
  role        string     Length-prefixed UTF-8 ("default" for first root, "root" for others)

Export Entry

Export =
  name        string     Length-prefixed UTF-8 export identifier
  root        u32 BE     Node index into the nodes section
  kind        string     Length-prefixed UTF-8 (currently "term")
  abi         string     Length-prefixed UTF-8 ABI string

TLV Entry

TLV =
  tag         u16 BE     Tag identifier
  length      u32 BE     Value length in bytes
  value       byte[length]

Metadata Tags

Tag	Name	Value
1	package	UTF-8 text
2	version	UTF-8 text
3	description	UTF-8 text
4	license	UTF-8 text
5	createdBy	UTF-8 text

Unknown metadata tags are ignored. Unknown extension tags are skipped by length.

Semantic Constraints

Constraint	Value
`schema`	`"arboricx.bundle.manifest.v1"`
`bundleType`	`"tree-calculus-executable-object"`
`treeCalculus`	`"tree-calculus.v1"`
`treeHashAlgorithm`	`"indexed"`
`treeHashDomain`	`"arboricx.indexed.node.v1"`
`treeNodePayload`	`"arboricx.indexed.payload.v1"`
`runtimeSemantics`	`"tree-calculus.v1"`
`runtimeEvaluation`	`"normal-order"`
`runtimeCapabilities`	Empty
Export names	Unique and nonempty
Export kind / ABI	`"term"` / `"arboricx.abi.tree.v1"`
`runtimeAbi`	`"arboricx.abi.tree.v1"`
`closure`	`0` (complete)
`rootCount`	At least 1
`exportCount`	At least 1

6. Section: Nodes (type 2)

NodesSection =
  nodeCount     u64 BE    Total number of node entries
  entries       NodeEntry[]

Node Entry

NodeEntry =
  payloadLen    u32 BE    Length of payload in bytes
  payload       byte[payloadLen]

Each node’s zero-based position in entries is its identity.

7. Node Payload Format

Child references are u32 big-endian indices into the node array. The array must be topologically sorted: every child index must be strictly less than the entry's own position.

Leaf

Payload = 0x00

Exactly 1 byte.

Stem

Payload = 0x01 || child_index (u32 BE)

Exactly 5 bytes.

Fork

Payload = 0x02 || left_index (u32 BE) || right_index (u32 BE)

Exactly 9 bytes.

8. Tree Calculus Reduction Semantics

The bundle represents a Tree Calculus term. The reduction rules are:

The t operator is left associative.
1.  t  t      a b       -> a
2.  t (t a)   b c       -> a c (b c)
3a. t (t a b) c t       -> a
3b. t (t a b) c (t u)   -> b u
3c. t (t a b) c (t u v) -> c u v

Closure: The bundle declares closure = 0 (complete), meaning all nodes reachable from export roots are present in the nodes section.

9. Binary Primitives

u8

Single byte, value 0-255.

u16 (2 bytes)

value = (byte[0] << 8) | byte[1]

u32 (4 bytes)

value = (byte[0] << 24) | (byte[1] << 16) | (byte[2] << 8) | byte[3]

u64 (8 bytes)

value = (byte[0] << 56) | ... | byte[7]

10. Bundle Verification

Magic check: First 8 bytes must be "ARBORICX".
Version check: Major version must be 1.
Section directory: Parse all entries; reject unknown critical sections. Verify reserved fields are zero.
Manifest parsing: Decode fixed-order manifest; validate semantic constraints.
Nodes section: Parse all entries.
Bounds checking:
- Every root index < nodeCount
- Every export index < nodeCount
- In every Stem payload, child_index < entry_position and child_index < nodeCount
- In every Fork payload, both indices < entry_position and < nodeCount
Acyclicity: Guaranteed by the child < parent rule above.
Closure: Traverse from all root/export indices; confirm every reached index is valid.

11. Canonicalization

A bundle is canonical iff:

Maximal deduplication. Each structurally distinct subtree has exactly one entry.
Topological order. Children precede parents.
Deterministic post-order traversal. Nodes are emitted in the order discovered by a left-to-right recursive post-order walk.
Exact section lengths. Each section ends immediately after its encoded content.
Reserved fields are zero.

Canonical writers produce identical bytes for identical ordered named roots and metadata.

12. Known Section Types

Type	Name	Required	Version	Description
1	Manifest	Yes	1	Bundle metadata
2	Nodes	Yes	1	Topological DAG node entries

Unknown section types are permitted if not marked critical.

Appendix A: Complete Example Layout

For Stem(Leaf) (t t), use two nodes: Leaf at index 0 and Stem(0) at index 1. With one manifest and one node section, the directory occupies 64 bytes and payloads start at offset 96. If the encoded manifest is M bytes, nodes start at 96 + M, and the complete canonical file is 118 + M bytes.

The node section is 22 bytes:

nodeCount: u64(2)                         8 bytes
Leaf:      u32(1), 00                     5 bytes
Stem(0):   u32(5), 01, u32(0)             9 bytes

Appendix B: File Extension

Bundles use the .arboricx file extension. Plain source files use .tri.

Portable library reader profile

lib/binary.tri and lib/arboricx/ implement the following reader profile. Focused tests exercise complete replies and error precedence. Reader profiles differ at the container boundary.

Binary input is a proper list of canonical octets. Prefix reads validate only consumed cells; a zero-length read returns its input unchanged and uninspected. Exact reads and expectations roll failures back to the start of that operation. Counted record parsers propagate the failing field's remainder. orParser deliberately retries the original input after failure, including a failure that consumed input.
Container boundaries validate the complete byte-list shape, header 1.0, zero header flags and directory offset 32. Section version 1, flags 0/1, compression value 0 and zero reserved fields are supported. Unknown critical sections, duplicate IDs, ranges before the directory, out-of-bounds ranges, and overlapping nonempty sections are rejected. Unknown noncritical version-1 sections are allowed, but still receive range/profile checks.
readManifest is a prefix parser returning the actual suffix. Its value is pair core (pair metadata extensions), retaining both TLV lists. readManifestComplete rejects a suffix. Manifest version 1.1, UTF-8 core strings/roles/export fields, the supported semantics/evaluation/ABI, empty capabilities, complete closure, nonempty roots and unique nonempty export names are enforced at their appropriate parsing or bundle-validation boundaries. Every export must declare term and the tree ABI. Known metadata text tags require UTF-8; unknown metadata/extension values remain opaque. Text retains its encoded Unicode form and is treated as manifest data.
Nodes require exact payload lengths, canonical octets, strictly backward child indices and unique payloads. All records, advertised roots, and exports are validated before choosing an executable, including unselected ones. Payload errors retain precedence over edge/duplicate checks. Reconstruction uses a persistent bit-indexed table.
readArboricxBundle validates both required sections; executable selection reuses the parsed sections. Container remainders are bytes after the directory. Sections are accessed by their advertised offsets and lengths; section-level suffix checks apply within those ranges. Bytes outside those ranges are permitted.

Additional numeric error codes: invalid binary input 15, invalid count 16, unsupported section profile 17, invalid section range 18. Manifest magic/version/ trailing-data errors use 10/11/12; unsupported manifest contracts use 13. Existing missing/duplicate node errors remain 9/7. eof? on nonempty input reports unexpected bytes (2).

Validation is in memory. Directory overlap and export-name checks are quadratic in their small lists. Counted parsers and logical-tree observation still need caller-selected resource limits, including for structurally valid inputs.

Host reader profiles

The Haskell decodeBundle / verifyBundle path validates required sections, manifest execution semantics and export ABIs, roots, backward edges, and duplicate nodes/exports. Its container decoder accepts a broader header/directory profile, with weaker constraints on minor version, header flags, section versions/reserved fields, and general section overlap than the portable reader above. Decode and semantic verification are separate API calls; CLI loading uses both.

The browser reader uses strict header/directory checks, contiguous sections, whole-file SHA-256 verification, and explicit byte/node/count limits. Its package and compiler download profiles are documented in the playground guide.

Canonical writers emit the format described here. Reordered roots/exports or changed metadata affect file identity; canonicalization is deterministic for an ordered named export set and metadata. Programs with equal application results can have distinct representations and bundle identities. Distribution authentication and execution permissions are separate from structural parsing.

tricu