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

57.2 KiB Raw
import { 
  Node, MethodDefinition, FieldDefinition, AccessorDeclaration, MixinDeclaration, ClassDeclaration, TypeAnnotation, NodeId, Identifier
} from '../ast.zena';
import { 
  Type, I32Type, U32Type, I64Type, U64Type, F32Type, F64Type,
  U8Type, U16Type, I8Type, I16Type, V128Type, BooleanType, BoolLiteralType,
  NullType, VoidType, ClassType, InterfaceType, ArrayType, RecordType,
  TupleType, InlineTupleType, InlineParamType, InlineRecordType, inlineOf, UnionType, TypeParameterType, FunctionType, UnknownType, typeToString,
  MixinType, MixinKey, instantiateClassType, TypeAliasType, EnumType, ErrorType, HoleType, NeverType, ThisType,
  AnyRefType, EqRefType, ExternRefType, StringLiteralType, NumLiteralType, baseType, ErasedType,
  MethodInfo, countTypeKey, countCodegenFunctionType, internFunctionType, mergeRow, mergeTupleRow,
  recursiveAliasKey, integerLiteralMagnitude, integerLiteralRadix, stripNumericUnderscores,
  OwnershipHandle, ownershipHandleOf, ownershipHandleInner, representsRestricted, isScopedType,
  scopedInner } from '../types.zena';
import { SemanticModel } from '../semantic-model.zena';
import { Symbol, SymbolId, noSymbolId } from '../scope/symbol.zena';
import { Program, CompilationUnit } from '../program.zena';
import { HashMap } from 'zena:collections';

export { MixinKey } from '../types.zena';

@intrinsic('hash')
declare function hash<T>(value: T): i32;



/**
 * The hidden i64 bitmask fields carrying optional-field presence on a
 * record struct (docs/design/record-presence.md §2). Word w holds bits
 * for optional fields 64*w .. 64*w+63 in canonical sorted name order.
 * The suffix is zero-padded so canonical field sorting keeps the words
 * in index order.
 */
export function presentWordName(word: i32): String {
  var suffix = i32ToString(word);
  while (suffix.length < 3) {
    suffix = '0' + suffix;
  }
  return '$present' + suffix;
}

export function isPresentWordName(name: String): boolean {
  return name.length == 11 && name.sliceBytes(0, 8) == '$present';
}

export function presentWordCount(optionalCount: i32): i32 {
  return (optionalCount + 63) >> 6;
}

// TODO: Add string comparison to the stdlib and use that instead.
export function compareStrings(a: String, b: String): i32 {
  let lenA = a.length;
  let lenB = b.length;
  let minLen = if (lenB < lenA) lenB else lenA;
  
  for (var i = 0; i < minLen; i += 1) {
    let byteA = a.getByteAt(i);
    let byteB = b.getByteAt(i);
    if (byteA < byteB) return -1;
    if (byteA > byteB) return 1;
  }
  
  if (lenA < lenB) return -1;
  if (lenA > lenB) return 1;
  return 0;
}

/**
 * Returns the highest non-mixin-intermediate ancestor of `classType` (or
 * `classType` itself) that declares `memberName`. Strips specialization
 * (`_spec_...`) and overload (`$...`) suffixes so specialized or
 * overloaded slot names match the member table's declared key.
 */
export function getMemberRootClass(classType: ClassType, memberName: String): ClassType {
  var baseName = memberName;
  if (memberName.contains("_spec_")) {
    baseName = memberName.split("_spec_")[0];
  } else if (!memberName.startsWith("get#") && !memberName.startsWith("set#") &&
      memberName.contains("$")) {
    let prefix = memberName.split("$")[0];
    if (prefix.length > 0) {
      baseName = prefix;
    }
  }
  var rootClass = classType;
  var currClass = classType.superType;
  while (currClass != null) {
    let superCt = currClass;
    if (superCt.isMixinIntermediate) {
      currClass = superCt.superType;
      continue;
    }
    var hasMember = superCt.members.has(memberName);
    if (!hasMember && baseName != memberName) {
      hasMember = superCt.members.has(baseName);
    }
    if (!hasMember && memberName.startsWith("get#")) {
      let propName = memberName.sliceBytes(4, memberName.length);
      hasMember = superCt.members.has(propName);
    }
    if (!hasMember && memberName.startsWith("set#")) {
      let propName = memberName.sliceBytes(4, memberName.length);
      hasMember = superCt.members.has(propName);
    }
    if (hasMember) {
      rootClass = superCt;
    }
    currClass = superCt.superType;
  }
  return rootClass;
}

export distinct type ClassKey = String;
export distinct type InterfaceKey = String;
export distinct type CellKey = String;
export distinct type ClosureKey = String;
export distinct type ExportKey = String;
export distinct type ExportGlobalKey = String;
export distinct type FunctionArgsKey = String;

export final class ClassInterfaceKey implements Hashable {
  classKey: ClassKey;
  interfaceKey: InterfaceKey;
  new(this.classKey, this.interfaceKey);

  hashCode(): i32 {
    return hash(this.classKey) ^ hash(this.interfaceKey);
  }

  operator ==(other: ClassInterfaceKey): boolean {
    return this.classKey == other.classKey && this.interfaceKey == other.interfaceKey;
  }
}

export final class ClassMethodKey implements Hashable {
  classKey: ClassKey;
  methodName: String;
  new(this.classKey, this.methodName);

  hashCode(): i32 {
    return hash(this.classKey) ^ hash(this.methodName);
  }

  operator ==(other: ClassMethodKey): boolean {
    return this.classKey == other.classKey && this.methodName == other.methodName;
  }
}

export final class ClosureSpecializationKey implements Hashable {
  closureId: NodeId;
  classKey: ClassKey;
  // The enclosing FUNCTION's specialization axis, next to the class
  // one: a closure inside `make<T>` exists once per instantiation of
  // `make`, exactly as one inside `Box<T>.method` exists once per Box
  // specialization. Empty outside generic functions.
  funcKey: FunctionArgsKey;
  new(this.closureId, this.classKey, this.funcKey = "" as FunctionArgsKey);

  /**
   * Whether this key names one function-instantiation's copy rather
   * than the per-node template or a class-only specialization.
   */
  specializesFunction(): boolean {
    return (this.funcKey as String).length > 0;
  }

  hashCode(): i32 {
    return (this.closureId as i32) ^ hash(this.classKey) ^ hash(this.funcKey);
  }

  operator ==(other: ClosureSpecializationKey): boolean {
    return this.closureId == other.closureId && this.classKey == other.classKey &&
        this.funcKey == other.funcKey;
  }
}

export final class FunctionAdaptationKey implements Hashable {
  src: Type;
  tgt: Type;
  new(this.src, this.tgt);

  hashCode(): i32 {
    return hash(getTypeUniqueKey(this.src)) ^ hash(getTypeUniqueKey(this.tgt));
  }

  operator ==(other: FunctionAdaptationKey): boolean {
    return getTypeUniqueKey(this.src) == getTypeUniqueKey(other.src) && getTypeUniqueKey(this.tgt) == getTypeUniqueKey(other.tgt);
  }
}

export final class FunctionValueWrapperKey implements Hashable {
  keyName: String;
  signatureKey: String;
  new(this.keyName, this.signatureKey);

  hashCode(): i32 {
    return hash(this.keyName) ^ hash(this.signatureKey);
  }

  operator ==(other: FunctionValueWrapperKey): boolean {
    return this.keyName == other.keyName && this.signatureKey == other.signatureKey;
  }
}

export final class SpecializedFunctionKey implements Hashable {
  baseName: String;
  typeArgs: Array<Type>;
  new(this.baseName, this.typeArgs);

