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

70.7 KiB Raw
/**
 * Compiler entry point for the self-hosted Zena compiler.
 *
 * A `Compiler` is a host, a standard library root and a package map.
 * Each compile names its own entry point and target, so one compiler
 * serves many compiles, at several targets; `compiler-target.zena`
 * holds what belongs to one target.
 *
 * Usage:
 *   let compiler = createCompiler(host, {stdlibRoot, packages});
 *   let result = await compiler.compile({entry: '/path/to/main.zena', target: 'js'});
 *   let checked = checkCompilation(result);
 *   for (let file in result.files) {
 *     // process each library in dependency order
 *   }
 */

import { Set, HashMap, HashSet, OrderedHashMap } from 'zena:collections';

import {
  CheckSettings, CompileOptions, CompilerOptions, sameCheckSettings
} from './compiler-options.zena';
import {
  CompilationResult, CompilerTarget, makeCompilerTarget
} from './compiler-target.zena';
import {
  CompilerHost, SourceFile, moduleStatements
} from './library-loader.zena';
import { getStandardPrelude } from './prelude.zena';
import { allWellKnown, isWellKnown, wellKnownName } from './well-known.zena';
import { Symbol } from './scope/symbol.zena';
import { Scope } from './scope/scope.zena';
import { ScopeBuilder, ScopeResult, ModuleExports as ScopeModuleExports } from './scope/scope-builder.zena';
import {
  ImportDeclaration, ExportFromDeclaration, ExportAllDeclaration, MemberExpression, FieldDefinition, MethodDefinition, ClassDeclaration, Identifier, Expression, ThisExpression, Node, Module, SourceLocation,
} from './ast.zena';
import { parse } from './parser.zena';
import { checkModule, beginModule, finishModule, ModuleCheck, CheckResult, SharedCheckerState } from './checker.zena';
import { walk } from './visitor.zena';
import { Diagnostic, DiagnosticCode, DiagnosticSeverity, SourceSpan, spanOf } from './diagnostics.zena';
import { PurityAnalysis } from './analysis/purity.zena';
import { SemanticModel } from './semantic-model.zena';
import { nowMs, performance } from './time.zena';
import {
  Type, ClassType, FunctionType, InterfaceType, MixinType, EnumType, MemberInfo, MemberTable, FieldInfo, MethodInfo, RecordType, TypeParameterType, TypeAliasType, SymbolType, ArrayType, TupleType, InlineTupleType, InlineParamType, InlineRecordType, UnionType, BoolLiteralType, StringLiteralType, NumLiteralType, I32Type, U32Type, I64Type, U64Type, F32Type, F64Type, U8Type, U16Type, I8Type, I16Type, V128Type, BooleanType, VoidType, NullType, NeverType, HoleType, ErrorType, UnknownType, AnyRefType, EqRefType, ExternRefType, ThisType, ErasedType, declaringModuleOf, sameNumericLiteralRaw,
} from './types.zena';
import { growable } from 'zena:core';

/** Re-export types used by consumers. */
export { CompilerHost } from './library-loader.zena';
export {
  CompilerOptions, CompileOptions, CheckSettings
} from './compiler-options.zena';
export { CompilationResult, CompilerTarget } from './compiler-target.zena';
export { PackageConfig, ModuleExport, ResolvedModule } from './module-resolver.zena';
export { SourceFile, SourceFileGraph } from './library-loader.zena';
export {
  loadWorkspace, buildStdlibConfig, withBuiltinPackages
} from './package-manifest.zena';
export { getStandardPrelude } from './prelude.zena';
export { ScopeResult, Symbol, UnresolvedName } from './scope.zena';
export { CheckResult } from './checker.zena';
export { SemanticModel } from './semantic-model.zena';
export { Diagnostic, DiagnosticSeverity, DiagnosticCode, SourceSpan } from './diagnostics.zena';
export { typeToString } from './types.zena';

/**
 * Whether to check every body of every module loaded, the way the
 * compiler did before bodies outside the local project waited for
 * reachability to ask for them. Diagnostics in a dependency are
 * reported again under it, which is what makes it worth having: a
 * type error in the standard library is otherwise invisible to a
 * program that merely uses it.
 *
 * Set from the environment by whoever reads one — `compileFile` reads
 * ZENA_CHECK_ALL_BODIES. Not read here, because this module is
 * compiled for the browser and for `lsp.wasm` too, and `zena:cli` is
 * not a library those targets have.
 */
var checkAllBodies = false;

/** See `checkAllBodies`. */
export function setCheckAllBodies(value: boolean): void {
  checkAllBodies = value;
}

/**
 * The result of type-checking an entire program.
 *
 * Contains per-module CheckResults keyed by file path, plus an aggregated
 * diagnostics array for convenience. The `results` map mirrors the module
 * graph: each module's CheckResult was produced independently from its own
 * AST, ScopeResult, and dependency scope exports.
 */
export final class ProgramCheckResult {
  /**
   * What the checker was told when this was produced.
   *
   * Every map here is keyed by file path, and a path names a different
   * library on a different target, so these results belong to one
   * target. `checkCompilation` carries a previous result forward only
   * when its settings match; a caller compiling several targets keeps
   * one result per target.
   */
  settings: CheckSettings;

  /** Per-module check results, keyed by file path. */
  results: HashMap<String, CheckResult>;

  /** Source text at the time each module was checked, keyed by file path. */
  sources: HashMap<String, String>;

  /** AST Module at the time each module was checked, keyed by file path. */
  asts: HashMap<String, Module>;

  /**
   * Export signatures at the time each module was checked, keyed by file path.
   * Each value maps exported names (prefixed "v:" or "t:") to their resolved
   * Type objects. Used for incremental invalidation: if a file's exports
   * change, its dependents must be re-checked.
   */
  exportSignatures: HashMap<String, HashMap<String, Type>>;

  /** Aggregated diagnostics from all modules. */
  diagnostics = new Array<Diagnostic>();

  /** The entry module's check result (convenience accessor). */
  entry: CheckResult;

  /** Shared checker state containing ID counters and prelude types. */
  sharedState: SharedCheckerState;

  /**
   * The scope tree each module was checked against, keyed by file path.
   * A result can only carry forward while its module's scope tree is
   * the same object: bindings are keyed by Symbol id, and a rebuilt
   * scope (the loader rebuilds a file's scope when a file it imports is
   * invalidated) mints fresh Symbols the old result cannot answer for.
   * That matters when another module consults the carried result
   * through the new Symbols — a member of the same import cycle does.
   */
  var scopes = new Map<String, ScopeResult>();

  new(
    this.settings: CheckSettings,
    this.results: HashMap<String, CheckResult>,
    this.sources: HashMap<String, String>,
    this.asts: HashMap<String, Module>,
    this.exportSignatures: HashMap<String, HashMap<String, Type>>,
    this.entry: CheckResult,
    this.sharedState: SharedCheckerState
  ) {
    // Aggregate diagnostics from all modules.
    for (let key in results.keys()) {
      for (let diagnostic in results[key].diagnostics) {
        this.diagnostics.push(diagnostic);
      }
    }
  }
}

/**
 * The main compiler entry point.
 *
 * A compiler is a host, a standard library root and a package map, and
 * it lives across compiles. Each compile names its own entry point and
 * target (`CompileOptions`), so one compiler serves several — including
 * several targets, which it keeps apart by holding a `CompilerTarget`
 * per target: a specifier resolves to a different library on each, so
 * the two library sets cannot share a cache.
 *
 * Only the host is shared between targets. A library loaded on two
 * targets is read, parsed, scoped and checked on each, because what it
 * imports may be two different libraries; what one compiler saves is
 * the second compiler, and everything a repeat compile on the same
 * target would have reloaded.
 *
 * A compiler runs one operation at a time. `compile`, `invalidate` and
 * `refreshCache` await the host, and a second call on the same compiler
 * while one is in flight would see a loader cache the first has half
 * filled, so it throws instead. A caller whose requests can overlap
 * queues them (the language service does).
 */
export final class Compiler {
  #host: CompilerHost;
  #options: CompilerOptions;

  /** One per target compiled so far, keyed by canonical target name. */
  #targets = new Map<String, CompilerTarget>();

  /** What is in flight, named for the error a second call gets. */
  var #inFlight: String | null = null;

  new(host: CompilerHost, options: CompilerOptions)
    : #host = host, #options = options;

