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, node: Node) { let found = new Array(); 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, 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(); classModels = new Map(); interfaceDecls = new Map(); interfaceModels = new Map(); symbolIdToModel = new Map(); symbolIdToDecl = new Map(); symbolIdToTargetId = new Map(); nodeIdToNode = new Map(); nodeIdToModel = new Map(); // RTA Reachability tracking state reachedGlobals = new Set(); recordLiteralArgs = new Set(); recordLiteralCtorArgs = new Set(); recordLiteralMethodArgs = new Set(); recordLiteralSpecArgs = new Set(); recordResultCalls = new Array(); recordResultCallIds = new Set(); /** * Method and generic function calls with a record result, by call id * and target, recorded once each. */ recordResultMethodCalls = new Set(); reachedMembers = new Set(); /** * 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(); instantiatedClasses = new Set(); instantiatedSpecializedClasses = new Set(); reachablyNamedClasses = new Set(); /** 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(); 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(); /** * 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(); /** * 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(); reachablyNamedAnonStructs = new Set(); /** * 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(); #namedCompositeKeys = new Set(); /** * 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 * ".". */ #demandedInterfaceMembers = new Set(); var #arrayPatternReached = false; /** The symbol ids of each interface declaration and those it extends. */ #interfaceLineages = new Map>(); /** Interface members given slots, keyed "|". */ #slottedInterfaceMembers = new Set(); /** What #syncInterfaceSlots last looked at; see there. */ var #interfaceSlotSyncState = -1; discoveredTypes = new Set(); reachedSemanticTypes = new Set(); specializedInterfaces = new Array(); genericInterfaceMethodDemands = new Array(); /** Demands keyed "." for dedup and slot lookup. */ #genericInterfaceDemandsByKey = new Map(); genericClassMethodDemands = new Array(); /** Demands keyed "." for dedup. */ #genericClassDemandsByKey = new Map(); specializedClassTypes = new Map>(); reachedClassMembers = new Map>(); reachedReachableClassMembers = new Map>(); /** The generic classes whose synthesized release member was reached. */ #reachedSyntheticReleases = new Set(); var mixinToClasses = new Map>(); #preludeClassCache = new Map(); #preludeInterfaceCache = new Map(); reachableQueue = new Array(); checkableQueue = new Array(); 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(); reachedIds = new Set(); /** * 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(); reachedFunctionsSet = new Set(); reachedTypesSet = new Set(); emittedTypes = new Array(); /** * 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(); /** * 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(); /** * 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(); asyncFrameFutureModels = new Array(); /** * 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(); parsedAdaptationRefs = new Map(); var typeIdGenerator = makeTypeIdGenerator(1); new(this.program, this.wasm, this.target = "core") { this.wasm.target = this.target; var idGen: IdGenerator | 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.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.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(); } // 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.push` is used because `Array.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 "")); } 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) { this.notePendingStaticTargets(ta, opName); } } } // `releaseOwned` 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) { 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 (`_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` 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): 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(); let seen = new Set(); 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`, 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): 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` on a class nothing reaches // used to specialize and emit `Completer` whole — all six of // its methods, plus the `Future` and `Box` 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)) { 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()); 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()); 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; 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()); 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()); 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()); this.wasm.types.push(emptyVTableStruct); this.wasm.interfaceVTableStructs[iKey] = emptyVTableStruct; let fatPtrFields = growable([ 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 = () => ...` and `function f() { ... }` 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>(); 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(); let seenMixins = new Map(); 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(); } 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(); // Pre-discover implemented interfaces of all reached/specialized and declared classes. let classesToDiscover = new Array(); 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(); 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(); 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(); 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(); 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(); 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(); 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(); 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(); 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 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` 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` 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(); 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(); 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(); 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>(); var #pendingStaticTargets = new Array(); /** * 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 { let keys = new Set(); 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(); 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(); let keptFuncs = new Array(); 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; 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. * - ``: 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 `` 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 * `` 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([ 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(); 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(); 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(); 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(); 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([ new WasmField("", 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(); let objectRoots = new Array(); let objectRootSet = new HashSet(); 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); } } } // `` 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(); // 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(); 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("", new ValTypeRefNull(typeInfo), false); rootFields[root] = f; field = f; } if (vst.fieldIndexByName("") < 0) { prependField(vst, field as WasmField); } if (root.superStruct == null) { root.superStruct = vtableBase; } } if (objectRoots.length > 0) { let objectStruct = new WasmStruct("Object", growable([ new WasmField("", 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(); 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()); 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([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(); for (let g in wasm.globals) { placed.push(false); } let ordered = new Array(); 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, placed: GrowableArray): 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(); /** * 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(); 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(); var cc: ClassType | null = cType; while (cc != null) { chain.push(cc as ClassType); cc = (cc as ClassType).superType; } let orderedNames = new Array(); let seenNames = new Set(); 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(); 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(); 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(); let newFields = new Array(); 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, 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, 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, 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 { let decl = it.genericSource ?? it; if (let (true, cached) = this.#interfaceLineages.get(decl.symbolId)) { return cached; } let ids = new Array(); let seen = new Set(); let pending = growable([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, 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(); let updatedSet = new Set(); let classes = new Array(); 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, updatedSet: HashSet): 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(); var ancestor: ClassType | null = classType; while (ancestor != null) { chain.push(ancestor); ancestor = ancestor.superType; } let orderedNames = new Array(); let seenNames = new Set(); 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(); for (let field in vtableStructType.fields) { let fieldName = field.name; if (fieldName != null) { fieldByName[fieldName] = field; } } let orderedFields = new Array(); 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(); let newFields = new Array(); 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; 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): 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 { let packs = new Array(); // 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([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(); 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(); this.cha.addInterfaceToTransitiveList(it, supers, new Map()); 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(); 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(); 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).length) else "null"; let tparamsLen = if (ccw.typeParameters != null) i32ToString((ccw.typeParameters as Array).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.:iterator` returns an * `ArrayIterator` packed as `Iterator`), 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(); let seenClassKeys = new Map(); 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` 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)) { throw new Error("Internal error: class-interface vtable funcs list is not growable"); } let growable = funcs as GrowableArray; 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(); 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): void { var round = true; while (round) { round = false; let pending = new Array(); 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`). 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(); #reachableEqualityBases = new Set(); 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(); 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(); 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 | null = null, node: Node | null = null): void { let ctParams: Array | null = if (classType != null) getClassTypeParameters(classType) else null; let ctArgs: Array | 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` inside `Box.make` stayed `State`, was erased // to `State`, and the `State` 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, 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(); 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, typeArguments as Array, funcTypeNode as Type); } let params = growable([new ValTypeStructRef()]); // ctx let returns = new Array(); 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).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(); for (let symId in closureDep.captures) { if (capturedInCell(symId, model)) { celled.add(symId); } } wasmFunc.mutableCaptures = celled; let caps = wasmFunc.captures ?? new Array(); 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(); 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, typeArguments as Array, 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([new ValTypeStructRef()]); // context for (let p in paramType.parameters) { mapParamTypeToWasmParams(this.wasm, p, paramValTypes); } let returnValTypes = new Array(); 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([new ValTypeStructRef()]); // ctx for (let p in tgt.parameters) { mapParamTypeToWasmParams(this.wasm, p, pValTypes); } let rValTypes = new Array(); 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`'s body constructs an `Array`, which at the * erasure is an `Array` 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; 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, 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() }; 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(); 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 == "") "" else "." + 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` is an `Array` 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` 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.map` in the compiler's own module, // referenced by nothing) — and each one built its result // with `new GrowableArray`, 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 != "") { // 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 | 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, 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) { 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 _: {} } }