Internals

Design

Overview

The compiler is a single pass with no AST and no IR. Bytecode is the only intermediate representation. Source flows through four stages.

1. A LUT-driven lexer.
2. A Pratt parser that emits SSA-versioned bytecode directly.
3. A peephole optimiser that folds constants.
4. A register interpreter that lowers each chunk once it runs hot.

The shipped compiler.wasm is about 250 KB served as brotli, 722 KB raw. It builds for wasm32-unknown-unknown with opt-level = "z", lto, one codegen unit and panic = "abort", then goes through wasm-opt.

• The core is about 25,000 lines of Rust.
• Production dependencies are hashbrown, itoa and libm, plus the in-repo wasm-abi crate. SHA-256 is implemented in-tree.
• The WASM build adds dlmalloc as the global allocator. Allocation cost stays flat as live blocks grow.

This page covers the parts that span the pipeline. Tokens, parsing and bytecode emission live in Compiler.

Key mechanisms

• Register dispatch. Each chunk lowers to instructions that name frame slots directly. The hot loop is a flat match that Rust lowers to a jump table. Opcodes without a register form run as stack opcodes.
• Inline tag checks and caches. Register arithmetic and comparisons test the NaN-box tags of both operands inline and take the generic handler for any other type. Attribute loads, stores, method calls and operator dunders cache the field index, method or builtin they last resolved. A class change invalidates them. Caching is per instruction. Each monomorphic site stabilises on its own.
• Template memoisation. A pure user function caches args -> result. The rules are in Template memoisation.
• Static scopes. The names of each function resolve once before anything runs. A name an enclosing function binds becomes a shared HeapObj::Cell. The cell is wrapped when that function is called and captured by the definition. Closures observe the nonlocal writes of each other. Every other free name reads the binding table of its module by a fixed index. The builtins answer while that binding is unbound.
• NaN-boxed values. Val is a 64-bit union. It holds 48-bit signed ints inline, IEEE-754 floats, bools, None, an undef sentinel, and 28-bit heap indices. See Memory model.
• Mark-and-sweep GC. Single-colour, with no reference counts. Cycles are reclaimed natively.

Template memoisation

A pure user function caches args -> result from the second run of a key.

• A table holds up to 256 entries. It is dropped after 256 misses in a row.
• A call qualifies when it has no keywords and no captures.
• Its arguments, defaults and result must be immutable all the way down. Functions and bound methods count as mutable.
• Its free names must be unable to change. Such a name is a builtin the program never binds, the function itself, or a top-level name bound once that no class or other module binds. That top-level name must hold an immutable value or a qualifying function.
• A function with defaults keys on itself.

A function stops memoising in these cases.

• It has attributes.
• It takes a mutable argument or returns a mutable result before any entry exists.
• It reads a free name that can change.

A global store, a module-level del, a function attribute write, or binding a builtin clears every table.

Purity is static, as Compiler describes, plus a runtime check that propagates effects through calls.

A pure wrapper over an impure callee, such as apply(print, x), is never cached. Keys hash strings, bytes and tuples by content and compare strictly. 1, 1.0 and True stay apart.

Dispatch shape

The first call of a chunk runs the code the compiler wrote. Its second call, or a loop past 16 back-edges, lowers it to register code that every frame shares. A hot frame carries on from its loop head.

• LoadAttr and Call sites fuse into CallMethod and CallMethodArgs when every argument is a single-push load. That holds up to 8 arguments and never across a jump target.
• Local loads become slot operands.
• A compare that feeds a branch becomes one compare-and-jump.
• Lowering runs once per chunk. A recursion holds one cache per depth.

Register forms keep int and float math inline. Stack arith and compare opcodes try the same numeric path in exec_arith_or_compare before the generic handler.

Constants become values once per chunk. Lowered code reads them from slots after the names.

• Inline-range ints stay inline.
• Ints from 2⁴⁷ to 2¹²⁷ allocate a HeapObj::LongInt slot.
• Literals beyond ±2¹²⁷ are rejected at parse time.

The instruction format is in Bytecode model.

Memory model

Val is 64 bits and NaN-boxed, with QNAN = 0x7FFC_0000_0000_0000 and SIGN = 0x8000....

INT_MAX = 140_737_488_355_327 and INT_MIN = -140_737_488_355_328. Inline ints cost one ALU op per arithmetic.

• Overflow promotes to HeapObj::LongInt(i128). Results demote back inline when they fit.
• LongInts are interned by value. Equal values share a heap index and stay consistent under hash and eq.
• The hard cap is ±2¹²⁷. Wider results raise OverflowError.

Arbitrary-precision bigints would need a limb vector with a heap allocation per op, or dropping NaN-boxing. Both regress the WASM size and the inner loop.

Dicts and sets key by content through hash_val_with_heap. Value-equal numbers collapse to one key. 1 == 1.0 and 10**16 == 1e16 hit the same slot.

• An inline int, and any integral float in range, hashes as its i64 value.
• Only non-integral floats hash their f64 bits. Hashing float bits directly would funnel small integers, whose low mantissa bits are zero, into one FxHasher bucket. Int-keyed lookups would degrade to O(n²).
• FxBuildHasher uses a fixed seed. Iteration order is reproducible across runs.

The heap is a Vec<HeapSlot> arena. Its free list is capped at 524,288 entries and sorted to prefer low indices.

• Side hashes intern names and string constants up to 128 bytes, one-character strings, bytes up to 128 bytes, all LongInts, and bound methods.
• Equal interned values share one slot. is holds between them, as it does for equal inline numbers.
• Strings built at run time are not interned.