  hashCode(): i32 {
    var h = hash(this.baseName);
    for (let arg in this.typeArgs) {
      h = h ^ hash(getTypeKeyForSpecialization(arg));
    }
    return h;
  }

  operator ==(other: SpecializedFunctionKey): boolean {
    if (this.baseName != other.baseName || this.typeArgs.length != other.typeArgs.length) {
      return false;
    }
    for (var i = 0; i < this.typeArgs.length; i += 1) {
      if (getTypeKeyForSpecialization(this.typeArgs[i]) != getTypeKeyForSpecialization(other.typeArgs[i])) {
        return false;
      }
    }
    return true;
  }
}

// `typeContainsTypeParameter` moved to types.zena (it is a pure function over
// Type, and the checker needs it too). Re-exported here for existing callers.
export { typeContainsTypeParameter } from '../types.zena';

/**
 * An alias instance's target as this instance means it. An instance
 * keeps its declaration's unsubstituted target and carries the
 * arguments alongside (instantiateTypeAliasType), so for an alias whose
 * target is one of its own parameters, `opaque type Own<T> = T` and the
 * other handles, the target is that parameter's argument: `Own<Res>` is
 * `Res`, as eraseTypeParameters lowers it. Read through the bare target,
 * every such instance was the erasure of `T`. Any other alias returns
 * its target.
 */
export function instantiatedAliasTarget(ta: TypeAliasType): Type {
  let params = ta.typeParameters;
  let args = ta.typeArguments;
  let target = ta.target;
  if (params != null && args != null && target is TypeParameterType) {
    for (var i = 0; i < params.length && i < args.length; i += 1) {
      if (params[i] === target) {
        return args[i];
      }
    }
  }
  return target;
}

export function isConcrete(t: Type): boolean {
  return match (t) {
    case TypeParameterType: false
    // An erasure is concrete in the sense this predicate asks about: it
    // is a type, and a slot can hold it. It is NOT something to emit
    // code for — nothing is ever registered at an erasure now (see
    // containsErasedType and registerSpecializedClass), so callers that
    // mean "should this get a body?" must ask that instead.
    case ErasedType: true
    case UnknownType: false
    case ErrorType: false
    case HoleType: false
    case NeverType: true
    case ThisType: false
    case ClassType as ct: {
      let {typeParameters} = ct;
      if (typeParameters != null && typeParameters.length > 0) {
        let args = ct.typeArguments;
        if (args == null) {
          return false;
        }
        var i = 0;
        var concrete = true;
        while (i < args.length) {
          if (!isConcrete(args[i])) { concrete = false; }
          i += 1;
        }
        concrete
      } else {
        true
      }
    }
    case InterfaceType as it: {
      let {typeParameters} = it;
      if (typeParameters != null && typeParameters.length > 0) {
        let args = it.typeArguments;
        if (args == null) {
          return false;
        }
        var i = 0;
        var concrete = true;
        while (i < args.length) {
          if (!isConcrete(args[i])) { concrete = false; }
          i += 1;
        }
        concrete
      } else {
        true
      }
    }
    case ArrayType {elementType}: isConcrete(elementType)
    case TupleType {elementTypes}: {
      var concrete = true;
      for (let el in elementTypes) {
        if (!isConcrete(el)) { concrete = false; }
      }
      concrete
    }
    case InlineParamType: false
    case InlineRecordType {record}: isConcrete(record)
    case InlineTupleType {elementTypes}: {
      var concrete = true;
      for (let el in elementTypes) {
        if (!isConcrete(el)) { concrete = false; }
      }
      concrete
    }
    case UnionType {types}: {
      var concrete = true;
      for (let ut in types) {
        if (!isConcrete(ut)) { concrete = false; }
      }
      concrete
    }
    case RecordType as rec: {
      var concrete = true;
      let keys = rec.properties.keys();
      for (let key in keys) {
        if (!isConcrete(rec.properties[key])) { concrete = false; }
      }
      concrete
    }
    case FunctionType as ft: {
      var concrete = true;
      for (let p in ft.parameters) {
        if (!isConcrete(p)) { concrete = false; }
      }
      if (!isConcrete(ft.returnType)) { concrete = false; }
      concrete
    }
    case EnumType: true
    case TypeAliasType as ta: {
      var concrete = true;
      let targs = ta.typeArguments;
      if (targs != null) {
        for (let arg in targs) {
          if (!isConcrete(arg)) { concrete = false; }
        }
      }
      if (concrete && !ta.resolving) {
        ta.resolving = true;
        if (!isConcrete(instantiatedAliasTarget(ta))) { concrete = false; }
        ta.resolving = false;
      }
      concrete
    }
    case _: true
  };
}


export function getTypeKeyForSpecialization(t: Type): String {
  let cached = t.specializationKeyCache;
  if (cached != null) {
    return cached;
  }
  if (t is TypeAliasType) {
    // Provisional, so a self-referencing alias's target can be keyed
    // without unwrapping the alias again: the name qualified by its
    // module, since the name alone is shared across libraries.
    t.specializationKeyCache = recursiveAliasKey(t);
  }
  let key = getTypeKeyForSpecializationRaw(t);
  t.specializationKeyCache = key;
  countTypeKey(key);
  return key;
}

