compiler 0.0.2-preview.1

The Zena self-hosted compiler

Readme Files Dependencies Versions

compiler#

The Zena compiler, written in Zena. It parses, type-checks, and compiles Zena source code to WebAssembly (Wasm GC) and WebAssembly Text (WAT).

Usage#

Parsing a Single File#

Use compiler/parser to parse Zena source text into an AST (Module):

import { parse } from 'compiler/parser';

let ast = parse('export let answer = 42;', 'example.zena');

Loading and Checking a Program#

Use compiler (createCompiler and checkCompilation) with a CompilerHost to resolve imports across a module graph and type-check a program:

import {
  createCompiler, checkCompilation, buildStdlibConfig
} from 'compiler';
import { FsCompilerHost } from 'compiler/fs-host';

let stdlibRoot = '/stdlib';
let host = new FsCompilerHost(stdlibRoot);
let packages = buildStdlibConfig(stdlibRoot, 'host');
let compiler = createCompiler(host, {
  stdlibRoot,
  packages,
});

let result = await compiler.compile({
  entry: '/workspace/main.zena',
  target: 'host',
});
let checked = checkCompilation(result);

Compiling a File to WebAssembly#

Use compiler/compile-file to compile an entry file on disk to a .wasm or .wat output file:

import { compileFile } from 'compiler/compile-file';

let ok = await compileFile({
  entry: 'src/main.zena',
  outPath: 'out/main.wasm',
  stdlibRoot: '/stdlib',
});

Libraries#

  • compiler / compiler/compiler — compiler entry point (Compiler, createCompiler, checkCompilation, ProgramCheckResult)
  • compiler/compile-file — end-to-end file compilation (compileFile, CompileFileOptions)
  • compiler/tokenizer — lexer and token definitions (tokenize, Token, TokenType)
  • compiler/parser — recursive-descent parser (parse, Parser)
  • compiler/ast — AST node definitions (Node, Module, Statement, Expression, TypeAnnotation)
  • compiler/visitor — AST traversal helpers (walk, Visitor)
  • compiler/scope — lexical scope and symbol resolution (ScopeBuilder, ScopeResult, Symbol)
  • compiler/checker — static type checker (checkModule, CheckResult)
  • compiler/semantic-model — semantic queries over a checked module (SemanticModel)
  • compiler/types — compiler type representations (Type, ClassType, FunctionType, typeToString)
  • compiler/diagnostics — compiler diagnostics and source spans (Diagnostic, DiagnosticCode, DiagnosticSeverity, SourceSpan)
  • compiler/package-manifest — zena-package.json manifest and workspace loader (loadWorkspace, loadPackageMap)
  • compiler/module-resolver — package and relative module specifier resolution (ModuleResolver, PackageConfig)
  • compiler/library-loader — module graph loader (LibraryLoader, CompilerHost, SourceFile)
  • compiler/codegen/binary-generator — WebAssembly GC binary emitter (BinaryGenerator)
  • compiler/codegen/wat-generator — WebAssembly Text (WAT) emitter (WatGenerator)

License#

MIT

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;
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19