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

66.6 KiB Raw
/**
 * Argument explosion (docs/design/argument-explosion.md): a record
 * parameter can be accepted as its fields, so a call that has the fields
 * on hand allocates no record and the callee reads each field from a
 * parameter instead of through the record's getters.
 *
 * The pass leaves every existing function as it is and adds a `core`
 * beside each eligible one, with the exploded parameters' fields in
 * their place. The original keeps its signature and becomes a
 * forwarder that reads the fields and calls the core, so function
 * values, exports, templates and every other reference to it keep
 * working unchanged. Only a direct call that has some exploded
 * argument's fields on hand calls the core (`#lowerDirectCallTo` in
 * lowering.zena).
 *
 * Two facts decide which parameters explode, both kept per (function,
 * parameter):
 *
 * - Demand, computed bottom-up: a parameter is fields-only when every
 *   use reads a field, destructures it, or passes it whole to a callee
 *   parameter that is itself fields-only. Otherwise the function needs
 *   the record. Summaries start optimistic and only ever turn to
 *   "needs the record" on evidence, so a recursive function that passes
 *   its record to itself is fields-only.
 * - Availability, computed top-down: some reached call passes the
 *   parameter unpacked, as a record literal (reachability's
 *   `recordLiteralArgs`) or as an exploded parameter of the calling
 *   core passed on whole.
 *
 * A parameter explodes when it is both. A record that enters a chain of
 * such functions as a literal is then never built, and one that enters
 * as a heap value is unpacked once, by the first forwarder; no core
 * rebuilds a record it was given as fields.
 *
 * Runs after reachability and before the generator and async splits,
 * which lower every suspending body as they prepare it: those bodies'
 * calls then see the cores, and a suspending function's core is split
 * like any other. Before `wasm.layout()`, because it interns signatures.
 */
import { HashMap, HashSet } from 'zena:collections';
import {
  AssignmentExpression, BinaryExpression, BlockStatement, CallExpression,
  ClassDeclaration, Expression,
  ExpressionStatement, FunctionExpression, FunctionDeclaration, IfExpression, MatchCase,
  IndexExpression, LetPatternCondition, LogicalPattern, MatchExpression, ReturnStatement,
  VariableDeclaration, IdentifierPattern, Identifier, MemberExpression,
  MethodDefinition, Parameter, RecordLiteral, RecordPattern, TupleLiteral, TuplePattern,
  SpreadElement, SuperInitializer, Node, hasEnsuresClause,
} from '../../ast.zena';
import { SemanticModel, memberKeyOf } from '../../semantic-model.zena';
import { Symbol, SymbolId, noSymbolId } from '../../scope/symbol.zena';
import {
  ClassType, FunctionType, RecordType, TupleType, Type, baseType, typeCarriesOwner,
} from '../../types.zena';
import { walkEnter } from '../../visitor.zena';
import { ValType } from '../wasm.zena';
import { valueEqOperand } from '../value-equality.zena';
import {
  ClassCodegenInfo, WasmModule, WasmFunction, RecordDispatchInfo, ExplosionSpec,
  asWasmStruct,
} from '../wasm-module.zena';
import {
  inlineParamLayoutOf, inlineRecordResultOf, recordWasmFields, sortedOptionalNames,
  substituteTypeParamsInFunctionContext, typeToValTypeWithSub,
} from '../type-mapping.zena';
import { ReachabilityAnalysis } from '../reachability/analysis.zena';
import {
  RecordResultCall, declaringInstantiation, methodTargetKey, recordLiteralArgKey,
  recordLiteralCtorArgKey, recordLiteralMethodArgKey, recordLiteralSpecArgKey,
  specMethodTargetKey,
} from '../reachability/context.zena';
import {
  containsErasedType, getClassKey, getClassMethodKey, getSpecializedFunctionKey,
  getSpecializedName, isConcrete, unwrapAliases,
} from '../codegen-utils.zena';
import { growable } from 'zena:core';

/**
 * A whole-record use of a parameter as argument `index` of a call to the
 * candidate keyed `callee` (`functionKey` or `constructorKey`).
 */
/**
 * What demand needs to follow a parameter's uses: the module, the
 * reachability results, and the function whose body it reads (null when
 * no single instantiation is known), so a method call can be resolved as
 * that function sees it.
 */
final class DemandContext {
  wasm: WasmModule;
  pass: ReachabilityAnalysis;
  f: WasmFunction | null;
  new(this.wasm, this.pass, this.f);
}

final class Forward {
  callee: String;
  index: i32;
  new(this.callee, this.index);
}

/**
 * The `callee` of the forward that stands for a parameter returned whole
 * by its own function. It keeps the parameter fields-only exactly when
 * that function's result explodes, which is settled after demand and
 * availability (explodeRecordParameters re-runs them when it is not).
 */
let returnedWhole = '';

function isReturnedWhole(fw: Forward) {
  return fw.callee == returnedWhole;
}

/** The candidate key of the top-level function `id`. */
function functionKey(id: SymbolId) {
  return `f${id as i32}`;
}

/** The candidate key of the method `target` (`methodTargetKey`). */
function methodKey(target: String) {
  return `m${target}`;
}

/**
 * The candidate key of the specialization of a generic function named
 * `specName` (its `WasmFunction.name`).
 */
function specKey(specName: String) {
  return `s${specName}`;
}

/** The candidate key of the callee a recorded record-result call names. */
function resultCalleeKey(rc: RecordResultCall) {
  return if (rc.methodTarget != null) methodKey(rc.methodTarget as String)
    else if (rc.specTarget != null) specKey(rc.specTarget as String)
    else functionKey(rc.callee);
}

/**
 * The candidate key of the function a call through `callee` names, as
 * seen from `dc.f`: a generic function's specialization for the call's
 * type arguments, instantiated as `dc.f` sees them (null when that
 * leaves a type parameter open, or no such specialization exists), or
 * the function itself.
 */
function functionCallKey(dc: DemandContext, callee: Identifier,
    model: SemanticModel): String | null {
  let sym = model.resolve(callee);
  if (sym == null) {
    return null;
  }
  let target = sym.resolveTarget();
  if (!dc.wasm.genericFunctions.has(target.id)) {
    return functionKey(target.id);
  }
  let ft = model.getNodeType(callee);
  if (!(ft is FunctionType)) {
    return null;
  }
  let typeArgs = ft.typeArguments;
  if (typeArgs == null) {
    return null;
  }
  let args = new Array<Type>();
  for (let t in typeArgs) {
    let arg = substituteTypeParamsInFunctionContext(dc.wasm, dc.f, t);
    if (!isConcrete(arg) || containsErasedType(arg)) {
      return null;
    }
    args.push(arg);
  }
  if (let (true, spec) = dc.wasm.specializedFunctions.get(
      getSpecializedFunctionKey(target.name, args))) {
    let name = spec.name;
    if (name != null) {
      return specKey(name as String);
    }
  }
  return null;
}

/**
 * The candidate key of the constructor `ctorMethod` (`<constructor>`, or
 * `<constructor>.name` for a named one) of the class keyed `classKey`.
 */
function constructorKey(classKey: String, ctorMethod: String) {
  return `c${classKey}|${ctorMethod}`;
}

/**
 * The constructor method name for `name`, a constructor's name node, or
 * null for the unnamed constructor.
 */
function ctorMethodOf(model: SemanticModel, name: Node | null) {
  return if (name == null) '<constructor>'
    else `<constructor>.${memberKeyOf(model, name as Node)}`;
}

/** A constructor method name's phase-name suffix: "" or `.name`. */
function ctorSuffixOf(ctorMethod: String) {
  return ctorMethod.sliceBytes('<constructor>'.length, ctorMethod.length);
}

/**
 * The class a `super(...)` in a constructor of `ct` constructs through:
 * the nearest superclass that is not a mixin's intermediate.
 */
function superWithConstructor(ct: ClassType): ClassType | null {
  var s = ct.superType;
  while (s != null) {
    let cur = s as ClassType;
    if (!cur.isMixinIntermediate) {
      return cur;
    }
    s = cur.superType;
  }
  return null;
}

/**
 * A function or constructor whose record parameters might explode, and
 * what is known about each.
 */