function getTypeKeyForSpecializationRaw(type: Type): String {
  return match (type) {
    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: "bool"
    case BoolLiteralType: "bool"
    case NullType: "null"
    case VoidType: "void"
    case ClassType as ct: {
      let symId = (ct.genericSource ?? ct).symbolId;
      let base = if (symId != noSymbolId) {
        `${ct.name}_s${i32ToString(symId as i32)}`
      } else {
        let baseId = if (ct.genericSource != null) (ct.genericSource as ClassType).id else ct.id;
        `${ct.name}_t${i32ToString(baseId as i32)}`
      };
      let {typeArguments} = ct;
      if (typeArguments != null && typeArguments.length > 0 && isConcrete(ct)) {
        let args = typeArguments;
        let parts = new Array<String>.fixed(1 + 2 * args.length, "");
        parts[0] = base;
        var i = 0;
        while (i < args.length) {
          parts[1 + 2 * i] = "_";
          parts[2 + 2 * i] = getTypeKeyForSpecialization(args[i]);
          i += 1;
        }
        String.fromParts(parts)
      } else {
        base
      }
    }
    case InterfaceType as it: {
      let symId = (it.genericSource ?? it).symbolId;
      let base = if (symId != noSymbolId) {
        `${it.name}_s${i32ToString(symId as i32)}`
      } else {
        let baseId = if (it.genericSource != null) (it.genericSource as InterfaceType).id else it.id;
        `${it.name}_t${i32ToString(baseId as i32)}`
      };
      let {typeArguments} = it;
      if (typeArguments != null && typeArguments.length > 0 && isConcrete(it)) {
        let args = typeArguments;
        let parts = new Array<String>.fixed(1 + 2 * args.length, "");
        parts[0] = base;
        var i = 0;
        while (i < args.length) {
          parts[1 + 2 * i] = "_";
          parts[2 + 2 * i] = getTypeKeyForSpecialization(args[i]);
          i += 1;
        }
        String.fromParts(parts)
      } else {
        base
      }
    }
    case ArrayType {elementType, elementsMutable}:
      (if (elementsMutable) "arr_" else "arrimm_") + getTypeKeyForSpecialization(elementType)
    case RecordType as rec: {
      let len = rec.properties.size;
      let parts = new Array<String>.fixed(1 + 4 * len, "");
      // An existential lowers to a fat pointer of its own.
      parts[0] = if (rec.isExistential) "recx" else "rec";
      let keys = rec.properties.keys();
      var i = 0;
      for (let key in keys) {
        parts[1 + 4 * i] = "_";
        parts[2 + 4 * i] = if (rec.isOptional(key)) key + "?" else key;
        parts[3 + 4 * i] = "_";
        parts[4 + 4 * i] = getTypeKeyForSpecialization(rec.properties[key]);
        i += 1;
      }
      String.fromParts(parts)
    }
    case TupleType {elementTypes}: {
      let parts = new Array<String>.fixed(1 + 2 * elementTypes.length, "");
      parts[0] = "tup";
      var i = 0;
      while (i < elementTypes.length) {
        parts[1 + 2 * i] = "_";
        parts[2 + 2 * i] = getTypeKeyForSpecialization(elementTypes[i]);
        i += 1;
      }
      String.fromParts(parts)
    }
    case InlineParamType {param}: getTypeKeyForSpecializationRaw(param)
    case InlineRecordType {record}: `inline ${getTypeKeyForSpecializationRaw(record)}`
    case InlineTupleType {elementTypes}: {
      let parts = new Array<String>.fixed(1 + 2 * elementTypes.length, "");
      parts[0] = "itup";
      var i = 0;
      while (i < elementTypes.length) {
        parts[1 + 2 * i] = "_";
        parts[2 + 2 * i] = getTypeKeyForSpecialization(elementTypes[i]);
        i += 1;
      }
      String.fromParts(parts)
    }
    // A type parameter and its erasure key the SAME — a specialization
    // named with `T` still standing and one named with `T` erased are
    // the same physical shape, a top-typed slot — and both key APART
    // from the real `anyref` type, which is a type a program can write
    // and construct. Spelling all three "anyref" made an erasure pass
    // `isConcrete` and gave RTA classes to build for types no value
    // has; see ErasedType in types.zena.
    case TypeParameterType as tp: "erased"
    case ErasedType: "erased"
    case UnionType {types}: {
      let parts = new Array<String>.fixed(1 + 2 * types.length, "");
      parts[0] = "union";
      var i = 0;
      while (i < types.length) {
        parts[1 + 2 * i] = "_";
        parts[2 + 2 * i] = getTypeKeyForSpecialization(types[i]);
        i += 1;
      }
      String.fromParts(parts)
    }
    case FunctionType as ft: {
      let parts = new Array<String>.fixed(3 + 2 * ft.parameters.length, "");
      parts[0] = "func";
      var i = 0;
      while (i < ft.parameters.length) {
        parts[1 + 2 * i] = "_";
        parts[2 + 2 * i] = getTypeKeyForSpecialization(ft.parameters[i]);
        i += 1;
      }
      parts[1 + 2 * ft.parameters.length] = "_";
      parts[2 + 2 * ft.parameters.length] = getTypeKeyForSpecialization(ft.returnType);
      String.fromParts(parts)
    }
    case TypeAliasType as ta: aliasKeyForSpecialization(ta)
    case EnumType as et: getTypeKeyForSpecialization(et.backingType)
    case NeverType: "never"
    case HoleType: "hole"
    case ErrorType: "error"
    case UnknownType: "unknown"
    case AnyRefType: "anyref"
    case EqRefType: "eqref"
    case ExternRefType: "externref"
    case StringLiteralType: "string"
    case NumLiteralType: "number"
    case ThisType: "this"
    case _: "unknown"
  };
}

/**
 * Whether a specialization keeps the alias `ta` apart from what it
 * wraps, as the key of its type argument (aliasKeyForSpecialization)
 * and the erasure of one (eraseTypeArgument) both do. A handle is
 * represented by the resource it wraps, but only an owner's body may
 * release or replace a value, so a `Borrow<R>` and an `Unmanaged<R>`
 * stay apart from `Own<R>`, which is `R`. A handle on an unrestricted
 * type is that type (`Borrow<String>` is `String`). A `Scoped<T>` must
 * be consumed, so it stays apart from `T`.
 */
export function specializesApart(ta: TypeAliasType): boolean {
  let handle = ownershipHandleOf(ta);
  if (handle != OwnershipHandle.None) {
    let inner = ownershipHandleInner(ta);
    return handle != OwnershipHandle.Own && inner != null && representsRestricted(inner);
  }
  return isScopedType(ta) && scopedInner(ta) != null;
}

/** An alias's key: its target's, or its own kind's (specializesApart). */
function aliasKeyForSpecialization(ta: TypeAliasType): String {
  if (!specializesApart(ta)) {
    return getTypeKeyForSpecialization(instantiatedAliasTarget(ta));
  }
  return `${apartKind(ta)}_${getTypeKeyForSpecialization(apartInner(ta))}`;
}

/** The kind an alias kept apart (specializesApart) is keyed with. */
function apartKind(ta: TypeAliasType): String {
  return match (ownershipHandleOf(ta)) {
    case OwnershipHandle.Borrow: "borrow"
    case OwnershipHandle.Unmanaged: "unmanaged"
    case _: "scoped"
  };
}

/** What an alias kept apart (specializesApart) wraps. */
function apartInner(ta: TypeAliasType): Type {
  return (ownershipHandleInner(ta) ?? scopedInner(ta)) as Type;
}

/**
 * Whether `t` is, or contains, the erasure of a type parameter.
 *
 * This is the structural test that used to need context: an erasure and
 * the real top type are now different types (ErasedType in types.zena),
 * so "did this mention come from inside generic code" is a question
 * about the type itself rather than about which walk produced it.
 */
export function containsErasedType(t: Type): boolean {
  return match (t) {
    case ErasedType: true
    // A type parameter still standing and its erasure key the SAME
    // (getTypeKeyForSpecialization), so `Array<T>` and `Array<erased>`
    // ARE one class — `Array_s777_erased`. They must classify the same
    // here too: a mention carrying a bare `T` is an erasure that has
    // not been spelled yet, not a specialization.
    case TypeParameterType: true
    case ArrayType {elementType}: containsErasedType(elementType)
    case ClassType as ct: {
      if (ct.typeArguments == null) { return false; }
      for (let arg in ct.typeArguments as Array<Type>) {
        if (containsErasedType(arg)) { return true; }
      }
      false
    }
    case InterfaceType as it: {
      if (it.typeArguments == null) { return false; }
      for (let arg in it.typeArguments as Array<Type>) {
        if (containsErasedType(arg)) { return true; }
      }
      false
    }
    case MixinType as mt: {
      if (mt.typeArguments == null) { return false; }
      for (let arg in mt.typeArguments as Array<Type>) {
        if (containsErasedType(arg)) { return true; }
      }
      false
    }
    case UnionType {types}: {
      for (let sub in types) {
        if (containsErasedType(sub)) { return true; }
      }
      false
    }
    case EnumType: false
    case TypeAliasType as ta: {
      // A symbolic alias instance (a distinct alias, or an intrinsic
      // operator like Awaited<T> that substitution has not closed):
      // erased-ness lives in its arguments and placeholder target.
      let targs = ta.typeArguments;
      if (targs != null) {
        for (let arg in targs as Array<Type>) {
          if (containsErasedType(arg)) { return true; }
        }
      }
      if (ta.resolving) { return false; }
      ta.resolving = true;
      let res = containsErasedType(instantiatedAliasTarget(ta));
      ta.resolving = false;
      res
    }
    case TupleType {elementTypes}: {
      for (let sub in elementTypes) {
        if (containsErasedType(sub)) { return true; }
      }
      false
    }
    case InlineParamType {param}: containsErasedType(param)
    case InlineRecordType {record}: containsErasedType(record)
    case InlineTupleType {elementTypes}: {
      for (let sub in elementTypes) {
        if (containsErasedType(sub)) { return true; }
      }
      false
    }
    case FunctionType as ft: {
      for (let p in ft.parameters) {
        if (containsErasedType(p)) { return true; }
      }
      containsErasedType(ft.returnType)
    }
    case _: false
  };
}

