/** * Type system for the Zena compiler. * * Types are the semantic representation of Zena's type system. They are * produced by the checker and consumed by codegen and analysis passes. * * Design: * - Sealed hierarchy enables exhaustive pattern matching. * - Primitive types are singletons (created once in TypeContext). * - Complex types (Class, Interface) are mutable classes built incrementally. * - Type identity is used for equality (interned generic instantiations). * - The AST is never mutated — types live in the SemanticModel side table. */ import { StringBuilder, IterableUtils, growable } from 'zena:core'; import { Set, HashMap, HashSet, OrderedHashMap, MapEntry } from 'zena:collections'; import { Expression, Statement, IdGenerator, FieldDefinition, EnumDeclaration } from './ast.zena'; import { SymbolId, noSymbolId } from './scope/symbol.zena'; import { WellKnown, isWellKnown } from './well-known.zena'; @intrinsic('hash') declare function hash(value: T): i32; export distinct type TypeId = i32; /** * The only way to get TypeIds. See `makeNodeIdGenerator` in ast.zena for why * the conversion lives here rather than being exported on its own. */ export function makeTypeIdGenerator(nextId: i32 = 1): IdGenerator { return new IdGenerator((id: i32) => id as TypeId, nextId); } var _nextTypeUid = 1; function nextTypeUid() { let id = _nextTypeUid; _nextTypeUid += 1; return id; } // Counts for the memory census (census.zena). Every Type takes a uid, // so the total is free; the kinds with a constructor of their own // count themselves there. Key strings are counted where they are // cached (codegen-utils.zena), which is the only place they are made. var _classTypes = 0; let _functionTypes = 0; var _interfaceTypes = 0; var _mixinTypes = 0; var _typeParameterTypes = 0; var _typeKeysCached = 0; var _typeKeyBytes = 0; // How the nominal instantiation caches fare: a hit still rebuilds the // instantiation's supertypes, constructor and lists today, so the hit // count is the allocation the cache does not save. var _instantiationHits = 0; var _instantiationMisses = 0; // Nominal types `substituteInType` builds outside any cache. var _substitutedNominals = 0; var _substitutionCacheHits = 0; var _functionTypeHits = 0; export function functionTypeHits(): i32 { return _functionTypeHits; } // Substitutions whose arguments mention a type parameter, built fresh // because they cannot be cached (see substituteInType's class case). let _parametricSubstitutions = 0; export function substitutionCacheHits(): i32 { return _substitutionCacheHits; } export function parametricSubstitutions(): i32 { return _parametricSubstitutions; } /** The type counters as they stood when a phase boundary was passed. */ export final class TypeMark { label: String; total: i32; classes: i32; functions: i32; interfaces: i32; new(this.label, this.total, this.classes, this.functions, this.interfaces); } let _typeMarks = new GrowableArray(); /** Records the counters under `label`, for the census to difference. */ export function markTypes(label: String): void { _typeMarks.push(new TypeMark(label, _nextTypeUid - 1, _classTypes, _functionTypes, _interfaceTypes)); } export function typeMarks(): GrowableArray { return _typeMarks; } /** * How many FunctionTypes each of codegen's substitution sites built * (type-mapping.zena numbers them), to say which path makes them. */ var _codegenFunctionSites = new FixedArray(16, 0); export function countCodegenFunctionType(site: i32): void { _codegenFunctionSites[site] = _codegenFunctionSites[site] + 1; } export function codegenFunctionTypeSite(site: i32): i32 { return _codegenFunctionSites[site]; } // How much of codegen's substitution is repeated work: every call, // the calls that hand back their input unchanged, and the distinct // (input, arguments) pairs among them. The distinct count keeps a set // of key strings, so it is only gathered when the census asks. var _censusEnabled = false; var _codegenSubstCalls = 0; var _codegenSubstUnchanged = 0; let _codegenSubstDistinct = new Set(); export function setCensusEnabled(on: boolean): void { _censusEnabled = on; } export function codegenSubstCalls(): i32 { return _codegenSubstCalls; } export function codegenSubstUnchanged(): i32 { return _codegenSubstUnchanged; } export function codegenSubstDistinct(): i32 { return _codegenSubstDistinct.size; } /** Records one top-level codegen substitution of `t` under `args`. */ export function countCodegenSubstitution( t: Type, args: Array, result: Type): void { _codegenSubstCalls += 1; if (result === t) { _codegenSubstUnchanged += 1; } if (!_censusEnabled) { return; } var key = i32ToString(t.uid) + "|"; for (let a in args) { key = `${key}${i32ToString(a.uid)},`; } _codegenSubstDistinct.add(key); } export function instantiationHits(): i32 { return _instantiationHits; } export function instantiationMisses(): i32 { return _instantiationMisses; } export function substitutedNominals(): i32 { return _substitutedNominals; } export function typesCreated(): i32 { return _nextTypeUid - 1; } export function classTypesCreated(): i32 { return _classTypes; } export function functionTypesCreated(): i32 { return _functionTypes; } export function interfaceTypesCreated(): i32 { return _interfaceTypes; } export function mixinTypesCreated(): i32 { return _mixinTypes; } export function typeParameterTypesCreated(): i32 { return _typeParameterTypes; } export function typeKeysCached(): i32 { return _typeKeysCached; } export function typeKeyBytes(): i32 { return _typeKeyBytes; } let _distinctTypeKeys = new Set(); /** * Records one cached type key string. Under the census the distinct * keys are kept too: types with equal keys are structurally the same * type built more than once, so distinct keys against keys cached is * what hash-consing would leave. */ export function countTypeKey(key: String): void { _typeKeysCached += 1; _typeKeyBytes = _typeKeyBytes + key.length; if (_censusEnabled) { _distinctTypeKeys.add(key); } } export function distinctTypeKeys(): i32 { return _distinctTypeKeys.size; } export sealed class Type implements Hashable { var uniqueKeyCache: String | null = null; var specializationKeyCache: String | null = null; /** Process-unique id for identity hashing (type identity is equality). */ uid: i32 = nextTypeUid(); /** * Identity hash. Without this, HashMap/HashSet keyed by Type fall back to a * constant hash and degenerate into linear scans. */ hashCode(): i32 { return this.uid; } /** * Type identity is equality, paired with the uid hash. Declaring it here * keeps the cases from deriving a structural `==` that would disagree with * that hash. */ operator ==(other: Type): boolean { return this === other; } // Numeric primitives case I32Type case U32Type case I64Type case U64Type case F32Type case F64Type // Narrow integer primitives. These are storage widths, not arithmetic // widths: every one is carried in a wasm i32 (unsigned zero-extended, // signed sign-extended) and promotes to its 32-bit counterpart the // moment it takes part in an operation. See // docs/design/arithmetic-conversions.md. case U8Type case U16Type case I8Type case I16Type /** * The WebAssembly SIMD vector, 128 bits with no interpretation of its * own: what the bits mean is chosen by each instruction that reads * them, not by the type. So there is no literal syntax, no arithmetic, * no conversion to or from anything — a `v128` is produced and consumed * by the `zena:simd` intrinsics and otherwise only moves. * * Not a reference type at the wasm level, so it is absent from * `isRefType` and from `isBoxablePrimitive`. That constrains it no * more than it constrains `i32`: nothing converts a primitive to a * reference implicitly, and wasm GC accepts `v128` as a struct field * and array element type, so a generic instantiated at `v128` stores * one directly. */ case V128Type // Other primitives case BooleanType case VoidType case NullType case NeverType case HoleType case ErrorType case UnknownType case AnyRefType case EqRefType case ExternRefType /** * The erasure of a type parameter — CODEGEN-INTERNAL, never produced * by the checker and never written in source. * * It is deliberately NOT `anyref`. A type parameter's erasure and the * real top type are different things that happen to share a wasm * representation: `FixedArray` is a type a program can write * and construct, while `FixedArray` erased is a shape used to give * one funcref signature to a generic function used as a VALUE. While * both spelled `anyref`, the specialization key could not tell them * apart, so an erasure passed `isConcrete` and RTA built classes, * vtables and method bodies for types no value can ever have — see * docs/design/binary-size.md §15. * * Erasure is not a substitute for monomorphization and cannot be one: * `Array` stores an i32 field where `Array` stores a * reference, so the erased form is a different struct, not a * supertype. Anything reaching a value across an erased boundary * boxes it. That is why `isConcrete` is FALSE here — an erasure is * never a specialization — and why lowering an erased body is a * compiler bug rather than a coverage gap. */ case ErasedType // Literal types (narrower than their base type) case BoolLiteralType(value: boolean) case StringLiteralType(value: String) case NumLiteralType(raw: String) // Compound types // // `elementsMutable` maps to Wasm's element `mut`: a mutable-element // array is `(array (mut T))`, an immutable one `(array T)`. The two // are unrelated Wasm types — see docs/design/array-mutability.md. // Until the surface default flips, every checker-built ArrayType has // mutable elements; `array` spells the mutability explicitly. case ArrayType(elementType: Type, elementsMutable: boolean) // `row` is the type parameter bounded by `tuple` that `(T, ...R)` // spreads, standing for elements spliced in at `rowIndex` among // `elementTypes` (docs/design/row-types.md §3.3). Substituting a tuple // for it splices that tuple's elements in. Null, with `rowIndex` 0, // for a tuple type that lists all its elements, which is every tuple // type codegen sees. case TupleType(elementTypes: Array, row: TypeParameterType | null, rowIndex: i32) case InlineTupleType(elementTypes: Array) // `inline? T`: unboxed when the argument for `T` is a tuple and the // argument as it is otherwise, decided per substitution (`inlineOf`). // Until then it stands for `T`. case InlineParamType(param: TypeParameterType) // `inline {x: i32, y: i32}`: a closed record passed as its fields, as a // parameter or `let` (docs/design/inline-parameters.md). Its structure // is the record's, so `unwrapAliases` reads through it; only where a // value is held does it differ. case InlineRecordType(record: RecordType) case UnionType(types: Array) case RecordType, FunctionType, ClassType, InterfaceType case MixinType, TypeParameterType, TypeAliasType, EnumType case SymbolType, ThisType } export class MemberInfo { var type: Type; var isAbstract: boolean; var isStatic: boolean; var isPrivate: boolean; /** * The `SymbolType` id of the symbol that named this member; -1 when the * member is name-keyed. Both symbol spellings set it: a top-level * `symbol sym` reached as `:sym`, and a `static symbol` reached as * `:Owner.sym`. * * The member's key already carries the symbol's identity (`:act_87`, * see `symbolMemberKey` in the checker), so two same-named symbols key * two members and a lookup by the wrong one simply misses. This id is * the same identity in a form an access can compare against directly, * and a member copied into a subtype's table carries it along. * * A symbol-keyed member always has one, so -1 on a `:`-prefixed key * means the declaration failed to resolve and was already reported. */ var symbolTypeId: i32 = -1; new( this.type, this.isAbstract = false, this.isStatic = false, this.isPrivate = false ); } export final class FieldInfo extends MemberInfo { var isMutable: boolean; var hasInitializer: boolean; /** * For a field declared without a type, infers it from the initializer * on first demand, in the declaring module's context (the checker * sets this at registration and clears it once run). A member of an * import cycle can read such a field of a class from another member * before that member's bodies have been checked. */ var pendingInit: (() => Type) | null = null; /** Whether the initializer has been checked, eagerly or on demand. */ var initializerChecked: boolean = false; new( type: Type, this.isMutable = false, isAbstract: boolean = false, isStatic: boolean = false, isPrivate: boolean = false, this.hasInitializer = false ) : super(type, isAbstract, isStatic, isPrivate); } /** * What a method does to the object it is called on. * * Nearly every method borrows its receiver, and says so by declaring nothing. * A release action ends the object's life, so it declares `this: Own` * and may only be reached through the owner. See docs/design/ownership.md * §"Release consumes its receiver". */ export enum ReceiverKind { /** No receiver declared: borrowing, the default. */ Implicit, /** `this: Borrow` — the default, spelled out. */ Borrowing, /** `this: Own` — the method consumes what it is called on. */ Owning, /** Declared, but not a receiver the language admits; already reported. */ Invalid, } export final class MethodInfo extends MemberInfo { // TODO: Move to MemberInfo var isFinal: boolean; /** * The receiver this method declared. Call sites read it to keep a * consuming method out of reach of a borrow, and an override is checked * against the one it inherits — a receiver is part of the signature. */ var receiverKind: ReceiverKind = ReceiverKind.Implicit; /** Whether this method consumes what it is called on. */ consumesReceiver(): boolean { return this.receiverKind == ReceiverKind.Owning; } new( // TODO: Make this FunctionType type: Type, isAbstract: boolean = false, isStatic: boolean = false, isPrivate: boolean = false, this.isFinal = false ) : super(type, isAbstract, isStatic, isPrivate); } /** * Whether a member under `key` stays with the class that declares it: a * private field or method (`#name`), a private accessor's `get##`/`set##` * entries, and a mixin's privates under their scope key (`::#name`). * A subclass never inherits these. */ function isPrivateMemberKey(key: String) { return (key.length > 0 && key.sliceBytes(0, 1) == "#") || key.startsWith("get##") || key.startsWith("set##") || key.contains("::#") || key.contains("::get##") || key.contains("::set##"); } /** * Whether a mixin member under `key` is private to the mixin: a `#name` * field or method, or a private accessor's entries. An application reads * these under the mixin's scope key (`::`), so a host's own * same-named private never aliases them (member-lookup.md §6). */ function isPrivateMixinKey(key: String) { return (key.length > 0 && key.sliceBytes(0, 1) == "#") || key.startsWith("get##") || key.startsWith("set##"); } /** * The scope key a mixin's private fields are namespaced under when it is * composed into another mixin or applied to a class: the declaration's * (`privateScopeKey`), reached through an instantiation's source. */ function composedScopeKey(mixin: MixinType) { return (mixin.genericSource ?? mixin).privateScopeKey ?? (mixin.name + "_This"); } /** * Whether a composed mixin's member under `key` is carried by the * composing mixin under the composed mixin's scope key: its private * (`#name`) fields and methods are; everything else keeps its key. */ function isScopedByComposition(key: String, member: MemberInfo) { return (member is FieldInfo || member is MethodInfo) && key.length > 0 && key.sliceBytes(0, 1) == "#"; } function sameType(a: Type | null, b: Type | null) { if (a == null || b == null) { return a == null && b == null; } return a === b; } /** * The substitution a member table applies to a member it reads through a * generic parent. The checker installs its own (`setMemberTypeSubstitution`) * when it starts, so an inherited member's type is substituted exactly as * the checker substitutes a type anywhere else. Null until then; nothing * reads a table through a parent before the checker runs. */ var memberTypeSubstitution: ((typeParams: Array | null, typeArgs: Array | null, t: Type) => Type) | null = null; export function setMemberTypeSubstitution( substitute: (typeParams: Array | null, typeArgs: Array | null, t: Type) => Type ): void { memberTypeSubstitution = substitute; } /** * A parent's member as a child sees it: the same object when the parent * takes no type arguments and `copyAlways` is false, otherwise a copy * whose type has the parent's type arguments substituted for its * parameters. The copy keeps a symbol-keyed member's symbol identity. */ export function inheritedMember( parent: MemberInfo, typeParams: Array | null, typeArgs: Array | null, copyAlways: boolean ): MemberInfo { let substitutes = if (typeParams != null) typeParams.length > 0 else false; if (!substitutes && !copyAlways) { return parent; } var subType = parent.type; let substitute = memberTypeSubstitution; if (substitute != null) { subType = substitute(typeParams, typeArgs, parent.type); } let copy = match (parent) { case FieldInfo as fi: { new FieldInfo( subType, fi.isMutable, fi.isAbstract, fi.isStatic, fi.isPrivate, fi.hasInitializer ) as MemberInfo } case MethodInfo as mi: { new MethodInfo( subType, mi.isAbstract, mi.isStatic, mi.isPrivate, mi.isFinal ) as MemberInfo } case _: parent }; copy.symbolTypeId = parent.symbolTypeId; return copy; } /** * Bumped by every write to any member table. A table caches what it * reads through its parents (substituted copies, and its key order) * tagged with the epoch, so a write anywhere invalidates every cache. * Tables are written during registration and only read while bodies are * checked, so the caches thrash while a module registers and hold * afterwards. */ var memberTableEpoch = 0; /** * The members of a class, interface or mixin: the ones it declares, * written by the checker at registration, and the ones it inherits, read * by reference at every lookup from the parents its owner names — a * class's `superType` and `appliedMixin`, an interface's `extendsList`. * Nothing inherited is ever copied into a type, so a parent that was an * empty shell when the child registered (an import cycle's back edge, * docs/design/import-cycles.md) is read filled once its own registration * runs. A read through a generic parent substitutes its type arguments * (`inheritedMember`) and is cached per key, so two reads of one member * return one object. * * The surface is `OrderedHashMap`'s: `[]`, `[]=`, `has`, `get`, `keys`, * `size`, `delete`, `clear`, and iteration over entries. Writes go to the * owner's own members. Keys iterate inherited first, in the parents' * order, then own, and an own member that overrides an inherited one * keeps the inherited position — the memory layout order codegen reads * for a class's struct. */ export final class MemberTable with IterableUtils> implements Iterable> { [Iterable.iterator](): Iterator> { let entries = new Array>(); for (let key in this.keys()) { let member = this.lookup(key); if (member != null) { entries.push(new MapEntry(key, member as MemberInfo, null)); } } return entries.[Iterable.iterator](); } /** The type whose members these are. Set by its constructor. */ var owner: Type | null = null; var isStaticTable: boolean = false; #own = new OrderedHashMap(); /** Keys every read reports absent until `unhideAll`; null when none. */ var #hidden: HashSet | null = null; var #inheritedCache: HashMap | null = null; var #keysCache: GrowableArray | null = null; var #cacheEpoch: i32 = -1; var #cacheParent: Type | null = null; var #cacheParentCount: i32 = -1; /** The owner's own members, without its parents'. */ own: OrderedHashMap { get { return this.#own; } } operator [](key: String): MemberInfo { let member = this.lookup(key); if (member == null) { throw new Error("Member not found: " + key); } return member as MemberInfo; } operator []=(key: String, value: MemberInfo): void { this.#own[key] = value; memberTableEpoch += 1; } has(key: String): boolean { return this.lookup(key) != null; } get(key: String): inline (true, MemberInfo) | inline (false, _) { let member = this.lookup(key); if (member != null) { return (true, member as MemberInfo); } return (false, _); } delete(key: String): boolean { memberTableEpoch += 1; return this.#own.delete(key); } clear(): void { this.#own.clear(); memberTableEpoch += 1; } size: i32 { get { return this.keys().length; } } /** * Hides `key`, own or inherited, from every read until `unhideAll`. The * checker hides the fields a field initializer may not read — those * declared after it and those of a superclass — while it checks the * initializer. Hiding does not disturb the table's order. */ hide(key: String): void { let hidden = this.#hidden ?? new Set(); this.#hidden = hidden; hidden.add(key); } unhideAll(): void { this.#hidden = null; } /** Every key, inherited first; the array is the table's, so do not write to it. */ keys(): GrowableArray { this.#validateCache(); var all = this.#keysCache; if (all == null) { let out = new Array(); let seen = new Set(); this.#collectInheritedKeys(out, seen); for (let key in this.#own.keys()) { if (!seen.has(key)) { seen.add(key); out.push(key); } } this.#keysCache = out; all = out; } let hidden = this.#hidden; if (hidden == null) { return all as GrowableArray; } let visible = new Array(); for (let key in all as GrowableArray) { if (!hidden.has(key)) { visible.push(key); } } return visible; } /** The member under `key`, own or inherited, or null. */ lookup(key: String): MemberInfo | null { let hidden = this.#hidden; if (hidden != null && hidden.has(key)) { return null; } if (let (true, member) = this.#own.get(key)) { return member; } return this.#inherited(key); } #inherited(key: String): MemberInfo | null { let owner = this.owner; if (owner == null) { return null; } this.#validateCache(); let cache = this.#inheritedCache as HashMap; if (let (true, cached) = cache.get(key)) { return cached; } var found: MemberInfo | null = null; match (owner) { case ClassType as ct: { found = this.#classInherited(ct, key); } case InterfaceType as it: { found = this.#interfaceInherited(it, key); } case MixinType as mt: { found = this.#composedMember(mt, key); } case _: {} } if (found != null) { cache[key] = found as MemberInfo; } return found; } #classInherited(ct: ClassType, key: String): MemberInfo | null { // A mixin's `This` sees the mixin's own members, composed ones // included, and the members of the interface the mixin is `on`. let self = ct.mixinSelf; if (self != null) { let own = self.memberTable(this.isStaticTable).lookup(key); if (own != null) { return own; } let on = ct.onType; if (!this.isStaticTable && on is InterfaceType && !(key.length > 0 && key.sliceBytes(0, 1) == "#")) { let onMember = (on as InterfaceType).members.lookup(key); if (onMember != null) { return inheritedMember(onMember as MemberInfo, on.typeParameters, on.typeArguments, false); } } } let mixin = ct.appliedMixin; if (mixin != null) { let fromMixin = this.#appliedMixinMember(ct, mixin, key); if (fromMixin != null) { let member = fromMixin as MemberInfo; if (!member.isAbstract) { return member; } // An abstract mixin member yields to a concrete one the base has. let below = this.#superMember(ct, key); if (below != null && !(below as MemberInfo).isAbstract) { return below; } return member; } } return this.#superMember(ct, key); } /** * A composing mixin's member from the mixins it composes, the last * composed winning. A composed mixin's private field or method is * carried under the composed mixin's scope key: privacy is lexical to * the declaring mixin, so the composing mixin's body cannot see it * and applications name the struct field with the inner scope. */ #composedMember(mt: MixinType, key: String): MemberInfo | null { var i = mt.mixins.length - 1; while (i >= 0) { let composed = mt.mixins[i]; let composedTable = composed.memberTable(this.isStaticTable); let prefix = composedScopeKey(composed) + "::"; if (key.startsWith(prefix)) { let inner = key.sliceBytes(prefix.length, key.length); let member = composedTable.lookup(inner); if (member != null && isScopedByComposition(inner, member as MemberInfo)) { return member; } } else { let member = composedTable.lookup(key); if (member != null && !isScopedByComposition(key, member as MemberInfo)) { return member; } } i -= 1; } return null; } #superMember(ct: ClassType, key: String): MemberInfo | null { if (isPrivateMemberKey(key)) { return null; } let parent = ct.superType; if (parent == null) { return null; } let member = parent.memberTable(this.isStaticTable).lookup(key); if (member == null) { return null; } return inheritedMember(member as MemberInfo, parent.typeParameters, parent.typeArguments, false); } /** * The applied mixin's member under `key` as the intermediate class * carries it: a private field or method only under the mixin's scope * key, everything else under its own. A decorator's intermediate * carries them under the decorator's renaming instead. */ #appliedMixinMember(ct: ClassType, mixin: MixinType, key: String): MemberInfo | null { if (ct.decoratorSubjectName != null) { return this.#decoratorMember(ct, mixin, key); } let mixinTable = mixin.memberTable(this.isStaticTable); let scope = mixin.privateScopeKey ?? (mixin.name + "_This"); let prefix = scope + "::"; if (key.startsWith(prefix)) { let inner = key.sliceBytes(prefix.length, key.length); let member = mixinTable.lookup(inner); if (member != null && isPrivateMixinKey(inner) && (member is FieldInfo || member is MethodInfo)) { return member; } return null; } let member = mixinTable.lookup(key); if (member == null) { return null; } if (isPrivateMixinKey(key) && (member is FieldInfo || member is MethodInfo)) { return null; } return member; } /** * A decorator's member as the intermediate of one application carries * it (docs/design/decorators.md): the subject accessor under the * decorated field's name; a `shared` member under the declaration's * scope key, and only from the first application in the host's chain; * any other private member under this application's scope key, which * is the declaration's plus the field's name. Nothing else: a public * member other than the subject accessor was rejected at the * declaration. */ #decoratorMember(ct: ClassType, source: MixinType, key: String): MemberInfo | null { let sourceTable = source.memberTable(this.isStaticTable); let subject = ct.decoratorSubjectName as String; let fieldName = ct.decoratorFieldName as String; if (key == "get#" + fieldName) { return sourceTable.lookup("get#" + subject); } if (key == "set#" + fieldName) { return sourceTable.lookup("set#" + subject); } let shared = source.sharedMembers; let sharedScope = ct.decoratorSharedScopeKey; if (sharedScope != null) { let sharedPrefix = sharedScope + "::"; if (key.startsWith(sharedPrefix)) { if (ct.decoratorSharedPlaced || shared == null) { return null; } let inner = key.sliceBytes(sharedPrefix.length, key.length); if (!shared.has(inner)) { return null; } return sourceTable.lookup(inner); } } let scope = ct.privateScopeKey; if (scope == null) { return null; } let prefix = scope + "::"; if (!key.startsWith(prefix)) { return null; } let inner = key.sliceBytes(prefix.length, key.length); if (!isPrivateMixinKey(inner)) { return null; } if (shared != null && shared.has(inner)) { return null; } return sourceTable.lookup(inner); } /** The key the intermediate of a decorator application carries `key` under, or null. */ #decoratorStoredKey(ct: ClassType, source: MixinType, key: String): String | null { let subject = ct.decoratorSubjectName as String; let fieldName = ct.decoratorFieldName as String; let shared = source.sharedMembers; if (shared != null && shared.has(key)) { if (ct.decoratorSharedPlaced) { return null; } return `${ct.decoratorSharedScopeKey ?? ""}::${key}`; } if (isPrivateMixinKey(key)) { return `${ct.privateScopeKey ?? ""}::${key}`; } if (key == "get#" + subject) { return "get#" + fieldName; } if (key == "set#" + subject) { return "set#" + fieldName; } return null; } #interfaceInherited(it: InterfaceType, key: String): MemberInfo | null { // A later parent's member wins over an earlier one's. var i = it.extendsList.length - 1; while (i >= 0) { let parent = it.extendsList[i]; let member = parent.members.lookup(key); if (member != null) { return inheritedMember(member as MemberInfo, parent.typeParameters, parent.typeArguments, true); } i -= 1; } return null; } #collectInheritedKeys(out: GrowableArray, seen: HashSet): void { let owner = this.owner; if (owner == null) { return; } match (owner) { case ClassType as ct: { let parent = ct.superType; if (parent != null) { for (let key in parent.memberTable(this.isStaticTable).keys()) { if (!isPrivateMemberKey(key) && !seen.has(key)) { seen.add(key); out.push(key); } } } let self = ct.mixinSelf; if (self != null) { let on = ct.onType; if (!this.isStaticTable && on is InterfaceType) { for (let key in (on as InterfaceType).members.keys()) { if (!(key.length > 0 && key.sliceBytes(0, 1) == "#") && !seen.has(key)) { seen.add(key); out.push(key); } } } for (let key in self.memberTable(this.isStaticTable).keys()) { if (!seen.has(key)) { seen.add(key); out.push(key); } } } let mixin = ct.appliedMixin; if (mixin != null) { let mixinTable = mixin.memberTable(this.isStaticTable); let scope = mixin.privateScopeKey ?? (mixin.name + "_This"); for (let key in mixinTable.keys()) { var stored: String | null = key; if (ct.decoratorSubjectName != null) { stored = this.#decoratorStoredKey(ct, mixin, key); } else if (isPrivateMixinKey(key)) { let member = mixinTable.lookup(key); if (member is FieldInfo || member is MethodInfo) { stored = `${scope}::${key}`; } } if (stored != null && !seen.has(stored as String)) { seen.add(stored as String); out.push(stored as String); } } } } case InterfaceType as it: { for (let parent in it.extendsList) { for (let key in parent.members.keys()) { if (!seen.has(key)) { seen.add(key); out.push(key); } } } } case MixinType as mt: { for (let composed in mt.mixins) { let composedTable = composed.memberTable(this.isStaticTable); let scope = composedScopeKey(composed); for (let key in composedTable.keys()) { let member = composedTable.lookup(key); let stored = if (member != null && isScopedByComposition(key, member as MemberInfo)) { `${scope}::${key}` } else { key }; if (!seen.has(stored)) { seen.add(stored); out.push(stored); } } } } case _: {} } } /** * Drops the caches when anything they were built from may have changed: * a write to any table, or the owner's parents (its supertype, whether * it applies a mixin, how many interfaces it extends). */ #validateCache(): void { var parent: Type | null = null; var parentCount = 0; match (this.owner) { case ClassType as ct: { parent = ct.superType; if (ct.appliedMixin != null) { parentCount = parentCount + 1; } if (ct.mixinSelf != null) { parentCount = parentCount + 2; } if (ct.onType is InterfaceType) { parentCount = parentCount + 4; } } case InterfaceType as it: { parentCount = it.extendsList.length; } case MixinType as mt: { parentCount = mt.mixins.length; } case _: {} } if (this.#inheritedCache == null || this.#cacheEpoch != memberTableEpoch || this.#cacheParentCount != parentCount || !sameType(this.#cacheParent, parent)) { this.#inheritedCache = new Map(); this.#keysCache = null; this.#cacheEpoch = memberTableEpoch; this.#cacheParent = parent; this.#cacheParentCount = parentCount; } } } export final class RecordType( properties: HashMap, optionalProperties: HashSet | null, /** * The row variable of `{x: i32, ...R}`: a type parameter bounded by * `record` that stands for the fields beside `properties`, none of * which `properties` names (docs/design/row-types.md §3.1). * Substituting a record for it merges that record's fields in. Null * for a record type that names all its fields, which is every record * type codegen sees. */ row: TypeParameterType | null, /** * `{x: i32, ...}`: an existential record type. Its values have * `properties` and other fields the type does not name, which they * keep (docs/design/row-types.md, Decisions). Never set with `row`. */ isExistential: boolean ) extends Type { isOptional(name: String): boolean { let optionals = this.optionalProperties; return optionals != null && optionals.has(name); } hasOptionalProperties(): boolean { let optionals = this.optionalProperties; return optionals != null && optionals.size > 0; } } /** * What a declaration says about a function beyond its signature: the * parameters' names, symbols, initializers and optionality, and the * `final`/`abstract` modifiers. One per declaration (or per function * type written in source), shared by every instantiation and * substitution of its type: these never change under substitution, * and copying them onto each result was most of what a FunctionType * carried. Immutable. */ export final class FunctionDeclInfo { parameterNames: GrowableArray | null; parameterSymbols: GrowableArray | null; parameterInitializers: GrowableArray | null; optionalParameters: GrowableArray | null; isFinal: boolean; isAbstract: boolean; /** * The declaration's instantiations and substitutions, by the * identities of their parts (`internFunctionType`): memo state, not * a fact about the declaration. */ instances = new TypeListTable(); new( this.parameterNames, this.parameterSymbols = null, this.parameterInitializers = null, this.optionalParameters = null, this.isFinal = false, this.isAbstract = false, ); } /** * The function type with these parts. One that carries declaration * info is shared: the info's trie, walked by the parameters', return * type's, type parameters', arguments' and source's identities, * holds one object per distinct list, so a signature substituted a * thousand times through one declaration is one type, which every * cache keyed by type identity then hits. A type without info — an * anonymous function type — has nothing to share under and is fresh. * Only arguments that have identity of their own share: a record or * tuple argument is a fresh uid each time, as before. */ export function internFunctionType( parameters: Array, returnType: Type, info: FunctionDeclInfo | null, typeParameters: Array | null = null, typeArguments: Array | null = null, genericSource: FunctionType | null = null, overloads: GrowableArray | null = null, ): FunctionType { if (info == null) { return new FunctionType(parameters, returnType, null, typeParameters, typeArguments, genericSource, overloads); } let table = info.instances.begin().addAll(parameters).sep() .add(returnType.uid).sep(); if (typeParameters != null) { for (let tp in typeParameters) { table.add(tp.uid); } } table.sep(); if (typeArguments != null) { table.addAll(typeArguments); } table.sep(); if (genericSource != null) { table.add(genericSource.uid); } let node = table.entry(); let existing = node.value; if (existing != null) { _functionTypeHits += 1; return existing as FunctionType; } let created = new FunctionType(parameters, returnType, info, typeParameters, typeArguments, genericSource, overloads); node.value = created; return created; } /** * A function's signature. The parameters, return type and type * parameters are what the type is; an instantiation records its * arguments and source; and `info` holds what the declaration added, * shared by its instantiations. All of those are fixed at * construction — `withReturnType` and `withTypeParameters` make a * changed copy — and the getters below read through `info`, so a * type without one answers as an anonymous function type. * * Two fields are set after construction. `overloads`: the checker * fills a declaration's list in as it meets the later overloads (a * substitution sets its own, substituted, list when built). The * symbol tag, `functionSymbolId`/`functionSymbolName`: the checker * stamps a function's type with the symbol an identifier resolved it * through, which RTA and lowering use to reach the function; an * instantiation copies the tag its source had when it was made. */ export final class FunctionType extends Type { parameters: Array; returnType: Type; info: FunctionDeclInfo | null; typeParameters: Array | null; typeArguments: Array | null; genericSource: FunctionType | null; var overloads: GrowableArray | null; var functionSymbolId: SymbolId = noSymbolId; var functionSymbolName: String = ""; new( this.parameters, this.returnType, this.info = null, this.typeParameters = null, this.typeArguments = null, this.genericSource = null, this.overloads = null, ) : super(); /** The same signature with another return type (constructors). */ withReturnType(returnType: Type): FunctionType { let copy = new FunctionType(this.parameters, returnType, this.info, this.typeParameters, this.typeArguments, this.genericSource, this.overloads); copy.functionSymbolId = this.functionSymbolId; copy.functionSymbolName = this.functionSymbolName; return copy; } /** The same signature with other type parameters (interface constructors). */ withTypeParameters(typeParameters: Array | null): FunctionType { let copy = new FunctionType(this.parameters, this.returnType, this.info, typeParameters, this.typeArguments, this.genericSource, this.overloads); copy.functionSymbolId = this.functionSymbolId; copy.functionSymbolName = this.functionSymbolName; return copy; } parameterNames: GrowableArray | null { get { let info = this.info; return if (info != null) info.parameterNames else null; } } parameterSymbols: GrowableArray | null { get { let info = this.info; return if (info != null) info.parameterSymbols else null; } } parameterInitializers: GrowableArray | null { get { let info = this.info; return if (info != null) info.parameterInitializers else null; } } optionalParameters: GrowableArray | null { get { let info = this.info; return if (info != null) info.optionalParameters else null; } } isFinal: boolean { get { let info = this.info; return info != null && info.isFinal; } } isAbstract: boolean { get { let info = this.info; return info != null && info.isAbstract; } } } export final class ClassType extends Type { id: TypeId; symbolId: SymbolId; name: String; var typeParameters: Array | null = null; var typeArguments: Array | null = null; var superType: ClassType | null = null; var implementsList: GrowableArray = new Array(); var mixins: GrowableArray = new Array(); var classKey: String | null = null; /** * For the synthetic `This` class of a mixin declaration: the scope * key under which the mixin's private fields are namespaced in * every host class that applies it (shared across applications — * mixin privates are lexical to the mixin declaration). Null for * ordinary classes. */ var privateScopeKey: String | null = null; /** * For the intermediate class a field decorator application creates * (docs/design/decorators.md): the decorator's placeholder name and the * decorated field's name. The body's accessor is written against the * placeholder and registered on the host under the field's name; every * pass that registers that accessor by name applies this rename. Null * on every other class. */ var decoratorSubjectName: String | null = null; var decoratorFieldName: String | null = null; /** * For a decorator application's intermediate: the declaration's own * scope key, under which the decorator's `shared` members live — one * copy per host class, found from any application's body. */ var decoratorSharedScopeKey: String | null = null; /** * For a class with decorated fields: each decorated field by name. The * field has no storage of its own on the class — the decorator's * intermediate holds it under `DecoratedField.storageKey` — so the * passes that would otherwise register or initialize the field consult * this instead. Null when the class decorates nothing. */ var decoratedFields: HashMap | null = null; /** * Declared `resource class` — the class has no unwrapped form, so naming it * bare in a type position is an error. Declares resource-ness, not * affineness: affineness comes from `Own`. See * docs/design/ownership.md §"Resource-ness and affineness are different * properties". */ var isResource: boolean = false; /** * Whether the checker synthesized this class's release member * (releaseMemberOf): the `:dispose` of a resource class that holds * owner fields and wrote no release action of its own, or the * `[release]` of a `scoped T` class that holds `T` in fields and * declared none. Either body is just the fields' release glue. RTA * registers the node-less method from this flag. */ var hasSyntheticRelease: boolean = false; /** * The members of the class (fields, methods, and accessors): its own, * written by the checker during registration, and the ones it inherits, * read by reference through `superType` and `appliedMixin` at every * lookup (MemberTable). Keys iterate in memory layout order: the * superclass's first, then the class's own, and a member the class * overrides or implements keeps the superclass's position. Codegen * reads the table as immutable to emit `WasmStruct`s. */ var members: MemberTable = new MemberTable(); var staticMembers: MemberTable = new MemberTable(); memberTable(isStatic: boolean): MemberTable { return if (isStatic) this.staticMembers else this.members; } /** * For the intermediate class a `with M` application or a field * decorator inserts into the host's chain: the mixin (or decorator) * whose members it carries, read by reference through `members` (see * MemberTable). A decorator's intermediate, told apart by * `decoratorSubjectName`, reads them under the decorator's renaming. * Null for every other class. */ var appliedMixin: MixinType | null = null; /** * For a decorator application's intermediate: whether an earlier * application of the same decorator in the host's chain already * carries the decorator's `shared` members, in which case this one * carries none (they are one copy per host class). */ var decoratorSharedPlaced = false; /** * For the synthetic `This` class a mixin's body is checked against: * the mixin itself, whose members (composed mixins' included) `this` * sees as its own, read by reference through `members`. Null for * every other class. */ var mixinSelf: MixinType | null = null; /** * Always empty: only an interface declares `static symbol`s, and the * checker rejects one written on a class or mixin body. Carried so that * `Owner.sym` resolves against any named owner and answers "declares no * static symbol" rather than "is not a type that has them". */ var staticSymbols: OrderedHashMap = new OrderedHashMap(); var constructorType: FunctionType | null = null; var constructors: HashMap = new Map(); var fieldSetterNames: HashMap | null = null; var isFinal = false; var isCaseClass = false; /** * The checker synthesized this case class's `==` and `hashCode`. False for * a case class that inherits either one from its base, whose pair is then * the hierarchy's equality (equality.md, "Hash keys declare equality"). */ var derivesEquality = false; var isAbstract = false; var isExtension = false; var isSealed = false; var isMixinIntermediate = false; var onType: Type | null = null; var genericSource: ClassType | null = null; var declaredFields: HashSet | null = null; var sealedVariants: GrowableArray | null = null; var forwardVariantNames: HashSet | null = null; /** * On a generic template: its instantiations by argument key, created * by `instantiateClassType` on the first one. Null on every other * class — which is nearly every ClassType object a compile builds, so * an eager table here was 96 bytes of garbage per instantiation. */ var instantiations: HashMap | null = null; /** * The instantiations `substituteInType` has built from this mention * with closed arguments, by argument identity, so a generic class * substituted a thousand times through one signature is * instantiated once per argument list rather than once per * substitution (issue #199: 610K of them in a large build). Null * until the first substitution through this mention. */ var substitutionCache: TypeListTable | null = null; /** * On a cached instantiation: `classShapeStamp` of its source when it * was built. The checker fills a class in phases, and a substitution * before its constructor or supertypes are set must not fix the * instantiation in that state, so a hit whose stamp no longer * matches is rebuilt in place. */ var shapeStamp: i32 = 0; /** The file path where this class was declared (set by the checker). */ var sourcePath: String = ""; // TODO: Implement a "copy constructor" or static `instantiate` method // that takes a generic class to copy. This will allow us to make as many // of these fields immutable as possible instead of reassigning them in // `instantiateClassType`. new(id: TypeId, symbolId: SymbolId, name: String) : id = id, symbolId = symbolId, name = name, super() { _classTypes += 1; this.members.owner = this; this.staticMembers.owner = this; this.staticMembers.isStaticTable = true; } /** * The original declaration this class was instantiated from: * follows genericSource to the root. Specializations of one * generic class compare equal through this; a non-generic class is * its own canonical. */ canonical(): ClassType { var c = this; while (c.genericSource != null) { c = c.genericSource as ClassType; } return c; } } /** * One field decorator application on a host class. * * `storageKey` is the member and struct-field key of the decorator's * storage field (`"::#"`), where `scope` is the * application's private scope key: the decorator declaration's key with * the field's name appended, so two applications of one decorator on one * class keep separate storage. `field` is the decorated declaration on * the host, whose initializer and constructor assignments target the * storage. */ export final class DecoratedField( fieldName: String, scope: String, storageKey: String, decorator: MixinType, field: FieldDefinition, fieldType: Type) /** * A class or interface instantiation substituteInType is in the middle * of building. A type can mention itself — `MapEntry`'s constructor * takes a `MapEntry`, `Iterator`'s methods return * `Iterator` — and substituting through such a mention must hand * back the instantiation already under construction rather than start * another, which would never finish. */ final class SubstitutionFrame(source: Type, key: TypeListEntry, result: Type) let substitutionFrames = new Array(); /** * One list's slot in a TypeListTable: the uids it was filed under, * the value stored for it, and membership bits for the tables that * store only membership. Its identity stands for the list (the * substitution frames compare entries). */ export final class TypeListEntry { key: FixedArray; var value: Type | null = null; var marks: i32 = 0; new(this.key); } /** * A map from a list of types to one value, keyed by the identities * (uids) of the list's members: the table behind everything that * identifies a type by other types — the interner's unions, the * instantiations cached on a generic's template, a declaration's * function types, codegen's substitution memo, RTA's referrers with * type arguments. * * Open addressing over one slot per distinct list. A lookup builds * its probe in the table's own scratch — `begin`, then `add`, `addAll` * and `sep` in the key's order, then `entry` — hashes the uids in * place and compares them against the stored key arrays, so a hit * allocates nothing and a miss allocates the entry and its key once. * `sep` walks a -1 between lists keyed in sequence (uids are never * negative), so lists of different lengths cannot alias. The probe * must be completed by `entry` before the table is probed again: the * callers build and look up back to back. * * This replaced a trie of hash maps, which cost about one node and * one map entry per element of every distinct list — 190 MB and 4% of * a large compile's allocation, and n map lookups per probe. */ export final class TypeListTable { var #slots: FixedArray; var #mask: i32; var #count: i32 = 0; var #limit: i32; #probe = new Array(8); new(capacity: i32 = 8) : #slots = new FixedArray(tablePow2(capacity), null), #mask = tablePow2(capacity) - 1, #limit = (tablePow2(capacity) >>> 2) * 3; /** Starts a probe. */ begin(): TypeListTable { this.#probe.clear(); return this; } add(uid: i32): TypeListTable { this.#probe.push(uid); return this; } addAll(types: Array): TypeListTable { for (let t in types) { this.#probe.push(t.uid); } return this; } /** A separator between lists keyed in sequence. */ sep(): TypeListTable { this.#probe.push(-1); return this; } /** The entry for `types` alone: `begin().addAll(types).entry()`. */ at(types: Array): TypeListEntry { return this.begin().addAll(types).entry(); } /** The entry for the probe built since `begin`, made if absent. */ entry(): TypeListEntry { let probe = this.#probe; let n = probe.length; var h = 0x811c9dc5; var i = 0; while (i < n) { h = (h ^ probe[i]) * 16777619; i += 1; } h = h ^ (h >>> 15); var slot = h & this.#mask; while (true) { let existing = this.#slots[slot]; if (existing == null) { break; } if (keyEquals(existing.key, probe)) { return existing; } slot = (slot + 1) & this.#mask; } let key = new FixedArray(n, 0); i = 0; while (i < n) { key[i] = probe[i]; i += 1; } let created = new TypeListEntry(key); this.#slots[slot] = created; this.#count += 1; if (this.#count > this.#limit) { this.#grow(); } return created; } #grow(): void { let old = this.#slots; let size = old.length * 2; this.#slots = new FixedArray(size, null); this.#mask = size - 1; this.#limit = (size >>> 2) * 3; for (let e in old) { if (e != null) { this.#place(e); } } } #place(e: TypeListEntry): void { let key = e.key; var h = 0x811c9dc5; for (let uid in key) { h = (h ^ uid) * 16777619; } h = h ^ (h >>> 15); var slot = h & this.#mask; while (this.#slots[slot] != null) { slot = (slot + 1) & this.#mask; } this.#slots[slot] = e; } } function keyEquals(key: FixedArray, probe: GrowableArray): boolean { if (key.length != probe.length) { return false; } var i = 0; while (i < key.length) { if (key[i] != probe[i]) { return false; } i += 1; } return true; } function tablePow2(n: i32): i32 { var size = 8; while (size < n) { size = size * 2; } return size; } // The one object per field-less primitive kind that an interned // union's members are replaced with. Every site that writes `T | null` // builds its own `NullType`, so without this no two `T | null` keys // could ever match. Process-wide, which is sound: a primitive has no // fields and belongs to no compiler. let nullSingleton = new NullType(); let i32Singleton = new I32Type(); let u32Singleton = new U32Type(); let i64Singleton = new I64Type(); let u64Singleton = new U64Type(); let f32Singleton = new F32Type(); let f64Singleton = new F64Type(); let u8Singleton = new U8Type(); let u16Singleton = new U16Type(); let i8Singleton = new I8Type(); let i16Singleton = new I16Type(); let v128Singleton = new V128Type(); let booleanSingleton = new BooleanType(); let voidSingleton = new VoidType(); let neverSingleton = new NeverType(); let anyRefSingleton = new AnyRefType(); let eqRefSingleton = new EqRefType(); let externRefSingleton = new ExternRefType(); /** The singleton for a field-less primitive, or null for any other type. */ function primitiveSingleton(t: Type): Type | null { return match (t) { case NullType: nullSingleton case I32Type: i32Singleton case U32Type: u32Singleton case I64Type: i64Singleton case U64Type: u64Singleton case F32Type: f32Singleton case F64Type: f64Singleton case U8Type: u8Singleton case U16Type: u16Singleton case I8Type: i8Singleton case I16Type: i16Singleton case V128Type: v128Singleton case BooleanType: booleanSingleton case VoidType: voidSingleton case NeverType: neverSingleton case AnyRefType: anyRefSingleton case EqRefType: eqRefSingleton case ExternRefType: externRefSingleton case _: null }; } /** * Whether `t`'s identity is stable enough to key an interned union on: * a primitive (canonicalized above), a type parameter, a declared class * or interface or a canonical instantiation of one (the substitution * caches key those on the template and the arguments' identities and * mark them with a shape stamp), or such a union. A substitution copy * is not — it is one of many equal copies, and a union interned over * it would pin the copy, and everything the copy references, for the * compile without ever matching another copy's union. */ function internableMember(t: Type): boolean { return match (t) { case TypeParameterType: true case ClassType as ct: (ct.typeArguments == null && ct.genericSource == null) || ct.shapeStamp != 0 case InterfaceType as it: (it.typeArguments == null && it.genericSource == null) || it.shapeStamp != 0 case UnionType {types}: { var all = true; for (let m in types) { if (primitiveSingleton(m) == null && !internableMember(m)) { all = false; } } all } case _: primitiveSingleton(t) != null }; } // Census counters for union interning, over the process. var _unionHits = 0; var _unionMisses = 0; var _unionFresh = 0; // Why a union was built fresh: the kind of its first uninternable // member (class instance, interface instance, function, array, tuple, // record, alias, union, other). var _unionFreshByKind = new FixedArray(9, 0); export function unionInternHits(): i32 { return _unionHits; } export function unionInternMisses(): i32 { return _unionMisses; } export function unionInternFresh(): i32 { return _unionFresh; } export function unionFreshByKind(kind: i32): i32 { return _unionFreshByKind[kind]; } /** * The interned types of one compiler. * * A union is a value: equal member lists are equal types (`typesEqual` * compares members in order), and nothing changes a union's members * after construction, so one object per member list can serve every * site that would build it — `T | null` for one `T` is built once * rather than at every mention and every substitution — and the * identity-keyed caches downstream (`substCache`, `substitutionsFor`) * hit where they used to miss on a fresh copy. * * `SharedCheckerState` owns one, and the generator hands the same one * to the compile's `WasmModule`, so a compile's unions share identity * across checking and codegen. Two compilers in one process never see * each other's: there is no process-wide table to reset, and nothing * for an interleaved compile to pull out from under another. */ export final class TypeInterner { #unions = new TypeListTable(); /** * The union of `members`, in order: the interned object for that list * when every member can be keyed on, else a fresh union, as before. */ union(members: Array): UnionType { var canonical: GrowableArray | null = null; var i = 0; for (let m in members) { let single = primitiveSingleton(m); if (single == null && !internableMember(m)) { _unionFresh += 1; let kind = match (m) { case ClassType: 0 case InterfaceType: 1 case FunctionType: 2 case ArrayType: 3 case TupleType: 4 case InlineTupleType: 4 case RecordType: 5 case TypeAliasType: 6 case UnionType: 7 case _: 8 }; _unionFreshByKind[kind] = _unionFreshByKind[kind] + 1; return new UnionType(toGrowable(members)); } if (single != null && single !== m) { let copy = canonical ?? GrowableArray.from(members); copy[i] = single; canonical = copy; } i += 1; } let keyed = canonical ?? members; let node = this.#unions.at(keyed); let existing = node.value; if (existing != null) { _unionHits += 1; return existing as UnionType; } _unionMisses += 1; let created = new UnionType(toGrowable(keyed)); node.value = created; return created; } } /** * A number that changes whenever any input of `substituteInType`'s * class instantiation other than the arguments does: the supertype, * mixins and interfaces, the constructors, the `on` type, and the * flags it copies. Members are shared by reference and need no stamp. */ export function classShapeStamp(ct: ClassType): i32 { var stamp = ct.implementsList.length * 7 + ct.mixins.length * 13 + ct.constructors.size * 17; let sup = ct.superType; if (sup != null) { stamp = stamp * 31 + sup.uid; } let ctor = ct.constructorType; if (ctor != null) { stamp = stamp * 31 + ctor.uid; } let on = ct.onType; if (on != null) { stamp = stamp * 31 + on.uid; } for (let impl in ct.implementsList) { stamp = stamp * 31 + impl.uid; } for (let m in ct.mixins) { stamp = stamp * 31 + m.uid; } var flags = 0; if (ct.isFinal) { flags = flags | 1; } if (ct.isCaseClass) { flags = flags | 2; } if (ct.isResource) { flags = flags | 4; } if (ct.hasSyntheticRelease) { flags = flags | 8; } if (ct.isAbstract) { flags = flags | 16; } if (ct.isExtension) { flags = flags | 32; } if (ct.isSealed) { flags = flags | 64; } if (ct.isMixinIntermediate) { flags = flags | 128; } return stamp * 256 + flags + 1; } /** As `classShapeStamp`, for an interface: its extends list. */ export function interfaceShapeStamp(it: InterfaceType): i32 { var stamp = it.extendsList.length; for (let ext in it.extendsList) { stamp = stamp * 31 + ext.uid; } return stamp + 1; } function reentrantSubstitution(source: Type, key: TypeListEntry): Type | null { for (let frame in substitutionFrames) { if (frame.source === source && frame.key === key) { return frame.result; } } return null; } /** * `{...fields, ...R}` once R is `row`: a record type merges its fields in * and passes on its own row variable, and another row parameter replaces * R. An error row (an argument the checker rejected) makes the whole type * an error, so nothing downstream reports it again; anything else leaves * the named fields alone. The checker rejects a row that names one of * `fields` (`rowLacks`), so on a collision the field written beside the * spread is kept. */ export function mergeRow( fields: HashMap, optionals: HashSet | null, row: Type ): Type { match (row) { case RecordType as r: { let props = new Map(); var opts: HashSet | null = null; for (let key in r.properties.keys()) { props[key] = r.properties[key]; if (r.isOptional(key)) { opts ??= new Set(); opts.add(key); } } for (let key in fields.keys()) { props[key] = fields[key]; if (optionals != null && optionals.has(key)) { opts ??= new Set(); opts.add(key); } else if (opts != null) { opts.delete(key); } } return new RecordType(props, opts, r.row, false); } case TypeParameterType as tp: { return new RecordType(fields, optionals, tp, false); } case ErrorType: { return row; } case _: { return new RecordType(fields, optionals, null, false); } } } /** * `(...before, ...R, ...after)` once R is `row`, where `elements` holds * `before` and `after` and `rowIndex` is where R sits: a tuple type * splices its elements in there and passes on its own row, another row * parameter replaces R, an error row makes the whole type an error (as * in `mergeRow`), and anything else leaves the listed elements alone. */ export function mergeTupleRow( elements: Array, rowIndex: i32, row: Type ): Type { match (row) { case TupleType as r: { let out = new Array(); for (var i = 0; i < rowIndex; i += 1) { out.push(elements[i]); } for (let element in r.elementTypes) { out.push(element); } for (var i = rowIndex; i < elements.length; i += 1) { out.push(elements[i]); } let inner = r.row; if (inner != null) { return new TupleType(out, inner, rowIndex + r.rowIndex); } return new TupleType(out, null, 0); } case TypeParameterType as tp: { return new TupleType(elements, tp, rowIndex); } case ErrorType: { return row; } case _: { return new TupleType(elements, null, 0); } } } /** * `inline` applied to what a type parameter stands for: a tuple that * lists its elements is unboxed, another type parameter keeps the * modifier for a later substitution, and anything else is itself. */ export function inlineOf(t: Type): Type { return match (t) { case TypeParameterType as tp: new InlineParamType(tp) as Type case TupleType {elementTypes, row}: if (row == null) new InlineTupleType(elementTypes) as Type else t case TypeAliasType as alias: { // Through aliases that are only names (`type Pair = (A, B)`). if (alias.isDistinct || alias.intrinsicName != null || alias.resolving) { t } else { let target = inlineOf(alias.target); if (target is InlineTupleType) target else t } } case _: t }; } function substituteInType( t: Type | null, typeParameters: Array | null, typeArguments: Array ): Type | null { if (t == null) return null; return match (t) { case TypeParameterType as tp: { var found: Type | null = null; if (typeParameters != null) { for (var i = 0; i < typeParameters.length; i += 1) { if (typeParameters[i] === tp && i < typeArguments.length) { found = typeArguments[i]; break; } } } if (found != null) { found } else { tp } } case ArrayType {elementType, elementsMutable}: { let subElem = substituteInType(elementType, typeParameters, typeArguments); if (subElem != null) { new ArrayType(subElem, elementsMutable) } else { t } } case TupleType {elementTypes, row, rowIndex}: { let newElems = new Array(); for (let el in elementTypes) { let sub = substituteInType(el, typeParameters, typeArguments); newElems.push((sub ?? el)); } if (row != null) { mergeTupleRow(newElems, rowIndex, substituteInType(row, typeParameters, typeArguments) ?? row) } else { new TupleType(newElems, null, 0) } } case InlineTupleType {elementTypes}: { let newElems = new Array(); for (let el in elementTypes) { let sub = substituteInType(el, typeParameters, typeArguments); newElems.push((sub ?? el)); } new InlineTupleType(newElems) } case InlineParamType {param}: inlineOf(substituteInType(param, typeParameters, typeArguments) ?? param) case InlineRecordType {record}: { let sub = substituteInType(record, typeParameters, typeArguments); if (sub is RecordType) new InlineRecordType(sub) as Type else t } case UnionType {types}: { let newTypes = new Array(); for (let ut in types) { let sub = substituteInType(ut, typeParameters, typeArguments); newTypes.push((sub ?? ut)); } new UnionType(toGrowable(newTypes)) } case RecordType as rec: { let newProps = new Map(); let keys = rec.properties.keys(); for (let key in keys) { let sub = substituteInType(rec.properties[key], typeParameters, typeArguments); newProps[key] = (sub ?? rec.properties[key]); } let row = rec.row; if (row != null) { mergeRow(newProps, rec.optionalProperties, substituteInType(row, typeParameters, typeArguments) ?? row) } else { new RecordType(newProps, rec.optionalProperties, null, rec.isExistential) } } case FunctionType as ft: { let newParams = new Array(); for (let p in ft.parameters) { let sub = substituteInType(p, typeParameters, typeArguments); newParams.push((sub ?? p)); } let newRet = substituteInType(ft.returnType, typeParameters, typeArguments); let newFt = internFunctionType(newParams, (newRet ?? ft.returnType), ft.info, ft.typeParameters, ft.typeArguments, ft.genericSource, ft.overloads); newFt.functionSymbolId = ft.functionSymbolId; newFt.functionSymbolName = ft.functionSymbolName; countCodegenFunctionType(5); newFt } case ClassType as ct: { var hasArgs = false; let ctArgsVal = new Array(); let ctParams = (ct.genericSource ?? ct).typeParameters; if (ct.typeArguments != null) { hasArgs = true; let targs = ct.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { ctArgsVal.push(targs[i]); i += 1; } } else if (typeParameters != null && ctParams != null) { hasArgs = true; var i = 0; let len = ctParams.length; while (i < len) { ctArgsVal.push(ctParams[i] as Type); i += 1; } } if (hasArgs && ctArgsVal.length > 0) { let newArgs = new Array(ctArgsVal.length); for (let arg in ctArgsVal) { let sub = substituteInType(arg, typeParameters, typeArguments); newArgs.push((sub ?? arg)); } // One instantiation per (class, arguments) for the compile: // cached on the class's template, keyed by the arguments' // identities, and built from the template, so a copy is never // made from another copy. An instance's supertypes are the // template's with the instance's arguments folded in, so the // result is the same whichever mention asked for it. // // The template's own constructor may name the class — the // checker resolves `MapEntry` inside `MapEntry` to a // self-instantiation made before the constructor was // registered, with no constructor of its own — so an // instantiation built from the template has a constructor // parameter that is the instantiation itself. The substitution // frames answer the re-entrant mention here, and codegen's // substitution registers before it recurses, so both walk the // cycle. The stamp catches a template that gained a // constructor or supertype since the instantiation was built. let template = ct.canonical(); let cache = template.substitutionCache ?? new TypeListTable(); template.substitutionCache = cache; let frameKey = cache.at(newArgs); let reentrant = reentrantSubstitution(template as Type, frameKey); if (reentrant != null) { return reentrant; } let stamp = classShapeStamp(template); var hit: ClassType | null = null; let cached = frameKey.value; if (cached != null) { hit = cached as ClassType; } if (hit != null && (hit as ClassType).shapeStamp == stamp) { _substitutionCacheHits += 1; return hit; } let inst = if (hit != null) { // The template changed shape since this was built: rebuild // in place, so everything holding it sees the new shape. let stale = hit as ClassType; stale.implementsList = new Array(); stale.mixins = new Array(); stale } else { let fresh = new ClassType(template.id, template.symbolId, template.name); frameKey.value = fresh; fresh }; _substitutedNominals += 1; inst.typeParameters = ctParams; inst.typeArguments = newArgs; inst.genericSource = template; inst.shapeStamp = stamp; substitutionFrames.push(new SubstitutionFrame(template as Type, frameKey, inst as Type)); let combinedParams = new Array(); let combinedArgs = new Array(); if (ctParams != null) { for (let p in ctParams) { combinedParams.push(p); } for (let a in newArgs) { combinedArgs.push(a); } } if (typeParameters != null) { for (let p in typeParameters) { combinedParams.push(p); } for (let a in typeArguments) { combinedArgs.push(a); } } if (template.superType != null) { let subSuper = substituteInType(template.superType, combinedParams, combinedArgs); inst.superType = (subSuper ?? template.superType) as ClassType; } for (let impl in template.implementsList) { let subImpl = substituteInType(impl, combinedParams, combinedArgs); inst.implementsList.push((subImpl ?? impl) as InterfaceType); } for (let m in template.mixins) { let subM = substituteInType(m, combinedParams, combinedArgs); inst.mixins.push((subM ?? m) as MixinType); } inst.constructorType = if (template.constructorType != null) { let ctor = template.constructorType as FunctionType; let newParams = new Array(); for (let p in ctor.parameters) { let sub = substituteInType(p, combinedParams, combinedArgs); newParams.push((sub ?? p)); } let newFt = internFunctionType(newParams, ctor.returnType, ctor.info); newFt.functionSymbolId = ctor.functionSymbolId; newFt.functionSymbolName = ctor.functionSymbolName; newFt } else { null }; inst.constructors = new Map(); for (let entry in template.constructors) { let ctorName = entry.key; let ctor = entry.value; let newParams = new Array(); for (let p in ctor.parameters) { let sub = substituteInType(p, combinedParams, combinedArgs); newParams.push((sub ?? p)); } let newFt = internFunctionType(newParams, ctor.returnType, ctor.info); newFt.functionSymbolId = ctor.functionSymbolId; newFt.functionSymbolName = ctor.functionSymbolName; inst.constructors[ctorName] = newFt; } inst.fieldSetterNames = template.fieldSetterNames; inst.isFinal = template.isFinal; inst.isCaseClass = template.isCaseClass; inst.derivesEquality = template.derivesEquality; // Resource-ness is a property of the class, uniform across every // mention of it (ownership.md §"Resource-ness and affineness are // separate"), so an instantiation of a generic resource class is // still a resource class. Codegen keys the hidden lifecycle field // off this flag, and an instantiation that dropped it would get // no field and silently skip disown/adopt's state check. inst.isResource = template.isResource; inst.hasSyntheticRelease = template.hasSyntheticRelease; inst.isAbstract = template.isAbstract; inst.isExtension = template.isExtension; inst.isSealed = template.isSealed; inst.isMixinIntermediate = template.isMixinIntermediate; inst.privateScopeKey = template.privateScopeKey; inst.decoratorSubjectName = template.decoratorSubjectName; inst.decoratorFieldName = template.decoratorFieldName; inst.decoratorSharedScopeKey = template.decoratorSharedScopeKey; inst.decoratedFields = template.decoratedFields; inst.sealedVariants = template.sealedVariants; inst.declaredFields = template.declaredFields; inst.forwardVariantNames = template.forwardVariantNames; inst.members = template.members; inst.staticMembers = template.staticMembers; inst.staticSymbols = template.staticSymbols; if (template.onType != null) { inst.onType = substituteInType(template.onType, combinedParams, combinedArgs); } inst.sourcePath = template.sourcePath; substitutionFrames.pop(); inst } else { ct } } case InterfaceType as it: { var hasArgs = false; let itArgsVal = new Array(); let itParams = (it.genericSource ?? it).typeParameters; if (it.typeArguments != null) { hasArgs = true; let targs = it.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { itArgsVal.push(targs[i]); i += 1; } } else if (typeParameters != null && itParams != null) { hasArgs = true; var i = 0; let len = itParams.length; while (i < len) { itArgsVal.push(itParams[i] as Type); i += 1; } } if (hasArgs && itArgsVal.length > 0) { let newArgs = new Array(); for (let arg in itArgsVal) { let sub = substituteInType(arg, typeParameters, typeArguments); newArgs.push((sub ?? arg)); } // One instantiation per (interface, arguments), on the // template; see the class case. var template = it; while (template.genericSource != null) { template = template.genericSource as InterfaceType; } let cache = template.substitutionCache ?? new TypeListTable(); template.substitutionCache = cache; let frameKey = cache.at(newArgs); let reentrant = reentrantSubstitution(template as Type, frameKey); if (reentrant != null) { return reentrant; } let stamp = interfaceShapeStamp(template); var hit: InterfaceType | null = null; let cached = frameKey.value; if (cached != null) { hit = cached as InterfaceType; } if (hit != null && (hit as InterfaceType).shapeStamp == stamp) { _substitutionCacheHits += 1; return hit; } let inst = if (hit != null) { hit as InterfaceType } else { let fresh = new InterfaceType(template.id, template.symbolId, template.name); frameKey.value = fresh; fresh }; _substitutedNominals += 1; inst.typeParameters = itParams; inst.typeArguments = newArgs; inst.genericSource = template; inst.shapeStamp = stamp; substitutionFrames.push(new SubstitutionFrame(template as Type, frameKey, inst as Type)); let combinedParams = new Array(); let combinedArgs = new Array(); if (itParams != null) { for (let p in itParams) { combinedParams.push(p); } for (let a in newArgs) { combinedArgs.push(a); } } if (typeParameters != null) { for (let p in typeParameters) { combinedParams.push(p); } for (let a in typeArguments) { combinedArgs.push(a); } } let newExtends = new Array(); for (let ext in template.extendsList) { let subExt = substituteInType(ext, combinedParams, combinedArgs); newExtends.push((subExt ?? ext) as InterfaceType); } inst.extendsList = newExtends; inst.members = template.members; inst.staticSymbols = template.staticSymbols; inst.constructors = template.constructors; inst.sourcePath = template.sourcePath; substitutionFrames.pop(); inst } else { it } } case TypeAliasType as alias: { var hasArgs = false; let aliasArgsVal = new Array(); let aliasParams = alias.typeParameters; if (alias.typeArguments != null) { hasArgs = true; let targs = alias.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { aliasArgsVal.push(targs[i]); i += 1; } } else if (typeParameters != null && aliasParams != null) { hasArgs = true; var i = 0; let len = aliasParams.length; while (i < len) { aliasArgsVal.push(aliasParams[i] as Type); i += 1; } } if (hasArgs && aliasArgsVal.length > 0) { let newArgs = new Array(); for (let arg in aliasArgsVal) { let sub = substituteInType(arg, typeParameters, typeArguments); newArgs.push((sub ?? arg)); } let inst = new TypeAliasType( alias.name, alias.typeParameters, alias.target, alias.isDistinct, newArgs, alias.isOpaque, alias.declaringModule ); inst.intrinsicName = alias.intrinsicName; // A substitution that closes an intrinsic alias's argument // normalizes the alias away; applyTypeIntrinsic is a no-op // for ordinary aliases and while the argument is still open. if (inst.intrinsicName != null) { applyTypeIntrinsic(inst) } else { inst } } else { alias } } case MixinType as mt: { var hasArgs = false; let mtArgsVal = new Array(); let mtParams = mt.typeParameters; if (mt.typeArguments != null) { hasArgs = true; let targs = mt.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { mtArgsVal.push(targs[i]); i += 1; } } else if (typeParameters != null && mtParams != null) { hasArgs = true; var i = 0; let len = mtParams.length; while (i < len) { mtArgsVal.push(mtParams[i] as Type); i += 1; } } if (hasArgs && mtArgsVal.length > 0) { let newArgs = new Array(); for (let arg in mtArgsVal) { let sub = substituteInType(arg, typeParameters, typeArguments); newArgs.push((sub ?? arg)); } let inst = new MixinType(mt.name); inst.typeParameters = mtParams; inst.typeArguments = newArgs; inst.genericSource = mt.genericSource ?? mt; inst.onType = mt.onType; inst.members = mt.members; inst.staticMembers = mt.staticMembers; inst.staticSymbols = mt.staticSymbols; inst.sourcePath = mt.sourcePath; inst } else { mt } } case _: t }; } /** * Identity suffix for a nominal type, so that two same-named * declarations never share a cache entry. Mirrors codegen's * `getTypeKeyForSpecialization`: the declaring Symbol when there is * one, else the TypeId. Both are copied onto every instantiation and * substitution copy, so `Foo` keys the same however it was * reached — unlike `Type.uid`, which is fresh per object. */ function nominalIdentity(name: String, symbolId: SymbolId, typeId: TypeId) { return if (symbolId != noSymbolId) { `${name}#s${i32ToString(symbolId as i32)}` } else { `${name}#t${i32ToString(typeId as i32)}` }; } /** * Cache key for one type argument. A type parameter keys by identity * (name plus the base Type uid) at any nesting depth: same-named * parameters of different declarations are different parameters and * must not share a cached instantiation. This matters doubly because * instantiate* re-assigns the cached object's fields on every call, so * a key collision would not just return the wrong object, it would * mutate the shared one. * * Nominal types key by identity for the same reason, and it is not * hypothetical: the `instantiations` cache hangs off the generic * source, and a generic source in the stdlib outlives any one entry * point. Keying `class Item` as `"Item"` let two entry points sharing * one `Compiler` collide on `Iterable`'s cache — the second got the * first's `Iterable` object, complete with the `interfaceKey` * codegen had already cached on it, and emitted an interface * trampoline that downcast its receiver to the wrong struct. * * Composite arms mirror typeToString and recurse; anything that cannot * embed a type parameter falls through to typeToString. */ function instantiationKeyOf(t: Type): String { return match (t) { case TypeParameterType as tp: `${tp.name}#${i32ToString(tp.uid)}` case InlineParamType {param}: `inline ${instantiationKeyOf(param)}` case InlineRecordType {record}: `inline ${instantiationKeyOf(record)}` case ArrayType {elementType, elementsMutable}: `${if (elementsMutable) "Array<" else "Array` case TupleType {elementTypes, row, rowIndex}: { var s = "["; var first = true; var i = 0; for (let elem in elementTypes) { if (row != null && i == rowIndex) { if (!first) { s = s + ","; } first = false; s = `${s}...${instantiationKeyOf(row)}`; } if (!first) { s = s + ","; } first = false; s = s + instantiationKeyOf(elem); i += 1; } if (row != null && rowIndex == elementTypes.length) { if (!first) { s = s + ","; } s = `${s}...${instantiationKeyOf(row)}`; } s + "]" } case InlineTupleType {elementTypes}: { var s = "("; var first = true; for (let elem in elementTypes) { if (!first) { s = s + ","; } first = false; s = s + instantiationKeyOf(elem); } s + ")" } case UnionType {types}: { var s = ""; var first = true; for (let member in types) { if (!first) { s = s + "|"; } first = false; s = s + instantiationKeyOf(member); } s } case RecordType as rec: { var s = "{"; var first = true; for (let key in rec.properties.keys()) { if (!first) { s = s + ","; } first = false; s = `${s}${key}:${instantiationKeyOf(rec.properties[key])}`; } let row = rec.row; if (row != null) { if (!first) { s = s + ","; } s = `${s}...${instantiationKeyOf(row)}`; } else if (rec.isExistential) { if (!first) { s = s + ","; } s = `${s}...`; } s + "}" } case FunctionType as ft: { var s = "("; var first = true; for (let param in ft.parameters) { if (!first) { s = s + ","; } first = false; s = s + instantiationKeyOf(param); } `${s})=>${instantiationKeyOf(ft.returnType)}` } case ClassType as ct: { let src = ct.genericSource ?? ct; let base = nominalIdentity(ct.name, src.symbolId, src.id); if (ct.typeArguments != null) { namedKey(base, ct.typeArguments as Array) } else { base } } case InterfaceType as it: { let src = it.genericSource ?? it; let base = nominalIdentity(it.name, src.symbolId, src.id); if (it.typeArguments != null) { namedKey(base, it.typeArguments as Array) } else { base } } case MixinType as mt: { // MixinType carries no Symbol or TypeId; `sourcePath` plus the name // is what `getMixinKey` already treats as a mixin's identity. let src = mt.genericSource ?? mt; let base = `${mt.name}#m${src.sourcePath}`; if (mt.typeArguments != null) { namedKey(base, mt.typeArguments as Array) } else { base } } case EnumType as et: `${et.name}#e${et.declaringModule}` case TypeAliasType as ta: { // Aliases have no generic source to normalise through, so key by // the declaring module — two aliases of one name cannot share it. let base = `${ta.name}#a${ta.declaringModule}`; if (ta.typeArguments != null) { namedKey(base, ta.typeArguments as Array) } else { base } } case _: typeToString(t) }; } /** `Name` for a generic nominal type's cache key. */ function namedKey(name: String, args: Array): String { var s = name + "<"; var i = 0; let len = args.length; while (i < len) { if (i > 0) { s = s + ","; } s = s + instantiationKeyOf(args[i]); i += 1; } return s + ">"; } function toGrowable(arr: Array): Array { if (arr is GrowableArray) { return arr as GrowableArray; } let g = new Array(arr.length); var i = 0; let len = arr.length; while (i < len) { g.push(arr[i]); i += 1; } return g; } function getInstantiationKey(typeArguments: Array) { var sb = ""; var i = 0; let len = typeArguments.length; while (i < len) { if (i > 0) { sb = sb + ","; } sb = sb + instantiationKeyOf(typeArguments[i]); i += 1; } return sb; } /** * Create an instantiated copy of a generic ClassType with concrete type arguments. * This is a factory function that properly initializes all fields from the source. */ export function instantiateClassType( source: ClassType, typeArguments: Array, ): ClassType { let key = getInstantiationKey(typeArguments); let instantiations = source.instantiations ?? new Map(); source.instantiations = instantiations; // A hit built from the source as it stands is returned as is; one // built before the source gained a constructor or supertype (the // stamp differs) is rebuilt in place below, as substituteInType does. let stamp = classShapeStamp(source); let result = if (let (true, cached) = instantiations.get(key)) { _instantiationHits += 1; if (cached.shapeStamp == stamp) { return cached; } cached } else { _instantiationMisses += 1; let res = new ClassType(source.id, source.symbolId, source.name); instantiations[key] = res; res }; result.shapeStamp = stamp; result.typeParameters = source.typeParameters; result.typeArguments = toGrowable(typeArguments); result.genericSource = source; result.superType = if (source.superType != null) { let subSuper = substituteInType(source.superType as Type, source.typeParameters, typeArguments); (subSuper ?? source.superType) as ClassType } else { null }; // Copy and substitute implementsList entries result.implementsList = new Array(); var i = 0; while (i < source.implementsList.length) { let subImpl = substituteInType(source.implementsList[i] as Type, source.typeParameters, typeArguments); result.implementsList.push((subImpl ?? source.implementsList[i]) as InterfaceType); i += 1; } // Copy and substitute mixins list result.mixins = new Array(); for (let m in source.mixins) { let subM = substituteInType(m, source.typeParameters, typeArguments); result.mixins.push((subM ?? m) as MixinType); } result.members = source.members; result.staticMembers = source.staticMembers; result.staticSymbols = source.staticSymbols; result.constructorType = if (source.constructorType != null) { let ctor = source.constructorType as FunctionType; let newParams = new Array(); for (let p in ctor.parameters) { let sub = substituteInType(p, source.typeParameters, typeArguments); newParams.push((sub ?? p)); } let newFt = internFunctionType(newParams, ctor.returnType, ctor.info); newFt.functionSymbolId = ctor.functionSymbolId; newFt.functionSymbolName = ctor.functionSymbolName; newFt } else { null }; result.constructors = new Map(); for (let entry in source.constructors) { let ctorName = entry.key; let ctor = entry.value; let newParams = new Array(); for (let p in ctor.parameters) { let sub = substituteInType(p, source.typeParameters, typeArguments); newParams.push((sub ?? p)); } let newFt = internFunctionType(newParams, ctor.returnType, ctor.info); newFt.functionSymbolId = ctor.functionSymbolId; newFt.functionSymbolName = ctor.functionSymbolName; result.constructors[ctorName] = newFt; } result.fieldSetterNames = source.fieldSetterNames; result.isFinal = source.isFinal; result.isCaseClass = source.isCaseClass; result.derivesEquality = source.derivesEquality; // See the matching copy in instantiateClassType: resource-ness is // declared at the class and survives instantiation. result.isResource = source.isResource; result.hasSyntheticRelease = source.hasSyntheticRelease; result.isAbstract = source.isAbstract; result.isExtension = source.isExtension; // An extension's receiver type, or a mixin intermediate's `on` type: // a decorator's `context` accessors take the host at the `on` type, // and codegen reads it off the instantiated intermediate. if (source.onType != null) { result.onType = substituteInType(source.onType, source.typeParameters, typeArguments); } result.isSealed = source.isSealed; result.isMixinIntermediate = source.isMixinIntermediate; result.privateScopeKey = source.privateScopeKey; result.decoratorSubjectName = source.decoratorSubjectName; result.decoratorFieldName = source.decoratorFieldName; result.decoratorSharedScopeKey = source.decoratorSharedScopeKey; result.decoratedFields = source.decoratedFields; result.sourcePath = source.sourcePath; result.sealedVariants = source.sealedVariants; result.declaredFields = source.declaredFields; result.forwardVariantNames = source.forwardVariantNames; return result; } /** * What a self-referencing alias stands for in a type key, where * unwrapping it would never end: its name, qualified by the module that * declares it. The name alone is not an identity — two libraries can * each declare a `TemplateValue` — and a key shared by both would make * one specialization serve two different types. */ export function recursiveAliasKey(alias: TypeAliasType): String { if (alias.declaringModule.length == 0) { return alias.name; } return `${alias.name}@${alias.declaringModule}`; } /** Returns whether `source` carries nominal keys from a recursive alias. */ export function hasRecursiveAliasKeys(source: Type): boolean { let {uniqueKeyCache, specializationKeyCache} = source; return uniqueKeyCache != null && uniqueKeyCache.startsWith("alias_") && specializationKeyCache != null; } /** * Copies a recursive alias's nominal keys onto `target` so the alias and * its unwrapped target produce the same specialization and unique keys. */ export function copyRecursiveAliasKeys(source: Type, target: Type): void { if (hasRecursiveAliasKeys(source)) { target.specializationKeyCache = source.specializationKeyCache; target.uniqueKeyCache = source.uniqueKeyCache; } } export function instantiateFunctionType( source: FunctionType, typeArguments: Array, ): FunctionType { let newParams = new Array(); for (let p in source.parameters) { let sub = substituteInType(p, source.typeParameters, typeArguments); newParams.push((sub ?? p)); } let newRet = substituteInType(source.returnType, source.typeParameters, typeArguments); let newFt = internFunctionType(newParams, (newRet ?? source.returnType), source.info, null, toGrowable(typeArguments), source.genericSource ?? source, source.overloads); newFt.functionSymbolId = source.functionSymbolId; newFt.functionSymbolName = source.functionSymbolName; countCodegenFunctionType(6); return newFt; } export final class InterfaceType extends Type { id: TypeId; symbolId: SymbolId; name: String; var typeParameters: Array | null = null; var typeArguments: Array | null = null; var extendsList: GrowableArray = new Array(); /** Own members, and every parent's through `extendsList` (MemberTable). */ var members: MemberTable = new MemberTable(); /** * The `static symbol` declarations this type makes, keyed by their * declared name. A static symbol is reached only through the type that * declares it — `Disposable.dispose` — so it lives here rather than in * `members`, and it never enters a lexical scope. The values are the * canonical `SymbolType` per declaration, which is what gives a * symbol-keyed member an identity distinct from its spelling. */ var staticSymbols: OrderedHashMap = new OrderedHashMap(); var genericSource: InterfaceType | null = null; var interfaceKey: String | null = null; var sourcePath: String = ""; /** As `ClassType.instantiations`: null until the first instantiation. */ var instantiations: HashMap | null = null; /** * The interface's constructors, keyed like a class's: "" * for `new(...)`, the bare name for `new name(...)`. Each is a factory * function whose return type is the interface at its own type * parameters; an instantiation shares the map and substitutes. */ var constructors: HashMap = new Map(); /** As `ClassType.substitutionCache` and `shapeStamp`. */ var substitutionCache: TypeListTable | null = null; var shapeStamp: i32 = 0; new(id: TypeId, symbolId: SymbolId, name: String) : id = id, symbolId = symbolId, name = name, super() { _interfaceTypes += 1; this.members.owner = this; } } /** * Create an instantiated copy of a generic InterfaceType with concrete type arguments. */ export function instantiateInterfaceType( source: InterfaceType, typeArguments: Array, ): InterfaceType { let key = getInstantiationKey(typeArguments); let instantiations = source.instantiations ?? new Map(); source.instantiations = instantiations; let stamp = interfaceShapeStamp(source); let result = if (let (true, cached) = instantiations.get(key)) { _instantiationHits += 1; if (cached.shapeStamp == stamp) { return cached; } cached } else { _instantiationMisses += 1; let res = new InterfaceType(source.id, source.symbolId, source.name); instantiations[key] = res; res }; result.shapeStamp = stamp; result.typeParameters = source.typeParameters; result.typeArguments = toGrowable(typeArguments); result.genericSource = source; // Sharing mutable arrays is technically unsafe, but we never modify these // after instantiation so it should be fine in practice. If this becomes an // issue we can copy the arrays here. result.extendsList = source.extendsList; result.members = source.members; result.staticSymbols = source.staticSymbols; result.constructors = source.constructors; result.sourcePath = source.sourcePath; return result; } /** * MixinKey serves as a mixin declaration key (uniquely identified by sourcePath * and name) rather than a type key. While MixinType represents a specific type-parameterized * instantiation (e.g. MyMixin vs MyMixin), MixinKey is used during codegen layout * and reachability analysis to identify the base mixin declaration itself, ensuring that * mixin fields/methods are mixed in only once and RTA lookups find all target classes. */ export final class MixinKey implements Hashable { sourcePath: String; name: String; new(this.sourcePath, this.name); hashCode(): i32 { return hash(this.sourcePath) ^ hash(this.name); } operator ==(other: MixinKey): boolean { return this.sourcePath == other.sourcePath && this.name == other.name; } } export final class MixinType extends Type { name: String; var symbolId: SymbolId = noSymbolId; var typeParameters: Array | null = null; var typeArguments: Array | null = null; var onType: Type | null = null; /** * The mixin's own members, composed mixins' included (copied in at * registration). A mixin has no parents of its own; its members reach * a host through the intermediate class an application inserts, whose * table reads them from here (MemberTable). */ var members: MemberTable = new MemberTable(); var staticMembers: MemberTable = new MemberTable(); memberTable(isStatic: boolean): MemberTable { return if (isStatic) this.staticMembers else this.members; } /** * Always empty: only an interface declares `static symbol`s, and the * checker rejects one written on a class or mixin body. Carried so that * `Owner.sym` resolves against any named owner and answers "declares no * static symbol" rather than "is not a type that has them". */ var staticSymbols: OrderedHashMap = new OrderedHashMap(); var genericSource: MixinType | null = null; var sourcePath: String = ""; var mixins: GrowableArray = new Array(); var mixinKeyCache: MixinKey | null = null; /** * Synthetic ClassType representing `this` inside this mixin's parameter * defaults and member bodies. Set at mixin registration. */ var selfType: ClassType | null = null; /** * Scope key namespacing this mixin's private fields in host * classes (see ClassType.privateScopeKey). Set at mixin * registration on the declaration's MixinType; instantiations * reach it through genericSource. */ var privateScopeKey: String | null = null; /** * For a `decorator` declaration (docs/design/decorators.md): the * placeholder field's name, mutability and resolved type. Null name on * an ordinary mixin. Set on the declaration's MixinType; instantiations * reach them through genericSource. */ var decoratorSubjectName: String | null = null; var decoratorSubjectMutable: boolean = false; var decoratorSubjectType: Type | null = null; /** * The member keys (`#name`) a decorator declares `shared`: one copy per * host class, under the declaration's scope key, rather than one per * application. Set on the declaration's MixinType; read through * genericSource. */ /** * The names of a decorator's `shared` members; null until one is * declared, which for every mixin that is not a decorator is always. */ var sharedMembers: HashSet | null = null; /** As `ClassType.instantiations`: null until the first instantiation. */ var instantiations: HashMap | null = null; /** Whether this is a `decorator` declaration rather than a mixin. */ isDecorator(): boolean { return (this.genericSource ?? this).decoratorSubjectName != null; } new(name: String) : name = name, super() { _mixinTypes += 1; this.members.owner = this; this.staticMembers.owner = this; this.staticMembers.isStaticTable = true; } } export function instantiateMixinType( source: MixinType, typeArguments: Array, ): MixinType { let key = getInstantiationKey(typeArguments); let instantiations = source.instantiations ?? new Map(); source.instantiations = instantiations; let result = if (let (true, cached) = instantiations.get(key)) { _instantiationHits += 1; cached } else { _instantiationMisses += 1; let res = new MixinType(source.name); instantiations[key] = res; res }; result.symbolId = source.symbolId; result.privateScopeKey = source.privateScopeKey; result.decoratorSubjectName = source.decoratorSubjectName; result.decoratorSubjectMutable = source.decoratorSubjectMutable; result.decoratorSubjectType = source.decoratorSubjectType; result.sharedMembers = source.sharedMembers; result.typeParameters = source.typeParameters; result.typeArguments = toGrowable(typeArguments); result.genericSource = source; result.onType = source.onType; result.members = source.members; result.staticMembers = source.staticMembers; result.staticSymbols = source.staticSymbols; result.sourcePath = source.sourcePath; result.mixins = new Array(); // Copy and substitute mixins for (let m in source.mixins) { let subM = substituteInType(m, source.typeParameters, typeArguments); result.mixins.push((subM ?? m) as MixinType); } return result; } export final class TypeParameterType extends Type { name: String; var constraint: Type | null; var defaultType: Type | null; /** * Declared `scoped T`: the parameter admits second-class arguments, * and the body treats every T value as second-class and consumed * exactly once (ownership.md §"Scoped type arguments"). */ var isScoped: boolean = false; /** * How many `if (isFirstClass())` branches for this parameter the * checker is inside. In one, `T` is first-class: a `scoped T` is * restricted only while this is 0 (isRestrictedParam). Each body * declares its own parameter objects, so a branch in one body never * relaxes another's. */ var firstClassDepth: i32 = 0; /** * Declared `R extends record`: the parameter ranges over record rows * and can be spread into a record type (docs/design/row-types.md * §3.1). `constraint` is null for one. */ var isRecordRow: boolean = false; /** * Declared `R extends tuple`: the parameter ranges over tuple element * lists and can be spread into a tuple type (row-types.md §3.3). * `constraint` is null for one. */ var isTupleRow: boolean = false; /** * For a row parameter, the fields its declaration's signature names * beside `...R`. A row bound to it must have none of them. */ var rowLacks: HashSet | null = null; new(this.name, this.constraint, this.defaultType) : super() { _typeParameterTypes += 1; } } export final class TypeAliasType( name: String, var typeParameters: Array | null, var target: Type, isDistinct: boolean, var typeArguments: Array | null, /** * True for `opaque type X = Y`. Always implies `isDistinct`, so the nominal * behaviour (assignability, erasure, codegen) needs no extra cases — the * only thing opacity adds is that casting *to* this alias is restricted to * `declaringModule`. See docs/design/opaque-types.md. */ isOpaque: boolean, /** * Canonical path of the module that declared this alias, in the same string * space as `Symbol.modulePath` and `CheckerContext.filePath`. Empty for * synthesized aliases (enum backing types) that are never opaque. */ declaringModule: String ) extends Type { /** * Ephemeral flag used by the checker to detect generic type resolution cycles. * When this is true, the checker is currently computing this alias's target. * If a code path reads `target` while `.resolving` is true, it MUST stop * unwrapping and treat this TypeAliasType as an opaque bound. Otherwise, * recursive aliases (e.g., `type T = T[]`) will trigger an infinite loop. */ var resolving: boolean = false; /** * The builtin type-operator rule this alias applies, from an * `@intrinsic('type.…')` decorator — 'type.awaited' is the first. * An intrinsic alias's TARGET is a placeholder: applying the alias * runs the named rule instead of unwrapping to the target, so * unwrapping treats these like distinct aliases (it stops), and * every substitution that closes the argument re-applies the rule * (`applyTypeIntrinsic`). */ var intrinsicName: String | null = null; } /** * The type an `enum` declaration declares. A value of it is one of the * declared members, carried at runtime as the backing primitive (`i32`, * or `String` for a string enum); the type is nominal, assignable only * to itself, and reaches the backing type through an explicit cast * (docs/design/enums.md). The declaration's name is bound to this type * in the value namespace too, where its `members` are the enum's * members, each a static field of this type (`Color.Red`). Codegen * erases it to the backing type. */ export final class EnumType extends Type { symbolId: SymbolId; name: String; /** * The declaration, whose member list says which values exist: match * exhaustiveness counts them, and lowering reads each member's value. */ declaration: EnumDeclaration; /** * Canonical path of the declaring module, in the same string space as * `Symbol.modulePath` and `CheckerContext.filePath`. */ declaringModule: String; /** * A hole until the enum's own registration fills it in: an importer * across an import cycle's back edge may create the type first. */ var backingType: Type = new HoleType(); var members: MemberTable = new MemberTable(); new(symbolId: SymbolId, name: String, declaration: EnumDeclaration, declaringModule: String) : symbolId = symbolId, name = name, declaration = declaration, declaringModule = declaringModule, super() { this.members.owner = this; } } /** * The canonical id of the module declaring a nominal type, or null for a * type no module declares. * * This is the value `isWellKnown` expects. It comes off the type rather * than off whichever path the declaring file was loaded under, because * those differ: a standard library file can be loaded under a filesystem * path, and only the canonical `zena:` id names a library. */ export function declaringModuleOf(t: Type): String | null { return match (t) { case ClassType as ct: ct.sourcePath case InterfaceType as it: it.sourcePath case MixinType as mt: mt.sourcePath case TypeAliasType as at: at.declaringModule case EnumType as et: et.declaringModule case _: null }; } /** * True when codegen compiles a for-in over this class to a direct * index loop (lowerForIn in ir/control-flow.zena): FixedArray, * ImmutableArray and GrowableArray lower to array.len/array.get, * and BoundedRange and FromRange to a loop counting from the range's * start. None of them touch the Iterable/Iterator protocol, so a for-in * iterable of one of these types must not register an interface * adaptation, and reachability must not root the protocol for it. * Mirrors lowerForIn's dispatch, including the type-argument * requirement for the arrays — a bare mention with no arguments has no * element type there and falls back to the iterator path — and the * `i32` requirement for the ranges. The classes are told by identity: * a program's own `FixedArray` iterates through the protocol. */ export function forInLowersToIndexLoop(ct: ClassType): boolean { var canonical = ct; while (canonical.genericSource != null) { canonical = canonical.genericSource as ClassType; } if (isCountingRangeClass(canonical)) { return isI32Range(ct); } let targs = ct.typeArguments; if (!isWellKnown(WellKnown.FixedArrayClass, canonical.name, canonical.sourcePath) && !isWellKnown(WellKnown.ImmutableArrayClass, canonical.name, canonical.sourcePath) && !isWellKnown(WellKnown.GrowableArrayClass, canonical.name, canonical.sourcePath)) { return false; } return targs != null && targs.length > 0; } /** True for the standard library's `BoundedRange` and `FromRange`, the * two ranges a `for`-in counts through, whatever their arguments. */ function isCountingRangeClass(ct: ClassType): boolean { return isWellKnown(WellKnown.BoundedRangeClass, ct.name, ct.sourcePath) || isWellKnown(WellKnown.FromRangeClass, ct.name, ct.sourcePath); } /** True when a range class's argument is `i32`, or defaulted to it. */ function isI32Range(ct: ClassType): boolean { let targs = ct.typeArguments; return targs == null || (targs.length == 1 && targs[0] is I32Type); } /** True for the standard library's `BoundedRange` and * `FromRange`: the ranges a `for`-in compiles to a counting loop. */ export function isIterableRangeClass(ct: ClassType): boolean { return isCountingRangeClass(ct) && isI32Range(ct); } /** * Whether `t` is one of the three ownership handles from `zena:ownership`. * A `resource class` may only be named as a type argument of one of these — * see docs/design/ownership.md §"Resource-ness and affineness are different * properties". */ export function isOwnershipWrapper(t: Type): boolean { if (!(t is TypeAliasType)) { return false; } if (!t.isDistinct) { return false; } return isWellKnown(WellKnown.OwnAlias, t.name, t.declaringModule) || isWellKnown(WellKnown.BorrowAlias, t.name, t.declaringModule) || isWellKnown(WellKnown.UnmanagedAlias, t.name, t.declaringModule); } /** * The sole non-null member of a `T | null` union, or null when `t` is * not exactly that shape. `using` and implicit drop accept a nullable * handle by skipping the release when the value is null, so both the * checker and lowering peel exactly this union form; wider unions have * no single release path and stay rejected. */ export function soleNonNullMember(t: Type): Type | null { if (!(t is UnionType)) { return null; } var nonNull: Type | null = null; var sawNull = false; for (let m in t.types) { if (m is NullType) { sawNull = true; } else { if (nonNull != null) { return null; } nonNull = m; } } if (!sawNull) { return null; } return nonNull; } /** * Whether `t` is `Scoped` (ownership.md §"Scoped: the fourth * corner"). Not one of the handles: it applies to any value, so it is * recognized separately and gets none of the handle behaviors — no * member forwarding, no receiver rules, no bare-mention checks. */ export function isScopedType(t: Type): boolean { if (!(t is TypeAliasType)) { return false; } // The conditional operator is scoped exactly when its condition // argument carries a second-class type; while that argument is an // open `scoped T` the body sees it as Scoped, and substitution // collapses it (applyTypeIntrinsic) once T closes. if (t.intrinsicName == 'type.scopedFrom') { let sargs = t.typeArguments; if (sargs == null || sargs.length != 2) { return false; } return typeContainsSecondClass(sargs[0]); } if (!t.isDistinct) { return false; } return isWellKnown(WellKnown.ScopedAlias, t.name, t.declaringModule); } /** * The type behind `Scoped`, or null if `t` is not one. Reads * `typeArguments` rather than `target` for the same reason * ownershipHandleInner does: `Scoped = T` has the bare type * parameter as its target. */ export function scopedInner(t: Type): Type | null { if (!isScopedType(t)) { return null; } let alias = t as TypeAliasType; let args = alias.typeArguments; if (args == null) { return null; } if (alias.intrinsicName == 'type.scopedFrom') { if (args.length != 2) { return null; } return args[1]; } if (args.length != 1) { return null; } return args[0]; } /** Which of the three ownership handles a type is, or none. */ export enum OwnershipHandle { None, Own, Borrow, Unmanaged } /** The handle `t` is: `None` when it is not one. */ export function ownershipHandleOf(t: Type): OwnershipHandle { if (!isOwnershipWrapper(t)) { return OwnershipHandle.None; } let alias = t as TypeAliasType; if (isWellKnown(WellKnown.OwnAlias, alias.name, alias.declaringModule)) { return OwnershipHandle.Own; } if (isWellKnown(WellKnown.BorrowAlias, alias.name, alias.declaringModule)) { return OwnershipHandle.Borrow; } return OwnershipHandle.Unmanaged; } /** * `t` with its transparent aliases peeled: a `distinct` alias, a type * operator and an alias still being resolved stop the walk, since a * distinct alias is a nominal type of its own, an operator's target is * a placeholder, and a self-referential alias would spin. */ export function unwrapAliases(t: Type): Type { var curr = t; var hops = 0; while (curr is TypeAliasType && hops < 32) { let ta = curr; if (ta.isDistinct || ta.intrinsicName != null || ta.resolving) { break; } curr = ta.target; hops += 1; } // An inline record has its record's structure; only where a value is // held does it differ (docs/design/inline-parameters.md). if (let InlineRecordType {record} = curr) { return record; } return curr; } /** Whether `t` is `null` or a union with a `null` member. */ export function isNullableType(t: Type): boolean { return match (t) { case NullType: true case UnionType {types}: { for (let member in types) { if (member is NullType) { return true; } } false } case _: false }; } /** * A type whose values follow the scoped consumption rules — the * `Scoped` wrapper itself, or a `scoped T` parameter's values, which * the body checks at the same discipline outside an * `isFirstClass()` branch. */ export function isScopedValueType(t: Type): boolean { if (isScopedType(t)) { return true; } return isRestrictedParam(t); } /** Whether `t` is an instance of the `WithDefault` operator. */ export function isWithDefaultType(t: Type): boolean { return t is TypeAliasType && t.intrinsicName == 'type.withDefault'; } /** * Whether `t` is a tuple, boxed or inline, or a union of them, that holds * an owner. Such a tuple is affine itself (#495): building it moves the * owner in, a binding of it moves like an `Own`, and destructuring it * moves the owners out. */ export function isAffineTuple(t: Type): boolean { let resolved = unwrapAliases(t); if (resolved is TupleType || resolved is InlineTupleType) { return typeCarriesOwner(resolved); } if (let UnionType {types} = resolved) { for (let member in types) { if (isAffineTuple(member)) { return true; } } } return false; } /** * Whether a binding of type `t` is move-checked like an owner: a tuple * holding an owner (#495), or an instance of a container of one, such * as a `Future>`, which its `await` consumes, or a union with * such a member, such as an `Option>`. */ export function isAffineValue(t: Type): boolean { if (isAffineTuple(t)) { return true; } return affineContainerMembers(t).length > 0; } /** * The members of `t` that are containers of an owner (isAffineContainer): * `t` itself, or each such member of a union, nullable or not. */ export function affineContainerMembers(t: Type): GrowableArray { let found = new Array(); let resolved = unwrapAliases(soleNonNullMember(t) ?? t); let members = if (let UnionType {types} = resolved) types else growable([resolved]); for (let member in members) { let core = unwrapAliases(member); if (core is ClassType && isAffineContainer(core)) { found.push(core); } } return found; } /** * The resource type behind a handle, or null if `t` is not a handle. * * This reads `typeArguments` rather than following `target`, and the * difference is load-bearing: the handles are *generic* aliases, so * `Own = T` has the bare type parameter as its target. Walking `target` * — which is what `unwrapAliases` does — lands on `T` rather than on the * resource, so a caller that wants the class must come through here. */ export function ownershipHandleInner(t: Type): Type | null { if (!isOwnershipWrapper(t)) { return null; } let args = (t as TypeAliasType).typeArguments; if (args == null) { return null; } if (args.length != 1) { return null; } return args[0]; } export function typeContainsTypeParameter(t: Type): boolean { return match (t) { case TypeParameterType: true case UnionType {types}: { for (let subtype in types) { if (typeContainsTypeParameter(subtype)) { return true; } } false } case ArrayType {elementType}: typeContainsTypeParameter(elementType) case TupleType {elementTypes, row}: { if (row != null) { return true; } for (let elem in elementTypes) { if (typeContainsTypeParameter(elem)) { return true; } } false } case InlineTupleType {elementTypes}: { for (let elem in elementTypes) { if (typeContainsTypeParameter(elem)) { return true; } } false } case InlineParamType: true case InlineRecordType {record}: typeContainsTypeParameter(record) case RecordType as rec: { if (rec.row != null) { return true; } for (let pair in rec.properties) { if (typeContainsTypeParameter(pair.value)) { return true; } } false } case FunctionType as ft: { for (let param in ft.parameters) { if (typeContainsTypeParameter(param)) { return true; } } typeContainsTypeParameter(ft.returnType) } case ClassType as ct: { let {typeParameters} = ct; if (typeParameters != null && typeParameters.length > 0 && ct.typeArguments == null) { return true; } if (ct.typeArguments != null) { let targs = ct.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { if (typeContainsTypeParameter(targs[i])) { return true; } i += 1; } } false } case InterfaceType as it: { let {typeParameters} = it; if (typeParameters != null && typeParameters.length > 0 && it.typeArguments == null) { return true; } if (it.typeArguments != null) { let targs = it.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { if (typeContainsTypeParameter(targs[i])) { return true; } i += 1; } } false } case TypeAliasType as ta: { let {typeParameters} = ta; if (typeParameters != null && typeParameters.length > 0 && ta.typeArguments == null) { return true; } if (ta.typeArguments != null) { let targs = ta.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { if (typeContainsTypeParameter(targs[i])) { return true; } i += 1; } } false } case MixinType as mt: { let {typeParameters} = mt; if (typeParameters != null && typeParameters.length > 0 && mt.typeArguments == null) { return true; } if (mt.typeArguments != null) { let targs = mt.typeArguments as Array; var i = 0; let len = targs.length; while (i < len) { if (typeContainsTypeParameter(targs[i])) { return true; } i += 1; } } let {onType} = mt; if (onType != null && typeContainsTypeParameter(onType)) { return true; } false } case _: false }; } /** * Whether `t` is the stdlib `Future` class (any instantiation). By * name and declaring library rather than by prelude identity, so the * `type.awaited` rule can run anywhere types are substituted, with or * without a checker context. `Future` is declared in * `zena:async/future.zena`, a private file of `zena:async`, and the * library is what the registry matches on, so the file it sits in can * change without changing this. */ export function isFutureClassType(t: Type): boolean { if (!(t is ClassType)) { return false; } return isWellKnown(WellKnown.FutureClass, t.name, t.sourcePath); } /** * The `type.awaited` rule: the type `await x` has when `x: T`, as a * total function (docs/design/async.md §1) — `Future` becomes `U`, * a union maps its arms (future arms unwrap, bare arms pass through, * duplicates collapse), and anything else passes through unchanged. * ONE level deliberately: Zena's runtime does not recursively flatten * nested futures, and one level is what monadic bind means. */ export function awaitedTypeOf(t: Type): Type { let unwrapArm = (arm: Type) => { // Awaiting is a scoped future's consumption, so the wrapper // unwraps with the future it carries: Awaited>> // is U. var core = arm; if (isScopedType(core)) { let inner = scopedInner(core); if (inner != null) { core = inner; } } if (isFutureClassType(core)) { let args = (core as ClassType).typeArguments; if (args != null && args.length == 1) { return args[0]; } } return arm; }; if (t is UnionType) { let mapped = new Array(); for (let arm in t.types) { let next = unwrapArm(arm); var seen = false; for (let existing in mapped) { if (instantiationKeyOf(existing) == instantiationKeyOf(next)) { seen = true; break; } } if (!seen) { mapped.push(next); } } if (mapped.length == 1) { return mapped[0]; } return new UnionType(mapped); } return unwrapArm(t); } /** * The `type.withDefault` rule: `WithDefault` is `T` at a primitive * and `T | null` at a reference (type-operators.md §"`type.withDefault`"). * It is the type of a slot that is empty until a `T` is stored, with * `defaultValue()` its empty value: zero, or null. */ export function withDefaultTypeOf(alias: TypeAliasType): Type { let args = alias.typeArguments; if (args == null || args.length != 1) { return alias; } let t = args[0]; if (typeContainsTypeParameter(t)) { return alias; } // A primitive has no null, and `void` and `never` have no value to // hold, so the slot is the type itself. if (hasPrimitiveRepresentation(t) || t is VoidType || t is NeverType) { return t; } if (t is NullType) { return t; } let members = new Array(); if (t is UnionType) { for (let m in t.types) { if (m is NullType) { return t; } members.push(m); } } else { members.push(t); } members.push(new NullType()); return new UnionType(members); } /** * Whether values of `t` are represented by a wasm scalar rather than a * reference, through enums and distinct aliases, so a slot of it has * no null. */ export function hasPrimitiveRepresentation(t: Type): boolean { var current = t; var hops = 0; while (hops < 32) { if (current is EnumType) { let e = current as EnumType; current = e.backingType; } else if (current is TypeAliasType) { let alias = current as TypeAliasType; if (alias.intrinsicName != null || alias.resolving || isOwnershipWrapper(alias)) { break; } current = alias.target; } else { break; } hops += 1; } return isNumericType(current) || current is BooleanType || current is BoolLiteralType || current is V128Type; } /** * The `type.scopedFrom` rule: `ScopedFrom` is `Scoped` when * `T` carries a second-class type and `R` otherwise * (ownership.md §"Combinator audit"). While `T` is still open the * instance stays symbolic, and isScopedType/scopedInner answer for it * as Scoped — the worst case a `scoped T` body must be checked at. * The operator's `target` is the `Scoped` declaration itself, set * where the operator is declared, so the collapse can instantiate the * real alias without a checker context. */ export function scopedFromTypeOf(alias: TypeAliasType): Type { let args = alias.typeArguments; if (args == null || args.length != 2) { return alias; } if (typeContainsTypeParameter(args[0])) { return alias; } if (!typeContainsSecondClass(args[0])) { return args[1]; } let scopedDecl = alias.target; if (scopedDecl is TypeAliasType) { if (scopedDecl.typeParameters != null) { let one = growable([args[1]]); return instantiateTypeAliasType(scopedDecl, one); } } return alias; } /** * Applies an intrinsic alias's rule once its argument is closed, and * returns the alias unchanged while the argument still mentions open * type parameters — substitution re-applies at every step, so the * first closing substitution normalizes the alias away. */ export function applyTypeIntrinsic(alias: TypeAliasType): Type { if (alias.intrinsicName == 'type.scopedFrom') { return scopedFromTypeOf(alias); } if (alias.intrinsicName == 'type.withDefault') { return withDefaultTypeOf(alias); } if (alias.intrinsicName != 'type.awaited') { return alias; } let args = alias.typeArguments; if (args == null || args.length != 1) { return alias; } if (typeContainsTypeParameter(args[0])) { return alias; } return awaitedTypeOf(args[0]); } export function instantiateTypeAliasType( source: TypeAliasType, typeArguments: Array ): TypeAliasType { let inst = new TypeAliasType( source.name, source.typeParameters, source.target, // We substitute the target in the checker since it needs the map source.isDistinct, typeArguments, source.isOpaque, source.declaringModule ); inst.intrinsicName = source.intrinsicName; return inst; } export type GenericNamedType = ClassType | InterfaceType | MixinType | TypeAliasType; /** * A `symbol` declaration's type: a name and an identity, and nothing * else. Two declarations that spell the same name are two symbols, which * is the whole point of having them — so `id` is what distinguishes a * member keyed by one from a member keyed by the other, and `name` is * only ever for reading. * * `debugName` qualifies the name for a message (`Disposable.dispose`); * `name` is the bare spelling, which is what a member key carries. * * `protocolKey` is set for the standard library symbols the compiler * invokes itself — `Disposable.dispose` when it drops a resource, * `Iterable.iterator` when it lowers a `for`-in, the async runtime's hooks * (the table is `protocolSymbolKey` in `well-known.zena`). Their identity * is fixed by the language, the way a well-known type's is, so their * member key is a constant codegen can name (`:dispose`) rather than one * minted from a per-compilation id. */ export final class SymbolType( id: TypeId, debugName: String | null, name: String, protocolKey: String | null ) extends Type export final class ThisType extends Type {} /** * Check if a type is a numeric primitive. */ export function isNumericType(t: Type): boolean { return match (baseType(t)) { case I32Type: true case U32Type: true case I64Type: true case U64Type: true case F32Type: true case F64Type: true case U8Type: true case U16Type: true case I8Type: true case I16Type: true case _: false }; } /** * Check if a type is an integer type. */ export function isIntegerType(t: Type): boolean { return match (baseType(t)) { case I32Type: true case U32Type: true case I64Type: true case U64Type: true case U8Type: true case U16Type: true case I8Type: true case I16Type: true case _: false }; } /** * Check if a type is one of the narrow integer types — the ones stored in * fewer than 32 bits and promoted before use. */ export function isNarrowIntType(t: Type): boolean { return match (baseType(t)) { case U8Type: true case U16Type: true case I8Type: true case I16Type: true case _: false }; } /** * Check if an integer type is unsigned. Signedness drives operator * selection (`_u` vs `_s` variants) and cast normalization. */ export function isUnsignedIntType(t: Type): boolean { return match (baseType(t)) { case U32Type: true case U64Type: true case U8Type: true case U16Type: true case _: false }; } /** * Storage width in bits of a narrow integer type, or 32 for everything * else. Used to build the normalizing mask/sign-extend on a cast. */ export function narrowIntBits(t: Type): i32 { return match (baseType(t)) { case U8Type: 8 case I8Type: 8 case U16Type: 16 case I16Type: 16 case _: 32 }; } /** * The 32-bit type a narrow integer promotes to. Non-narrow types are * returned unchanged, so this is safe to apply to any operand. */ export function promoteNarrowInt(t: Type): Type { return match (baseType(t)) { case U8Type: new U32Type() case U16Type: new U32Type() case I8Type: new I32Type() case I16Type: new I32Type() case _: t }; } /** * Check if a type is a floating point type. */ export function isFloatType(t: Type): boolean { return match (baseType(t)) { case F32Type: true case F64Type: true case _: false }; } /** * Check if a type is a 64-bit type. */ export function is64BitType(t: Type): boolean { return match (baseType(t)) { case I64Type: true case U64Type: true case F64Type: true case _: false }; } /** * Check if a type is a Wasm GC reference type. */ export function isRefType(t: Type): boolean { let b = baseType(t); return b is RecordType || b is ClassType || b is ArrayType || b is InterfaceType || b is TypeParameterType || b is ThisType || b is AnyRefType || b is EqRefType || b is ExternRefType || b is FunctionType || b is TupleType || b is NullType || b is UnionType || b is StringLiteralType || b is StringLiteralType; } export function isVoidOrNeverType(t: Type): boolean { let b = baseType(t); return b is VoidType || b is NeverType || b is HoleType; } /** * How many arguments a call must actually supply. * * Optional parameters are omittable, and so are ZERO-WIDTH ones. A * `void` parameter carries no value: codegen erases it (it takes no * wasm slot), and there is no way to spell a `void` argument except by * calling a void-returning function. That is what makes `void` usable * as a type argument — `Completer` instantiates * `complete(value: T)` into a parameter nothing can be passed for, so * callers write `c.complete()`. * * Omitting is permitted, not required: an explicit void-typed * expression still type-checks in the slot, and still runs for its * side effects. * * Counting (rather than position-matching) is safe here because void * accepts nothing but void: an argument that slides into a void * parameter's position fails its own assignability check. */ export function requiredParameterCount( parameters: Array, optionals: GrowableArray | null): i32 { var required = 0; for (var i = 0; i < parameters.length; i += 1) { let isOptional = if (optionals != null) { i < optionals.length && optionals[i] } else { false }; if (!isOptional && !isVoidOrNeverType(parameters[i])) { required += 1; } } return required; } /** * Get the name of a numeric type. */ export function numericTypeName(t: Type): String { return match (t) { case I32Type: "i32" case U32Type: "u32" case I64Type: "i64" case U64Type: "u64" case F32Type: "f32" case F64Type: "f64" case U8Type: "u8" case U16Type: "u16" case I8Type: "i8" case I16Type: "i16" case _: "unknown" }; } /** * Check if a type is a boolean or boolean literal. */ export function isBooleanLike(t: Type): boolean { return match (t) { case BooleanType: true case BoolLiteralType {}: true case UnionType {types}: { var allBool = true; for (let member in types) { if (!isBooleanLike(member)) { allBool = false; } } allBool } case _: false }; } /** * Get the base type of a literal type, or the type itself if not literal. */ export function baseType(t: Type): Type { return match (t) { case BoolLiteralType {}: new BooleanType() case NumLiteralType {raw}: { var isFloat = false; var i = 0; while (i < raw.length) { if (raw.getByteAt(i) == 46) { // '.' isFloat = true; break; } i += 1; } if (isFloat) new F64Type() else new I32Type() } case _: t }; } /** * Compute the promoted numeric type for a binary operation. * Returns null if the types are incompatible. */ export function promoteNumeric(leftOrig: Type, rightOrig: Type): Type | null { let leftLit = if (leftOrig is NumLiteralType) baseType(leftOrig) else leftOrig; let rightLit = if (rightOrig is NumLiteralType) { baseType(rightOrig) } else { rightOrig }; // Narrow integers are storage widths, not arithmetic widths: each side // promotes to its 32-bit counterpart before anything else is decided. // Mixed sizes within one signedness therefore just work (u8 + u16 is // u32), while mixed signedness stays an error at every width, and a // narrow type never survives the operation. let left = promoteNarrowInt(leftLit); let right = promoteNarrowInt(rightLit); // f64 dominates everything if (left is F64Type || right is F64Type) { return new F64Type(); } // f32 + 64-bit → f64 if (left is F32Type && is64BitType(right)) { return new F64Type(); } if (right is F32Type && is64BitType(left)) { return new F64Type(); } // f32 dominates remaining if (left is F32Type || right is F32Type) { return new F32Type(); } // u64 dominates integers if (left is U64Type || right is U64Type) { // Reject mixed signedness: u64 + i32/i64 is an error if (left is U64Type && right is U64Type) { return new U64Type(); } return null; } // i64 dominates remaining integers if (left is I64Type || right is I64Type) { return new I64Type(); } // Same signedness 32-bit integers if (left is U32Type && right is U32Type) { return new U32Type(); } if (left is I32Type && right is I32Type) { return new I32Type(); } // Mixed signedness i32/u32 — reject if (isIntegerType(left) && isIntegerType(right)) { return null; } return null; } /** * Extract the radix (`2`, `8`, `10`, `16`) and digit start index of an * unsigned integer literal source string (`0b`, `0o`, `0x`, or decimal). */ export function integerLiteralRadix(raw: String): inline (i32, i32) { if (raw.length >= 2 && raw.getByteAt(0) == 48) { let c1 = raw.getByteAt(1); if (c1 == 120 || c1 == 88) { return (16, 2); } if (c1 == 98 || c1 == 66) { return (2, 2); } if (c1 == 111 || c1 == 79) { return (8, 2); } } return (10, 0); } /** * Return `raw` with `'_'` separators removed, reusing `raw` unchanged when * none are present. */ export function stripNumericUnderscores(raw: String): String { if (!raw.contains('_')) { return raw; } let sb = new StringBuilder(); for (var i = 0; i < raw.length; i += 1) { let c = raw.getByteAt(i); if (c != 95) { sb.appendByte(c); } } return sb.toString(); } /** * Parse a non-negative integer literal intended as a static tuple index. */ export function parseTupleIndexLiteral(raw: String): inline (boolean, i32) { if (raw.contains('.')) { return (false, 0); } if (let (true, mag) = integerLiteralMagnitude(raw)) { if (mag <= (2147483647 as u64)) { return (true, mag as i32); } } return (false, 0); } /** * Whether `raw` is an integer literal carrying the `n` (`BigInt`) suffix * (`42n`, `42_n`, `0xffn`, `0b1010n`, `0o755n`). */ export function isBigIntLiteralRaw(raw: String): boolean { return raw.length > 0 && raw.getByteAt(raw.length - 1) == 110 && !raw.contains('.'); } /** * Whether two numeric literal spellings denote the same literal-type value * (`1_000` and `1000`, `0x10` and `16`, `3.14_15` and `3.1415`). */ export function sameNumericLiteralRaw(a: String, b: String): boolean { if (isBigIntLiteralRaw(a) || isBigIntLiteralRaw(b)) { return false; } if (a == b) { return true; } let aFloat = a.contains('.'); let bFloat = b.contains('.'); if (aFloat != bFloat) { return false; } if (aFloat) { return stripNumericUnderscores(a) == stripNumericUnderscores(b); } let negA = a.length > 0 && a.getByteAt(0) == 45; let negB = b.length > 0 && b.getByteAt(0) == 45; let digitsA = if (negA) a.sliceBytes(1, a.length) else a; let digitsB = if (negB) b.sliceBytes(1, b.length) else b; if (let (true, magA) = integerLiteralMagnitude(digitsA)) { if (let (true, magB) = integerLiteralMagnitude(digitsB)) { if (magA == (0 as u64) && magB == (0 as u64)) { return true; } return negA == negB && magA == magB; } } return false; } /** * Parse the magnitude of an integer literal, reporting overflow rather * than wrapping. `raw` is the literal's source text without a sign; * underscores are ignored and `0x`/`0b`/`0o` prefixes select hex, binary, * or octal. Returns `(false, _)` for a malformed literal or one that does * not fit in 64 bits, which is the widest magnitude any Zena primitive * integer type can hold. */ export function integerLiteralMagnitude(raw: String): inline (boolean, u64) { let (radix, start) = integerLiteralRadix(raw); // Largest value that can still absorb another digit, and the largest // digit it can absorb: u64Max / base and u64Max % base. Written as // constants because `/` on integers promotes to a float in Zena. let limit = if (radix == 16) { 1152921504606846975 as u64 } else if (radix == 8) { 2305843009213693951 as u64 } else if (radix == 2) { 9223372036854775807 as u64 } else { 1844674407370955161 as u64 }; let lastDigit = if (radix == 16) { 15 as u64 } else if (radix == 8) { 7 as u64 } else if (radix == 2) { 1 as u64 } else { 5 as u64 }; let base = radix as u64; var res = 0 as u64; var i = start; var hasDigits = false; while (i < raw.length) { let code = raw.getByteAt(i); if (code == 95) { // '_' i += 1; continue; } var digit = 0 as u64; if (radix == 2) { if (code == 48 || code == 49) { digit = (code - 48) as u64; } else { return (false, 0 as u64); } } else if (radix == 8) { if (code >= 48 && code <= 55) { digit = (code - 48) as u64; } else { return (false, 0 as u64); } } else if (code >= 48 && code <= 57) { // '0'..'9' digit = (code - 48) as u64; } else if (radix == 16 && code >= 97 && code <= 102) { // 'a'..'f' digit = (code - 97 + 10) as u64; } else if (radix == 16 && code >= 65 && code <= 70) { // 'A'..'F' digit = (code - 65 + 10) as u64; } else { return (false, 0 as u64); } if (res > limit) { return (false, 0 as u64); } if (res == limit && digit > lastDigit) { return (false, 0 as u64); } res = res * base + digit; hasDigits = true; i += 1; } if (!hasDigits) { return (false, 0 as u64); } return (true, res); } /** * The element type of an array-shaped type: the intrinsic `array`, * or a generic class over it (`FixedArray`, `Array`) whose first * type argument is the element. Returns null for anything else. * * Callers use this to recover the *semantic* element type when the wasm * type cannot answer a question — chiefly whether a packed element * should be read sign-extended, since `u8` and `i8` share one wasm * array type. */ export function arrayElementType(t: Type): Type | null { return match (baseType(t)) { case ArrayType {elementType}: elementType case ClassType as ct: { let {typeArguments} = ct; if (typeArguments != null && typeArguments.length > 0) { typeArguments[0] } else { null } } case _: null }; } /** * Whether a narrow integer type is one of the signed ones, i.e. whether * a packed load of it must sign-extend. False for everything that is not * a narrow type, so a caller that has already established packing can * read this as "use array.get_s". */ export function isSignedNarrowIntType(t: Type): boolean { return match (baseType(t)) { case I8Type: true case I16Type: true case _: false }; } /** * Whether an integer literal fits a type with a checked range. `raw` is * the unsigned source text and `negative` reports a leading unary minus, * kept separate so that `-128` fits `i8` even though `128` alone does * not. Callers must have established `integerTypeHasCheckedRange(t)`. */ export function integerLiteralFits(raw: String, negative: boolean, t: Type): boolean { if (let (true, mag) = integerLiteralMagnitude(raw)) { let zero = 0 as u64; if (negative) { // Negative zero is still zero, and so fits anywhere. if (mag == zero) { return true; } return match (baseType(t)) { case I8Type: mag <= (128 as u64) case I16Type: mag <= (32768 as u64) // The unsigned types hold no negative value at all. case _: false }; } return match (baseType(t)) { case U8Type: mag <= (255 as u64) case U16Type: mag <= (65535 as u64) case I8Type: mag <= (127 as u64) case I16Type: mag <= (32767 as u64) case U32Type: mag <= (4294967295 as u64) // Any magnitude that parsed at all fits u64. case U64Type: true case _: false }; } // Malformed, or wider than 64 bits: fits nothing. return false; } /** * Whether an integer literal fits `i64` (`is64`) or `i32`, the types a * literal takes without a range-checked context. A decimal literal must * fit the signed range, with `negative` reporting a leading unary minus * as in `integerLiteralFits`. A radix literal (`0x`, `0b`, `0o`) may use * every bit, as a bit pattern, so `0xFFFFFFFF` is the i32 -1. */ export function signedLiteralFits(raw: String, negative: boolean, is64: boolean): boolean { if (let (true, mag) = integerLiteralMagnitude(raw)) { let (radix, _) = integerLiteralRadix(raw); let isBitPattern = radix != 10; if (is64) { // Any magnitude that parsed at all is a 64-bit pattern. if (isBitPattern) { return true; } return if (negative) mag <= (9223372036854775808 as u64) else mag <= (9223372036854775807 as u64); } if (isBitPattern) { return mag <= (4294967295 as u64); } return if (negative) mag <= (2147483648 as u64) else mag <= (2147483647 as u64); } // Malformed, or wider than 64 bits: fits nothing. return false; } /** * Format a type as a human-readable string for diagnostics. */ export function typeToString(t: Type): String { return match (t) { case I32Type: "i32" case U32Type: "u32" case I64Type: "i64" case U64Type: "u64" case F32Type: "f32" case F64Type: "f64" case U8Type: "u8" case U16Type: "u16" case I8Type: "i8" case I16Type: "i16" case V128Type: "v128" case BooleanType: "boolean" case VoidType: "void" case NullType: "null" case NeverType: "never" case HoleType: "_" case ErrorType: "" case UnknownType: "unknown" case AnyRefType: "anyref" case ErasedType: "erased" case EqRefType: "eqref" case ExternRefType: "externref" case BoolLiteralType {value}: if (value) "true" else "false" case StringLiteralType {value}: `'${value}'` case NumLiteralType {raw}: raw // Mutable elements keep today's spelling; immutable elements print as // `array`, the surface spelling they will own once the default flips. case ArrayType {elementType, elementsMutable}: `${if (elementsMutable) "Array<" else "array<"}${typeToString(elementType)}>` case TupleType {elementTypes, row, rowIndex}: { var s = "["; var i = 0; var written = 0; while (i <= elementTypes.length) { if (row != null && i == rowIndex) { if (written > 0) { s = s + ", "; } s = `${s}...${row.name}`; written += 1; } if (i < elementTypes.length) { if (written > 0) { s = s + ", "; } s = s + typeToString(elementTypes[i]); written += 1; } i += 1; } s + "]" } case InlineTupleType {elementTypes}: { var s = "("; var i = 0; while (i < elementTypes.length) { if (i > 0) { s = s + ", "; } s = s + typeToString(elementTypes[i]); i += 1; } s + ")" } case UnionType {types}: { // A union of one type with null prints as the nullable shorthand. var nullableInner: Type | null = null; if (types.length == 2) { if (types[0] is NullType) { nullableInner = types[1]; } else if (types[1] is NullType) { nullableInner = types[0]; } } if (nullableInner != null) { let inner = nullableInner; if (inner is FunctionType) { `(${typeToString(inner)})?` } else { typeToString(inner) + "?" } } else { var s = ""; var i = 0; while (i < types.length) { if (i > 0) { s = s + " | "; } s = s + typeToString(types[i]); i += 1; } s } } case RecordType as rec: { var s = "{ "; let keys = rec.properties.keys(); var first = true; for (let key in keys) { if (!first) { s = s + ", "; } s = `${s}${key}: ${typeToString(rec.properties[key])}`; first = false; } let row = rec.row; if (row != null) { if (!first) { s = s + ", "; } s = `${s}...${row.name}`; } else if (rec.isExistential) { if (!first) { s = s + ", "; } s = `${s}...`; } s + " }" } case FunctionType as ft: { var s = "("; var i = 0; while (i < ft.parameters.length) { if (i > 0) { s = s + ", "; } let parameterNames = ft.parameterNames; if (parameterNames != null) { let names = parameterNames; if (i < names.length) { s = `${s}${names[i]}: `; } } s = s + typeToString(ft.parameters[i]); i += 1; } `${s}) => ${typeToString(ft.returnType)}` } case ClassType as ct: { let {typeArguments} = ct; if (typeArguments != null) { let args = typeArguments; var s = ct.name + "<"; var i = 0; while (i < args.length) { if (i > 0) { s = s + ", "; } s = s + typeToString(args[i]); i += 1; } s + ">" } else { ct.name } } case InterfaceType as it: { let {typeArguments} = it; if (typeArguments != null) { let args = typeArguments; var s = it.name + "<"; var i = 0; while (i < args.length) { if (i > 0) { s = s + ", "; } s = s + typeToString(args[i]); i += 1; } s + ">" } else { it.name } } case MixinType as mt: { let {typeArguments} = mt; if (typeArguments != null) { let args = typeArguments; var s = mt.name + "<"; var i = 0; while (i < args.length) { if (i > 0) { s = s + ", "; } s = s + typeToString(args[i]); i += 1; } s + ">" } else { mt.name } } case TypeParameterType as tp: tp.name case InlineParamType {param}: `inline? ${param.name}` case InlineRecordType {record}: `inline ${typeToString(record)}` case EnumType as et: et.name case TypeAliasType as ta: { let {typeArguments} = ta; if (typeArguments != null) { let sb = new StringBuilder(); let args = typeArguments; sb.append(ta.name); sb.append("<"); for (var i = 0; i < args.length; i += 1) { if (i > 0) { sb.append(", "); } sb.append(typeToString(args[i])); } sb.append(">"); sb.toString() } else { ta.name } } case SymbolType as sym: { let {debugName} = sym; if (debugName != null) { `symbol(${debugName})` } else { "symbol" } } case ThisType: "this" }; } // --------------------------------------------------------------------------- // Second-class containment (ownership.md §"The two axes") // --------------------------------------------------------------------------- /** * Whether `t` is a `scoped` type parameter whose values are restricted * where it is being checked: everywhere but inside an * `if (isFirstClass())` branch for it (firstClassDepth). */ export function isRestrictedParam(t: Type): boolean { return t is TypeParameterType && t.isScoped && t.firstClassDepth == 0; } /** * Whether `t` is **second-class**: a value of it may not outlive the extent * it was borrowed from, so it may not be stored in the heap or returned * except to the caller that supplied the borrow it derives from. * * Only `Borrow` is second-class, and only where there is an owner to * outlive. Borrowing an unrestricted value is a no-op — `Borrow` is * `i32`, `Borrow` is `String` — so those instantiations carry no * restrictions at all; see ownership.md §"`Borrow` is the identity at * unrestricted instantiations". * * A borrow of a bare type parameter *is* restricted. A generic body is * checked against the worst case its bound permits, and an unbounded `T` * permits a resource. The restriction is on the generic body only: at a * call site `T` is substituted, so `read` is checked with the * unrestricted `Borrow` and nothing applies. */ export function isSecondClass(t: Type): boolean { // A scoped value is second-class whatever it wraps: it owns a frame // that holds a borrow, so the extent restriction is unconditional // (ownership.md §"Scoped: the fourth corner"). if (isScopedType(t)) { return true; } // A `scoped T` parameter's values are checked at the same // discipline — the worst case the parameter admits. if (isRestrictedParam(t)) { return true; } if (ownershipHandleOf(t) != OwnershipHandle.Borrow) { return false; } let inner = ownershipHandleInner(t); if (inner == null) { return false; } return borrowInnerRestricts(inner); } /** * Whether a value of `t` can carry a second-class value — the * containment test behind the storage bans. Walks unions and pierces * distinct aliases the way typeCarriesOwner does, so a nullable or * aliased spelling (`Scoped | null`, `type Sneak = Borrow`) is * not a storage loophole. */ export function typeContainsSecondClass(t: Type): boolean { return typeContainsSecondClassAtDepth(t, 0); } export function typeContainsSecondClassAtDepth(t: Type, depth: i32): boolean { if (depth > 32) { return false; } if (isSecondClass(t)) { return true; } if (t is UnionType) { for (let m in t.types) { if (typeContainsSecondClassAtDepth(m, depth + 1)) { return true; } } return false; } if (t is TypeAliasType) { if (isOwnershipWrapper(t) || isScopedType(t)) { return false; } // Awaited strips the wrappers by meaning, and a future's payload // cannot be second-class (Future is a storage error), // so the symbolic form is first-class whatever T is. if (t.intrinsicName == 'type.awaited') { return false; } if (t.resolving) { return false; } t.resolving = true; let res = typeContainsSecondClassAtDepth(t.target, depth + 1); t.resolving = false; return res; } // A container derives the restriction from its arguments — // `Array>` and `Array` under a scoped T are // second-class values (ownership.md §"Scoped containers and extent // nesting"). Such instantiations exist only in the sanctioned // shapes; the walk is what restricts the values they produce. if (t is ClassType) { let args = t.typeArguments; if (args != null) { for (let a in args) { if (typeContainsSecondClassAtDepth(a, depth + 1)) { return true; } } } return false; } if (t is InterfaceType) { let iargs = t.typeArguments; if (iargs != null) { for (let a in iargs) { if (typeContainsSecondClassAtDepth(a, depth + 1)) { return true; } } } return false; } if (t is ArrayType) { return typeContainsSecondClassAtDepth(t.elementType, depth + 1); } return false; } /** * Whether a value of `t` can carry an owner — the general containment * test behind ownership.md's "types containing one". Aggressive on * purpose: it pierces distinct aliases and walks every union member, * so the affine-field and structural-member rules stay accurate * however the formation rules for owner-containing types loosen later. * `Borrow` and `Unmanaged` carry no obligation, and a class type never * appears bare while carrying one — a resource class has no unwrapped * form, and a class holding an owner is forced to be a resource. */ export function typeCarriesOwner(t: Type): boolean { if (ownershipHandleOf(t) == OwnershipHandle.Own) { return true; } // An instance of a container of an owner carries it too // (owner-futures.md §"Restricted instantiations"). if (isAffineContainer(t)) { return true; } // A tuple holding an owner carries it (#495). if (t is TupleType) { for (let el in t.elementTypes) { if (typeCarriesOwner(el)) { return true; } } return false; } if (t is InlineTupleType) { for (let el in t.elementTypes) { if (typeCarriesOwner(el)) { return true; } } return false; } if (t is UnionType) { for (let m in t.types) { if (typeCarriesOwner(m)) { return true; } } return false; } if (t is TypeAliasType) { if (isOwnershipWrapper(t)) { return false; } if (t.resolving) { return false; } t.resolving = true; let res = typeCarriesOwner(t.target); t.resolving = false; return res; } return false; } /** * Whether a value of `t` holds an owner that dropping or replacing it * releases, in the types codegen sees: an owner, a tuple or union * holding one, or a `scoped T` container with a `[release]` whose * argument holds one. Codegen erases `Own` to `R`, so a resource * class with no handle is an owner, while `Borrow` and * `Unmanaged` survive the erasure of a type argument * (eraseTypeArgument) and are not. A specialization is keyed by handle * (owner-futures.md §"Specialization"), so in a generic body this * answers for the instantiation. */ export function holdsOwner(t: Type): boolean { return holdsOwnerAt(t, 0); } function holdsOwnerAt(t: Type, depth: i32): boolean { if (depth > 16) { return false; } let next = depth + 1; return match (t) { case ClassType as ct: ct.isResource || containerHoldsOwner(ct, next) case TupleType {elementTypes}: anyHoldsOwner(elementTypes, next) case InlineTupleType {elementTypes}: anyHoldsOwner(elementTypes, next) case UnionType {types}: anyHoldsOwner(types, next) case TypeAliasType as ta: { let handle = ownershipHandleOf(ta); let args = ta.typeArguments; if (handle != OwnershipHandle.None) { handle == OwnershipHandle.Own } else if (isWithDefaultType(ta) && args != null && args.length == 1) { holdsOwnerAt(args[0], next) } else if (ta.isDistinct || ta.intrinsicName != null || ta.resolving) { false } else { ta.resolving = true; let res = holdsOwnerAt(ta.target, next); ta.resolving = false; res } } case _: false }; } function anyHoldsOwner(types: Array, depth: i32): boolean { for (let m in types) { if (holdsOwnerAt(m, depth)) { return true; } } return false; } /** * Whether `ct` is a `scoped T` container that a drop releases, with a * `scoped` argument holding an owner (holdsOwner). */ function containerHoldsOwner(ct: ClassType, depth: i32): boolean { if (releaseMemberOf(ct) != ":release" || !hasReleaseMember(ct)) { return false; } var c: ClassType | null = ct; while (c != null) { let cls = c; let args = cls.typeArguments; if (args != null) { for (var i = 0; i < args.length; i += 1) { if (isScopedClassParam(cls, i) && holdsOwnerAt(args[i], depth)) { return true; } } } c = cls.superType; } return false; } /** * Whether `t` is an instance of a class that holds a restricted * argument and carries an owner in it: a `scoped T` class bound to an * owner, such as a `Future>`, as an affine tuple is * (ownership.md §"Scoped type arguments"). */ export function isAffineContainer(t: Type): boolean { if (t is TypeAliasType) { if (t.isDistinct || t.intrinsicName != null || t.resolving) { return false; } t.resolving = true; let res = isAffineContainer(t.target); t.resolving = false; return res; } if (!(t is ClassType)) { return false; } var c: ClassType | null = t; while (c != null) { let cls = c as ClassType; let args = cls.typeArguments; if (args != null) { for (var i = 0; i < args.length; i += 1) { if (isScopedClassParam(cls, i) && typeCarriesOwner(args[i])) { return true; } } } c = cls.superType; } return false; } /** * The member an implicit drop calls on `owner`: `:dispose` on a * resource class, and `[release]` on a `scoped T` class or a subclass * of one, which releases the owners its `T` values hold: a `Future`'s * when its value lands (owner-futures.md, "Releasing what nobody * took"), or a synthesized one's field by field. */ export function releaseMemberOf(owner: ClassType): String { if (owner.isResource) { return ":dispose"; } var c: ClassType | null = owner; while (c != null) { let cls = c as ClassType; if (scopedTypeParamsOf(cls).length > 0) { return ":release"; } c = cls.superType; } return ":dispose"; } /** * Whether `ct` has a `[release]`, declared or synthesized (a `scoped T` * class with `T` in its fields gets one): what an implicit drop of it * at an owner calls. One with nothing that could hold an owner has none. */ export function hasReleaseMember(ct: ClassType): boolean { return (ct.genericSource ?? ct).members.has(":release"); } /** * Whether the checker synthesized `ct`'s release member * (ClassType.hasSyntheticRelease), read off its declaration. An * instantiation copies the flag when it is made, and one made before * its class finished registering, as `Some` is while `zena:core` * registers, holds a stale false. */ export function synthesizedRelease(ct: ClassType): boolean { return (ct.genericSource ?? ct).hasSyntheticRelease; } /** * `t` as a container whose `T` carries an owner and that an implicit * drop releases, or null: an instance of a `scoped T` class at an * owner, such as a `Future>` or a `Slot>`, when it has a * `[release]` (hasReleaseMember). The checker roots the call and * lowering emits it from the same test. */ export function releasableContainer(t: Type): ClassType | null { if (t is TypeAliasType) { let alias = t as TypeAliasType; if (alias.isDistinct || alias.intrinsicName != null || alias.resolving || isOwnershipWrapper(alias)) { return null; } alias.resolving = true; let res = releasableContainer(alias.target); alias.resolving = false; return res; } if (!(t is ClassType)) { return null; } let ct = t as ClassType; if (!isAffineContainer(ct) || !hasReleaseMember(ct)) { return null; } return ct; } /** Whether `cls`'s declaration marks its type parameter `i` `scoped`. */ export function isScopedClassParam(cls: ClassType, i: i32): boolean { let params = (cls.genericSource ?? cls).typeParameters; return params != null && i < params.length && params[i].isScoped; } /** * Does `t` name any of `params` (by identity)? Asked of a static * member's signature, this is what separates the two kinds of static a * generic class can declare: one that cannot see the class's type * parameters lives on the class itself, one that names them needs them * bound at every call. Asked of a `scoped T` class's field, it is * whether the field holds `T`. */ export function mentionsTypeParams(t: Type, params: Array): boolean { let anyOf = (types: Array): boolean => { for (let each in types) { if (mentionsTypeParams(each, params)) { return true; } } return false; }; return match (t) { case TypeParameterType as tp: { for (let p in params) { if (p === tp) { return true; } } false } case UnionType {types}: anyOf(types) case ArrayType {elementType}: mentionsTypeParams(elementType, params) case TupleType {elementTypes, row}: (row != null && mentionsTypeParams(row, params)) || anyOf(elementTypes) case InlineTupleType {elementTypes}: anyOf(elementTypes) case RecordType {properties, row}: { if (row != null && mentionsTypeParams(row, params)) { return true; } for (let {key} in properties) { if (mentionsTypeParams(properties[key], params)) { return true; } } false } case FunctionType as ft: { if (mentionsTypeParams(ft.returnType, params)) { return true; } anyOf(ft.parameters) } case ClassType as ct: { if (ct.typeArguments == null) false else anyOf(ct.typeArguments as Array) } case InterfaceType as it: { if (it.typeArguments == null) false else anyOf(it.typeArguments as Array) } case MixinType as mt: { if (mt.typeArguments == null) false else anyOf(mt.typeArguments as Array) } case TypeAliasType as ta: { if (ta.typeArguments == null) false else anyOf(ta.typeArguments as Array) } case _: false }; } /** The type parameters `ct`'s declaration marks `scoped`. */ export function scopedTypeParamsOf(ct: ClassType): Array { let scoped = new GrowableArray(); let params = (ct.genericSource ?? ct).typeParameters; if (params != null) { for (let p in params) { if (p.isScoped) { scoped.push(p); } } } return scoped; } /** * The names of the instance fields `ct`'s own declaration gives a type * holding one of its `scoped` type parameters, in declaration order: * what a synthesized `[release]` releases. */ export function scopedFieldNames(ct: ClassType): GrowableArray { let names = new GrowableArray(); let declaring = ct.genericSource ?? ct; let scoped = scopedTypeParamsOf(declaring); if (scoped.length == 0) { return names; } for (let entry in declaring.members.own) { let member = entry.value; if (member is FieldInfo && !member.isStatic && mentionsTypeParams(member.type, scoped)) { names.push(entry.key); } } return names; } /** * Whether a specialization over `t` serves a restricted instantiation: * whether its takes empty a slot, and `isFirstClass()` is false. A * resource class anywhere in `t` means restricted, which is what an * owner is in codegen, since it erases `Own` to `R`. A `Borrow` * is the resource it wraps, and so restricted. An `Unmanaged` is * unrestricted, as the checker treats it: a type argument keeps the * handle (eraseTypeArgument), so its specialization is its own. * `Scoped` is `F`'s answer, since its restriction is the checker's * to enforce. */ export function representsRestricted(t: Type): boolean { if (t is ClassType) { if (t.isResource) { return true; } let args = t.typeArguments; if (args != null) { for (var i = 0; i < args.length; i += 1) { if (isScopedClassParam(t, i) && representsRestricted(args[i])) { return true; } } } return false; } if (t is UnionType) { for (let m in t.types) { if (representsRestricted(m)) { return true; } } return false; } if (t is TupleType) { for (let el in t.elementTypes) { if (representsRestricted(el)) { return true; } } return false; } if (t is InlineTupleType) { for (let el in t.elementTypes) { if (representsRestricted(el)) { return true; } } return false; } if (t is TypeAliasType) { // A handle or `Scoped` is judged by what it wraps, an unmanaged // handle aside. An alias instance keeps its declaration's // unsubstituted target, so a generic one is judged by its // arguments, which over-approximates. if (isOwnershipWrapper(t)) { if (ownershipHandleOf(t) == OwnershipHandle.Unmanaged) { return false; } let inner = ownershipHandleInner(t); return inner != null && representsRestricted(inner); } if (isScopedType(t)) { let inner = scopedInner(t); return inner != null && representsRestricted(inner); } let args = t.typeArguments; if (args != null && t.typeParameters != null) { for (let a in args) { if (representsRestricted(a)) { return true; } } return false; } if (t.resolving) { return false; } t.resolving = true; let res = representsRestricted(t.target); t.resolving = false; return res; } return false; } /** The scoped half of typeContainsSecondClass, for diagnostic wording. */ export function typeContainsScoped(t: Type): boolean { if (isScopedType(t)) { return true; } if (t is UnionType) { for (let m in t.types) { if (typeContainsScoped(m)) { return true; } } return false; } if (t is TypeAliasType) { if (isOwnershipWrapper(t)) { return false; } if (t.resolving) { return false; } t.resolving = true; let res = typeContainsScoped(t.target); t.resolving = false; return res; } return false; } /** * typeContainsSecondClass, excluding `scoped` type parameters. The * symbolic containment a scoped-T signature mentions — `Array` as * a parameter type — is sanctioned, because the argument is checked * where `T` is bound; a concrete second-class argument * (`Array>`) stays a storage error wherever it is written * (ownership.md §"Scoped containers and extent nesting"). */ export function typeContainsConcreteSecondClass(t: Type): boolean { return typeContainsConcreteSecondClassAtDepth(t, 0); } export function typeContainsConcreteSecondClassAtDepth(t: Type, depth: i32): boolean { if (depth > 32) { return false; } if (t is TypeParameterType) { return false; } if (isSecondClass(t)) { return true; } if (t is UnionType) { for (let m in t.types) { if (typeContainsConcreteSecondClassAtDepth(m, depth + 1)) { return true; } } return false; } if (t is TypeAliasType) { if (isOwnershipWrapper(t) || isScopedType(t)) { return false; } if (t.intrinsicName == 'type.awaited') { return false; } if (t.resolving) { return false; } t.resolving = true; let res = typeContainsConcreteSecondClassAtDepth(t.target, depth + 1); t.resolving = false; return res; } if (t is ClassType) { let args = t.typeArguments; if (args != null) { for (let a in args) { if (typeContainsConcreteSecondClassAtDepth(a, depth + 1)) { return true; } } } return false; } if (t is InterfaceType) { let iargs = t.typeArguments; if (iargs != null) { for (let a in iargs) { if (typeContainsConcreteSecondClassAtDepth(a, depth + 1)) { return true; } } } return false; } if (t is ArrayType) { return typeContainsConcreteSecondClassAtDepth(t.elementType, depth + 1); } return false; } /** * Whether borrowing `inner` is restricted. A union inner — a merged * `Borrow | Borrow` — restricts when ANY member does: a value of * the union may dynamically be the restricted member, and dropping the * restriction there would let that arm escape its owner's extent. */ export function borrowInnerRestricts(inner: Type): boolean { if (inner is TypeParameterType) { return true; } if (inner is ClassType) { return inner.isResource; } if (inner is UnionType) { for (let m in inner.types) { if (borrowInnerRestricts(m)) { return true; } } } return false; }