final class Candidate {
  f: WasmFunction;
  /** A top-level function's symbol; null for a constructor. */
  self: Symbol | null;
  /** A constructor's class key; null for a function. */
  ctorKey: String | null;
  /** Per parameter, its record dispatch, or null for a non-record parameter. */
  dispatches: GrowableArray<RecordDispatchInfo | null>;
  /** Per parameter, the calls it is passed to whole. */
  forwards: GrowableArray<GrowableArray<Forward>>;
  /** Per parameter, whether every use only needs its fields. */
  fieldsOnly: GrowableArray<boolean>;
  /** Per parameter, whether some reached call passes it unpacked. */
  available: GrowableArray<boolean>;
  /**
   * A function's record result's dispatch, when it could return the
   * fields instead; null for a constructor or a non-record result.
   */
  result: RecordDispatchInfo | null;
  /** The expressions the function returns, for `result`. */
  returns: GrowableArray<Expression>;
  /** Whether some call of the function only needs `result`'s fields. */
  var resultDemanded: boolean = false;
  /** Whether the core returns `result`'s fields. */
  var resultExplodes: boolean = false;
  /**
   * A method's `methodTargetKey` (its candidate key); null for a function
   * or a constructor.
   */
  var methodTarget: String | null = null;
  /**
   * A method some reached subclass overrides: a call to it dispatches
   * through the vtable and passes the record, so passing a record on to
   * it does not keep the fields.
   */
  var overridden: boolean = false;
  /** A constructor's method name: `<constructor>` or `<constructor>.name`. */
  var ctorMethod: String = '<constructor>';
  /**
   * A generic function's specialization's name (`specKey`); null
   * otherwise.
   */
  var specName: String | null = null;
  new(this.f, this.self, this.ctorKey, this.dispatches, this.forwards,
      this.fieldsOnly, this.available, this.result, this.returns);

  /** This candidate's key in the pass's lookup. */
  key(): String {
    let {self, ctorKey} = this;
    let methodTarget = this.methodTarget;
    if (methodTarget != null) {
      return methodKey(methodTarget);
    }
    let specName = this.specName;
    if (specName != null) {
      return specKey(specName);
    }
    return if (self != null) functionKey(self.id) else
        constructorKey(ctorKey as String, this.ctorMethod);
  }

  /** The declared parameters of the function, method or constructor. */
  params(): GrowableArray<Parameter> {
    let node = this.f.node;
    if (node is FunctionExpression) {
      return node.params;
    }
    return (node as MethodDefinition).params;
  }

  /**
   * Whether some reached call passes parameter `i` a record literal: a
   * call or `new`, or, for a constructor, a subclass's `super(...)`
   * (`superLiterals`, keyed `recordLiteralCtorArgKey`).
   */
  hasLiteralArg(pass: ReachabilityAnalysis, superLiterals: HashSet<String>,
      i: i32): boolean {
    let {self, ctorKey} = this;
    let methodTarget = this.methodTarget;
    if (methodTarget != null) {
      return pass.recordLiteralMethodArgs.has(
          recordLiteralMethodArgKey(methodTarget, i));
    }
    let specName = this.specName;
    if (specName != null) {
      return pass.recordLiteralSpecArgs.has(recordLiteralSpecArgKey(specName, i));
    }
    if (self != null) {
      return pass.recordLiteralArgs.has(recordLiteralArgKey(self.id, i));
    }
    if (ctorKey == null) {
      return false;
    }
    let key = recordLiteralCtorArgKey(ctorKey, this.ctorMethod, i);
    return pass.recordLiteralCtorArgs.has(key) || superLiterals.has(key);
  }
}

export function explodeRecordParameters(
  wasm: WasmModule,
  pass: ReachabilityAnalysis
): void {
  // Candidates in module order, for deterministic output; the map is
  // for lookups only.
  let candidates = new Array<Candidate>();
  let byKey = new HashMap<String, Candidate>();
  for (let f in wasm.functions) {
    let c = candidateFor(wasm, pass, f);
    if (c != null) {
      candidates.push(c);
      byKey[c.key()] = c;
    }
  }

  let superLiterals = literalSuperArgs(wasm);
  // A parameter returned whole is assumed fields-only until its
  // function's result verdict is in. One that would explode while the
  // result does not needs the record after all, which can change every
  // verdict downstream, so the whole analysis runs again without it.
  // Each round only takes parameters away, so this ends.
  var held = new Array<HeldVar>();
  while (true) {
    settleDemand(candidates, byKey);

    // Availability: literal arguments, then exploded parameters passed on.
    for (let c in candidates) {
      for (var i = 0; i < c.available.length; i += 1) {
        c.available[i] = c.fieldsOnly[i] &&
            c.hasLiteralArg(pass, superLiterals, i);
      }
    }
    propagateAvailability(candidates, byKey);

    wasm.fieldsOnlyResultCalls.clear();
    held = explodeResults(wasm, pass, candidates, byKey);
    // A held var passed to a fields-only parameter is passed as its
    // fields, so that parameter is available unpacked.
    for (let hv in held) {
      for (let fw in hv.forwards) {
        if (let (true, target) = byKey.get(fw.callee)) {
          target.available[fw.index] = true;
        }
      }
    }
    propagateAvailability(candidates, byKey);

    var contradicted = false;
    for (let c in candidates) {
      if (c.resultExplodes) {
        continue;
      }
      for (var i = 0; i < c.fieldsOnly.length; i += 1) {
        if (c.fieldsOnly[i] && c.available[i] &&
            c.forwards[i].some((fw) => isReturnedWhole(fw))) {
          c.fieldsOnly[i] = false;
          contradicted = true;
        }
      }
    }
    if (!contradicted) {
      break;
    }
  }
  for (let hv in held) {
    wasm.fieldHeldVars[hv.sym.id] = hv.dispatch;
  }

  // A value phase returns its `super(...)` arguments, which the
  // subclass's factory passes on to the next level's phases; those for
  // exploded parameters are returned as their fields (`superArgTail`).
  for (let c in candidates) {
    let params = new Array<RecordDispatchInfo | null>();
    var any = c.resultExplodes;
    for (var i = 0; i < c.dispatches.length; i += 1) {
      if (c.available[i]) {
        params.push(c.dispatches[i]);
        any = true;
      } else {
        params.push(null);
      }
    }
    if (any) {
      // A method's receiver passes through ahead of its parameters.
      addCore(wasm, pass, c.f, params,
          if (c.methodTarget != null && !c.f.isStatic) 1 else 0,
          if (c.resultExplodes) c.result else null);
      let {ctorKey} = c;
      if (ctorKey != null) {
        addPhaseCores(wasm, pass, c.f, ctorSuffixOf(c.ctorMethod), params,
            byKey);
      }
    }
  }
  // The value phases of constructors whose own parameters stay boxed.
  let inits = new Array<WasmFunction>();
  for (let f in wasm.functions) {
    if (f.explosion == null && isValuePhase(f)) {
      inits.push(f);
    }
  }
  for (let f in inits) {
    let tail = superArgTail(f, byKey);
    if (tail != null) {
      // Every parameter passes as it is.
      let params = new Array<RecordDispatchInfo | null>();
      for (var i = 0; i < f.signature.params.length; i += 1) {
        params.push(null);
      }
      addCore(wasm, pass, f, params, 0, null, tail);
    }
  }
}

/**
 * Demand: a forward keeps a parameter fields-only only while its target
 * is fields-only too, through the same record type.
 */
function settleDemand(candidates: GrowableArray<Candidate>,
    byKey: HashMap<String, Candidate>): void {
  var changed = true;
  while (changed) {
    changed = false;
    for (let c in candidates) {
      for (var i = 0; i < c.fieldsOnly.length; i += 1) {
        if (!c.fieldsOnly[i]) {
          continue;
        }
        for (let fw in c.forwards[i]) {
          if (!forwardKeepsFields(byKey, c.dispatches[i], fw)) {
            c.fieldsOnly[i] = false;
            changed = true;
            break;
          }
        }
      }
    }
  }
}

/**
 * Makes every parameter an available exploded parameter is passed on
 * to available too, to a fixpoint.
 */
function propagateAvailability(candidates: GrowableArray<Candidate>,
    byKey: HashMap<String, Candidate>): void {
  var changed = true;
  while (changed) {
    changed = false;
    for (let c in candidates) {
      for (var i = 0; i < c.available.length; i += 1) {
        if (!c.available[i]) {
          continue;
        }
        for (let fw in c.forwards[i]) {
          // Demand settled every forward of a fields-only parameter to a
          // fields-only target.
          if (let (true, target) = byKey.get(fw.callee)) {
            if (!target.available[fw.index]) {
              target.available[fw.index] = true;
              changed = true;
            }
          }
        }
      }
    }
  }
}

/**
 * How a call's record result is used: only for its fields (`direct`),
 * returned from the function keyed `returnedFrom`, or neither.
 */
final class ResultUse {
  rc: RecordResultCall;
  callee: String;
  direct: boolean;
  returnedFrom: String | null;
  /** The `var` the result is assigned to or initializes, if any. */
  assignedTo: SymbolId;
  /**
   * The fields-only parameters the result is passed to whole, straight
   * or through a `let`; they receive its fields when the call returns
   * them.
   */
  forwards: GrowableArray<Forward>;
  new(this.rc, this.callee, this.direct, this.returnedFrom, this.assignedTo,
      this.forwards);

