One Representation#

One Representation#

A tree you already believe in#

Ask anyone to sketch a document and they draw the same thing: a heading, then a list, one item holding a paragraph, another holding two. A tree. The question a converter must answer is not whether the middle representation is a tree. The question is which tree, and how it is stored.

The answer to “which tree” is a Zig-native node set. It is structurally compatible with pandoc’s document model but owned by this project. Blocks nest. Inlines nest. Nodes carry identifiers, classes, and key-value attributes. The full roster, from core/src/ast.zig:

Two tags keep this set closed for ordinary structure: container (a block with attributes) and span (an inline with attributes). An AsciiDoc sidebar, an HTML <section>, a DOCX content control, an ODP speaker-notes page: each becomes a container with a class, not a new node type. If a format ever truly cannot be expressed this way, the node set is wrong. That is a design alarm, not an extension point.

The extension tags are the one sanctioned escape hatch, and they pay for the privilege (ZDS 0013). An extension names its owner in reverse-DNS form, names itself, and carries a version. Its children are not optional decoration; they are the fallback every other writer renders. The validator refuses an extension with no fallback, and it refuses an extension nested inside another extension of the same owner. The first producer is the HTML reader, which maps <details> to an extension whose fallback is the summary line and the disclosed content.

The shape of the storage#

The obvious implementation allocates a node object per element and links the objects with pointers. zenfmt instead does what Zig’s own compiler does for std.zig.Ast. Every block lives in one std.MultiArrayList, a struct-of-arrays, as parallel columns. The tree structure is encoded in a single integer per node.

// core/src/ast.zig (storage row, private)
pub const Block = struct {
    tag: BlockTag,          // 1 byte
    payload: u32,           // meaning depends on tag
    attrs: OptionalAttrsIndex,
    inlines: InlineRange,   // for leaf blocks: its prose
    subtree_len: u32,       // this node plus all descendants
};

A test asserts that the columns of one block row sum to 21 bytes. A million-block document costs 21 MB of block storage. It is contiguous, and it is allocated out of one arena that is freed in one call when the conversion ends. Note what the row does not contain: no entity field, no facet pointer, no style handle. Rich-document identity lives outside the row, in side tables that cost nothing when unused. That design is this chapter’s second half.

The worked example#

ZDS 0002 fixes the layout with a small document. It is reproduced here because every walker in the codebase is a loop over these columns.

## The *quick* [brown](http://x) fox

- one
- two

  still two

The indentation in the table is commentary. It is not stored. The structure lives entirely in subtree_len. Node 1′s subtree is 6 rows long, so the document’s next top-level block, if there were one, would sit at index $1+6=7$. Node 2′s subtree is 2, so its sibling item sits at $2+2=4$. Walking children is a short loop. There is no recursion and no call stack:

var child = parent + 1;
const end = parent + subtree_len[parent];
while (child < end) : (child += subtree_len[child]) {
    // visit `child`
}

The heading’s prose is the inline range 0..9 in the parallel inline table. The encoding is the same, with 13-byte rows:

Hop from 0 and you visit exactly the heading’s 7 top-level children. The hop skips the insides of emphasis and link without ever testing what they are.

Payloads live in side tables#

The payload column is a bare u32. Its meaning depends on the tag. For heading it is a level. For list it is an index into a table of list properties. For link and image it is an index into targets. For code it is a range in the text pool. For extension it is an index into the extensions table holding the owner, the name, and the version. These side tables (targets, headings, lists, table properties, extensions, citations, metadata) are append-only arrays in the same Store.

Append-only is a load-bearing property. Side-table indices are never invalidated, so a filter that rebuilds the node arrays can leave every payload index untouched and share the tables wholesale. An identity filter costs one memcpy per column and zero side-table work. The test suite measures this claim rather than asserting it.

Strings follow the same discipline. All prose lives in one UTF-8 text pool. A text node’s payload is a range into that pool. Extracted binary content, such as image data a reader pulled out of a PDF or a DOCX, lives in a separate resource pool, described below.

One schema, one row per tag#

Every fact stated so far raises the same maintenance question: where do the rules about a tag live? What children may a table hold? Which side table does a citation payload index? Before ZDS 0013 the answers lived in a set of coordinated switch statements. The compiler enforced that every switch covered every tag, but nothing enforced that the switches agreed with one another.