  /** Marks `operation` as in flight; throws when one already is. */
  #begin(operation: String): void {
    let current = this.#inFlight;
    if (current != null) {
      throw new Error(
          `Compiler.${operation} called while ${current} is in flight; ` +
          `a compiler runs one operation at a time`);
    }
    this.#inFlight = operation;
  }

  /**
   * This compiler's state for `target`, built on first use: the
   * resolver, the file set and the scopes of everything compiled for
   * that target. Throws on a target name the compiler does not know.
   */
  forTarget(target: String): CompilerTarget {
    if (let (true, existing) = this.#targets.get(target)) {
      return existing;
    }
    let made = makeCompilerTarget(this.#host, target, this.#options);
    this.#targets[made.target] = made;
    return made;
  }

  /** The targets this compiler has compiled, by canonical name. */
  compiledTargets: GrowableArray<String> {
    get {
      let names = new Array<String>(this.#targets.size);
      for (let name in this.#targets.keys()) {
        names.push(name);
      }
      return names;
    }
  }

  /**
   * Compile a program from an entry point on one target.
   *
   * Loads and parses the entry and its transitive dependencies, runs
   * scope analysis, wires up cross-module imports, and returns the
   * files in topological order. Type checking is `checkCompilation`'s.
   *
   * NOTE: this does NOT detect file changes. In push-based environments
   * (an editor), call `invalidate(path)` first; in pull-based ones (a
   * build), call `refreshCache()`.
   */
  async compile(options: CompileOptions): Future<CompilationResult> {
    this.#begin("compile");
    try {
      return await this.forTarget(options.target).compile(options);
    } finally {
      this.#inFlight = null;
    }
  }

  /** Time spent reading source, across every target. */
  loadTime: f64 {
    get {
      var total = 0.0;
      for (let name in this.#targets.keys()) {
        total += this.#targets[name].loadTime;
      }
      return total;
    }
  }

  /** Time spent parsing, across every target. */
  parseTime: f64 {
    get {
      var total = 0.0;
      for (let name in this.#targets.keys()) {
        total += this.#targets[name].parseTime;
      }
      return total;
    }
  }

  /**
   * Delete a library from every target's cache (push-based).
   *
   * Every target, because a file that is gone from disk is gone on all
   * of them. The same goes for `invalidate` and `refreshCache`: what
   * changed is the source, which no target owns.
   */
  delete(path: String): void {
    for (let name in this.#targets.keys()) {
      this.#targets[name].delete(path);
    }
  }

  /**
   * Invalidate a single cached file and re-load it (push-based).
   *
   * Call this when a specific file's source has changed, e.g. the
   * language service receiving an editor update.
   */
  async invalidate(path: String): Future<void> {
    this.#begin("invalidate");
    try {
      for (let name in this.#targets.keys()) {
        await this.#targets[name].invalidate(path);
      }
    } finally {
      this.#inFlight = null;
    }
  }

  /**
   * Re-read all cached non-stdlib files from the host (pull-based).
   *
   * For batch and CLI environments, where no notification of file
   * changes is available. In push-based environments prefer
   * `invalidate(path)`.
   */
  async refreshCache(): Future<void> {
    this.#begin("refreshCache");
    try {
      for (let name in this.#targets.keys()) {
        await this.#targets[name].refreshCache();
      }
    } finally {
      this.#inFlight = null;
    }
  }
}

/**
 * Create a Compiler. Prefer this over `new Compiler(...)`: the
 * constructor's shape is the compiler's business, this is the API.
 */
export function createCompiler(
  host: CompilerHost,
  options: CompilerOptions
): Compiler {
  return new Compiler(host, options);
}

// ============================================================================
// Single-File API (for LSP and quick checks)
// ============================================================================

/**
 * Parse, scope-analyze, and type-check a single source string.
 *
 * This is the simplest way to get diagnostics and type information for
 * one file without setting up a full Compiler with module resolution.
 * Cross-module imports won't resolve, but parse errors, scope errors,
 * and single-file type errors will all be reported.
 *
 * Returns a CheckResult containing the SemanticModel (node types,
 * binding types, name resolution) and diagnostics.
 */
export function checkSource(source: String, path: String): CheckResult {
  let ast = parse(source, path);
  let builder = new ScopeBuilder(path, null);
  let scopeResult = builder.build(ast);
  return checkModule(ast, scopeResult, null, null, false);
}

// ============================================================================
// Compilation-Level Checking
// ============================================================================

/**
 * Compute the export signature for a checked module.
 *
 * The signature maps each exported name (prefixed with "v:" for values
 * or "t:" for types) to its resolved Type object. Two modules have the
 * same export signature if and only if they export the same names with
 * the same types (compared via signatureTypeEquals).
 *
 * Used for incremental invalidation: if a file is re-checked and its
 * export signature is unchanged, its dependents don't need re-checking.
 */
function computeExportSignature(
  exports: ScopeModuleExports,
  rootScope: Scope,
  model: SemanticModel
) {
  let sig = new Map<String, Type>();

  let iter = exports.keys();
  for (let name in iter) {
    let exp = (if (let (true, val) = exports.get(name)) { val } else { null }) as Symbol;
    if (exp.isValue()) {
      let scopeInfo = rootScope.getLocal(name);
      let bt = if (scopeInfo != null) {
        model.getBindingType(scopeInfo)
      } else {
        null
      };
      if (bt != null) {
        sig["v:" + name] = bt;
      }
    }
    
    if (exp.isType()) {
      // For types, prefer the explicitly registered exportType over localType binding if possible.
      // We'll just read from getExportType first, fallback to getBindingType(localType).
      // Wait, this is just for hashing signatures right now in compiler.zena.
      // Let's use getExportType correctly.
      let bt = model.getExportType(name);
      let t = if (bt != null) {
        bt
      } else {
        let scopeInfo = rootScope.getLocal(name);
        if (scopeInfo != null) {
          model.getBindingType(scopeInfo)
        } else {
          null
        }
      };
      
      if (t != null) {
        sig["t:" + name] = t;
      }
    }
  }

  return sig;
}

/**
 * Deep structural comparison of two types for export signature purposes.
 *
 * Uses === (referential equality) as a fast path: if a type object is
 * carried forward from a previous check, it's the *same* ref and we
 * return true immediately. For re-checked files that produce fresh type
 * objects, falls back to deep structural comparison.
 *
 * Unlike `typesEqual` in the checker (which compares ClassType by id),
 * this compares ClassType by (name, sourcePath) and then recursively
 * checks all members, flags, supertypes, etc. This correctly detects
 * changes to class shape across re-checks where fresh ids are assigned.
 *
 * A visited set (keyed on "name:sourcePath" for classes/interfaces/mixins)
 * breaks cycles in recursive types like `class Node { next: Node | null }`.
 * Optimistic assumption: if already visiting a pair, return true.
 */
export function signatureTypeEquals(a: Type, b: Type): boolean {
  let visited = new Set<String>();
  return signatureTypeEqualsRec(a, b, visited);
}

function signatureTypeEqualsRec(a: Type, b: Type, visited: HashSet<String>): boolean {
  // Fast path: referential identity (singletons, carried-forward objects).
  if (a === b) { return true; }

  return match (a) {
    case I32Type: b is I32Type
    case U32Type: b is U32Type
    case I64Type: b is I64Type
    case U64Type: b is U64Type
    case F32Type: b is F32Type
    case F64Type: b is F64Type
    case U8Type: b is U8Type
    case U16Type: b is U16Type
    case I8Type: b is I8Type
    case I16Type: b is I16Type
    case V128Type: b is V128Type
    case BooleanType: b is BooleanType
    case VoidType: b is VoidType
    case NullType: b is NullType
    case NeverType: b is NeverType
    case HoleType: b is HoleType
    case ErrorType: b is ErrorType
    case UnknownType: b is UnknownType
    case AnyRefType: b is AnyRefType
    // Codegen-internal (types.zena): the checker never builds one, but
    // the match is exhaustive over Type.
    case ErasedType: b is ErasedType
    case EqRefType: b is EqRefType
    case ExternRefType: b is ExternRefType
    case ThisType: b is ThisType

    case BoolLiteralType {value as va}: {
      if (let BoolLiteralType {value as vb} = b) va == vb else false
    }
    case StringLiteralType {value as va}: {
      if (let StringLiteralType {value as vb} = b) va == vb else false
    }
    case NumLiteralType {raw as va}: {
      if (let NumLiteralType {raw as vb} = b) sameNumericLiteralRaw(va, vb) else false
    }

    case ArrayType {elementType as ea}: {
      if (let ArrayType {elementType as eb} = b) {
        signatureTypeEqualsRec(ea, eb, visited)
      } else {
        false
      }
    }
    case TupleType {elementTypes as ta}: {
      if (let TupleType {elementTypes as tb} = b) {
        arrayTypesEqual(ta, tb, visited)
      } else {
        false
      }
    }
    case InlineTupleType {elementTypes as ta}: {
      if (let InlineTupleType {elementTypes as tb} = b) {
        arrayTypesEqual(ta, tb, visited)
      } else {
        false
      }
    }
    case InlineParamType {param as pa}: {
      if (let InlineParamType {param as pb} = b) {
        signatureTypeEqualsRec(pa, pb, visited)
      } else {
        false
      }
    }
    case InlineRecordType {record as ra}: {
      if (let InlineRecordType {record as rb} = b) {
        signatureTypeEqualsRec(ra, rb, visited)
      } else {
        false
      }
    }
    case UnionType {types as ua}: {
      if (let UnionType {types as ub} = b) {
        arrayTypesEqual(ua, ub, visited)
      } else {
        false
      }
    }

    case RecordType as ra: {
      match (b) {
        case RecordType as rb: {
          if (ra.properties.size != rb.properties.size) { return false; }
          let keys = ra.properties.keys();
          for (let key in keys) {
            if (!rb.properties.has(key)) { return false; }
            if (!signatureTypeEqualsRec(ra.properties[key], rb.properties[key], visited)) {
              return false;
            }
          }
          // Compare optional properties.
          if (ra.optionalProperties == null && rb.optionalProperties == null) { return true; }
          if (ra.optionalProperties == null || rb.optionalProperties == null) { return false; }
          let optA = ra.optionalProperties as HashSet<String>;
          let optB = rb.optionalProperties as HashSet<String>;
          stringSetEquals(optA, optB)
        }
        case _: false
      }
    }

    case FunctionType as fa: {
      match (b) {
        case FunctionType as fb: functionTypeEquals(fa, fb, visited)
        case _: false
      }
    }

    case ClassType as ca: {
      match (b) {
        case ClassType as cb: classTypeEquals(ca, cb, visited)
        case _: false
      }
    }

    case InterfaceType as ia: {
      match (b) {
        case InterfaceType as ib: interfaceTypeEquals(ia, ib, visited)
        case _: false
      }
    }

    case MixinType as ma: {
      match (b) {
        case MixinType as mb: mixinTypeEquals(ma, mb, visited)
        case _: false
      }
    }

    case TypeParameterType as tpa: {
      match (b) {
        case TypeParameterType as tpb: {
          if (tpa.name != tpb.name) { return false; }
          if (tpa.constraint == null && tpb.constraint == null) { return true; }
          if (tpa.constraint == null || tpb.constraint == null) { return false; }
          signatureTypeEqualsRec(tpa.constraint as Type, tpb.constraint as Type, visited)
        }
        case _: false
      }
    }

    case EnumType as ea: {
      match (b) {
        case EnumType as eb: {
          if (ea.name != eb.name || ea.declaringModule != eb.declaringModule ||
              ea.declaration.members.length != eb.declaration.members.length) {
            return false;
          }
          var i = 0;
          while (i < ea.declaration.members.length) {
            if (ea.declaration.members[i].name.name != eb.declaration.members[i].name.name) {
              return false;
            }
            i += 1;
          }
          signatureTypeEqualsRec(ea.backingType, eb.backingType, visited)
        }
        case _: false
      }
    }

    case TypeAliasType as taa: {
      match (b) {
        case TypeAliasType as tab: {
          taa.name == tab.name
            && taa.isDistinct == tab.isDistinct
            && taa.isOpaque == tab.isOpaque
            && taa.declaringModule == tab.declaringModule
            && signatureTypeEqualsRec(taa.target, tab.target, visited)
        }
        case _: false
      }
    }

    case SymbolType as sa: {
      match (b) {
        case SymbolType as sb: sa.id == sb.id
        case _: false
      }
    }
  };
}

/**
 * Compare two arrays of types elementwise.
 */
function arrayTypesEqual(
  a: Array<Type>, b: Array<Type>, visited: HashSet<String>
): boolean {
  if (a.length != b.length) {
    return false;
  }
  for (var i = 0; i < a.length; i += 1) {
    if (!signatureTypeEqualsRec(a[i], b[i], visited)) {
      return false;
    }
  }
  return true;
}

/**
 * Compare optional type-parameter arrays.
 */
function typeParamsEqual(
  a: Array<TypeParameterType> | null,
  b: Array<TypeParameterType> | null,
  visited: HashSet<String>
): boolean {
  if (a == null && b == null) {
    return true;
  }
  if (a == null || b == null) {
    return false;
  }
  if (a.length != b.length) {
    return false;
  }
  for (var i = 0; i < a.length; i += 1) {
    if (!signatureTypeEqualsRec(a[i], b[i], visited)) {
      return false;
    }
  }
  return true;
}

/** 
 * Compare optional type-argument arrays.
 */
function typeArgsEqual(
  a: Array<Type> | null,
  b: Array<Type> | null,
  visited: HashSet<String>
): boolean {
  if (a == null && b == null) {
    return true;
  }
  if (a == null || b == null) {
    return false;
  }
  return arrayTypesEqual(a, b, visited);
}

/**
 * Compare two HashMaps of name → Type.
 */
function typeMapEquals(
  a: HashMap<String, Type>, b: HashMap<String, Type>, visited: HashSet<String>
): boolean {
  if (a.size != b.size) {
    return false;
  }
  for (let key in a.keys()) {
    if (!b.has(key)) {
      return false;
    }
    if (!signatureTypeEqualsRec(a[key], b[key], visited)) {
      return false;
    }
  }
  return true;
}

/**
 * Compare two Maps of name → MemberInfo.
 */
function membersMapEquals(
  a: MemberTable, b: MemberTable, visited: HashSet<String>
): boolean {
  if (a.size != b.size) {
    return false;
  }
  for (let key in a.keys()) {
    if (!b.has(key)) {
      return false;
    }
    let aMem = a[key];
    let bMem = b[key];
    if (aMem.isAbstract != bMem.isAbstract) {
      return false;
    }
    if (aMem.isStatic != bMem.isStatic) {
      return false;
    }
    if (aMem.isPrivate != bMem.isPrivate) {
      return false;
    }
    match (aMem) {
      case FieldInfo as aFi: {
        match (bMem) {
          case FieldInfo as bFi: {
            if (aFi.isMutable != bFi.isMutable) {
              return false;
            }
            if (aFi.hasInitializer != bFi.hasInitializer) {
              return false;
            }
          }
          case _: { return false; }
        }
      }
      case MethodInfo as aMi: {
        match (bMem) {
          case MethodInfo as bMi: {
            if (aMi.isFinal != bMi.isFinal) {
              return false;
            }
          }
          case _: { return false; }
        }
      }
      case _: { return false; }
    }
    if (!signatureTypeEqualsRec(aMem.type, bMem.type, visited)) {
      return false;
    }
  }
  return true;
}

/** 
 * Compare two HashMaps of name → boolean.
 */
function boolMapEquals(
  a: HashMap<String, boolean>, b: HashMap<String, boolean>
): boolean {
  if (a.size != b.size) {
    return false;
  }
  for (let key in a.keys()) {
    if (!b.has(key) || a[key] != b[key]) {
      return false;
    }
  }
  return true;
}

/**
 * Compare two HashSets of String.
 */
function stringSetEquals(a: HashSet<String>, b: HashSet<String>): boolean {
  if (a.size != b.size) {
    return false;
  }
  for (let key in a) {
    if (!b.has(key)) {
      return false;
    }
  }
  return true;
}

/**
 * Compare nullable Set<String>.
 */
function nullableStringSetEquals(
  a: HashSet<String> | null, b: HashSet<String> | null
): boolean {
  if (a == null && b == null) {
    return true;
  }
  if (a == null || b == null) {
    return false;
  }
  return stringSetEquals(a, b);
}

/** Deep comparison of FunctionType for signature purposes. */
function functionTypeEquals(
  fa: FunctionType, fb: FunctionType, visited: HashSet<String>
): boolean {
  if (fa === fb) { return true; }
  if (fa.parameters.length != fb.parameters.length) { return false; }
  if (!signatureTypeEqualsRec(fa.returnType, fb.returnType, visited)) { return false; }
  var i = 0;
  while (i < fa.parameters.length) {
    if (!signatureTypeEqualsRec(fa.parameters[i], fb.parameters[i], visited)) { return false; }
    i += 1;
  }
  if (fa.isFinal != fb.isFinal) { return false; }
  if (fa.isAbstract != fb.isAbstract) { return false; }
  if (!typeParamsEqual(fa.typeParameters, fb.typeParameters, visited)) { return false; }
  if (!typeArgsEqual(fa.typeArguments, fb.typeArguments, visited)) { return false; }
  return optionalFlagsEqual(fa.optionalParameters, fb.optionalParameters);
}

/**
 * Whether two signatures mark the same parameters optional.
 *
 * `null` and an array of all `false` both mean "none are", so they
 * compare equal. It used to be a difference, which no re-check of one
 * library's own source could expose — both sides come from the same
 * declaration — but which made two interchangeable signatures compare
 * unequal as soon as anything compared a `declare function` against a
 * defined one. A missing flag is a flag that is false.
 */
function optionalFlagsEqual(
  a: GrowableArray<boolean> | null,
  b: GrowableArray<boolean> | null
): boolean {
  let aLen = if (a == null) { 0 } else { a.length };
  let bLen = if (b == null) { 0 } else { b.length };
  let len = if (aLen > bLen) { aLen } else { bLen };
  for (var i = 0; i < len; i += 1) {
    let aFlag = a != null && i < a.length && a[i];
    let bFlag = b != null && i < b.length && b[i];
    if (aFlag != bFlag) { return false; }
  }
  return true;
}

/** Deep comparison of ClassType for signature purposes. */
function classTypeEquals(
  ca: ClassType, cb: ClassType, visited: HashSet<String>
): boolean {
  if (ca === cb) { return true; }
  if (ca.name != cb.name) { return false; }
  if (ca.sourcePath != cb.sourcePath) { return false; }

  // Cycle guard: if we're already comparing this class pair, assume equal.
  let visitKey = `c:${ca.name}:${ca.sourcePath}`;
  if (visited.has(visitKey)) { return true; }
  visited.add(visitKey);

  // Boolean flags.
  if (ca.isFinal != cb.isFinal) { return false; }
  if (ca.isCaseClass != cb.isCaseClass) { return false; }
  if (ca.isAbstract != cb.isAbstract) { return false; }
  if (ca.isExtension != cb.isExtension) { return false; }
  if (ca.isSealed != cb.isSealed) { return false; }
  if (ca.isMixinIntermediate != cb.isMixinIntermediate) { return false; }

  // Type parameters and arguments.
  if (!typeParamsEqual(ca.typeParameters, cb.typeParameters, visited)) { return false; }
  if (!typeArgsEqual(ca.typeArguments, cb.typeArguments, visited)) { return false; }

  // Supertype.
  if (ca.superType == null && cb.superType != null) { return false; }
  if (ca.superType != null && cb.superType == null) { return false; }
  let {superType} = ca;
  if (superType != null && cb.superType != null) {
    if (!classTypeEquals(superType, cb.superType as ClassType, visited)) {
      return false;
    }
  }

  // Members.
  if (!membersMapEquals(ca.members, cb.members, visited)) { return false; }
  if (!membersMapEquals(ca.staticMembers, cb.staticMembers, visited)) { return false; }

  // Constructor.
  if (ca.constructorType == null && cb.constructorType != null) { return false; }
  if (ca.constructorType != null && cb.constructorType == null) { return false; }
  let {constructorType} = ca;
  if (constructorType != null && cb.constructorType != null) {
    if (!functionTypeEquals(
      constructorType,
      cb.constructorType as FunctionType,
      visited
    )) { return false; }
  }

  // Sealed variants.
  if (ca.sealedVariants == null && cb.sealedVariants == null) { return true; }
  if (ca.sealedVariants == null || cb.sealedVariants == null) { return false; }
  let sva = ca.sealedVariants as GrowableArray<ClassType>;
  let svb = cb.sealedVariants as GrowableArray<ClassType>;
  if (sva.length != svb.length) { return false; }
  var svi = 0;
  while (svi < sva.length) {
    if (!classTypeEquals(sva[svi], svb[svi], visited)) { return false; }
    svi += 1;
  }

  // Optional boolean maps.
  if (!nullableStringSetEquals(ca.declaredFields, cb.declaredFields)) { return false; }
  return nullableStringSetEquals(ca.forwardVariantNames, cb.forwardVariantNames);
}

/** Deep comparison of InterfaceType for signature purposes. */
function interfaceTypeEquals(
  ia: InterfaceType, ib: InterfaceType, visited: HashSet<String>
): boolean {
  if (ia === ib) { return true; }
  if (ia.name != ib.name) { return false; }

  let visitKey = "i:" + ia.name;
  if (visited.has(visitKey)) { return true; }
  visited.add(visitKey);

  if (!typeParamsEqual(ia.typeParameters, ib.typeParameters, visited)) { return false; }
  if (!typeArgsEqual(ia.typeArguments, ib.typeArguments, visited)) { return false; }
  if (!membersMapEquals(ia.members, ib.members, visited)) { return false; }

  // extendsList
  if (ia.extendsList.length != ib.extendsList.length) { return false; }
  var ei = 0;
  while (ei < ia.extendsList.length) {
    if (!interfaceTypeEquals(ia.extendsList[ei], ib.extendsList[ei], visited)) { return false; }
    ei += 1;
  }

  return true;
}

/** Deep comparison of MixinType for signature purposes. */
function mixinTypeEquals(
  ma: MixinType, mb: MixinType, visited: HashSet<String>
): boolean {
  if (ma === mb) { return true; }
  if (ma.name != mb.name) { return false; }

  let visitKey = "m:" + ma.name;
  if (visited.has(visitKey)) { return true; }
  visited.add(visitKey);

  if (!typeParamsEqual(ma.typeParameters, mb.typeParameters, visited)) { return false; }
  if (!typeArgsEqual(ma.typeArguments, mb.typeArguments, visited)) { return false; }
  if (!membersMapEquals(ma.members, mb.members, visited)) { return false; }
  if (!membersMapEquals(ma.staticMembers, mb.staticMembers, visited)) { return false; }

  // onType
  if (ma.onType == null && mb.onType != null) { return false; }
  if (ma.onType != null && mb.onType == null) { return false; }
  let {onType} = ma;
  if (onType != null && mb.onType != null) {
    if (!classTypeEquals(onType as ClassType, mb.onType as ClassType, visited)) {
      return false;
    }
  }

  return true;
}

/**
 * Build a reverse dependency map with imported-name tracking.
 *
 * For each file, records which files depend on it AND which names they
 * import. This enables precise invalidation: when a dependency's export
 * signature changes, a dependent is only invalidated if one of the names
 * it actually i * Structure: depPath → Map<importerPath, GrowableArray<String>>
 * where the GrowableArray<String> contains the imported names (prefixed "v:" or
 * "t:" to match signature keys).
 */
function buildReverseDeps(
  files: GrowableArray<SourceFile>
) {
  let reverseDeps = new Map<String, HashMap<String, GrowableArray<String>>>();

  for (let file in files) {
    // Walk the AST to find import/re-export declarations and their names.
    for (let statement in moduleStatements(file)) {
      match (statement) {
        case ImportDeclaration {moduleSpecifier, imports}: {
          let specifier = moduleSpecifier.value;
          if (file.imports.has(specifier)) {
            let depPath = file.imports[specifier];
            if (!reverseDeps.has(depPath)) {
              reverseDeps[depPath] = new Map<String, GrowableArray<String>>();
            }
            let depMap = reverseDeps[depPath];
            if (!depMap.has(file.path)) {
              depMap[file.path] = new Array<String>(4);
            }
            let names = depMap[file.path];
            var k = 0;
            while (k < imports.length) {
              let importedName = imports[k].imported.name;
              if (importedName == "*") {
                names.push("*");
              } else {
                names.push("v:" + importedName);
                names.push("t:" + importedName);
              }
              k += 1;
            }
          }
        }
        case ExportAllDeclaration {moduleSpecifier}: {
          let specifier = moduleSpecifier.value;
          if (file.imports.has(specifier)) {
            let depPath = file.imports[specifier];
            if (!reverseDeps.has(depPath)) {
              reverseDeps[depPath] = new Map<String, GrowableArray<String>>();
            }
            let depMap = reverseDeps[depPath];
            if (!depMap.has(file.path)) {
              depMap[file.path] = new Array<String>(4);
            }
            let names = depMap[file.path];
            names.push("*");
          }
        }
        case ExportFromDeclaration {moduleSpecifier, specifiers}: {
          let specifier = moduleSpecifier.value;
          if (file.imports.has(specifier)) {
            let depPath = file.imports[specifier];
            if (!reverseDeps.has(depPath)) {
              reverseDeps[depPath] = new Map<String, GrowableArray<String>>();
            }
            let depMap = reverseDeps[depPath];
            if (!depMap.has(file.path)) {
              depMap[file.path] = new Array<String>(4);
            }
            let names = depMap[file.path];
            var m = 0;
            while (m < specifiers.length) {
              let importedName = specifiers[m].imported.name;
              names.push("v:" + importedName);
              names.push("t:" + importedName);
              m += 1;
            }
          }
        }
        case _: {}
      }
    }
  }
  return reverseDeps;
}

/**
 * Check a single file: build its depExports/depModels and run checkModule.
 */
/**
 * What a file's check reads from the rest of the compilation: the
 * export maps of the modules it imports (by specifier), and the models
 * of every module checked so far (by specifier and by path) — including
 * cycle members that have registered their declarations but not yet
 * checked their bodies (`inProgress`), whose models already hold those
 * declarations.
 */
final class FileCheckInputs {
  depExports: HashMap<String, ScopeModuleExports>;
  depModels: HashMap<String, SemanticModel>;
  laterPaths: HashSet<String> | null;
  new(this.depExports, this.depModels, this.laterPaths);
}

function fileCheckInputs(
  file: SourceFile,
  allResults: HashMap<String, CheckResult>,
  inProgress: HashMap<String, ModuleCheck> | null,
  allFiles: GrowableArray<SourceFile>,
  recheckPaths: HashSet<String> | null
) {
  let depExports = new Map<String, ScopeModuleExports>();
  let depModels = new Map<String, SemanticModel>();
  let specIter = file.imports.keys();
  for (let specifier in specIter) {
    let depPath = file.imports[specifier];
    var li = 0;
    while (li < allFiles.length) {
      let dep = allFiles[li];
      if (dep.path == depPath && dep.scopeResult != null) {
        let sr = dep.scopeResult as ScopeResult;
        depExports[specifier] = sr.exports;
      }
      li = li + 1;
    }
    if (allResults.has(depPath)) {
      depModels[specifier] = allResults[depPath].model;
    } else if (inProgress != null && inProgress.has(depPath)) {
      depModels[specifier] = inProgress[depPath].ctx.model;
    }
  }

  // Populate depModels with all known semantics models by their absolute path.
  let resIter = allResults.keys();
  for (let path in resIter) {
    depModels[path] = allResults[path].model;
  }
  if (inProgress != null) {
    let progIter = inProgress.keys();
    for (let path in progIter) {
      if (path != file.path) {
        depModels[path] = inProgress[path].ctx.model;
      }
    }
  }

  // Modules that run after this one in evaluation order: an import
  // whose declaration originates in one of them crosses an import
  // cycle's back edge (docs/design/import-cycles.md). Null in the
  // common acyclic case so the checker skips the bookkeeping.
  var laterPaths: HashSet<String> | null = null;
  if (recheckPaths != null) {
    let later = new Set<String>();
    var seen = false;
    for (let other in allFiles) {
      if (seen) {
        later.add(other.path);
      }
      if (other.path == file.path) {
        seen = true;
      }
    }
    laterPaths = later;
  }
  return new FileCheckInputs(depExports, depModels, laterPaths);
}

/**
 * The first half of checking a member of an import cycle: register its
 * declarations. Its bodies are checked by finishModule once every
 * member of the cycle has registered.
 */
function beginFile(
  file: SourceFile,
  allResults: HashMap<String, CheckResult>,
  inProgress: HashMap<String, ModuleCheck>,
  allFiles: GrowableArray<SourceFile>,
  emitLocations: boolean,
  sharedState: SharedCheckerState,
  warnUnnecessaryCasts: boolean,
  recheckPaths: HashSet<String> | null,
  deferBodies: boolean
) {
  let inputs = fileCheckInputs(file, allResults, inProgress, allFiles, recheckPaths);
  return beginModule(
    file.ast,
    file.scopeResult as ScopeResult,
    inputs.depExports,
    inputs.depModels,
    emitLocations,
    sharedState,
    warnUnnecessaryCasts,
    inputs.laterPaths,
    recheckPaths,
    null,
    deferBodies);
}

/**
 * Make every model checked or registered since a cycle member began
 * visible to it, before its bodies are checked.
 */
function refreshDepModels(
  mc: ModuleCheck,
  file: SourceFile,
  allResults: HashMap<String, CheckResult>,
  inProgress: HashMap<String, ModuleCheck>
) {
  let specIter = file.imports.keys();
  for (let specifier in specIter) {
    let depPath = file.imports[specifier];
    if (allResults.has(depPath)) {
      mc.ctx.addDepModel(specifier, allResults[depPath].model);
    } else if (inProgress.has(depPath)) {
      mc.ctx.addDepModel(specifier, inProgress[depPath].ctx.model);
    }
  }
  let resIter = allResults.keys();
  for (let path in resIter) {
    mc.ctx.addDepModel(path, allResults[path].model);
  }
  let progIter = inProgress.keys();
  for (let path in progIter) {
    if (path != file.path) {
      mc.ctx.addDepModel(path, inProgress[path].ctx.model);
    }
  }
}

function checkFile(
  file: SourceFile,
  allResults: HashMap<String, CheckResult>,
  allFiles: GrowableArray<SourceFile>,
  emitLocations: boolean,
  sharedState: SharedCheckerState,
  warnUnnecessaryCasts: boolean,
  recheckPaths: HashSet<String> | null,
  deferBodies: boolean
) {
  let inputs = fileCheckInputs(file, allResults, null, allFiles, recheckPaths);
  let depExports = inputs.depExports;
  let depModels = inputs.depModels;
  let laterPaths = inputs.laterPaths;

  // The same file's model from an earlier pass over this compilation
  // (the cycle-driven re-check): the splice of default arguments into
  // call nodes persists in the shared AST, and the re-check needs the
  // prior pass's caller-written-count records to not re-resolve those
  // spliced expressions in this module's scope.
  let priorModel = if (allResults.has(file.path)) allResults[file.path].model else null;

  return checkModule(
    file.ast,
    file.scopeResult as ScopeResult,
    depExports,
    depModels,
    emitLocations,
    sharedState,
    warnUnnecessaryCasts,
    laterPaths,
    recheckPaths,
    priorModel,
    deferBodies);
}

/**
 * The strongly connected components of a compilation's import graph
 * (Tarjan's algorithm), as lists of indexes into the files.
 *
 * A component with more than one member is an import cycle. Its members
 * are the modules whose first check ran before some module they import
 * from had a model, and so the only ones that need the second checking
 * pass of docs/design/import-cycles.md. A module outside every cycle
 * that imports from one is checked once, after that cycle's second
 * pass: the files are in evaluation (post-)order, so every member of a
 * cycle precedes every module outside it that imports from it.
 */
final class ImportComponents {
  #files: GrowableArray<SourceFile>;
  #pathIndex: HashMap<String, i32>;
  #index = new Array<i32>();
  #low = new Array<i32>();
  #onStack = new Array<boolean>();
  #stack = new Array<i32>();
  var #next = 0;
  components = new Array<GrowableArray<i32>>();

  new(files: GrowableArray<SourceFile>, pathIndex: HashMap<String, i32>)
    : #files = files, #pathIndex = pathIndex {
    var i = 0;
    while (i < files.length) {
      this.#index.push(-1);
      this.#low.push(0);
      this.#onStack.push(false);
      i += 1;
    }
    i = 0;
    while (i < files.length) {
      if (this.#index[i] == -1) {
        this.#connect(i);
      }
      i += 1;
    }
  }

  #connect(v: i32): void {
    this.#index[v] = this.#next;
    this.#low[v] = this.#next;
    this.#next += 1;
    this.#stack.push(v);
    this.#onStack[v] = true;
    let file = this.#files[v];
    let iter = file.imports.keys();
    for (let spec in iter) {
      let depPath = file.imports[spec];
      if (!this.#pathIndex.has(depPath)) {
        continue;
      }
      let w = this.#pathIndex[depPath];
      if (this.#index[w] == -1) {
        this.#connect(w);
        if (this.#low[w] < this.#low[v]) {
          this.#low[v] = this.#low[w];
        }
      } else if (this.#onStack[w]) {
        if (this.#index[w] < this.#low[v]) {
          this.#low[v] = this.#index[w];
        }
      }
    }
    if (this.#low[v] == this.#index[v]) {
      let component = new Array<i32>();
      var w = -1;
      while (w != v) {
        w = this.#stack.pop();
        this.#onStack[w] = false;
        component.push(w);
      }
      this.components.push(component);
    }
  }
}