  /**
   * Whether the call would only need the result's fields if every
   * function it is returned from returned them: demand, ahead of
   * whether the fields are on hand.
   */
  demandsFields(byKey: HashMap<String, Candidate>,
      held: HashMap<SymbolId, HeldVar>): boolean {
    if (this.direct) {
      return true;
    }
    if (this.assignedTo != noSymbolId) {
      return held.has(this.assignedTo);
    }
    let from = this.returnedFrom;
    if (from != null) {
      if (let (true, owner) = byKey.get(from)) {
        return owner.resultDemanded;
      }
    }
    return false;
  }

  /** Whether the result only needs its fields, given the current verdicts. */
  holdsFields(byKey: HashMap<String, Candidate>,
      held: HashMap<SymbolId, HeldVar>): boolean {
    if (this.direct) {
      return true;
    }
    if (this.assignedTo != noSymbolId) {
      return held.has(this.assignedTo);
    }
    let from = this.returnedFrom;
    if (from != null) {
      if (let (true, owner) = byKey.get(from)) {
        return owner.resultExplodes;
      }
    }
    return false;
  }
}

/**
 * A `var` local of a record type that may be carried as its fields:
 * every use reads a field, destructures it, is assigned to, or passes it
 * to a fields-only parameter (`forwards`), so it is held as fields when
 * every value written to it (`writes`) has its fields on hand.
 */
final class HeldVar {
  sym: Symbol;
  dispatch: RecordDispatchInfo;
  /** The function the `var` is declared in, to resolve method calls written to it. */
  dc: DemandContext;
  writes: GrowableArray<Expression>;
  forwards: GrowableArray<Forward>;
  new(this.sym, this.dispatch, this.dc, this.writes, this.forwards);
}

/**
 * Decides which functions return their record result's fields: those
 * some call uses only for its fields (demand) and that have the fields
 * on hand at some return (production). Both depend on other functions
 * through `return g(...)`, in opposite directions: `g` is demanded when
 * `f` is, and `f` produces when `g` does. So demand is settled first,
 * from "nothing is demanded" up, and production then grows among the
 * demanded functions; growing both at once could never start a chain
 * whose only demand is at its head. Marks the calls whose results
 * lowering holds as fields in `wasm.fieldsOnlyResultCalls`.
 */
function explodeResults(wasm: WasmModule, pass: ReachabilityAnalysis,
    candidates: GrowableArray<Candidate>,
    byKey: HashMap<String, Candidate>): GrowableArray<HeldVar> {
  let owners = ownerKeys(candidates);
  let uses = new Array<ResultUse>();
  for (let rc in pass.recordResultCalls) {
    let key = resultCalleeKey(rc);
    if (let (true, target) = byKey.get(key)) {
      let result = target.result;
      if (result != null) {
        uses.push(classifyResultUse(new DemandContext(wasm, pass, null), rc, key,
            result, byKey, owners));
      }
    }
  }
  // `pos = step(pos)` makes a held var and an exploding result each
  // depend on the other, so vars start held and drop out while some
  // write lacks its fields; results are recomputed from "nothing
  // explodes" for each candidate set of held vars.
  var heldList = heldVarCandidates(wasm, pass, byKey);
  var held = heldById(heldList);
  while (true) {
    for (let c in candidates) {
      c.resultDemanded = false;
      c.resultExplodes = false;
    }
    var changed = true;
    while (changed) {
      changed = false;
      for (let use in uses) {
        if (let (true, callee) = byKey.get(use.callee)) {
          if (!callee.resultDemanded && use.demandsFields(byKey, held)) {
            callee.resultDemanded = true;
            changed = true;
          }
        }
      }
    }
    changed = true;
    while (changed) {
      changed = false;
      for (let c in candidates) {
        if (c.result != null && c.resultDemanded && !c.resultExplodes &&
            producesFields(wasm, pass, c, byKey)) {
          c.resultExplodes = true;
          changed = true;
        }
      }
    }
    let next = new Array<HeldVar>();
    for (let hv in heldList) {
      if (writesHaveFields(hv, byKey, held)) {
        next.push(hv);
      }
    }
    if (next.length == heldList.length) {
      break;
    }
    heldList = next;
    held = heldById(heldList);
  }
  for (let use in uses) {
    if (let (true, callee) = byKey.get(use.callee)) {
      if (callee.resultExplodes && use.holdsFields(byKey, held)) {
        wasm.fieldsOnlyResultCalls.add((use.rc.call as Node).id as i32);
        // The bound result is held as its fields, so the parameters it is
        // passed on to are available unpacked.
        for (let fw in use.forwards) {
          if (let (true, target) = byKey.get(fw.callee)) {
            target.available[fw.index] = true;
          }
        }
      }
    }
  }
  return heldList;
}

/**
 * Each method or generic function specialization candidate's
 * declaration node id to its key. A declaration compiled once per
 * instantiation (of a generic class, or of the function itself) maps to
 * "", since a call in its body cannot tell which instantiation it is in.
 */
function ownerKeys(candidates: GrowableArray<Candidate>): HashMap<i32, String> {
  let out = new HashMap<i32, String>();
  for (let c in candidates) {
    if (c.methodTarget != null || c.specName != null) {
      let id = (c.f.node as Node).id as i32;
      out[id] = if (out.has(id)) '' else c.key();
    }
  }
  return out;
}

function heldById(list: GrowableArray<HeldVar>): HashMap<SymbolId, HeldVar> {
  let out = new HashMap<SymbolId, HeldVar>();
  for (let hv in list) {
    out[hv.sym.id] = hv;
  }
  return out;
}

/**
 * Whether every value written to `hv` has its fields on hand: a record
 * or tuple literal, a call whose result explodes, or another held var,
 * of the same type.
 */
function writesHaveFields(hv: HeldVar, byKey: HashMap<String, Candidate>,
    held: HashMap<SymbolId, HeldVar>): boolean {
  for (let w in hv.writes) {
    if (!writeHasFields(w, hv, byKey, held)) {
      return false;
    }
  }
  return true;
}

function writeHasFields(w: Expression, hv: HeldVar,
    byKey: HashMap<String, Candidate>,
    held: HashMap<SymbolId, HeldVar>): boolean {
  if (w is RecordLiteral || w is TupleLiteral) {
    return true;
  }
  let model = (hv.dc.f as WasmFunction).model;
  if (w is Identifier) {
    let sym = model.resolve(w);
    if (sym != null) {
      if (let (true, other) = held.get(sym.id)) {
        return other.dispatch === hv.dispatch;
      }
    }
    return false;
  }
  if (w is CallExpression) {
    return returnsFieldsOf(hv.dc, w, model, byKey, hv.dispatch);
  }
  return false;
}

/**
 * Whether `call` returns a record of `dispatch`'s type as its fields: it
 * calls a function, or a method it does not dispatch to, whose result
 * explodes.
 */
function returnsFieldsOf(dc: DemandContext, call: CallExpression,
    model: SemanticModel, byKey: HashMap<String, Candidate>,
    dispatch: RecordDispatchInfo | null): boolean {
  let callee = call.callee;
  var key: String | null = null;
  if (callee is Identifier) {
    key = functionCallKey(dc, callee, model);
  } else if (callee is MemberExpression) {
    let target = methodTargetOf(dc, callee, model);
    if (target != null) {
      key = methodKey(target);
    }
  }
  if (key == null) {
    return false;
  }
  if (let (true, target) = byKey.get(key as String)) {
    return target.resultExplodes && !target.overridden &&
        target.result === dispatch;
  }
  return false;
}

/**
 * The `var` locals of record and boxed tuple types, in reached
 * functions, whose every use only needs the fields: field and element
 * reads, destructuring and matching, plain assignment, and passing it to
 * a fields-only parameter of the same type. Their writes are checked against the result verdicts by
 * the caller.
 */
function heldVarCandidates(wasm: WasmModule, pass: ReachabilityAnalysis,
    byKey: HashMap<String, Candidate>): GrowableArray<HeldVar> {
  let out = new Array<HeldVar>();
  let declared = new HashSet<SymbolId>();
  let seen = new HashSet<i32>();
  for (let f in wasm.functions) {
    let owner = f.node;
    if (owner == null || seen.has((owner as Node).id as i32)) {
      continue;
    }
    if (!(owner is FunctionExpression) && !(owner is MethodDefinition)) {
      continue;
    }
    seen.add((owner as Node).id as i32);
    let roots = codeRoots(owner as Node);
    for (let root in roots) {
      walkEnter(root, (n) => {
        if (n is VariableDeclaration) {
          noteHeldVarCandidate(new DemandContext(wasm, pass, f), f, owner as Node,
              roots, n, byKey,
              declared, out);
        }
      });
    }
  }
  return out;
}