export function getSpecializedName(baseName: String, typeArgs: Array<Type>): String {
  let len = typeArgs.length;
  let parts = new Array<String>.fixed(2 + 2 * len, "");
  parts[0] = baseName;
  parts[1] = "_spec";
  var i = 0;
  while (i < len) {
    parts[2 + 2 * i] = "_";
    parts[3 + 2 * i] = getTypeKeyForSpecialization(typeArgs[i]);
    i += 1;
  }
  return String.fromParts(parts);
}

export function getClassKey(ct: ClassType): ClassKey {
  let cached = ct.classKey;
  if (cached != null) {
    return cached as ClassKey;
  }
  let key = getTypeKeyForSpecialization(ct) as ClassKey;
  ct.classKey = key as String;
  return key;
}

export function getInterfaceKey(it: InterfaceType): InterfaceKey {
  let cached = it.interfaceKey;
  if (cached != null) {
    return cached as InterfaceKey;
  }
  let key = getTypeKeyForSpecialization(it) as InterfaceKey;
  it.interfaceKey = key as String;
  return key;
}

/**
 * The name an interface constructor's specializations are registered
 * under in `specializedFunctions` (getSpecializedFunctionKey appends the
 * type arguments): the declaring interface's key, then `.new` or
 * `.new.<name>`. RTA mints under it and lowering looks it up.
 */
export function getInterfaceConstructorBaseName(it: InterfaceType, ctorName: String): String {
  let key = getInterfaceKey(it.genericSource ?? it) as String;
  if (ctorName == "<constructor>") {
    return key + ".new";
  }
  return `${key}.new.${ctorName}`;
}

/**
 * Resolves or constructs the MixinKey for the generic mixin declaration.
 * Note that this ignores any parameterized type arguments on the MixinType,
 * since the layout and reachability caches care only about the base mixin declaration.
 */
export function getMixinKey(mt: MixinType): MixinKey {
  let cached = mt.mixinKeyCache;
  if (cached != null) {
    return cached;
  }
  let key = new MixinKey(mt.sourcePath, mt.name);
  mt.mixinKeyCache = key;
  return key;
}

export function getMixinKeyFromSymbol(model: SemanticModel, sym: Symbol): MixinKey {
  let mt = model.getBindingType(sym);
  if (mt == null || !(mt is MixinType)) {
    throw new Error(`Symbol is not a mixin: ${sym.name}`);
  }
  return getMixinKey(mt);
}

export function getClassInterfaceKey(classKey: ClassKey, interfaceKey: InterfaceKey): ClassInterfaceKey {
  return new ClassInterfaceKey(classKey, interfaceKey);
}

export function getClassPrivateFieldKey(classKey: ClassKey, fieldName: String): String {
  return `${classKey as String}::${fieldName}`;
}

export function getClassInterfaceVTableName(cName: ClassKey, iName: InterfaceKey): String {
  return `${cName as String}_${iName as String}_vtable`;
}

export function getInterfaceTrampolineName(cName: ClassKey, iName: InterfaceKey, fieldName: String): String {
  return `${cName as String}_${iName as String}_${fieldName}_trampoline`;
}

export function getClassVTableName(cName: ClassKey): String {
  return `${cName as String}_vtable`;
}

export function getClassSingletonName(cName: ClassKey): String {
  return `${cName as String}_singleton`;
}

export function classInterfaceKeyToString(key: ClassInterfaceKey): String {
  return `${key.classKey as String}::${key.interfaceKey as String}`;
}


/** `<a,b>` for a type's arguments, keyed like `getTypeKey`; empty when
 * it has none. */
function typeArgumentsKey(typeArguments: Array<Type> | null) {
  if (typeArguments == null || typeArguments.length == 0) {
    return "";
  }
  var key = "<";
  for (var i = 0; i < typeArguments.length; i += 1) {
    if (i > 0) {
      key = key + ",";
    }
    key = key + getTypeKey(typeArguments[i]);
  }
  return key + ">";
}

/** `a,b` for a list of types, keyed like `getTypeKey`. */
function typeListKey(types: Array<Type>) {
  var key = "";
  for (var i = 0; i < types.length; i += 1) {
    if (i > 0) {
      key = key + ",";
    }
    key = key + getTypeKey(types[i]);
  }
  return key;
}

/** `rec{a:i32,b?:String}` for a record type, keyed like `getTypeKey`. */
function recordTypeKey(rec: RecordType) {
  // An existential lowers to a fat pointer of its own.
  var key = if (rec.isExistential) "recx{" else "rec{";
  var first = true;
  for (let name in rec.properties.keys()) {
    if (!first) {
      key = key + ",";
    }
    first = false;
    let optional = if (rec.isOptional(name)) "?" else "";
    key = `${key}${name}${optional}:${getTypeKey(rec.properties[name])}`;
  }
  return key + "}";
}

export function getTypeKey(type: Type): String {
  return match (type) {
    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: "bool"
    case BoolLiteralType: "bool"
    case NullType: "null"
    case VoidType: "void"
    // Type arguments are part of the key: `of(b: Box<i32>)` and
    // `of(b: Box<f64>)` are two overloads, and the key is what names
    // each one's function.
    case ClassType as ct: ct.name + typeArgumentsKey(ct.typeArguments)
    case InterfaceType as it: it.name + typeArgumentsKey(it.typeArguments)
    case TypeAliasType as ta: ta.name + typeArgumentsKey(ta.typeArguments)
    case EnumType as et: et.name
    case ArrayType {elementType, elementsMutable}:
      (if (elementsMutable) "arr_" else "arrimm_") + getTypeKey(elementType)
    // A structural type keys by its parts, for the same reason:
    // `visit(fn: (x: i32) => void)` and
    // `visit(fn: (x: i32) => Future<void>)` are two overloads, as are
    // two signatures taking different records, tuples or unions.
    case RecordType as rec: recordTypeKey(rec)
    case TupleType {elementTypes}: `tup(${typeListKey(elementTypes)})`
    case InlineParamType {param}: getTypeKey(param)
    case InlineRecordType {record}: `inline ${getTypeKey(record)}`
    case InlineTupleType {elementTypes}: `tup(${typeListKey(elementTypes)})`
    case UnionType {types}: `union(${typeListKey(types)})`
    case FunctionType as ft:
      `fn(${typeListKey(ft.parameters)})=>${getTypeKey(ft.returnType)}`
    // A type parameter and its erasure key the SAME — a specialization
    // named with `T` still standing and one named with `T` erased are
    // the same physical shape, a top-typed slot — and both key APART
    // from the real `anyref` type, which is a type a program can write
    // and construct. Spelling all three "anyref" made an erasure pass
    // `isConcrete` and gave RTA classes to build for types no value
    // has; see ErasedType in types.zena.
    case TypeParameterType as tp: "erased"
    case ErasedType: "erased"
    case _: "unknown"
  };
}

export function getSignatureKey(funcType: FunctionType): String {
  let len = funcType.parameters.length;
  if (len == 0) {
    return "$void";
  }
  let parts = new Array<String>.fixed(2 * len, "");
  var i = 0;
  while (i < len) {
    parts[2 * i] = "$";
    parts[2 * i + 1] = getTypeKey(funcType.parameters[i]);
    i += 1;
  }
  return String.fromParts(parts);
}

