compiler 0.0.2-preview.1
The Zena self-hosted compiler
compiler#
The Zena compiler, written in Zena. It parses, type-checks, and compiles Zena source code to WebAssembly (Wasm GC) and WebAssembly Text (WAT).
Usage#
Parsing a Single File#
Use compiler/parser to parse Zena source text into an AST (Module):
import { parse } from 'compiler/parser';
let ast = parse('export let answer = 42;', 'example.zena');
Loading and Checking a Program#
Use compiler (createCompiler and checkCompilation) with a CompilerHost to resolve imports across a module graph and type-check a program:
import {
createCompiler, checkCompilation, buildStdlibConfig
} from 'compiler';
import { FsCompilerHost } from 'compiler/fs-host';
let stdlibRoot = '/stdlib';
let host = new FsCompilerHost(stdlibRoot);
let packages = buildStdlibConfig(stdlibRoot, 'host');
let compiler = createCompiler(host, {
stdlibRoot,
packages,
});
let result = await compiler.compile({
entry: '/workspace/main.zena',
target: 'host',
});
let checked = checkCompilation(result);
Compiling a File to WebAssembly#
Use compiler/compile-file to compile an entry file on disk to a .wasm or .wat output file:
import { compileFile } from 'compiler/compile-file';
let ok = await compileFile({
entry: 'src/main.zena',
outPath: 'out/main.wasm',
stdlibRoot: '/stdlib',
});
Libraries#
compiler/compiler/compiler— compiler entry point (Compiler,createCompiler,checkCompilation,ProgramCheckResult)compiler/compile-file— end-to-end file compilation (compileFile,CompileFileOptions)compiler/tokenizer— lexer and token definitions (tokenize,Token,TokenType)compiler/parser— recursive-descent parser (parse,Parser)compiler/ast— AST node definitions (Node,Module,Statement,Expression,TypeAnnotation)compiler/visitor— AST traversal helpers (walk,Visitor)compiler/scope— lexical scope and symbol resolution (ScopeBuilder,ScopeResult,Symbol)compiler/checker— static type checker (checkModule,CheckResult)compiler/semantic-model— semantic queries over a checked module (SemanticModel)compiler/types— compiler type representations (Type,ClassType,FunctionType,typeToString)compiler/diagnostics— compiler diagnostics and source spans (Diagnostic,DiagnosticCode,DiagnosticSeverity,SourceSpan)compiler/package-manifest—zena-package.jsonmanifest and workspace loader (loadWorkspace,loadPackageMap)compiler/module-resolver— package and relative module specifier resolution (ModuleResolver,PackageConfig)compiler/library-loader— module graph loader (LibraryLoader,CompilerHost,SourceFile)compiler/codegen/binary-generator— WebAssembly GC binary emitter (BinaryGenerator)compiler/codegen/wat-generator— WebAssembly Text (WAT) emitter (WatGenerator)
License#
MIT
169.0 KiB
Raw
/**
* 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<T>(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<TypeId> {
return new IdGenerator<TypeId>((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<TypeMark>();
/** 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<TypeMark> {
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<i32>(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<String>();
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<Type>, 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<String>();
/**
* 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<anyref>` is a type a program can write
* and construct, while `FixedArray<T>` 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<i32>` stores an i32 field where `Array<anyref>` 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<var T>` 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<Type>, row: TypeParameterType | null, rowIndex: i32)
case InlineTupleType(elementTypes: Array<Type>)
// `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<Type>)
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<this>`
* 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<this>` — the default, spelled out. */
Borrowing,
/** `this: Own<this>` — 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 (`<scope>::#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 (`<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<TypeParameterType> | null, typeArgs: Array<Type> | null, t: Type) => Type) | null = null;
export function setMemberTypeSubstitution(
substitute: (typeParams: Array<TypeParameterType> | null, typeArgs: Array<Type> | 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<TypeParameterType> | null,
typeArgs: Array<Type> | 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<MapEntry<String, MemberInfo>> implements Iterable<MapEntry<String, MemberInfo>> {
[Iterable.iterator](): Iterator<MapEntry<String, MemberInfo>> {
let entries = new Array<MapEntry<String, MemberInfo>>();
for (let key in this.keys()) {
let member = this.lookup(key);
if (member != null) {
entries.push(new MapEntry<String, MemberInfo>(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<String, MemberInfo>();
/** Keys every read reports absent until `unhideAll`; null when none. */
var #hidden: HashSet<String> | null = null;
var #inheritedCache: HashMap<String, MemberInfo> | null = null;
var #keysCache: GrowableArray<String> | 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<String, MemberInfo> {
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<String>();
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<String> {
this.#validateCache();
var all = this.#keysCache;
if (all == null) {
let out = new Array<String>();
let seen = new Set<String>();
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<String>;
}
let visible = new Array<String>();
for (let key in all as GrowableArray<String>) {
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<String, MemberInfo>;
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<String>, seen: HashSet<String>): 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<String, MemberInfo>();
this.#keysCache = null;
this.#cacheEpoch = memberTableEpoch;
this.#cacheParent = parent;
this.#cacheParentCount = parentCount;
}
}
}
export final class RecordType(
properties: HashMap<String, Type>,
optionalProperties: HashSet<String> | 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<String> | null;
parameterSymbols: GrowableArray<SymbolId> | null;
parameterInitializers: GrowableArray<Expression | null> | null;
optionalParameters: GrowableArray<boolean> | 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<Type>,
returnType: Type,
info: FunctionDeclInfo | null,
typeParameters: Array<TypeParameterType> | null = null,
typeArguments: Array<Type> | null = null,
genericSource: FunctionType | null = null,
overloads: GrowableArray<FunctionType> | 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<Type>;
returnType: Type;
info: FunctionDeclInfo | null;
typeParameters: Array<TypeParameterType> | null;
typeArguments: Array<Type> | null;
genericSource: FunctionType | null;
var overloads: GrowableArray<FunctionType> | 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<TypeParameterType> | 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<String> | null {
get {
let info = this.info;
return if (info != null) info.parameterNames else null;
}
}
parameterSymbols: GrowableArray<SymbolId> | null {
get {
let info = this.info;
return if (info != null) info.parameterSymbols else null;
}
}
parameterInitializers: GrowableArray<Expression | null> | null {
get {
let info = this.info;
return if (info != null) info.parameterInitializers else null;
}
}
optionalParameters: GrowableArray<boolean> | 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<TypeParameterType> | null = null;
var typeArguments: Array<Type> | null = null;
var superType: ClassType | null = null;
var implementsList: GrowableArray<InterfaceType> = new Array<InterfaceType>();
var mixins: GrowableArray<MixinType> = new Array<MixinType>();
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<String, DecoratedField> | 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<T>`. 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<String, Type> = new OrderedHashMap<String, Type>();
var constructorType: FunctionType | null = null;
var constructors: HashMap<String, FunctionType> = new Map<String, FunctionType>();
var fieldSetterNames: HashMap<String, String> | 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<String> | null = null;
var sealedVariants: GrowableArray<ClassType> | null = null;
var forwardVariantNames: HashSet<String> | 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<String, ClassType> | 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 (`"<scope>::#<subject>"`), 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<K, V>`, `Iterator<T>`'s methods return
* `Iterator<T>` — 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<SubstitutionFrame>();
/**
* 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<i32>;
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<TypeListEntry | null>;
var #mask: i32;
var #count: i32 = 0;
var #limit: i32;
#probe = new Array<i32>(8);
new(capacity: i32 = 8)
: #slots = new FixedArray<TypeListEntry | null>(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<Type>): 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<Type>): 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<i32>(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<TypeListEntry | null>(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<i32>, probe: GrowableArray<i32>): 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<i32>(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<Type>): UnionType {
var canonical: GrowableArray<Type> | 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<Type>(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<String, Type>,
optionals: HashSet<String> | null,
row: Type
): Type {
match (row) {
case RecordType as r: {
let props = new Map<String, Type>();
var opts: HashSet<String> | null = null;
for (let key in r.properties.keys()) {
props[key] = r.properties[key];
if (r.isOptional(key)) {
opts ??= new Set<String>();
opts.add(key);
}
}
for (let key in fields.keys()) {
props[key] = fields[key];
if (optionals != null && optionals.has(key)) {
opts ??= new Set<String>();
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<Type>,
rowIndex: i32,
row: Type
): Type {
match (row) {
case TupleType as r: {
let out = new Array<Type>();
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<TypeParameterType> | null,
typeArguments: Array<Type>
): 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<Type>();
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<Type>();
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<Type>();
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<String, Type>();
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<Type>();
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<Type>();
let ctParams = (ct.genericSource ?? ct).typeParameters;
if (ct.typeArguments != null) {
hasArgs = true;
let targs = ct.typeArguments as Array<Type>;
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<Type>(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<K, V>` 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<InterfaceType>();
stale.mixins = new Array<MixinType>();
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<TypeParameterType>();
let combinedArgs = new Array<Type>();
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<Type>();
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<String, FunctionType>();
for (let entry in template.constructors) {
let ctorName = entry.key;
let ctor = entry.value;
let newParams = new Array<Type>();
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<Type>();
let itParams = (it.genericSource ?? it).typeParameters;
if (it.typeArguments != null) {
hasArgs = true;
let targs = it.typeArguments as Array<Type>;
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<Type>();
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<TypeParameterType>();
let combinedArgs = new Array<Type>();
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<InterfaceType>();
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<Type>();
let aliasParams = alias.typeParameters;
if (alias.typeArguments != null) {
hasArgs = true;
let targs = alias.typeArguments as Array<Type>;
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<Type>();
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<Type>();
let mtParams = mt.typeParameters;
if (mt.typeArguments != null) {
hasArgs = true;
let targs = mt.typeArguments as Array<Type>;
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<Type>();
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<i32>` 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<Item>` 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<imm "}${instantiationKeyOf(elementType)}>`
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<Type>)
} 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<Type>)
} 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<Type>)
} 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<Type>)
} else {
base
}
}
case _: typeToString(t)
};
}
/** `Name<key,key,...>` for a generic nominal type's cache key. */
function namedKey(name: String, args: Array<Type>): 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<Type>): Array<Type> {
if (arr is GrowableArray<Type>) {
return arr as GrowableArray<Type>;
}
let g = new Array<Type>(arr.length);
var i = 0;
let len = arr.length;
while (i < len) {
g.push(arr[i]);
i += 1;
}
return g;
}
function getInstantiationKey(typeArguments: Array<Type>) {
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<Type>,
): ClassType {
let key = getInstantiationKey(typeArguments);
let instantiations = source.instantiations ?? new Map<String, ClassType>();
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<InterfaceType>();
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<MixinType>();
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<Type>();
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<String, FunctionType>();
for (let entry in source.constructors) {
let ctorName = entry.key;
let ctor = entry.value;
let newParams = new Array<Type>();
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<Type>,
): FunctionType {
let newParams = new Array<Type>();
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<TypeParameterType> | null = null;
var typeArguments: Array<Type> | null = null;
var extendsList: GrowableArray<InterfaceType> = new Array<InterfaceType>();
/** 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<String, Type> = new OrderedHashMap<String, Type>();
var genericSource: InterfaceType | null = null;
var interfaceKey: String | null = null;
var sourcePath: String = "";
/** As `ClassType.instantiations`: null until the first instantiation. */
var instantiations: HashMap<String, InterfaceType> | null = null;
/**
* The interface's constructors, keyed like a class's: "<constructor>"
* 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<String, FunctionType> = new Map<String, FunctionType>();
/** 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<Type>,
): InterfaceType {
let key = getInstantiationKey(typeArguments);
let instantiations = source.instantiations ?? new Map<String, InterfaceType>();
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<i32> vs MyMixin<String>), 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<TypeParameterType> | null = null;
var typeArguments: Array<Type> | 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<String, Type> = new OrderedHashMap<String, Type>();
var genericSource: MixinType | null = null;
var sourcePath: String = "";
var mixins: GrowableArray<MixinType> = new Array<MixinType>();
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<String> | null = null;
/** As `ClassType.instantiations`: null until the first instantiation. */
var instantiations: HashMap<String, MixinType> | 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<Type>,
): MixinType {
let key = getInstantiationKey(typeArguments);
let instantiations = source.instantiations ?? new Map<String, MixinType>();
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<MixinType>();
// 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<T>())` 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<String> | null = null;
new(this.name, this.constraint, this.defaultType) : super() {
_typeParameterTypes += 1;
}
}
export final class TypeAliasType(
name: String,
var typeParameters: Array<TypeParameterType> | null,
var target: Type,
isDistinct: boolean,
var typeArguments: Array<Type> | 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<i32>` and
* `FromRange<i32>`: 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<T>` (ownership.md §"Scoped<T>: 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<R>, 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<T>`, or null if `t` is not one. Reads
* `typeArguments` rather than `target` for the same reason
* ownershipHandleInner does: `Scoped<T> = 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<T>()` branch.
*/
export function isScopedValueType(t: Type): boolean {
if (isScopedType(t)) { return true; }
return isRestrictedParam(t);
}
/** Whether `t` is an instance of the `WithDefault<T>` 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<R>`, 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<Own<R>>`, which its `await` consumes, or a union with
* such a member, such as an `Option<Own<R>>`.
*/
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<ClassType> {
let found = new Array<ClassType>();
let resolved = unwrapAliases(soleNonNullMember(t) ?? t);
let members = if (let UnionType {types} = resolved) types else growable<Type>([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> = 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<Type>;
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<Type>;
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<Type>;
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<Type>;
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<U>` 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<Scoped<Future<U>>>
// 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<Type>();
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<T>` 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<T>()` 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<Type>();
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<T, R>` is `Scoped<R>` 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<R> — 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<Type>([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<Type>
): 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<void>` 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<Type>, optionals: GrowableArray<boolean> | 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<T>`,
* or a generic class over it (`FixedArray<T>`, `Array<T>`) 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: "<error>"
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<T>`, 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<T>())` 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<R>` is second-class, and only where there is an owner to
* outlive. Borrowing an unrestricted value is a no-op — `Borrow<i32>` is
* `i32`, `Borrow<String>` is `String` — so those instantiations carry no
* restrictions at all; see ownership.md §"`Borrow<T>` 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<i32>` is checked with the
* unrestricted `Borrow<i32>` 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<T>: 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<F> | null`, `type Sneak = Borrow<R>`) 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<T> strips the wrappers by meaning, and a future's payload
// cannot be second-class (Future<second-class> 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<Scoped<F>>` and `Array<T>` 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<R>` to `R`, so a resource
* class with no handle is an owner, while `Borrow<R>` and
* `Unmanaged<R>` 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<Type>, 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<Own<R>>`, 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<T>` 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<Own<R>>` or a `Slot<Own<R>>`, 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<TypeParameterType>): boolean {
let anyOf = (types: Array<Type>): 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<Type>)
}
case InterfaceType as it: {
if (it.typeArguments == null) false else anyOf(it.typeArguments as Array<Type>)
}
case MixinType as mt: {
if (mt.typeArguments == null) false else anyOf(mt.typeArguments as Array<Type>)
}
case TypeAliasType as ta: {
if (ta.typeArguments == null) false else anyOf(ta.typeArguments as Array<Type>)
}
case _: false
};
}
/** The type parameters `ct`'s declaration marks `scoped`. */
export function scopedTypeParamsOf(ct: ClassType): Array<TypeParameterType> {
let scoped = new GrowableArray<TypeParameterType>();
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<String> {
let names = new GrowableArray<String>();
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<T>()` is false. A
* resource class anywhere in `t` means restricted, which is what an
* owner is in codegen, since it erases `Own<R>` to `R`. A `Borrow<R>`
* is the resource it wraps, and so restricted. An `Unmanaged<R>` is
* unrestricted, as the checker treats it: a type argument keeps the
* handle (eraseTypeArgument), so its specialization is its own.
* `Scoped<F>` 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<T>` as
* a parameter type — is sanctioned, because the argument is checked
* where `T` is bound; a concrete second-class argument
* (`Array<Scoped<F>>`) 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<A> | Borrow<B>` — 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;
}
- zena-lang:wit-parser wit-parser.zena-lang.pkg.zena-lang.dev ~0.0.1-preview.1
| Version | Published | Dependencies | Approved by |
|---|---|---|---|
| 0.0.2-preview.1 | 2026-11-19 |
|
|