TinyObjectMap: the Writ workhorse

The TinyObjectMap — WMap<Wu6, WAny>, alias WTinyValMap, wire code W_TINYMAP = 98 — is the single most important container in Writ. It is a compact, fixed-capacity, bitmap-indexed map of up to 52 small keys (0..51) to WAny values, and it is the structure Writ leans on everywhere a small keyed object is needed:

• it is the default backing store for a schema — a typed view is a view over a TOM;
• it is the shape of every logosc AST node — the compiler’s own IR is built from these;
• and its layout is byte-identical across C++ and Logos, which is what makes the heterogeneous compiler story mechanical (see Where the TOM earns its keep).

Its trick is to make a dynamically-chosen field set cost about what a statically-laid-out struct field costs: an O(1) lookup that is a bitmask, a popcount, and an indexed load.

The layout #

A TOM is a small header followed by a packed value buffer. The header is one 64-bit word plus a schema code; the values live in a separate, self-relative buffer kept in key order.

Concretely, the header is:

• bitmap (bits 0–51) — one presence bit per possible key. Bit k set ⇔ key k is present. This is the whole index; there are no key bytes stored.
• cap (bits 52–57) and size (bits 58–63) — the buffer capacity and the current live count, each a 6-bit field.
• schema_code : u64 — a separate word holding the schema’s global identity (0 = unset). It is read from the pointee, never stored alongside the value; schema_type_code() / set_schema_type_code() access it. This is how a schema view knows what it is looking at.
• data : *zoned mut WAny — a self-relative pointer to the value buffer, whose entries are kept in key order. Being *zoned, it is a self-relative delta, so the whole TOM is position-independent like the rest of a zoned graph.

Because keys are not stored — only their presence bits — a TOM with n live entries is a 16-byte header plus n eight-byte value words. That density is why it is the default.

O(1) lookup by rank #

A key carries no stored position; its slot is computed. The value for key k sits at index

popcount(bitmap & ((1 << k) - 1))

— the number of present keys below k. Mask the bitmap down to the bits under k, count them, and that rank is the index into the key-ordered value buffer. One AND, one popcount, one indexed load: about what reading a struct field at a fixed offset costs — except which fields exist is decided at runtime, per value.

get(key) returns a null WAny for an absent or out-of-range key (never a fault, never an Option — the sparse-store default). set(key, val) is a thin &mut: the capacity is fixed, so it never allocates, and it flips the presence bit and writes the slot in place. Two calls are deliberate no-ops: a key ≥ 52, or a set of a new key into an already-full map — the TOM does not grow.

Wu6 in WMap<Wu6, WAny> is a pure type-level label for the 6-bit key; it carries no runtime representation of its own.

Fixed capacity, by design #

The TOM is intentionally not a growable hash map. Its fixed capacity is what buys the thin-&mut writes (no reallocation, no rehash, no self-relative re-anchoring) and the tiny header. When you need a growable, string-keyed object map, that is a different container — WMap<WString, WAny> (W_MAP = 101), which grows and rehashes like a HashMap. The TOM is for the common case: a small, known-bounded set of small integer keys — exactly what a schema’s field set, or an AST node’s child set, is.

As the backing of a schema #

A schema is a typed view whose backing store is, by default, a TOM. The view itself is a 16-byte fat pair { m, z } — m a pointer to the backing TOM, z the arena allocator for boxing wide values on write. A schema field p.f desugars to a TOM get(KEY) / set(KEY, …) on m, with the field’s stable key code chosen at declaration. Because fields are presence-keyed, the layout is forward- and backward-compatible: adding a field leaves an old reader valid, and an absent field reads back as the type’s zero.

The schema’s identity lives in the TOM header’s schema_code, stamped at construction. A schema enum needs no stored discriminant at all — the active variant is read from the pointee’s own schema_type_code. That is also the check .view_checked::<S>() performs at a trust boundary: resolve to the TOM pointer, compare its schema_type_code() against S::CODE, yield Some iff they match.

Where the TOM earns its keep #

The reason the TOM matters beyond “a nice small map” is that logosc’s own IR is built from it. Every AST node is a TinyObjectMap with a CODE discriminant and typed children; the LIR is the same. And crucially, the TOM’s byte layout is identical across the C++ and Logos implementations — so both halves of the compiler read and write the same in-memory structure, with no marshalling boundary between them. (See the introduction for how this makes logosc a single heterogeneous C++/Logos pipeline over one data structure.)

Because the nodes are position-independent, a compiled library can embed its AST as zero-serialized Writ in .rodata and the compiler mmaps it straight back — no parse. A metaprogram written in Logos constructs IR that the C++ compiler consumes directly, because to both of them an AST node is just this map.

Related #

• Writ: the data substrate — where the TOM sits in the larger Writ picture, and the heterogeneous-compiler story.
• Writ Reference — the TOM header bit-packing, container codes, and schema desugaring rules.
• Zoned memory — why the data buffer is self-relative and the whole node relocatable.
• Writ Tutorial — build maps and schemas hands-on from a first @{…} literal.