export function getOverloadedFunctionKey(symId: SymbolId, funcType: FunctionType): String {
  return `${i32ToString(symId as i32)}${getSignatureKey(funcType)}`;
}

export function matchOverload(moduleModel: SemanticModel, ft: FunctionType, mDef: MethodDefinition): FunctionType | null {
  if (ft.overloads == null) {
    return null;
  }
  let paramTypes = new Array<Type>();
  for (let p in mDef.params) {
    let sym = moduleModel.resolveDeclaration(p as Node);
    if (sym != null) {
      let pType = moduleModel.getBindingType(sym);
      if (pType != null) {
        paramTypes.push(pType);
      } else {
        paramTypes.push(new UnknownType());
      }
    } else {
      paramTypes.push(new UnknownType());
    }
  }

  let methName = if (let Identifier {name} = mDef.name) name else "";

  // Check if main function type matches
  if (ft.parameters.length == paramTypes.length) {
    var match = true;
    for (var pi = 0; pi < paramTypes.length; pi += 1) {
      if (getTypeUniqueKey(ft.parameters[pi]) != getTypeUniqueKey(paramTypes[pi])) {
        match = false;
      }
    }
    if (match) {
      return ft;
    }
  }
  
  let ovs = ft.overloads as GrowableArray<FunctionType>;
  for (let ov in ovs) {
    if (ov.parameters.length == paramTypes.length) {
      var match = true;
      for (var pi = 0; pi < paramTypes.length; pi += 1) {
        if (getTypeUniqueKey(ov.parameters[pi]) != getTypeUniqueKey(paramTypes[pi])) {
          match = false;
        }
      }
      if (match) {
        return ov;
      }
    }
  }
  return null;
}

export function findMixinDeclaration(program: Program, mt: MixinType): MixinDeclaration | null {
  let path = mt.sourcePath;
  var unitOpt: CompilationUnit | null = null;
  if (let (true, unit) = program.unitsByPath.get(path)) {
    unitOpt = unit;
  } else if (path.startsWith("/")) {
    if (let (true, unit) = program.unitsByPath.get(path.sliceBytes(1, path.length))) {
      unitOpt = unit;
    }
  } else if (let (true, unit) = program.unitsByPath.get("/" + path)) {
    unitOpt = unit;
  }
  if (unitOpt != null) {
    for (let stmt in (unitOpt as CompilationUnit).ast.body) {
      if (stmt is MixinDeclaration) {
        if (stmt.name.name == mt.name) {
          return stmt;
        }
      }
    }
  }
  for (let u in program.units) {
    for (let stmt in u.ast.body) {
      if (stmt is MixinDeclaration) {
        if (stmt.name.name == mt.name) {
          return stmt;
        }
      }
    }
  }
  return null;
}

export function collectMixinMembers(
  program: Program,
  model: SemanticModel,
  mixinAnns: GrowableArray<TypeAnnotation> | null,
  methods: GrowableArray<Node>,
  seen: HashMap<MixinKey, boolean>,
  scopes: GrowableArray<String> | null = null,
  models: GrowableArray<SemanticModel> | null = null
): void {
  if (mixinAnns == null) { return; }
  for (let ann in mixinAnns) {
    let sym = model.resolve(ann);
    if (sym != null) {
      let mt = model.getBindingType(sym);
      if (mt is MixinType) {
        let md = findMixinDeclaration(program, mt);
        if (md != null) {
          let mixinKey = getMixinKey(mt);
          if (!seen.has(mixinKey)) {
            seen[mixinKey] = true;
            collectMixinMembers(program, model, md.mixins, methods, seen, scopes, models);
            // The mixin's private scope key, parallel to `methods`
            // when the caller asks for it: functions compiled from
            // these nodes resolve their "#" fields under this scope
            // (see WasmFunction.privateScopeKey). Read from the
            // MixinType — the key includes the declaration's source
            // path, so it is never rederived from the name.
            let mtRoot = mt.genericSource ?? mt;
            let scope = if (mtRoot.privateScopeKey != null) {
              mtRoot.privateScopeKey as String
            } else {
              mt.name + "_This"
            };
            var mixinModel = model;
            if (let (true, unit) = program.unitsByPath.get(mt.sourcePath)) {
              mixinModel = unit.model;
            }
            for (let member in md.body) {
              if (member is MethodDefinition || member is AccessorDeclaration || member is FieldDefinition) {
                methods.push(member);
                if (scopes != null) {
                  scopes.push(scope);
                }
                if (models != null) {
                  models.push(mixinModel);
                }
              }
            }
          }
        }
      }
    }
  }
}

/**
 * The private scope key of the mixin that declares `member`, when the
 * class declaration `cd` acquires `member` through a mixin (directly
 * or composed) — null for the class's own members. Used by
 * registration paths that reach members via nodes rather than via
 * the member-collection loops.
 */
export function mixinScopeOfMember(
  program: Program,
  model: SemanticModel,
  cd: Node | null,
  member: Node
): String | null {
  match (cd) {
    case ClassDeclaration as cdd: {
      if (cdd.mixins == null) { return null; }
      let members = new Array<Node>();
      let scopes = new Array<String>();
      let seen = new Map<MixinKey, boolean>();
      collectMixinMembers(program, model, cdd.mixins, members, seen, scopes);
      for (var i = 0; i < members.length; i += 1) {
        if (members[i] === member) {
          return scopes[i];
        }
      }
    }
    case _: {}
  }
  return null;
}

export function mixinModelOfMember(
  program: Program,
  model: SemanticModel,
  cd: Node | null,
  member: Node
): SemanticModel | null {
  match (cd) {
    case ClassDeclaration as cdd: {
      if (cdd.mixins == null) { return null; }
      let members = new Array<Node>();
      let seen = new Map<MixinKey, boolean>();
      let models = new Array<SemanticModel>();
      collectMixinMembers(program, model, cdd.mixins, members, seen, null, models);
      for (var i = 0; i < members.length; i += 1) {
        if (members[i] === member) {
          return models[i];
        }
      }
    }
    case _: {}
  }
  return null;
}

/**
 * The private scope key of the mixin declaration a node sits inside
 * LEXICALLY — null for nodes written in a class body or at top level.
 *
 * Privacy is a property of where the source text was written, not of
 * which registration path produced a function, so this walks the AST
 * parent chain rather than consulting the member-collection loops.
 * That is what makes it answer for the functions those loops never
 * name: a closure inside a mixin method, a monomorphized copy of a
 * generic mixin method. Both used to reach lowering with no scope and
 * silently bind the HOST class's same-named private.
 *
 * The walk stops at a ClassDeclaration — classes do not nest inside
 * mixin bodies, so a class member's answer costs one step.
 */
export function mixinScopeOfNode(model: SemanticModel, node: Node): String | null {
  var cur: Node | null = node;
  while (cur != null) {
    let c = cur;
    if (c is ClassDeclaration) { return null; }
    if (c is MixinDeclaration) {
      let sym = model.resolve(c);
      if (sym == null) { return null; }
      let mt = model.getBindingType(sym);
      if (mt == null || !(mt is MixinType)) { return null; }
      // Read the key from the MixinType — it carries the declaration's
      // source path, so two same-named mixins from different modules
      // are different scopes. Never rederive it from the name.
      let mtRoot = mt.genericSource ?? mt;
      let {privateScopeKey} = mtRoot;
      if (privateScopeKey != null) {
        return privateScopeKey;
      }
      return mt.name + "_This";
    }
    cur = model.getParent(c);
  }
  return null;
}