/**
 * Settles the purity obligations of freshly checked modules: reports
 * each `static` condition and `old` argument that would change
 * something a caller can see, with the chain of calls that leads to
 * the change (docs/design/pure-functions.md).
 *
 * A module that already has errors is passed over. Its expressions may
 * hold nodes without types, which the analysis would report as effects
 * it cannot follow, a second error for one mistake.
 */
function checkPurityObligations(checked: GrowableArray<CheckResult>, state: SharedCheckerState) {
  let analysis = new PurityAnalysis(state.modelIndex);
  for (let checkResult in checked) {
    let {model, diagnostics} = checkResult;
    if (model.purityObligations.length == 0) { continue; }
    var hasErrors = false;
    for (let reported in diagnostics) {
      if (reported.severity == DiagnosticSeverity.Error) { hasErrors = true; }
    }
    if (hasErrors) { continue; }
    for (let obligation in model.purityObligations) {
      let verdict = analysis.verdictOfExpression(
        obligation.expression, model, obligation.inEnsures
      );
      let reason = verdict.changesBecause;
      if (reason == null) { continue; }
      let loc = reason.loc ?? obligation.expression.loc;
      let span: SourceSpan | null = if (loc != null) { spanOf(loc, model.sourcePath) } else { null };
      let diagnostic = new Diagnostic(
        DiagnosticCode.ImpureExpression,
        `${obligation.subject} cannot have effects: it ${reason.render()}.`,
        DiagnosticSeverity.Error, span
      );
      diagnostics.push(diagnostic);
      model.addDiagnostic(diagnostic);
    }
  }
}

