Identity

Lossless vs strict canonical (recap)

Two canonical forms (see canonical-strict + canonical-lossless in surfaces for the surface-level treatment):

• **Lossless canonical (`cx fmt`)** — preserves comments, anchors, aliases, presentation. Idempotent. Used for source-file formatting and diff stability.
• **Strict canonical (`cx canonical` / `cx hash`)** — strips comments, expands anchors and aliases, normalizes date offsets, sorts attributes lexicographically. Two docs with the same data hash identically. Used for content addressing.

**The hash is taken over strict canonical bytes**, not over lossless. This means `[user email='a' #ada]` and `[user #ada email='a']` (different attribute order, same data) hash to the same SHA-256.

              [# Source: #]
           [user email='ada@example.com' id=42 active=true]

           [# cx canonical output (strict canonical bytes): #]
           [user active=true email='ada@example.com' id=42]
            

**Canonicalization rules (strict):**

• **Attribute key order:** lexicographic by attribute name. Ties broken by Unicode code point. Comments stripped.
• **String quoting:** single quotes for single-line; triple double-quotes for multi-line. Escapes minimal — only what the parser requires.
• **Whitespace:** no insignificant whitespace; bodies joined with single spaces; structural newlines only where the grammar requires them.
• **Numeric form:** integers as plain digits; floats in the shortest representation that round-trips to the same value (IEEE-754 shortest-form).
• **Boolean form:** `true` / `false`.
• **Date/datetime:** offset preserved (NOT normalized to UTC); fractional seconds dropped if all zero; identity-comparison is by absolute instant.
• **Anchors expanded:** `&base` / `*base` shapes resolve into their expanded form in the canonical output.

Cross-format identity (hash stable through projections)

The hash is over CX strict canonical bytes — NOT over the projection (JSON / YAML / TOML / etc.). This produces a key property: **a document's hash is stable through round-trip projections**.

              # Original CX
           cx hash users.cx
           # → sha256:3a7bd3e2360a...

           # Convert to JSON then back
           cx convert users.cx --to json > users.json
           cx convert users.json --to cx | cx hash
           # → sha256:3a7bd3e2360a...  (same hash)
            

The property holds for **lossless** projections (JSON, YAML, TOML, XML — within their expressive range; see roundtrip). For **lossy** projections (Markdown, CSV/TSV, JSONL with non-trivial nesting) the round-trip drops information; the re-imported document will have a different hash. CX makes the lossy-ness explicit; see roundtrip for the full matrix.

Practical use: in a content-addressable store, you can accept incoming data in any supported format, convert to CX, hash, dedupe — knowing that two clients sending the same data in different formats will produce the same key.

Stability across bindings + machines

The hash function is **stable across bindings, OSes, and architectures**. V, Python, Go, and Rust all produce byte-identical hash strings for byte-identical input. The guarantee extends to architecture (x86-64, ARM64, little-endian, big-endian) and OS (macOS, Linux, Windows, BSD). Verified by [`conformance/binding_api.txt`](../../conformance/binding_api.txt) gate 28.6.

**Determinism details:**

• **Float formatting:** the canonical shortest-form produces byte-identical output regardless of host C library (`printf("%g")` is NOT used; CX implements its own dragon-grisu-style formatter).
• **Endianness:** the canonical bytes are UTF-8 text, no multi-byte numeric encoding in the canonical form itself.
• **Unicode normalization:** identifiers and string content are normalized to NFC before canonicalization.
• **Locale-independence:** sort order for attribute names is by Unicode code point, not by locale collation (no LC_COLLATE influence).

Truncation safety (short ids)

SHA-256 is 256 bits (64 hex chars). For human-facing identifiers, you can truncate. Birthday-collision math: with N items and a hash of B bits, the probability of any collision crosses 50% at roughly N ≈ √(π/2 · 2^B). Useful safe-truncation lengths:

**Recommended:** 16 hex (64 bits) for short IDs in UI / URL / log contexts. 24 hex (96 bits) for cross-tenant content stores. Full 64 hex for security-sensitive identifiers.

Use cases — cache keys, dedup, content stores

**Cache key:** `cx hash request.cx` is a stable cache key for an expensive computation parameterized on the document. Same input → same key → memoization works.

**Deduplication:** in a document store, hash on ingestion; store the canonical bytes once, point all duplicates at the same blob.

**Content-addressable storage:** the hash IS the address. Git, IPFS, Nix all use the same model. CX hashes interop directly:

• **Git LFS:** point `cx hash`-derived blob ids at the CX file's strict-canonical bytes.
• **IPFS:** wrap the canonical bytes in a CIDv1 dag-pb envelope or use raw codec; the SHA-256 maps to the CID's multihash.
• **Nix:** identical store-path-shape (SHA-256-named blob with metadata sidecar).
• **S3 / object storage:** content-MD5 header is too weak; use `x-amz-meta-cx-sha256` for stronger integrity.

**Signing:** sign the strict canonical bytes; verify by re-canonicalizing on receipt. The signature is robust against benign reformatting (whitespace, attribute order, comments) because those don't affect strict canonical form.

Buffer envelope

An ast-bin payload is a self-contained byte buffer with a versioned header followed by tree topology and length-prefixed atoms. Layout:

• **Magic + version (8 bytes):** ASCII `'CXAB'` then a u32 format version. Reader validates magic + version before parsing further.
• **Capability bits (8 bytes):** u64 bitmask declaring what features the payload uses. A reader that does not advertise a required capability refuses the payload.
• **Payload length (8 bytes):** u64 byte count of the tree-topology section; enables stream chunking.
• **Tree topology:** preorder-encoded node tags + length-prefixed strings + zig-zag varints for child offsets.
• **Optional trailer:** SHA-256 of the equivalent canonical bytes (skip if the producer doesn't compute it) — readers can use it to verify cross-format identity without re-canonicalizing.

Length-prefixed strings: all element names, attribute names, and string scalars carry their byte length as a varint before the bytes. No null terminators.

Capability bits (full table)

Capability bits are the forward-compat mechanism. When a newer libcx adds a feature, it claims a new cap bit. Readers that don't know that bit refuse the payload (rather than silently mis-interpret it). The full table:

Bits 33-63 reserved for future revisions. The cap-bit layout is fixed; bits are never re-assigned.

Version negotiation + forward-compat

When a newer libcx talks to an older binding, the version negotiation runs at FFI handshake: `cx_features()` returns a u64 bitmask of supported caps. The caller compares with the bits required by the payload it's about to send:

• **All required bits supported:** payload accepted.
• **Required bit NOT supported:** payload refused with CXER0200 (capability mismatch). Caller MAY downgrade — re-emit the payload without the unsupported feature if a downgrade path exists — or surface an error to the user.
• **Unknown bits set:** strict mode refuses; lenient mode accepts (the unknown bits are forward-feature hints; the payload's required-bits are explicit).

Lenient mode is the default; strict mode is opt-in via `cx_set_strict(true)`. The choice trades forward-compat against accidental-misinterpretation risk.

Self-describing mode

Every value is tagged with its kind. Comparable to JSON or BSON in flexibility. Used when the schema is not known to both sides — e.g., wire-formatted between two CX bindings that don't share schemas, or for ad-hoc tooling.

Tag bytes: a one-byte type tag (`0x01` = bool, `0x02` = int, `0x03` = float, `0x10` = string, `0x20` = array, `0x21` = map, etc.) followed by the value bytes. Length prefix where applicable. Full tag table in [`spec/core/data-bin.md §3`](../../spec/core/data-bin.md).

Schema-driven mode (cap bit 1)

Tag bytes and field names are omitted; the schema is the dictionary. Wire size comparable to Protobuf or Avro. Used for high-throughput bindings (e.g. the analytics-bridge Arrow / Parquet path).

**Negotiation:** the schema-driven mode is gated on capability bit 1 (see ast-bin-capabilities). A reader that does not advertise the schema-driven cap bit gets self-describing payload, never silently corrupted bytes. The schema is exchanged out-of-band (e.g., the `.cxs` file is shipped alongside or referenced by hash); the data-bin payload carries a SHA-256 of the schema in its trailer so readers can verify.

Chunked tables (§3.11)

Tables (`:table` data shape) get a dedicated wire form in data-bin §3.11. Layout:

• **Per-table preamble:** column count, column-spec table (name + type + nullability).
• **Per-chunk header:** row count, dictionary references if dictionary-encoded.
• **Per-column buffers:** contiguous, dictionary-encoded where applicable, nullable via a separate validity bitmap.
• **Per-chunk manifest:** min/max/null-count per column, used for predicate pushdown on read.
• **Trailer:** cumulative chunk count, file-level statistics, optional content-hash of the canonical form.

This is the wire format under the CXCol streaming surface (see cxcol in analytics). Reading is chunk-by-chunk; the manifest enables skip-on-predicate without loading the full payload.

Page-compression wrapper (§3.12)

An optional page-compression wrapper (`0x90` envelope, per [`spec/core/data-bin.md §3.12`](../../spec/core/data-bin.md)) wraps ranges of bytes inside the payload with a compression codec. Supported codecs: Snappy (default), Zstd, LZ4, Gzip. The wrapper is gated by cap bit 1 alongside schema-driven mode.

Compression operates on column buffers, not on the structural header — so readers can navigate the page index without decompressing the value bodies. The hash is taken over the canonical (uncompressed) bytes.

Document-unique scoping

An identity `#name` is unique within a single CX document. Duplicate `#name` declarations raise CXER0102 at parse time. The uniqueness check spans the entire document **after include resolution** — an `[?cx include]`-imported sub-document contributes its `#name`s to the same namespace.

Identities do NOT cross document boundaries except via includes. Two separate CX files can each declare `#ada` without conflict; they refer to different elements in their respective documents.

IDREF resolution + cycles

A reference to an identity uses the `#name` sigil in **value position**: `[post author-id=#ada ...]`. The reference resolves to the element bearing `#ada` via CXPath's `id('name')` function.

              [users
           [user #ada email='ada@example.com']
           [user #grace email='grace@example.com']]
         [posts
           [post author-id=#ada \"\"\"First post\"\"\"]
           [post author-id=#grace \"\"\"Second\"\"\"]]
            

**Reference cycles** (A references B references A) are not an error — the references are values, not container relationships; no infinite recursion. However, cyclic **merge** references (via the `*` sigil — see merge) ARE errors and raise CXER0101.

The ID/IDREF model is XML-compatible: round-trip through XML preserves the references; round-trip through JSON encodes them as `{"$ref": "name"}` envelopes per [`spec/conversions.md §4`](../../spec/conversions.md).

Identity preservation across projections

IDs survive round-trip through every supported projection:

The data layer preserves the identity; the lossy projections (CSV / JSONL with flattening) lose it. For those, use CX as the intermediate format.

Doc lifetime per binding

Every binding's `Doc` value owns a `cx_doc_ref` (an opaque libcx handle). The lifetime is:

• **V:** Boehm-GC-tracked. Dropped when no live reference exists; libcx releases the underlying memory at GC time. No explicit free.
• **Python:** PyObject wrapping a C pointer. Dropped on garbage collection (reference count → 0); a `__del__`-equivalent finaliser calls `cx_doc_release(handle)`.
• **Go:** wrapping struct with a `runtime.SetFinalizer`-registered cleanup. Dropped when the wrapper becomes unreachable; the finaliser calls `cx_doc_release(handle)` on the next GC cycle.
• **Rust:** wrapping struct with a `Drop` impl. Dropped deterministically when the binding goes out of scope; the `Drop::drop` calls `cx_doc_release(handle)`.

**Practical implications:**

• **Long-lived Docs:** keep a reference for the duration of use. Bindings do not silently free under pressure.
• **Cyclic references:** between two CX Docs are not possible (CX values are immutable trees), so no cycle detection needed in the host GC.
• **Multi-process sharing:** ast-bin is the wire format — serialize on one side, deserialize on the other. There is no shared-memory Doc passing (yet).

Node borrowing from a Doc

A `Node` selected from a `Doc` (via `select_all`, `select`, `children`, etc.) is a **borrowed reference** into the Doc's memory — it does NOT take an independent lifetime. When the parent Doc is freed, all Nodes selected from it become invalid.

• **Python/Go:** the Node wrapper holds a strong reference to the Doc wrapper, preventing the Doc from being GC'd while Nodes exist. Safe by construction.
• **Rust:** Node carries a lifetime parameter tied to the Doc's borrow. The borrow checker prevents use of a Node beyond the Doc's lifetime.
• **V:** Boehm-GC tracking; the Doc stays live while Nodes referencing it are reachable.

**Doc.bytes() output is owned:** the canonical bytes returned from `doc.bytes()` are a freshly-allocated copy owned by the caller. Modifying or freeing it does not affect the Doc.

**[?modify] returns a NEW Doc:** the input Doc is unchanged. The new Doc has its own lifetime; the input Doc continues to exist independently. Structural sharing means the two Docs share most of their underlying memory but libcx tracks the references so both Docs are valid until both are released.

Thread registration (cx_thread_register)

libcx uses Boehm GC, which requires that every thread that calls libcx APIs is **registered** with the GC. The C ABI exports `cx_init()` (call once per process at start) and `cx_thread_register()` (call per thread before first libcx call from that thread). Per [`spec/abi.md §1.5.5`](../../spec/abi.md).

**Bindings handle this automatically** at the FFI chokepoint — every Layer-1 method has a per-thread guard that registers the calling thread on first use. Host application code doesn't call `cx_thread_register` directly unless dropping below the binding layer to raw FFI.

**Cap bit 26 (thread-register):** advertised by libcx ≥ v0.6.0. Older libcx (pre-v0.6.0) ran single-threaded only; [; version-literal-ok ] the cap bit's introduction signaled thread-safe FFI.

**Practical implication:** spawning a thread from host code and calling a CX binding method from it is safe — the binding registers the thread transparently. The only caveat: if you're calling libcx via raw FFI (not through a binding), you must call `cx_thread_register()` yourself before any other libcx call from that thread.

Canonical form recap

Canonical mode strips presentation — comments, anchors, whitespace, attribute order normalisation — and emits a data-equivalent byte-identical form. Two documents with the same data emit to the same bytes; the difference between them is something a human added, not something the data carries.

              cx canonical menu.cx     # canonical bytes
           cx hash menu.cx          # SHA-256 hex over canonical bytes
           cx eq a.cx b.cx          # exit 0 iff canonical(a) == canonical(b)
            

Canonical form is the basis for content-addressed identity (`cx hash`), for byte-identical conformance tests across bindings, and for diff that ignores presentation.

Declared identifiers (#id, @ref)

Declared identity is what you write when you want one element to point at another by name. Declare with `#`; reference with `@`. IDs are unique within their scope; the scope is the document root by default.

              [order #main
             [item #latte]
             [item #scone]]
           [receipt order=@main]
            

Anchors and merge targets

An anchor (`&` sigil) names a value once and lets later places refer to it without repeating it. A merge target (`*` sigil) folds the anchor referent into the current element. Anchors are anonymous handles; the canonical form renumbers them so two documents that bind the same data with different anchor names hash to the same identity.

              [defaults &shared timeout=30 retries=3]
           [server *shared name=api]
           [server *shared name=worker]
            

ast-bin quick reference

ast-bin is the binary serialization of the canonical form. The buffer envelope is `[u32 LE size][payload bytes]`; payload is the AST in a column-major encoding keyed by capability bits. Release the buffer with `cx_free`; never call system `free()`. Capability bit 36 advertises the PathNode wire format (ast_bin v8); cap bit 3 advertises symmetric AST round-trip. The full bit table is in [`spec/abi.md` §3](../../spec/abi.md).

data-bin quick reference (CXCol v1)

data-bin is the strict-canonical binary data format, branded `CXCol` (retitled in commit `cbed7754`). Magic bytes are `0x43 0x58 0x44 0x42` (historical, preserved for forward-compat); modes are self-describing (default), schema-driven (cap bit 1 — caller supplies a `.cxs`, payload omits the schema preamble), chunked tables (`spec/core/data-bin.md` §3.11), and page-compressed (`spec/core/data-bin.md` §3.12). All four modes round-trip byte-stable through `cx --to=data-bin | cx --from=data-bin`.