/** Adds the `var` declared by `vd` in `owner` to `out` when it qualifies. */
function noteHeldVarCandidate(dc: DemandContext, f: WasmFunction, owner: Node,
    roots: GrowableArray<Node>, vd: VariableDeclaration,
    byKey: HashMap<String, Candidate>, declared: HashSet<SymbolId>,
    out: GrowableArray<HeldVar>): void {
  let model = f.model;
  let pattern = vd.pattern;
  if (vd.kind != 'var') {
    return;
  }
  if (!(pattern is IdentifierPattern)) {
    return;
  }
  if (enclosingFunction(vd, model) !== owner) {
    return;
  }
  let sym = model.resolveDeclaration(pattern);
  if (sym == null || declared.has(sym.id)) {
    return;
  }
  declared.add(sym.id);
  let bindingType = model.getBindingType(sym);
  if (bindingType == null) {
    return;
  }
  // Reassigning a var that holds an owner drops the old value, which the
  // release bookkeeping reads as one tuple (#495).
  if (typeCarriesOwner(substituteTypeParamsInFunctionContext(dc.wasm, f, bindingType))) {
    return;
  }
  let d = valueDispatchOf(dc.wasm, f, bindingType);
  if (d == null || d.fields.length == 0) {
    return;
  }
  let forwards = new Array<Forward>();
  if (!usesOnlyFields(dc, owner, roots, model, pattern,
      forwards, null, true)) {
    return;
  }
  for (let fw in forwards) {
    if (!forwardKeepsFields(byKey, d, fw)) {
      return;
    }
  }
  let writes = growable<Expression>([vd.init]);
  for (let root in roots) {
    walkEnter(root, (n) => {
      if (n is AssignmentExpression) {
        let left = n.left;
        if (left is Identifier) {
          let target = model.resolve(left);
          if (target != null && target.id == sym.id) {
            writes.push(n.value);
          }
        }
      }
    });
  }
  out.push(new HeldVar(sym, d, dc, writes, forwards));
}

/** The body of a function or method, if it has one. */
function ownerBody(owner: Node): Node | null {
  if (owner is FunctionExpression) {
    return owner.body as Node;
  }
  if (owner is MethodDefinition) {
    return owner.body;
  }
  return null;
}

/** The code of a function or method: its body, and a constructor's initializers. */
function codeRoots(owner: Node): GrowableArray<Node> {
  let roots = new Array<Node>();
  if (owner is FunctionExpression) {
    roots.push(owner.body as Node);
  } else if (owner is MethodDefinition) {
    let body = owner.body;
    if (body != null) {
      roots.push(body);
    }
    let inits = owner.initializerList;
    if (inits != null) {
      for (let init in inits) {
        roots.push(init);
      }
    }
    let superInit = owner.superInitializer;
    if (superInit != null) {
      roots.push(superInit);
    }
  }
  return roots;
}

/**
 * Whether some return of `c` has its result's fields on hand: a record
 * literal, an exploded parameter of the same record type, a call whose
 * result is returned as fields, or an `if` or `match` with such an arm.
 */
function producesFields(wasm: WasmModule, pass: ReachabilityAnalysis,
    c: Candidate, byKey: HashMap<String, Candidate>): boolean {
  let dc = new DemandContext(wasm, pass, c.f);
  for (let e in c.returns) {
    if (hasFieldsOnHand(dc, c, byKey, e)) {
      return true;
    }
  }
  return false;
}

/**
 * Whether the returned node `n` has `c`'s result fields on hand. The arms
 * of an `if` or `match`, and a value block's tail, count: the core merges
 * the arms' fields (control-flow.zena, lowerArmFields).
 */
function hasFieldsOnHand(dc: DemandContext, c: Candidate,
    byKey: HashMap<String, Candidate>, n: Node): boolean {
  if (n is IfExpression) {
    let alternate = n.alternate;
    return hasFieldsOnHand(dc, c, byKey, n.consequent) ||
        (alternate != null && hasFieldsOnHand(dc, c, byKey, alternate as Node));
  }
  if (n is MatchExpression) {
    for (let mc in n.cases) {
      if (hasFieldsOnHand(dc, c, byKey, mc.body)) {
        return true;
      }
    }
    return false;
  }
  if (n is BlockStatement) {
    let stmts = n.body;
    if (stmts.length == 0) {
      return false;
    }
    let last = stmts[stmts.length - 1];
    return last is ExpressionStatement &&
        hasFieldsOnHand(dc, c, byKey, last.expression);
  }
  let params = c.params();
  let model = c.f.model;
  if (n is RecordLiteral || n is TupleLiteral) {
    return true;
  }
  if (n is Identifier) {
    let sym = model.resolve(n);
    if (sym != null) {
      for (var i = 0; i < params.length; i += 1) {
        let ps = model.resolveDeclaration(params[i].name);
        if (ps != null && ps.id == sym.id && c.available[i] &&
            c.dispatches[i] === c.result) {
          return true;
        }
      }
    }
    return false;
  }
  if (n is CallExpression) {
    return returnsFieldsOf(dc, n, model, byKey, c.result);
  }
  return false;
}

/** How `rc`'s result is used. */
function classifyResultUse(dc: DemandContext, rc: RecordResultCall,
    calleeKey: String,
    result: RecordDispatchInfo, byKey: HashMap<String, Candidate>,
    owners: HashMap<i32, String>): ResultUse {
  let call = rc.call;
  let model = rc.model;
  let owner = enclosingFunction(call, model);
  let parent = model.getParent(call);
  var direct = false;
  var returnedFrom: String | null = null;
  var assignedTo = noSymbolId;
  let forwards = new Array<Forward>();
  if (parent is AssignmentExpression) {
    let left = parent.left;
    if ((parent.value as Node) === (call as Node) && parent.operator == null) {
      if (left is Identifier) {
        let target = model.resolve(left);
        if (target != null) {
          assignedTo = target.id;
        }
      }
    }
  } else if (parent is MemberExpression) {
    direct = (parent.object as Node) === (call as Node) &&
        !parent.optional && !parent.isSymbolAccess;
  } else if (parent is IndexExpression) {
    direct = (parent.object as Node) === (call as Node) && !parent.optional;
  } else if (parent is MatchExpression) {
    direct = (parent.discriminant as Node) === (call as Node);
    for (let c in parent.cases) {
      direct = direct && takesTupleApart(c.pattern);
    }
  } else if (parent is LetPatternCondition) {
    direct = (parent.init as Node) === (call as Node) &&
        takesTupleApart(parent.pattern);
  } else if (parent is CallExpression) {
    // Passed straight to a fields-only parameter, like a bound result.
    let fw = forwardOf(dc, parent, call as Node, model);
    if (fw != null && forwardKeepsFields(byKey, result, fw)) {
      direct = true;
      forwards.push(fw);
    }
  } else if (parent is VariableDeclaration) {
    let pattern = parent.pattern;
    if ((parent.init as Node) === (call as Node)) {
      if (pattern is RecordPattern || pattern is TuplePattern) {
        direct = true;
      } else if (pattern is IdentifierPattern) {
        if (parent.kind == 'let' && owner != null) {
          direct = boundResultUsesFields(dc, owner as Node, model, pattern,
              result, byKey, forwards);
        } else if (parent.kind == 'var') {
          let target = model.resolveDeclaration(pattern);
          if (target != null) {
            assignedTo = target.id;
          }
        }
      }
    }
  } else if (owner != null && returnsFrom(call, parent, owner as Node)) {
    // A plain function by its symbol; a method or a generic function's
    // specialization by its declaration, when it has one candidate.
    var plain: FunctionExpression | null = null;
    if (owner is FunctionExpression) {
      if (owner.typeParameters == null) {
        plain = owner;
      }
    }
    if (plain != null) {
      let ownerSym = declaredSymbol(plain, model);
      if (ownerSym != null) {
        returnedFrom = functionKey(ownerSym.id);
      }
    } else if (let (true, key) = owners.get((owner as Node).id as i32)) {
      if (key != '') {
        returnedFrom = key;
      }
    }
  }
  return new ResultUse(rc, calleeKey, direct, returnedFrom, assignedTo,
      forwards);
}

/**
 * Whether `call`, whose parent is `parent`, is a value `owner` returns:
 * a `return` operand, the expression body, or a value block's tail.
 */
