compiler 0.0.2-preview.1

The Zena self-hosted compiler

Readme Files Dependencies Versions

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.json manifest 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

17.1 KiB Source Raw

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 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.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.

VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19