export function collectMixinFields(
  program: Program,
  model: SemanticModel,
  mixinAnns: GrowableArray<TypeAnnotation> | null,
  fields: GrowableArray<FieldDefinition>,
  scopes: GrowableArray<String>,
  seen: HashMap<MixinKey, boolean>
): void {
  if (mixinAnns == null) { return; }
  for (let ann in mixinAnns) {
    let sym = model.resolve(ann);
    if (sym != null) {
      let mt = model.getBindingType(sym);
      if (mt is MixinType) {
        let md = findMixinDeclaration(program, mt);
        if (md != null) {
          let mixinKey = getMixinKey(mt);
          if (!seen.has(mixinKey)) {
            seen[mixinKey] = true;
            collectMixinFields(program, model, md.mixins, fields, scopes, seen);
            // The mixin's private-field scope key: struct fields for
            // this mixin's privates are named "<scope>::#name" in
            // every host (see ClassType.privateScopeKey). Empty for
            // public fields' purposes — callers only apply it to
            // "#"-prefixed names.
            let mtRoot = mt.genericSource ?? mt;
            let scope = if (mtRoot.privateScopeKey != null) {
              mtRoot.privateScopeKey as String
            } else {
              mt.name + "_This"
            };
            for (let member in md.body) {
              if (member is FieldDefinition) {
                fields.push(member);
                scopes.push(scope);
              }
            }
          }
        }
      }
    }
  }
}

export function substituteTypeParams(
  typeParams: Array<TypeParameterType> | null,
  typeArgs: Array<Type> | null,
  t: Type
): Type {
  if (typeParams == null || typeArgs == null) { return t; }
  let tpLen = typeParams.length;
  let taLen = typeArgs.length;

  return match (t) {
    case TypeParameterType {name}: {
      for (var i = 0; i < tpLen && i < taLen; i += 1) {
        if (typeParams[i].name == name) {
          return typeArgs[i];
        }
      }
      t
    }
    case UnionType {types}: {
      let substituted = new Array<Type>();
      for (let subtype in types) {
        substituted.push(substituteTypeParams(typeParams, typeArgs, subtype));
      }
      new UnionType(substituted)
    }
    case ArrayType {elementType, elementsMutable}: {
      let subElem = substituteTypeParams(typeParams, typeArgs, elementType);
      new ArrayType(subElem, elementsMutable)
    }
    case TupleType {elementTypes, row, rowIndex}: {
      let subElems = new Array<Type>();
      for (let elem in elementTypes) {
        subElems.push(substituteTypeParams(typeParams, typeArgs, elem));
      }
      if (row != null) {
        return mergeTupleRow(subElems, rowIndex,
            substituteTypeParams(typeParams, typeArgs, row));
      }
      new TupleType(subElems, null, 0)
    }
    case InlineTupleType {elementTypes}: {
      let subElems = new Array<Type>();
      for (let elem in elementTypes) {
        subElems.push(substituteTypeParams(typeParams, typeArgs, elem));
      }
      new InlineTupleType(subElems)
    }
    case InlineParamType {param}:
      inlineOf(substituteTypeParams(typeParams, typeArgs, param))
    case InlineRecordType {record}: {
      let sub = substituteTypeParams(typeParams, typeArgs, record);
      if (sub is RecordType) new InlineRecordType(sub) as Type else t
    }
    case RecordType as rec: {
      let subProps = new Map<String, Type>();
      for (let pair in rec.properties) {
        subProps[pair.key] = substituteTypeParams(typeParams, typeArgs, pair.value);
      }
      let row = rec.row;
      if (row != null) {
        return mergeRow(subProps, rec.optionalProperties,
            substituteTypeParams(typeParams, typeArgs, row));
      }
      let res = new RecordType(subProps, rec.optionalProperties, null, rec.isExistential);
      res
    }
    case FunctionType as ft: {
      let subParams = new Array<Type>();
      for (let param in ft.parameters) {
        subParams.push(substituteTypeParams(typeParams, typeArgs, param));
      }
      let subRet = substituteTypeParams(typeParams, typeArgs, ft.returnType);
      let res = internFunctionType(subParams, subRet, ft.info, ft.typeParameters, ft.typeArguments, ft.genericSource, ft.overloads);
      res.functionSymbolId = ft.functionSymbolId;
      res.functionSymbolName = ft.functionSymbolName;
      countCodegenFunctionType(10);
      res
    }
    case ClassType as ct: {
      let {typeArguments} = ct;
      if (typeArguments != null) {
        let srcArgs = typeArguments;
        let subArgs = new Array<Type>();
        for (let arg in srcArgs) {
          subArgs.push(substituteTypeParams(typeParams, typeArgs, arg));
        }
        instantiateClassType(ct.genericSource ?? ct, subArgs)
      } else {
        ct
      }
    }
    case _: t
  };
}

export function unwrapAliases(t: Type): Type {
  var curr = t;
  while (curr is TypeAliasType) {
    curr = curr.target;
  }
  // An inline record has its record's structure; only a parameter or a
  // `let` holds it differently (docs/design/inline-parameters.md).
  if (curr is InlineRecordType) {
    curr = curr.record;
  }
  if (curr is EnumType) {
    return baseType((curr as EnumType).backingType);
  }
  return baseType(curr);
}

export function getTypeUniqueKey(t: Type): String {
  let cached = t.uniqueKeyCache;
  if (cached != null) {
    return cached;
  }
  if (t is TypeAliasType) {
    t.uniqueKeyCache = "alias_" + recursiveAliasKey(t);
  }
  let key = getTypeUniqueKeyRaw(t);
  t.uniqueKeyCache = key;
  countTypeKey(key);
  return key;
}