function returnsFrom(call: CallExpression, parent: Node | null,
    owner: Node): boolean {
  let bodyOpt = ownerBody(owner);
  if (bodyOpt == null) {
    return false;
  }
  let body = bodyOpt as Node;
  if (body === (call as Node)) {
    return true;
  }
  if (parent is ReturnStatement) {
    let arg = parent.argument;
    return arg != null && (arg as Node) === (call as Node) && !parent.isTail;
  }
  if (parent is ExpressionStatement) {
    if (body is BlockStatement) {
      let stmts = body.body;
      return stmts.length > 0 &&
          (stmts[stmts.length - 1] as Node) === (parent as Node);
    }
  }
  return false;
}

/**
 * Whether the record bound by `let pattern = call` in `owner` is only
 * read for its fields, or passed to parameters of the same record type
 * that are, which are collected in `forwards`.
 */
function boundResultUsesFields(dc: DemandContext, owner: Node,
    model: SemanticModel,
    pattern: IdentifierPattern, result: RecordDispatchInfo,
    byKey: HashMap<String, Candidate>,
    forwards: GrowableArray<Forward>): boolean {
  let roots = codeRoots(owner);
  if (!usesOnlyFields(dc, owner, roots, model, pattern, forwards, null)) {
    return false;
  }
  for (let fw in forwards) {
    if (!forwardKeepsFields(byKey, result, fw)) {
      return false;
    }
  }
  return true;
}

/** The function or method whose code `node` is in, if any. */
function enclosingFunction(node: Node, model: SemanticModel): Node | null {
  var p = model.getParent(node);
  while (p != null) {
    if (p is FunctionExpression || p is MethodDefinition) {
      return p;
    }
    p = model.getParent(p);
  }
  return null;
}

/**
 * The dispatch of `f`'s record result, when it could be returned as
 * fields: one wasm result, a record type with at least one field.
 */
function resultDispatchOf(wasm: WasmModule, f: WasmFunction,
    self: Symbol) {
  return resultDispatchOfType(wasm, f, f.model.getBindingType(self));
}

/** resultDispatchOf, given the function's type. */
function resultDispatchOfType(wasm: WasmModule, f: WasmFunction,
    ft: Type | null): RecordDispatchInfo | null {
  if (f.signature.returns.length != 1) {
    return null;
  }
  if (!(ft is FunctionType)) {
    return null;
  }
  let d = valueDispatchOf(wasm, f, ft.returnType);
  if (d == null || d.fields.length == 0) {
    return null;
  }
  return d;
}

/**
 * Collects the expressions `fn` returns into `out`: `return` operands
 * outside nested functions, the expression body, or a value block's
 * tail. False when `fn` has a `tail return`, whose call the core could
 * not turn into fields.
 */
function collectReturns(fn: Node, model: SemanticModel,
    out: GrowableArray<Expression>): boolean {
  let bodyOpt = ownerBody(fn);
  if (bodyOpt == null) {
    return false;
  }
  let body = bodyOpt as Node;
  if (!(body is BlockStatement)) {
    out.push(body as Expression);
    return true;
  }
  var ok = true;
  walkEnter(body, (n) => {
    if (n is ReturnStatement) {
      if (enclosingFunction(n, model) === fn) {
        if (n.isTail) {
          ok = false;
        }
        let arg = n.argument;
        if (arg != null) {
          out.push(arg);
        }
      }
    }
  });
  let stmts = body.body;
  if (stmts.length > 0) {
    let last = stmts[stmts.length - 1];
    if (last is ExpressionStatement) {
      out.push(last.expression);
    }
  }
  return ok;
}

/**
 * Cores for the phase functions of a constructor whose parameters
 * explode: a subclass's `super(...)` calls `<ctor-init>` and
 * `<ctor-body>`, not the factory (with `suffix`, `.name`, for a named
 * constructor). They exist only for a class some reached constructor
 * extends. `<ctor-body>` takes the instance first.
 */
function addPhaseCores(wasm: WasmModule, pass: ReachabilityAnalysis,
    factory: WasmFunction, suffix: String,
    params: GrowableArray<RecordDispatchInfo | null>,
    byKey: HashMap<String, Candidate>): void {
  let classKey = getClassKey(factory.classType as ClassType);
  if (let (true, init) = wasm.classMethodMap.get(
      getClassMethodKey(classKey, `<ctor-init>${suffix}`))) {
    addCore(wasm, pass, init, params, 0, null,
        if (isValuePhase(init)) superArgTail(init, byKey) else null);
  }
  if (let (true, body) = wasm.classMethodMap.get(
      getClassMethodKey(classKey, `<ctor-body>${suffix}`))) {
    addCore(wasm, pass, body, params, 1, null);
  }
}

/** Whether `f` is a constructor's value phase, `<ctor-init>[.name]`. */
function isValuePhase(f: WasmFunction): boolean {
  let meth = f.methodName;
  if (meth == null || f.classType == null || !(f.node is MethodDefinition)) {
    return false;
  }
  let m = meth as String;
  return m == '<ctor-init>' || m.startsWith('<ctor-init>.');
}

/**
 * For the value phase `f`, when its `super(...)` calls a constructor
 * with exploded parameters, the dispatch of each argument it returns as
 * fields, or null for one returned as it is; else null. The subclass
 * factory that calls the phase passes them to that constructor's
 * phases, whose cores take those fields.
 */
function superArgTail(f: WasmFunction, byKey: HashMap<String, Candidate>):
    GrowableArray<RecordDispatchInfo | null> | null {
  let md = f.node as MethodDefinition;
  let si = md.superInitializer;
  let superCt = superWithConstructor(f.classType as ClassType);
  if (!(si is SuperInitializer) || superCt == null) {
    return null;
  }
  let key = constructorKey(getClassKey(superCt) as String,
      ctorMethodOf(f.model, si.constructorName));
  if (let (true, target) = byKey.get(key)) {
    let tail = new Array<RecordDispatchInfo | null>();
    var any = false;
    for (var i = 0; i < target.available.length; i += 1) {
      if (target.available[i]) {
        tail.push(target.dispatches[i]);
        any = true;
      } else {
        tail.push(null);
      }
    }
    if (any) {
      return tail;
    }
  }
  return null;
}

/** Adds the literal arguments of `md`'s `super(...)` to `out`. */
function noteLiteralSuperArgs(md: MethodDefinition, ct: ClassType,
    model: SemanticModel, out: HashSet<String>) {
  let si = md.superInitializer;
  let superCt = superWithConstructor(ct);
  if (si is SuperInitializer && superCt != null) {
    let superKey = getClassKey(superCt) as String;
    let ctorMethod = ctorMethodOf(model, si.constructorName);
    for (var k = 0; k < si.args.length; k += 1) {
      if (si.args[k] is RecordLiteral || si.args[k] is TupleLiteral) {
        out.add(recordLiteralCtorArgKey(superKey, ctorMethod, k));
      }
    }
  }
}

/**
 * The `recordLiteralCtorArgKey`s of the record literals reached
 * constructors pass to a `super(...)`.
 */
function literalSuperArgs(wasm: WasmModule): HashSet<String> {
  let out = new HashSet<String>();
  for (let f in wasm.functions) {
    let ct = f.classType;
    let md = f.node;
    let meth = f.methodName;
    if (ct != null && meth != null &&
        (meth as String).startsWith('<constructor>') &&
        md is MethodDefinition) {
      noteLiteralSuperArgs(md, ct, f.model, out);
    }
  }
  return out;
}

/**
 * Adds `f`'s core, taking each exploded parameter's fields. The first
 * `leading` parameters of `f`'s signature (a phase's instance) are not
 * declared parameters and stay as they are. `result` makes the core
 * return a record result's fields; `tail`, for a value phase, the
 * fields of the `super(...)` arguments it returns (`superArgTail`).
 */
