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
241.6 KiB
Raw
import { Program, CompilationUnit } from '../../program.zena';
import {
WasmModule, WasmFunction, WasmSignature, WasmGlobal, WasmStruct, WasmField, WasmArray, VTableInit, ClassCodegenInfo, asWasmSignature, TrampolineParamWrap, ClosureForwarderSpec, ForwarderParamPack, AdaptationPack, isValSubtype, RecordDispatchInfo, existentialCastCandidates,
typeTestSlotName, rootStruct, prependField, typeTestChainMax,
} from '../wasm-module.zena';
import { SemanticModel, SymbolDependencies, memberKeyOf } from '../../semantic-model.zena';
import {
Type, ClassType, InterfaceType, FunctionType, TypeId, makeTypeIdGenerator, TypeParameterType, MethodInfo, FieldInfo, isVoidOrNeverType, UnionType, TupleType, InlineTupleType, InlineParamType, InlineRecordType, ArrayType, RecordType, TypeAliasType, EnumType, TypeListTable, baseType, releaseMemberOf, hasReleaseMember, synthesizedRelease,
ownershipHandleOf, OwnershipHandle, soleNonNullMember,
} from '../../types.zena';
import {
Node, ClassDeclaration, InterfaceDeclaration, MixinDeclaration, MethodDefinition, AccessorDeclaration, FieldDefinition, VariableDeclaration, FunctionDeclaration, DeclareFunction, ImportDeclaration, IdentifierPattern, FunctionExpression, SealedVariant, SourceLocation, Module, Identifier, SymbolPropertyName, MemberExpression, CallExpression, ExportAllDeclaration, ExportFromDeclaration, IdGenerator, ShieldedStatement, TryExpression,
} from '../../ast.zena';
import { capturedInCell } from '../../analysis/capture.zena';
import { Set, HashMap, HashSet } from 'zena:collections';
import { StringBuilder, growable } from 'zena:core';
import {
getClassKey, getInterfaceKey, getClassMethodKey, getClassInterfaceKey, getClassInterfaceVTableName, getClassVTableName, getClassSingletonName, getInterfaceTrampolineName, getSignatureKey, collectMixinMembers, mixinScopeOfMember, mixinModelOfMember, getClassPrivateFieldKey, MixinKey, getFunctionAdaptationKey, ClassKey, ClassMethodKey, getTypeUniqueKey, getClosureSpecializationKey, isConcrete, getSpecializedName, containsErasedType, InterfaceKey, getMemberRootClass,
} from '../codegen-utils.zena';
import {
typeToValType, getClosureStruct, getInterfaceMemberSignature, interfaceMethodOverloads, pushInterfaceMethodSlots, interfaceSlotOverload, interfaceOverloadSignature, InterfaceSlotOverload, mapReturnTypeToWasmResults, mapParamTypeToWasmParams, substituteTypeParamsInCodegen, getClassTypeParameters, scopedFieldTypesAt, getInterfaceTypeParameters, getCellStruct, substituteTypeParamsInClassContext, getGenericInterfaceMemberSignature, getGenericInterfaceMethodType, substituteThisTypeInCodegen, getNonNullableType,
} from '../type-mapping.zena';
import { SymbolId, Symbol, noSymbolId } from '../../scope/symbol.zena';
import {
ValType, ValTypeVoid, ValTypeI32, ValTypeRefNull, ValTypeAnyRef, ValTypeRef, ValTypeStructRef, WasmType, ValTypeFuncRef, valTypeToOpcode, refTargetOf,
} from '../wasm.zena';
import { Referrer, RecordResultCall, ReachabilityContext, SpecializerInterface, TypeLowererInterface, ReachabilityVisitorInterface, GenericInterfaceMethodDemand, GenericClassMethodDemand } from './context.zena';
import { ClassHierarchyAnalysis } from './hierarchy.zena';
import { Specializer, applyMixinPrivateScope } from './specialization.zena';
import { ReachabilityVisitor, TypeLowerer } from './visitor.zena';
import { walkEnter } from '../../visitor.zena';
import { performance } from '../../time.zena';
import {
componentAbiUnitId, componentDriverUnitId
} from '../component-emitter.zena';
import {
targetEmitsComponent, targetUsesJsStrings, targetUsesZenaComponentHost
} from '../../targets.zena';
import { isHostBoundaryLibrary, isWebUiProtocolLibrary } from '../../stdlib-manifest.zena';
import {
isComponentEntryPath, componentSyncExportSuffix, componentEntryRunName,
hasAsyncMain
} from '../../component-entry.zena';
import { WellKnown, isWellKnown, wellKnownName } from '../../well-known.zena';
final class ParsedMethodRef {
classSymId: SymbolId;
mName: String;
new(this.classSymId, this.mName);
}
final class ParsedAdaptationRef {
classSymId: SymbolId;
ifaceSymId: SymbolId;
new(this.classSymId, this.ifaceSymId);
}
/**
* Every field-decorator application in `ct`'s superclass chain whose
* declaration body contains `node`. A decorator applied to two fields of
* one class puts two intermediates in the chain that share one body, so
* a node alone names all of them (docs/design/decorators.md). Empty when
* `node` is not a decorator's member.
*/
function findDecoratorIntermediates(ct: ClassType, classDecls: HashMap<SymbolId, Node>, node: Node) {
let found = new Array<ClassType>();
var scWalk = ct.superType;
while (scWalk != null && scWalk.isMixinIntermediate) {
let sc = scWalk;
if (sc.decoratorSubjectName != null) {
let scId = (sc.genericSource ?? sc).symbolId;
if (classDecls.has(scId)) {
let scDecl = classDecls[scId];
if (scDecl is MixinDeclaration) {
for (let m in (scDecl as MixinDeclaration).body) {
if (m === node ||
(m is AccessorDeclaration &&
((m as AccessorDeclaration).setter as Node) === node)) {
found.push(sc);
break;
}
}
}
}
}
scWalk = sc.superType;
}
return found;
}
function findDeclaringMixinIntermediate(ct: ClassType, classDecls: HashMap<SymbolId, Node>, node: Node): ClassType | null {
var scWalk = ct.superType;
while (scWalk != null && scWalk.isMixinIntermediate) {
let sc = scWalk;
let scId = (sc.genericSource ?? sc).symbolId;
if (classDecls.has(scId)) {
let scDecl = classDecls[scId];
if (scDecl is MixinDeclaration) {
for (let m in (scDecl as MixinDeclaration).body) {
if (m === node) {
return sc;
}
if (m is AccessorDeclaration &&
((m as AccessorDeclaration).setter as Node) === node) {
return sc;
}
}
}
}
scWalk = sc.superType;
}
return null;
}
/**
* ReachabilityAnalysis manages the whole-program reachability tracking,
* driving queues of reachable functions/types and triggering monomorphization.
*/
/**
* A referrer naming a node or symbol, within at most a class, as one
* i64: the class's uid, then the symbol/node distinction, then the id
* offset into the non-negative range, each in its own bits. Referrers
* carrying type arguments are keyed by string instead.
*/
function referrerKey(isSymbol: boolean, id: i32, ct: ClassType | null) {
let ctUid = if (ct != null) (ct as ClassType).uid else 0;
let sym: i64 = if (isSymbol) 1 else 0;
return ((ctUid as i64) * 2 + sym) * 4294967296 + ((id as i64) + 2147483648);
}
/** Whether method `mi` has type parameters of its own. */
function isGenericMethod(mi: MethodInfo): boolean {
let ft = mi.type;
if (ft is FunctionType) {
let {typeParameters} = ft;
return typeParameters != null && typeParameters.length > 0;
}
return false;
}
/**
* The type a non-generic alias names. A generic alias keeps its
* unsubstituted target, so it stays as it is.
*/
function unwrapPlainAlias(t: Type): Type {
var u = t;
while (u is TypeAliasType && (u as TypeAliasType).typeParameters == null) {
u = (u as TypeAliasType).target;
}
return u;
}
export final class ReachabilityAnalysis implements ReachabilityContext {
program: Program;
wasm: WasmModule;
target: String;
var #chaBacking: ClassHierarchyAnalysis | null = null;
var #specializerBacking: SpecializerInterface | null = null;
var #typeLowererBacking: TypeLowererInterface | null = null;
var #visitorBacking: ReachabilityVisitorInterface | null = null;
cha: ClassHierarchyAnalysis {
get { return this.#chaBacking as ClassHierarchyAnalysis; }
}
specializer: SpecializerInterface {
get { return this.#specializerBacking as SpecializerInterface; }
}
typeLowerer: TypeLowererInterface {
get { return this.#typeLowererBacking as TypeLowererInterface; }
}
visitor: ReachabilityVisitorInterface {
get { return this.#visitorBacking as ReachabilityVisitorInterface; }
}
// Global lookups
classDecls = new Map<SymbolId, Node>();
classModels = new Map<SymbolId, SemanticModel>();
interfaceDecls = new Map<SymbolId, InterfaceDeclaration>();
interfaceModels = new Map<SymbolId, SemanticModel>();
symbolIdToModel = new Map<SymbolId, SemanticModel>();
symbolIdToDecl = new Map<SymbolId, Node>();
symbolIdToTargetId = new Map<SymbolId, SymbolId>();
nodeIdToNode = new Map<i32, Node>();
nodeIdToModel = new Map<i32, SemanticModel>();
// RTA Reachability tracking state
reachedGlobals = new Set<SymbolId>();
recordLiteralArgs = new Set<i64>();
recordLiteralCtorArgs = new Set<String>();
recordLiteralMethodArgs = new Set<String>();
recordLiteralSpecArgs = new Set<String>();
recordResultCalls = new Array<RecordResultCall>();
recordResultCallIds = new Set<i32>();
/**
* Method and generic function calls with a record result, by call id
* and target, recorded once each.
*/
recordResultMethodCalls = new Set<String>();
reachedMembers = new Set<String>();
/**
* Members traversed with `currentReachable` set, tracked apart from
* `reachedMembers` for the same reason `queueReferrer` keeps
* `reached` apart from `visited`: a checkable-phase traversal
* discovers a member's dependencies without marking them reached, so
* it must not satisfy a later reachable traversal of the same member.
*/
reachedReachableMembers = new Set<String>();
instantiatedClasses = new Set<SymbolId>();
instantiatedSpecializedClasses = new Set<String>();
reachablyNamedClasses = new Set<String>();
/** See ReachabilityVisitor.noteEqualityUse. */
var equalityDispatchUsed = false;
/**
* The closed record types an `as` converts an existential to when they
* name fields it does not know: the run time finds the record among
* the shapes packed into existentials (`#finishExistentialCasts`).
*/
existentialCastTargets = new Array<RecordDispatchInfo>();
noteExistentialCastTarget(target: RecordDispatchInfo): void {
for (let t in this.existentialCastTargets) {
if (t === target) {
return;
}
}
this.existentialCastTargets.push(target);
}
/**
* A table reading each run-time `as` target through every packed shape
* that has its fields. Runs once discovery has settled, when every pack
* the program makes is known; the tables reach nothing new.
*/
#finishExistentialCasts(): void {
let model = this.program.units[0].model;
for (let target in this.existentialCastTargets) {
for (let source in existentialCastCandidates(this.wasm.existentialPacks, target)) {
if (source !== target) {
this.wasm.getForwardDispatch(model, source, target);
}
}
}
}
/** Generic-source symbols with at least one `new` site; see queueExplicitCtor. */
ctorDemandedGenerics = new Set<SymbolId>();
/**
* Members to reach BY MAP KEY at the settle point, once every
* registration has happened: field accessors named before populate
* creates them, synthesized case-class ==/hashCode (no AST node to
* find), demanded constructors, and String.== for the by-name
* lowering paths. While registration force-reached every method
* this timing hole was invisible.
*/
#pendingMemberReaches = new Array<ClassMethodKey>();
/**
* How many of `#pendingMemberReaches` have been reached: -1 until the
* first drain, which waits for populate to register the members.
*/
var #pendingDrained = -1;
reachablyNamedClosures = new Set<WasmStruct>();
reachablyNamedAnonStructs = new Set<WasmStruct>();
/**
* Record/tuple SEMANTIC types named in-queue, resolved to their
* dispatch/struct at the settle point — resolving eagerly would call
* typeToValType before nested dispatches exist. Insertion-ordered
* array + key set: iteration order must not depend on Type.hashCode,
* which is a process-global uid (the batch-nondeterminism bug).
*/
#namedCompositeTypes = new Array<Type>();
#namedCompositeKeys = new Set<String>();
/**
* True only while a queue referrer is being processed —
* currentReachable is accurately set per referrer there, and there
* alone. Everything else (init, layout, vtable passes, helper
* ensures) runs with whatever the last referrer left behind, which
* is exactly the ambient-phase hazard binary-size.md documents.
* Naming evidence is only collected when this is true.
*/
var inQueueWalk = false;
var suppressNameEvidence = false;
/** See ReachabilityContext.layingOutUnemittedClass. */
var layingOutUnemittedClass = false;
/** See ReachabilityContext.walkingTemplateOf. */
var walkingTemplateOf: ClassType | null = null;
var isRtaActive = true;
/**
* The members reachable code calls through an interface, keyed
* "<symbol id of the interface declaration>.<member name>".
*/
#demandedInterfaceMembers = new Set<String>();
var #arrayPatternReached = false;
/** The symbol ids of each interface declaration and those it extends. */
#interfaceLineages = new Map<SymbolId, GrowableArray<SymbolId>>();
/** Interface members given slots, keyed "<interfaceKey>|<member name>". */
#slottedInterfaceMembers = new Set<String>();
/** What #syncInterfaceSlots last looked at; see there. */
var #interfaceSlotSyncState = -1;
discoveredTypes = new Set<String>();
reachedSemanticTypes = new Set<String>();
specializedInterfaces = new Array<InterfaceType>();
genericInterfaceMethodDemands = new Array<GenericInterfaceMethodDemand>();
/** Demands keyed "<interfaceKey>.<slotName>" for dedup and slot lookup. */
#genericInterfaceDemandsByKey = new Map<String, GenericInterfaceMethodDemand>();
genericClassMethodDemands = new Array<GenericClassMethodDemand>();
/** Demands keyed "<rootClassKey>.<slotName>" for dedup. */
#genericClassDemandsByKey = new Map<String, GenericClassMethodDemand>();
specializedClassTypes = new Map<SymbolId, GrowableArray<ClassType>>();
reachedClassMembers = new Map<SymbolId, HashMap<i32, boolean>>();
reachedReachableClassMembers = new Map<SymbolId, HashMap<i32, boolean>>();
/** The generic classes whose synthesized release member was reached. */
#reachedSyntheticReleases = new Set<SymbolId>();
var mixinToClasses = new Map<MixinKey, GrowableArray<ClassType>>();
#preludeClassCache = new Map<i32, ClassType>();
#preludeInterfaceCache = new Map<i32, InterfaceType>();
reachableQueue = new Array<Referrer>();
checkableQueue = new Array<Referrer>();
var reachHead = 0;
var checkHead = 0;
var globalsHead = 0;
// Referrers seen, keyed two ways: packed into an i64 when the referrer
// names a node or symbol within at most a class, which is nearly all
// of them, and by string when it carries type arguments too.
visitedIds = new Set<i64>();
reachedIds = new Set<i64>();
/**
* The referrers carrying type arguments, by the same i64 and then
* the arguments' identities; the entry's marks hold visited (1) and
* reached (2).
*/
genericReferrers = new Map<i64, TypeListTable>();
reachedFunctionsSet = new Set<WasmFunction>();
reachedTypesSet = new Set<WasmType>();
emittedTypes = new Array<WasmType>();
/**
* Cell structs interned for `try`-body-assigned locals. Closure cells
* reach the type section through their context struct's field type;
* these have no such referrer — only the lowered body's struct.new —
* so layout roots them explicitly.
*/
tryCellStructs = new Array<WasmStruct>();
/**
* Interfaces something is actually packed into — recorded when a
* class-interface vtable global is built. Their fat-pointer and
* vtable structs are referenced from lowered pack sites, which run
* after layout and so are invisible to signature-driven type
* reachability, exactly like closure structs.
*/
usedInterfaceTypes = new Array<InterfaceType>();
/**
* Set once struct layout begins. After that point a class that has
* never been instantiated cannot become instantiated: Pass 1.05
* populates every known class's struct exactly once, so a late
* arrival would carry an empty layout and fail somewhere further on
* — as `$stringCreate layout` and `operator dispatch` both did.
* Closing it turns that into a named error at the point of the bug.
*/
var instantiationClosed = false;
var currentReachable = true;
/** Whether a reached body can cause a cancellation (a call to
* TaskGroup's cancel) — the whole-program gate the async machinery is
* emitted under. Aggregated from dependency records as bodies are
* reached; `#activateCancellationMachinery` reacts to it at each
* fixpoint juncture. */
var cancellationPossible: boolean = false;
/** Whether the machinery has been minted and queued. */
var cancellationMachineryActive: boolean = false;
/** Whether a reached body has a `for`-in through the Iterator
* protocol — half of the generator-disposal gate. */
var iteratorForInReached: boolean = false;
/** Whether a reached body creates a generator — the other half. */
var generatorReached: boolean = false;
/** Whether a reached body creates an async generator (`async gen`).
* Together with `iteratorForInReached`, this also enables scope
* cancellation so `for await` disposal cancels in-flight async work. */
var asyncGeneratorReached: boolean = false;
/** Every async function's frame Future instantiation, recorded so a
* cause discovered late can still equip every frame. */
asyncFrameFutures = new Array<Type>();
asyncFrameFutureModels = new Array<SemanticModel>();
/**
* Mints the tag and queues the scope machinery for every recorded
* async function, once, when a cancellation cause has been reached.
* Called between queue drains: a cause can surface in any round,
* and the machinery's own members never introduce one, so the
* fixpoint still terminates.
*/
activateCancellationMachinery(): void {
if (this.iteratorForInReached && this.asyncGeneratorReached) {
this.cancellationPossible = true;
}
if (this.cancellationMachineryActive || !this.cancellationPossible) {
return;
}
if (!this.program.unitsByPath.has('zena:async')) {
return;
}
this.cancellationMachineryActive = true;
this.wasm.ensureCancellationInfra();
this.wasm.scopeCancellationActive = true;
var i = 0;
while (i < this.asyncFrameFutures.length) {
this.visitor.queueCancellationMachinery(
this.asyncFrameFutures[i] as ClassType,
this.asyncFrameFutureModels[i]);
i += 1;
}
}
/**
* Opens the generator-disposal gate: a reached protocol `for`-in in
* a program that also creates a generator means a loop may be
* handed one and leave early. The tag is minted alone — disposal
* raises and catches it entirely inside a generator's `next()`, so
* none of the scope machinery is queued (`scopeCancellationActive`
* stays with the causes gate). Called at the late-fixpoint juncture
* because the exception-infra mint queues reaches that the next
* drain must pick up; the split pass and the for-in lowering read
* the flag after RTA.
*/
activateGeneratorDisposal(): void {
if (this.wasm.generatorDisposalActive ||
!this.iteratorForInReached || !this.generatorReached) {
return;
}
this.wasm.generatorDisposalActive = true;
this.wasm.ensureCancellationInfra();
// The for-in disposal finalizer is a full finally region: its
// throw arm needs the exception infrastructure even in a program
// that never throws.
this.noteExceptionInfra(this.program.units[0].model);
}
parsedClassMethodRefs = new Map<String, ParsedMethodRef>();
parsedAdaptationRefs = new Map<String, ParsedAdaptationRef>();
var typeIdGenerator = makeTypeIdGenerator(1);
new(this.program, this.wasm, this.target = "core") {
this.wasm.target = this.target;
var idGen: IdGenerator<TypeId> | null = null;
let {entryPoint} = program;
if (entryPoint != null) {
idGen = (entryPoint as CompilationUnit).model.typeIdGenerator;
} else if (program.units.length > 0) {
idGen = program.units[0].model.typeIdGenerator;
}
if (idGen != null) {
this.typeIdGenerator = idGen;
}
this.#chaBacking = new ClassHierarchyAnalysis(this.program, this.instantiatedSpecializedClasses, this.wasm, this.classModels);
this.#specializerBacking = new Specializer(this);
this.#typeLowererBacking = new TypeLowerer(this);
this.#visitorBacking = new ReachabilityVisitor(this);
}
recordReachedClassMember(classSymId: SymbolId, nodeId: i32, model: SemanticModel, isReachable: boolean): void {
if (isReachable) {
if (!this.reachedReachableClassMembers.has(classSymId)) {
this.reachedReachableClassMembers[classSymId] = new Map<i32, boolean>.ordered();
}
let set = this.reachedReachableClassMembers[classSymId];
if (!set.has(nodeId)) {
set[nodeId] = true;
if (let (true, specList) = this.specializedClassTypes.get(classSymId)) {
for (let specCt in specList) {
this.queueReferrer(new Referrer(false, noSymbolId, nodeId, model, specCt, true));
}
}
}
} else {
if (!this.reachedClassMembers.has(classSymId)) {
this.reachedClassMembers[classSymId] = new Map<i32, boolean>.ordered();
}
let set = this.reachedClassMembers[classSymId];
if (!set.has(nodeId)) {
set[nodeId] = true;
if (let (true, specList) = this.specializedClassTypes.get(classSymId)) {
for (let specCt in specList) {
this.queueReferrer(new Referrer(false, noSymbolId, nodeId, model, specCt, false));
}
}
}
}
}
/**
* Record a concrete specialization of a generic class, and fan the
* members already reached on the generic out over it.
*
* This is the register of specializations the program asks for. It
* is what carries a member reached on the template to every
* specialization, and what `instantiateClassType` walks to
* instantiate a generic's siblings, so a specialization listed here
* is one the module will emit. Discovery lists a mention; a mention
* from a class nothing reaches is not listed, and instantiation
* lists whatever it instantiates — so a specialization that becomes
* real after being passed over still arrives.
*/
noteSpecialization(ct: ClassType, model: SemanticModel): void {
let lookupId = (ct.genericSource ?? ct).symbolId;
if (!this.specializedClassTypes.has(lookupId)) {
this.specializedClassTypes[lookupId] = new Array<ClassType>();
}
// Before the duplicate check: discovery can list a specialization
// the release was reached for only once it is instantiated, which
// notes it again.
if (this.#reachedSyntheticReleases.has(lookupId)) {
this.notePendingMemberReach(getClassMethodKey(getClassKey(ct), releaseMemberOf(ct)));
}
let list = this.specializedClassTypes[lookupId];
let ctKey = getClassKey(ct);
for (let existing in list) {
if (getClassKey(existing) == ctKey) { return; }
}
list.push(ct);
if (let (true, reachedSet) = this.reachedClassMembers.get(lookupId)) {
let rcKeys = reachedSet.keys();
for (let nid in rcKeys) {
this.queueReferrer(new Referrer(false, noSymbolId, nid, model, ct, this.currentReachable));
}
}
if (this.currentReachable) {
if (let (true, reachedSet) = this.reachedReachableClassMembers.get(lookupId)) {
let rrKeys = reachedSet.keys();
for (let nid in rrKeys) {
this.queueMember(nid, model, ct, true);
}
}
}
}
/**
* queueReferrer for a class member named by node, skipping the
* Referrer when its key has already been seen: the per-dependency
* walks re-derive the same members over and over, and nearly all of
* what they queue has been queued before.
*/
queueMember(nodeId: i32, model: SemanticModel, classType: ClassType | null, isReachable: boolean): void {
let key = referrerKey(false, nodeId, classType);
let seen = if (isReachable) this.reachedIds.has(key) else this.visitedIds.has(key);
if (seen) {
return;
}
this.queueReferrer(new Referrer(false, noSymbolId, nodeId, model, classType, isReachable));
}
queueReferrer(ref: Referrer): void {
let {typeArguments} = ref;
var isNew = false;
if (typeArguments == null) {
let key = referrerKey(ref.isSymbol,
if (ref.isSymbol) ref.symId as i32 else ref.nodeId, ref.classType);
if (ref.isReachable) {
isNew = !this.reachedIds.has(key);
if (isNew) {
this.reachedIds.add(key);
this.visitedIds.add(key);
}
} else {
isNew = !this.visitedIds.has(key);
if (isNew) {
this.visitedIds.add(key);
}
}
} else {
let key = referrerKey(ref.isSymbol,
if (ref.isSymbol) ref.symId as i32 else ref.nodeId, ref.classType);
let root = this.genericReferrers.get(key) ?? new TypeListTable();
this.genericReferrers[key] = root;
let node = root.at(typeArguments);
if (ref.isReachable) {
isNew = (node.marks & 2) == 0;
if (isNew) {
node.marks = node.marks | 3;
}
} else {
isNew = (node.marks & 1) == 0;
if (isNew) {
node.marks = node.marks | 1;
}
}
}
if (!isNew) {
return;
}
if (ref.isReachable) {
this.reachableQueue.push(ref);
if (!ref.isSymbol && ref.classType != null) {
let ct = ref.classType as ClassType;
// Only a referrer against the generic TEMPLATE is evidence
// about every specialization. One against a concrete
// specialization names its own, and fanning that out claims
// `Array<i32>.push` is used because `Array<String>.push` is
// — which emits a member on every instantiation as soon as
// one of them uses it.
if (!isConcrete(ct)) {
let lookupId = (ct.genericSource ?? ct).symbolId;
this.recordReachedClassMember(lookupId, ref.nodeId, ref.model, true);
}
}
} else {
this.checkableQueue.push(ref);
if (!ref.isSymbol && ref.classType != null) {
let ct = ref.classType as ClassType;
if (!isConcrete(ct)) {
let lookupId = (ct.genericSource ?? ct).symbolId;
this.recordReachedClassMember(lookupId, ref.nodeId, ref.model, false);
}
}
}
}
/**
* markFunctionReached regardless of the ambient phase flag. For
* callers that KNOW the function will be emitted (a vtable of an
* instantiated class references it), where checkable-phase gating
* would leave an emitted body whose dependencies were never
* traversed.
*/
forceReachFunction(func: WasmFunction): void {
let saved = this.currentReachable;
this.currentReachable = true;
this.markFunctionReached(func);
this.currentReachable = saved;
}
markFunctionReached(func: WasmFunction): void {
if (this.currentReachable) {
if (!this.reachedFunctionsSet.has(func)) {
// A STATIC is exempt: it takes no receiver and cannot name the
// class's type parameters, so a copy on the template is a whole
// function rather than half of one — `Holder.answer()` names it
// with no way to spell arguments.
if (func.classType != null && !isConcrete(func.classType as ClassType) &&
!func.isStatic) {
throw new Error("non-concrete function reached: " + (if (func.name != null) func.name as String else "<null>"));
}
this.reachedFunctionsSet.add(func);
func.isReached = true;
// A reached function is a lowered function, and lowering reads
// the node types of its body. The queue walk checks the bodies
// it dequeues, and a function can be reached without ever
// being dequeued — a vtable slot, a synthesized trampoline's
// target — so a module with deferred bodies is asked here too.
let deferred = func.model.deferredBodies;
if (deferred != null) {
let {node} = func;
if (node != null) {
deferred.checkBodyOfNode((node as Node).id as i32);
}
}
// A synthesized case-class == compares fields through the
// equality diamond, which dispatches through class-vtable
// ==/hashCode slots on erased fields. The eq/hash INTRINSICS
// lower through the same diamond, whose string tier resolves
// String.== by name.
if (func.isCaseClassEq || func.isCaseClassHash ||
(func.intrinsic != null &&
((func.intrinsic as String) == "eq" ||
(func.intrinsic as String) == "hash"))) {
this.useEqualityDispatch();
let {stringClass} = this.wasm;
if (stringClass != null) {
let sKey = getClassKey(stringClass);
this.notePendingMemberReach(getClassMethodKey(sKey, "=="));
this.notePendingMemberReach(getClassMethodKey(sKey, "hashCode"));
}
// A synthesized == or hashCode calls the same operation on each
// field of a class type, and the eq/hash intrinsics call it on
// their operand; reach those the way a written call would be.
let owner = func.classType;
if ((func.isCaseClassEq || func.isCaseClassHash) && owner != null) {
let opName = if (func.isCaseClassEq) "==" else "hashCode";
this.#noteFieldStaticTargets(owner as ClassType, opName);
}
let {intrinsic} = func;
let intrinsicArgs = func.typeArguments;
if (intrinsic != null && intrinsicArgs != null) {
let opName = if ((intrinsic as String) == "eq") "==" else "hashCode";
for (let ta in intrinsicArgs as Array<Type>) {
this.notePendingStaticTargets(ta, opName);
}
}
}
// `releaseOwned<T>` releases what a `T` owns at this
// specialization: a resource's `:dispose`, or a nested future's
// `[release]`.
let releaseArgs = func.typeArguments;
if (func.intrinsic != null && (func.intrinsic as String) == "release_owned" &&
releaseArgs != null) {
for (let ta in releaseArgs as Array<Type>) {
this.noteReleaseTargets(ta, func.model);
}
}
// A resource's :dispose releases each owner field the same way,
// written or synthesized: lowering appends the field glue to a
// written one too (collectAffineDropFields). A synthesized
// [release] releases what each `T` field owns.
let releaseOwner = func.classType;
if (releaseOwner != null && releaseOwner.isResource &&
(func.isSyntheticRelease ||
func.methodName == releaseMemberOf(releaseOwner))) {
this.#noteOwnerFieldReleases(releaseOwner, func.model);
} else if (func.isSyntheticRelease && releaseOwner != null) {
for (let fieldType in scopedFieldTypesAt(this.wasm, releaseOwner)) {
this.noteReleaseTargets(fieldType, func.model);
}
}
if (!func.isImport) {
this.wasm.addFunction(func);
}
this.markTypeReached(func.signature);
// Reaching a linear-memory intrinsic means the module needs a
// memory section (and the "memory" export). A target reaches
// zena:memory only through user code — the compiler's own
// time.zena, for the LSP — and previously emitted memory ops
// with no declared memory (invalid wasm at instantiation).
let {intrinsic} = func;
if (intrinsic != null) {
let iname = intrinsic;
if (iname == 'memory.size' || iname == 'memory.grow' ||
iname.contains('.load') || iname.contains('.store')) {
this.wasm.ensureMemory();
}
}
let {contextStruct} = func;
if (contextStruct != null) {
this.markTypeReached(contextStruct);
}
let {classType} = func;
if (classType != null) {
let ct = classType;
let model = this.getClassModel(ct);
this.specializer.instantiateClassType(ct, model);
}
let {node} = func;
if (node != null) {
let fnNode = node;
this.nodeIdToNode[fnNode.id as i32] = fnNode;
this.nodeIdToModel[fnNode.id as i32] = func.model;
this.queueReferrer(new Referrer(
false,
noSymbolId,
fnNode.id as i32,
func.model,
func.classType,
this.currentReachable,
func.typeArguments
));
}
}
}
}
markTypeReached(t: WasmType | null): void {
if (t == null) { return; }
if (this.currentReachable) {
if (t is WasmStruct) {
}
if (!this.reachedTypesSet.has(t)) {
this.reachedTypesSet.add(t);
this.emittedTypes.push(t);
}
}
}
markValTypeReached(vt: ValType): void {
if (vt is ValTypeRefNull) {
this.markTypeReached(vt.target);
} else if (vt is ValTypeRef) {
this.markTypeReached(vt.target);
}
}
closeReachedTypes(): void {
this.currentReachable = true;
var head = 0;
while (head < this.emittedTypes.length) {
let t = this.emittedTypes[head];
head += 1;
if (t is WasmStruct) {
if (t.superStruct != null) {
this.markTypeReached(t.superStruct);
}
for (let f in t.fields) {
this.markValTypeReached(f.type);
}
} else if (t is WasmArray) {
if (t.superArray != null) {
this.markTypeReached(t.superArray);
}
this.markValTypeReached(t.elementType);
} else if (t is WasmSignature) {
for (let p in t.params) {
this.markValTypeReached(p);
}
for (let r in t.returns) {
this.markValTypeReached(r);
}
}
}
}
/**
* Root `zena:wasi`, the component target's string marshaling.
*
* Its functions are reached from nowhere inside the program: two of
* them are called only by wrappers the compiler synthesizes after this
* pass, and `realloc` is called only by the host, through the
* lift's canonical options. So RTA has to be told, the same way
* `zena:js` is.
*
* The gate is that a String actually crosses an export, which the root
* loop above has just finished deciding — a component that moves no
* strings links neither these nor the allocator behind them, and stays
* as small as the timer components in binary-size_test. Only the
* component target resolves this module at all, so no other target
* reaches this branch with a unit to root.
*/
#rootComponentAbi(): void {
if (!this.wasm.componentMovesStrings && !this.#wrapperHasSyncExport()) {
return;
}
let prog = this.program;
// A module id here, not the library: unitsByPath is keyed by module
// id, while componentAbiModule names the library getStdlibFunc wants.
// The id names the file that declares the ABI rather than the library
// entry point, which re-exports it and declares nothing of its own.
let abiUnitId = componentAbiUnitId;
if (prog == null || !prog.unitsByPath.has(abiUnitId)) {
return;
}
let unit = prog.unitsByPath[abiUnitId];
let {model} = unit;
let gKeys = model.globalDeclarations.keys();
for (let id in gKeys) {
let decl = model.globalDeclarations[id];
let isExported = if (decl is VariableDeclaration) {
decl.exported
} else if (decl is FunctionDeclaration) {
decl.exported
} else if (decl is DeclareFunction) {
decl.exported
} else {
false
};
if (isExported) {
this.queueReferrer(new Referrer(true, id, -1, model, null, true));
}
}
}
/**
* Whether the entry wrapper the compiler wrote declares a
* synchronous export wrapper (`<name>_export_sync`): a result richer
* than a string may come back through a return area the host
* releases with `post-return`, and the lift's memory options name
* `realloc` — both the ABI's, referenced by nothing in the program.
*/
#wrapperHasSyncExport(): boolean {
let prog = this.program;
if (prog == null) {
return false;
}
for (let unit in prog.units) {
if (!isComponentEntryPath(unit.ast.path)) { continue; }
for (let stmt in unit.ast.body) {
if (stmt is FunctionDeclaration &&
stmt.name.name.endsWith(componentSyncExportSuffix)) {
return true;
}
}
}
return false;
}
/**
* Root `zena:wasi`, the component target's async-import
* driver — conditionally.
*
* Its `componentPoll`/`componentResume` are called only by the host,
* through the callback-lifted entry, so nothing inside the program
* references them and plain RTA would drop them. But rooting them
* whenever the unit is linked would force the async entry — and its
* `main(): void` requirement — onto every program that imports a WIT
* interface *declaring* an async function and calls none of them,
* because a synthesized WIT module always links the driver for its
* wrappers. So the gate is that the program's own traversal, which
* has just finished, reached a door into the driver's registries:
* `awaitPacked` (subtasks) or `awaitWaitable` (stream and future
* copies), or `waitable-set.wait` itself, which is how a synchronous
* call blocks — a stdout write that did not complete at once — and
* which the host allows only inside a task it lifted async. A program
* that never awaits an async-lowered import, never blocks and has no
* async main keeps the synchronous lift.
*
* The zena command's host is the exception: it lifts every `main`
* async, so that the entry installs the host's stack-trace hooks
* before the program runs.
*/
#rootComponentAsyncDriver(): void {
let driverPath = componentDriverUnitId;
let hostSetupUnitId = "zena:host-setup";
let prog = this.program;
if (prog == null || !prog.unitsByPath.has(driverPath)) {
return;
}
let awaitPacked = this.wasm.getStdlibFunc('wasi', 'awaitPacked');
let awaitWaitable =
this.wasm.getStdlibFunc('wasi', 'awaitWaitable');
let blockingWait =
this.wasm.getStdlibFunc('wasi', 'waitableSetWait');
var anyDoorReached =
(awaitPacked != null && (awaitPacked as WasmFunction).isReached) ||
(awaitWaitable != null && (awaitWaitable as WasmFunction).isReached) ||
(blockingWait != null && (blockingWait as WasmFunction).isReached);
// A declared world's export wrappers hand the event loop a value
// through `finishTask`, which only an async export's entry and
// callback can deliver: a program with one needs the event loop
// whether or not it ever awaits an import. The wrapper's `run` is
// written only for an async main, which counts below on its own;
// it is kept below with the rest of the event loop.
var wrapper: CompilationUnit | null = null;
for (let unit in prog.units) {
if (isComponentEntryPath(unit.ast.path)) {
wrapper = unit;
for (let stmt in unit.ast.body) {
if (stmt is FunctionDeclaration) {
let fn = stmt as FunctionDeclaration;
if (fn.exported && fn.name.name != componentEntryRunName) {
anyDoorReached = true;
}
}
}
}
}
// An async main is the same case without a wrapper to notice it
// by: its `Future<void>` return can only be lifted by the component
// entry, which subscribes to the future and calls `finishVoidTask`.
// Leaving the driver unrooted here means `prepareComponentEntry`
// finds no `componentPoll` in the function map, builds no entry,
// and the export loops reach the async ramp directly.
// Only a component has an entry to lift: a `core` module links the
// driver's unit through the console it shares with the component
// target, and must not root it.
let entry = prog.entryPoint;
let asyncMain = entry != null &&
hasAsyncMain((entry as CompilationUnit).ast);
if (entry != null && targetEmitsComponent(this.target) &&
(targetUsesZenaComponentHost(this.target) || asyncMain)) {
anyDoorReached = true;
}
if (!anyDoorReached) {
return;
}
// The four the adapters call from outside the program, by name.
let driver = prog.unitsByPath[driverPath];
this.#rootUnitExport(driver, 'componentPoll');
this.#rootUnitExport(driver, 'componentResume');
this.#rootUnitExport(driver, 'beginTask');
this.#rootUnitExport(driver, 'markReturned');
if (asyncMain) {
this.#rootUnitExport(driver, 'finishVoidTask');
}
if (wrapper != null) {
this.#rootUnitExports(wrapper as CompilationUnit);
}
// The zena command's host also supplies `Error`'s stack traces
// through `zena:host-setup`, whose installer the entry calls before
// the program runs: rooted with the driver, since the entry needs
// it in the function map the same way.
if (prog.unitsByPath.has(hostSetupUnitId)) {
this.#rootUnitExports(prog.unitsByPath[hostSetupUnitId]);
}
// The abi rooting above queues before the main drain; this one runs
// after it, so it drains what it queued.
this.processQueues();
}
/** Queue one exported function of a unit as a root, by name. */
#rootUnitExport(unit: CompilationUnit, name: String): void {
let {model} = unit;
let gKeys = model.globalDeclarations.keys();
for (let id in gKeys) {
let decl = model.globalDeclarations[id];
if (decl is FunctionDeclaration) {
let fn = decl as FunctionDeclaration;
if (fn.exported && fn.name.name == name) {
this.queueReferrer(new Referrer(true, id, -1, model, null, true));
return;
}
}
}
throw new Error(`${unit.ast.path} does not export the function '${name}'`);
}
/** Queue every export of a unit as a root. */
#rootUnitExports(unit: CompilationUnit): void {
let {model} = unit;
let gKeys = model.globalDeclarations.keys();
for (let id in gKeys) {
let decl = model.globalDeclarations[id];
let isExported = if (decl is VariableDeclaration) {
decl.exported
} else if (decl is FunctionDeclaration) {
decl.exported
} else if (decl is DeclareFunction) {
decl.exported
} else {
false
};
if (isExported) {
this.queueReferrer(new Referrer(true, id, -1, model, null, true));
}
}
}
#linkSuperAndVT(ct: ClassType, model: SemanticModel, linkedClasses: HashMap<ClassKey, boolean>): void {
let ctKey = getClassKey(ct);
if (linkedClasses.has(ctKey)) { return; }
linkedClasses[ctKey] = true;
let {superType} = ct;
if (superType != null) {
let superCt = superType;
this.typeLowerer.discoverType(superCt, model);
this.#linkSuperAndVT(superCt, model, linkedClasses);
let cKey = getClassKey(ct);
let superKey = getClassKey(superCt);
if (let (true, info) = this.wasm.classInfos.get(cKey)) {
if (let (true, superInfo) = this.wasm.classInfos.get(superKey)) {
info.structType.superStruct = superInfo.structType;
var hasSub = false;
for (let existingSub in superInfo.subclasses) {
if (existingSub === info) {
hasSub = true;
break;
}
}
if (!hasSub) {
superInfo.subclasses.push(info);
}
let {vtableStructType} = info;
if (vtableStructType != null && superInfo.vtableStructType != null) {
let vst = vtableStructType;
let superVst = superInfo.vtableStructType as WasmStruct;
vst.superStruct = superVst;
}
}
}
let ctVtable = this.wasm.classVtable(cKey);
let superVtable = this.wasm.classVtable(superKey);
if (superVtable.length > 0 || ctVtable.length > 0) {
let newVTable = new Array<String>();
let seen = new Set<String>();
for (let methName in superVtable) {
newVTable.push(methName);
seen.add(methName);
}
for (let methName in ctVtable) {
if (!seen.has(methName)) {
newVTable.push(methName);
seen.add(methName);
}
}
while (ctVtable.length > 0) {
ctVtable.pop();
}
for (let m in newVTable) {
ctVtable.push(m);
}
}
}
}
/**
* Whether anything so far says a value of this class, or a mention of
* its struct, can appear in the emitted module — the same question
* the type section is rooted from in `run`, asked earlier.
*
* Instantiation and mention are the whole answer. There used to be a
* third case, `Box<prim>`, because the erased-`==` diamond ref_tested
* every registered one with no AST naming it; nothing is synthesized
* behind the AST's back any more.
*/
#classHasEmissionEvidence(ct: ClassType): boolean {
let cKeyStr = getClassKey(ct) as String;
return this.instantiatedSpecializedClasses.has(cKeyStr) ||
this.reachablyNamedClasses.has(cKeyStr);
}
#populateClassStruct(ct: ClassType, populated: HashMap<ClassKey, boolean>): void {
let key = getClassKey(ct);
if (populated.has(key)) { return; }
let {superType} = ct;
if (superType != null) {
this.#populateClassStruct(superType, populated);
}
populated[key] = true;
let lookupId = (ct.genericSource ?? ct).symbolId;
let cd: Node | null = if (this.classDecls.has(lookupId)) this.classDecls[lookupId] else null;
let model = this.getClassModel(ct);
// Every declared class is laid out, including the ones nothing
// reaches: the layout is what registers a class's members, and a
// class can pick up evidence after its turn here. But laying one
// out is not evidence about the types its members' signatures
// name. A field typed `Completer<i32>` on a class nothing reaches
// used to specialize and emit `Completer<i32>` whole — all six of
// its methods, plus the `Future<i32>` and `Box<i32>` they need —
// whenever some other code had reached `Completer` at any type at
// all. See docs/design/binary-size.md §18.
let hasEvidence = this.#classHasEmissionEvidence(ct);
let savedReachable = this.currentReachable;
let savedLayingOut = this.layingOutUnemittedClass;
if (!hasEvidence) {
this.currentReachable = false;
this.layingOutUnemittedClass = true;
}
this.specializer.populateClassStructAndMethods(ct, cd, model);
this.currentReachable = savedReachable;
this.layingOutUnemittedClass = savedLayingOut;
}
run(): void {
let tInit = performance.start("codegen-discovery-init");
// Pass 0: Register empty structs for all declared classes & interfaces to prevent cyclic dependencies
for (let unit in this.program.units) {
let {model} = unit;
{
// Populate class declarations and their members
let classKeys = model.classDeclarations.keys();
for (let id in classKeys) {
let classDecl = model.classDeclarations[id];
this.nodeIdToNode[classDecl.id as i32] = classDecl;
this.nodeIdToModel[classDecl.id as i32] = model;
for (let member in classDecl.body) {
this.nodeIdToNode[member.id as i32] = member;
this.nodeIdToModel[member.id as i32] = model;
}
}
// Populate interface declarations and their members
let interfaceKeys = model.interfaceDeclarations.keys();
for (let id in interfaceKeys) {
let ifaceDecl = model.interfaceDeclarations[id];
this.nodeIdToNode[ifaceDecl.id as i32] = ifaceDecl;
this.nodeIdToModel[ifaceDecl.id as i32] = model;
for (let member in ifaceDecl.body) {
this.nodeIdToNode[member.id as i32] = member;
this.nodeIdToModel[member.id as i32] = model;
}
}
// Populate mixin declarations and their members
let mixinKeys = model.mixinDeclarations.keys();
for (let id in mixinKeys) {
let mixinDecl = model.mixinDeclarations[id];
this.classDecls[id] = mixinDecl;
this.classModels[id] = model;
this.symbolIdToDecl[id] = mixinDecl;
this.symbolIdToModel[id] = model;
this.nodeIdToNode[mixinDecl.id as i32] = mixinDecl;
this.nodeIdToModel[mixinDecl.id as i32] = model;
for (let member in mixinDecl.body) {
this.nodeIdToNode[member.id as i32] = member;
this.nodeIdToModel[member.id as i32] = model;
}
}
// Populate global declarations
let globalKeys = model.globalDeclarations.keys();
for (let id in globalKeys) {
let decls = model.getGlobalDeclarations(id);
if (decls != null) {
for (let decl in (decls as GrowableArray<Node>)) {
this.nodeIdToNode[decl.id as i32] = decl;
this.nodeIdToModel[decl.id as i32] = model;
}
}
}
}
// Classes
let classKeys = model.classDeclarations.keys();
for (let id in classKeys) {
let classDecl = model.classDeclarations[id];
this.classDecls[id] = classDecl;
this.classModels[id] = model;
this.symbolIdToModel[id] = model;
this.symbolIdToDecl[id] = classDecl;
let rawClassType = this.getClassDeclType(classDecl, model);
if (rawClassType != null) {
let classType = rawClassType;
if (isWellKnown(WellKnown.StringClass, classType.name,
classType.sourcePath)) {
this.wasm.stringClass = classType;
} else if (isWellKnown(WellKnown.TemplateStringsArrayClass,
classType.name, classType.sourcePath)) {
this.wasm.templateStringsArrayClass = classType;
} else if (isWellKnown(WellKnown.BigIntClass,
classType.name, classType.sourcePath)) {
this.wasm.bigIntClass = classType;
} else if (isWellKnown(WellKnown.ErrorClass, classType.name,
classType.sourcePath)) {
this.wasm.errorClass = classType;
}
var ctWalk: ClassType | null = classType;
while (ctWalk != null) {
let currCt = ctWalk;
let cKey = getClassKey(currCt);
if (!this.wasm.classInfos.has(cKey)) {
let emptyStruct = new WasmStruct(currCt.name, new Array<WasmField>());
emptyStruct.classType = currCt;
if (!currCt.isExtension) {
this.wasm.types.push(emptyStruct);
}
let info = new ClassCodegenInfo(emptyStruct);
this.wasm.classInfos[cKey] = info;
let emptyVTableStruct = new WasmStruct(currCt.name + "_VTable", new Array<WasmField>());
emptyVTableStruct.classType = currCt;
if (!currCt.isExtension) {
this.wasm.types.push(emptyVTableStruct);
}
info.vtableStructType = emptyVTableStruct;
}
ctWalk = currCt.superType;
}
}
if (classDecl.isSealed && classDecl.sealedVariants != null) {
let variants = classDecl.sealedVariants as GrowableArray<SealedVariant>;
for (let variant in variants) {
let variantSym = model.resolve(variant);
if (variantSym != null) {
let vId = variantSym.id;
if (!this.classDecls.has(vId) || !(this.classDecls[vId] is ClassDeclaration)) {
this.classDecls[vId] = variant;
this.classModels[vId] = model;
this.symbolIdToDecl[vId] = variant;
}
this.symbolIdToModel[vId] = model;
// The node may carry no type (whether it does varies
// with what else the checker visited), but the resolved
// symbol always knows its binding — and a silent skip
// here leaves the case class without a struct, which a
// lowered `is`/`as` against it then trips over.
var rawVariantType = model.getNodeType(variant);
if (!(rawVariantType is ClassType)) {
rawVariantType = model.getBindingTypeDirect(variantSym);
}
if (rawVariantType is ClassType) {
var vWalk: ClassType | null = rawVariantType;
while (vWalk != null) {
let currV = vWalk;
let vKey = getClassKey(currV);
if (!this.wasm.classInfos.has(vKey)) {
let isIntermediate = currV.isMixinIntermediate;
let emptyStruct = new WasmStruct(currV.name, new Array<WasmField>());
emptyStruct.classType = currV;
if (!currV.isExtension && !isIntermediate) {
this.wasm.types.push(emptyStruct);
}
let info = new ClassCodegenInfo(emptyStruct);
this.wasm.classInfos[vKey] = info;
let emptyVTableStruct = new WasmStruct(currV.name + "_VTable", new Array<WasmField>());
emptyVTableStruct.classType = currV;
if (!currV.isExtension && !isIntermediate) {
this.wasm.types.push(emptyVTableStruct);
}
info.vtableStructType = emptyVTableStruct;
}
vWalk = currV.superType;
}
}
}
}
}
}
// Interfaces
let interfaceKeys = model.interfaceDeclarations.keys();
for (let id in interfaceKeys) {
let ifaceDecl = model.interfaceDeclarations[id];
this.interfaceDecls[id] = ifaceDecl;
this.interfaceModels[id] = model;
this.symbolIdToModel[id] = model;
this.symbolIdToDecl[id] = ifaceDecl;
let ifaceType = model.getNodeType(ifaceDecl) as InterfaceType;
let iKey = getInterfaceKey(ifaceType);
if (!this.wasm.interfaceStructs.has(iKey)) {
let emptyVTableStruct = new WasmStruct(ifaceType.name + "_VTable", new Array<WasmField>());
this.wasm.types.push(emptyVTableStruct);
this.wasm.interfaceVTableStructs[iKey] = emptyVTableStruct;
let fatPtrFields = growable<WasmField>([
new WasmField("instance", new ValTypeAnyRef(), false),
new WasmField("vtable", new ValTypeRef(emptyVTableStruct), false),
]);
let emptyStruct = new WasmStruct(ifaceType.name + "_FatPtr", fatPtrFields);
this.wasm.types.push(emptyStruct);
this.wasm.interfaceStructs[iKey] = emptyStruct;
}
}
// Mixins
let mixinKeys = model.mixinDeclarations.keys();
for (let id in mixinKeys) {
let mixinDecl = model.mixinDeclarations[id];
this.classDecls[id] = mixinDecl;
this.classModels[id] = model;
this.symbolIdToModel[id] = model;
this.symbolIdToDecl[id] = mixinDecl;
}
// Enums
let enumKeys = model.enumDeclarations.keys();
for (let id in enumKeys) {
this.symbolIdToModel[id] = model;
this.symbolIdToDecl[id] = model.enumDeclarations[id];
}
// Globals
let globalKeys = model.globalDeclarations.keys();
for (let id in globalKeys) {
this.symbolIdToModel[id] = model;
this.symbolIdToDecl[id] = model.globalDeclarations[id];
let decl = model.globalDeclarations[id];
// Both `let f = <T>() => ...` and `function f<T>() { ... }` bind a
// FunctionExpression; either can be generic.
let initNode: Node | null = if (decl is VariableDeclaration) {
decl.init
} else if (decl is FunctionDeclaration) {
decl.func
} else {
null
};
if (initNode is FunctionExpression) {
// Read off the declaration rather than its checked type: a
// module whose bodies are deferred has not checked this
// declaration yet, and the index is built before the walk
// that would ask for it. The two agree — the checked
// signature's type parameters are the written ones.
let {typeParameters} = initNode as FunctionExpression;
let len = if (typeParameters != null) typeParameters.length else 0;
if (len > 0) {
this.wasm.genericFunctions[id] = initNode;
this.wasm.genericFunctionModels[id] = model;
}
}
}
}
// The `$string*` four are host-interop exports letting an embedder
// build and read a guest String. Creating them here rooted String's
// constructor — and so the entire class — in every program, and
// their bodies are synthesized against String's struct layout, so
// they cannot exist for a module with no String at all. They are
// created from ensureAllHelperFunctionsReached instead, once RTA
// knows whether String was instantiated.
if (this.wasm.stringClass != null && this.wasm.stringLiterals.size > 0 && !targetUsesJsStrings(this.target)) {
this.wasm.ensureStringHelpers(this.program.units[0].model);
this.wasm.ensureStringLiteralHelpers(this.program.units[0].model);
this.markFunctionReached(this.wasm.stringFromSharedFunc as WasmFunction);
this.markFunctionReached(this.wasm.getStringLiteralFunc as WasmFunction);
}
// Populate mixinToClasses mapping
this.mixinToClasses = new Map<MixinKey, GrowableArray<ClassType>>();
for (let unit in this.program.units) {
let {model} = unit;
let classKeys = model.classDeclarations.keys();
for (let id in classKeys) {
let classDecl = model.classDeclarations[id];
let rawClassType = this.getClassDeclType(classDecl, model);
if (rawClassType != null) {
let mixinMembers = new Array<Node>();
let seenMixins = new Map<MixinKey, boolean>();
collectMixinMembers(this.program, model, classDecl.mixins, mixinMembers, seenMixins);
let mKeys = seenMixins.keys();
for (let mixKey in mKeys) {
if (!this.mixinToClasses.has(mixKey)) {
this.mixinToClasses[mixKey] = new Array<ClassType>();
}
this.mixinToClasses[mixKey].push(rawClassType);
}
}
}
}
// Process all import declarations upfront for namespace objects and their closure trampolines
for (let unit in this.program.units) {
let mod = unit.ast;
let {model} = unit;
for (let stmt in mod.body) {
if (stmt is ImportDeclaration) {
this.visitor.discoverImportDeclaration(stmt, model);
}
}
}
// RTA Roots
for (let unit in this.program.units) {
let {model} = unit;
let isEntry = this.program.entryPoint != null && unit.ast.path == (this.program.entryPoint as CompilationUnit).ast.path;
// zena:js's exports are wasm exports too (async.md §4): the JS
// host calls them to settle a future, so nothing inside the
// program ever references them and RTA would drop them. Rooting
// them here rather than force-reaching a hardcoded list keeps the
// gate exact — the unit only exists when the program imports the
// module, so a program that does no host I/O links none of it.
// `zena:wasi` is a host boundary in the same sense —
// the component's event loop calls `componentPoll` and
// `componentResume` from outside the program — but its exports
// root conditionally, after the main traversal below: see
// `#rootComponentAsyncDriver`. The component entry wrapper the
// compiler writes (lib/component-entry.zena) is one too, and
// roots with the driver for the same reason: the entry adapter
// calls its `run` from outside the program, and only exists when
// the driver does.
let isHostBoundary = isHostBoundaryLibrary(unit.ast.path);
// The root set is `main` plus the exports of those two units.
// Every other unit is a library: its globals are roots only if
// something reaches them. Queuing them all — which is what this
// did — made the checkable traversal walk the entire stdlib, and
// walking it instantiates.
let rootsExports = isEntry || isHostBoundary;
if (!rootsExports) {
continue;
}
let gKeys = model.globalDeclarations.keys();
for (let id in gKeys) {
let decl = model.globalDeclarations[id];
var isExported = false;
var isMain = false;
var declName = "";
if (decl is VariableDeclaration) {
let isFunction = decl.init is FunctionExpression;
isExported = rootsExports && (decl.exported || (isEntry && !isFunction));
if (decl.pattern is IdentifierPattern) {
declName = (decl.pattern as IdentifierPattern).name;
}
if (isEntry && declName == "main") {
isMain = true;
}
} else if (decl is FunctionDeclaration) {
isExported = rootsExports && decl.exported;
declName = decl.name.name;
if (isEntry && declName == "main") {
isMain = true;
}
} else if (decl is DeclareFunction) {
isExported = rootsExports && decl.exported;
declName = decl.name.name;
}
// A template-protocol library exports its API to programs too
// (`html`, `Event`, `defineElement`), and those are reached
// like any library's exports when something imports them. Only
// its `webui_*` functions are the host's to call, so only those
// root; the rest are left to be reached.
if (!isEntry && isWebUiProtocolLibrary(unit.ast.path) &&
!(declName.startsWith("webui_") && targetUsesJsStrings(this.target))) {
continue;
}
if (isMain || isExported) {
this.queueReferrer(new Referrer(true, id, -1, model, null, true));
// An export whose type mentions String is boundary evidence
// that a String VALUE can exist: the host is entitled to
// build one with $stringCreate and hand it in, even if the
// guest never constructs a string itself
// (`export let identity = (s: String) => s;`).
let {stringClass} = this.wasm;
if (stringClass != null) {
// The type hangs off different nodes per declaration kind;
// a VariableDeclaration's own node carries none, its
// pattern and init do.
var declType = model.getNodeType(decl);
if (declType == null && decl is VariableDeclaration) {
declType = model.getNodeType(decl.pattern);
if (declType == null && decl.init != null) {
declType = model.getNodeType(decl.init as Node);
}
} else if (declType == null && decl is FunctionDeclaration) {
declType = model.getNodeType(decl.func);
}
if (declType != null &&
this.#typeMentionsString(declType, 0)) {
let sClass = stringClass;
this.specializer.instantiateClassType(
sClass, this.getClassModel(sClass));
if (targetEmitsComponent(this.target)) {
// A component's boundary is not the core module's. The
// `$string*` four exist for an embedder holding the core
// module directly, and nothing inside a component can
// reach them — its strings cross through the canonical
// ABI instead, which is `zena:wasi`'s job and
// wants a flag of its own.
this.wasm.componentMovesStrings = true;
} else if (declType is FunctionType) {
// Which DIRECTION does the boundary move strings?
// Export parameters are host-written, returns are
// host-read; a non-function String export is both.
for (let p in declType.parameters) {
if (this.#typeMentionsString(p, 0)) {
this.wasm.hostWritesStrings = true;
}
}
if (this.#typeMentionsString(declType.returnType, 0)) {
this.wasm.hostReadsStrings = true;
}
} else {
this.wasm.hostWritesStrings = true;
this.wasm.hostReadsStrings = true;
}
}
}
} else {
this.queueReferrer(new Referrer(true, id, -1, model, null, false));
}
}
let mod = unit.ast;
for (let stmt in mod.body) {
if (!(stmt is VariableDeclaration) && !(stmt is FunctionDeclaration) && !(stmt is DeclareFunction) && !(stmt is ClassDeclaration) && !(stmt is InterfaceDeclaration) && !(stmt is MixinDeclaration) && !(stmt is ImportDeclaration) && !(stmt is ExportAllDeclaration) && !(stmt is ExportFromDeclaration)) {
this.nodeIdToNode[stmt.id as i32] = stmt;
this.nodeIdToModel[stmt.id as i32] = model;
this.queueReferrer(new Referrer(false, noSymbolId, stmt.id as i32, model, null, true));
}
}
}
// String is NOT instantiated here. Discovering the class — which
// every program does, through the prelude — is not evidence that a
// String value exists. A program that builds one reaches its
// constructor through the normal graph, and a string literal
// instantiates it below through the literal helpers.
// TemplateStringsArray is not instantiated here either, for the same
// reason. Only a tagged template builds one, and
// `registerTaggedTemplate` instantiates the class when it finds one.
// Doing it here cost every module that could see the class — which
// is every module importing a library that re-exports it — its
// struct, the two String arrays its fields name, and a vtable
// global, for a program with no tagged template in it.
this.#rootComponentAbi();
this.ensureAllHelperFunctionsReached();
performance.end(tInit);
let tQueues = performance.start("codegen-discovery-queues");
// Main reachability queue traversal
this.processQueues();
this.ensureAllHelperFunctionsReached();
this.processQueues();
this.#rootComponentAsyncDriver();
performance.end(tQueues);
let tLayout = performance.start("codegen-discovery-layout");
// Pass 0.6: Link superStruct for inheritance and inherit vtable slots recursively
let linkedClasses = new Map<ClassKey, boolean>();
// Pre-discover implemented interfaces of all reached/specialized and declared classes.
let classesToDiscover = new Array<ClassType>();
for (let cPair in this.wasm.classInfos) {
let info = cPair.value;
let {classType} = info.structType;
if (classType != null) {
classesToDiscover.push(classType);
}
}
for (let pair in this.classDecls) {
let classDecl = pair.value;
let moduleModel = this.classModels[pair.key];
let ct = this.getClassDeclType(classDecl, moduleModel);
if (ct != null) {
classesToDiscover.push(ct);
}
}
for (let ct in classesToDiscover) {
let model = this.getClassModel(ct);
let specIfaces = this.cha.collectAllImplementedInterfaces(ct);
for (let iface in specIfaces) {
this.typeLowerer.discoverType(iface, model);
}
}
let classesToLink = new Array<ClassType>();
for (let cPair in this.wasm.classInfos) {
let info = cPair.value;
let {classType} = info.structType;
if (classType != null) {
classesToLink.push(classType);
}
}
for (let ct in classesToLink) {
let model = this.getClassModel(ct);
this.#linkSuperAndVT(ct, model, linkedClasses);
}
// Pass 0.8: Discover declared interfaces' member types, in the
// declaring module's model, so that slot signatures resolve to
// concrete wasm types. Without this, types not yet lowered fall back
// to structref in the vtable field while the trampolines created
// later use the concrete type, producing an invalid module.
// Specializations discover theirs when they are registered. The
// slots themselves are added on demand (#syncInterfaceSlots).
for (let pair in this.interfaceDecls) {
let ifaceModel = this.interfaceModels[pair.key];
let it = ifaceModel.getNodeType(pair.value) as InterfaceType;
let itParams = getInterfaceTypeParameters(it);
for (let mPair in it.members) {
let resolvedType = substituteTypeParamsInCodegen(this.wasm, itParams, it.typeArguments, mPair.value.type);
this.typeLowerer.discoverType(resolvedType, ifaceModel);
// Substitution leaves an overload list as declared, so each
// overload's types are discovered separately.
let overloads = interfaceMethodOverloads(this.wasm, it, mPair.key);
if (overloads != null) {
for (let overload in overloads) {
this.typeLowerer.discoverType(overload, ifaceModel);
}
}
}
}
// Pass 1.05: Unified recursive class struct and vtable fields
// population (superclass first). Populating a class registers its
// methods, which can instantiate further classes — so this runs to
// a fixpoint, and only then is instantiation CLOSED. After that a
// class that has never been instantiated cannot become
// instantiated, because nothing would populate its struct: it
// would carry an empty layout and fail much further downstream
// (`$stringCreate layout`, `operator dispatch`) with nothing
// pointing back here.
let populated = new Map<ClassKey, boolean>();
this.#layoutClassStructs(populated);
// Pass 1.1: Synthesize physical field getters/setters for virtual/inherited slots
for (let cPair in this.wasm.classInfos) {
let cName = cPair.key;
let cStruct = cPair.value.structType;
let {classType} = cStruct;
if (classType != null) {
let cType = classType;
for (let methName in this.wasm.classVtable(cName)) {
if (methName.startsWith("get#")) {
let fieldName = methName.sliceBytes(4, methName.length);
var hasPhysical = false;
var backingName = "";
let lookupName = fieldName;
let lookupPrivateName = getClassPrivateFieldKey(cName, fieldName);
let lookupPrivateHashName = getClassPrivateFieldKey(cName, "#" + fieldName);
for (let f in cStruct.fields) {
let {name} = f;
if (name != null) {
let fname = name;
if (fname == lookupName) {
hasPhysical = true;
backingName = lookupName;
} else if (fname == lookupPrivateName) {
hasPhysical = true;
backingName = lookupName;
} else if (fname == lookupPrivateHashName) {
hasPhysical = true;
backingName = "#" + fieldName;
} else if (fname.endsWith("::" + fieldName)) {
hasPhysical = true;
backingName = fieldName;
} else if (fname.endsWith("::#" + fieldName)) {
hasPhysical = true;
backingName = "#" + fieldName;
}
}
}
if (hasPhysical) {
let hasGetter = this.wasm.classMethodMap.has(getClassMethodKey(getClassKey(cType), methName));
if (!hasGetter) {
this.specializer.registerClassMethod(cType, null, methName, null, true, false, backingName, this.program.units[0].model, null);
}
}
} else if (methName.startsWith("set#")) {
let fieldName = methName.sliceBytes(4, methName.length);
var hasPhysical = false;
var backingName = "";
let lookupName = fieldName;
let lookupPrivateName = getClassPrivateFieldKey(cName, fieldName);
let lookupPrivateHashName = getClassPrivateFieldKey(cName, "#" + fieldName);
for (let f in cStruct.fields) {
let {name} = f;
if (name != null) {
let fname = name;
if (fname == lookupName) {
hasPhysical = true;
backingName = lookupName;
} else if (fname == lookupPrivateName) {
hasPhysical = true;
backingName = lookupName;
} else if (fname == lookupPrivateHashName) {
hasPhysical = true;
backingName = "#" + fieldName;
} else if (fname.endsWith("::" + fieldName)) {
hasPhysical = true;
backingName = fieldName;
} else if (fname.endsWith("::#" + fieldName)) {
hasPhysical = true;
backingName = "#" + fieldName;
}
}
}
if (hasPhysical) {
let hasSetter = this.wasm.classMethodMap.has(getClassMethodKey(getClassKey(cType), methName));
if (!hasSetter) {
this.specializer.registerClassMethod(cType, null, methName, null, false, true, backingName, this.program.units[0].model, null);
}
}
}
}
}
}
// Pass 1.15: Register any remaining vtable slots that haven't been registered yet (e.g. abstract fields/methods)
for (let cPair in this.wasm.classInfos) {
let cStruct = cPair.value.structType;
let {classType} = cStruct;
if (classType != null) {
let cType = classType;
for (let methName in this.wasm.classVtable(cPair.key)) {
var hasImpl = false;
var curr: ClassType | null = cType;
while (curr != null) {
let k = getClassMethodKey(getClassKey(curr), methName);
if (this.wasm.classMethodMap.has(k)) {
hasImpl = true;
break;
}
curr = curr.superType;
}
if (!hasImpl) {
let isGetter = methName.startsWith("get#");
let isSetter = methName.startsWith("set#");
let stub = this.specializer.registerClassMethod(cType, null, methName, null, isGetter, isSetter, null, this.program.units[0].model, null);
stub.isVtableSlotStub = true;
}
}
}
}
// Pass 1.2: Resolve indices for all synthesized getters and
// setters — over every REGISTERED method, not `wasm.functions`.
// Registration computes the backing index against the struct's
// fields, which populate pushes only after its member walk, so an
// early-registered getter carries -1 (an `unreachable` stub body)
// until this fixes it up. While every registered method of an
// instantiated class was force-reached, being in wasm.functions
// was equivalent to being registered; with reaching driven by use,
// a getter can be registered now and reached later.
let synthFixups = new Array<WasmFunction>();
for (let f in this.wasm.functions) {
synthFixups.push(f);
}
for (let mPair in this.wasm.classMethods) {
for (let f in mPair.value) {
synthFixups.push(f);
}
}
for (let f in synthFixups) {
let {classType} = f;
if (classType != null) {
let cType = classType;
if (!cType.isExtension) {
let cKey = getClassKey(cType);
if (let (true, info) = this.wasm.classInfos.get(cKey)) {
let st = info.structType;
let {methodName} = f;
if (methodName != null) {
let mName = methodName;
if (mName.startsWith("get#")) {
let fieldName = mName.sliceBytes(4, mName.length);
let lookupName = fieldName;
let lookupPrivateName = getClassPrivateFieldKey(cKey, fieldName);
let lookupPrivateHashName = getClassPrivateFieldKey(cKey, "#" + fieldName);
var foundIdx = -1;
for (var fi = 0; fi < st.fields.length; fi += 1) {
let fname = st.fields[fi].name;
if (fname != null) {
if (fname == lookupName || fname == lookupPrivateName || fname == lookupPrivateHashName || fname.endsWith("::" + fieldName) || fname.endsWith("::#" + fieldName)) {
foundIdx = fi;
break;
}
}
}
f.getterStruct = st;
f.getterFieldIndex = foundIdx;
} else if (mName.startsWith("set#")) {
let fieldName = mName.sliceBytes(4, mName.length);
let lookupName = fieldName;
let lookupPrivateName = getClassPrivateFieldKey(cKey, fieldName);
let lookupPrivateHashName = getClassPrivateFieldKey(cKey, "#" + fieldName);
var foundIdx = -1;
for (var fi = 0; fi < st.fields.length; fi += 1) {
let fname = st.fields[fi].name;
if (fname != null) {
if (fname == lookupName || fname == lookupPrivateName || fname == lookupPrivateHashName || fname.endsWith("::" + fieldName) || fname.endsWith("::#" + fieldName)) {
foundIdx = fi;
break;
}
}
}
f.setterStruct = st;
f.setterFieldIndex = foundIdx;
}
}
}
}
}
}
// Pre-mark all singleton case classes as instantiated so they get class and interface vtables built
for (let cPair in this.wasm.classInfos) {
let info = cPair.value;
let cStruct = info.structType;
let {classType} = cStruct;
if (classType != null) {
let cType = classType;
if (cType.isCaseClass && (cType.constructorType == null || (cType.constructorType as FunctionType).parameters.length == 0)) {
let model = this.getClassModel(cType);
this.specializer.instantiateClassType(cType, model);
}
}
}
this.currentReachable = true;
this.#buildClassVTableGlobals();
// Pass 1.25: Allocate singleton globals for unit variants
for (let cPair in this.wasm.classInfos) {
let cName = cPair.key;
let info = cPair.value;
let cStruct = info.structType;
let {classType} = cStruct;
if (classType != null) {
let cType = classType;
if (cType.isCaseClass && (cType.constructorType == null || (cType.constructorType as FunctionType).parameters.length == 0)) {
if (info.singletonGlobal != null) {
continue;
}
// Mirror the bootstrap: only unit variants with no user fields
// (own or inherited) may be pre-allocated singletons. The
// singleton is built with struct.new of default values, which
// silently skips field initializers — e.g. a base-class
// `uid: i32 = nextUid()` would stay 0 on every instance.
var hasUserFields = false;
var curr: ClassType | null = cType;
while (curr != null && !hasUserFields) {
let cc = curr;
for (let mPair in cc.members) {
if (mPair.value is FieldInfo && !mPair.value.isStatic) {
hasUserFields = true;
break;
}
}
curr = cc.superType;
}
if (hasUserFields) {
continue;
}
let globalName = getClassSingletonName(cName);
// Non-nullable: the singleton is immutable and initialized in
// place with a constant struct.new (the vtable global it reads
// is always declared earlier). Reads flow directly into the
// non-nullable locals that 8fae4045 introduced, with no cast.
let globalType = new ValTypeRef(cStruct);
let wasmGlobal = new WasmGlobal(
globalName,
globalName,
globalType,
false,
null,
null,
this.program.units[0].model
);
wasmGlobal.initSingletonStruct = cType;
// The WasmGlobal constructor nullifies ref types for globals it
// cannot prove initialized in place (initSingletonStruct is only
// attached after construction), so re-tighten here: the singleton
// is immutable with a constant struct.new initializer, and its
// reads flow into non-nullable locals with no cast.
wasmGlobal.type = globalType;
this.wasm.globals.push(wasmGlobal);
info.singletonGlobal = wasmGlobal;
}
}
}
performance.end(tLayout);
let tQueues2 = performance.start("codegen-discovery-queues");
this.#settleQueues();
performance.end(tQueues2);
this.activateCancellationMachinery();
this.#settleQueues();
let tLayout2 = performance.start("codegen-discovery-layout");
// Pass 2 and the queue drain feed each other; run them to fixpoint.
var vtRound = true;
while (vtRound) {
vtRound = this.#buildClassInterfaceVTables();
this.#settleQueues();
this.activateCancellationMachinery();
}
performance.end(tLayout2);
let tQueues3 = performance.start("codegen-discovery-queues");
this.#settleQueues();
performance.end(tQueues3);
let tLayout3 = performance.start("codegen-discovery-layout");
// Field accessors named by reachable referrers before populate
// registered them: re-check now that populate has run, BEFORE the
// settle layout — the drain can reach bodies that instantiate.
// From here every settle drains what was pended since.
this.currentReachable = true;
this.#pendingDrained = 0;
this.#drainPendingMemberReaches();
this.#settleQueues();
this.activateCancellationMachinery();
this.#settleQueues();
// The drains above can instantiate classes and record interface
// adaptations the earlier vtable fixpoint never saw — a generic
// method reached late packs a generic class at an interface slot,
// and without another round the pair has a struct and no vtable
// (lowering's iface_pack then fails). Re-run to fixpoint.
var lateVtRound = true;
while (lateVtRound) {
lateVtRound = this.#buildClassInterfaceVTables();
// Interface type tests pack through class-interface vtables too,
// and which classes a test can answer true for is known only
// once the classes exist: mark the pairs here, and the next
// round builds them.
if (this.#markTypeTestPairs()) {
lateVtRound = true;
}
this.#settleQueues();
let wasCancelActive = this.cancellationMachineryActive;
let wasDisposeActive = this.wasm.generatorDisposalActive;
this.activateCancellationMachinery();
// Generator disposal activates here too: its exception-infra
// mint queues reaches, and the loop's next round drains them
// (the activation is once-only, so the fixpoint terminates).
this.activateGeneratorDisposal();
if (this.cancellationMachineryActive != wasCancelActive ||
this.wasm.generatorDisposalActive != wasDisposeActive) {
this.#settleQueues();
lateVtRound = true;
}
}
this.#finishExistentialCasts();
// Discovery is settled. Catch layout up with anything the vtable
// pass or the final drain instantiated, then CLOSE: from here a
// new class cannot get a struct, so becoming instantiated now is a
// bug, and a named one.
//
// A class first instantiated after the class vtable globals were
// built has none, and that is fine while it only inherits. One that
// overrides a method called through a base-typed receiver needs its
// vtable, or the call is lowered as a direct call to the base's
// method. Building its vtable lets #fillReachedSlots reach the
// override, whose body can instantiate further classes, so this
// runs to a fixpoint with layout and the interface vtables.
this.#layoutClassStructs(populated);
while (this.#buildLateOverridingVTableGlobals()) {
this.#settleQueues();
var lateOverrideVtRound = true;
while (lateOverrideVtRound) {
lateOverrideVtRound = this.#buildClassInterfaceVTables();
if (this.#markTypeTestPairs()) {
lateOverrideVtRound = true;
}
this.#settleQueues();
}
this.#layoutClassStructs(populated);
}
// Catching up is not only missing structs: a struct laid out early
// can hold a field baked `structref` for a class a later walk then
// registered — whose method signatures are precise, so the erased
// field fails receiver conformance in lowering. Re-resolve those
// fields against the settled registrations.
this.specializer.refreshErasedFieldTypes();
// And late-instantiated String needs its class vtable global,
// exactly as it needs its struct — $stringCreate is synthesized
// against it, and String can be instantiated as late as a literal
// in a body walked here.
let {stringClass} = this.wasm;
if (stringClass != null) {
let sKey = getClassKey(stringClass);
if (this.instantiatedSpecializedClasses.has(sKey as String)) {
this.#buildClassVTableGlobals(sKey);
this.#settleQueues();
}
}
// Superclass constructor phases: every signature and struct these
// derive from is final once the queues drain, and their bodies are
// slices of already-walked constructor ASTs, so minting here adds
// functions but no discovery.
this.specializer.mintConstructorPhases();
this.instantiationClosed = true;
this.isRtaActive = false;
// The type section is recomputed here rather than accumulated.
// `markTypeReached` runs all through discovery, so `emittedTypes`
// otherwise ends up as "every type anything ever looked at" — for
// `return 42` that is 59 types and a third of the module, most of
// them interface member signatures reached through vtable structs
// of interfaces the program never mentions. Everything the emitted
// module can actually reference is rooted below, and
// closeReachedTypes takes the transitive closure; a type that is
// genuinely needed and missing is a loud wasm validation failure,
// not a silent miscompile.
this.reachedTypesSet.clear();
while (this.emittedTypes.length > 0) {
this.emittedTypes.pop();
}
// A class struct is emitted on EVIDENCE, not declaration: the
// class was instantiated (values exist), or reached code names the
// type — a cast, a type test, a field read on a nullable reference
// — recorded by discoverType during reachable traversal. This used
// to mark every entry in classInfos, and classInfos holds every
// DECLARED class (init pre-registers them all for circular
// definitions), which put 134 struct types in `return 42`'s module.
for (let cPair in this.wasm.classInfos) {
let cKeyStr = cPair.key as String;
// An EXTENSION class's struct is a placeholder: a value of the
// class IS its representation type (typeToValType returns the
// onType), so no cast, test, field read or signature can ever
// name the struct — being named or instantiated keeps the
// class's METHODS reachable, not this pair of dead types.
var isExtensionPlaceholder = false;
{
let ctOpt = cPair.value.structType.classType;
if (ctOpt != null && ctOpt.isExtension) {
isExtensionPlaceholder = true;
}
}
if (!isExtensionPlaceholder &&
(this.instantiatedSpecializedClasses.has(cKeyStr) ||
this.reachablyNamedClasses.has(cKeyStr))) {
this.markTypeReached(cPair.value.structType);
this.markTypeReached(cPair.value.vtableStructType);
}
}
this.#pruneUndispatchedSlots();
this.#layoutTypeTests();
// A global only unreached code names is dropped from the map too: the
// start function initializes the module variables it finds there.
let keptGlobals = new Array<WasmGlobal>();
for (let g in this.wasm.globals) {
if (g.symbolId == noSymbolId || this.reachedGlobals.has(g.symbolId)) {
keptGlobals.push(g);
} else {
this.wasm.globalMap.delete(g.symbolId);
}
}
while (this.wasm.globals.length > 0) { this.wasm.globals.pop(); }
for (let g in keptGlobals) { this.wasm.globals.push(g); }
// The loop below roots every kept global, as the queue walk does, so
// the walk starts again at the end of the shorter list. Left where it
// was, it would skip as many of the globals made from here on (the
// string literals') as were dropped.
this.globalsHead = this.wasm.globals.length;
for (let g in this.wasm.globals) {
this.markValTypeReached(g.type);
let {initVTable} = g;
if (initVTable != null) {
let vtableInit = initVTable;
this.markTypeReached(vtableInit.structType);
for (let func in vtableInit.funcs) {
this.markFunctionReached(func);
}
}
}
this.currentReachable = true;
if (this.wasm.stringClass != null && this.wasm.stringLiterals.size > 0 && !targetUsesJsStrings(this.target)) {
this.wasm.ensureStringLiteralHelpers(this.program.units[0].model);
this.markFunctionReached(this.wasm.stringFromSharedFunc as WasmFunction);
this.markFunctionReached(this.wasm.getStringLiteralFunc as WasmFunction);
}
this.ensureAllHelperFunctionsReached();
this.processQueues();
this.#checkNoPrunedSlotDispatched();
this.#checkNoLateInterfaceSlot();
for (let iface in this.usedInterfaceTypes) {
let iName = getInterfaceKey(iface);
if (this.wasm.interfaceStructs.has(iName)) {
this.markTypeReached(this.wasm.interfaceStructs[iName]);
}
if (this.wasm.interfaceVTableStructs.has(iName)) {
this.markTypeReached(this.wasm.interfaceVTableStructs[iName]);
}
}
for (let t in this.wasm.tags) {
this.markTypeReached(t.signature);
}
for (let f in this.wasm.functionImports) {
this.markTypeReached(f.signature);
}
let originalFunctions = this.wasm.functions;
let reachedList = new Array<WasmFunction>();
for (let f in originalFunctions) {
let isReached = this.reachedFunctionsSet.has(f);
if (isReached) {
reachedList.push(f);
this.markTypeReached(f.signature);
// The captured-variable environment is referenced from the
// lowered body, not from the signature.
let {contextStruct} = f;
if (contextStruct != null) {
this.markTypeReached(contextStruct);
}
}
}
this.wasm.functions = reachedList;
this.wasm.invalidateFunctionIndex();
// Bodies lowered before layout() (the generator and async split
// passes) consult classMethodMap too. Until layout() rebuilds it from
// the reached functions it still names every registered method, so
// such a body could resolve a member to a function that is never
// emitted. Drop those now, so early and late lowering see one map.
let unreachedKeys = new Array<ClassMethodKey>();
for (let mPair in this.wasm.classMethodMap) {
if (!this.reachedFunctionsSet.has(mPair.value)) {
unreachedKeys.push(mPair.key);
}
}
for (let k in unreachedKeys) {
this.wasm.classMethodMap.delete(k);
}
let unreachedStaticKeys = new Array<ClassMethodKey>();
for (let mPair in this.wasm.staticMethodMap) {
if (!this.reachedFunctionsSet.has(mPair.value)) {
unreachedStaticKeys.push(mPair.key);
}
}
for (let k in unreachedStaticKeys) {
this.wasm.staticMethodMap.delete(k);
}
if (this.wasm.stringCreateFunc != null) { this.markTypeReached((this.wasm.stringCreateFunc as WasmFunction).signature); }
if (this.wasm.stringSetByteFunc != null) { this.markTypeReached((this.wasm.stringSetByteFunc as WasmFunction).signature); }
if (this.wasm.stringGetByteFunc != null) { this.markTypeReached((this.wasm.stringGetByteFunc as WasmFunction).signature); }
if (this.wasm.stringGetLengthFunc != null) { this.markTypeReached((this.wasm.stringGetLengthFunc as WasmFunction).signature); }
// Record-dispatch types are referenced from getter BODIES, which
// are synthesized after this pruning and therefore invisible to
// signature-driven reachability: the getters' signatures only
// mention structref. Pruning them leaves index -1 references in
// the synthesized code (invalid wasm). Keep every dispatch's
// types; dispatches are few and their getters are in the
// functions list whenever the dispatch is usable at all.
// Resolve the record/tuple types reached code named into their
// dispatch fat pointers and interned structs, now that discovery
// has settled and every nested dispatch exists.
for (let compT in this.#namedCompositeTypes) {
if (compT is TupleType) {
let elements = new Array<ValType>();
for (let el in compT.elementTypes) {
elements.push(typeToValType(this.wasm, el));
}
this.reachablyNamedAnonStructs.add(this.wasm.getTupleStruct(compT, elements));
} else if (compT is FunctionType) {
this.reachablyNamedClosures.add(
getClosureStruct(this.wasm, compT));
} else if (compT is ArrayType) {
// The raw wasm array of an array VALUE reached code names: an
// index-loop for-in references it directly (array.new_fixed,
// array.get) with no reached signature ever mentioning it.
// typeToValType is the same derivation lowering uses, so the
// marked array is the one the instructions will reference.
let saved = this.currentReachable;
this.currentReachable = true;
this.markValTypeReached(typeToValType(this.wasm, compT));
this.currentReachable = saved;
} else if (compT is InterfaceType) {
let iName = getInterfaceKey(compT);
if (this.wasm.interfaceStructs.has(iName)) {
this.markTypeReached(this.wasm.interfaceStructs[iName]);
}
if (this.wasm.interfaceVTableStructs.has(iName)) {
this.markTypeReached(this.wasm.interfaceVTableStructs[iName]);
}
}
}
// Dispatch types stay WHOLESALE for now, unlike the other roots:
// getRecordDispatch pushes the dispatch's vtable global
// unconditionally, the globals walk below force-reaches its getter
// functions, and the getters' bodies struct.get the concrete type
// — so an evidence gate here prunes types a getter that IS emitted
// still references (`struct_get owner references unemitted
// struct`). Gating these requires pruning unused dispatch GLOBALS
// first, which is its own change.
for (let rd in this.wasm.recordDispatchInfos) {
this.markTypeReached(rd.concreteType);
this.markTypeReached(rd.fatPtrType);
this.markTypeReached(rd.vtableType);
}
for (let rd in this.wasm.adaptedDispatchInfos) {
this.markTypeReached(rd.concreteType);
this.markTypeReached(rd.fatPtrType);
this.markTypeReached(rd.vtableType);
}
// An existential's fat pointer and table, which its packs' slots
// cast to and read (ir/existential.zena).
for (let rd in this.wasm.existentialDispatchInfos) {
this.markTypeReached(rd.fatPtrType);
this.markTypeReached(rd.vtableType);
}
// Closure structs are referenced from lowered bodies, which run
// after layout and are invisible to signature-driven reachability
// — but "every closure struct ever interned" is not the root set:
// plumbing walks mint shapes nothing emitted refers to, each
// dragging its impl signature along. Root the ones RTA recorded
// evidence for; a lowering-time lookup of an unrecorded one is a
// loud index -1, not a silent miscompile.
// Membership comes from the evidence set, but ITERATION follows
// the interned map — a Set<WasmStruct> iterates in uid order,
// which is process-global state (the batch-nondeterminism bug).
for (let pair in this.wasm.closureStructs) {
if (this.reachablyNamedClosures.has(pair.value)) {
this.markTypeReached(pair.value);
}
}
for (let cell in this.tryCellStructs) {
this.markTypeReached(cell);
}
// Boxed tuples and records: named from lowered bodies only — of
// reached functions, whose walks recorded them.
for (let anon in this.wasm.anonymousStructs) {
if (this.reachablyNamedAnonStructs.has(anon)) {
this.markTypeReached(anon);
}
}
this.closeReachedTypes();
this.wasm.types = this.emittedTypes;
performance.end(tLayout3);
}
/**
* Queues `memberName` as a static target on every class `t` names,
* looking through unions (`C | null`) and type aliases (the ownership
* handles `Own<C>` and friends are aliases).
*/
/**
* Reaches what releasing a `t` calls: the `:dispose` of each resource
* class it names, and the `[release]` of each future, through the
* same record a checker-rooted implicit drop leaves
* (`traverseDependencies`). For `releaseOwned<T>` and a store into a
* `scoped T` field in a specialized body, whose generic record could
* not name `T`'s classes. A slot
* target would not do: a final resource class's `:dispose` has no
* slot, and it is called directly.
*/
noteReleaseTargets(t: Type, model: SemanticModel): void {
let classes = new Array<ClassType>();
collectNamedClasses(t, classes, 0, true);
let deps = new SymbolDependencies();
for (let ct in classes) {
let member = releaseMemberOf(ct);
if (member == ":dispose" && !ct.isResource) {
continue;
}
if (member == ":release" && !hasReleaseMember(ct)) {
continue;
}
let symId = (ct.genericSource ?? ct).symbolId;
deps.referencedSymbols.add(symId);
deps.referencedClassMethods.add(`${i32ToString(symId as i32)}.${member}`);
}
if (deps.referencedClassMethods.size > 0) {
this.traverseDependencies(deps, model, null);
}
}
notePendingStaticTargets(t: Type, memberName: String): void {
let classes = new Array<ClassType>();
collectNamedClasses(t, classes, 0);
for (let ct in classes) {
if (isConcrete(ct) && !ct.isMixinIntermediate) {
this.#pendingStaticTargets.push(new PendingStaticTarget(ct, memberName));
}
}
}
/**
* noteReleaseTargets for each owner field of the resource class
* `owner`: what the glue appended to its `:dispose` releases
* (collectAffineDropFields in ir/control-flow.zena). Through the
* release record rather than a static target, since the field's own
* `:dispose` may be synthesized, and a synthesized member has no
* declaration for a static target to find (#493).
*/
#noteOwnerFieldReleases(owner: ClassType, model: SemanticModel): void {
for (let mPair in owner.members) {
let member = mPair.value;
if (!(member is FieldInfo) || member.isStatic) {
continue;
}
let core = soleNonNullMember(member.type) ?? member.type;
if (ownershipHandleOf(core) != OwnershipHandle.Own) {
continue;
}
let fieldType = substituteTypeParamsInCodegen(this.wasm,
getClassTypeParameters(owner), owner.typeArguments, member.type);
this.noteReleaseTargets(fieldType, model);
}
}
/**
* notePendingStaticTargets for each instance field of `owner`. For a
* case class's derived `==` or `hashCode`, a record or tuple field
* also needs its type's comparison or hash function (ir/equality.zena).
*/
#noteFieldStaticTargets(owner: ClassType, memberName: String): void {
for (let mPair in owner.members) {
let member = mPair.value;
if (!(member is FieldInfo) || member.isStatic) {
continue;
}
let fieldType = substituteTypeParamsInCodegen(this.wasm,
getClassTypeParameters(owner), owner.typeArguments, member.type);
this.notePendingStaticTargets(fieldType, memberName);
if (memberName == "==") {
this.visitor.noteValueEquality(fieldType, fieldType, this.getClassModel(owner));
} else if (memberName == "hashCode") {
this.visitor.noteValueHash(fieldType, this.getClassModel(owner));
}
}
}
/**
* Drains the reach queues, then reaches the slot functions that new
* reaches made necessary, until neither adds anything.
*/
#settleQueues(): void {
this.processQueues();
while (this.#syncGenericClassSlots() || this.#fillReachedSlots() ||
this.#drainPendingMemberReaches()) {
this.processQueues();
}
}
/**
* Reaches the members pended since the last drain, and says whether
* it reached any. Nothing is drained before the first drain in `run`,
* which waits for populate. After it, every settle drains, because
* the late rounds walk bodies too: a `new` in a body that only a late
* override reaches pends its synthesized constructor, which nothing
* else reaches, and lowering failed with `constructor missing`.
*/
#drainPendingMemberReaches(): boolean {
if (this.#pendingDrained < 0) {
return false;
}
let savedReachable = this.currentReachable;
this.currentReachable = true;
var reached = false;
// Index loop: draining can push MORE pending reaches (reaching a
// case class's == pends String.== for its string fields).
while (this.#pendingDrained < this.#pendingMemberReaches.length) {
let pendingKey = this.#pendingMemberReaches[this.#pendingDrained];
this.#pendingDrained += 1;
if (let (true, f) = this.wasm.classMethodMap.get(pendingKey)) {
if (!this.reachedFunctionsSet.has(f)) {
this.markFunctionReached(f);
reached = true;
}
}
}
this.currentReachable = savedReachable;
return reached;
}
/**
* The class a vtable slot belongs to: the topmost class in `ct`'s
* superclass chain whose slot list names `slotName`, keyed by its
* generic source so every specialization of a hierarchy shares one
* answer. Every class below that one has the slot at the same index,
* so the slot is kept or dropped for all of them together. Null when
* `ct` has no such slot (static, private and constructor members).
*/
#slotOwnerKey(ct: ClassType, slotName: String): String | null {
// Cached per class by identity, then by slot name, so a lookup
// builds no key string: the concatenated keys were 70K strings
// held for the whole compile.
let perClass = this.#slotOwnerCache.get(ct) ?? new HashMap<String, String>();
this.#slotOwnerCache[ct] = perClass;
let cacheKey = slotName;
if (let (true, cached) = perClass.get(cacheKey)) {
return if (cached == "") null else cached;
}
var owner: ClassType | null = null;
var c: ClassType | null = ct;
while (c != null) {
let cc = c as ClassType;
var listed = false;
for (let n in this.wasm.classVtable(getClassKey(cc))) {
if (n == slotName) {
listed = true;
break;
}
}
if (listed) {
owner = cc;
}
c = cc.superType;
}
if (owner == null) {
perClass[cacheKey] = "";
return null;
}
let o = owner as ClassType;
let key = `${getClassKey(o.genericSource ?? o) as String}|${slotName}`;
perClass[cacheKey] = key;
return key;
}
#slotOwnerCache = new Map<ClassType, HashMap<String, String>>();
var #pendingStaticTargets = new Array<PendingStaticTarget>();
/**
* The slot keys of every reached class method. `ownOnly` keeps only
* methods a class declares below the slot's owner, which are the
* ones that can make a call dispatch: lowering calls a method
* directly unless some subclass of the receiver's class has its own
* reached version (`memberProvidedBySubclass`).
*/
#reachedSlotKeys(ownOnly: boolean): HashSet<String> {
let keys = new Set<String>();
for (let f in this.reachedFunctionsSet) {
let {classType, methodName} = f;
if (classType == null || methodName == null || f.isStatic) {
continue;
}
let ct = classType as ClassType;
let key = this.#slotOwnerKey(ct, methodName as String);
if (key == null) {
continue;
}
if (ownOnly) {
let ownKey = (getClassKey(ct.genericSource ?? ct) as String) + "|" +
(methodName as String);
if (ownKey == (key as String)) {
continue;
}
}
keys.add(key as String);
}
return keys;
}
/**
* Reaches, for every class with a vtable global, the function in
* each slot whose method is reached somewhere in the slot's
* hierarchy. A call through a base-typed receiver reaches the base's
* method, and an instance of a subclass may arrive there, so its
* override has to exist too. This replaces reaching every slot of
* every instantiated class. Returns whether anything new was reached.
*/
#fillReachedSlots(): boolean {
var changed = false;
this.currentReachable = true;
var pendIdx = 0;
while (pendIdx < this.#pendingStaticTargets.length) {
let pend = this.#pendingStaticTargets[pendIdx];
pendIdx += 1;
if (pend.resolved) {
continue;
}
// Only slots matter here: a member with no slot (a generic or
// static method, a constructor, a private member) is never
// dispatched, and its calls reach their own callees.
if (this.#slotOwnerKey(pend.classType, pend.memberName) == null) {
pend.resolved = true;
continue;
}
var c: ClassType | null = pend.classType;
while (c != null) {
let cc = c as ClassType;
let key = getClassMethodKey(getClassKey(cc), pend.memberName);
if (let (true, f) = this.wasm.classMethodMap.get(key)) {
pend.resolved = true;
if (!this.reachedFunctionsSet.has(f)) {
this.markFunctionReached(f);
changed = true;
}
break;
}
c = cc.superType;
}
}
// A resolved target is never looked at again, so the list keeps
// only what the next round has to retry. Left as it was, the list
// held every target ever noted — 200K entries, each with its own
// mangled name string — for the rest of the compile.
let unresolved = new Array<PendingStaticTarget>();
for (let pend in this.#pendingStaticTargets) {
if (!pend.resolved) {
unresolved.push(pend);
}
}
this.#pendingStaticTargets = unresolved;
let keys = this.#reachedSlotKeys(false);
for (let cPair in this.wasm.classInfos) {
let info = cPair.value;
let {vtableGlobal} = info;
if (vtableGlobal == null) {
continue;
}
let init = (vtableGlobal as WasmGlobal).initVTable;
let ct = info.structType.classType;
if (init == null || ct == null) {
continue;
}
let {fields} = init.structType;
for (var i = 0; i < fields.length && i < init.funcs.length; i += 1) {
let f = init.funcs[i];
if (this.reachedFunctionsSet.has(f)) {
continue;
}
let key = this.#slotOwnerKey(ct as ClassType, fields[i].name as String);
if (key != null && keys.has(key as String)) {
this.markFunctionReached(f);
changed = true;
}
}
}
return changed;
}
/**
* Drops, from every class's vtable struct and vtable global, the slots
* nothing can dispatch through: those where no class below the slot's
* owner has its own reached version of the method. Every class in a
* hierarchy loses the same slots, so each vtable struct still extends
* its superclass's. The shape of the hierarchy plays no part: a class
* with no subclasses, a final class, a class with a mixin and a deep
* hierarchy with one overridden method follow the same rule.
*/
#pruneUndispatchedSlots(): void {
// Anything the post-close drain reaches must not need a slot this
// drops; #checkNoPrunedSlotDispatched says so loudly if it does.
while (this.#syncGenericClassSlots() || this.#fillReachedSlots()) {
this.processQueues();
}
let dispatched = this.#reachedSlotKeys(true);
this.#dispatchedSlotKeys = dispatched;
for (let cPair in this.wasm.classInfos) {
let info = cPair.value;
let {vtableStructType} = info;
let ct = info.structType.classType;
if (vtableStructType == null || ct == null) {
continue;
}
let vst = vtableStructType as WasmStruct;
var init: VTableInit | null = null;
let {vtableGlobal} = info;
if (vtableGlobal != null) {
init = (vtableGlobal as WasmGlobal).initVTable;
}
let keptFields = new Array<WasmField>();
let keptFuncs = new Array<WasmFunction>();
for (var i = 0; i < vst.fields.length; i += 1) {
let field = vst.fields[i];
let key = this.#slotOwnerKey(ct as ClassType, field.name as String);
if (key == null || !dispatched.has(key as String)) {
continue;
}
keptFields.push(field);
if (init != null && i < (init as VTableInit).funcs.length) {
keptFuncs.push((init as VTableInit).funcs[i]);
}
}
while (vst.fields.length > 0) {
vst.fields.pop();
}
for (let field in keptFields) {
vst.fields.push(field);
}
if (init != null) {
// The builder made this list, as a GrowableArray.
let funcs = (init as VTableInit).funcs as GrowableArray<WasmFunction>;
while (funcs.length > 0) {
funcs.pop();
}
for (let f in keptFuncs) {
f.isReferenceTaken = true;
funcs.push(f);
}
}
}
}
/**
* Turns the interface type tests the walks recorded into
* class-interface pairs: for each site, every instantiated class
* that implements the tested interface and fits the operand's static
* type. A class-typed operand admits the class and its subclasses,
* an interface-typed one the classes that implement both, and any
* other operand (`anyref`, a type parameter, a union) every
* implementer. A pair's test packs through the class-interface
* vtable, so the pair is marked as an adaptation for
* #buildClassInterfaceVTables, which the caller runs again while
* this finds new pairs. A candidate also needs its class vtable
* global, where #layoutTypeTests stores the type-info pointer.
* Returns whether it found a new pair.
*/
#markTypeTestPairs(): boolean {
var marked = false;
let wasm = this.wasm;
for (let site in wasm.typeTestSites) {
let iKey = getInterfaceKey(site.iface);
let bound = getNonNullableType(baseType(site.source));
let open = !(bound is ClassType || bound is InterfaceType);
if (open) {
wasm.typeTestOpenSite = true;
}
for (let cPair in wasm.classInfos) {
let ctOpt = cPair.value.structType.classType;
if (ctOpt == null) {
continue;
}
let ct = ctOpt;
let cName = cPair.key;
if (ct.isExtension || containsErasedType(ct as Type)) {
continue;
}
let {typeParameters} = ct;
if (typeParameters != null && typeParameters.length > 0 &&
(ct.typeArguments == null || !isConcrete(ct))) {
continue;
}
if (!this.instantiatedSpecializedClasses.has(cName as String)) {
continue;
}
if (!this.#classImplementsKey(ct, iKey)) {
continue;
}
if (bound is ClassType) {
if (!this.cha.isSubclassOf(ct, bound)) {
continue;
}
} else if (bound is InterfaceType) {
if (!this.#classImplementsKey(ct, getInterfaceKey(bound))) {
continue;
}
}
let key = getClassInterfaceKey(cName, iKey);
if (!wasm.typeTestPairs.has(key)) {
wasm.typeTestPairs[key] = true;
wasm.typeTestClasses[cName] = ct;
this.demandPackPair(ct, site.iface);
if (!wasm.typeTestSlots.has(iKey)) {
wasm.typeTestSlots[iKey] = wasm.typeTestSlotInterfaces.length;
wasm.typeTestSlotInterfaces.push(site.iface);
}
if (cPair.value.vtableGlobal == null) {
this.#buildClassVTableGlobals(cName);
}
marked = true;
}
if (open && !wasm.typeTestOpenClasses.has(cName)) {
wasm.typeTestOpenClasses[cName] = true;
}
}
}
return marked;
}
#classImplementsKey(ct: ClassType, iKey: InterfaceKey): boolean {
for (let iface in this.cha.collectAllImplementedInterfaces(ct)) {
if (getInterfaceKey(iface) == iKey) {
return true;
}
}
return false;
}
/**
* Lays out what answers the interface type tests, once discovery
* and slot pruning have settled (docs/design/interface-type-tests.md):
*
* - `TypeInfo`: one field per tested interface, holding the
* class-interface vtable of a class that implements it, or null.
* Each candidate class gets a global of it.
* - `<typeinfo>`: a leading field on the vtable struct of every class
* in a candidate hierarchy, holding that global or null.
* `VTableBase`, with just that field, is the roots' supertype, so
* a test reads the field from the vtable of any such class.
* - `Object`: one `<vtable>` field typed `VTableBase`, the supertype
* of the root struct of every candidate hierarchy some test
* reaches through a non-class operand; the test casts an `anyref`
* to it and reads the vtable. A class-typed operand reads its own
* `<vtable>` field and casts nothing.
* - `FatPtrBase`: the `instance` field alone, the supertype of every
* interface fat pointer struct when some operand can hold a fat
* pointer of any interface, so one cast unwraps it.
*
* The leading field is not a function slot: #pruneUndispatchedSlots
* aligns vtable fields with their functions by index, so this runs
* after it, and the field's value travels in `VTableInit.slotGlobals`.
*/
#layoutTypeTests(): void {
let wasm = this.wasm;
if (wasm.typeTestSlotInterfaces.length == 0) {
return;
}
let model = this.program.units[0].model;
this.currentReachable = true;
// A chained test on an operand that can hold a fat pointer of any
// interface unwraps it through `FatPtrBase` on its miss path, so
// the base exists whenever such an operand does, slots or not.
if (wasm.typeTestOpenSite) {
let fatBase = new WasmStruct("FatPtrBase", growable<WasmField>([
new WasmField("instance", new ValTypeAnyRef(), false),
]));
wasm.types.push(fatBase);
wasm.fatPointerBaseStruct = fatBase;
for (let pair in wasm.interfaceStructs) {
let st = pair.value;
if (st.superStruct == null) {
st.superStruct = fatBase;
}
}
this.markTypeReached(fatBase);
}
// An interface with few candidate pairs is tested by a chain of
// class tests, each an inline compare against a final struct, and
// gets no slot; the slots, and everything below, are for the rest.
let pairCounts = new HashMap<InterfaceKey, i32>();
for (let pPair in wasm.typeTestPairs) {
let iKey = pPair.key.interfaceKey;
var n = 0;
if (let (true, seen) = pairCounts.get(iKey)) {
n = seen;
}
pairCounts[iKey] = n + 1;
}
let slotInterfaces = new Array<InterfaceType>();
for (let iface in wasm.typeTestSlotInterfaces) {
let iKey = getInterfaceKey(iface);
var n = 0;
if (let (true, seen) = pairCounts.get(iKey)) {
n = seen;
}
if (n <= typeTestChainMax) {
wasm.typeTestChained[iKey] = iface;
} else {
slotInterfaces.push(iface);
}
}
while (wasm.typeTestSlotInterfaces.length > 0) {
wasm.typeTestSlotInterfaces.pop();
}
wasm.typeTestSlots.clear();
for (let iface in slotInterfaces) {
wasm.typeTestSlots[getInterfaceKey(iface)] = wasm.typeTestSlotInterfaces.length;
wasm.typeTestSlotInterfaces.push(iface);
}
if (slotInterfaces.length == 0) {
return;
}
// The candidate classes of some slot interface.
let slotClasses = new Map<ClassKey, ClassType>();
for (let cPair in wasm.typeTestClasses) {
for (let iface in slotInterfaces) {
if (wasm.typeTestPairs.has(getClassInterfaceKey(cPair.key, getInterfaceKey(iface)))) {
slotClasses[cPair.key] = cPair.value;
break;
}
}
}
let infoFields = new Array<WasmField>();
for (var i = 0; i < wasm.typeTestSlotInterfaces.length; i += 1) {
let iKey = getInterfaceKey(wasm.typeTestSlotInterfaces[i]);
if (!wasm.interfaceVTableStructs.has(iKey)) {
throw new Error(`Internal error: tested interface ${iKey as String} has no vtable struct`);
}
infoFields.push(new WasmField(typeTestSlotName(i),
new ValTypeRefNull(wasm.interfaceVTableStructs[iKey]), false));
}
let typeInfo = new WasmStruct("TypeInfo", infoFields);
wasm.types.push(typeInfo);
wasm.typeInfoStruct = typeInfo;
let vtableBase = new WasmStruct("VTableBase", growable<WasmField>([
new WasmField("<typeinfo>", new ValTypeRefNull(typeInfo), false),
]));
wasm.types.push(vtableBase);
wasm.vtableBaseStruct = vtableBase;
// The hierarchies the candidates belong to, by root vtable struct,
// and the roots some test reaches through a non-class operand.
let candidateRoots = new HashSet<WasmStruct>();
let objectRoots = new Array<WasmStruct>();
let objectRootSet = new HashSet<WasmStruct>();
for (let cPair in slotClasses) {
let cName = cPair.key;
let info = wasm.classInfos[cName];
if (info.vtableGlobal == null || info.vtableStructType == null) {
throw new Error(`Internal error: type-test candidate ${cName as String} has no class vtable`);
}
candidateRoots.add(rootStruct(info.vtableStructType as WasmStruct));
if (wasm.typeTestOpenClasses.has(cName)) {
let root = rootStruct(info.structType);
if (!objectRootSet.has(root)) {
objectRootSet.add(root);
objectRoots.push(root);
}
}
}
// `<typeinfo>` leads every vtable struct in a candidate hierarchy.
// The root's field object is shared down the hierarchy, as every
// inherited field is.
let rootFields = new HashMap<WasmStruct, WasmField>();
// Every vtable struct in a candidate hierarchy, collected before the
// roots are linked below: once a root extends `VTableBase`, walking
// up from a struct ends there instead.
let candidateVsts = new HashSet<WasmStruct>();
for (let cPair in wasm.classInfos) {
let vstOpt = cPair.value.vtableStructType;
if (vstOpt == null) {
continue;
}
let vst = vstOpt;
// The hierarchy's root, which an earlier class in the hierarchy
// may already have linked to `VTableBase`.
var root = vst;
while (root.superStruct != null && root.superStruct !== vtableBase) {
root = root.superStruct as WasmStruct;
}
if (!candidateRoots.has(root)) {
continue;
}
candidateVsts.add(vst);
var field: WasmField | null = null;
if (let (true, f) = rootFields.get(root)) {
field = f;
} else {
let f = new WasmField("<typeinfo>", new ValTypeRefNull(typeInfo), false);
rootFields[root] = f;
field = f;
}
if (vst.fieldIndexByName("<typeinfo>") < 0) {
prependField(vst, field as WasmField);
}
if (root.superStruct == null) {
root.superStruct = vtableBase;
}
}
if (objectRoots.length > 0) {
let objectStruct = new WasmStruct("Object", growable<WasmField>([
new WasmField("<vtable>", new ValTypeRefNull(vtableBase), false),
]));
wasm.types.push(objectStruct);
wasm.objectStruct = objectStruct;
for (let root in objectRoots) {
if (root.superStruct == null) {
root.superStruct = objectStruct;
}
}
this.markTypeReached(objectStruct);
}
// One TypeInfo global per candidate class, then the pointer to it
// in the class vtable; every other vtable in the hierarchy stores
// null there.
for (let cPair in slotClasses) {
let cName = cPair.key;
let slots = new Array<WasmGlobal | null>();
for (let iface in wasm.typeTestSlotInterfaces) {
let key = getClassInterfaceKey(cName, getInterfaceKey(iface));
let g = wasm.getClassInterfaceVTable(key);
if (g == null && wasm.typeTestPairs.has(key)) {
throw new Error(`Internal error: type-test pair ${cName as String} as ${getInterfaceKey(iface) as String} has no vtable`);
}
slots.push(g);
}
let init = new VTableInit(typeInfo, new Array<WasmFunction>());
init.slotGlobals = slots;
let name = `${cName as String}_TypeInfo`;
let g = new WasmGlobal(name, name, new ValTypeRef(typeInfo), false,
null, init, model);
wasm.globals.push(g);
wasm.typeInfoGlobals[cName] = g;
}
for (let cPair in wasm.classInfos) {
let info = cPair.value;
let vstOpt = info.vtableStructType;
let gOpt = info.vtableGlobal;
if (vstOpt == null || gOpt == null || !candidateVsts.has(vstOpt)) {
continue;
}
let init = gOpt.initVTable;
if (init == null) {
continue;
}
var tiGlobal: WasmGlobal | null = null;
if (let (true, ti) = wasm.typeInfoGlobals.get(cPair.key)) {
tiGlobal = ti;
}
init.slotGlobals = growable<WasmGlobal | null>([tiGlobal]);
}
this.markTypeReached(typeInfo);
this.markTypeReached(vtableBase);
this.#orderGlobalInitializers();
}
/**
* Reorders `wasm.globals` so that every global an initializer reads
* (`VTableInit.slotGlobals`, a singleton's class vtable) is declared
* before the global that reads it, keeping the order otherwise.
*/
#orderGlobalInitializers(): void {
let wasm = this.wasm;
for (var i = 0; i < wasm.globals.length; i += 1) {
wasm.globals[i].index = i;
}
let placed = new Array<boolean>();
for (let g in wasm.globals) {
placed.push(false);
}
let ordered = new Array<WasmGlobal>();
for (let g in wasm.globals) {
this.#placeGlobal(g, ordered, placed);
}
while (wasm.globals.length > 0) {
wasm.globals.pop();
}
for (let g in ordered) {
wasm.globals.push(g);
}
}
#placeGlobal(g: WasmGlobal, ordered: GrowableArray<WasmGlobal>,
placed: GrowableArray<boolean>): void {
if (g.index < 0 || placed[g.index]) {
return;
}
placed[g.index] = true;
let init = g.initVTable;
if (init != null) {
let slots = init.slotGlobals;
if (slots != null) {
for (let s in slots) {
if (s != null) {
this.#placeGlobal(s, ordered, placed);
}
}
}
}
let singleton = g.initSingletonStruct;
if (singleton != null) {
if (let (true, info) = this.wasm.classInfos.get(getClassKey(singleton))) {
let vt = info.vtableGlobal;
if (vt != null) {
this.#placeGlobal(vt, ordered, placed);
}
}
}
ordered.push(g);
}
var #dispatchedSlotKeys = new Set<String>();
/**
* After the post-close drain: every slot a call could now dispatch
* through must have survived pruning. A method reached this late
* that overrides one below a slot's owner would make lowering
* dispatch through a slot that no longer exists.
*/
#checkNoPrunedSlotDispatched(): void {
for (let key in this.#reachedSlotKeys(true)) {
if (!this.#dispatchedSlotKeys.has(key)) {
throw new Error("Internal error: vtable slot " + key +
" became dispatchable after slots were pruned");
}
}
}
/**
* After the post-close drain: an interface member demanded this late
* would get a slot that pair vtables built earlier have no trampoline
* for, and the class's method would never be reached.
*/
#checkNoLateInterfaceSlot(): void {
let addedSlots = this.#syncInterfaceSlots();
if (!this.#syncGenericInterfaceSlots() && !addedSlots) {
return;
}
for (let entry in this.wasm.classInterfaceVTables) {
let init = entry.value.initVTable;
if (init != null && init.funcs.length < init.structType.fields.length) {
throw new Error(`Internal error: interface vtable ${entry.value.name} ` +
"gained a slot after the class-interface vtables were built");
}
}
}
/**
* Builds the class vtable global for each instantiated class that has
* none yet and declares its own version of a slot whose method is
* reached somewhere in the slot's hierarchy. Without it, lowering sees
* no reached override below the receiver's class and calls the base's
* method directly, so an instance of this class would run the wrong
* method. Returns whether any global was built.
*/
#buildLateOverridingVTableGlobals(): boolean {
let reachedKeys = this.#reachedSlotKeys(false);
let lateKeys = new Array<ClassKey>();
for (let cPair in this.wasm.classInfos) {
let cName = cPair.key;
let info = cPair.value;
let ct = info.structType.classType;
if (info.vtableGlobal != null || info.vtableStructType == null ||
ct == null || !this.instantiatedSpecializedClasses.has(cName as String)) {
continue;
}
let overrides = this.wasm.classVtable(cName).some((slotName) => {
if (!this.wasm.classMethodMap.has(getClassMethodKey(cName, slotName))) {
return false;
}
let key = this.#slotOwnerKey(ct, slotName);
return key != null && reachedKeys.has(key);
});
if (overrides) {
lateKeys.push(cName);
}
}
for (let cName in lateKeys) {
this.#buildClassVTableGlobals(cName);
}
return lateKeys.length > 0;
}
/**
* Pass 1.5: builds the class vtable global for every instantiated
* class that does not have one yet. Incremental — classes with a
* vtableGlobal are skipped. `onlyKey` restricts a re-run to one
* class: at the settle point it runs again for String alone, because
* $stringCreate is synthesized against String's vtable global and a
* literal in a body walked late instantiates String after the main
* pass. Other late-instantiated classes get one only when they
* override a method that something calls through a base-typed
* receiver (#buildLateOverridingVTableGlobals); a class that only
* inherits needs none, and building them for all late classes cost
* array-sum 13 functions and 9 globals.
*/
#buildClassVTableGlobals(onlyKey: ClassKey | null = null): void {
for (let cPair in this.wasm.classInfos) {
let cName = cPair.key;
let info = cPair.value;
if (onlyKey != null && cName != (onlyKey as ClassKey)) {
continue;
}
if (info.vtableGlobal != null) {
continue;
}
let {vtableStructType} = info;
if (vtableStructType != null) {
let vstVal = vtableStructType;
let cType = vstVal.classType as ClassType;
let {typeParameters} = cType;
let isGenericTemplate = typeParameters != null &&
typeParameters.length > 0 &&
(cType.typeArguments == null || !isConcrete(cType));
if (isGenericTemplate) {
continue;
}
// Slot order must extend the base's: a dispatch through a
// base-typed receiver indexes the base's layout, and the
// instance's vtable is the subclass's. Both merge sites
// (Pass 0.6 and registerSpecializedClass) prefix the super's
// list, but a slot registered AFTER either merge lands
// wherever registration put it — batch-history-dependent —
// and a subclass whose base list filled late ends up with a
// permuted layout that type-checks (every slot is funcref)
// and dispatches the wrong method. Rebuild the order here,
// super chain root-first, before the global bakes it.
let chain = new Array<ClassType>();
var cc: ClassType | null = cType;
while (cc != null) {
chain.push(cc as ClassType);
cc = (cc as ClassType).superType;
}
let orderedNames = new Array<String>();
let seenNames = new Set<String>();
var ci = chain.length - 1;
while (ci >= 0) {
for (let n in this.wasm.classVtable(getClassKey(chain[ci]))) {
if (!seenNames.has(n)) {
seenNames.add(n);
orderedNames.push(n);
}
}
ci -= 1;
}
let fieldByName = new Map<String, WasmField>();
for (let field in vstVal.fields) {
fieldByName[field.name as String] = field;
}
// Names in ancestor lists whose slots this class does not
// carry (pruned) are skipped; a field with no list entry
// would be a bookkeeping bug and keeps its tail position.
let orderedFields = new Array<WasmField>();
for (let n in orderedNames) {
if (let (true, f) = fieldByName.get(n)) {
orderedFields.push(f);
fieldByName.delete(n);
}
}
for (let field in vstVal.fields) {
if (fieldByName.has(field.name as String)) {
orderedFields.push(field);
}
}
let methods = new Array<WasmFunction>();
let newFields = new Array<WasmField>();
for (let field in orderedFields) {
var foundFunc: WasmFunction | null = null;
var currClass: ClassType | null = cType;
while (currClass != null && foundFunc == null) {
let key = getClassMethodKey(getClassKey(currClass), field.name as String);
if (this.wasm.classMethodMap.has(key)) {
foundFunc = this.wasm.classMethodMap[key];
break;
}
currClass = currClass.superType;
}
if (foundFunc != null) {
newFields.push(field);
methods.push(foundFunc);
} else {
throw new Error(`Internal error: class ${cName as String} does not implement vtable method: ${field.name as String}`);
}
}
while (vstVal.fields.length > 0) {
vstVal.fields.pop();
}
for (var fIdx = 0; fIdx < newFields.length; fIdx += 1) {
vstVal.fields.push(newFields[fIdx]);
}
if (!this.instantiatedSpecializedClasses.has(cName as String)) {
continue;
}
// No slot function is reached here: #fillReachedSlots reaches
// the ones whose method is reached anywhere in the hierarchy,
// and #pruneUndispatchedSlots drops the rest before emission.
let vtableInit = new VTableInit(vstVal, methods, false);
vtableInit.isClassVTable = true;
let vName = getClassVTableName(cName);
let vtableGlobal = new WasmGlobal(
vName,
vName,
new ValTypeRef(vstVal),
false,
null,
vtableInit,
this.program.units[0].model
);
this.wasm.globals.push(vtableGlobal);
info.vtableGlobal = vtableGlobal;
}
}
}
/**
* Records a virtual use of a generic interface method: one demand
* per (interface specialization, solved type-argument list). The
* demand's slot is appended to the interface's vtable struct by
* `#syncGenericInterfaceSlots`, inside the class-interface vtable
* fixpoint, so a demand discovered in any round still gets its slot
* and every already-built pair vtable is patched to cover it.
*/
demandGenericInterfaceMethod(it: InterfaceType, methName: String, typeArgs: Array<Type>, model: SemanticModel): void {
let iKey = getInterfaceKey(it);
let slotName = getSpecializedName(methName, typeArgs);
let dedupKey = `${iKey as String}.${slotName}`;
if (this.#genericInterfaceDemandsByKey.has(dedupKey)) {
return;
}
this.typeLowerer.discoverType(it as Type, model);
for (let a in typeArgs) {
this.typeLowerer.discoverType(a, model);
}
let d = new GenericInterfaceMethodDemand(it, methName, slotName, typeArgs, model);
this.#genericInterfaceDemandsByKey[dedupKey] = d;
this.genericInterfaceMethodDemands.push(d);
}
demandInterfaceMember(it: InterfaceType, memberName: String): void {
if (!this.currentReachable) {
return;
}
let id = (it.genericSource ?? it).symbolId;
this.#demandedInterfaceMembers.add(`${i32ToString(id as i32)}.${memberName}`);
}
noteArrayPattern(): void {
if (this.currentReachable) {
this.#arrayPatternReached = true;
}
}
/**
* Appends to each interface's vtable struct a slot for every member
* that reachable code calls through the interface or through one it
* extends, and returns whether it added any. A slot comes with a
* trampoline for each class packed as the interface, and the
* trampoline reaches the class's method, so a slot nothing dispatches
* through keeps that method and everything it constructs (#425).
*
* A member demanded through an interface this one extends gets a slot
* here too: an upcast (`repackInterface`) copies the target
* interface's slots out of the source's vtable by name. Slots are
* appended in the order demands are found. Dispatch looks a slot up by
* name, and #buildClassInterfaceVTables extends pair vtables that were
* built before the slot existed.
*/
#syncInterfaceSlots(): boolean {
// Every term only grows, so an unchanged sum means nothing changed.
let state = this.#demandedInterfaceMembers.size +
this.interfaceDecls.size + this.specializedInterfaces.length +
(if (this.#arrayPatternReached) 1 else 0);
if (state == this.#interfaceSlotSyncState) {
return false;
}
this.#interfaceSlotSyncState = state;
var changed = false;
for (let pair in this.interfaceDecls) {
let model = this.interfaceModels[pair.key];
if (this.#addDemandedSlots(model.getNodeType(pair.value) as InterfaceType)) {
changed = true;
}
}
// Index loop: computing a slot's signature can specialize further
// interfaces, which the next call picks up.
var i = 0;
while (i < this.specializedInterfaces.length) {
if (this.#addDemandedSlots(this.specializedInterfaces[i])) {
changed = true;
}
i += 1;
}
return changed;
}
#addDemandedSlots(it: InterfaceType): boolean {
let iKey = getInterfaceKey(it);
if (!this.wasm.interfaceVTableStructs.has(iKey)) {
return false;
}
let vst = this.wasm.interfaceVTableStructs[iKey];
let lineage = this.#interfaceLineage(it);
var changed = false;
for (let key in it.members.keys()) {
let member = it.members[key];
if (member is FieldInfo) {
if (this.#addSlotIfDemanded(it, vst, lineage, "get#" + key, false)) {
changed = true;
}
if (member.isMutable &&
this.#addSlotIfDemanded(it, vst, lineage, "set#" + key, false)) {
changed = true;
}
} else if (member is MethodInfo) {
// A generic method's slots are per specialization
// (#syncGenericInterfaceSlots).
if (!isGenericMethod(member) &&
this.#addSlotIfDemanded(it, vst, lineage, key, true)) {
changed = true;
}
}
}
return changed;
}
/**
* Appends the slot of member `name` of `it` (every overload's, for a
* method) to `vst` if it is demanded and not there yet.
*/
#addSlotIfDemanded(it: InterfaceType, vst: WasmStruct,
lineage: GrowableArray<SymbolId>, name: String, isMethod: boolean): boolean {
let slottedKey = `${getInterfaceKey(it) as String}|${name}`;
if (this.#slottedInterfaceMembers.has(slottedKey) ||
!this.#isInterfaceMemberDemanded(lineage, name)) {
return false;
}
this.#slottedInterfaceMembers.add(slottedKey);
if (isMethod) {
pushInterfaceMethodSlots(this.wasm, it, name, vst);
} else {
let sig = getInterfaceMemberSignature(this.wasm, it, name);
vst.fields.push(new WasmField(name, new ValTypeRef(sig), false));
}
return true;
}
#isInterfaceMemberDemanded(lineage: GrowableArray<SymbolId>, name: String): boolean {
if (this.#arrayPatternReached &&
(name == "[]" || name == "get#length" || name == "length")) {
return true;
}
for (let id in lineage) {
if (this.#demandedInterfaceMembers.has(`${i32ToString(id as i32)}.${name}`)) {
return true;
}
}
return false;
}
#interfaceLineage(it: InterfaceType): GrowableArray<SymbolId> {
let decl = it.genericSource ?? it;
if (let (true, cached) = this.#interfaceLineages.get(decl.symbolId)) {
return cached;
}
let ids = new Array<SymbolId>();
let seen = new Set<SymbolId>();
let pending = growable<InterfaceType>([decl]);
var i = 0;
while (i < pending.length) {
let curr = pending[i].genericSource ?? pending[i];
i += 1;
if (seen.has(curr.symbolId)) {
continue;
}
seen.add(curr.symbolId);
ids.push(curr.symbolId);
for (let ext in curr.extendsList) {
pending.push(ext);
}
}
this.#interfaceLineages[decl.symbolId] = ids;
return ids;
}
findGenericInterfaceDemand(iKey: String, slotName: String): GenericInterfaceMethodDemand | null {
let dedupKey = `${iKey}.${slotName}`;
if (let (true, d) = this.#genericInterfaceDemandsByKey.get(dedupKey)) {
return d;
}
return null;
}
/**
* Appends a vtable slot field for each pending demand whose
* interface has been discovered. Slots land after every declared
* (non-generic) member Pass 0.8 populated, in demand order — both
* deterministic, so the field order is too.
*/
#syncGenericInterfaceSlots(): boolean {
var changed = false;
for (let d in this.genericInterfaceMethodDemands) {
if (d.slotAdded) {
continue;
}
let iKey = getInterfaceKey(d.interfaceType);
if (!this.wasm.interfaceVTableStructs.has(iKey)) {
this.typeLowerer.discoverType(d.interfaceType as Type, d.model);
}
if (!this.wasm.interfaceVTableStructs.has(iKey)) {
continue;
}
let vst = this.wasm.interfaceVTableStructs[iKey];
if (vst.fieldIndexByName(d.slotName) >= 0) {
d.slotAdded = true;
continue;
}
let sig = getGenericInterfaceMemberSignature(this.wasm, d.interfaceType, d.methName, d.typeArgs);
vst.fields.push(new WasmField(d.slotName, new ValTypeRef(sig), false));
d.slotAdded = true;
changed = true;
}
return changed;
}
/**
* Records a virtual use of a generic class method: one demand per
* (hierarchy root class, method name, solved type-argument list).
* `#syncGenericClassSlots` appends the specialized slot name across
* the root class's hierarchy and specializes overrides on concrete
* subclasses.
*/
demandGenericClassMethod(
classType: ClassType,
methodName: String,
typeArgs: Array<Type>,
model: SemanticModel): void {
let rootClass = getMemberRootClass(classType, methodName);
let rootKey = getClassKey(rootClass);
let slotName = getSpecializedName(methodName, typeArgs);
let dedupKey = `${rootKey as String}.${slotName}`;
if (this.#genericClassDemandsByKey.has(dedupKey)) {
return;
}
this.typeLowerer.discoverType(rootClass, model);
for (let typeArg in typeArgs) {
this.typeLowerer.discoverType(typeArg, model);
}
let demand = new GenericClassMethodDemand(
rootClass, methodName, slotName, typeArgs, model);
this.#genericClassDemandsByKey[dedupKey] = demand;
this.genericClassMethodDemands.push(demand);
}
/**
* Syncs every recorded `GenericClassMethodDemand` across all known
* classes in the demand's `rootClass` hierarchy, top-down from
* superclass to subclass.
*/
#syncGenericClassSlots(): boolean {
if (this.genericClassMethodDemands.length == 0) {
return false;
}
let updatedClasses = new Array<ClassType>();
let updatedSet = new Set<String>();
let classes = new Array<ClassType>();
for (let entry in this.wasm.classInfos) {
let classType = entry.value.structType.classType;
if (classType != null) {
classes.push(classType);
}
}
var demandIndex = 0;
while (demandIndex < this.genericClassMethodDemands.length) {
let demand = this.genericClassMethodDemands[demandIndex];
demandIndex += 1;
let rootKey = getClassKey(demand.rootClass);
for (let classType in classes) {
var inHierarchy = false;
var ancestor: ClassType | null = classType;
while (ancestor != null) {
if (getClassKey(ancestor) == rootKey) {
inHierarchy = true;
break;
}
ancestor = ancestor.superType;
}
if (inHierarchy) {
this.#syncClassForDemand(
demand, classType, rootKey, updatedClasses, updatedSet);
}
}
}
if (updatedClasses.length == 0) {
return false;
}
this.#slotOwnerCache.clear();
for (let classType in updatedClasses) {
this.#rebuildClassVTableOrder(classType);
}
return true;
}
#syncClassForDemand(
demand: GenericClassMethodDemand,
classType: ClassType,
rootKey: ClassKey,
updatedClasses: GrowableArray<ClassType>,
updatedSet: HashSet<String>): void {
let classKey = getClassKey(classType);
let classKeyStr = classKey as String;
if (demand.syncedClasses.has(classKeyStr)) {
return;
}
let superType = classType.superType;
if (classKey != rootKey && superType != null) {
this.#syncClassForDemand(
demand, superType, rootKey, updatedClasses, updatedSet);
}
demand.syncedClasses.add(classKeyStr);
let {typeParameters} = classType;
let isGenericTemplate = typeParameters != null &&
typeParameters.length > 0 &&
(classType.typeArguments == null || !isConcrete(classType));
if (classType.isExtension || classType.isMixinIntermediate ||
isGenericTemplate || !isConcrete(classType) ||
containsErasedType(classType)) {
return;
}
let vtableSlots = this.wasm.classVtable(classKey);
var hasSlot = false;
for (let existing in vtableSlots) {
if (existing == demand.slotName) {
hasSlot = true;
break;
}
}
if (!hasSlot) {
vtableSlots.push(demand.slotName);
}
let hasEvidence = this.#classHasEmissionEvidence(classType);
let savedReachable = this.currentReachable;
let savedLayingOut = this.layingOutUnemittedClass;
if (!hasEvidence) {
this.currentReachable = false;
this.layingOutUnemittedClass = true;
}
let unspecializedId = (classType.genericSource ?? classType).symbolId;
let classDecl = if (let (true, decl) = this.classDecls.get(unspecializedId)) decl else null;
let targetModel = this.getClassModel(classType);
let methodDecls = this.cha.findImplementingMethods(classType, demand.methodName);
for (let methodDecl in methodDecls) {
if (methodDecl.isStatic || methodDecl.typeParameters == null ||
methodDecl.typeParameters.length != demand.typeArgs.length) {
continue;
}
let mixScope = if (this.classModels.has(unspecializedId)) {
mixinScopeOfMember(this.program, this.classModels[unspecializedId], classDecl, methodDecl)
} else {
null
};
let nodeModel = (if (this.classModels.has(unspecializedId)) {
mixinModelOfMember(this.program, this.classModels[unspecializedId], classDecl, methodDecl)
} else {
null
}) ?? this.getNodeModel(methodDecl, targetModel);
let specializedFunc = this.specializer.instantiateGenericMethod(
classType, classDecl, demand.methodName, methodDecl, demand.typeArgs, nodeModel);
if (specializedFunc.classType == classType) {
specializedFunc.declaringType =
findDeclaringMixinIntermediate(classType, this.classDecls, methodDecl);
applyMixinPrivateScope(specializedFunc, methodDecl, mixScope);
}
}
var hasImplementation = false;
var ancestor: ClassType | null = classType;
while (ancestor != null) {
let methodKey = getClassMethodKey(getClassKey(ancestor), demand.slotName);
if (this.wasm.classMethodMap.has(methodKey)) {
hasImplementation = true;
break;
}
ancestor = ancestor.superType;
}
if (!hasImplementation) {
let stub = this.specializer.registerClassMethod(
classType, classDecl, demand.slotName, null, false, false, null, targetModel, demand.typeArgs);
stub.isVtableSlotStub = true;
}
this.currentReachable = savedReachable;
this.layingOutUnemittedClass = savedLayingOut;
if (!updatedSet.has(classKeyStr)) {
updatedSet.add(classKeyStr);
updatedClasses.push(classType);
}
}
/**
* Re-orders a laid-out class's `vtableStructType.fields` (and
* `vtableGlobal.initVTable.funcs` when already built) root-first
* after `#syncGenericClassSlots` adds a generic method slot.
*/
#rebuildClassVTableOrder(classType: ClassType): void {
let classKey = getClassKey(classType);
if (let (true, info) = this.wasm.classInfos.get(classKey)) {
if (info.structType.fields.length == 0) {
return;
}
let {vtableStructType} = info;
if (vtableStructType == null) {
return;
}
let chain = new Array<ClassType>();
var ancestor: ClassType | null = classType;
while (ancestor != null) {
chain.push(ancestor);
ancestor = ancestor.superType;
}
let orderedNames = new Array<String>();
let seenNames = new Set<String>();
var chainIndex = chain.length - 1;
while (chainIndex >= 0) {
for (let slotName in this.wasm.classVtable(getClassKey(chain[chainIndex]))) {
if (!seenNames.has(slotName)) {
seenNames.add(slotName);
orderedNames.push(slotName);
}
}
chainIndex -= 1;
}
let fieldByName = new Map<String, WasmField>();
for (let field in vtableStructType.fields) {
let fieldName = field.name;
if (fieldName != null) {
fieldByName[fieldName] = field;
}
}
let orderedFields = new Array<WasmField>();
for (let slotName in orderedNames) {
if (let (true, existingField) = fieldByName.get(slotName)) {
orderedFields.push(existingField);
fieldByName.delete(slotName);
} else {
orderedFields.push(new WasmField(slotName, new ValTypeFuncRef(), false));
}
}
for (let field in vtableStructType.fields) {
let fieldName = field.name;
if (fieldName != null && fieldByName.has(fieldName)) {
orderedFields.push(field);
}
}
let methods = new Array<WasmFunction>();
let newFields = new Array<WasmField>();
for (let field in orderedFields) {
let fieldName = field.name;
if (fieldName == null) {
continue;
}
var foundFunc: WasmFunction | null = null;
var currClass: ClassType | null = classType;
while (currClass != null && foundFunc == null) {
let key = getClassMethodKey(getClassKey(currClass), fieldName);
if (this.wasm.classMethodMap.has(key)) {
foundFunc = this.wasm.classMethodMap[key];
break;
}
currClass = currClass.superType;
}
if (foundFunc != null) {
newFields.push(field);
methods.push(foundFunc);
}
}
while (vtableStructType.fields.length > 0) {
vtableStructType.fields.pop();
}
for (let field in newFields) {
vtableStructType.fields.push(field);
}
let {vtableGlobal} = info;
if (vtableGlobal != null) {
let init = vtableGlobal.initVTable;
if (init != null) {
let funcs = init.funcs as GrowableArray<WasmFunction>;
while (funcs.length > 0) {
funcs.pop();
}
for (let method in methods) {
funcs.push(method);
}
}
}
}
}
/**
* The implementing class's own view of a generic interface method at
* one type-argument list: the class's declared member type with the
* class's type arguments, `this`, and the method's type parameters
* substituted. What the class's monomorphized copy was compiled
* against, so the trampoline adaptation compares the interface view
* to this.
*/
#implGenericMethodType(cType: ClassType, methName: String, typeArgs: Array<Type>): FunctionType | null {
var declared: FunctionType | null = null;
var declaring: ClassType | null = cType;
while (declaring != null && declared == null) {
let dc = declaring;
if (dc.members.has(methName)) {
let mi = dc.members[methName];
if (mi.type is FunctionType) {
declared = mi.type as FunctionType;
}
}
declaring = dc.superType;
}
if (declared == null) {
return null;
}
var sub = substituteTypeParamsInClassContext(this.wasm, cType, declared as Type);
sub = substituteThisTypeInCodegen(cType as Type, sub);
if (!(sub is FunctionType)) {
return null;
}
var subFt = sub as FunctionType;
let mtps = subFt.typeParameters;
if (mtps != null && mtps.length > 0) {
let resub = substituteTypeParamsInCodegen(this.wasm, mtps, typeArgs, subFt as Type);
if (!(resub is FunctionType)) {
return null;
}
subFt = resub as FunctionType;
}
return subFt;
}
/**
* Whether two types lower to the same wasm value type. Ref targets
* compare by identity — type-section indexes are not assigned until
* layout, so the index-based `valTypeEquals` would call every pair
* of refs equal here.
*/
#sameLoweredType(a: Type, b: Type): boolean {
if (a === b) {
return true;
}
let va = typeToValType(this.wasm, a);
let vb = typeToValType(this.wasm, b);
return match (va) {
case ValTypeRef as ta: match (vb) {
case ValTypeRef as tb: ta.target == tb.target
case _: false
}
case ValTypeRefNull as ta: match (vb) {
case ValTypeRefNull as tb: ta.target == tb.target
case _: false
}
case _: match (vb) {
case ValTypeRef: false
case ValTypeRefNull: false
case _: valTypeToOpcode(va) == valTypeToOpcode(vb)
}
};
}
/**
* 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 type
* parameters (a generic function's declaration, an erasure's
* referrer), and the walk of the same body under each substitution
* marks the specialization that substitution packs. Dependency
* records, which name a pair by its declarations, come here too.
*/
demandPackPair(c: ClassType, i: InterfaceType): void {
if (isConcrete(c) && isConcrete(i) &&
!containsErasedType(c) && !containsErasedType(i)) {
this.wasm.usedInterfaceAdaptations.add(
getClassInterfaceKey(getClassKey(c), getInterfaceKey(i)));
}
}
isPackPairUsed(c: ClassType, i: InterfaceType): boolean {
return this.wasm.usedInterfaceAdaptations.has(
getClassInterfaceKey(getClassKey(c), getInterfaceKey(i)));
}
/**
* The interface packs a function-adaptation wrapper from `src` to
* `tgt` makes (AdaptationPack): an argument the target passes as a
* class or a sub-interface where the source takes an interface, and a
* result the source returns as one where the target returns an
* interface.
*/
#functionAdaptationPacks(src: FunctionType, tgt: FunctionType): GrowableArray<AdaptationPack> {
let packs = new Array<AdaptationPack>();
// The source takes a prefix of the target's parameters (lowering
// forwards that many).
let shared = if (src.parameters.length < tgt.parameters.length) {
src.parameters.length
} else {
tgt.parameters.length
};
let lowered = growable<ValType>([new ValTypeStructRef()]); // ctx
for (var i = 0; i < shared; i += 1) {
let index = lowered.length;
mapParamTypeToWasmParams(this.wasm, src.parameters[i], lowered);
// An argument arrives as the target's type and leaves as the source's.
let pack = this.#adaptationPack(index, tgt.parameters[i], src.parameters[i]);
if (pack != null) {
packs.push(pack);
}
}
let result = this.#adaptationPack(-1, src.returnType, tgt.returnType);
if (result != null) {
packs.push(result);
}
return packs;
}
/**
* The pack that turns a value held as `from` into one held as `to`, or
* null when it passes as it is. The same choice the checker makes for
* an assignment (checkAndRegisterInterfaceAdaptation): null comes off
* the source and passes through, and a union target takes the first
* member the source converts to. Any other change of representation
* gets no pack, and lowering refuses it.
*/
#adaptationPack(index: i32, from: Type, to: Type): AdaptationPack | null {
if (this.#sameLoweredType(from, to)) {
return null;
}
let fromType = unwrapPlainAlias(from);
let nonNull = getNonNullableType(fromType);
let nullable = nonNull !== fromType;
let source = unwrapPlainAlias(nonNull);
let target = unwrapPlainAlias(to);
let members = new Array<Type>();
if (let UnionType {types} = target) {
for (let t in types) {
members.push(t);
}
} else {
members.push(target);
}
for (let m in members) {
let member = unwrapPlainAlias(m);
if (source is ClassType) {
if (member is ClassType && this.cha.isSubclassOf(source, member)) {
return null;
}
if (member is InterfaceType && this.#classImplementsKey(source, getInterfaceKey(member))) {
this.demandPackPair(source, member);
return new AdaptationPack(index,
getClassInterfaceKey(getClassKey(source), getInterfaceKey(member)),
null, getInterfaceKey(member), nullable);
}
} else if (source is InterfaceType && member is InterfaceType) {
let sourceKey = getInterfaceKey(source);
let memberKey = getInterfaceKey(member);
if (sourceKey == memberKey) {
return null;
}
if (this.#interfaceExtendsKey(source, memberKey)) {
return new AdaptationPack(index, null, sourceKey, memberKey, nullable);
}
}
}
return null;
}
#interfaceExtendsKey(it: InterfaceType, key: InterfaceKey): boolean {
let supers = new Array<InterfaceType>();
this.cha.addInterfaceToTransitiveList(it, supers, new Map<InterfaceKey, boolean>());
for (let s in supers) {
if (getInterfaceKey(s) == key) {
return true;
}
}
return false;
}
/**
* Computes the adaptations a generic-slot trampoline needs between
* the interface-view slot signature and the class's monomorphized
* copy: a class-typed covariant result packs into the interface fat
* pointer, and a callback parameter the class's declaration narrows
* (the interface wrote `this`) is rebuilt through a forwarder that
* packs the narrowed arguments. Any other mismatch throws — a shape
* this dispatch cannot adapt must fail the compile loudly rather
* than emit an invalid call.
*/
#computeGenericTrampolineAdaptations(trampFunc: WasmFunction, cType: ClassType, iface: InterfaceType, d: GenericInterfaceMethodDemand): void {
let ifaceFt = getGenericInterfaceMethodType(this.wasm, iface, d.methName, d.typeArgs);
let implFtOpt = this.#implGenericMethodType(cType, d.methName, d.typeArgs);
if (implFtOpt == null) {
throw new Error(`Internal error: no declared type for generic interface method ${cType.name}.${d.methName}`);
}
let implFt = implFtOpt;
if (ifaceFt.parameters.length != implFt.parameters.length) {
throw new Error(`Internal error: generic interface method arity mismatch for ${cType.name}.${d.methName}`);
}
for (var j = 0; j < ifaceFt.parameters.length; j += 1) {
let ip = ifaceFt.parameters[j];
let cp = implFt.parameters[j];
if (this.#sameLoweredType(ip, cp)) {
continue;
}
if (ip is FunctionType && cp is FunctionType) {
let ipf = ip as FunctionType;
let cpf = cp as FunctionType;
let sIface = getClosureStruct(this.wasm, ipf);
let sImpl = getClosureStruct(this.wasm, cpf);
if (sIface == sImpl) {
continue;
}
if (ipf.parameters.length != cpf.parameters.length) {
throw new Error(`generic interface dispatch: callback arity differs for ${cType.name}.${d.methName}`);
}
if (!this.#sameLoweredType(ipf.returnType, cpf.returnType)) {
throw new Error(`generic interface dispatch: callback result adaptation is not supported (${cType.name}.${d.methName})`);
}
let packs = new Array<ForwarderParamPack>();
for (var k = 0; k < ipf.parameters.length; k += 1) {
let ipk = ipf.parameters[k];
let cpk = cpf.parameters[k];
if (this.#sameLoweredType(ipk, cpk)) {
continue;
}
if (ipk is InterfaceType && cpk is ClassType) {
let packIface = ipk as InterfaceType;
let packClass = cpk as ClassType;
this.demandPackPair(packClass, packIface);
// +1: the closure impl signature's param 0 is the ctx.
packs.push(new ForwarderParamPack(k + 1,
getClassInterfaceKey(getClassKey(packClass), getInterfaceKey(packIface)),
getInterfaceKey(packIface)));
continue;
}
throw new Error(`generic interface dispatch: callback parameter adaptation is not supported (${cType.name}.${d.methName})`);
}
let fwdSigOpt = asWasmSignature(sImpl.fields[0].type);
if (fwdSigOpt == null) {
throw new Error("Internal error: closure struct without impl signature");
}
let fwd = new WasmFunction(fwdSigOpt, null, this.program.units[0].model);
fwd.name = `${trampFunc.name ?? "tramp"}$arg${i32ToString(j)}`;
fwd.closureForwarder = new ClosureForwarderSpec(sIface, packs);
// The trampoline takes this function's ref.func, which needs a
// declared function reference.
fwd.isReferenceTaken = true;
this.wasm.addFunction(fwd);
this.markFunctionReached(fwd);
this.markTypeReached(sIface);
this.markTypeReached(sImpl);
this.noteClosureStruct(sIface);
this.noteClosureStruct(sImpl);
var wraps = trampFunc.trampolineParamWraps;
if (wraps == null) {
let fresh = new Array<TrampolineParamWrap>();
trampFunc.trampolineParamWraps = fresh;
wraps = fresh;
}
// +1: the trampoline signature's param 0 is the receiver.
wraps.push(new TrampolineParamWrap(j + 1, sImpl, fwd));
continue;
}
throw new Error(`generic interface dispatch: parameter adaptation is not supported (${cType.name}.${d.methName})`);
}
if (!this.#sameLoweredType(ifaceFt.returnType, implFt.returnType)) {
let ir = ifaceFt.returnType;
let cr = implFt.returnType;
if (ir is InterfaceType && cr is ClassType) {
let retIface = ir as InterfaceType;
let retClass = cr as ClassType;
this.demandPackPair(retClass, retIface);
trampFunc.trampolineResultPackPair = getClassInterfaceKey(getClassKey(retClass), getInterfaceKey(retIface));
trampFunc.trampolineResultPackIface = getInterfaceKey(retIface);
} else {
throw new Error(`generic interface dispatch: result adaptation is not supported (${cType.name}.${d.methName})`);
}
}
}
/**
* A class may implement an interface method with a narrower result:
* `scaled(): Square` for `scaled(): Shape`. When the interface's result
* is an interface type and the class method returns a class value, the
* trampoline packs that value into the interface (the same adaptation
* #computeGenericTrampolineAdaptations makes for generic methods).
*/
#adaptCovariantResult(trampoline: WasmFunction, target: WasmFunction,
iface: InterfaceType, slotName: String,
slotOverload: InterfaceSlotOverload | null): void {
let slotResults = trampoline.signature.returns;
let targetResults = target.signature.returns;
if (slotResults.length != 1 || targetResults.length != 1 ||
isValSubtype(targetResults[0], slotResults[0])) {
return;
}
let interfaceResult = this.#interfaceSlotResult(iface, slotName, slotOverload);
// The class is read off the method's declared result rather than its
// wasm result: a value of an extension class is its underlying array,
// which names no class.
let classResult = this.#declaredResultType(target);
if (interfaceResult is InterfaceType && classResult is ClassType) {
this.demandPackPair(classResult, interfaceResult);
trampoline.trampolineResultPackPair = getClassInterfaceKey(
getClassKey(classResult), getInterfaceKey(interfaceResult));
trampoline.trampolineResultPackIface = getInterfaceKey(interfaceResult);
}
}
/**
* The result type an interface vtable slot declares, with the
* interface's type arguments substituted.
*/
#interfaceSlotResult(iface: InterfaceType, slotName: String,
slotOverload: InterfaceSlotOverload | null): Type | null {
if (slotOverload != null) {
return slotOverload.overload.returnType;
}
if (let (true, member) = iface.members.get(slotName)) {
let resolved = substituteTypeParamsInCodegen(this.wasm,
getInterfaceTypeParameters(iface), iface.typeArguments, member.type);
if (member is MethodInfo && resolved is FunctionType) {
return resolved.returnType;
}
}
return null;
}
/**
* A class method's declared result type, in its class's context. The
* method is registered under its member name, plus the overload's
* signature key when the member is overloaded.
*/
#declaredResultType(method: WasmFunction): Type | null {
let {classType, methodName} = method;
if (classType == null || methodName == null) {
return null;
}
for (let memberName in classType.members.keys()) {
if (!methodName.startsWith(memberName)) {
continue;
}
let member = classType.members[memberName];
let memberType = member.type;
if (!(member is MethodInfo) || !(memberType is FunctionType)) {
continue;
}
if (memberName == methodName) {
return substituteTypeParamsInClassContext(this.wasm, classType, memberType.returnType);
}
let {overloads} = memberType;
if (overloads != null) {
if (let (true, overload) = overloads.find(
(overload) => memberName + getSignatureKey(overload) == methodName)) {
return substituteTypeParamsInClassContext(this.wasm, classType, overload.returnType);
}
}
}
return null;
}
/**
* Builds the trampoline for one interface vtable slot of one class.
* A generic slot (a recorded demand names it) first instantiates the
* class's monomorphized copy — a class can join a demand's interface
* in any round, so resolution has to happen here, not at demand
* time — and computes the trampoline's adaptations.
*/
#buildTrampolineForSlot(cType: ClassType, cName: ClassKey, iface: InterfaceType, iName: InterfaceKey, vst: WasmStruct, fieldIdx: i32): WasmFunction {
let fldName = vst.fields[fieldIdx].name;
if (fldName == null) {
throw new Error("Internal error: unnamed interface vtable slot");
}
let fName = fldName;
let demand = this.findGenericInterfaceDemand(iName as String, fName);
if (demand != null) {
let d = demand;
let unspecCdId = (cType.genericSource ?? cType).symbolId;
let cd = if (let (true, decl) = this.classDecls.get(unspecCdId)) decl else null;
let targetModel = this.getClassModel(cType);
for (let md in this.cha.findImplementingMethods(cType, d.methName)) {
if (md.isStatic) { continue; }
let fn = this.specializer.instantiateGenericMethod(cType, cd, d.methName, md as Node, d.typeArgs, this.getNodeModel(md as Node, targetModel));
this.markFunctionReached(fn);
}
}
var foundFunc: WasmFunction | null = null;
// The name the class registers it under, which names its class
// vtable slot.
var foundName = fName;
var currClass: ClassType | null = cType;
// A slot for one overload of an overloaded interface method: the class
// registers each of its overloads under the name plus its signature
// key, and a class with a single method of that name under the name.
let slotOverload = interfaceSlotOverload(this.wasm, iface, fName);
if (slotOverload != null) {
let overloadName = slotOverload.methodName + getSignatureKey(slotOverload.overload);
while (currClass != null && foundFunc == null) {
let classKey = getClassKey(currClass);
if (let (true, method) = this.wasm.classMethodMap.get(
getClassMethodKey(classKey, overloadName))) {
foundFunc = method;
foundName = overloadName;
} else if (let (true, method) = this.wasm.classMethodMap.get(
getClassMethodKey(classKey, slotOverload.methodName))) {
foundFunc = method;
foundName = slotOverload.methodName;
}
currClass = currClass.superType;
}
}
while (currClass != null && foundFunc == null) {
let mKey = getClassMethodKey(getClassKey(currClass), fName);
if (this.wasm.classMethodMap.has(mKey)) {
foundFunc = this.wasm.classMethodMap[mKey];
break;
}
if (iface.members.has(fName)) {
let mi = iface.members[fName];
if (mi is MethodInfo && mi.type is FunctionType) {
let ft = mi.type as FunctionType;
let itParams = getInterfaceTypeParameters(iface);
let subFt = substituteTypeParamsInCodegen(this.wasm, itParams, iface.typeArguments, ft);
if (subFt is FunctionType) {
let resolvedFt = subFt as FunctionType;
let sigKey = getSignatureKey(resolvedFt);
let mKeyWithSig = getClassMethodKey(getClassKey(currClass), fName + sigKey);
if (this.wasm.classMethodMap.has(mKeyWithSig)) {
foundFunc = this.wasm.classMethodMap[mKeyWithSig];
foundName = fName + sigKey;
break;
}
}
}
}
currClass = currClass.superType;
}
if (foundFunc == null) {
var chain = "";
var cw: ClassType | null = cType;
while (cw != null) {
let ccw = cw;
let targsLen = if (ccw.typeArguments != null) i32ToString((ccw.typeArguments as Array<Type>).length) else "null";
let tparamsLen = if (ccw.typeParameters != null) i32ToString((ccw.typeParameters as Array<TypeParameterType>).length) else "null";
let conc = if (isConcrete(ccw)) "true" else "false";
chain = `${chain}${ccw.name}[args:${targsLen},params:${tparamsLen},conc:${conc},key:${getClassKey(ccw) as String}] -> `;
cw = ccw.superType;
}
throw new Error(`Internal error: class ${cName as String} does not implement interface method: ${fName}; chain: ${chain}`);
}
let trampSig = if (demand != null) {
getGenericInterfaceMemberSignature(this.wasm, iface, demand.methName, demand.typeArgs)
} else if (slotOverload != null) {
interfaceOverloadSignature(this.wasm, slotOverload.overload)
} else {
getInterfaceMemberSignature(this.wasm, iface, fName)
};
let trampFunc = new WasmFunction(trampSig, null, this.program.units[0].model);
trampFunc.name = getInterfaceTrampolineName(cName, iName, fName);
trampFunc.interfaceTrampolineTarget = foundFunc;
trampFunc.interfaceTrampolineClass = cType;
trampFunc.interfaceTrampolineSlot = foundName;
if (demand != null) {
this.#computeGenericTrampolineAdaptations(trampFunc, cType, iface, demand);
} else {
this.#adaptCovariantResult(trampFunc, foundFunc, iface, fName, slotOverload);
}
this.wasm.addFunction(trampFunc);
this.markFunctionReached(trampFunc);
this.markFunctionReached(foundFunc);
return trampFunc;
}
/**
* Builds the class-interface trampoline vtable globals, returning
* whether it created any. Reaching an interface method's body can
* instantiate further classes (`FixedArray<T>.:iterator` returns an
* `ArrayIterator<T>` packed as `Iterator<T>`), and those need
* class-interface vtables of their own — so `run` alternates this
* with `processQueues` until neither adds anything, rather than
* building once and leaving the last round's classes without one.
* The pair set is finite and only ever grows, so this terminates.
*/
#buildClassInterfaceVTables(): boolean {
var created = this.#syncInterfaceSlots();
if (this.#syncGenericInterfaceSlots()) {
created = true;
}
// Pass 2: Generate class-interface trampoline vtables
let classes = new Array<ClassType>();
let seenClassKeys = new Map<ClassKey, boolean>();
for (let cPair in this.wasm.classInfos) {
let cStruct = cPair.value.structType;
let {classType} = cStruct;
if (classType != null) {
let cType = classType;
let cKey = getClassKey(cType);
if (!seenClassKeys.has(cKey)) {
seenClassKeys[cKey] = true;
classes.push(cType);
}
}
}
// Only classes codegen has state for (the classInfos walk above).
// This used to ALSO walk every declared class — and since a
// class's interfaces are collected transitively, that instantiated
// `FixedArray` at four element types for a program that mentions
// none of them. The classInfos set already contains every class a
// vtable could matter for: `usedInterfaceAdaptations`, checked
// per-pair below, is only ever recorded against discovered classes.
for (let cType in classes) {
let {typeParameters} = cType;
let isGenericTemplate = typeParameters != null &&
typeParameters.length > 0 &&
(cType.typeArguments == null || !isConcrete(cType));
// An ERASURE passes `isConcrete` (an erased slot IS a type) but is
// no more dispatchable than a template: it has a struct and no
// methods, so there is nothing to put in a trampoline slot.
if (isGenericTemplate || containsErasedType(cType as Type)) {
continue;
}
let cName = getClassKey(cType);
// An extension class has no `struct.new` — a value of it IS a
// value of its `on` type — so "instantiated" never becomes true
// for one now that mentioning the type no longer instantiates
// it, and gating here would deny `FixedArray<T>` the
// class-interface vtable its values genuinely dispatch through.
// `isPackPairUsed` just below is the honest signal: it is
// recorded from real pack sites, and gates each class-interface
// pair on its own.
if (!this.instantiatedSpecializedClasses.has(cName as String) &&
!cType.isExtension) {
continue;
}
let allIfaces = this.cha.collectAllImplementedInterfaces(cType);
for (let iface in allIfaces) {
let iName = getInterfaceKey(iface);
let key = getClassInterfaceKey(cName, iName);
if (this.isPackPairUsed(cType, iface)) {
if (this.wasm.classInterfaceVTables.has(key)) {
// Slots appended after this pair's vtable was built (a
// demand discovered in a later round) leave the stored
// funcs list short — extend it with trampolines for the
// tail slots. Fields are append-only, so the existing
// entries still align.
let existing = this.wasm.classInterfaceVTables[key];
let init = existing.initVTable;
if (init != null) {
let vstNow = init.structType;
let funcs = init.funcs;
if (funcs.length < vstNow.fields.length) {
if (!(funcs is GrowableArray<WasmFunction>)) {
throw new Error("Internal error: class-interface vtable funcs list is not growable");
}
let growable = funcs as GrowableArray<WasmFunction>;
for (var i = growable.length; i < vstNow.fields.length; i += 1) {
let tramp = this.#buildTrampolineForSlot(cType, cName, iface, iName, vstNow, i);
tramp.isReferenceTaken = true;
growable.push(tramp);
created = true;
}
}
}
continue;
}
if (!this.wasm.interfaceVTableStructs.has(iName)) {
this.typeLowerer.discoverType(iface, this.getClassModel(cType));
}
let vst = this.wasm.interfaceVTableStructs[iName];
let methods = new Array<WasmFunction>();
for (var i = 0; i < vst.fields.length; i += 1) {
let tramp = this.#buildTrampolineForSlot(cType, cName, iface, iName, vst, i);
methods.push(tramp);
}
let vtableInit = new VTableInit(vst, methods);
let viName = getClassInterfaceVTableName(cName, iName);
let vtableGlobal = new WasmGlobal(
viName,
viName,
new ValTypeRef(vst),
false,
null,
vtableInit,
this.program.units[0].model
);
this.wasm.globals.push(vtableGlobal);
this.wasm.classInterfaceVTables[key] = vtableGlobal;
this.usedInterfaceTypes.push(iface);
created = true;
}
}
}
return created;
}
/**
* Populates every known class's struct and vtable slots, to a
* fixpoint: populating a class registers its methods, and that can
* instantiate further classes which then need laying out too.
*
* Called again once discovery has fully settled, immediately before
* instantiation is closed — a class first instantiated by the
* class-interface vtable pass or the final queue drain still has to
* get a layout, and before this ran twice it silently did not.
*/
#layoutClassStructs(populated: HashMap<ClassKey, boolean>): void {
var round = true;
while (round) {
round = false;
let pending = new Array<ClassType>();
for (let cPair in this.wasm.classInfos) {
let ct = cPair.value.structType.classType;
if (ct != null && !populated.has(getClassKey(ct))) {
pending.push(ct);
}
}
for (let ct in pending) {
this.#populateClassStruct(ct, populated);
round = true;
}
if (this.#syncGenericClassSlots()) {
round = true;
}
}
}
/** Host-import boundary directions; see wasm.hostReadsStrings/hostWritesStrings. */
noteHostImportSignature(ft: FunctionType): void {
for (let p in ft.parameters) {
if (this.#typeMentionsString(p, 0)) {
this.wasm.hostReadsStrings = true;
}
}
if (this.#typeMentionsString(ft.returnType, 0)) {
this.wasm.hostWritesStrings = true;
}
}
/**
* Whether `t` mentions the stdlib String class anywhere a value
* could cross a boundary typed by `t`: directly, in a function
* type's parameters or return, through unions, tuples, records,
* arrays and alias targets, or in a class/interface's type ARGUMENTS
* (`Array<String>`). Class MEMBERS are not walked — a member's
* String is produced by code, which instantiates through its own
* body. Depth-bounded rather than seen-set-deduplicated: a set keyed
* by symbol would conflate specializations of one generic, and the
* types that reach an export boundary are shallow.
*/
#typeMentionsString(t: Type, depth: i32): boolean {
if (depth > 12) {
return false;
}
return match (t) {
case ClassType as ct: {
if (isWellKnown(WellKnown.StringClass, ct.name, ct.sourcePath)) {
true
} else {
var found = false;
let {typeArguments} = ct;
if (typeArguments != null) {
for (let ta in typeArguments) {
if (this.#typeMentionsString(ta, depth + 1)) { found = true; break; }
}
}
found
}
}
case InterfaceType as it: {
var found = false;
let {typeArguments} = it;
if (typeArguments != null) {
for (let ta in typeArguments) {
if (this.#typeMentionsString(ta, depth + 1)) { found = true; break; }
}
}
found
}
case FunctionType as ft: {
var found = this.#typeMentionsString(ft.returnType, depth + 1);
if (!found) {
for (let p in ft.parameters) {
if (this.#typeMentionsString(p, depth + 1)) { found = true; break; }
}
}
found
}
case UnionType {types}: {
var found = false;
for (let m in types) {
if (this.#typeMentionsString(m, depth + 1)) { found = true; break; }
}
found
}
case TupleType {elementTypes}: {
var found = false;
for (let e in elementTypes) {
if (this.#typeMentionsString(e, depth + 1)) { found = true; break; }
}
found
}
case InlineParamType {param}: this.#typeMentionsString(param, depth + 1)
case InlineRecordType {record}: this.#typeMentionsString(record, depth + 1)
case InlineTupleType {elementTypes}: {
var found = false;
for (let e in elementTypes) {
if (this.#typeMentionsString(e, depth + 1)) { found = true; break; }
}
found
}
case ArrayType {elementType}: this.#typeMentionsString(elementType, depth + 1)
case RecordType as rec: {
var found = false;
for (let pair in rec.properties) {
if (this.#typeMentionsString(pair.value, depth + 1)) { found = true; break; }
}
found
}
case TypeAliasType as alias: this.#typeMentionsString(alias.target, depth + 1)
case EnumType as et: this.#typeMentionsString(et.backingType, depth + 1)
case _: false
};
}
/**
* Ensures the exception infrastructure AND accounts for what it
* implies: `ensureExceptionInfra` creates `$stringCreate` and
* `$stringSetByte` (the host builds a String through them, e.g. for
* a stack-trace message), and a created-but-unreached helper is a
* dangling export — function index -1, an invalid module. Their
* bodies are synthesized against String's layout and vtable, so
* String is instantiated as their prerequisite. Exceptions are, for
* now, String evidence.
*/
/**
* Records a closure struct that emitted code can reference, under
* the same evidence gate as reachablyNamedClasses. See the interface
* doc; `force` is for sites that create a REACHED function whose
* synthesized body references the struct regardless of what walk
* discovered it (value wrappers, adaptations).
*/
noteCompositeType(t: Type): void {
let key = getTypeUniqueKey(t);
if (!this.#namedCompositeKeys.has(key)) {
this.#namedCompositeKeys.add(key);
this.#namedCompositeTypes.push(t);
}
}
/** Deferred by-key member reach; drained with the field accessors at settle. */
notePendingMemberReach(key: ClassMethodKey): void {
this.#pendingMemberReaches.push(key);
}
/**
* Classes compared with `==` that have no `operator ==` of their own.
* Such a comparison dispatches to the classes below that introduce one
* (ir/equality.zena, lowerClassEquality), so their operators are reached
* once both the comparison and the class are. A base compared by
* reachable code is in both sets.
*/
#equalityBases = new Set<String>();
#reachableEqualityBases = new Set<String>();
noteEqualityBase(ct: ClassType): void {
let key = getClassKey(ct) as String;
// A base first compared by code that is only visited is noted again
// when reachable code compares it, so the operators below it are
// reached as reachable too.
if (this.currentReachable) {
if (!this.#reachableEqualityBases.add(key)) {
return;
}
this.#equalityBases.add(key);
} else if (!this.#equalityBases.add(key)) {
return;
}
// Only the classes below this base are new to compare; a class below
// another base was reached when that base, or the class, arrived.
// Classes instantiated later are checked as they are
// (Specializer.instantiateClassType).
let below = new Array<ClassType>();
for (let sub in this.cha.findInstantiatedSubclasses(ct)) {
below.push(sub);
}
for (let sub in below) {
this.reachEqualityBelowComparedBase(sub);
}
}
/**
* Marks equality as dispatched on values whose class is not known
* statically (an erased or interface-typed `==`, or the `eq`/`hash`
* intrinsics). The erased comparison calls the `operator ==` of whatever
* class it meets (ir/equality.zena, lowerErasedEqDispatch), so every
* instantiated class's operator is reached: those already instantiated
* now, and later ones as they are (Specializer.instantiateClassType).
*/
useEqualityDispatch(): void {
if (this.equalityDispatchUsed) {
return;
}
this.equalityDispatchUsed = true;
let instantiated = new Array<ClassType>();
for (let entry in this.wasm.classInfos) {
let ct = entry.value.structType.classType;
if (ct != null && this.instantiatedSpecializedClasses.has(entry.key as String)) {
instantiated.push(ct);
}
}
for (let ct in instantiated) {
this.reachEqualityOf(ct);
}
}
/** Reaches `ct`'s `operator ==`, declared or derived, if it has one. */
reachEqualityOf(ct: ClassType): void {
if (!ct.members.has("==")) {
return;
}
let eqMethod = this.cha.findImplementingMethod(ct, "==");
if (eqMethod != null) {
this.queueReferrer(new Referrer(false, noSymbolId, (eqMethod as Node).id as i32,
this.getNodeModel(eqMethod as Node, this.getClassModel(ct)), ct,
this.currentReachable));
}
this.notePendingMemberReach(getClassMethodKey(getClassKey(ct), "=="));
}
/** Reaches `ct`'s `operator ==` when some class above it is compared. */
reachEqualityBelowComparedBase(ct: ClassType): void {
if (!ct.members.has("==")) {
return;
}
var above = false;
var curr = ct.superType;
while (curr != null && !above) {
let anc = curr as ClassType;
above = this.#equalityBases.has(getClassKey(anc) as String);
curr = anc.superType;
}
if (!above) {
return;
}
let eqMethod = this.cha.findImplementingMethod(ct, "==");
if (eqMethod != null) {
this.queueReferrer(new Referrer(false, noSymbolId, (eqMethod as Node).id as i32,
this.getNodeModel(eqMethod as Node, this.getClassModel(ct)), ct,
this.currentReachable));
}
this.notePendingMemberReach(getClassMethodKey(getClassKey(ct), "=="));
}
noteClosureStruct(cs: WasmStruct): void {
if (this.inQueueWalk && this.currentReachable) {
this.reachablyNamedClosures.add(cs);
}
}
noteExceptionInfra(model: SemanticModel): void {
this.wasm.ensureExceptionInfra(model);
let {stringClass} = this.wasm;
if (stringClass != null) {
if (targetUsesJsStrings(this.target)) {
this.visitor.queueStdlibFunction('core', '$stringCreate');
this.visitor.queueStdlibFunction('core', '$stringGetHandle');
this.visitor.queueStdlibFunction('core', '$stringGetLength');
} else {
let sClass = stringClass;
this.specializer.instantiateClassType(sClass, this.getClassModel(sClass));
let {stringCreateFunc} = this.wasm;
if (stringCreateFunc != null) {
this.markFunctionReached(stringCreateFunc);
}
let {stringSetByteFunc} = this.wasm;
if (stringSetByteFunc != null) {
this.markFunctionReached(stringSetByteFunc);
}
}
}
}
ensureAllHelperFunctionsReached(): void {
for (let unit in this.program.units) {
let mod = unit.ast;
let {model} = unit;
for (let stmt in mod.body) {
if (stmt is ImportDeclaration) {
this.visitor.discoverImportDeclaration(stmt, model);
}
}
}
// Gated on String being INSTANTIATED, not declared: the $string*
// helpers' bodies are synthesized against String's struct, and
// they exist to hand String values across the host boundary — a
// module with no String value has nothing to hand across.
if (this.wasm.stringClass != null &&
this.instantiatedSpecializedClasses.has(
getClassKey(this.wasm.stringClass as ClassType) as String)) {
if (targetUsesJsStrings(this.target)) {
this.visitor.queueStdlibFunction('core', '$stringCreate');
this.visitor.queueStdlibFunction('core', '$stringGetHandle');
this.visitor.queueStdlibFunction('core', '$stringGetLength');
} else {
this.wasm.stringClassIsInstantiated = true;
this.wasm.ensureStringHelpers(this.program.units[0].model);
if (this.wasm.stringCreateFunc != null) { this.markFunctionReached(this.wasm.stringCreateFunc as WasmFunction); }
if (this.wasm.stringSetByteFunc != null) { this.markFunctionReached(this.wasm.stringSetByteFunc as WasmFunction); }
if (this.wasm.stringGetByteFunc != null) { this.markFunctionReached(this.wasm.stringGetByteFunc as WasmFunction); }
if (this.wasm.stringGetLengthFunc != null) { this.markFunctionReached(this.wasm.stringGetLengthFunc as WasmFunction); }
}
}
// The string hash helper follows the equality evidence, like the
// ==/hashCode slots it serves. If literal interning ever calls it
// directly, the miss is a loud 'function index < 0', not a wrong
// answer.
let {stringHashFunc} = this.wasm;
if (stringHashFunc != null && this.equalityDispatchUsed) {
this.markFunctionReached(stringHashFunc);
}
// The erased comparison's shared dispatch (ir/equality.zena).
if (this.equalityDispatchUsed) {
this.wasm.ensureErasedEqInfra(this.program.units[0].model);
this.markFunctionReached(this.wasm.erasedEqFunc as WasmFunction);
}
}
traverseDependencies(deps: SymbolDependencies, model: SemanticModel, classType: ClassType | null, typeArguments: Array<Type> | null = null, node: Node | null = null): void {
let ctParams: Array<TypeParameterType> | null = if (classType != null) getClassTypeParameters(classType) else null;
let ctArgs: Array<Type> | null = if (classType != null) classType.typeArguments else null;
// A function's OWN type parameters, when this walk is of one
// monomorphization of it. Both node shapes that carry them count: a
// generic arrow (`FunctionExpression`) and a generic METHOD, which
// is a `MethodDefinition`. Only the arrow was recognized, so a
// generic method's body was walked with its parameters still open —
// `new State<B>` inside `Box.make<B>` stayed `State<B>`, was erased
// to `State<anyref>`, and the `State<i32>` the call really needs was
// never discovered. Lowering then bailed "class not discovered" on
// the specialization it had just been handed.
// A CLOSURE's walk carries the ENCLOSING generic function's
// arguments and has no parameters of its own, so the lookup walks
// up to the nearest node that declares some.
let ownTypeParams = if (node == null || typeArguments == null) {
null
} else {
enclosingOwnTypeParameters(model, node as Node)
};
let resolveType = (t: Type) => {
var res = substituteTypeParamsInClassContext(this.wasm, classType, t);
if (ownTypeParams != null) {
res = substituteTypeParamsInCodegen(
this.wasm, ownTypeParams,
typeArguments as Array<Type>, res);
}
return res;
};
// 0. Register used interface adaptations first
for (let adaptKey in deps.usedInterfaceAdaptations) {
var parsed: ParsedAdaptationRef | null = null;
if (let (true, cached) = this.parsedAdaptationRefs.get(adaptKey)) {
parsed = cached;
} else {
let keyStr = adaptKey;
var colonIdx = -1;
for (var i = 0; i < keyStr.length - 1; i += 1) {
if (keyStr.getByteAt(i) == 58 && keyStr.getByteAt(i + 1) == 58) {
colonIdx = i;
break;
}
}
if (colonIdx != -1) {
let classIdStr = keyStr.sliceBytes(0, colonIdx);
let ifaceIdStr = keyStr.sliceBytes(colonIdx + 2, keyStr.length);
let classId = if (let (true, cid) = parseI32(classIdStr)) cid else -1;
let ifaceId = if (let (true, iid) = parseI32(ifaceIdStr)) iid else -1;
let newRef = new ParsedAdaptationRef(classId as SymbolId, ifaceId as SymbolId);
this.parsedAdaptationRefs[adaptKey] = newRef;
parsed = newRef;
}
}
if (parsed != null) {
let classId = parsed.classSymId;
let ifaceId = parsed.ifaceSymId;
if (this.interfaceDecls.has(ifaceId)) {
let ifaceDecl = this.interfaceDecls[ifaceId];
let ifaceModel = this.interfaceModels[ifaceId];
let it = ifaceModel.getBindingType(ifaceModel.resolve(ifaceDecl) as Symbol) as InterfaceType;
if (this.symbolIdToDecl.has(classId)) {
let classDecl = this.symbolIdToDecl[classId];
let classModel = this.symbolIdToModel[classId];
let ct = this.getClassDeclType(classDecl, classModel);
if (ct != null && it != null) {
this.demandPackPair(ct, it);
}
} else if (classType != null) {
if (classType != null && it != null) {
this.demandPackPair(classType, it);
}
}
}
}
}
if (deps.needsExceptionInfra) {
this.noteExceptionInfra(model);
}
if (deps.causesCancellation) {
this.cancellationPossible = true;
}
if (deps.hasIteratorForIn) {
this.iteratorForInReached = true;
}
if (deps.createsGenerator) {
this.generatorReached = true;
}
if (deps.createsAsyncGenerator) {
this.asyncGeneratorReached = true;
}
// Enclosing locals assigned inside a `try` body live in heap cells,
// exactly like closure-mutated captures: the handler is entered
// from anywhere in the protected extent, so only a cell can show it
// the assignments the body completed before it threw. Registering
// the symbol here is all lowering needs — `isCelled` already routes
// the declaration, reads, and writes through the cell. The struct
// must be interned NOW: lowering runs after layout, where a miss is
// a hard error.
for (let symId in deps.tryMutatedSymbols) {
let bindingType = model.getBindingTypeById(symId);
if (bindingType == null) { continue; }
let valType = typeToValType(this.wasm, resolveType(bindingType));
this.tryCellStructs.push(getCellStruct(this.wasm, valType));
this.wasm.mutableCapturedSymbols.add(symId);
}
// 1. Discover referenced types
for (let t in deps.referencedTypes) {
let resolved = resolveType(t);
// A function-typed record is a SIGNATURE reference — the checker
// records a callee's type for a plain call too, and a call needs
// no closure struct. Genuine value uses of a named function are
// handled by the wrapper registration just below (and arrows in
// value position by the node walks), which mint the closure
// struct themselves.
if (resolved is FunctionType) {
this.typeLowerer.discoverSignatureType(resolved, model);
} else {
this.typeLowerer.discoverType(resolved, model);
}
if (resolved is ClassType) {
this.specializer.instantiateClassType(resolved, model);
} else if (resolved is FunctionType) {
// Generic instantiations only. The identifier-reference path
// below cannot see these: at the reference site the specialized
// function may not exist yet, so the wrapper has to be
// registered from the type. Dropping this breaks
// execution/functions/generic_closure_substitution.zena with
// "non-local identifier @Holder_s788_i32.getVal".
let resTargs = resolved.typeArguments;
if (resTargs != null && resTargs.length > 0) {
this.visitor.discoverFunctionValueWrapper(resolved, model);
}
}
// A non-generic FunctionType here does NOT imply a value is needed.
// `referencedTypes` collects every type the checker assigns to a
// node (checker.zena setNodeType/resolveIdentifier), so a plain
// call contributes its callee's FunctionType, and in Zena every
// function is an arrow bound to a `let`. Registering a wrapper
// from this set emitted one for every function in the program —
// 51 dead wrappers in basic_bench, each with its own signature
// and an entry in the declared-func elem table.
//
// Wrappers come from visitor.discoverIdentifierReferenceAsValue(),
// which fires on identifier references outside callee position and
// so covers arguments, field stores, returns and local bindings.
}
// 2. Queue referenced symbols
for (let symId in deps.referencedSymbols) {
let targetSymId = if (this.symbolIdToTargetId.has(symId)) {
this.symbolIdToTargetId[symId]
} else {
symId
};
if (let (true, targetModel) = this.symbolIdToModel.get(targetSymId)) {
this.queueReferrer(new Referrer(true, targetSymId, -1, targetModel, null, this.currentReachable));
}
}
for (let methStr in deps.referencedClassMethods) {
var parsed: ParsedMethodRef | null = null;
if (let (true, cached) = this.parsedClassMethodRefs.get(methStr)) {
parsed = cached;
} else {
var dotIdx = -1;
for (var i = 0; i < methStr.length; i += 1) {
if (methStr.getByteAt(i) == 46) {
dotIdx = i;
break;
}
}
if (dotIdx != -1) {
let classIdStr = methStr.sliceBytes(0, dotIdx);
let mName = methStr.sliceBytes(dotIdx + 1, methStr.length);
let classId = if (let (true, cid) = parseI32(classIdStr)) cid else -1;
parsed = new ParsedMethodRef(classId as SymbolId, mName);
} else {
parsed = new ParsedMethodRef(noSymbolId, "");
}
this.parsedClassMethodRefs[methStr] = parsed;
}
if (parsed != null && parsed.classSymId as i32 != -1) {
let {classSymId} = parsed;
let {mName} = parsed;
if (let (true, targetModel) = this.symbolIdToModel.get(classSymId)) {
var targetClassType: ClassType | null = null;
let t = targetModel.getBindingTypeById(classSymId);
if (t is ClassType) {
targetClassType = t;
if (classType != null && classType.genericSource != null) {
let genSrc = classType.genericSource as ClassType;
if (genSrc.symbolId == classSymId) {
targetClassType = classType;
}
}
this.specializer.instantiateClassType(targetClassType, targetModel);
} else if (targetModel.mixinDeclarations.has(classSymId)) {
let mixinDecl = targetModel.mixinDeclarations[classSymId];
targetClassType = new ClassType(this.typeIdGenerator.next(), classSymId, mixinDecl.name.name);
}
if (targetClassType != null) {
// The function lowering will resolve for this access, found
// by walking up from the receiver's class: a direct call's
// callee, or the slot signature a dispatch uses. It may not
// be registered yet (an abstract field's stub is added in
// Pass 1.15), so it is resolved later, by #fillReachedSlots.
if (this.currentReachable && mName != "" &&
!targetClassType.isMixinIntermediate &&
isConcrete(targetClassType)) {
this.#pendingStaticTargets.push(
new PendingStaticTarget(targetClassType, mName));
}
let {cha} = this;
let list = new Array<ClassType>();
if (targetClassType.isExtension) {
list.push(targetClassType);
} else {
let subclasses = cha.findInstantiatedSubclasses(targetClassType);
for (let subCt in subclasses) {
list.push(subCt);
}
}
// The records are symbol-level, and findInstantiatedSubclasses
// sees only specializations that exist NOW — a member dep
// traversed before the receiver's specialization is
// instantiated queues nothing, and the edge is lost. While
// every method of an instantiated class was force-reached
// that never showed (JsonObject.size reads its
// OrderedHashMap's size before any OrderedHashMap is
// instantiated). Record the member against the generic;
// discovery and instantiation replay it per specialization.
let recMds = cha.findImplementingMethods(targetClassType, mName);
for (let md in recMds) {
let mdNode = md as Node;
this.nodeIdToNode[mdNode.id as i32] = mdNode;
this.nodeIdToModel[mdNode.id as i32] = this.getNodeModel(mdNode, targetModel);
this.recordReachedClassMember(classSymId, mdNode.id as i32,
this.getNodeModel(mdNode, targetModel), this.currentReachable);
}
for (let recAcc in cha.findImplementingAccessors(targetClassType, mName)) {
let accNode = recAcc as Node;
this.nodeIdToNode[accNode.id as i32] = accNode;
this.nodeIdToModel[accNode.id as i32] = this.getNodeModel(accNode, targetModel);
this.recordReachedClassMember(classSymId, accNode.id as i32,
this.getNodeModel(accNode, targetModel), this.currentReachable);
}
// A synthesized release has no node to record, so the
// generic records that it was reached, and noteSpecialization
// replays it for a specialization that arrives later.
let generic = targetClassType.genericSource ?? targetClassType;
if (this.currentReachable && synthesizedRelease(generic) &&
mName == releaseMemberOf(generic)) {
this.#reachedSyntheticReleases.add(classSymId);
}
for (let subCt in list) {
let subModel = this.getClassModel(subCt);
let mds = cha.findImplementingMethods(subCt, mName);
for (let md in mds) {
this.queueMember((md as Node).id as i32, this.getNodeModel(md as Node, subModel), subCt, this.currentReachable);
}
let accs = cha.findImplementingAccessors(subCt, mName);
for (let acc in accs) {
this.queueMember((acc as Node).id as i32, this.getNodeModel(acc as Node, subModel), subCt, this.currentReachable);
}
if (mName == "==" || mName == "hashCode" ||
(synthesizedRelease(subCt) && mName == releaseMemberOf(subCt))) {
// A case class's synthesized ==/hashCode — and a
// synthesized release member — have no AST node to
// find; reach the registered function by key, deferred
// past its registration.
if (this.currentReachable && mds.length == 0 && accs.length == 0) {
this.notePendingMemberReach(getClassMethodKey(getClassKey(subCt), mName));
}
} else if (mName.startsWith("get#") || mName.startsWith("set#")) {
let fieldName = mName.sliceBytes(4, mName.length);
for (let fd in cha.findImplementingFields(subCt, fieldName)) {
this.queueMember((fd as Node).id as i32, this.getNodeModel(fd as Node, subModel), subCt, this.currentReachable);
}
}
}
}
}
}
}
// 3. Record reached closures
for (let closureDep in deps.closures) {
let funcExpr = closureDep.node as FunctionExpression;
this.nodeIdToNode[funcExpr.id as i32] = funcExpr;
this.nodeIdToModel[funcExpr.id as i32] = model;
let classKey = if (classType != null) getClassKey(classType) else "" as ClassKey;
// A closure inside a generic FUNCTION (or generic method, or
// generic static) exists once per instantiation of it: the
// captures' and signature's types mention the function's type
// parameters, and at a primitive argument nothing can share the
// erased impl (i32 is not a subtype of anyref). The enclosing
// function's argument vector is the key's second axis, next to
// the class specialization.
let enclosingFnParams = enclosingOwnTypeParameters(model, funcExpr as Node);
let closureKey = getClosureSpecializationKey(funcExpr.id, classKey,
enclosingFnParams, typeArguments);
if (this.wasm.specializedClosures.has(closureKey)) {
let existingFunc = this.wasm.specializedClosures[closureKey];
// The function-axis template (registered by a walk of the
// generic function's own body) is never a function to reach —
// marking it here would emit the erased impl after all.
let existingIsFuncTemplate = enclosingFnParams != null &&
typeArguments == null;
if (this.currentReachable && !existingIsFuncTemplate) {
this.markFunctionReached(existingFunc);
}
this.queueReferrer(new Referrer(false, noSymbolId, funcExpr.id as i32, model, classType, this.currentReachable, typeArguments));
continue;
}
let rawFuncTypeNode = model.getNodeType(funcExpr);
var funcTypeNode = if (classType != null && ctParams != null) {
substituteTypeParamsInCodegen(this.wasm, ctParams, ctArgs, rawFuncTypeNode as Type)
} else {
rawFuncTypeNode
};
if (closureKey.specializesFunction() && funcTypeNode != null) {
funcTypeNode = substituteTypeParamsInCodegen(this.wasm,
enclosingFnParams as Array<TypeParameterType>,
typeArguments as Array<Type>, funcTypeNode as Type);
}
let params = growable<ValType>([new ValTypeStructRef()]); // ctx
let returns = new Array<ValType>();
if (funcTypeNode is FunctionType) {
// Discover the closure's type before mapping it. A class its
// signature names that no earlier walk registered would map to
// a bare structref here, while the pair struct lowering looks up
// by this signature is made from the registered class: the two
// keys then differ, and lowering finds no pair struct. A walk of
// a template is not a value and discovers nothing (see "An
// Erasure Is Not a Specialization" in CONTEXT.md).
let walkingTemplate = (enclosingFnParams != null && typeArguments == null) ||
(classType != null && classType.typeParameters != null &&
(classType.typeParameters as Array<TypeParameterType>).length > 0 &&
(classType.typeArguments == null || !isConcrete(classType)));
if (!walkingTemplate) {
this.typeLowerer.discoverType(funcTypeNode, model);
}
for (let p in funcTypeNode.parameters) {
mapParamTypeToWasmParams(this.wasm, p, params);
}
mapReturnTypeToWasmResults(this.wasm, funcTypeNode.returnType, returns);
} else {
returns.push(new ValTypeI32());
}
let sig = this.wasm.getSignature(params, returns);
let wasmFunc = new WasmFunction(sig, funcExpr, model);
wasmFunc.isClosure = true;
wasmFunc.isReferenceTaken = true;
wasmFunc.classType = classType;
if (closureKey.specializesFunction()) {
// The impl's body mentions the enclosing function's type
// parameters too; carrying the binding here is what routes
// its lowering (and its body's own RTA walk, via
// markFunctionReached) through the same substitution the
// enclosing specialization uses.
wasmFunc.typeParameters = enclosingFnParams;
wasmFunc.typeArguments = typeArguments;
}
var suffix = if ((classKey as String).length > 0) "_" + (classKey as String) else "";
suffix += closureKey.funcKey as String;
let fileBase = sanitizeName(getFileNameBase(getNodeFilePath(model, funcExpr)));
let locStr = if (funcExpr.loc != null) {
let loc = funcExpr.loc as SourceLocation;
"O" + i32ToString(loc.start)
} else {
i32ToString(funcExpr.id as i32)
};
wasmFunc.name = `closure_impl_${fileBase}${suffix}_${locStr}`;
wasmFunc.capturesThis = closureDep.capturesThis;
// A closure that only reads a celled variable still holds its
// cell, or it would read a stale copy (capturedInCell).
let celled = new Set<SymbolId>();
for (let symId in closureDep.captures) {
if (capturedInCell(symId, model)) {
celled.add(symId);
}
}
wasmFunc.mutableCaptures = celled;
let caps = wasmFunc.captures ?? new Array<SymbolId>();
wasmFunc.captures = caps;
for (let symId in closureDep.captures) {
let symName = if (model.symbolNames.has(symId)) {
model.symbolNames[symId]
} else {
"captured_var"
};
this.wasm.symbolNames[symId] = symName;
caps.push(symId);
}
var enclosingClassType = classType;
if (enclosingClassType == null && closureDep.capturesThis) {
var curr = funcExpr as Node;
while (true) {
let parent = model.getParent(curr);
if (parent == null) { break; }
if (parent is ClassDeclaration) {
let ct = model.getNodeType(parent);
if (ct is ClassType) {
enclosingClassType = ct;
}
break;
}
curr = parent;
}
}
let fields = new Array<WasmField>();
if (closureDep.capturesThis && enclosingClassType != null) {
var thisValType: ValType = new ValTypeStructRef();
if (let (true, info) = this.wasm.classInfos.get(getClassKey(enclosingClassType))) {
thisValType = new ValTypeRefNull(info.structType);
} else {
thisValType = typeToValType(this.wasm, enclosingClassType);
}
fields.push(new WasmField("this", thisValType, false));
}
for (let symId in closureDep.captures) {
let rawSymType = model.getBindingTypeById(symId);
var symType = if (classType != null && ctParams != null) {
substituteTypeParamsInCodegen(this.wasm, ctParams, ctArgs, rawSymType as Type)
} else {
rawSymType
};
if (closureKey.specializesFunction() && symType != null) {
symType = substituteTypeParamsInCodegen(this.wasm,
enclosingFnParams as Array<TypeParameterType>,
typeArguments as Array<Type>, symType as Type);
}
let valType = typeToValType(this.wasm, symType as Type);
var fieldType = valType;
if (celled.has(symId)) {
let cellStruct = getCellStruct(this.wasm, valType);
fieldType = new ValTypeRefNull(cellStruct);
}
fields.push(new WasmField("capture_" + i32ToString(symId as i32), fieldType, false));
}
let typeParameters = if (classType != null) classType.typeParameters else null;
let isGenericTemplate = classType != null &&
typeParameters != null &&
typeParameters.length > 0 &&
(classType.typeArguments == null || !isConcrete(classType));
// The walk of a generic function's own body — its parameters
// still open — is the FUNCTION-axis template, not a function:
// registered so the erased shape exists, never emitted. The real
// impls are minted above, one per instantiation, when the
// specialized bodies are walked with their argument vectors.
let isFuncTemplate = enclosingFnParams != null && typeArguments == null;
let contextStructName = `ClosureCtx_${fileBase}${suffix}_${locStr}`;
let contextStruct = new WasmStruct(contextStructName, fields);
wasmFunc.contextStruct = contextStruct;
if (!isGenericTemplate && !isFuncTemplate) {
this.wasm.types.push(contextStruct);
this.markTypeReached(contextStruct);
this.wasm.addFunction(wasmFunc);
this.markFunctionReached(wasmFunc);
}
if (!closureKey.specializesFunction()) {
// The by-node fallback stays the per-node template; a
// function-specialized impl must never be found through it,
// or a missed specialization would silently reuse another
// instantiation's context layout.
this.wasm.closureFunctions[funcExpr] = wasmFunc;
}
this.wasm.specializedClosures[closureKey] = wasmFunc;
this.queueReferrer(new Referrer(false, noSymbolId, funcExpr.id as i32, model, classType, this.currentReachable, typeArguments));
}
// 4. Record function adaptations
for (let fAdapt in deps.functionAdaptations) {
let src = resolveType(fAdapt.source) as FunctionType;
let tgt = resolveType(fAdapt.target) as FunctionType;
let expr = fAdapt.node;
this.typeLowerer.discoverType(src, model);
this.typeLowerer.discoverType(tgt, model);
var expectedWasmSig: WasmSignature | null = null;
var resolvedTargetStruct: WasmStruct | null = null;
let parent = model.getParent(expr);
if (parent is CallExpression) {
var argIdx = -1;
for (var idx = 0; idx < parent.args.length; idx += 1) {
if (parent.args[idx] === expr) {
argIdx = idx;
break;
}
}
if (argIdx >= 0 && parent.callee is MemberExpression) {
let mem = parent.callee as MemberExpression;
let calleeType = model.getNodeType(mem);
if (calleeType is FunctionType) {
if (argIdx < calleeType.parameters.length) {
let paramType = calleeType.parameters[argIdx];
if (paramType is FunctionType) {
let paramCs = getClosureStruct(this.wasm, paramType);
resolvedTargetStruct = paramCs;
this.reachablyNamedClosures.add(paramCs);
let paramValTypes = growable<ValType>([new ValTypeStructRef()]); // context
for (let p in paramType.parameters) {
mapParamTypeToWasmParams(this.wasm, p, paramValTypes);
}
let returnValTypes = new Array<ValType>();
if (!isVoidOrNeverType(paramType.returnType)) {
returnValTypes.push(typeToValType(this.wasm, paramType.returnType));
}
expectedWasmSig = this.wasm.getSignature(paramValTypes, returnValTypes);
}
}
}
}
}
let wrapperSig = if (expectedWasmSig != null) {
expectedWasmSig
} else {
let pValTypes = growable<ValType>([new ValTypeStructRef()]); // ctx
for (let p in tgt.parameters) {
mapParamTypeToWasmParams(this.wasm, p, pValTypes);
}
let rValTypes = new Array<ValType>();
mapReturnTypeToWasmResults(this.wasm, tgt.returnType, rValTypes);
this.wasm.getSignature(pValTypes, rValTypes)
};
let actualClosureStruct = getClosureStruct(this.wasm, src);
this.reachablyNamedClosures.add(actualClosureStruct);
if (resolvedTargetStruct == null) {
let tgtCs = getClosureStruct(this.wasm, tgt);
resolvedTargetStruct = tgtCs;
this.reachablyNamedClosures.add(tgtCs);
}
// A closure that already is one of the target type needs no wrapper:
// two function types can differ only in what shares a wasm type, such
// as tuple types that meet (#1137). Lowering passes the value on.
if (actualClosureStruct === resolvedTargetStruct) {
continue;
}
let adaptKey = getFunctionAdaptationKey(src, tgt);
let existingWrapper: WasmFunction | null = if (this.wasm.functionAdaptations.has(adaptKey)) {
this.wasm.functionAdaptations[adaptKey]
} else {
null
};
if (existingWrapper != null) {
existingWrapper.functionAdaptationResolvedSourceStruct = actualClosureStruct;
existingWrapper.functionAdaptationResolvedTargetStruct = resolvedTargetStruct;
this.wasm.functionAdaptationWrappers[expr] = existingWrapper;
this.markFunctionReached(existingWrapper);
} else {
let wrapperFunc = new WasmFunction(wrapperSig, null, model);
let fileBase = sanitizeName(getFileNameBase(getNodeFilePath(model, expr)));
let locStr = if (expr.loc != null) {
let loc = expr.loc as SourceLocation;
"O" + i32ToString(loc.start)
} else {
i32ToString(expr.id as i32)
};
wrapperFunc.name = `function_adapt_${fileBase}_${locStr}`;
wrapperFunc.isFunctionAdaptation = true;
wrapperFunc.isReferenceTaken = true;
wrapperFunc.functionAdaptationSource = src;
wrapperFunc.functionAdaptationTarget = tgt;
wrapperFunc.functionAdaptationResolvedSourceStruct = actualClosureStruct;
wrapperFunc.functionAdaptationResolvedTargetStruct = resolvedTargetStruct;
let packs = this.#functionAdaptationPacks(src, tgt);
if (packs.length > 0) {
this.wasm.functionAdaptationPacks[wrapperFunc] = packs;
}
this.wasm.addFunction(wrapperFunc);
this.markFunctionReached(wrapperFunc);
this.wasm.functionAdaptations[adaptKey] = wrapperFunc;
this.wasm.functionAdaptationWrappers[expr] = wrapperFunc;
}
}
}
getModelPath(model: SemanticModel): String {
return model.sourcePath;
}
getNodeModel(node: Node, defaultModel: SemanticModel): SemanticModel {
let id = node.id as i32;
if (this.nodeIdToModel.has(id)) {
return this.nodeIdToModel[id];
}
return defaultModel;
}
getClassModel(ct: ClassType): SemanticModel {
var curr: ClassType | null = ct;
while (curr != null) {
let lookupId = (curr.genericSource ?? curr).symbolId;
if (this.classModels.has(lookupId)) {
return this.classModels[lookupId];
}
if (this.program.modelIndex.symbolToModel.has(lookupId)) {
return this.program.modelIndex.symbolToModel[lookupId];
}
curr = curr.superType;
}
return this.program.units[0].model;
}
getClassDeclType(classDecl: Node, model: SemanticModel): ClassType | null {
let {cha} = this;
if (cha.classDeclTypeCache.has(classDecl.id)) {
return cha.classDeclTypeCache[classDecl.id];
}
let raw = model.getNodeType(classDecl);
if (raw is ClassType) {
cha.classDeclTypeCache[classDecl.id] = raw;
return raw;
}
var sym = model.resolve(classDecl);
if (sym == null && classDecl.loc != null) {
sym = model.resolveByOffset((classDecl.loc as SourceLocation).start);
}
if (sym != null) {
let bType = model.getBindingTypeDirect(sym);
if (bType is ClassType) {
cha.classDeclTypeCache[classDecl.id] = bType;
return bType;
}
}
return null;
}
findPreludeClass(w: WellKnown): ClassType | null {
let key = w as i32;
if (this.#preludeClassCache.has(key)) {
return this.#preludeClassCache[key];
}
let name = wellKnownName(w);
for (let unit in this.program.units) {
let {model} = unit;
let t = model.getExportType(name);
if (t is ClassType && isWellKnown(w, t.name, t.sourcePath)) {
this.#preludeClassCache[key] = t;
return t;
}
}
return null;
}
findPreludeInterface(w: WellKnown): InterfaceType | null {
let key = w as i32;
if (this.#preludeInterfaceCache.has(key)) {
return this.#preludeInterfaceCache[key];
}
let name = wellKnownName(w);
for (let unit in this.program.units) {
let {model} = unit;
let t = model.getExportType(name);
if (t is InterfaceType && isWellKnown(w, t.name, t.sourcePath)) {
this.#preludeInterfaceCache[key] = t;
return t;
}
}
return null;
}
/**
* Is this a static the class TEMPLATE can carry? A static cannot name
* the class's type parameters, so one that declares none of its own
* has exactly one copy and the template holds it. One that DOES
* declare its own is monomorphized per solved argument list, like a
* generic function, and must not also be lowered at the erasure —
* `Array.from<A>`'s body constructs an `Array<A>`, which at the
* erasure is an `Array<anyref>` nothing ever instantiated.
*/
#isMonomorphicStatic(mDef: MethodDefinition): boolean {
if (!mDef.isStatic) { return false; }
let tps = mDef.typeParameters;
if (tps == null) { return true; }
return tps.length == 0;
}
processQueues(): void {
// Counted in locals and reported once at the end: the item loop is
// the hottest in the compiler, and a map lookup per item would be
// a measurable part of what it is trying to measure.
//
// `items` against the size of the program says whether the walk is
// linear in the program; `outerRounds` is the specialization
// fixpoint, and each of its rounds rewalks whatever the previous
// one queued.
var items = 0;
var outerRounds = 0;
let nodesAtStart = this.visitor.discoveredNodes;
var lastInstantiatedCount = -1;
while (this.instantiatedSpecializedClasses.size > lastInstantiatedCount) {
outerRounds += 1;
lastInstantiatedCount = this.instantiatedSpecializedClasses.size;
var progress = true;
while (progress) {
while (this.reachHead < this.reachableQueue.length || this.checkHead < this.checkableQueue.length) {
items += 1;
var refItem: Referrer | null = null;
if (this.reachHead < this.reachableQueue.length) {
refItem = this.reachableQueue[this.reachHead];
this.reachHead += 1;
} else {
refItem = this.checkableQueue[this.checkHead];
this.checkHead += 1;
}
this.currentReachable = refItem.isReachable;
this.inQueueWalk = true;
this.walkingTemplateOf = if (refItem.classType != null &&
!isConcrete(refItem.classType as ClassType)) {
refItem.classType
} else {
null
};
if (refItem.isSymbol) {
let {symId} = refItem;
let {model} = refItem;
if (refItem.isReachable) {
this.reachedGlobals.add(symId);
}
// A global of a module whose bodies waited to be reached.
// Check it before reading its node types or its dependency
// record, both of which checking is what writes.
let deferredGlobal = model.deferredBodies;
if (deferredGlobal != null) {
deferredGlobal.checkGlobalBody(symId);
}
var funcExpr: Node | null = null;
let decls = model.getGlobalDeclarations(symId);
if (decls != null) {
let {visitor} = this;
let resolver = (t: Type) => t;
let declList = decls as GrowableArray<Node>;
for (let decl in declList) {
visitor.discoverNodeTypes(decl, model, resolver);
if (decl is FunctionDeclaration) {
visitor.discoverFunctionDeclaration(symId, decl, model);
} else if (decl is VariableDeclaration) {
visitor.discoverVariableDeclaration(symId, decl, model);
if (decl.init is FunctionExpression) {
funcExpr = decl.init;
}
} else if (decl is DeclareFunction) {
visitor.discoverDeclareFunction(decl, model);
}
}
}
if (let (true, deps) = model.symbolDependencies.get(symId)) {
this.traverseDependencies(deps, model, refItem.classType, refItem.typeArguments, funcExpr);
}
} else {
let {nodeId} = refItem;
var model = refItem.model;
if (let (true, m) = this.nodeIdToModel.get(nodeId)) {
model = m;
}
var memberSuffix = if (refItem.classType != null) "@" + (getClassKey(refItem.classType as ClassType) as String) else "";
let {typeArguments} = refItem;
if (typeArguments != null) {
memberSuffix += `<${getSpecializedName("", typeArguments)}>`;
}
let memberKey = i32ToString(nodeId) + memberSuffix;
// A checkable visit records only `reachedMembers`, so a
// later reachable visit of the same member still runs.
// Collapsing the two skipped that second traversal, and
// with it the marking of closures the first pass created
// but left unreached — pruned from wasm.functions, they
// kept index -1 while lowering still emitted a ref_func to
// them.
if (refItem.isReachable) {
if (this.reachedReachableMembers.has(memberKey)) {
continue;
}
this.reachedReachableMembers.add(memberKey);
this.reachedMembers.add(memberKey);
} else {
if (this.reachedMembers.has(memberKey)) {
continue;
}
this.reachedMembers.add(memberKey);
}
// A member of a module whose bodies waited to be reached.
// Check it before anything below reads its node types or
// its dependency record, both of which checking is what
// writes.
let deferredMember = model.deferredBodies;
if (deferredMember != null) {
deferredMember.checkBodyOfNode(nodeId);
}
let node = if (this.nodeIdToNode.has(nodeId)) this.nodeIdToNode[nodeId] else null;
if (node != null) {
let {classType} = refItem;
let {visitor} = this;
let {specializer} = this;
let resolver = (t: Type) => {
var res = substituteTypeParamsInClassContext(this.wasm, classType, t);
// The parameters these arguments bind, when this
// referrer is one monomorphization of the walked node:
// the node's own — a generic arrow (FunctionExpression)
// or a generic METHOD (MethodDefinition) — or, for a
// CLOSURE specialized per enclosing instantiation, the
// enclosing generic function's. The same lookup
// traverseDependencies uses.
if (refItem.typeArguments != null) {
let typeParameters = enclosingOwnTypeParameters(model, node);
if (typeParameters != null) {
res = substituteTypeParamsInCodegen(this.wasm, typeParameters, refItem.typeArguments as Array<Type>, res);
}
}
return res;
};
if (!model.nodeDependencies.has(nodeId)) {
visitor.discoverNodeTypes(node, model, resolver);
} else {
visitor.registerLiterals(node);
visitor.registerInstantiations(node, model, resolver,
if (refItem.classType != null) refItem.classType as ClassType else null);
}
// A referrer whose class is an ERASURE registers nothing:
// the erasure has a struct and no methods, and every value
// it stands for belongs to some real specialization that
// queues its own referrer.
let refClassIsErasure = refItem.classType != null &&
containsErasedType(refItem.classType as Type);
// A field decorator's member body is shared by every
// application of that decorator in the class's chain, and
// each application compiles its own copy under its own
// name, scope key and type arguments — as the member
// collection loops do. One node cannot say which
// application a referrer meant, so every one is registered.
let decoratorInts = if (refItem.classType != null && !refClassIsErasure) {
findDecoratorIntermediates(refItem.classType as ClassType, this.classDecls, node)
} else {
new Array<ClassType>()
};
if (decoratorInts.length > 0) {
let ct = refItem.classType as ClassType;
getClassKey(ct);
let lookupId = (ct.genericSource ?? ct).symbolId;
let cd = if (let (true, decl) = this.classDecls.get(lookupId)) decl else null;
for (let decInt in decoratorInts) {
// A `shared` method lives under the declaration's key,
// one copy for every application in the class.
let scope = if (node is MethodDefinition && node.isShared &&
decInt.decoratorSharedScopeKey != null) {
decInt.decoratorSharedScopeKey
} else {
decInt.privateScopeKey
};
let decId = (decInt.genericSource ?? decInt).symbolId;
let nodeModel = if (this.classModels.has(decId)) {
this.classModels[decId]
} else {
this.classModels[lookupId]
};
let regs = new Array<WasmFunction>();
if (node is MethodDefinition) {
let {typeParameters} = node;
if (node.isConstructor || node.isStatic ||
(typeParameters != null && typeParameters.length > 0)) {
continue;
}
var methName = getMethodName(nodeModel, node);
if (scope != null && methName.startsWith("#")) {
methName = `${scope as String}::${methName}`;
}
let regF = specializer.registerClassMethod(ct, cd, methName, node, false, false, null, nodeModel, null);
regF.declaringType = decInt;
applyMixinPrivateScope(regF, node, scope);
regs.push(regF);
} else if (node is AccessorDeclaration) {
var accName = memberKeyOf(nodeModel, node.name as Node);
if ((decInt.decoratorSubjectName as String) == accName) {
accName = decInt.decoratorFieldName as String;
}
let accPrefix = if (scope != null && accName.startsWith("#")) {
(scope as String) + "::"
} else {
""
};
if (node.getter != null) {
let regG = specializer.registerClassMethod(ct, cd, `${accPrefix}get#${accName}`, node, false, false, null, nodeModel, null);
regG.declaringType = decInt;
applyMixinPrivateScope(regG, node, scope);
regs.push(regG);
}
let {setter} = node;
if (setter != null) {
let regS = specializer.registerClassMethod(ct, cd, `${accPrefix}set#${accName}`, setter, false, false, null, nodeModel, null);
regS.declaringType = decInt;
applyMixinPrivateScope(regS, setter, scope);
regs.push(regS);
}
}
if (refItem.isReachable && isConcrete(ct)) {
for (let f in regs) {
this.wasm.addFunction(f);
this.markFunctionReached(f);
}
}
}
} else if (node is MethodDefinition && refItem.classType != null && !refClassIsErasure) {
let ct = refItem.classType as ClassType;
getClassKey(ct);
let lookupId = (ct.genericSource ?? ct).symbolId;
let cd = if (let (true, decl) = this.classDecls.get(lookupId)) decl else null;
// Mixin-declared methods carry the mixin's private
// scope key, and mixin PRIVATE methods register under
// it — mirroring the member-collection loops, so this
// node-driven path never creates an unscoped twin.
let mixScope = mixinScopeOfMember(this.program, this.classModels[lookupId], cd, node);
let nodeModel = mixinModelOfMember(this.program, this.classModels[lookupId], cd, node) ?? this.classModels[lookupId];
var methName = getMethodName(nodeModel, node);
if (node.isConstructor) {
methName = if (methName == "<constructor>") "<constructor>" else "<constructor>." + methName;
} else if (mixScope != null && methName.length > 0 &&
methName.sliceBytes(0, 1) == "#") {
methName = `${mixScope}::${methName}`;
}
let regF = specializer.registerClassMethod(ct, cd, methName, node, false, false, null, nodeModel, null);
regF.declaringType = findDeclaringMixinIntermediate(ct, this.classDecls, node);
applyMixinPrivateScope(regF, node, mixScope);
// A REACHABLE member referrer is the evidence that
// used to be implied by the vtable force-reach:
// registration alone is erased by layout()'s
// classMethodMap rebuild (binary-size.md §3a). Only
// for CONCRETE classes — a template referrer registers
// the unspecialized copy, and reaching that is
// 'non-concrete function reached'; the fan-out queues
// a concrete referrer per specialization. NOT for
// constructors: their evidence is a `new` site (which
// pends them by key) — the checker's records name
// ctors for paths that never call one, and reaching
// here emitted a constructor in every literal-only
// String program.
// A static is the one exception to the concreteness
// rule. It cannot name the class's type parameters, so
// there is exactly one copy of it and the template
// carries it: `Holder.answer()` has nothing to bind.
//
// A static that declares its OWN parameters is the
// opposite case and is held out entirely: its copies are
// the monomorphizations, which the call site looks up by
// specialized name. Registering the unspecialized one
// too lowers its body at the erasure, where
// `new GrowableArray<A>` is an `Array<anyref>` nothing ever
// constructed.
let genericStatic = node.isStatic &&
!this.#isMonomorphicStatic(node);
// A GENERIC method registered with no type arguments is
// the body at the method's OWN erasure, and there is no
// such function: `map<R>` exists once per R, each with
// its own signature, minted by registerGenericMethodUse
// at the call site. Reaching the erased registration
// emitted one dead body per specialization of the class
// (80 `Array<X>.map` in the compiler's own module,
// referenced by nothing) — and each one built its result
// with `new GrowableArray<R>`, which is the only thing that ever
// made an ERASURE look constructible.
let {typeParameters} = regF;
let isGenericAtErasure = typeParameters != null &&
typeParameters.length > 0 &&
regF.typeArguments == null;
if (refItem.isReachable && !genericStatic && !isGenericAtErasure &&
(isConcrete(ct) || this.#isMonomorphicStatic(node)) &&
!node.isConstructor && methName != "<constructor>") {
// The statics' backing globals hang off reaching a
// static, not off instantiating the class — a generic
// class whose statics are all anyone uses is never
// instantiated, and its counter still has to exist.
if (node.isStatic && cd is ClassDeclaration) {
specializer.discoverStaticFields(
ct, cd, this.classModels[lookupId]);
}
this.wasm.addFunction(regF);
this.markFunctionReached(regF);
}
} else if (node is AccessorDeclaration && refItem.classType != null && !refClassIsErasure) {
let ct = refItem.classType as ClassType;
getClassKey(ct);
let accName = memberKeyOf(model, node.name as Node);
if (accName != "") {
let lookupId = (ct.genericSource ?? ct).symbolId;
let cd = if (let (true, decl) = this.classDecls.get(lookupId)) decl else null;
if (node.isStatic && cd is ClassDeclaration) {
specializer.discoverStaticFields(
ct, cd, this.classModels[lookupId]);
}
let mixScope = mixinScopeOfMember(this.program, this.classModels[lookupId], cd, node);
let nodeModel = mixinModelOfMember(this.program, this.classModels[lookupId], cd, node) ?? this.classModels[lookupId];
// A mixin's PRIVATE accessor registers under the
// mixin's scope key, exactly as the method arm above
// and the member-collection loops do. Registering the
// bare name here would mint an unscoped twin on the
// host — a second function under the name the host's
// own accessor owns — and leave the name the mixin
// body actually looks up unregistered.
let isPrivateAcc = accName.length > 0 && accName.sliceBytes(0, 1) == "#";
let accPrefix = if (mixScope != null && isPrivateAcc) {
mixScope + "::"
} else {
""
};
if (node.getter != null) {
let regG = specializer.registerClassMethod(ct, cd, `${accPrefix}get#${accName}`, node, false, false, null, nodeModel, null);
regG.declaringType = findDeclaringMixinIntermediate(ct, this.classDecls, node);
applyMixinPrivateScope(regG, node, mixScope);
if (refItem.isReachable && (isConcrete(ct) || node.isStatic)) {
this.wasm.addFunction(regG);
this.markFunctionReached(regG);
}
}
let {setter} = node;
if (setter != null) {
let regS = specializer.registerClassMethod(ct, cd, `${accPrefix}set#${accName}`, setter, false, false, null, nodeModel, null);
regS.declaringType = findDeclaringMixinIntermediate(ct, this.classDecls, setter as Node);
applyMixinPrivateScope(regS, setter, mixScope);
if (refItem.isReachable && (isConcrete(ct) || node.isStatic)) {
this.wasm.addFunction(regS);
this.markFunctionReached(regS);
}
}
}
} else if (node is FieldDefinition && refItem.classType != null) {
let ct = refItem.classType as ClassType;
if (node.isStatic) {
if (refItem.isReachable) {
let lookupId = (ct.genericSource ?? ct).symbolId;
if (let (true, cd) = this.classDecls.get(lookupId)) {
if (cd is ClassDeclaration) {
specializer.discoverStaticFields(ct, cd, this.classModels[lookupId]);
}
}
}
} else {
let cKey = getClassKey(ct);
let propName = memberKeyOf(model, node.name as Node);
let {typeParameters} = ct;
let isGenericTemplate = typeParameters != null &&
typeParameters.length > 0 &&
(ct.typeArguments == null || !isConcrete(ct));
if (propName != "" && !isGenericTemplate) {
let getterKey = getClassMethodKey(cKey, "get#" + propName);
if (let (true, f) = this.wasm.classMethodMap.get(getterKey)) {
this.markFunctionReached(f);
} else if (refItem.isReachable) {
this.#pendingMemberReaches.push(getterKey);
}
let setterKey = getClassMethodKey(cKey, "set#" + propName);
if (let (true, f) = this.wasm.classMethodMap.get(setterKey)) {
this.markFunctionReached(f);
} else if (refItem.isReachable) {
this.#pendingMemberReaches.push(setterKey);
}
}
}
}
}
if (let (true, deps) = model.nodeDependencies.get(nodeId)) {
this.traverseDependencies(deps, model, refItem.classType, refItem.typeArguments, node);
}
}
}
this.inQueueWalk = false;
this.walkingTemplateOf = null;
progress = false;
this.currentReachable = true;
let endIdx = this.wasm.globals.length;
while (this.globalsHead < endIdx) {
let g = this.wasm.globals[this.globalsHead];
this.globalsHead += 1;
this.markValTypeReached(g.type);
let {initVTable} = g;
if (initVTable != null) {
let vtableInit = initVTable;
this.markTypeReached(vtableInit.structType);
// A class vtable's slots are reached by #fillReachedSlots,
// only where something can dispatch to them; every other
// table's functions (interface trampolines) are all live.
if (vtableInit.isClassVTable) {
continue;
}
for (let func in vtableInit.funcs) {
if (!this.reachedFunctionsSet.has(func)) {
this.markFunctionReached(func);
progress = true;
}
}
}
}
}
}
performance.add("codegen-discovery-queues-items", 0.0, items);
performance.add("codegen-discovery-queues-rounds", 0.0, outerRounds);
performance.add("codegen-discovery-queues-nodes", 0.0,
this.visitor.discoveredNodes - nodesAtStart);
}
}
/**
* The function-own type-parameter list a node's walk substitutes
* against: the node's own, when its checked type carries one, else the
* nearest enclosing FunctionExpression or MethodDefinition's. A
* closure has no parameters of its own, so this is how its walk finds
* the axis its Referrer's typeArguments belong to — the enclosing
* generic function's. Stops at a class boundary: the class's
* parameters are a separate axis, substituted from the walk's
* classType.
*/
function enclosingOwnTypeParameters(model: SemanticModel, node: Node): Array<TypeParameterType> | null {
var curr: Node | null = node;
while (curr != null) {
let c = curr as Node;
if (c is FunctionExpression || c is MethodDefinition) {
let t = model.getNodeType(c);
if (t is FunctionType) {
let tps = t.typeParameters;
if (tps != null && tps.length > 0) {
return tps;
}
}
}
if (c is ClassDeclaration) {
return null;
}
curr = model.getParent(c);
}
return null;
}
function getMethodName(model: SemanticModel, md: MethodDefinition): String {
return memberKeyOf(model, md.name as Node);
}
function getNodeFilePath(model: SemanticModel, node: Node): String {
var curr: Node | null = node;
while (curr != null) {
if (curr is Module) {
return curr.path;
}
curr = model.getParent(curr);
}
return "";
}
function getFileNameBase(path: String): String {
var lastSlash = -1;
var i = 0;
let len = path.length;
while (i < len) {
if (path.sliceBytes(i, i + 1) == "/" || path.sliceBytes(i, i + 1) == "\\") {
lastSlash = i;
}
i += 1;
}
if (lastSlash >= 0) {
return path.sliceBytes(lastSlash + 1, len);
}
return path;
}
function sanitizeName(s: String): String {
let sb = new StringBuilder();
var i = 0;
let len = s.length;
while (i < len) {
let char = s.sliceBytes(i, i + 1);
if (char == "." || char == "-" || char == "/" || char == "\\") {
sb.append("_");
} else {
sb.append(char);
}
i += 1;
}
return sb.toString();
}
/**
* A member a reached access resolves on a class, waiting to be found
* among the registered methods (see #fillReachedSlots).
*/
final class PendingStaticTarget {
classType: ClassType;
memberName: String;
var resolved = false;
new(this.classType, this.memberName);
}
/**
* The classes a type names directly: itself, the members of a union, the
* target and arguments of an alias. Bounded, since aliases can nest.
*/
function collectNamedClasses(t: Type, out: GrowableArray<ClassType>,
depth: i32, throughTuples: boolean = false): void {
if (depth > 8) {
return;
}
match (t) {
case ClassType as ct: {
out.push(ct);
}
case UnionType {types}: {
for (let m in types) {
collectNamedClasses(m, out, depth + 1, throughTuples);
}
}
case EnumType as et: {
collectNamedClasses(et.backingType, out, depth + 1, throughTuples);
}
case TypeAliasType as ta: {
collectNamedClasses(ta.target, out, depth + 1, throughTuples);
let {typeArguments} = ta;
if (typeArguments != null) {
for (let a in typeArguments as Array<Type>) {
collectNamedClasses(a, out, depth + 1, throughTuples);
}
}
}
// Releasing a tuple releases the owners among its elements.
case TupleType {elementTypes}: {
if (throughTuples) {
for (let el in elementTypes) {
collectNamedClasses(el, out, depth + 1, throughTuples);
}
}
}
case InlineTupleType {elementTypes}: {
if (throughTuples) {
for (let el in elementTypes) {
collectNamedClasses(el, out, depth + 1, throughTuples);
}
}
}
case _: {}
}
}
- 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 |
|
|