Data-Oriented Design in Yuku's Parser

June 28, 2026

Yuku is a JavaScript and TypeScript parser I write in Zig, and its npm packages are downloaded tens of millions of times a week. It parses typescript.js, an 8 MB file, in about 15 ms on my M3. The grammar has little to do with that. It is plain recursive descent, written from the spec. The speed comes from how the tree sits in memory, and the same layout is what lets the tree reach JavaScript cheaply.

The pointer tree

The usual AST looks like this:

const Node = union(enum) {
    binary: struct { op: Op, left: *Node, right: *Node },
    call: struct { callee: *Node, args: []*Node },
    identifier: struct { name: []const u8 },
    // ...
};

typescript.js produces close to a million nodes, about one for every ten bytes of source. In this shape each node is its own allocation, somewhere on the heap, and every walk over the tree is a chain of dependent loads the CPU can't predict. The tree is also full of absolute addresses, so it only means something inside the process that built it. You can't write it to disk or hand it to JavaScript without rebuilding it object by object.

Indices instead of pointers

Yuku keeps every node in one array and replaces every pointer with a u32 index into it. The maximum value means "no child", so an optional child costs nothing extra. Lists of children, like the statements of a block, go into a second shared array called extras, and the node keeps a start and a length. Everything comes from one arena, so freeing the tree is one call.

pub const NodeIndex = enum(u32) { null = std.math.maxInt(u32), _ };

pub const Tree = struct {
    nodes: std.MultiArrayList(Node),
    extras: std.ArrayList(NodeIndex),
    strings: StringPool,
    source: []const u8,
    arena: std.heap.ArenaAllocator,
    // ...
};

This is let x = 1 + 2; as it comes out of the parser:

let x = 1 + 2;
0   4   8   12      byte offsets

[0] binding_identifier    4..5    name=4..5 ("x")
[1] numeric_literal       8..9    raw=8..9 ("1")
[2] numeric_literal       12..13  raw=12..13 ("2")
[3] binary_expression     8..13   left=1 right=2 operator=add
[4] variable_declarator   4..13   id=0 init=3
[5] variable_declaration  0..14   kind=let declarators=extras[0..1]
[6] program               0..14   body=extras[1..2]

extras: [ 4 ][ 5 ]

A parse function builds its children and then appends itself, so children always come before their parents and the root is the last node. A plain loop from the first index to the last is a post-order walk, with no recursion and no stack.

The node array is stored as columns, not as an array of structs. A pass that only switches on node kinds reads one dense column and never pulls spans through the cache:

array of structs                  struct of arrays
[ data | span ][ data | span ]    data: [ d0 ][ d1 ][ d2 ] ...
                                  span: [ s0 ][ s1 ][ s2 ] ...

Scratch buffers

A block doesn't know how many statements it has until the closing brace. Allocating a growable list for every block, call and array literal would put the allocator back on the hot path, so the parser keeps a few scratch stacks for the whole parse. A list records the stack's length when it begins, pushes its items, copies them into extras in one go when it ends, and truncates the stack back.

pub fn parseBody(self: *Parser, terminator: ?TokenTag) !ast.IndexRange {
    const checkpoint = self.scratch_statements.begin();
    defer self.scratch_statements.reset(checkpoint);
    while (!self.isAtBodyEnd(terminator)) {
        const statement = try statements.parseStatement(self, .{});
        try self.scratch_statements.append(self.allocator(), statement);
    }
    return self.flushToExtras(&self.scratch_statements, checkpoint);
}

For { a; { b; c; } d; }, with B as the inner block:

scratch     extras
[a]         []              outer block, after a;
[a|b c]     []              inner block pushes on top
[a]         [b c]           inner flushes, truncates back
[a B d]     [b c]           outer resumes
[]          [b c|a B d]     outer flushes

Nesting costs nothing, because the inner list is flushed and gone before the outer one continues. Only lists that grow at the same time need separate stacks, like the strings and expressions of a template literal.

Backtracking falls out of the same idea. TypeScript sometimes makes the parser guess, for example whether <T>(x) => x is a generic arrow or JSX. A checkpoint is the lexer position plus the lengths of the node, extras and diagnostics arrays, and rewinding truncates them. Whatever a failed attempt built is just the tail of those arrays, so there is nothing to free.