function addCore(wasm: WasmModule, pass: ReachabilityAnalysis, f: WasmFunction,
    params: GrowableArray<RecordDispatchInfo | null>, leading: i32,
    result: RecordDispatchInfo | null,
    tail: GrowableArray<RecordDispatchInfo | null> | null = null): void {
  let sig = f.signature;
  let coreParams = new Array<ValType>();
  for (var i = 0; i < leading; i += 1) {
    coreParams.push(sig.params[i]);
  }
  for (var i = 0; i < params.length; i += 1) {
    let d = params[i];
    if (d == null) {
      coreParams.push(sig.params[leading + i]);
    } else {
      for (let field in d.fields) {
        coreParams.push(field.type);
      }
    }
  }
  var coreReturns = sig.returns;
  if (result != null) {
    coreReturns = new Array<ValType>();
    for (let field in result.fields) {
      coreReturns.push(field.type);
    }
  } else if (tail != null) {
    // A value phase's own fields, then each `super(...)` argument, as
    // its fields when `tail` explodes it.
    coreReturns = new Array<ValType>();
    let own = sig.returns.length - tail.length;
    for (var i = 0; i < own; i += 1) {
      coreReturns.push(sig.returns[i]);
    }
    for (var j = 0; j < tail.length; j += 1) {
      let d = tail[j];
      if (d == null) {
        coreReturns.push(sig.returns[own + j]);
      } else {
        for (let field in d.fields) {
          coreReturns.push(field.type);
        }
      }
    }
  }
  let coreSig = wasm.getSignature(coreParams, coreReturns);
  pass.markTypeReached(coreSig);
  let core = new WasmFunction(coreSig, f.node, f.model);
  core.name = `${f.name ?? 'function'}.core`;
  // A constructor's core lowers as a factory too. It has no method name:
  // `layout()` rebuilds the class method map from method names, and the
  // core must not replace the factory every `new` looks up.
  core.classType = f.classType;
  core.structType = f.structType;
  core.classDecl = f.classDecl;
  // A specialization's body names its type parameters; the core
  // substitutes them as the forwarder does.
  core.typeParameters = f.typeParameters;
  core.typeArguments = f.typeArguments;
  let spec = new ExplosionSpec(params, f, core, result);
  spec.tail = tail;
  f.explosion = spec;
  core.explosion = spec;
  wasm.addFunction(core);
  pass.markFunctionReached(core);
}

/**
 * Whether passing a record whole, as `fw`, needs only its fields: the
 * callee is a candidate whose matching parameter takes the same record
 * type and is fields-only.
 */
function forwardKeepsFields(byKey: HashMap<String, Candidate>,
    dispatch: RecordDispatchInfo | null, fw: Forward): boolean {
  if (isReturnedWhole(fw)) {
    return true;
  }
  if (let (true, target) = byKey.get(fw.callee)) {
    if (target.overridden || fw.index >= target.dispatches.length) {
      return false;
    }
    let targetDispatch = target.dispatches[fw.index];
    return targetDispatch != null && targetDispatch === dispatch &&
        target.fieldsOnly[fw.index];
  }
  return false;
}

/**
 * `f` as a candidate, with each record parameter's uses classified, or
 * null when `f` can take no core.
 */
/**
 * Whether `f` takes a parameter inline. Its signature already takes the
 * parameter's slots, which every caller passes, so it has no boxed form to
 * forward from (docs/design/inline-parameters.md).
 */
function takesInlineParameter(wasm: WasmModule, f: WasmFunction): boolean {
  let fn = f.node;
  let params = if (fn is FunctionExpression) {
    fn.params
  } else if (fn is MethodDefinition) {
    fn.params
  } else {
    null
  };
  if (params == null) {
    return false;
  }
  for (let p in params) {
    let sym = f.model.resolve(p.name);
    if (sym == null) {
      continue;
    }
    let bt = f.model.getBindingType(sym);
    if (bt != null && inlineParamLayoutOf(wasm, bt) != null) {
      return true;
    }
  }
  return false;
}

function candidateFor(wasm: WasmModule, pass: ReachabilityAnalysis,
    f: WasmFunction): Candidate | null {
  // An inline record result is the fields already, for every caller.
  if (takesInlineParameter(wasm, f) || inlineRecordResultOf(wasm, f) != null) {
    return null;
  }
  if (f.classType != null) {
    let methodName = f.methodName;
    if (methodName != null && !(methodName as String).startsWith('<constructor>')) {
      return methodCandidateFor(wasm, pass, f);
    }
    return constructorCandidateFor(wasm, pass, f);
  }
  // A plain top-level function, or one specialization of a generic one:
  // no receiver, context or suspension machinery, and nothing
  // synthesized. A generic function's template is never emitted.
  let captures = f.captures;
  let typeArgs = f.typeArguments;
  let spec = f.typeParameters != null && typeArgs != null;
  if (f.structType != null || f.isClosure ||
      f.contextStruct != null || (captures != null && captures.length > 0) ||
      f.capturesThis || (f.typeParameters != null && !spec) ||
      (typeArgs != null && !spec) || f.intrinsic != null || f.isImport ||
      f.isFunctionAdaptation || f.isClosureWrapper ||
      f.isClosureTrampoline || f.closureForwarder != null ||
      f.explosion != null) {
    return null;
  }
  let fn = f.node;
  if (!(fn is FunctionExpression)) {
    return null;
  }
  if ((fn.typeParameters != null) != spec) {
    return null;
  }
  let sig = f.signature;
  // One slot per declared parameter: no zero-width ones to skip.
  if (sig.returns.length > 1 || sig.params.length != fn.params.length) {
    return null;
  }
  let model = f.model;
  let self = declaredSymbol(fn, model);
  if (self == null) {
    return null;
  }
  let decls = model.getGlobalDeclarations(self.id);
  if (decls != null && (decls as GrowableArray<Node>).length > 1) {
    return null;
  }
  // The function every call resolves to: a specialization is registered
  // by name and type arguments, as lowering looks it up.
  var registered: WasmFunction | null = null;
  if (spec) {
    if (let (true, sf) = wasm.specializedFunctions.get(
        getSpecializedFunctionKey(self.name, typeArgs as Array<Type>))) {
      registered = sf;
    }
  } else if (let (true, mf) = wasm.functionMap.get(self.id)) {
    registered = mf;
  }
  if (registered !== f) {
    return null;
  }
  // An injected default can name an earlier parameter, which the core
  // no longer has as one value; such calls would need the record.
  for (let p in fn.params) {
    if (p.defaultValue != null) {
      return null;
    }
  }
  let roots = growable<Node>([fn.body as Node]);
  // A generator or async function returns its iterator or future: its
  // `return` operands are not its result. A function with postconditions
  // returns its result whole, for them to read as `result`.
  var result = if (fn.isAsync || fn.isGenerator || hasEnsuresClause(fn.contracts)) null
      else resultDispatchOf(wasm, f, self);
  let returns = new Array<Expression>();
  if (result != null && !collectReturns(fn, model, returns)) {
    result = null;
  }
  let c = classifyParams(new DemandContext(wasm, pass, f), f, fn, fn.params,
      roots, self, null, null, result, returns);
  if (c != null && spec) {
    c.specName = f.name;
  }
  return c;
}

/**
 * A class's own written constructor as a candidate: the factory `new`
 * calls, on a plain, non-generic class. Its phase functions, which a
 * subclass's `super(...)` calls, keep the boxed signature.
 */
/**
 * An instance method of a non-generic class whose record parameters or
 * result might explode. Its vtable slot keeps the method itself, which
 * becomes the forwarder, so dispatch is unchanged: only a call the
 * lowering makes directly, to this very method, can call the core.
 */
function methodCandidateFor(wasm: WasmModule, pass: ReachabilityAnalysis,
    f: WasmFunction): Candidate | null {
  let ct = f.classType as ClassType;
  let typeArgs = ct.typeArguments;
  let typeParams = ct.typeParameters;
  let methodName = f.methodName as String;
  // A generic class's template is never emitted; each instantiation's
  // method is a function of its own, keyed by the instantiation.
  let template = typeParams != null && typeParams.length > 0 &&
      (typeArgs == null || typeArgs.length == 0);
  // A generic method exists only per specialization (`map_spec_i32`),
  // which carries the method's own type arguments.
  let spec = f.typeParameters != null && f.typeArguments != null;
  if (ct.isExtension || ct.isMixinIntermediate || template ||
      !isConcrete(ct as Type) || containsErasedType(ct as Type) ||
      methodName.contains('::') || f.intrinsic != null ||
      (!spec && (f.typeParameters != null || f.typeArguments != null)) ||
      f.explosion != null || f.isCaseClassEq || f.isCaseClassHash) {
    return null;
  }
  let md = f.node;
  if (!(md is MethodDefinition)) {
    return null;
  }
  if (md.isConstructor || md.isStatic != f.isStatic || md.isAbstract ||
      md.decorators.length > 0 || md.receiver != null ||
      (md.typeParameters != null) != spec || md.body == null) {
    return null;
  }
  let sig = f.signature;
  let receiver = if (f.isStatic) 0 else 1;
  if (sig.returns.length > 1 || sig.params.length != md.params.length + receiver) {
    return null;
  }
  if (let (true, mapped) = wasm.methodMap(f.isStatic).get(
      getClassMethodKey(getClassKey(ct), methodName))) {
    if (mapped !== f) {
      return null;
    }
  } else {
    return null;
  }
  for (let p in md.params) {
    if (p.defaultValue != null || p.isThisParam) {
      return null;
    }
  }
  // The member is declared under its own name; a specialization's slot
  // is named for its type arguments.
  let declaredName = if (spec) memberKeyOf(f.model, md.name as Node) else methodName;
  var ft: Type | null = null;
  if (let (true, info) = ct.memberTable(f.isStatic).get(declaredName)) {
    ft = info.type;
  }
  // As for functions, a generator or async method's result is its
  // iterator or future, and a method with postconditions returns its
  // result whole.
  var result = if (md.isAsync || md.isGenerator || hasEnsuresClause(md.contracts)) null
      else resultDispatchOfType(wasm, f, ft);
  let returns = new Array<Expression>();
  if (result != null && !collectReturns(md, f.model, returns)) {
    result = null;
  }
  let roots = codeRoots(md);
  let c = classifyParams(new DemandContext(wasm, pass, f), f, md, md.params, roots, null, null, null,
      result, returns);
  if (c != null) {
    let target = methodTargetKey((md as Node).id as i32, ct);
    c.methodTarget = if (spec) specMethodTargetKey(target, methodName) else target;
    c.overridden = !f.isStatic && hasReachedOverride(wasm, ct, methodName);
  }
  return c;
}

