compiler 0.0.2-preview.1
The Zena self-hosted compiler
compiler#
The Zena compiler, written in Zena. It parses, type-checks, and compiles Zena source code to WebAssembly (Wasm GC) and WebAssembly Text (WAT).
Usage#
Parsing a Single File#
Use compiler/parser to parse Zena source text into an AST (Module):
import { parse } from 'compiler/parser';
let ast = parse('export let answer = 42;', 'example.zena');
Loading and Checking a Program#
Use compiler (createCompiler and checkCompilation) with a CompilerHost to resolve imports across a module graph and type-check a program:
import {
createCompiler, checkCompilation, buildStdlibConfig
} from 'compiler';
import { FsCompilerHost } from 'compiler/fs-host';
let stdlibRoot = '/stdlib';
let host = new FsCompilerHost(stdlibRoot);
let packages = buildStdlibConfig(stdlibRoot, 'host');
let compiler = createCompiler(host, {
stdlibRoot,
packages,
});
let result = await compiler.compile({
entry: '/workspace/main.zena',
target: 'host',
});
let checked = checkCompilation(result);
Compiling a File to WebAssembly#
Use compiler/compile-file to compile an entry file on disk to a .wasm or .wat output file:
import { compileFile } from 'compiler/compile-file';
let ok = await compileFile({
entry: 'src/main.zena',
outPath: 'out/main.wasm',
stdlibRoot: '/stdlib',
});
Libraries#
compiler/compiler/compiler— compiler entry point (Compiler,createCompiler,checkCompilation,ProgramCheckResult)compiler/compile-file— end-to-end file compilation (compileFile,CompileFileOptions)compiler/tokenizer— lexer and token definitions (tokenize,Token,TokenType)compiler/parser— recursive-descent parser (parse,Parser)compiler/ast— AST node definitions (Node,Module,Statement,Expression,TypeAnnotation)compiler/visitor— AST traversal helpers (walk,Visitor)compiler/scope— lexical scope and symbol resolution (ScopeBuilder,ScopeResult,Symbol)compiler/checker— static type checker (checkModule,CheckResult)compiler/semantic-model— semantic queries over a checked module (SemanticModel)compiler/types— compiler type representations (Type,ClassType,FunctionType,typeToString)compiler/diagnostics— compiler diagnostics and source spans (Diagnostic,DiagnosticCode,DiagnosticSeverity,SourceSpan)compiler/package-manifest—zena-package.jsonmanifest and workspace loader (loadWorkspace,loadPackageMap)compiler/module-resolver— package and relative module specifier resolution (ModuleResolver,PackageConfig)compiler/library-loader— module graph loader (LibraryLoader,CompilerHost,SourceFile)compiler/codegen/binary-generator— WebAssembly GC binary emitter (BinaryGenerator)compiler/codegen/wat-generator— WebAssembly Text (WAT) emitter (WatGenerator)
License#
MIT
# Reachability Analysis & Codegen Specialization (RTA)
This directory implements the whole-program reachability analysis and monomorphization/specialization pass for the Zena self-hosted compiler.
## Design Overview
In WebAssembly GC, having concrete struct and vtable definitions is required before code generation. To minimize the compiled code size and Wasm type section complexity, Zena utilizes a whole-program reachability analysis that performs **Rapid Type Analysis (RTA)**.
Instead of generating structures and function signatures for every class/interface or generic overload, the reachability pass starts at entry point roots (e.g. `main` or exports) and iteratively traverses reached functions and types. As new instantiations (`new Point()`) and dynamic dispatches are encountered, the pass resolves implementing virtual method overloads and queues them for traversal.
## Component Subsystems
To keep the codebase maintainable and maintain low AST traversal overhead, the reachability analysis is broken down into four cooperating modules:
```mermaid
graph TD
Analysis["ReachabilityAnalysis (analysis.zena)"]
Visitor["ReachabilityVisitor & TypeLowerer (visitor.zena)"]
Specializer["Specializer (specialization.zena)"]
CHA["ClassHierarchyAnalysis (hierarchy.zena)"]
Analysis -->|Delegates AST walks| Visitor
Analysis -->|Triggers specialization| Specializer
Analysis -->|Queries class hierarchies| CHA
Specializer -->|Queries subclass implementations| CHA
Visitor -->|Discovers types / registers methods| Specializer
```
### 1. Central Coordinator: `ReachabilityAnalysis` (`analysis.zena`)
- Main entry point that manages RTA traversal queues (`reachableQueue`, `checkableQueue`).
- Configures and instantiates the helper subsystems in its constructor.
- Coordinates the overall compilation passes:
- Pre-registers declared types to handle circular definitions.
- Walks traversed functions iteratively until no new reachable symbols/methods are found.
- Performs structural linker steps like linking base class vtables and resolving property getters/setters.
### 2. AST Visitor & Type Lowerer: `ReachabilityVisitor` & `TypeLowerer` (`visitor.zena`)
- **`ReachabilityVisitor`**: Traverses reached function and method bodies, discovering global dependencies, closures, and interface usage, and queues any newly referenced virtual members.
- **`TypeLowerer`**: Resolves structural types (`RecordType`, `TupleType`, etc.), array classes, and class/interface types to concrete WebAssembly types.
- **A reached body is walked one of two ways.** A body the checker
recorded dependencies for gets `registerLiterals` and
`registerInstantiations`, with the records standing in for the rest;
any other body gets the full `discoverNodeTypes` walk. The records
name symbols only: they hold no instantiations, string literals or
interface members. So a new fact RTA collects from nodes has to be
collected in both walks, as `noteInterfaceDispatch` is.
- **Look a member access up by `accessKeyOf(model, expr)`**
(`semantic-model.zena`). A member declared with a symbol is keyed by
that symbol's identity (`:act_368`), which only the checker can
resolve and which it records on the access node. A key built as
`":" + property.name` matches only the symbols the compiler invokes
itself (`:dispose`, `:iterator`), whose keys are fixed
(`SymbolType.protocolKey`).
### 3. Monomorphizer: `Specializer` (`specialization.zena`)
- Performs generic class and interface specialization.
- Maintains lists of instantiated classes. When a generic class is instantiated, it generates specialized vtables, structs, and physical methods corresponding to that concrete type argument combination.
- Instantiates specialized generic function signatures.
### 4. Class Hierarchy Analysis: `ClassHierarchyAnalysis` (`hierarchy.zena`)
- Manages caches for subclass relationships (`isSubclassOf`).
- Resolves dynamic overrides, locating the concrete `MethodDefinition`, `AccessorDeclaration`, or `FieldDefinition` that implements a virtual slot on a subclass.
- Collects implementing interfaces transitively.
## An Erasure Is Not a Specialization
A type parameter lowers to `anyref`, so `Store<K, V>` named from inside
generic code is discovered as `Store<anyref, anyref>` — which
`isConcrete` accepts, because anyref is a type (and a real one:
`let x: anyref = "hi"`). It must not become a specialization. Every
value the mention stands for is some real specialization, discovered on
its own, while believing in the erasure makes it a fan-out target for
every reached member of the generic class and, once instantiated, gives
it a class vtable global whose slots force-reach an erased body of every
method — none of which lower when the class uses `hash`/`eq`, which
dispatch on their operand's type.
The mentions that fabricate one are plumbing, not code that runs:
`#linkSuperAndVT` naming a subclass template's supertype, and the walk
of a generic class's own template naming its field types.
`containsErasedType` (in `codegen-utils.zena`) is what asks whether a
type IS an erasure — `ErasedType` in `types.zena` is a distinct
codegen-internal type, so this is a fact about the type rather than a
guess about which walk produced the mention. The erased class's struct
is still registered, because erased signatures and fields refer to it.
Nothing is emitted at an erasure, including the erasure of a generic
FUNCTION. `fill<T>(v)` named from inside `outer<T>`'s body is not a call
site, it is the template of one: every value it stands for belongs to
some `fill<i32>` a real call site names. `noOpenTypeParameters`
(`visitor.zena`) refuses to specialize on arguments that are still bare
type parameters, so `fill_spec_erased` is never minted, and with it goes
the only thing that ever ran `new Full<T>` as `new Full<erased>`.
`walkingTemplateOf` does not cover this and structurally cannot: it is
`ClassType | null`, set only for a non-concrete class referrer, so it is
always null while walking a generic top-level function.
So `registerSpecializedClass` stops after the struct for an erasure — no
vtable slots, no methods, no constructor — `#buildClassInterfaceVTables`
skips it (an erasure passes `isConcrete` but has nothing to put in a
trampoline slot), and a member referrer whose class is an erasure
registers nothing. The struct itself is still registered, because erased
signatures and fields name it.
The two halves check each other. Mint an erased function specialization
without the class half and lowering fails loudly — `constructor missing
for Full_s867_erased @fill_spec_erased` — instead of emitting a dead
body that happens not to be called. In the compiler's own module this
removed 87 functions (15,155 → 15,068), every one of them unreferenced
from any non-erased body.
A trap when measuring this: `getTypeKeyForSpecialization` maps a bare
`TypeParameterType` and an `ErasedType` to the SAME key, `"erased"`. So
`fill_spec_erased` may have been minted with a raw `T` and never an
`ErasedType` at all, and a `containsErasedType` probe will not see it.
`Array<T>` and `Array<erased>` are likewise one class,
`Array_s777_erased` — which is why `containsErasedType` answers true for
a bare type parameter too.
## A Specialization Is Keyed by Representation and Ownership
`getTypeKeyForSpecialization` keys a type alias by its target and an
enum by its backing type, except for the aliases that decide what a
body may do with a value (`specializesApart`): `Borrow<R>` and
`Unmanaged<R>` on a restricted type, which key apart from `Own<R>` (that
is, `R`), and `Scoped<T>`, which keys apart from `T`. So `C<Own<R>>`,
`C<Borrow<R>>` and `C<Unmanaged<R>>` are three specializations of `C`
with one layout, and a body's `T` names its instantiation's own handle.
See owner-futures.md §"Specialization".
Three things have to agree for that to hold, and a new key or erasure
has to keep them agreeing:
- **The erasure of a type argument.** `eraseTypeParameters` erases a
handle to its resource, which is right for a value's type and wrong
for a type argument, since discovery registers specializations from
erased types and lowering often looks them up unerased. Class,
interface and mixin arguments go through `eraseTypeArgument`
(`type-mapping.zena`), which keeps the aliases a key keeps, inside
tuples, unions, records, arrays and function types too. So inside a
specialization `Own<R>` reads as a bare `R`, and `holdsOwner`
(`types.zena`) counts a bare resource class as an owner.
- **The discovery key.** `getTypeUniqueKey` dedupes discovered types.
An alias instance's target is its declaration's `T`, the same for
every handle, so it keys a kept-apart alias by its kind and what it
wraps.
- **The specialization key** above.
An alias instance keeps its declaration's unsubstituted target, so
"its target" means `instantiatedAliasTarget` (`codegen-utils.zena`):
for `opaque type Own<T> = T` and the other handles, the argument. Read
as the bare target, every handle was the erasure of `T`, and a generic
function called at one was minted as an erasure (#789). `isConcrete`
and `containsErasedType` read it the same way.
The hybrid mode planned in docs/design/generic-specialization-strategy.md,
which shares one body across reference type arguments, keeps this axis:
arguments share a body only within one ownership kind.
## A Synthesized Member Is Replayed by Name
A member reached on a generic class is recorded against the generic
and replayed for each specialization that arrives later
(`recordReachedClassMember`, `noteSpecialization`), keyed by its AST
node. A member the checker synthesized has no node: a case class's
`==` and `hashCode`, and a release member (`:dispose` of a resource
with only owner fields, `[release]` of a `scoped T` class). A reached
release is recorded by class (`#reachedSyntheticReleases`) and
`noteSpecialization` replays it before its duplicate check, since
discovery can list a specialization that is only instantiated later.
Read the synthesized flag off the declaration, `synthesizedRelease(ct)`,
never off an instantiation: an instantiation copies
`hasSyntheticRelease` when it is made, and one made before its class
finished registering (`Some<T>` while `zena:core` registers) holds a
stale false.
## A Generic Method Exists Only Per Specialization
A method's OWN type parameters are a separate axis from its class's.
`registerGenericMethodUse` mints `map_spec_i32` per call site; the
unspecialized registration — the body at the method's erasure — is not
a function, so:
- it gets no class-vtable slot (a slot is one `ref.func` of one
signature, and a generic method has no single signature), and
- the member referrer in `processQueues` does not reach it
(`isGenericAtErasure`).
Emitting it anyway put one dead body per specialization of the class in
every module (80 `Array<X>.map` in the compiler's own, referenced by
nothing), and those bodies' `new Array<R>` were the only thing that ever
made an erasure look constructible — which is why the rule above can be
flat. It is also what `zir unsupported: method not found` found where a
specialization should have been. See §15 of
`docs/design/binary-size.md`.
Virtual calls follow the same per-specialization rule on both interfaces
and classes:
- **Interface receivers**: a generic method called through an
interface-typed receiver records a `GenericInterfaceMethodDemand`
(visitor → `demandGenericInterfaceMethod`), and each demand becomes
one interface vtable slot named by the same `getSpecializedName`
mangle. Slots are appended and per-class trampolines built inside the
`#buildClassInterfaceVTables` fixpoint — a class can join a demand's
interface in any round, so the fan-out to implementing classes happens
at trampoline build, not at demand time. Trampolines adapt covariant
class-typed results (pack through the pair vtable) and `this`-narrowed
callback parameters (a synthesized closure forwarder). See
`docs/design/generic-interface-dispatch.md`.
- **Class receivers**: a non-static generic method called through a
class-typed receiver records a `GenericClassMethodDemand` rooted at
`getMemberRootClass(targetClass, methName)` (visitor →
`demandGenericClassMethod`). `#syncGenericClassSlots` appends the
specialized slot name to `classVtable` across the root class's
hierarchy, specializes overrides (or registers a vtable slot stub when
abstract) on subclasses, and re-orders laid-out `vtableStructType`
fields root-first so `#fillReachedSlots` and `#pruneUndispatchedSlots`
treat the specialized slot identically to a non-generic method slot.
## An Interface Slot Exists Only When Something Calls It
An interface vtable struct starts empty. A member gets a slot when
reachable code calls it through the interface, recorded by
`demandInterfaceMember`, or through an interface it extends: an upcast
(`repackInterface`) copies the target's slots out of the source's
vtable by name, so `#interfaceLineage` makes a demand on an interface
count for every interface below it. `#syncInterfaceSlots` appends the
slots inside the class-interface vtable fixpoint, and pair vtables
built earlier get trampolines for the new tail. Each slot is a
trampoline per packed class, and each trampoline reaches a method, so
a slot nothing dispatches through used to keep that method and
whatever it constructed (#425). Trampolines are also the only thing
that reaches an implementation through an interface: a class never
packed as an interface cannot be dispatched to through it.
So **a new interface dispatch in lowering needs a demand**, or it
fails with `interface member not in vtable: <member>`. Node-level
dispatches go in `noteInterfaceDispatch` (visitor), which both body
walks run — most bodies get `registerInstantiations` and the checker's
dependency records, not `discoverNodeTypes`, and the records hold no
interface members. Dispatches a construct implies
without naming them (a generator's `next`, an async frame's `run`,
`:toString` in a template) are demanded where that construct is
registered. See §19 of `docs/design/binary-size.md`.
A class-interface vtable exists only for a specialization something
packs. `demandPackPair` marks the pair a pack site resolves to,
`(Box<i32>, Shape<i32>)`, and the vtable phase builds `Box<String>`'s
vtable only if a pack of `Box<String>` marks it too. A pair that still
holds a type parameter or an erasure marks nothing: it comes from a
walk of a generic body under its own parameters, and the walk under
each substitution marks the real pair. Marking the generic pair
instead built 3,749 vtables and 9,487 trampolines in the self-compile,
of which 195 and 812 survived harvest (#815).
## A Class Nothing Reaches Specializes Nothing
`#layoutClassStructs` lays out every declared class in every loaded
module, emitted or not — the layout is what registers a class's
members, and a class can pick up evidence after its turn. But laying
one out walks its members' signatures, and a signature's mention of
`Completer<i32>` is not a `new Completer<i32>()`.
`layingOutUnemittedClass` is set for the classes with no emission
evidence — the same question the type section is rooted from:
instantiated, or named by reached code. Under it a mention still
registers the specialization's struct, because fields and signatures
name it, and stops there: `discoverType` neither instantiates it nor
puts it on the generic's `specializedClassTypes` list.
Being on that list is what makes a specialization travel.
`instantiateClassType` instantiates every listed sibling, and
`recordReachedClassMember` fans each newly reached member of the
generic out over all of them — so one unreachable class's field type
was enough to emit `Completer`, `Future` and `Box` whole at type
arguments no reachable code names. To keep passing over a mention from
losing a real specialization, the list is no longer built by discovery
alone: `noteSpecialization` is also called from `instantiateClassType`,
so a specialization rejoins the register at the `new` that makes it
real. See §18 of `docs/design/binary-size.md`.
## Interface Type Tests Read Per-Class Tables
`x is I`, `x as I` and `case I` mean "the class of `x` implements `I`",
answered from a `TypeInfo` table hung off the class vtable rather than
a `ref.test` of the interface's fat pointer struct, which only says how
the value is held. The visitor records each site with its operand's
static type (`noteTypeTestSites`), `#markTypeTestPairs` turns the sites
into the `(class, interface)` pairs that can answer true once the
instantiated classes are known (inside the late vtable fixpoint, since
each pair needs its class-interface vtable), and `#layoutTypeTests`,
after slot pruning, lays out `TypeInfo`, `VTableBase`, `Object` and
`FatPtrBase` for exactly those classes and orders the globals so the
initializers' `global.get`s point backwards. A program that tests no
interface emits none of it. See `docs/design/interface-type-tests.md`.
## Code Generation Pipeline Integration
The reachability pass is run in [module-generator.zena](../module-generator.zena):
```zena
let pass = new ReachabilityAnalysis(this.program, wasm, this.target);
pass.run();
```
After `pass.run()`, the `WasmModule` contains exactly the functions, struct layouts, and vtable allocations that are actually reached during execution, drastically reducing the Wasm module size.
- zena-lang:wit-parser wit-parser.zena-lang.pkg.zena-lang.dev ~0.0.1-preview.1
| Version | Published | Dependencies | Approved by |
|---|---|---|---|
| 0.0.2-preview.1 | 2026-11-19 |
|
|