function getTypeUniqueKeyRaw(t: Type): String {
  return match (t) {
  case ClassType as ct: {
    let baseId = if (ct.genericSource != null) (ct.genericSource as ClassType).id else ct.id;
    let base = `${ct.name}_${i32ToString(baseId as i32)}`;
    let {typeArguments} = ct;
    if (typeArguments != null) {
      let args = typeArguments;
      let len = args.length;
      if (len > 0) {
        let parts = new Array<String>.fixed(2 * len + 2, "");
        parts[0] = base;
        parts[1] = "<";
        parts[2] = getTypeUniqueKey(args[0]);
        var i = 1;
        while (i < len) {
          parts[2 * i + 1] = ", ";
          parts[2 * i + 2] = getTypeUniqueKey(args[i]);
          i += 1;
        }
        parts[2 * len + 1] = ">";
        String.fromParts(parts)
      } else {
        base
      }
    } else {
      base
    }
  }
  case InterfaceType as it: {
    let baseId = if (it.genericSource != null) (it.genericSource as InterfaceType).id else it.id;
    let base = `${it.name}_${i32ToString(baseId as i32)}`;
    let {typeArguments} = it;
    if (typeArguments != null) {
      let args = typeArguments;
      let len = args.length;
      if (len > 0) {
        let parts = new Array<String>.fixed(2 * len + 2, "");
        parts[0] = base;
        parts[1] = "<";
        parts[2] = getTypeUniqueKey(args[0]);
        var i = 1;
        while (i < len) {
          parts[2 * i + 1] = ", ";
          parts[2 * i + 2] = getTypeUniqueKey(args[i]);
          i += 1;
        }
        parts[2 * len + 1] = ">";
        String.fromParts(parts)
      } else {
        base
      }
    } else {
      base
    }
  }
  case ArrayType {elementType, elementsMutable}:
    `${if (elementsMutable) "Array<" else "Array<imm "}${getTypeUniqueKey(elementType)}>`
  case TupleType {elementTypes}: {
    let len = elementTypes.length;
    if (len > 0) {
      let parts = new Array<String>.fixed(2 * len + 1, "");
      parts[0] = "[";
      parts[1] = getTypeUniqueKey(elementTypes[0]);
      var i = 1;
      while (i < len) {
        parts[2 * i] = ", ";
        parts[2 * i + 1] = getTypeUniqueKey(elementTypes[i]);
        i += 1;
      }
      parts[2 * len] = "]";
      String.fromParts(parts)
    } else {
      "[]"
    }
  }
  case InlineParamType {param}: `inline ${getTypeUniqueKeyRaw(param)}`
  case InlineRecordType {record}: `inline ${getTypeUniqueKeyRaw(record)}`
  case InlineTupleType {elementTypes}: {
    let len = elementTypes.length;
    if (len > 0) {
      let parts = new Array<String>.fixed(2 * len + 1, "");
      parts[0] = "(";
      parts[1] = getTypeUniqueKey(elementTypes[0]);
      var i = 1;
      while (i < len) {
        parts[2 * i] = ", ";
        parts[2 * i + 1] = getTypeUniqueKey(elementTypes[i]);
        i += 1;
      }
      parts[2 * len] = ")";
      String.fromParts(parts)
    } else {
      "()"
    }
  }
  case UnionType {types}: {
    let len = types.length;
    if (len > 0) {
      let parts = new Array<String>.fixed(2 * len - 1, "");
      parts[0] = getTypeUniqueKey(types[0]);
      var i = 1;
      while (i < len) {
        parts[2 * i - 1] = " | ";
        parts[2 * i] = getTypeUniqueKey(types[i]);
        i += 1;
      }
      String.fromParts(parts)
    } else {
      ""
    }
  }
  case RecordType as recT: {
    let {properties} = recT;
    let len = properties.size;
    if (len > 0) {
      let parts = new Array<String>.fixed(4 * len + 1, "");
      parts[0] = "{ ";
      let keys = properties.keys();
      var i = 0;
      for (let key in keys) {
        let shownKey = if (recT.isOptional(key)) key + "?" else key;
        if (i > 0) {
          parts[4 * i] = ", ";
          parts[4 * i + 1] = shownKey;
          parts[4 * i + 2] = ": ";
          parts[4 * i + 3] = getTypeUniqueKey(properties[key]);
        } else {
          parts[1] = shownKey;
          parts[2] = ": ";
          parts[3] = getTypeUniqueKey(properties[key]);
        }
        i += 1;
      }
      // An existential lowers to a fat pointer of its own.
      parts[4 * len] = if (recT.isExistential) ", ... }" else " }";
      String.fromParts(parts)
    } else {
      if (recT.isExistential) "{ ... }" else "{  }"
    }
  }
  case FunctionType as ft: {
    let paramsLen = ft.parameters.length;
    
    // First pass: count parts
    var numParts = 3; // For "(", ") => ", and returnType
    if (paramsLen > 0) {
      numParts = numParts + (paramsLen - 1); // For ", " delimiters
    }
    
    let names = ft.parameterNames;
    var i = 0;
    while (i < paramsLen) {
      if (names != null && i < names.length) {
        numParts = numParts + 2; // For name and ": "
      }
      numParts = numParts + 1; // For type key
      i += 1;
    }
    
    // Allocate FixedArray
    let parts = new Array<String>.fixed(numParts, "");
    parts[0] = "(";
    
    // Second pass: fill parts
    var idx = 1;
    i = 0;
    while (i < paramsLen) {
      if (i > 0) {
        parts[idx] = ", ";
        idx += 1;
      }
      if (names != null && i < names.length) {
        parts[idx] = names[i];
        parts[idx + 1] = ": ";
        idx += 2;
      }
      parts[idx] = getTypeUniqueKey(ft.parameters[i]);
      idx += 1;
      i += 1;
    }
    parts[idx] = ") => ";
    parts[idx + 1] = getTypeUniqueKey(ft.returnType);
    
    String.fromParts(parts)
  }
  // An alias instance keeps its declaration's unsubstituted target, so
  // the target alone keys every handle alike (`alias_T`).
  case TypeAliasType as a: if (specializesApart(a)) {
    `alias_${apartKind(a)}_${getTypeUniqueKey(apartInner(a))}`
  } else {
    `alias_${getTypeUniqueKey(a.target)}`
  }
  // Keyed as a distinct alias over the backing type is: the key names a
  // representation, which every enum over one backing type shares.
  case EnumType as e: `alias_${getTypeUniqueKey(e.backingType)}`
  case _: typeToString(t)
};
}

export function getFunctionAdaptationKey(src: Type, tgt: Type): FunctionAdaptationKey {
  return new FunctionAdaptationKey(src, tgt);
}

export function getClassMethodKey(classKey: ClassKey, methodName: String): ClassMethodKey {
  return new ClassMethodKey(classKey, methodName);
}

export function getSpecializedFunctionKey(baseName: String, typeArgs: Array<Type>): SpecializedFunctionKey {
  return new SpecializedFunctionKey(baseName, typeArgs);
}

/**
 * The function axis of a closure specialization key: the enclosing
 * function's argument vector, spelled the way `getSpecializedName`
 * spells it, or empty when the context has no function-own arguments
 * to bind (a non-generic enclosing function, or its template walked
 * with parameters still open).
 */
export function getFunctionArgsKey(
    typeParameters: Array<TypeParameterType> | null,
    typeArguments: Array<Type> | null): FunctionArgsKey {
  if (typeParameters == null || typeParameters.length == 0 ||
      typeArguments == null) {
    return "" as FunctionArgsKey;
  }
  return getSpecializedName("", typeArguments) as FunctionArgsKey;
}

export function getClosureSpecializationKey(closureId: NodeId, classKey: ClassKey,
    typeParameters: Array<TypeParameterType> | null = null,
    typeArguments: Array<Type> | null = null): ClosureSpecializationKey {
  return new ClosureSpecializationKey(closureId, classKey,
      getFunctionArgsKey(typeParameters, typeArguments));
}

export function getFunctionValueWrapperKey(keyName: String, ft: FunctionType): FunctionValueWrapperKey {
  return new FunctionValueWrapperKey(keyName, getSignatureKey(ft));
}

export function sortStringsByLengthDescending(arr: GrowableArray<String>): void {
  quickSortStringsByLengthDescending(arr, 0, arr.length - 1);
}

function quickSortStringsByLengthDescending(arr: GrowableArray<String>, low: i32, high: i32): void {
  if (low < high) {
    let pIdx = partitionStringsByLengthDescending(arr, low, high);
    quickSortStringsByLengthDescending(arr, low, pIdx);
    quickSortStringsByLengthDescending(arr, pIdx + 1, high);
  }
}