/**
 * Type-check all modules in a compilation result in dependency order.
 *
 * Uses export signature comparison for precise incremental invalidation:
 * when a file changes, only dependents that import names whose types
 * actually changed are re-checked. Invalidation propagates through the
 * dependency graph but stops as soon as a re-checked file's export
 * signature is unchanged for the names that matter.
 *
 * Algorithm:
 * 1. Identify files whose source text changed (must be re-checked).
 * 2. Re-check changed files in topo order. After each, compare the new
 *    export signature to the previous one.
 * 3. For each direct dependent, check whether any of the names it
 *    actually imports were affected by the signature change. Only
 *    invalidate if so.
 * 4. For invalidated files: re-check even though their source is
 *    unchanged, then repeat the per-name comparison for their own
 *    dependents.
 * 5. Files whose imports are all stable carry forward their previous
 *    CheckResult.
 */
export function checkCompilation(
  result: CompilationResult,
  carried: ProgramCheckResult | null = null
): ProgramCheckResult {
  let settings = {
    target: result.options.target,
    emitLocations: result.compilerOptions.emitLocations ?? false,
    warnUnnecessaryCasts: result.compilerOptions.warnUnnecessaryCasts ?? false,
  };
  let {emitLocations, warnUnnecessaryCasts} = settings;

  // A result checked under different settings answers a different
  // question: another target means the same path is another library,
  // and the two flags change the diagnostics and the model a file's
  // check produces. Carrying one forward would serve its answers for
  // this compile's files, so drop it and check from scratch.
  let previous = if (carried != null && sameCheckSettings(carried.settings, settings)) {
    carried
  } else {
    null
  };

  let allResults = new Map<String, CheckResult>();
  let allSources = new Map<String, String>();
  let allAsts = new Map<String, Module>();
  let allSignatures = new Map<String, HashMap<String, Type>>();

  let sharedState = previous?.sharedState ?? new SharedCheckerState();

  // Build reverse dependency map for invalidation propagation.
  let reverseDeps = buildReverseDeps(result.files);

  // Set of file paths that must be (re-)checked. Start with files whose
  // source text changed or that are new, or that import missing/deleted files.
  let mustCheck = new Set<String>();
  if (previous != null) {
    let currentPaths = new Set<String>();
    for (let file in result.files) {
      currentPaths.add(file.path);
    }

    for (let file in result.files) {
      if (!previous.sources.has(file.path) || previous.sources[file.path] != file.source ||
          !previous.asts.has(file.path) || previous.asts[file.path] != file.ast) {
        mustCheck.add(file.path);
      } else if (!file.isStdlib) {
        for (let spec in file.imports.keys()) {
          let depPath = file.imports[spec];
          if (!depPath.startsWith("zena:") && !currentPaths.has(depPath)) {
            mustCheck.add(file.path);
          }
        }
      }
    }

    let prevIter = previous.sources.keys();
    for (let prevPath in prevIter) {
      if (!currentPaths.has(prevPath)) {
        for (let file in result.files) {
          let importIter = file.imports.keys();
          for (let spec in importIter) {
            if (file.imports[spec] == prevPath) {
              mustCheck.add(file.path);
            }
          }
        }
      }
    }
    // Whether an expression is free of effects depends on the bodies of
    // what it calls, in whichever files those are, and a body can change
    // without its file's export signature changing. So when anything is
    // checked again, so is every file that asked that of an expression.
    if (mustCheck.size > 0) {
      for (let file in result.files) {
        if (previous.results.has(file.path) &&
            previous.results[file.path].model.purityObligations.length > 0) {
          mustCheck.add(file.path);
        }
      }
    }
    for (let path in mustCheck) {
      sharedState.invalidatePath(path);
    }
  }

  // The local project: the entry point and everything it reaches by
  // relative import. A package specifier ('zena:core',
  // 'zena-lang:wit-parser/parser') crosses out of the project, and what lies
  // beyond it is a dependency. A local file is checked in full — a
  // typo in a function nobody calls yet is still the author's to fix —
  // and a dependency has its function and class bodies checked only
  // where reachability reaches them.
  let localPaths = new Set<String>();
  let byPath = new Map<String, SourceFile>();
  for (let f in result.files) {
    byPath[f.path] = f;
  }
  let localQueue = growable<String>([result.entry.path]);
  localPaths.add(result.entry.path);
  var lq = 0;
  while (lq < localQueue.length) {
    let path = localQueue[lq];
    lq += 1;
    if (let (true, f) = byPath.get(path)) {
      for (let entry in f.imports) {
        let specifier = entry.key;
        if (!specifier.startsWith("./") && !specifier.startsWith("../")) {
          continue;
        }
        let target = entry.value;
        if (localPaths.add(target)) {
          localQueue.push(target);
        }
      }
    }
  }
  let defersBodies = (path: String) =>
      !checkAllBodies && !localPaths.has(path);

  let tCheck = performance.start("check");

  // When the import graph has cycles, compute the re-check closure up
  // front (docs/design/import-cycles.md): a file with a back-edge
  // import (a dependency later in evaluation order) cannot resolve it
  // on the first pass, and any file importing from a re-checked file
  // must also re-check. The set feeds both the second pass below and
  // the checker's cycle rules (types and inferred signatures may only
  // cross a back edge when they originate OUTSIDE this set — an
  // origin checked exactly once has stable, unique types).
  //
  // The set is the members of the import cycles themselves — the
  // strongly connected components with more than one module. It used
  // to also take in every module importing from a re-checked one,
  // transitively, which made a cycle anywhere in the standard library
  // re-check the whole program (the prelude reaches everything). Each
  // cycle's second pass now runs as soon as its last member has had
  // its first, before any module outside the cycle that imports from
  // it is checked, so those importers see final models and check once.
  var recheckPaths: HashSet<String> | null = null;
  // For the index of a cycle's last member in evaluation order: the
  // cycle's members, in evaluation order.
  let cyclesEndingAt = new Map<i32, GrowableArray<SourceFile>>();
  if (result.hasCycle) {
    let pathIndex = new Map<String, i32>();
    var pi = 0;
    while (pi < result.files.length) {
      pathIndex[result.files[pi].path] = pi;
      pi = pi + 1;
    }
    let recheck = new Set<String>();
    let finder = new ImportComponents(result.files, pathIndex);
    for (let component in finder.components) {
      if (component.length < 2) {
        continue;
      }
      var last = -1;
      let inComponent = new Set<i32>();
      for (let member in component) {
        inComponent.add(member);
        if (member > last) {
          last = member;
        }
      }
      let members = new Array<SourceFile>();
      var mi = 0;
      while (mi < result.files.length) {
        if (inComponent.has(mi)) {
          members.push(result.files[mi]);
          recheck.add(result.files[mi].path);
        }
        mi += 1;
      }
      cyclesEndingAt[last] = members;
    }
    recheckPaths = recheck;
  }

  // What a checked file contributes: its result, the prelude and
  // well-known declarations it owns, and its export signature — which
  // decides whether its importers must re-check.
  //
  // The prelude and well-known records come first, as a helper of their
  // own: a member of an import cycle records them once the whole cycle
  // has registered, before any member's bodies are checked.
  let recordPreludeNames = (file: SourceFile, model: SemanticModel) => {
    if (file.isStdlib && file.scopeResult != null) {
      let exports = (file.scopeResult as ScopeResult).exports;
      let stdlibPrelude = getStandardPrelude("js");
      let specIter = stdlibPrelude.keys();
      for (let specifier in specIter) {
        let names = stdlibPrelude[specifier];
        for (let name in names) {
          if (exports.has(name)) {
            let exp = exports[name] as Symbol;
            if (exp.isType()) {
              let bt = model.getExportType(name);
              let t = if (bt != null) { bt } else { model.getBindingType(exp) };
              if (t != null) {
                sharedState.preludeTypes[name] = t;
              }
            }
            if (exp.isValue()) {
              let t = model.getBindingType(exp);
              if (t != null) {
                sharedState.preludeValues[name] = t;
              }
            }
          }
        }
      }

      // Record the well-known declarations this file owns. Membership is
      // decided by the library that declares the type — read off the type
      // itself, the same value every other `isWellKnown` caller passes —
      // so a program that declares its own `Error` or `Array` never lands
      // here. `file.path` is not that value: a stdlib file may be loaded
      // under a filesystem path rather than its `zena:` id.
      for (let w in allWellKnown()) {
        let name = wellKnownName(w);
        if (!exports.has(name)) { continue; }
        let exp = exports[name] as Symbol;
        if (!exp.isType()) { continue; }
        let bt = model.getExportType(name);
        let t = if (bt != null) { bt } else { model.getBindingType(exp) };
        if (t == null) { continue; }
        let declaredIn = declaringModuleOf(t as Type);
        if (declaredIn == null) { continue; }
        if (!isWellKnown(w, name, declaredIn as String)) { continue; }
        sharedState.wellKnownTypes[w as i32] = t;
      }
    }
  };

  // The results this call produced, as opposed to carried forward.
  let checkedNow = new Array<CheckResult>();

  let recordChecked = (file: SourceFile, checkResult: CheckResult) => {
    checkedNow.push(checkResult);
    allResults[file.path] = checkResult;
    allSources[file.path] = file.source;
    allAsts[file.path] = file.ast;
    recordPreludeNames(file, checkResult.model);

    // Compute export signature and compare with previous.
    let {scopeResult} = file;
    if (scopeResult != null) {
      let sr = scopeResult;
      let newSig = computeExportSignature(sr.exports, sr.rootScope, checkResult.model);
      allSignatures[file.path] = newSig;

      // If the signature changed, invalidate dependents that import
      // affected names. A dependent is only invalidated if at least one
      // of the names it imports from this file actually changed type.
      if (previous != null && reverseDeps.has(file.path)) {
        let oldSig = if (previous.exportSignatures.has(file.path)) {
          previous.exportSignatures[file.path]
        } else {
          new Map<String, Type>()  // new file — all names are "changed"
        };

        let importerMap = reverseDeps[file.path];
        let importerIter = importerMap.keys();
        for (let importerPath in importerIter) {
          let importedNames = importerMap[importerPath];
          // Check if any of the names this importer uses actually changed.
          var affected = false;
          for (let sigKey in importedNames) {
            let hasOld = oldSig.has(sigKey);
            let hasNew = newSig.has(sigKey);
            if (hasOld != hasNew) {
              // Name added or removed.
              affected = true;
            } else if (hasOld && hasNew) {
              if (!signatureTypeEquals(oldSig[sigKey], newSig[sigKey])) {
                affected = true;
              }
            }
          }
          if (affected) {
            mustCheck.add(importerPath);
          }
        }
      }
    }

  };

  // Members of import cycles that have registered their declarations
  // and not yet checked their bodies, by path.
  let inProgress = new Map<String, ModuleCheck>();
  let allScopes = new Map<String, ScopeResult>();

  // Check each file in topo order.
  var fileIndex = -1;
  for (let file in result.files) {
    fileIndex += 1;
    if (file.scopeResult != null) {
      allScopes[file.path] = file.scopeResult as ScopeResult;
    }
    // Carry forward if source unchanged AND not invalidated by a
    // dependency AND checked against this same scope tree (see
    // ProgramCheckResult.scopes).
    let inCycleNow = recheckPaths != null && recheckPaths.has(file.path);
    let sameScope = previous != null && file.scopeResult != null &&
        previous.scopes.has(file.path) &&
        previous.scopes[file.path] === (file.scopeResult as ScopeResult);
    if (previous != null && !mustCheck.has(file.path) && sameScope) {
      if (previous.sources.has(file.path) && previous.results.has(file.path) &&
          previous.asts.has(file.path) && previous.asts[file.path] == file.ast) {
        allResults[file.path] = previous.results[file.path];
        allSources[file.path] = file.source;
        allAsts[file.path] = file.ast;
        if (previous.exportSignatures.has(file.path)) {
          allSignatures[file.path] = previous.exportSignatures[file.path];
        }
        // Counted, not timed: how many files a warm compiler carried
        // forward is what says whether the incremental path is working.
        performance.add("check-carried", 0.0);
        continue;
      }
    }

    if (inCycleNow) {
      // A member of an import cycle registers its declarations now;
      // its bodies wait until every member has registered
      // (docs/design/import-cycles.md): a body may construct a class
      // from later in the cycle, and needs that class's constructor.
      // Counted, not timed: `beginFile` is `check-register`.
      performance.add("check-cycle-members", 0.0);
      let mc = beginFile(file, allResults, inProgress, result.files, emitLocations, sharedState, warnUnnecessaryCasts, recheckPaths, defersBodies(file.path));
      inProgress[file.path] = mc;
      sharedState.inProgressModules[file.path] = mc.ctx;
    } else {
      // Counted, not timed: `checkFile` is register plus bodies plus
      // exports, each of which times itself, so timing it here as well
      // would report the same milliseconds twice.
      performance.add("check-whole-files", 0.0);
      recordChecked(file, checkFile(file, allResults, result.files, emitLocations, sharedState, warnUnnecessaryCasts, recheckPaths, defersBodies(file.path)));
    }

    // The last member of a cycle has registered. Every canonical type
    // the cycle declares is filled in now, but the registrations that
    // ran while some were still empty shells built their signatures'
    // instantiations from those shells, and an instantiation copies
    // the structure it finds. So register every member once more, in
    // evaluation order — signatures only, which is cheap — and then
    // check every member's bodies, once, against the second
    // registrations. The first registrations are discarded, their
    // diagnostics with them. Modules outside the cycle come later in
    // evaluation order and are checked once, against these results.
    if (let (true, members) = cyclesEndingAt.get(fileIndex)) {
      // The compiler's own lookups of well-known declarations — the
      // `String` an enum is backed by, the `Future` and `Awaited` an
      // `await` is typed with — read shared records that are otherwise
      // filled only as each module finishes, which inside a cycle is
      // after every body in it has been checked. Record them from the
      // first registrations: the canonical types exist by now, and the
      // second registrations and the bodies below read them.
      for (let member in members) {
        if (let (true, mc) = inProgress.get(member.path)) {
          recordPreludeNames(member, mc.ctx.model);
        }
      }
      for (let member in members) {
        if (inProgress.has(member.path)) {
          // A cycle member registers twice; the second registration is
          // `check-register` again, so this only counts them.
          performance.add("check-cycle-reregistrations", 0.0);
          let again = beginFile(member, allResults, inProgress, result.files, emitLocations, sharedState, warnUnnecessaryCasts, recheckPaths, defersBodies(member.path));
          inProgress[member.path] = again;
          sharedState.inProgressModules[member.path] = again.ctx;
        }
      }
      for (let member in members) {
        if (let (true, mc) = inProgress.get(member.path)) {
          let tRefresh = nowMs();
          refreshDepModels(mc, member, allResults, inProgress);
          performance.add("check-cycle-refresh", nowMs() - tRefresh);
          let checkResult = finishModule(mc);
          sharedState.inProgressModules.delete(member.path);
          inProgress.delete(member.path);
          recordChecked(member, checkResult);
        }
      }
    }
  }
  performance.end(tCheck);

  let tPurity = nowMs();
  checkPurityObligations(checkedNow, sharedState);
  performance.add("check-purity", nowMs() - tPurity);

  // The entry module's result is always the last in topo order.
  let entryResult = allResults[result.entry.path];
  let checked = new ProgramCheckResult(settings, allResults, allSources,
      allAsts, allSignatures, entryResult, sharedState);
  checked.scopes = allScopes;
  return checked;
}