/** Whether some reached subclass of `ct` has its own `methodName`. */
function hasReachedOverride(wasm: WasmModule, ct: ClassType,
    methodName: String): boolean {
  if (let (true, info) = wasm.classInfos.get(getClassKey(ct))) {
    let subs = new Array<ClassCodegenInfo>();
    info.getTransitiveSubclasses(subs);
    for (let sub in subs) {
      let sct = sub.structType.classType;
      if (sct != null && wasm.classMethodMap.has(
          getClassMethodKey(getClassKey(sct), methodName))) {
        return true;
      }
    }
  }
  return false;
}

function constructorCandidateFor(wasm: WasmModule, pass: ReachabilityAnalysis,
    f: WasmFunction): Candidate | null {
  let ct = f.classType as ClassType;
  let typeArgs = ct.typeArguments;
  let typeParams = ct.typeParameters;
  // As for methods, a generic class's template is never emitted; each
  // instantiation's constructor is a function of its own.
  let template = typeParams != null && typeParams.length > 0 &&
      (typeArgs == null || typeArgs.length == 0);
  if (ct.isExtension || ct.isCaseClass || ct.isMixinIntermediate ||
      ct.isResource || template || !isConcrete(ct as Type) ||
      containsErasedType(ct as Type) ||
      f.methodName == null || f.explosion != null ||
      !(f.classDecl is ClassDeclaration)) {
    return null;
  }
  let ctorMethod = f.methodName as String;
  if (ctorMethod != '<constructor>' && !ctorMethod.startsWith('<constructor>.')) {
    return null;
  }
  let md = f.node;
  if (!(md is MethodDefinition)) {
    return null;
  }
  if (!md.isConstructor || md.decorators.length > 0 || md.isAsync ||
      md.isGenerator) {
    return null;
  }
  let sig = f.signature;
  if (sig.returns.length != 1 || sig.params.length != md.params.length) {
    return null;
  }
  let classKey = getClassKey(ct);
  if (let (true, mapped) = wasm.classMethodMap.get(
      getClassMethodKey(classKey, ctorMethod))) {
    if (mapped !== f) {
      return null;
    }
  } else {
    return null;
  }
  for (let p in md.params) {
    if (p.defaultValue != null || p.isThisParam) {
      return null;
    }
  }
  let roots = new Array<Node>();
  let body = md.body;
  if (body != null) {
    roots.push(body);
  }
  let inits = md.initializerList;
  if (inits != null) {
    for (let init in inits) {
      roots.push(init);
    }
  }
  let superInit = md.superInitializer;
  var superKey: String | null = null;
  let superCt = superWithConstructor(ct);
  if (superInit is SuperInitializer) {
    roots.push(superInit);
    if (superCt != null) {
      // The constructor `super(...)` or `super.name(...)` calls.
      superKey = constructorKey(getClassKey(superCt) as String,
          ctorMethodOf(f.model, superInit.constructorName));
    }
  }
  let c = classifyParams(new DemandContext(wasm, pass, f), f, md, md.params,
      roots, null, classKey as String, superKey, null, new Array<Expression>());
  if (c != null) {
    c.ctorMethod = ctorMethod;
  }
  return c;
}

/**
 * The candidate for `f`, whose declaration `owner` has `params` and
 * whose code is `roots`, or null when no parameter is a record it only
 * needs the fields of.
 */
function classifyParams(dc: DemandContext, f: WasmFunction, owner: Node,
    params: GrowableArray<Parameter>, roots: GrowableArray<Node>,
    self: Symbol | null, ctorKey: String | null,
    superKey: String | null, result: RecordDispatchInfo | null,
    returns: GrowableArray<Expression>): Candidate | null {
  let dispatches = new Array<RecordDispatchInfo | null>();
  let forwards = new Array<GrowableArray<Forward>>();
  let fieldsOnly = new Array<boolean>();
  let available = new Array<boolean>();
  var anyRecord = false;
  for (let p in params) {
    let out = new Array<Forward>();
    let d = recordDispatchOfParam(dc.wasm, f, p.name);
    // Returning the parameter whole only passes its fields on when it has
    // the result's own shape.
    let returnable = result != null && d === result;
    let usesFields = d != null &&
        usesOnlyFields(dc, owner, roots, f.model, p.name,
            out, superKey, false,
            returnable);
    dispatches.push(if (usesFields) d else null);
    forwards.push(out);
    fieldsOnly.push(usesFields);
    available.push(false);
    if (usesFields) {
      anyRecord = true;
    }
  }
  if (!anyRecord && result == null) {
    return null;
  }
  return new Candidate(f, self, ctorKey, dispatches, forwards, fieldsOnly,
      available, result, returns);
}

/** The dispatch of a parameter of a record or boxed tuple type. */
function recordDispatchOfParam(wasm: WasmModule, f: WasmFunction,
    name: Identifier): RecordDispatchInfo | null {
  let sym = f.model.resolveDeclaration(name);
  if (sym == null) {
    return null;
  }
  let declared = f.model.getBindingType(sym);
  if (declared == null) {
    return null;
  }
  return valueDispatchOf(wasm, f, declared);
}

/**
 * The dispatch a value of type `t` in `f` can be taken apart through: a
 * closed record type's, or a boxed tuple's stand-in
 * (`RecordDispatchInfo.isTuple`). Null for any other type.
 */
function valueDispatchOf(wasm: WasmModule, f: WasmFunction,
    t: Type): RecordDispatchInfo | null {
  let rt = unwrapAliases(substituteTypeParamsInFunctionContext(wasm, f, t));
  if (rt is TupleType) {
    let st = asWasmStruct(typeToValTypeWithSub(wasm, rt, f));
    return if (st != null) wasm.getTupleDispatch(f.model, st) else null;
  }
  if (!(rt is RecordType)) {
    return null;
  }
  if (rt.isExistential) {
    return null;
  }
  return wasm.findRecordDispatch(
      recordWasmFields(wasm, rt, f), sortedOptionalNames(rt));
}

/** The symbol a top-level function's declaration binds. */
function declaredSymbol(fn: FunctionExpression, model: SemanticModel): Symbol | null {
  let parent = model.getParent(fn);
  if (parent is FunctionDeclaration) {
    return model.resolveDeclaration(parent.name);
  }
  if (parent is VariableDeclaration) {
    let pattern = parent.pattern;
    if (pattern is IdentifierPattern) {
      return model.resolveDeclaration(pattern);
    }
  }
  return null;
}

/**
 * Whether every use in `roots` of the parameter declared by `name` reads
 * a field or passes the record whole to a top-level function, recording
 * each such call in `forwards`. Any other use needs the record itself,
 * and the core would rebuild it on entry, which moves the allocation
 * instead of removing it.
 */
function usesOnlyFields(dc: DemandContext, owner: Node,
    roots: GrowableArray<Node>, model: SemanticModel, name: Node,
    forwards: GrowableArray<Forward>, superKey: String | null,
    allowAssign: boolean = false, allowReturn: boolean = false): boolean {
  let param = model.resolveDeclaration(name);
  if (param == null) {
    return false;
  }
  var ok = true;
  for (let root in roots) {
    walkEnter(root, (n) => {
      if (ok && n is Identifier) {
        let sym = model.resolve(n);
        if (sym != null && sym.id == param.id &&
            !isFieldUse(dc, n, owner, model, forwards, superKey, allowAssign,
                allowReturn)) {
          ok = false;
        }
      }
    });
  }
  return ok;
}