function partitionStringsByLengthDescending(arr: GrowableArray<String>, low: i32, high: i32): i32 {
  let mid = low + ((high - low) >> 1);
  let pivot = arr[mid];
  let pivotLen = pivot.length;
  
  var i = low - 1;
  var j = high + 1;
  
  while (true) {
    i += 1;
    while (arr[i].length > pivotLen) {
      i += 1;
    }
    
    j -= 1;
    while (arr[j].length < pivotLen) {
      j -= 1;
    }
    
    if (i >= j) {
      return j;
    }
    
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  return j;
}

// ---- Literal parsing shared across codegen ----

export function parseI64OrU64Literal(raw: String): inline (boolean, i64) {
  if (raw.length == 0 || raw.contains('.')) return (false, 0 as i64);

  var isNeg = false;
  var start = 0;
  let first = raw.getByteAt(0);
  if (first == 45) { // '-'
    isNeg = true;
    start = 1;
  } else if (first == 43) { // '+'
    start = 1;
  }

  let digits = if (start > 0) raw.sliceBytes(start, raw.length) else raw;
  if (let (true, mag) = integerLiteralMagnitude(digits)) {
    let finalVal = if (isNeg) (0 as i64) - (mag as i64) else mag as i64;
    return (true, finalVal);
  }
  return (false, 0 as i64);
}

export function parseI32WithHex(s: String): (boolean, i32) {
  if (s.length == 0 || s.contains('.')) return (false, 0);
  var start = 0;
  var isNeg = false;
  let first = s.getByteAt(0);
  if (first == 45) { // '-'
    isNeg = true;
    start = 1;
  } else if (first == 43) { // '+'
    start = 1;
  }

  let digits = if (start > 0) s.sliceBytes(start, s.length) else s;
  if (let (true, mag) = integerLiteralMagnitude(digits)) {
    if (isNeg) {
      let (radix, _) = integerLiteralRadix(digits);
      let limit = if (radix != 10) 4294967295 as u64 else 2147483648 as u64;
      if (mag <= limit) {
        return (true, 0 - (mag as i32));
      }
    } else if (mag <= (4294967295 as u64)) {
      return (true, mag as i32);
    }
  }
  return (false, 0);
}

export function parseFloatLiteral(raw: String): f64 {
  let clean = stripNumericUnderscores(raw);
  if (clean.length == 0) {
    return 0.0 / 0.0;
  }
  var start = 0;
  var isNeg = false;
  let first = clean.getByteAt(0);
  if (first == 45) {
    isNeg = true;
    start = 1;
  } else if (first == 43) {
    start = 1;
  }
  let body = if (start > 0) clean.sliceBytes(start, clean.length) else clean;
  let (radix, digitStart) = integerLiteralRadix(body);
  if (radix == 2 || radix == 8) {
    var acc = 0.0;
    let baseF = radix as f64;
    for (var i = digitStart; i < body.length; i += 1) {
      let d = body.getByteAt(i) - 48;
      acc = acc * baseF + (d as f64);
    }
    return if (isNeg) 0.0 - acc else acc;
  }
  return parseF64(clean);
}

/**
 * The `zena:string-convert` helper a template interpolation of type
 * `t` lowers to, or `''` when the operand is already a String (or is
 * not convertible).
 *
 * Shared by the lowering that emits the call (`ir/templates.zena`) and
 * the reachability pass that must root it. Lowering looks the helper
 * up by NAME through `getStdlibFunc`, so there is no call node for RTA
 * to see — the two have to agree, and a disagreement shows up as
 * `Invalid function call: function index < 0`.
 */
export function templateConvertHelperName(t: Type): String {
  return match (baseType(t)) {
    case I32Type: 'i32ToString'
    case U32Type: 'u32ToString'
    case I64Type: 'i64ToString'
    case U64Type: 'u64ToString'
    case F32Type: 'f32ToString'
    case F64Type: 'f64ToString'
    // Narrow types are held in canonical 32-bit form, so they print
    // through their promoted counterpart's helper.
    case U8Type: 'u32ToString'
    case U16Type: 'u32ToString'
    case I8Type: 'i32ToString'
    case I16Type: 'i32ToString'
    case BooleanType: 'boolToString'
    case _: ''
  };
}

/**
 * `Some<V>`, out of the `Future<Option<V>>` a Pending iteration step
 * carries: the member of the future's `Option<V>` argument that holds a
 * value. Null for anything else.
 */
export function pendingSomeClass(pendingFuture: ClassType): ClassType | null {
  let args = pendingFuture.typeArguments;
  if (args == null || args.length != 1) {
    return null;
  }
  let option = unwrapAliases(args[0]);
  if (option is UnionType) {
    for (let member in option.types) {
      if (member is ClassType && member.name == 'Some') {
        return member;
      }
    }
  }
  return null;
}

/**
 * `None`, out of the `Future<Option<V>>` a Pending iteration step
 * carries: the exhausted-step member of `Option<V>`. Null for anything
 * else.
 */
export function pendingNoneClass(pendingFuture: ClassType): ClassType | null {
  let args = pendingFuture.typeArguments;
  if (args == null || args.length != 1) {
    return null;
  }
  let option = unwrapAliases(args[0]);
  if (option is UnionType) {
    for (let member in option.types) {
      if (member is ClassType && member.name == 'None') {
        return member;
      }
    }
  }
  return null;
}

/**
 * Parse an unsigned integer literal source string (`raw`, with optional `'_'`
 * separators, `0x`/`0b`/`0o` radix prefix, and `'n'` suffix) together with
 * `negative` into `BigInt`'s normalized `(sign, limbs)` representation:
 * `sign` is `0` for zero (`limbs` empty) or `1`/`-1` for non-zero with
 * little-endian 64-bit limbs and a non-zero highest limb.
 */
export function parseBigIntLiteralLimbs(raw: String, negative: boolean): inline (i32, FixedArray<u64>) {
  var end = raw.length;
  if (end > 0 && raw.getByteAt(end - 1) == 110) {
    end -= 1;
  }
  let (radix, start) = integerLiteralRadix(raw);
  let base = radix as u64;
  let words32 = new Array<u64>();
  for (var i = start; i < end; i += 1) {
    let c = raw.getByteAt(i);
    if (c == 95) {
      continue;
    }
    let digit = if (c >= 48 && c <= 57) {
      (c - 48) as u64
    } else if (c >= 97 && c <= 102) {
      (c - 87) as u64
    } else {
      (c - 55) as u64
    };
    var carry = digit;
    for (var j = 0; j < words32.length; j += 1) {
      let prod = words32[j] * base + carry;
      words32[j] = prod & (4294967295 as u64);
      carry = prod >>> (32 as u64);
    }
    if (carry != (0 as u64)) {
      words32.push(carry);
    }
  }
  if (words32.length == 0) {
    return (0, new Array<u64>.fixed(0, 0 as u64));
  }
  let limbCount = (words32.length + 1) >> 1;
  let limbs = new Array<u64>.fixed(limbCount, 0 as u64);
  for (var k = 0; k < limbCount; k += 1) {
    let lo = words32[k * 2];
    let hi = if (k * 2 + 1 < words32.length) words32[k * 2 + 1] else (0 as u64);
    limbs[k] = lo | (hi << (32 as u64));
  }
  let sign = if (negative) -1 else 1;
  return (sign, limbs);
}

/**
 * Canonical module-wide cache key for a normalized `(sign, limbs)` `BigInt`
 * literal so equivalent spellings (`42n`, `42_n`, `0x2an`, contextual `42`)
 * share one cached global.
 */
export function bigIntLiteralCacheKey(sign: i32, limbs: FixedArray<u64>): String {
  if (sign == 0 || limbs.length == 0) {
    return "0";
  }
  let prefixLen = if (sign < 0) 1 else 0;
  let parts = new Array<String>.fixed(prefixLen + 4 * limbs.length - 1, "");
  var idx = 0;
  if (sign < 0) {
    parts[0] = "-";
    idx = 1;
  }
  for (var i = 0; i < limbs.length; i += 1) {
    if (i > 0) {
      parts[idx] = ":";
      idx += 1;
    }
    let w = limbs[i];
    let lo = (w & (4294967295 as u64)) as i32;
    let hi = (w >>> (32 as u64)) as i32;
    parts[idx] = i32ToString(lo);
    parts[idx + 1] = ",";
    parts[idx + 2] = i32ToString(hi);
    idx += 3;
  }
  return String.fromParts(parts);
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19