The rules now live in one comptime table in core/src/schema.zig, one row per tag:

pub const BlockRow = struct {
    tag: BlockTag,
    payload: PayloadKind,   // which side table, or none
    children: ChildRule,    // flow, only: {...}, inline_content, none
};
pub const block_schema = [_]BlockRow{
    .{ .tag = .paragraph, .payload = .none, .children = .inline_content },
    .{ .tag = .list, .payload = .list, .children = .{ .only = &.{.list_item} } },
    // ... one row per tag, checked complete at compile time
};

Content kind, placement rules, payload validation, debug names, and the writer capability checks of Chapter 5 are all derived from this table by comptime iteration. A property that used to be five agreeing switches is now one row read five ways. Drift between the rules is no longer expressible, and a new tag fails compilation everywhere at once until its row exists.

Storage is private; views are typed#

No format library reads those columns directly. The public face of a node is a tagged union built in core/src/payload.zig from the schema table’s payload kinds:

switch (doc.block(index).content) {
    .heading => |h| // h.level, h.inlines: InlineRange
    .list => |l|    // l.kind, l.start, l.items: BlockRange
    .extension => |x| // x.owner, x.name, x.version, x.fallback
    else => {},
}

This split is the chapter’s central trade. Storage is chosen for the machine: cache-friendly columns, one arena, integer links. Views are chosen for the person: exhaustive switches, named fields, no way to read a payload as the wrong type. Neither leaks into the other.

Attributes follow the pattern. A node’s attrs is an optional index into an attrs table holding an identifier, classes, and key-value pairs, with interned keys. Metadata is a small value model: null, bool, int, float, string, inlines, blocks, list, map. Its maps keep bytewise-sorted keys, so the manifest encoding is canonical without a sort at write time. Footnotes are the one deliberate indirection. A note inline carries only a reference. Note bodies are collected separately by the builder (declareNote, then beginNoteBody after the main flow), because every target format renders note bodies out of line.

Entities and facets#

Markdown consumes none of what this section describes, and that is the point. A DOCX paragraph has a named style. A PDF line has a page and a position. A spreadsheet cell has coordinates and a formula. Future writers want that information; the flow representation must not pay for it. ZDS 0013′s answer is stand-off annotation: typed facet rows stored beside the tree, joined to nodes by identity, ignored freely.

Five facet kinds ship, each an append-only table sorted by entity:

One rule keeps the whole arrangement sane, and the validator enforces its checkable consequences:

Layout coordinates deserve their own sentence, because the unit was chosen by arithmetic rather than taste. Every Layout box is stored in EMU, English Metric Units, 1/914400 of an inch, with a top-left origin. One point is exactly 12700 EMU. One CSS pixel is exactly 9525. One millimeter is exactly 36000. DOCX and PPTX geometry is EMU natively, so office coordinates transfer without rounding, and PDF points round at a scale of nanometers. A reader normalizes once, at read time, in the one place that knows its source geometry.

Facets survive filtering. The rebuild transform of Chapter 7 records which node ranges it copied, rebases the entity bindings across those ranges in one ordered merge, and hands the new snapshot its own slice of binding rows. A node that a filter drops takes its bindings with it, and its facets become unreachable, exactly as a dropped paragraph’s prose does. This is Lemma 2 of ZDS 0013, running as code.

The resource store#

Extracted binary content generalizes the same way. When a reader pulls image bytes out of an archive or a PDF stream, it registers them in the resource store: source name, MIME type, the bytes in a binary pool, and a BLAKE3 digest computed once at registration. On path output the engine writes each resource into a _media directory beside the artifact, rewrites matching image URLs, and lists every file with its digest in the manifest, reusing the digest it already has. Stream output extracts nothing and keeps source URLs, so piping stays pure.

The validator#

Everything above is an invariant that something else depends on. The validator in core/src/ast.zig proves all of it, with fixed-size explicit stacks and no recursion:

The validator runs after every reader, and again after every filter stage. That placement is the architecture’s honesty mechanism. A reader bug cannot smuggle an impossible tree into the writer. A filter bug is caught at the stage that introduced it, not three stages later. When the validator rejects, the conversion fails with core.invalid-document-tree, and the report names the plugin at fault. The tree is evidence, and the report says whose.