// ============================================================================
// AST Query Utilities
// ============================================================================

/**
 * Find the innermost AST node whose span contains the given byte offset.
 *
 * Walks the tree depth-first. When a node's loc contains `offset`, we
 * record it and descend into children. The last (deepest) match wins,
 * giving the most specific node at that position.
 *
 * Useful for LSP features that map a cursor position to an AST node
 * (hover, go-to-definition, etc.).
 */
export function findNodeAtOffset(root: Node, offset: i32): Node | null {
  var found: Node | null = null;
  walk(root, (node): boolean => {
    if (node.loc != null) {
      let loc = node.loc as SourceLocation;
      if (offset >= loc.start && offset < loc.end) {
        found = node;
        return true;  // descend — a child may be more specific
      }
      return false;  // outside this node's span, skip subtree
    }
    return true;  // no loc info, descend anyway
  }, (node) => {});
  return found;
}

/**
 * Find the innermost MemberExpression containing the given byte offset.
 */
export function findMemberExpressionAtOffset(root: Node, offset: i32): MemberExpression | null {
  var found: MemberExpression | null = null;
  walk(root, (node): boolean => {
    if (node is MemberExpression) {
      if (node.loc != null) {
        let loc = node.loc as SourceLocation;
        if (offset >= loc.start && offset <= loc.end + 1) {
          found = node;
          return true;
        }
      }
    }
    return true;
  }, (node) => {});
  return found;
}