Strings are offsets

Almost every string a parser produces already exists in the source, byte for byte. So a string in Yuku is a start and an end offset. Below the source length it is a slice of the source. Past it, it points into a small pool for the few strings that don't exist in the source, like a string literal whose escapes had to be decoded.

pub fn get(self: *const StringPool, id: String) []const u8 {
    const src_len: u32 = @intCast(self.source.len);
    if (id.start < src_len) return self.source[id.start..id.end];
    return self.extra.items[id.start - src_len .. id.end - src_len];
}

let x = "a\nb";            15 bytes of source

string_literal  raw   = 8..14    source slice   "a\nb"
                value = 15..18   pool[0..3]     a, newline, b

The lexer never decodes while scanning. It records the span and sets a flag if it saw a backslash, and the value is decoded only when the parser asks for it. For a whole 8 MB file the pool stays tiny.

This pays off again in JavaScript. The caller already has the source as a string, so the JavaScript decoder uses the same rule: below the source length it slices the caller's string, and past it it reads the pool. Only the pool is copied across. The source text itself never crosses the boundary.

Crossing into JavaScript

Most JavaScript tools need the AST as JavaScript objects, and this is where native parsers usually lose. Serializing to JSON and calling JSON.parse, or building objects one at a time through N-API, often costs more than the parse.

Yuku's tree has no pointers anywhere. Children are indices, lists are offsets into extras, and strings are offsets into the source. It is already position-independent bytes, so serializing it is mostly a copy:

header | nodes   | extras  | string pool | comments | diagnostics
         packed    memcpy    memcpy

Yuku computes the exact size first, asks the JavaScript engine for an ArrayBuffer of that size, and writes straight into it. There is no intermediate buffer and nothing preallocated. The WebAssembly build uses the same serializer.

Each node is packed into a fixed record: a tag, some flag bits, a row of u32 slots, and the span. The mapping is derived at compile time from the fields of each AST struct, in declaration order. A bool takes one flag bit, an enum with n variants takes ⌈log₂ n⌉ bits, a child takes one slot, and a list or a string takes two. If a node ever needs more than the record has, the build fails and names the node.

The JavaScript decoder is generated by a Zig program that calls the same layout function at comptime, so the encoder and the decoder can't drift apart. This is what it emits for a binary expression, with b pointing at the node's record:

case 8: {
  const f1 = _u32[b + 1], f2 = _u32[b + 2];
  return {
    type: "BinaryExpression", start, end,
    left: f1 !== NULL ? node(f1) : null,
    right: f2 !== NULL ? node(f2) : null,
    operator: BINARY_OPS[flags & 31],
  };
}

There is no parsing step on the JavaScript side, only reads from a typed array. Each kind is created as an object literal with a fixed key order, so V8 gives every node of a kind the same hidden class.

Offsets need one conversion on the way out, because Zig counts UTF-8 bytes and JavaScript counts UTF-16 units. The two agree up to the first non-ASCII byte, so an ASCII file needs nothing. Past that byte, Yuku keeps one bit per byte marking where a UTF-16 unit starts, plus a running count per block, so converting an offset is one lookup and a popcount.

From JavaScript, Yuku returns the full AST 3 to 9 times faster than Acorn, Babel, Oxc and SWC (benchmark). It relies on no platform-specific tricks, and the same package runs in Node.js, Bun, Deno, browsers and edge runtimes.

What it opens up

Native tools have always had trouble with JavaScript extensions. Plugins, custom transforms, and webpack and Rspack loaders all run in JavaScript and need the tree there, often for every file in a project, and paying for the boundary on every file is what kept them slow. When the AST crosses as one copy and a decode, a native toolchain no longer has to choose between speed and letting people extend it in JavaScript. It works in the other direction too: a tree changed in JavaScript goes back to Zig in the same format to be printed.

The design is in Rust now as well. SWC Next is built on a port of Yuku's AST, parser and semantic analysis.

Why not denser

The Zig compiler packs its AST even tighter, as a tag plus two words whose meaning depends on the tag. That's the right call when the compiler is the only one reading it. Yuku's AST is for other people's tools, so nodes keep named, typed fields, and that is also what makes generating the decoder possible.