/**
 * `ident.field`, `ident[0]` (a tuple's element), `let {...} = ident` or
 * `let (...) = ident`, `match (ident)` or `if (let (...) = ident)` with
 * tuple patterns (`takesTupleApart`), `{...ident}` in a record literal,
 * `g(..., ident, ...)` for a top-level function `g`, or
 * `super(..., ident, ...)` (or `super.name(...)`) to the constructor
 * keyed `superKey`, outside any nested function: a closure would capture
 * the record.
 */
function isFieldUse(dc: DemandContext, ident: Identifier, owner: Node,
    model: SemanticModel, forwards: GrowableArray<Forward>,
    superKey: String | null, allowAssign: boolean,
    allowReturn: boolean): boolean {
  let parent = model.getParent(ident);
  var accepted = false;
  var forward: Forward | null = null;
  if (allowReturn && isReturnedValue(ident, owner, model)) {
    forwards.push(new Forward(returnedWhole, -1));
    return true;
  }
  if (parent is SpreadElement) {
    // A record literal's spread reads the source's statically known
    // fields, each through `recordDispatchRead`, which answers from the
    // fields of a record held as them.
    accepted = model.getParent(parent) is RecordLiteral;
  } else if (parent is BinaryExpression) {
    // `==` on records compares their fields (equality.md, "Structural
    // equality for records and tuples"), from the fields of an operand
    // held as them (ir/equality.zena, lowerValueEq).
    accepted = isValueComparison(parent, model);
  } else if (parent is MemberExpression) {
    accepted = (parent.object as Node) === (ident as Node) &&
        !parent.optional && !parent.isSymbolAccess;
  } else if (parent is IndexExpression) {
    // A tuple's element, read with `struct_get`, which simplify answers
    // from the struct the core builds on entry.
    accepted = (parent.object as Node) === (ident as Node) && !parent.optional;
  } else if (parent is MatchExpression) {
    // Matching a tuple against tuple patterns reads its elements, each
    // with `struct_get` as an index does.
    accepted = (parent.discriminant as Node) === (ident as Node);
    for (let c in parent.cases) {
      accepted = accepted && takesTupleApart(c.pattern);
    }
  } else if (parent is LetPatternCondition) {
    accepted = (parent.init as Node) === (ident as Node) &&
        takesTupleApart(parent.pattern);
  } else if (parent is VariableDeclaration) {
    let pattern = parent.pattern;
    accepted = (parent.init as Node) === (ident as Node) &&
        (pattern is RecordPattern || pattern is TuplePattern);
  } else if (parent is CallExpression) {
    forward = forwardOf(dc, parent, ident, model);
    accepted = forward != null;
  } else if (parent is AssignmentExpression) {
    // Being assigned to is a write, not a use of the record, for a
    // `var` whose every write is itself checked (heldVarCandidates).
    accepted = allowAssign && (parent.left as Node) === (ident as Node) &&
        parent.operator == null;
  } else if (parent is SuperInitializer) {
    if (superKey != null) {
      for (var k = 0; k < parent.args.length; k += 1) {
        if ((parent.args[k] as Node) === (ident as Node)) {
          forward = new Forward(superKey, k);
        }
      }
    }
    accepted = forward != null;
  }
  if (!accepted) {
    return false;
  }
  var p = model.getParent(parent as Node);
  while (p != null && p !== owner) {
    if (p is FunctionExpression) {
      return false;
    }
    p = model.getParent(p);
  }
  if (forward != null) {
    forwards.push(forward);
  }
  return true;
}

/**
 * Whether `pattern`, matched against a tuple, reads only its elements: a
 * tuple pattern (whatever its elements bind), `_`, or an or-pattern of
 * those. A pattern that binds the whole value (`let t`, `(...) as t`)
 * needs the tuple.
 */
function takesTupleApart(pattern: Node): boolean {
  if (pattern is TuplePattern) {
    return true;
  }
  if (pattern is Identifier) {
    return pattern.name == "_";
  }
  if (pattern is LogicalPattern) {
    return takesTupleApart(pattern.left) && takesTupleApart(pattern.right);
  }
  return false;
}

/** Whether `bin` is `==` or `!=` between two record or tuple operands. */
function isValueComparison(bin: BinaryExpression, model: SemanticModel): boolean {
  if (bin.operator != "==" && bin.operator != "!=") {
    return false;
  }
  let lt = model.getNodeType(bin.left);
  let rt = model.getNodeType(bin.right);
  return lt != null && rt != null && valueEqOperand(lt as Type) != null &&
      valueEqOperand(rt as Type) != null;
}

/**
 * Whether `node` is the whole value `owner` returns: a `return` operand,
 * the expression body or a value block's tail, or an arm of an `if` or
 * `match` (or a value block's tail inside one) in any of those places.
 */
function isReturnedValue(node: Node, owner: Node,
    model: SemanticModel): boolean {
  let body = ownerBody(owner);
  if (body == null) {
    return false;
  }
  var cur = node;
  while (true) {
    if ((body as Node) === cur) {
      return true;
    }
    let p = model.getParent(cur);
    if (p == null) {
      return false;
    }
    if (p is ReturnStatement) {
      let arg = p.argument;
      return arg != null && (arg as Node) === cur && !p.isTail &&
          enclosingFunction(p, model) === (owner as Node);
    }
    if (p is IfExpression) {
      if (p.test === cur) {
        return false;
      }
    } else if (p is MatchCase) {
      if ((p.body as Node) !== cur) {
        return false;
      }
    } else if (p is MatchExpression) {
      if ((p.discriminant as Node) === cur) {
        return false;
      }
    } else if (p is ExpressionStatement) {
      let block = model.getParent(p);
      if (!(block is BlockStatement)) {
        return false;
      }
      let stmts = block.body;
      if (stmts.length == 0 || (stmts[stmts.length - 1] as Node) !== (p as Node)) {
        return false;
      }
      cur = block;
      continue;
    } else {
      return false;
    }
    cur = p as Node;
  }
  return false;
}

/**
 * The method `member` calls, from the function `dc.f`: its receiver's
 * static class, instantiated as in `dc.f`, and the method that class
 * resolves the name to. Null when it cannot be told, such as in a body
 * no instantiation is known for.
 */
function methodTargetOf(dc: DemandContext, member: MemberExpression,
    model: SemanticModel): String | null {
  if (member.optional || member.isSymbolAccess) {
    return null;
  }
  let objType = model.getNodeType(member.object);
  if (objType == null) {
    return null;
  }
  let receiver = baseType(substituteTypeParamsInFunctionContext(dc.wasm, dc.f,
      objType as Type));
  if (!(receiver is ClassType) || !isConcrete(receiver)) {
    return null;
  }
  let name = memberKeyOf(model, member.property as Node);
  if (name == "") {
    return null;
  }
  let md = dc.pass.cha.findImplementingMethod(receiver, name, model.isStaticAccess(member));
  if (md == null) {
    return null;
  }
  let declaring = declaringInstantiation(dc.pass.classDecls, receiver, md as Node);
  if (declaring == null) {
    return null;
  }
  let target = methodTargetKey((md as Node).id as i32, declaring);
  if (md.typeParameters == null) {
    return target;
  }
  // A generic method: the specialization for the call's solved type
  // arguments, instantiated as `dc.f` sees them (lowering's slot name).
  let ft = model.getNodeType(member);
  if (!(ft is FunctionType)) {
    return null;
  }
  let typeArgs = ft.typeArguments;
  if (typeArgs == null) {
    return null;
  }
  let args = new Array<Type>();
  for (let t in typeArgs) {
    let arg = substituteTypeParamsInFunctionContext(dc.wasm, dc.f, t);
    if (!isConcrete(arg) || containsErasedType(arg)) {
      return null;
    }
    args.push(arg);
  }
  return specMethodTargetKey(target, getSpecializedName(name, args));
}

/**
 * `arg` as an argument of a direct call to a module-level function or of
 * a method call.
 */
function forwardOf(dc: DemandContext, call: CallExpression,
    arg: Node, model: SemanticModel): Forward | null {
  let callee = call.callee;
  if (callee is MemberExpression) {
    if ((callee.object as Node) === arg) {
      return null;
    }
    let target = methodTargetOf(dc, callee, model);
    if (target == null) {
      return null;
    }
    for (var k = 0; k < call.args.length; k += 1) {
      if ((call.args[k] as Node) === arg) {
        return new Forward(methodKey(target), k);
      }
    }
    return null;
  }
  if (!(callee is Identifier)) {
    return null;
  }
  let key = functionCallKey(dc, callee, model);
  if (key == null) {
    return null;
  }
  for (var k = 0; k < call.args.length; k += 1) {
    if ((call.args[k] as Node) === arg) {
      return new Forward(key, k);
    }
  }
  return null;
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19