/**
 * On-demand member definition resolution for goto-definition.
 *
 * Given a byte offset in a module's AST, checks whether the offset falls
 * on a MemberExpression property (e.g., the `x` in `p.x`). If so, looks
 * up the object's type from the SemanticModel and finds the field or
 * method declaration in the owning class.
 *
 * Returns a SourceSpan pointing to the FieldDefinition, MethodDefinition,
 * or CaseClassParam, or null if the offset is not on a member access.
 */
export function resolveMemberDefinition(
  ast: Module,
  offset: i32,
  model: SemanticModel,
  scopeResult: ScopeResult,
  target: CompilerTarget
): SourceSpan | null {
  // Find the deepest node at the offset.
  let node = findNodeAtOffset(ast, offset);
  if (node == null) { return null; }

  // Check if it's a MemberExpression and the offset is on the property.
  match (node) {
    case MemberExpression {object, property, loc}: {
      // Verify the offset is actually on the property identifier,
      // not on the object expression.
      if (property.loc == null) { return null; }
      let propLoc = property.loc as SourceLocation;
      if (offset < propLoc.start || offset >= propLoc.end) { return null; }

      // Get the object's type.
      // We can't use model.getNodeType(object) directly because the
      // MemberExpression and its object child share the same loc.start
      // offset, and setNodeType overwrites the object's type with the
      // member access result type.
      // Instead, resolve through the scope system when the object is
      // a simple identifier, and fall back to getNodeType only when the
      // object has a different loc.start than the MemberExpression.
      let objType = resolveObjectType(object, model, scopeResult, loc, ast, null);
      if (objType == null) { return null; }

      match (objType) {
        case ClassType as ct: {
          return findMemberInClass(ct, property.name, target);
        }
        case _: { return null; }
      }
    }
    case _: { return null; }
  }
}