The heap counts what it holds against the memory limit of the run, see Sandboxed execution.

The main HeapObj variants are Str, Bytes, LongInt, List, Dict (insertion-ordered), Set, FrozenSet, Tuple, Func, Range, Slice, Type, ExcInstance, BoundMethod, NativeFn, Class, Instance, BoundUserMethod, Super, Property, StaticMethod, ClassMethod, Coroutine, Module, Iter, Cell, and Extern.

Garbage collection

Collection triggers when live >= gc_threshold or alloc_count >= max(live / 4, alloc_limit). After each sweep the thresholds reset, with marked the values the last mark visited.

gc_threshold = max(live * 2, 512, marked / 4)
alloc_limit  = max(marked / 4, 4096)

The roots are these.

• The value stack, the with-stack, yields, and the event queue.
• The pending yield from value.
• The slots of every running frame, and slot templates.
• Module binding tables, and cells around class bodies.
• Parked scheduler coroutines and iterator frames.
• Chunk constant pools, inline-cache values, and memoisation entries.

Coroutine dispatch

async def and a def that holds yield both compile to HeapObj::Coroutine. The primitives a program sees are in Async.

A plain def inside a coroutine can call a builtin that yields. Its state (ip, slots, stack and iterator deltas) is then saved as a SyncFrame on the sync_frames of the enclosing coroutine, innermost last.

• Resume walks this stack from the inside out before it enters the outer body again. The return value of each helper lands at its original Call site.
• An error that escapes a helper raises again at that same site. The handlers of the caller and the traceback notes match a run that never suspended.

vm.run() wraps the module body as an implicit coroutine. Top-level statements suspend like async def bodies. Dispatch has a single driver, and top_loop is the only place that picks coroutines.

run, gather, with_timeout, await, and calling a coroutine value all work the same way. They push targets to the scheduler, park the caller in CoroState::WaitingForChildren, and yield. The WaitKind picks how the wait finishes.

When the children finish, the result replaces the saved stack placeholder of the outer coroutine and the outer is marked ready.

A child error, a timeout or a failed host call marks it CoroState::Raising instead. The next resume raises the error at the park point. Handlers and the traceback position follow the normal path.

Coroutines carry their own try and except frames across yields. On entry the stored frames are denormalised onto the live exception stack.

On a yield they are renormalised and saved. That is how try: run(coro) except E: catches the raise of a child across several resume cycles.

Snapshots

A snapshot holds only the dynamic state of a parked VM. The blob format is in Blob layout.

• save_state writes Val bits verbatim. Heap slots come back at identical indices. References, cycles and interning survive with no remapping.
• restore_state replays the blob onto a VM booted fresh from the source the blob embeds.
• Chunk-derived tables such as the bytecode, the name pools and the extern table are not stored. They come from the re-parse.

Preemption supplies the parked state when a program never suspends on its own. set_preempt_interval(n) makes the dispatch loop sample a counter at loop back-edges. Every n hits it takes the ordinary yield path, the coroutine stays ready, and top_loop returns Preempted.

Sampling is gated on a frame_safe flag per frame. Only the dispatch Call path and the scheduler step ever set it. Native re-entry cannot be preempted by default, and a new re-entrant path inherits that default instead of corrupting a blob.

Restore runs in two passes, because hashing reads the heap.

1. Every slot is materialised. Sets and frozensets land empty.
2. A rehash pass rebuilds the dict indexes and fills the sets. rebuild_mro recomputes the linearization of each class.

Inline caches and memoisation tables start empty and warm lazily. Extern handles resolve by name against the extern table of the re-parsed chunk.

Host-side resources such as in-flight host calls and DOM handles are not part of the snapshot. state_globals and state_stack inspect a parked run without resuming it. The feature as a program sees it is in Snapshots.

A coverage-guided fuzzer drives the lexer, the parser, the VM and this snapshot round trip every day, see Runbook.

What the compiler intentionally does not do

• No SSA-wide constant propagation through LoadName. The names stay. That keeps the inline cache, fusion and memoisation paths fast.
• No CSE, GVN, LICM, inlining, branch DCE, or loop folding. The optimiser does constant folding, phi-noop elimination, and dead-instruction compaction with jump-operand remap.
• No JIT. A method JIT needs stencils per architecture, and a tracing JIT duplicates the execution model and complicates the GC.
• No runtime module system. Imports resolve at parse time through a resolver the host injects. See Modules.
• No bigints, complex numbers, bytearray, memoryview, Decimal, or Fraction.
• No gen.send, throw or close, and no asyncio module. The concurrency primitives are top-level builtins, see Async.

References

1. Aho, Sethi & Ullman. Compilers. Principles, Techniques and Tools (1986). LUT-based lexer.
2. Pratt. Top Down Operator Precedence (POPL 1973).
3. Cytron et al. Efficiently Computing Static Single Assignment Form (TOPLAS 1991).
4. Gudeman. Representing Type Information in Dynamically Typed Languages (1993). NaN-boxing.
5. Deutsch & Schiffman. Efficient Implementation of the Smalltalk-80 System (POPL 1984). Inline caching.
6. Shi et al. Virtual Machine Showdown. Stack Versus Registers (VEE 2005). Register lowering.
7. Casey et al. Towards Superinstructions for Java Interpreters (SCOPES 2003). LoadAttr+Call fusion.
8. Michie. Memo Functions and Machine Learning (Nature 1968). Pure-function memoization.
9. McCarthy. Recursive Functions of Symbolic Expressions (CACM 1960). Mark-sweep GC.