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:
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
registerLiteralsandregisterInstantiations, with the records standing in for the rest; any other body gets the fulldiscoverNodeTypeswalk. 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, asnoteInterfaceDispatchis. - 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.namematches 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, orFieldDefinitionthat 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.
eraseTypeParameterserases 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 througheraseTypeArgument(type-mapping.zena), which keeps the aliases a key keeps, inside tuples, unions, records, arrays and function types too. So inside a specializationOwn<R>reads as a bareR, andholdsOwner(types.zena) counts a bare resource class as an owner. - The discovery key.
getTypeUniqueKeydedupes discovered types. An alias instance's target is its declaration'sT, 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.funcof one signature, and a generic method has no single signature), and - the member referrer in
processQueuesdoes 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 samegetSpecializedNamemangle. Slots are appended and per-class trampolines built inside the#buildClassInterfaceVTablesfixpoint — 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) andthis-narrowed callback parameters (a synthesized closure forwarder). Seedocs/design/generic-interface-dispatch.md. - Class receivers: a non-static generic method called through a
class-typed receiver records a
GenericClassMethodDemandrooted atgetMemberRootClass(targetClass, methName)(visitor →demandGenericClassMethod).#syncGenericClassSlotsappends the specialized slot name toclassVtableacross the root class's hierarchy, specializes overrides (or registers a vtable slot stub when abstract) on subclasses, and re-orders laid-outvtableStructTypefields root-first so#fillReachedSlotsand#pruneUndispatchedSlotstreat 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.gets 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:
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 |
|
|