/**
 * Resolve the type of a member expression's object node.
 *
 * For simple identifiers, uses the scope system (ReferenceMap → Symbol
 * → binding type) to avoid the loc.start collision issue with getNodeType.
 * For compound expressions, falls back to getNodeType if they have a
 * different start offset than their parent MemberExpression.
 */
export function resolveObjectType(
  object: Expression,
  model: SemanticModel,
  scopeResult: ScopeResult,
  parentLoc: SourceLocation | null,
  ast: Module,
  sharedState: SharedCheckerState | null = null
): Type | null {
  // For identifiers, resolve via the model's own reference map.
  // This ensures the Symbol matches the model's binding types,
  // even when the AST is from a newer compilation than the model
  // (carry-forward scenario).
  match (object as Node) {
    case Identifier {name, loc as objLoc}: {
      let sym = model.resolve(object);
      if (sym != null) {
        let bindingType = model.getBindingType(sym);
        if (bindingType != null) { return bindingType; }
      }
      if (scopeResult != null) {
        let symInfo = scopeResult.rootScope.resolve(name);
        if (symInfo != null) {
          let bindingType = model.getBindingType(symInfo);
          if (bindingType != null) { return bindingType; }
          if (symInfo.declaration != null) {
            let declType = model.getNodeType(symInfo.declaration as Node);
            if (declType != null) { return declType; }
          }
        }
      }
      let nodeType = model.getNodeType(object);
      if (nodeType != null) { return nodeType; }
      if (sharedState != null) {
        if (let (true, pv) = sharedState.preludeValues.get(name)) {
          return pv;
        }
      }
      return null;
    }
    case ThisExpression: {
      // `this` always shares loc.start with the parent MemberExpression,
      // so getNodeType returns the member result type, not the class type.
      // Instead, find the enclosing ClassDeclaration and look up its type.
      return findEnclosingClassType(ast, object, model);
    }
    case _: {
      // For compound expressions (call, index, nested member, etc.),
      // use getNodeType if the object's start differs from the parent's.
      if (object.loc != null && parentLoc != null) {
        let oLoc = object.loc as SourceLocation;
        if (oLoc.start != parentLoc.start) {
          return model.getNodeType(object);
        }
      }
      return null;
    }
  }
}

