AST and Memory Layout

AST and Memory Layout

The AST is a flat, index-addressed, struct-of-arrays structure modeled on the Zig compiler's own AST. Nodes never point at each other and never heap-allocate individually: a node refers to its children by u32 index into shared column arrays. That is what makes the tree cache-dense, cheap to build, and trivially serializable — a JavaScript consumer can read it straight out of a zero-copy buffer.

Node identity

// src/ast.zig:11
pub const NodeIndex = enum(u32) {
    root = 0,                     // the Program node is always index 0
    none = std.math.maxInt(u32),  // the "no child" sentinel
    _,
};

Index 0 is always the program root; maxInt(u32) is the null child. TokenIndex and ExtraIndex are plain u32.

The node

A node is three fields (ast.zig:37). Because nodes live in a MultiArrayList, each field is its own column array:

tag         Tag, enum(u8)   — 214 variants (ast.zig:50)
main_token  u32             — the node's defining token
data        extern struct { lhs: NodeIndex, rhs: NodeIndex }   — two u32 slots

That is 13 bytes of payload per node, split across three arrays. data is an extern struct so lhs and rhs sit at fixed offsets a zero-copy reader can rely on. Parents are not stored on the node — when a consumer needs them they are built on demand (see Parents).

main_token is the node's defining token, not necessarily its first: for a member_expr it is the property token, for a binary operator it is the operator. So it locates a node but does not by itself give the node's source span (see Spans).

How lhs/rhs encode children

Each tag defines its own use of the two slots, in one of four patterns.

Direct children. Operands sit in the slots directly. add uses both (lhs + rhs); logical_not uses lhs. member_expr puts the object in lhs and a property_ident node in rhs — rhs is a node index, and that node's main_token is the property name (expressions.zig:6389).

Inline SubRange. block_stmt and root store a statement list directly as lhs = start, rhs = end — two raw extra_data offsets reinterpreted through NodeIndex. This is the special case; most list-bearing nodes use the next pattern instead.

ExtraIndex to a typed struct. Nodes with several heterogeneous children store one slot as an index into extra_data, where a struct's fields are laid out as consecutive u32s. fn_decl's lhs points at a FnData; if_else_stmt keeps the condition in lhs and points rhs at an IfData.

Packed offsets. A few nodes pack byte offsets rather than node indices — jsx_empty_expr stores the { / } offsets — read back through NodeIndex.fromInt / toInt.

extra_data and the payload structs

extra_data: []const u32 is one flat side table for everything variable-arity. A SubRange { start, end } is a half-open [start, end) window into it (extraSlice). Typed payloads are written field-by-field and read back with extraData(T, index), which uses comptime reflection to map each field to one u32 — only NodeIndex and u32 fields are permitted — and bounds-checks the read.

Struct	Used by	Fields
SubRange	every list node	start, end
IfData	if_else_stmt	consequent, alternate
ForData	for_stmt	init, condition, update
ForInOfData	for_in / of / await_of_stmt	binding, expr, body
TryData	try_stmt	catch_node, finally_body
FnData	functions, function types	name, params, params_end, body, return_type, type_params, type_params_end
ArrowData	arrows	params_start, params_end, body, return_type, type_params, type_params_end
ClassData	classes	name, super_class, body, impls_*, type_params_*
MethodData	class methods	params_*, body, return_type, modifiers, type_params_*
PropertyData	class fields	value, type_annotation, optional
Conditional	conditional	consequent, alternate
ImportData	import_decl, export_named_from	specifiers_start, specifiers_end, source
InterfaceData, TypeAliasData, EnumData	TS declarations	name token + ranges
JsxElementData, JsxOpeningData	JSX	opening / children / closing, name / attr ranges

Class-member modifiers are bit-packed into MethodData.modifiers per the ModifierBit constants — accessibility in bits 0–1, then readonly, override, declare, abstract, static, async, generator, and accessor as single bits.

The Ast container

