AST and Memory Layout

AST and Memory Layout

Who this is for: consumers reading the AST and engineers studying the layout. The two facts every consumer must know are flagged inline (tokens are not owned by the Ast; ESTree types come from layout.tag_names); buffer- transfer/*_cap mechanics are in Internals.

The AST is a flat, index-addressed, struct-of-arrays structure modeled on the Zig compiler's own AST. There are no per-node heap allocations and no pointers between nodes: a node refers to its children by u32 index. This is what makes the tree cache-dense and trivially serializable.

NodeIndex

pub const NodeIndex = enum(u32) {
    root = 0,                  // the Program node is always index 0
    none = std.math.maxInt(u32),  // the "no child" sentinel
    _,
    pub fn unwrap(self) ?u32   // null for .none
    pub fn toInt(self) u32
    pub fn fromInt(i: u32) NodeIndex
};

root = 0 and none = 0xFFFF_FFFF are reserved. TokenIndex and ExtraIndex are plain u32.

Node

pub const Node = struct {
    tag:        Tag,          // enum(u8), ~140 variants
    main_token: TokenIndex,   // u32 — the defining token (operator, name, literal)
    data:       Data,
    pub const Data = extern struct { lhs: NodeIndex, rhs: NodeIndex };  // two u32 slots
};

Data is an extern struct so its layout is guaranteed: lhs/rhs sit at known offsets, which downstream consumers (e.g. a JS reader over a zero-copy buffer) rely on. Because Node is stored in a MultiArrayList, the three fields live in three separate columns (items(.tag), items(.main_token), items(.data)); the per-node logical footprint is the 13 bytes of field data, column-packed rather than padded per element.

A comment in ast.zig describing the node as "20 bytes per node with parent pointer" is historical: parents are not stored on the node. They are built on demand by the semantic phase (parent_builder.buildParentsOnly), so the live node carries only tag, main_token, and data.

How lhs/rhs encode children

Each tag documents its own use of the two slots. The encodings fall into a few patterns:

• Direct child(ren). Unary/binary expressions store operands directly: add → lhs + rhs; logical_not → lhs is the operand. member_expr → lhs is the object and rhs is a property_ident node whose main_token is the property name (the ast.zig comment "rhs encodes property token" is stale — it's a node index, not a raw token index; see the worked example below).
• SubRange inline. block_stmt and root store a statement list as lhs = SubRange.start, rhs = SubRange.end directly (both are raw extra_data indices reinterpreted through NodeIndex). This is a deliberate special case — most list-bearing nodes instead store an ExtraIndex to a SubRange struct in extra_data.
• ExtraIndex to a typed struct. Nodes with several heterogeneous children store one slot as an index into extra_data where a typed struct's fields are laid out as consecutive u32s. Example: fn_decl → lhs is an index to FnData; if_else_stmt → lhs is the condition, rhs indexes IfData.
• Token-offset payloads. A few nodes pack byte offsets into lhs/rhs rather than node indices (e.g. jsx_empty_expr stores the {/} byte offsets; jsx_gap_node stores a whitespace gap span). These are read back via NodeIndex.fromInt/toInt.

extra_data and the typed structs

extra_data: []u32 is one flat side table. Variable-arity and multi-field payloads live here. A SubRange { start, end } is a half-open [start, end) window into it (Ast.extraSlice). Typed payloads are written field-by-field and read back with Ast.extraData(T, index), which uses comptime reflection to map each field to one u32 (only NodeIndex and u32 field types are permitted) and bounds-checks against extra_data.len.

Representative payload structs (ast.zig):

Struct	Used by	Fields
SubRange	every list node	start, end
IfData	if_else_stmt	consequent, alternate
ForData	for_stmt	init, condition, update (each .none if empty)
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 decls	name token + ranges
InterfaceSigData	interface call/construct/method sigs	key, params_*, return_type, kind, type_params_*
JsxElementData, JsxOpeningData	JSX	opening/children/closing, name/attrs ranges

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

The Ast container

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,        // true backing capacity (buffer transferred w/o shrink)
    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 index
    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 subtleties:

• Tokens are not owned by the Ast. They belong to the TokenizeResult; the caller deinits both. The parser borrows the token slice.
• *_cap fields (extra_data_cap, scope_events_cap, …) let deinit free buffers the parser transferred without a shrinking realloc. Consumers just call Ast.deinit; the mechanics are in Internals.

Worked example: decoding o.p

Given the index i of a member_expr node (o.p):

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"  (NOT a raw token in rhs)

For a list-bearing node (call_expr args, array_literal, …) the slot is an ExtraIndex instead: const r = ast.extraData(SubRange, @intFromEnum(d.rhs)); then for (ast.extraSlice(r)) |child_u32| { ... }. (block_stmt/root are the special case that store SubRange.start/.end directly in lhs/rhs — slice ast.extra_data[@intFromEnum(d.lhs)..@intFromEnum(d.rhs)].)

Spans: main_token, and the node_end_toks end

main_token is the node's defining token, which for many compound nodes is not the leftmost one — member_expr's main_token is the property token, binary operators' is the operator. So Ast.nodeSpan(i) (which spans main_token only) is exact for single-token nodes (identifiers, literals) but not the full ESTree range of a compound node.

• End. Use node_end_toks[i] — the last token index consumed when node i was created (captured at addNode time, so it is exact with no second pass). There is no Ast accessor that combines it; compute the end byte yourself:

  const last = ast.node_end_toks[@intFromEnum(i)];
  const end = ast.tokenStart(last) + ast.tokens.items(.len)[last];

• Start. For a compound node, recurse to the leftmost descendant and take its start (e.g. for member_expr, the object's start). es-parser stores no per-node start token; main_token is a defining token, not a guaranteed left edge.

ESTree mapping

layout.zig builds, at comptime, a table tag_names: [tag_count][*:0]const u8 mapping every Node.Tag ordinal to its ESTree type string (estreeNameForTag). Multiple internal tags collapse to one ESTree type — e.g. fn_decl, async_fn_decl, generator_fn_decl, async_generator_fn_decl all map to "FunctionDeclaration"; if_stmt and if_else_stmt both map to "IfStatement"; the dozens of binary-operator tags all map to "BinaryExpression". The split into many internal tags (e.g. one tag per operator, one per assignment operator) lets the parser and JS-side consumers dispatch on a single u8 without re-parsing the operator text. The table is exposed over the C ABI via ez_tag_count() and ez_tag_name(index).

A few tags worth noting because they are finer-grained than ESTree:

• property_ident / property_literal — an identifier/string used as a property key (member access, import/export specifier name). Type Identifier / Literal in ESTree, but distinct internally so the semantic phase does not emit a variable reference for them.
• class_body — an explicit ClassBody node holding members as a SubRange.
• jsx_identifier / jsx_member_expr / jsx_namespaced_name / jsx_text_node / jsx_gap_node / jsx_empty_expr — JSX-specific structure (jsx_gap_node carries inter-child whitespace for layout-aware rules).
• ts_named_tuple_member — preserves a labeled tuple element's name ([a: number]), which TS treats as display-only but consumers may want.

Accessors

Ast exposes O(1) typed reads: nodeTag, nodeMainToken, nodeData, tokenTag, tokenStart, tokenText (uses stored len; a legacy re-scan fallback exists only for zero-length tokens), extraData, extraSlice, nodeSpan, nodeName (handles ts_enum_decl, whose name lives in extra_data). The .none index reads back as .root/0 from the tag/token accessors so traversal code can stay branch-light.

---

Next: Parser · Semantic Analysis