/**
 * Find the ClassType for the enclosing class of a `this` expression.
 *
 * Walks the module's top-level declarations to find the ClassDeclaration
 * whose span contains the ThisExpression, then looks up the class name's
 * type from the SemanticModel.
 */
function findEnclosingClassType(ast: Module, thisExpr: Expression, model: SemanticModel): Type | null {
  if (thisExpr.loc == null) { return null; }
  let thisLoc = thisExpr.loc as SourceLocation;
  let thisOffset = thisLoc.start;

  var i = 0;
  while (i < ast.body.length) {
    match (ast.body[i]) {
      case ClassDeclaration as cd: {
        if (cd.loc != null) {
          let cdLoc = cd.loc as SourceLocation;
          if (thisOffset >= cdLoc.start && thisOffset < cdLoc.end) {
            // Found the enclosing class. The checker stores the ClassType
            // on the ClassDeclaration node via declareBinding → setNodeType.
            return model.getNodeType(ast.body[i]);
          }
        }
      }
      case _: {}
    }
    i += 1;
  }
  return null;
}


/**
 * Find a field or method declaration in a class's AST.
 *
 * Uses ClassType.sourcePath to locate the source file, then walks
 * the ClassDeclaration body to find the matching member.
 */
function findMemberInClass(
  ct: ClassType,
  memberName: String,
  target: CompilerTarget
): SourceSpan | null {
  // For instantiated generics, look at the original source class.
  var sourceClass = ct;
  let {genericSource} = ct;
  if (genericSource != null) {
    sourceClass = genericSource;
  }

  let filePath = sourceClass.sourcePath;
  if (filePath.length == 0) { return null; }

  // Get the source file from the target's loader cache.
  let sourceFile = target.getSourceFile(filePath);
  if (sourceFile == null) { return null; }

  // Find the ClassDeclaration in the file's AST.
  var classDecl: ClassDeclaration | null = null;
  var si = 0;
  while (si < sourceFile.ast.body.length) {
    match (sourceFile.ast.body[si]) {
      case ClassDeclaration as cd: {
        if (cd.name.name == sourceClass.name) {
          classDecl = cd;
        }
      }
      case _: {}
    }
    si += 1;
  }

  if (classDecl == null) { return null; }

  // Check case class params first (e.g., `class Point(x: f64, y: f64)`).
  let {caseParams} = classDecl;
  if (caseParams != null) {
    let params = caseParams;
    var pi = 0;
    while (pi < params.length) {
      if (params[pi].name.name == memberName) {
        if (params[pi].loc != null) {
          return spanOf(params[pi].loc as SourceLocation, filePath);
        }
      }
      pi += 1;
    }
  }

  // Search class body for FieldDefinition or MethodDefinition.
  var bi = 0;
  while (bi < classDecl.body.length) {
    match (classDecl.body[bi]) {
      case FieldDefinition as fd: {
        let fieldName = if (let Identifier {name} = fd.name) name else "";
        if (fieldName == memberName && fd.loc != null) {
          return spanOf(fd.loc as SourceLocation, filePath);
        }
      }
      case MethodDefinition as md: {
        let methodName = if (let Identifier {name} = md.name) name else "";
        if (methodName == memberName && md.loc != null) {
          return spanOf(md.loc as SourceLocation, filePath);
        }
      }
      case _: {}
    }
    bi += 1;
  }

  // Check inherited members from superclass.
  let {superType} = sourceClass;
  if (superType != null) {
    return findMemberInClass(superType, memberName, target);
  }

  return null;
}
VersionPublishedDependenciesApproved by
0.0.2-preview.1 2026-11-19