// src/ast.zig:728
pub const Ast = struct {
    source: []const u8,
    is_ts: bool = false,            // ts/tsx/dts — gates TS-specific later semantics
    nodes: NodeList.Slice,          // SoA nodes
    tokens: TokenList.Slice,        // NOT owned — caller frees the lexer result
    extra_data: []const u32,
    extra_data_cap: u32 = 0,
    errors: []const Diagnostic,
    scope_events: []const ScopeEvent = &.{},   // empty unless emission was on
    scope_events_cap: u32 = 0,
    node_end_toks: []const u32 = &.{},          // per-node last consumed token
    node_end_toks_cap: u32 = 0,
    parent_fixups: []const u32 = &.{},          // non-structural (child, parent) pairs
    parent_fixups_cap: u32 = 0,
    pub fn deinit(self, allocator) void { … }
};

Two ownership facts a consumer must know. Tokens are not owned by the Ast — they belong to the TokenizeResult, and the caller frees both. And the *_cap fields record the true backing capacity of each buffer the parser handed over without a shrinking realloc, so deinit frees them correctly; consumers just call deinit.

Decoding a node: o.p

Given the index i of a member_expr:

const tag    = ast.nodeTag(i);                   // .member_expr
const estree = std.mem.span(layout.tag_names[@intFromEnum(tag)]);  // "MemberExpression"
const d      = ast.nodeData(i);
const object = d.lhs;                             // NodeIndex of `o` — recurse to decode
const prop   = d.rhs;                             // NodeIndex of a property_ident node
const name   = ast.tokenText(ast.nodeMainToken(prop));   // "p"

For a list-bearing node (call_expr args, array_literal) the slot is an ExtraIndex instead — ast.extraData(SubRange, @intFromEnum(d.rhs)), then iterate ast.extraSlice(r). For block_stmt / root, slice ast.extra_data[@intFromEnum(d.lhs)..@intFromEnum(d.rhs)] directly.

Spans

nodeSpan(i) covers main_token only, which is exact for single-token nodes (identifiers, literals) but not for a compound node, whose main_token is a defining token rather than a left edge.

End comes from node_end_toks[i] — the last token consumed when node i was built, captured at addNode time, so it is exact with no second pass. There is no accessor that combines it; compute the end byte directly:

// ast.node_end_toks column — src/ast.zig:751
const last = ast.node_end_toks[@intFromEnum(i)];
const end  = ast.tokenStart(last) + ast.tokens.items(.len)[last];

Start of a compound node is the start of its leftmost descendant (for member_expr, the object's start) — recurse to find it. There is no per-node start-token field.

ESTree mapping

layout.zig builds, at comptime, a table tag_names: [tag_count][*:0]const u8 (layout.zig:13) mapping every Tag ordinal to its ESTree type string. Many internal tags collapse to one ESTree type: fn_decl, async_fn_decl, generator_fn_decl, and async_generator_fn_decl all map to "FunctionDeclaration"; the dozens of binary-operator tags all map to "BinaryExpression". The finer internal split lets the parser and JS-side consumers dispatch on a single u8 without re-reading the operator text. The table is exposed over the C ABI as ez_tag_count() and ez_tag_name(index) (layout.zig:212).

A few tags are deliberately finer-grained than ESTree:

• property_ident / property_literal — an identifier or string used as a property key. ESTree Identifier / Literal, but distinct internally so the semantic phase emits no variable reference for them.
• class_body — an explicit ClassBody node holding members as a SubRange.
• the jsx_* family — JSX structure, including jsx_gap_node for inter-child whitespace that layout-aware rules care about.
• ts_named_tuple_member — preserves a labeled tuple element's name ([a: number]), which TypeScript treats as display-only.

Accessors

Ast exposes O(1) typed reads (ast.zig:810): nodeTag, nodeMainToken, nodeData, tokenTag, tokenStart, tokenText (uses the stored length), extraData, extraSlice, nodeSpan, and nodeName (which handles ts_enum_decl, whose name lives in extra_data). The .none index reads back as .root / 0 from the tag and token accessors, so traversal code can stay branch-light.

Parents (on demand)

Parent links are not stored on nodes and not built by the parser. When a consumer sets build_parents, parent_builder.buildParentsOnly (parent_builder.zig:423) does a single forward scan that, for each node, writes itself as the parent of every child it owns — one pass suffices because each child is claimed by exactly one structural parent, so traversal order is irrelevant. It then replays ast.parent_fixups, the small set of non-structural (child, parent) links the parser recorded for cases the tree shape can't express (a type annotation on a destructured parameter, whose pattern node has no slot to hold it).