# Self-Hosted Compiler Design

_The compiler is fully self-hosting: stage-2 rebuilds are byte-identical,
and code generation goes through the ZIR backend — see [ir.md](./ir.md).
The milestone statuses below record where each area stands._

## Strategy: Informed Port

We're not doing a blind copy of the TypeScript compiler, and we're not starting
from scratch. We're doing an **informed port**: use the working TypeScript
implementation as a reference, but critically review each component before
porting it, cleaning up known problems and laying groundwork for a better
architecture.

This avoids second-system syndrome (we have a working compiler and a test suite)
while giving us the opportunity to fix structural issues that are expensive to
fix in the TypeScript codebase.

### Guiding Principles

1. **Port what works, redesign what's broken.** The TypeScript compiler works.
   Most of its logic is correct. Port the algorithms; improve the data
   structures.
2. **Immutable ASTs.** The parser produces ASTs that are never mutated. Semantic
   information lives in separate side tables. This enables parallelism,
   incremental compilation, and LSP reuse.
3. **Identity-based types.** Type objects are interned and compared by identity,
   never by name. This is already mostly true in the TS compiler but we make it
   a hard invariant.
4. **Prepare for parallelism.** Design data structures so that parsing and
   per-module checking can happen independently. Don't implement parallelism yet,
   but don't create structures that prevent it.
5. **Prepare for incrementality.** Version-stamp source files. Keep ASTs
   reusable across edits. Don't implement incremental recheck yet, but make sure
   the architecture doesn't preclude it.
6. **Visitors everywhere.** Every pass over the AST or type graph uses a visitor
   or structured traversal. No ad-hoc recursive walks buried in checking or
   codegen logic.
7. **Deliver value early.** Ship a formatter before a checker, and an LSP before
   codegen. Each milestone is independently useful.

---

## Architecture Overview

```
Source File (.zena)
    │
    ▼
┌──────────┐
│  Lexer   │  Token stream (per-file, parallelizable)
└────┬─────┘
     ▼
┌──────────┐
│  Parser  │  Immutable AST (per-file, parallelizable)
└────┬─────┘
     ▼
┌─────────────────────┐
│  Module Resolution  │  Import graph, topological ordering
└────┬────────────────┘
     ▼
┌─────────────────────┐
│  Checker            │  On-demand type materialization, validation
│  (per-module,       │  Types created lazily from scope declarations
│   DAG-parallel)     │  Semantic model as output
└────┬────────────────┘
     ▼
┌─────────────────────┐
│  Analysis Passes    │  Whole-program + per-function (visitor-based)
│  ├─ DCE             │  Reachability from entry point
│  ├─ Devirtualization│  Effectively-final, static dispatch
│  ├─ Capture analysis│  Closure variables, mutability
│  └─ Adaptations     │  Fat-pointer packing for dispatch
└────┬────────────────┘
     ▼
┌─────────────────────┐
│  Codegen            │  AST + SemanticModel → ZIR → WASM binary
└─────────────────────┘  (lowering, GVN, emission — see ir.md)
```

---

## Key Architectural Decisions

### 1. Immutable AST + Semantic Side Tables

**Current TS problem:** The checker sets `inferredType` directly on AST nodes.
This mutates the parser's output, coupling the AST to a specific check pass and
preventing reuse.

**Self-hosted design:** The AST is a pure data structure produced by the parser.
The checker produces a `SemanticModel` — a separate data structure that maps AST
node IDs to their semantic information.

```
// AST nodes get a unique ID assigned by the parser
class Node {
  id: i32       // Unique within a module
  loc: SourceLoc
}

// The semantic model maps node IDs to types, bindings, etc.
class SemanticModel {
  // Per-node information
  nodeTypes: Map<i32, Type>           // node.id → inferred type
  resolvedBindings: Map<i32, Binding> // identifier.id → what it refers to

  // Per-declaration information
  classTypes: Map<i32, ClassType>     // classDecl.id → checker type
  functionTypes: Map<i32, FunctionType>

  // Diagnostics
  diagnostics: Array<Diagnostic>
}
```

**Why node IDs instead of AST node identity?** Several reasons:

- We'll eventually want to send ASTs across worker boundaries. We control our
  own serialization (it doesn't have to be JSON — it can be closer to
  structured clone, and we can even reconstruct object references across
  multiple messages with bookkeeping). But IDs make this simpler and cheaper.
- Node IDs make side tables simple arrays or maps rather than WeakMaps, which
  Zena doesn't have.
- Side tables keyed by integer IDs can be efficiently serialized to disk for
  incremental compilation caches.
- When the compiler runs in-memory (e.g., in a web-based playground), integer
  IDs avoid holding entire ASTs alive through WeakMap entries.

**Note on serialization:** We have full control over our serialization format.
We can define binary formats that reconstruct object graphs, not just trees.
So "survives serialization" isn't the only reason for IDs — they're also
simpler, faster for lookups (array indexing vs. hash lookup), and naturally
stable across compiler invocations (useful for caching).

**Trade-off:** Slightly more verbose lookups (`model.getType(expr.id)` vs
`expr.inferredType`), but the benefits for parallelism, incrementality, and
architectural cleanliness are substantial.

### 2. Consolidated Type Representation

**Current TS problem:** Class member information is scattered across ClassType
(checker), ClassInfo (codegen), ClassDeclaration (AST), and various maps in
CodegenContext. Fields alone exist in 4+ places with different representations.

**Self-hosted design:** One authoritative type representation with clear
ownership.

```zena
class ClassType {
  id: i32                    // Unique, interned
  name: String
  declaration: i32           // AST node ID (link back to source)

  // Generic info
  typeParameters: Array<TypeParameter>
  typeArguments: Array<Type> // Empty for uninstantiated
  genericSource: ClassType?  // Points to uninstantiated template

  // Hierarchy
  superType: ClassType?
  interfaces: Array<InterfaceType>
  mixins: Array<MixinType>

  // Members — all in one place
  members: Map<String, Member>

  // Flags
  isFinal: boolean
  isAbstract: boolean
  isExtension: boolean
  onType: Type?              // For extension classes
}

// A single Member type covers fields, methods, accessors
enum MemberKind { Field, Method, Getter, Setter, Constructor }

class Member {
  name: String
  kind: MemberKind
  type: Type                 // Field type or function signature
  isPrivate: boolean
  isFinal: boolean
  isAbstract: boolean
  isStatic: boolean
  isMutable: boolean         // For fields: var vs let
  vtableSlot: i32            // -1 if not in vtable (set by checker)
  declaration: i32           // AST node ID
}
```

Codegen adds its own index tables (WASM struct indices, function indices), but
these are purely codegen-local and reference back to the checker's types by
identity.

### 3. Type Interning

Same approach as the TS compiler, but cleaner:

```
class TypeContext {
  // All type creation goes through here to ensure interning
  intern(type: Type): Type

  // Factory methods that auto-intern
  makeClassType(name: String, typeParams: ...): ClassType
  instantiateClass(template: ClassType, args: Array<Type>): ClassType
  makeUnionType(members: Array<Type>): UnionType
  // ...

  // Identity check is just reference equality after interning
  // type1 === type2  iff  they represent the same type
}
```

The key insight from the TS implementation: interning makes identity-based
lookups in WeakMaps reliable. We keep this. The improvement is that _all_ type
creation goes through the `TypeContext`, not just generic instantiation.

### 4. Checker: On-Demand Type Resolution

**Current TS design:** A single 5-pass checker processes all modules together.
Passes 1-4 pre-declare types and functions; pass 5 does full checking.

**Self-hosted design:** Scope analysis is the single source of truth for name
resolution. The checker never searches for names — it materializes `Type`
objects on demand from declarations that scope analysis already found.

#### Scope Analysis Owns All Names

The `ScopeBuilder` registers every name in the appropriate namespace:
classes, interfaces, mixins, enums, type aliases, sealed variants, imports,
and local bindings. Prelude types (`String`, `Array`, `Box`, `Option`, etc.)
are implicit imports at the root scope — not special-cased. By the time the
checker runs, every name reference resolves to a `Symbol` in the scope
chain, or doesn't exist (and scope analysis has already flagged it).

#### The Checker Materializes Types

The checker maintains a single `Symbol → Type` map. When it needs a
type for a name, it asks scope analysis for the `Symbol`, then
materializes a `Type` object on demand based on the declaration kind:

```zena
resolveTypeName(name: String): Type | null {
  // 1. Scope lookup → get Symbol
  let si = this.scopeResult.resolveType(name);
  if (si == null) { return null; }

  // 2. Already materialized?
  let existing = this.getTypeForSymbol(si);
  if (existing != null) { return existing; }

  // 3. Materialize on demand from declaration kind
  let t = this.materializeType(si);
  this.setTypeForSymbol(si, t);
  return t;
}

let materializeType = (si: Symbol): Type => match (si.declaration) {
  case ClassDeclaration as cd: {
    let ct = new ClassType(freshTypeId(), cd.name.name);
    // Set ALL boolean flags immediately from the AST node
    ct.isFinal = cd.isFinal;
    ct.isAbstract = cd.isAbstract || cd.isSealed;
    ct.isSealed = cd.isSealed;
    ct.isCaseClass = cd.params != null && !cd.isSealed;
    ct.isExtension = cd.isExtension;
    ct
  }
  case InterfaceDeclaration as id:
    new InterfaceType(freshTypeId(), id.name.name)
  case MixinDeclaration as md:
    new MixinType(md.name.name)
  case SealedVariant as sv: {
    let ct = new ClassType(freshTypeId(), sv.name.name);
    ct.isCaseClass = true;
    ct.isFinal = true;
    ct
  }
  case EnumDeclaration as ed:
    new TypeAliasType(ed.name.name, null, new I32Type(), true)
  case TypeAliasDeclaration as td:
    // Resolve target annotation (may recurse — cycle detection catches loops)
    resolveTypeAnnotation(td.typeAnnotation)
  case ImportSpecifier as is:
    // Query the imported file's semantic model
    resolveImportedType(is)
  case null:
    // Built-in / prelude: query prelude's semantic model (same as imports)
    resolvePreludeType(si)
}
```

At materialization time, all boolean flags (isFinal, isSealed, isAbstract,
isCaseClass, isExtension) are set directly from the AST node. The type identity
is established and registered before any further work is done.

#### Two-Phase Checking Strategy

Type discovery and checking officially operates in two cleanly separated phases:

**Phase 1: Signature Registration**
The checker iterates over the entire module AST. When it hits declarations
(Classes, Interfaces, Mixins, Type Aliases), it registers their _shapes_. For
classes, it registers the superclass, applies mixins, and populates the `fields`
and `methods` maps with their type signatures. It _does not_ check method bodies
or field initializers.

**Phase 2: Body Checking**
The checker iterates over the AST again. This time it walks inside the bodies of
functions, method implementations, getters/setters, and field initializers to
type-check the actual statements and expressions. It also validates interface
conformance here (since all signatures are now fully known).

**Why?** This guarantees that a method body in Class A can reference a field or
method in Class B, even if Class B is declared at the bottom of the file. It
fully resolves the "cross-class forward reference" problem without requiring
developers to order their classes topologically.

#### Cycle Detection

A `#pendingTypes: Set<Symbol>` tracks types currently being materialized.
If `resolveTypeName` encounters a name already in the pending set, that's a
circular type reference. For most declaration kinds, cycles through type
annotations are errors. But note that _structural_ cycles (class A has a
field of type B, class B has a field of type A) are fine — `resolveTypeName`
only creates the type identity, and field types are resolved later during
the main pass when both types already exist.

#### Cross-File Resolution

Files are checked in dependency order. When the checker encounters an
`ImportSpecifier`, it queries the imported file's already-checked
`SemanticModel` for the resolved type — using exactly the same mechanism
as prelude types (which are just implicit imports).

For libraries with circular dependencies between files, a library has
three states:

- **not-checked** — library hasn't started checking
- **in-progress** — types exist as identity-only stubs (flags set, structural
  members not yet populated)
- **checked** — all types fully resolved

When file A (in an in-progress library) imports `Foo` from file B (same
library), it gets back the identity-only `ClassType` for `Foo`. This is
sufficient for type annotations, since annotations only need identity, not
members. The members of `Foo` are populated when B finishes its main pass.

#### What This Eliminates

- **Pass 1** (class/interface name pre-registration) — names come from scope
  analysis
- **Pass 1.5** (sealed variant pre-declaration) — sealed variants are just
  another declaration kind in scope analysis
- **`pass1TypeNames`** — no need to distinguish placeholder vs real types
- **`resolveLocalTypeName`** — no prelude fallback to work around, because
  prelude types are in scope analysis like everything else
- **`#preludeTypes` HashMap** — prelude is part of the scope chain
- **Prelude shadowing bugs** — a local `Box` class shadows the prelude `Box`
  naturally because it's in a nearer scope

#### Parallelism

The checker is parallelizable across the module dependency DAG: if modules B
and C both depend only on A, then once A is checked, B and C can be checked
in parallel. The practical parallelism depends on how "wide" the dependency
graph is.

The checker's job ends here. It produces a complete `SemanticModel` with
resolved types, bindings, class hierarchies, and diagnostics. Everything
that follows operates on the `SemanticModel` without producing type errors.

Whole-program concerns like reachability (DCE), devirtualization, and
effectively-final analysis are _not_ part of checking — they're analysis
passes that run after all modules are checked. See section 6 below.

### 5. Visitor Infrastructure

**Currently (TS):** One AST visitor (`visitor.ts`) with a ~60-method optional
interface, a `NodeType` enum for dispatch, and a 500-line `switch` that casts
to each concrete type. A `default: break` silently swallows new node types.

**Self-hosted design:** The Zena AST is a sealed hierarchy with nested
sub-hierarchies (`Node → Expression → BinaryExpression`). This means `match`
expressions **are** the visitor dispatch — the compiler generates discriminant
tags, exhaustive checking, and safe casts. We don't need to port the TypeScript
`Visitor<T>` interface; it was a workaround for TypeScript's lack of sum types.

#### What we provide: `walk` + `walkChildren`

A thin utility module (`visitor.zena`) provides automatic tree traversal:

```zena
// Walk a node tree: enter is called pre-order, leave is called post-order.
// Return false from enter to skip children.
export let walk = (node: Node, enter: (Node) => boolean, leave: (Node) => void) => {
  if (!enter(node)) { return; }
  walkChildren(node, enter, leave);
  leave(node);
}

// Walk children only — for when you want to handle the root specially.
export let walkChildren = (node: Node, enter: (Node) => boolean, leave: (Node) => void) => {
  match (node) {
    // === Module ===
    case Module(body, _, _, _):
      for (let stmt in body) { walk(stmt, enter, leave); }

    // === Expressions ===
    case BinaryExpression(_, left, right, _): {
      walk(left, enter, leave);
      walk(right, enter, leave);
    }
    case UnaryExpression(_, argument, _, _):
      walk(argument, enter, leave);
    case CallExpression(callee, args, typeArgs, _, _): {
      walk(callee, enter, leave);
      for (let arg in args) { walk(arg, enter, leave); }
      if (let ta = typeArgs) { for (let t in ta) { walk(t, enter, leave); } }
    }
    case FunctionExpression(typeParams, params, returnType, body, _): {
      if (let tp = typeParams) { for (let t in tp) { walk(t, enter, leave); } }
      for (let p in params) { walk(p, enter, leave); }
      if (let rt = returnType) { walk(rt, enter, leave); }
      walk(body, enter, leave);
    }
    // ... every other Node variant — exhaustive
    case Identifier(_, _): {}        // leaf
    case NumberLiteral(_, _): {}     // leaf
    case BooleanLiteral(_, _): {}    // leaf
    case NullLiteral(_): {}          // leaf
    // ...
  }
}

// Convenience: walk with enter only (no leave callback).
export let walkEnter = (node: Node, fn: (Node) => void) => {
  walk(node, (n) => { fn(n); return true; }, (n) => {});
}
```

#### Why this is better than the TypeScript visitor

| TypeScript Visitor                     | Zena `match` + `walk`                  |
| -------------------------------------- | -------------------------------------- |
| ~60 optional interface methods         | Zero — callers use closures + `match`  |
| `NodeType` enum (manual discriminant)  | Sealed class **is** the discriminant   |
| 500-line `switch` with casts           | Exhaustive `match` with destructuring  |
| `visitor.visitFoo?.(node)` null checks | Pattern match — zero overhead          |
| Silent `default: break` on new nodes   | **Compile error** on unhandled variant |
| `visitChildren` reflection fallback    | Explicit children in `walkChildren`    |

The key advantage is **exhaustiveness**: when a new AST node is added, every
`match` on `Node` in the codebase produces a compile error until updated. The
TypeScript visitor silently ignores new node types via `default: break`, which
has been a recurring source of bugs.

#### Pattern 1: Simple collection (enter-only)

For simple analyses that collect information in a single pass:

```zena
// Collect all identifiers in an AST
let identifiers: Array<String> = [];
walkEnter(ast, (node) => {
  match (node) {
    case Identifier(name, _): identifiers.push(name)
    case _: {}
  }
});
```

#### Pattern 2: Scoped analysis (enter + leave)

For analyses that need scope tracking or depth:

```zena
// Capture analysis: track variables referenced inside closures
var insideClosure = false;
let captured: Array<String> = [];

walk(ast, (node) => {
  match (node) {
    case FunctionExpression(_, _, _, _, _): {
      insideClosure = true;
    }
    case Identifier(name, _): {
      if (insideClosure) { captured.push(name); }
    }
    case _: {}
  }
  return true;
}, (node) => {
  match (node) {
    case FunctionExpression(_, _, _, _, _): {
      insideClosure = false;
    }
    case _: {}
  }
});
```

#### Pattern 3: Skipping subtrees

Return `false` from `enter` to skip a node's children:

```zena
// Visit top-level declarations only, don't recurse into bodies
walk(ast, (node) => {
  match (node) {
    case Module(_, _, _, _): return true  // recurse into module body
    case ClassDeclaration(name, _, _, _, _, _, _, _, _, _, _, _, _, _, _): {
      registerClass(name);
      return false;  // don't recurse into class body
    }
    case _: return false  // skip everything else
  }
}, (n) => {});
```

#### Pattern 4: Full control (direct `match`, no walker)

Passes that need full control over recursion order — like the formatter and
codegen — don't use `walk` at all. They write recursive functions with `match`:

```zena
// Formatter: convert AST to Doc IR
let printNode = (node: Node): Doc => match (node) {
  case BinaryExpression(op, left, right, _):
    group(concat(printNode(left), text(" ${op} "), printNode(right)))
  case Identifier(name, _):
    text(name)
  case CallExpression(callee, args, _, _, _):
    group(concat(
      printNode(callee),
      text("("),
      indent(join(text(", "), args.map(printNode))),
      text(")")
    ))
  // ... exhaustive — compiler enforces all cases
}
```

This is the primary pattern for the formatter: each node type maps to a `Doc`
structure, with recursive calls to `printNode` for children. No walker needed.

#### Pattern 5: Sub-hierarchy matching

The nested sealed hierarchy (`Node → Expression`, `Node → Statement`) enables
matching at any granularity:

```zena
// Route to sub-handlers by hierarchy level
let processNode = (node: Node) => match (node) {
  case Expression: handleExpr(node)
  case Statement: handleStmt(node)
  case Pattern: handlePattern(node)
  case TypeAnnotation: handleType(node)
  case _: {}  // other direct Node variants
}

// Sub-handler gets exhaustive matching on Expression variants
let handleExpr = (expr: Expression) => match (expr) {
  case BinaryExpression(op, left, right, _): ...
  case Identifier(name, _): ...
  // exhaustive within Expression's variants
}
```

#### Type Visitor (future)

The AST walker covers Milestone 1 (formatter) and the early checker milestones.
When we build the type checker, we'll also need a **type visitor** for
traversing the `Type` graph (not the AST). This is useful for:

- Type substitution (`substituteTypeParams`)
- Type key computation (`computeTypeKey`)
- Type printing
- Finding all type parameters referenced in a type

Since `Type` will also be a sealed hierarchy (`ClassType`, `FunctionType`,
`UnionType`, `TypeParameterType`, ...), the same pattern applies: a
`walkType` function with an exhaustive `match` over `Type` variants. We'll
add this when the checker is built — it depends on the `Type` hierarchy
design.

### 6. Analysis Passes: Between Checking and Codegen

After the checker produces a complete `SemanticModel`, a series of analysis
passes prepare information that codegen needs. These are visitor-based passes
that read the AST + SemanticModel and produce `AnalysisResults`.

Some are whole-program (need all modules), some are per-function:

**Whole-program passes (sequential):**

- **Dead code elimination** — Mark reachable declarations from the entry point
- **Effectively-final analysis** — Methods never overridden can be devirtualized
- **Devirtualization** — Replace virtual dispatch with static calls where safe
- **Generic specialization** — Decide which concrete instantiations to emit
- **Cross-module exhaustiveness** — For sealed hierarchies (future)

**Per-function passes (parallelizable):**

- **Capture analysis** — Which variables each closure captures
- **Mutability analysis** — Which captured variables need cells (mutable boxes)
- **Adaptation analysis** — Which values need fat-pointer packing for interface/function dispatch
- **Escape analysis** (future) — Which allocations can be stack-allocated

The key design point: these passes don't produce type errors. The
`SemanticModel` is complete and correct. Analysis passes add optimization and
codegen-preparation information on top.

### 7. IR: Not Yet, But Structured For It

**Question:** Should we introduce an intermediate representation between the
AST and WASM codegen?

**Decision:** Not in the initial port. But structure the code so an IR can be
inserted later.

**Reasoning:**

- An IR adds significant complexity and we don't have optimization passes that
  need one yet.
- The current AST-to-WASM translation works.
- WASM itself is somewhat of an IR — it has structured control flow and a type
  system.
- The main benefit of an IR would be optimization passes (constant folding,
  inlining, escape analysis). We can add these later.

**Preparation:** Keep codegen cleanly separated from checking. The checker
produces a `SemanticModel` that is backend-agnostic. Codegen consumes the AST +
SemanticModel. If we later insert an IR, it goes between:

```
AST + SemanticModel → IR → Optimizations → WASM
```

The only code that changes is the AST→IR lowering and IR→WASM emission.
Everything before (parsing, checking) is untouched.

### 8. Formatter and LSP as Early Deliverables

> **Status (2026-08): done, not planned.** Both shipped and are self-hosted.
> `packages/zena-formatter/zena/` is the formatter; and
> `packages/language-service/zena/lsp.zena` is the language server, written in
> Zena against `zena-compiler`, `zena-formatter` and the stdlib — see
> [lsp.md](lsp.md). The TypeScript in `packages/language-service` is a JS shim
> exposing a JS API to the VS Code extension; it depends on
> `@zena-lang/runtime`, not on the bootstrap compiler. The section below is
> retained for its rationale. See
> [bootstrap-retirement.md](bootstrap-retirement.md) §1 — neither is a blocker
> for retiring the bootstrap compiler.

A compiler that only emits WASM is useful but narrow. We can deliver value
sooner by building tools that don't require codegen:

- **Formatter:** Only needs the parser. Useful immediately.
- **LSP basics:** Needs parser + checker. Provides hover types, go-to-definition,
  error diagnostics, completion — even before codegen works.
- **Linter:** Needs parser + visitors. Add rules incrementally.

These also serve as excellent tests of the parser and checker in isolation.

### 9. Program, SourceFileCache, and LanguageService

**Problem:** The current architecture creates a fresh `Compiler` + `LibraryLoader`
on every `check()` call. Every keystroke re-reads, re-parses, and re-checks the
entry file and all its transitive dependencies — including the entire stdlib. This
is wasteful. The stdlib doesn't change between keystrokes, and neither do most
dependencies.

**Current state (what we do today):**

The `LibraryLoader` conflates two responsibilities:

1. **Loading** — reading files via `CompilerHost`, parsing, resolving imports
   (stateless operation)
2. **Caching** — the `#cache: HashMap<String, SourceFile>` that accumulates
   the module graph (stateful)

The `CompilationResult` is a snapshot of a single compilation — `files` in
topological order, the `entry` module, and a `hasCycle` flag.
`checkCompilation` type-checks all non-stdlib modules in dependency order,
using per-module `depExports` and `depModels` maps wired from dependency
`ScopeResult`s and `CheckResult`s. Each module gets its own `SemanticModel`.

**What's already been implemented (incremental checking foundation):**

- **Persistent `Compiler` + `LibraryLoader`** in `lsp.zena` — no longer
  recreated per `check()` call. The loader cache survives across edits.
- **`ScopeResult` caching** — unchanged files reuse their scope analysis
  from the loader cache. Scope analysis is file-local (depends only on
  source text), so this is always safe.
- **Export signature comparison** — `computeExportSignature()` maps each
  module's exported names (prefixed `v:` / `t:`) to their resolved `Type`.
  `signatureTypeEquals()` does deep structural comparison (with cycle guard)
  to detect when a module's public API actually changed.
- **Per-import-name invalidation** — `buildReverseDeps()` tracks which
  specific names each importer uses. When a dependency's signature changes,
  only importers that reference affected names are re-checked.
- **Push/pull invalidation split** — `Compiler.invalidate(path)` for
  targeted IDE updates (evicts one file, clears importers' `scopeResult`,
  re-loads); `Compiler.refreshCache()` for batch/CLI (re-reads all cached
  non-stdlib files, compares source text, evicts changed files).
- **`ProgramCheckResult` carry-forward** — `checkCompilation()` accepts an
  optional `previous: ProgramCheckResult` and carries forward `CheckResult`s
  for files whose source is unchanged and whose imports are unaffected.
- **Language service wired to push-based invalidation** — `lsp.zena`'s
  `check()` calls `compiler.invalidate(path)` then `compiler.compile(path)`.
  No version bumping needed.

**Design:** Three new abstractions that separate concerns cleanly:

1. **`SourceFileCache`** — Long-lived, mutable cache of parsed source files.
   Shared across `Program` snapshots.
2. **`Program`** — Immutable snapshot of the compilation state at a point in
   time. Contains references to `SourceFile`s and lazily-computed check results.
3. **`LanguageService`** — The stateful orchestrator that the WASM exports talk
   to. Manages open files, creates new `Program` snapshots on edits, and
   delegates queries.

#### SourceFileCache

The `SourceFileCache` stores `(path, version) → SourceFile`. It sits outside
`Program` and survives across Program snapshots. This is the primary mechanism
for avoiding re-parsing.

```zena
class SourceFileCache {
  #entries: HashMap<String, CacheEntry>

  // Returns cached SourceFile if version matches, else re-reads + re-parses.
  getOrLoad(path: String, version: i32, host: CompilerHost, resolver: ModuleResolver): SourceFile

  // For files from the editor — source text is already available.
  getOrParse(path: String, version: i32, source: String): SourceFile

  // Evict an entry (e.g., when a file is removed from the project).
  evict(path: String): void

  // Eviction policy: drop entries not referenced by any recent Program.
  // Called after creating a new Program — entries not in the new Program's
  // file set can be evicted (unless they're stdlib, which we always keep).
  retainOnly(paths: HashMap<String, i32>): void
}

class CacheEntry {
  version: i32;
  sourceFile: SourceFile;
  // Scope result depends only on the AST, so it's cached here too.
  scopeResult: ScopeResult | null;
}
```

**Key insight**: Scope analysis (`ScopeBuilder.build`) depends _only_ on the
AST, not on other modules. So `ScopeResult` can be cached alongside the
`SourceFile` in the cache. Import wiring is a separate cross-module step that
happens at the `Program` level.

**Eviction policy**: After each edit cycle, the `LanguageService` calls
`retainOnly()` with the set of paths in the current `Program`. Files not in
that set are evicted — unless they're stdlib (which we always keep). This
handles the case where a user removes an import: the orphaned dependency gets
evicted on the next cycle. We don't evict eagerly because a file might be
re-imported quickly (undo, or editing an import statement).

#### Program: Immutable Compilation Snapshot

A `Program` is an immutable snapshot of the compilation state. When files
change, we create a _new_ `Program` rather than mutating the existing one.
This is analogous to TypeScript's `Program` type.

```zena
class Program {
  files: HashMap<String, SourceFile>        // all loaded files
  fileVersions: HashMap<String, i32>        // path → version at snapshot time
  graph: Array<SourceFile>                  // topological order
  options: CompilerOptions
  #cache: SourceFileCache                   // shared, long-lived

  // Lazily computed, but immutable within this snapshot.
  #scopeResults: HashMap<String, ScopeResult>
  #checkResults: HashMap<String, CheckResult>

  // Carried forward from the previous Program for unchanged files.
  #inheritedCheckResults: HashMap<String, CheckResult>

  // Lazy queries — compute on first access, cache for this snapshot.
  getScopeResult(path: String): ScopeResult
  getCheckResult(path: String): CheckResult
  getDiagnostics(path: String): Array<Diagnostic>
  getSemanticModel(path: String): SemanticModel
  getDefinition(path: String, offset: i32): SourceSpan | null
}
```

**Why immutable snapshots?**

- Clean semantics — a query always sees a consistent snapshot.
- No issue with interleaved queries (definition lookup mid-check).
- The old `Program` can be referenced while a new one is being constructed.
- When we add async checking or workers, immutability pays off.

**Why this isn't expensive**: Creating a new `Program` is cheap because:

- `SourceFile`s are shared via `SourceFileCache` (just HashMap inserts, not copies).
- `ScopeResult`s for unchanged files are in the cache already.
- `CheckResult`s for unchanged files (with unchanged deps) can be _carried
  forward_ from the old Program.
- Only the changed file(s) and their transitive dependents need recomputation.

#### Sharing CheckResults Across Programs

The key optimization for high-frequency edits: **unaffected subgraphs carry
forward**. When creating a new `Program`, we inherit `CheckResult`s from the
old `Program` for files that haven't changed and whose dependencies haven't
changed.

```zena
// Creating a new Program from an old one + file changes.
let createProgram = (
  oldProgram: Program | null,
  cache: SourceFileCache,
  openFiles: HashMap<String, FileState>,
  host: CompilerHost,
  options: CompilerOptions
): Program => {
  let newProgram = new Program(cache, options);

  // 1. Load all open files and their transitive deps into the new Program.
  //    SourceFileCache handles the version check — unchanged files are free.
  for (let (path, state) in openFiles) {
    newProgram.addRoot(path, state.source, state.version);
  }

  // 2. For each file in the new Program, check if we can inherit results.
  if (oldProgram != null) {
    for (let (path, _) in newProgram.files) {
      let oldVersion = oldProgram.fileVersions.get(path);
      let newVersion = newProgram.fileVersions.get(path);
      if (oldVersion == newVersion && !depsChanged(path, oldProgram, newProgram)) {
        // File and all its deps unchanged — inherit CheckResult.
        let oldResult = oldProgram.#checkResults.get(path);
        if (oldResult != null) {
          newProgram.#inheritedCheckResults.set(path, oldResult);
        }
      }
    }
  }

  return newProgram;
};
```

The `depsChanged` check walks the file's transitive imports and compares
versions between the old and new Programs. If _any_ dependency's version
changed, we can't inherit the `CheckResult` (because its types might be
different).

#### Granular Invalidation: Function-Body Edits

The most common editing scenario is typing inside a function body. In this
case, the file's _exports_ (function signatures, class declarations, type
aliases) haven't changed — only the internal implementation. This means:

1. **This file's ScopeResult changes** (new AST), but its exports may be identical.
2. **Dependents' CheckResults are still valid** if the exports didn't change.

To support this, we can add **export signature comparison**:

```zena
// Compare two ScopeResults to see if the module's public API changed.
let exportsChanged = (oldScope: ScopeResult, newScope: ScopeResult): boolean => {
  // Compare exported value names + their declaration shapes
  // Compare exported type names + their declaration shapes
  // If identical, dependents don't need re-checking.
}
```

With export signature comparison, editing inside a function body in file A
only triggers:

- Re-parse A (version changed)
- Re-scope A (new AST)
- Compare A's old vs new exports → identical
- Re-check A (its body changed)
- Dependents of A: **skip** (their dep's exports unchanged)

This is the key to making high-frequency typing fast. The stdlib (20+ files)
never needs re-checking during normal editing. Even editing file A doesn't
force re-checking of B/C/D that import from A, as long as A's exports are
stable.

**Future: intra-file granularity.** The ultimate optimization is to re-check
_only the changed function_ within a file, reusing the rest of the file's
`CheckResult`. This requires:

- Tracking which AST nodes each `CheckResult` entry depends on.
- A way to "splice" new check results for one function into an existing
  per-file result.
- Careful handling of top-level declarations that affect the whole file
  (like type aliases or class fields).

This is complex and not needed initially, but the immutable-snapshot
architecture doesn't preclude it. The path is: `Program.getCheckResult(path)`
checks whether only function bodies changed, and if so, re-checks only those
functions while reusing the rest.

#### On-Demand Checking

Type checking is the most expensive step, so we defer it until a query needs
it. The pipeline becomes:

| Step               | When                                                   | Depends on                            |
| ------------------ | ------------------------------------------------------ | ------------------------------------- |
| **Parse**          | File loaded/changed                                    | Source text only                      |
| **Scope analysis** | File loaded/changed                                    | AST only (file-local)                 |
| **Import wiring**  | Program created                                        | File's ScopeResult + dep ScopeResults |
| **Type checking**  | **On demand** — when diagnostics/types/hover requested | AST + wired ScopeResult + dep exports |

When the user opens files A and B but only has A focused:

- Parse + scope-analyze both A and B (and their transitive deps) — cheap.
- Type-check only A (since that's what the editor shows diagnostics for).
- If the user switches to B, type-check B then (likely instant — deps already
  cached/checked).

The trigger for type-checking is the JS side calling `getDiagnostics(path)`.
VS Code does this automatically for visible editors.

#### LanguageService: The Stateful Orchestrator

This replaces the current module-level globals in `lsp.zena`:

```zena
class LanguageService {
  #cache: SourceFileCache
  #host: CompilerHost
  #options: CompilerOptions
  #resolver: ModuleResolver
  #currentProgram: Program | null
  #openFiles: HashMap<String, FileState>  // path → {source, version}

  // Called when a file is opened/changed in the editor.
  // Creates a new Program snapshot.
  updateFile(path: String, source: String, version: i32): void

  // Called when a file is closed.
  closeFile(path: String): void

  // Queries — delegate to currentProgram.
  getDiagnostics(path: String): Array<Diagnostic>
  getDefinition(path: String, offset: i32): SourceSpan | null
  getType(path: String, offset: i32): Type | null
}

class FileState {
  source: String;
  version: i32;
}
```

#### Project Concept: Implicit, Derived from Open Files

We don't need an explicit project definition yet. The "project" is:

- **Root files**: All files currently open in the editor.
- **Discovered files**: Transitively imported by root files.
- **Stdlib**: Always loaded (version 0, never changes).

The `LanguageService` maintains the set of open files. When creating a new
`Program`, the root files are the union of all open files. The module resolver

- loader discovers the rest.

Later, `zena-packages.json` can define explicit root files, include/exclude
patterns, and become the project definition. But for now, the implicit
approach works — TypeScript works the same way with the IDE only activating
when a `.ts` file is opened.

#### Key Design Points

- **Stdlib is not special.** It uses the same versioning and caching as any
  other dependency. The stdlib happens to never change during a session, so its
  version stays at 0 and its cached results are always reused. But the mechanism
  is the same — if you're editing the stdlib itself, it invalidates normally.

- **Version numbers come from the host.** The LSP protocol provides
  `TextDocument.version` (an integer that increments on every edit). The JS
  glue layer tracks these and passes them to the WASM side. For files read
  from disk (not open in the editor), the version can be a hash or timestamp.

- **Parse and scope analysis are per-file, cached by version.** Parsing depends
  only on the source text. Scope analysis depends only on the AST. Neither
  depends on other modules. So these can be cached purely by `(path, version)`
  with no dependency tracking.

- **CheckResults depend on imports.** `checkModule(ast, scopeResult, depExports)`
  takes dependency exports as input. If any dependency's exports change, the
  result is stale. In practice we detect this by comparing versions transitively
  when creating a new `Program`, and only inherit results for unchanged subgraphs.

#### What Changes from Current Code

| Before incremental work                             | Current state (implemented)                                               | Future (Program + LanguageService)                                |
| --------------------------------------------------- | ------------------------------------------------------------------------- | ----------------------------------------------------------------- |
| `lsp.zena` creates a fresh `Compiler` per `check()` | Persistent `Compiler`; `invalidate(path)` before `compile()`              | `LanguageService` holds `SourceFileCache` + immutable `Program`   |
| `LibraryLoader` owns the cache + loading logic      | Same, but with `invalidate()` (push) and `refreshCache()` (pull)          | `SourceFileCache` owns parsed files; `LibraryLoader` is stateless |
| Stdlib is re-parsed on every call                   | Stdlib parsed once, cached in `LibraryLoader` forever                     | Same, in `SourceFileCache`                                        |
| Only `ScopeResult` is cached for queries            | `ScopeResult` + `CheckResult` cached; carry-forward in `checkCompilation` | Lazy checking per file per `Program`                              |
| No incremental invalidation                         | Export signature comparison + per-import-name invalidation                | On-demand checking + intra-file granularity                       |
| Only one file can be "active" at a time             | Same (single entry point per compile)                                     | All open files tracked; each can be queried independently         |

#### Incremental Workflow

```
1. User opens foo.zena
   → LanguageService.updateFile("foo.zena", source, version=1)
   → New Program created: parse foo.zena, load deps (stdlib cached)
   → JS calls getDiagnostics("foo.zena") → lazy check → cache result
   → Return diagnostics

2. User types in foo.zena (adds a line inside a function body)
   → LanguageService.updateFile("foo.zena", source, version=2)
   → New Program created from old + changes:
     - Re-parse foo.zena (version changed), scope-analyze
     - Compare foo.zena's old vs new exports → identical
     - Dependencies unchanged → carry forward their CheckResults
   → JS calls getDiagnostics("foo.zena") → re-check foo.zena only
   → Return diagnostics

3. User opens bar.zena (imports foo.zena)
   → LanguageService.updateFile("bar.zena", source, version=1)
   → New Program: foo.zena cached at version=2, bar.zena is new
   → JS calls getDiagnostics for both open files
   → foo.zena: inherited from previous Program (unchanged)
   → bar.zena: checked using foo.zena's cached exports
   → Return diagnostics

4. User edits foo.zena's exported function signature
   → New Program: re-parse foo.zena, exports changed
   → foo.zena: re-check (exports changed)
   → bar.zena: CheckResult NOT inherited (dep exports changed), re-check
   → Return diagnostics
```

#### Implementation Plan

1. ~~**Near term:** Make the `Compiler` and `LibraryLoader` persistent in
   `lsp.zena` (don't recreate them per call). Add version tracking on the
   JS side to skip `check()` when the document hasn't changed.~~ ✅ Done.
   Persistent compiler with push-based `invalidate(path)` in language service.

2. ~~**Medium term (partial):** Export signature comparison for function-body
   edits. `CheckResult` carry-forward for unchanged subgraphs.~~ ✅ Done.
   `checkCompilation()` with `ProgramCheckResult` carry-forward, export
   signature comparison via `signatureTypeEquals()`, per-import-name
   invalidation via `buildReverseDeps()`.

3. **Medium term (remaining):** Extract `SourceFileCache` from `LibraryLoader`.
   Implement immutable `Program` snapshots created per edit cycle. This would
   enable clean multi-file queries and concurrent read access.

4. **Long term:** `LanguageService` as the full orchestrator. On-demand
   checking (only check files the editor asks about). Intra-file granularity
   (re-check only changed functions). Cache eviction for files no longer in
   the module graph. Content-hashed result caching for undo optimization
   (state 1→2→1 gets instant cache hit).

---

## Milestone Plan

### Milestone 0: Parser ✅ Complete

**Status:** Complete. Tokenizer, parser, and AST produce correct output for all
Zena syntax. 389 portable syntax tests pass on both the bootstrap (TS) and
self-hosted (Zena) parsers.

**What was built:**

- `tokenizer.zena` — Full lexer with 50+ token types, string/template literal
  handling, comment support, source position tracking (28 tests)
- `parser.zena` — Complete recursive descent parser (~2000 lines) covering all
  expressions, statements, patterns, type annotations, classes, interfaces,
  mixins, enums, decorators, and import/export syntax (11+ unit tests + 389
  portable snapshot tests)
- `ast.zena` — Sealed AST node hierarchy: Module, Expression (30+ variants),
  Statement (20+ variants), Pattern, TypeAnnotation, with case classes for each
  concrete node type (~600 lines)
- `ast-json.zena` — AST→JSON serialization for debugging and portable test
  comparison (6 tests)

**Deliverable:** `parse(source: String, path: String): Module` ✅

### Milestone 1: Formatter ← In Progress

**Status:** Implemented (`packages/zena-formatter`: Wadler-style doc/
doc-printer/printer over the shared parser) but not yet battle-tested —
it has not been run across the compiler's own source, and test coverage
is thin. Hardening it and self-formatting the codebase are the open
work.

**Depends on:** Milestone 0 (parser) ✅

**Scope:** A code formatter that parses Zena source and re-emits it with
consistent style. This is:

- A great test of the parser (every valid program must round-trip)
- Immediately useful for the project itself
- Low risk (no type system complexity)

**Key decisions:**

- Print from AST, preserving comments (need to attach comments to AST nodes
  during parsing — either as node properties or in a side table)
- Configurable style (indent width, quote style) via a config record

**Deliverable:** `format(source: String): String`

### Milestone 2: Name Resolution & Module System ✅ Complete

**Depends on:** Milestone 0 ✅

**What was built:**

- `module-resolver.zena` — Import resolution supporting stdlib (`zena:*`),
  user packages, relative paths, target-conditional modules (`*.host.zena`,
  `*.wasi.zena`), and internal modules (~700 lines, 30 tests)
- `package-manifest.zena` — `zena-packages.json` parsing for package config
  with shorthand and full-form syntax, stdlib config builder (9 tests)
- `library-loader.zena` — Source loading, parsing, caching, dependency
  resolution via `CompilerHost` interface. Handles circular imports via
  cache-before-resolve. `SourceFile` tracks path, source, AST, resolved
  import mappings, and scope results
- `scope.zena` — Two-namespace (value + type) lexical scoping with Module,
  Function, Block, and Class scope kinds. Tracks symbol info (let/var/type,
  declaration node), module exports, reference tracking, unresolved name
  detection, and pre-declaration for hoisted classes/functions (~800 lines,
  39 tests)
- `visitor.zena` — Generic `walk()` / `walkEnter()` / `walkChildren()` tree
  traversal using exhaustive `match` (all AST node types covered, 12 tests)
- `compiler.zena` — Main orchestrator wiring the pipeline: module resolution →
  source loading/parsing → dependency graph (topological sort) → scope analysis
  → cross-module import wiring with `ExportFromDeclaration` re-export support.
  `createCompiler()` factory for clean construction (9 integration tests)

**Data structures built:**

```zena
// Scope hierarchy
class Scope { parent, bindings: HashMap<String, Symbol>, kind: ScopeKind }
class Symbol { name, kind: SymbolKind, declaration: Node }
class ModuleExports { #values, #types: HashMap<String, Symbol> }

// Module resolution
class ModuleResolver { resolve(specifier, referrer): ResolvedModule }
class SourceFile { path, source, ast, imports, scopeResult }
class LibraryLoader { load(path), computeGraph(entry): SourceFileGraph }
```

**Deliverable:** `compiler.compile(entryPoint): CompilationResult` with all
modules in dependency order, scopes built, imports validated ✅

### Milestone 3: Type Checker (Core) ✅ Complete

**Status:** Complete. The self-hosted checker checks the whole compiler
and the portable semantics suite; remaining bootstrap/self-hosted
divergences are tracked in BUGS.md.

**Depends on:** Milestone 2 ✅

**Scope:** Type inference and validation for the core language. Port the
checking logic from the TypeScript compiler, with three key improvements:

1. **No AST mutation** — all type info stored in `SemanticModel` side tables
2. **No string-based type lookups** — use AST node references and interned types
3. **Prelude always available** — no fallbacks for missing stdlib types

**Architecture:**

The checker uses its own type scope stack (separate from `ScopeBuilder`'s
name-resolution scopes). It maps value names → `Type` objects and type
names → `Type` objects. The `SemanticModel` records per-node types by source
offset, keyed the same way as `ReferenceMap`. The AST is read-only.

**Sub-milestones:**

**3a: Type infrastructure + primitives ✅**

- `types.zena` — Sealed `Type` hierarchy with all variants
- `diagnostics.zena` — `Diagnostic`, `DiagnosticBag`, `DiagnosticCode`
- `semantic-model.zena` — `SemanticModel` (node offset → Type, ResolvedBinding)
- `checker.zena` — `CheckerContext` (type scope stack, narrowings, diagnostics)
- Resolve `NamedTypeAnnotation` → Type (i32, boolean, void, etc.)
- Resolve `UnionTypeAnnotation`, `FunctionTypeAnnotation`
- Check literal expressions (Number→i32/f32, String→String, Boolean→literal, Null→null)
- Check identifier expressions (scope lookup → return type)
- Check variable declarations (infer type, validate annotation, bind pattern)
- `var` bindings widen literal types (true → boolean)
- Check expression statements

**3b: Operators + control flow ✅**

- Binary expressions (arithmetic, comparison, logical, bitwise)
  - Contextual typing: `0 < x` where x is i64 makes 0 → i64
  - Numeric promotion: f64 > f32 > i64 > i32
- Unary expressions (-, !)
- Assignment expressions (type compatibility check)
- `if`/`while`/`for`/`for-in` statements (boolean condition validation)
- `break`/`continue` (loop depth validation)
- Block scoping (`enterScope`/`exitScope`)

**3c: Functions + calls ✅**

- Function expressions → `FunctionType`
- Contextual typing for closures (infer param types from expected type)
- Call expressions (check callee, arg count, arg types, return type)
- Return statements (validate against expected return type)
- If expressions (union of branch types)

**3d: Classes and interfaces ✅**

- Class type creation from `ClassDeclaration`
- Case class constructors
- Field types and member resolution
- `new` expressions
- Member expressions (field access, method access)
- Interface conformance checking
- Inheritance and override validation
- Mixin application

**3e: Generics ✅**

- Type parameter resolution and constraint checking
- Generic instantiation with interning
- Type argument inference (simple: `TypeParameterType` → arg type)
- `substituteTypeParams` via `TypeContext`

**3f: Declarations ✅**

- Enum declarations (distinct TypeAliasType + record value binding)
- Mixin declarations (type params, on clause, composed mixins, fields/methods)
- Declare function (annotation-only FunctionType)
- Symbol declarations (SymbolType with unique ID)
- On-demand type materialization from scope declarations (replaces multi-pass
  pre-registration — see Section 4)

**3g: Patterns + expressions ✅**

- Pattern matching: class patterns, logical patterns, record/tuple destructuring
- `if-let` / `while-let`
- `match` expressions with exhaustiveness checking (basic)
- `as` expressions (type casts)
- `super` expressions
- `try` / `catch` expressions
- Array literals, record literals, map literals
- Template literals and tagged template expressions
- Range expressions (bounded, from, to, full)
- Pipeline expressions with `#` placeholder
- Index expressions (arrays, tuples, operator `[]`)

**3h: Remaining improvements (not yet started)**

- [x] Identity-based type deduplication in `createUnionType` (now uses
      `typeIdentityKey` with numeric IDs for named types)
- [x] Complex generic type argument inference (e.g., `Array<T>` against
      `Array<i32>` — currently only handles bare `TypeParameterType`)
- [x] Tuple literal index with specific element type (currently returns union
      of all element types when index is a literal)
- [x] Logical expression narrowing (extract narrowings from `&&` left side,
      apply to right side)
- [x] Operator overloading on non-numeric classes (checks `ClassType.methods`
      for operator methods, e.g., String.+)
- [x] Equality type validation (ensure `==`/`!=` operands are comparable)
- [x] Diagnostic for unresolved `String` type (now emits
      `SymbolNotFound` error instead of silent `UnknownType` fallback)

**Important design note:** The checker should produce information that is
backend-agnostic. It should NOT make decisions specific to WASM (like "this
needs boxing" or "this needs a vtable"). Those belong in codegen or in a
backend-agnostic analysis layer that codegen calls.

However, the checker _should_ compute things that any backend needs:

- Resolved types for every expression
- Which methods are virtual vs final
- Vtable layouts (these are semantic, not WASM-specific)
- Which variables are captured by closures
- Exhaustiveness of match expressions

Note that generic monomorphization decisions currently happen in codegen (it
instantiates concrete WASM types when it encounters `Box<i32>`). In the
self-hosted compiler, the checker should track which instantiations exist
(it already does via interning), and codegen should consume that list rather
than discovering instantiations on its own.

**Testing:** The checker is validated at two levels:

- **Portable semantics tests** (`tests/language/semantics/`) — compiler-agnostic
  `.zena` files with `// @error:` directives, run by both bootstrap and
  self-hosted compilers. A comprehensive porting plan maps ~278 tests from the
  bootstrap checker's unit tests to portable format. See
  `tests/language/semantics/PLAN.md`.
- **Checker API tests** (`packages/zena-compiler/zena/test/checker_test.zena`) —
  self-hosted unit tests that exercise the `checkModule()` API, `SemanticModel`
  queries, and `Diagnostic` output directly.

**Deliverable:** `check(modules: Array<Module>): SemanticModel`

### Milestone 4: LSP Foundation ← In Progress

**Depends on:** Milestone 3 (at least 3a-3b)

**Scope:** IDE features for Zena via VS Code extension, backed by the
self-hosted compiler running as WASM. See `docs/design/lsp.md` for full
details.

**Completed ✅:**

- Extension infrastructure (CJS entry, WASM loading, string marshaling)
- `lsp.zena` WASM entry point with `init()`, `check()`, `format()`,
  `getDefinition()` exports
- Diagnostics (parse errors, type errors, unresolved names)
- Go to definition (within-file, cross-module, class fields/methods,
  case class params, inherited members, `this.member` access)
- Document formatting via zena-formatter
- Integration test suite
- Persistent `Compiler` + `LibraryLoader` in language service (no longer
  recreated per call)
- Push-based invalidation (`compiler.invalidate(path)`) wired into
  `lsp.zena` for efficient single-file updates
- Incremental type checking via `checkCompilation()` with
  `ProgramCheckResult` carry-forward, export signature comparison, and
  per-import-name invalidation

**In progress:**

- **`SourceFileCache` + `Program` snapshots** — extract cache from
  `LibraryLoader`, create immutable `Program` per edit cycle (Section 9)
- **On-demand checking** — only type-check files the editor asks about
- **Hover types** — show inferred types on hover via `SemanticModel`

**Deliverable:** A working language service with diagnostics, go-to-definition,
formatting, and hover — backed by the `Program` abstraction for efficient
incremental recompilation.

### Milestone 5: Analysis Passes ✅ Complete

**Status:** Complete. The passes live in `codegen/reachability/`
(ReachabilityAnalysis: RTA liveness, generic instantiation, vtable
membership, devirtualization inputs) rather than as a separate
AnalysisResults stage; capture analysis lives with the checker.

**Depends on:** Milestone 3

**Scope:** The visitor-based analysis passes that sit between checking and
codegen. These operate on the completed `SemanticModel` and produce
`AnalysisResults` consumed by codegen.

**Whole-program passes:**

- **Dead code elimination** — Mark reachable declarations from entry points
- **Effectively-final analysis** — Methods never overridden → devirtualization
- **Devirtualization** — Replace virtual dispatch with static calls where safe
- **Generic specialization** — Decide which concrete instantiations to emit

**Per-function passes:**

- **Capture analysis** — Determine which variables each closure captures
- **Mutability analysis** — Which captured variables need cells (mutable boxes)
- **Adaptation analysis** — Which values need fat-pointer packing for interface/function dispatch
- **Escape analysis** (future) — Which allocations can be stack-allocated

Each pass is a visitor that reads the AST + SemanticModel. None produce type
errors — the SemanticModel is already complete.

**Deliverable:** `analyze(modules, semanticModel): AnalysisResults`

### Milestone 6: Code Generation ✅ Complete

**Status:** Complete — twice. The direct AST→wasm port shipped first
and was later replaced wholesale by the ZIR backend (lowering →
optimize → emit; [ir.md](./ir.md)), which is now the only backend.

**Depends on:** Milestone 3, Milestone 5

**Scope:** Port the WASM codegen from TypeScript. This is the largest single
milestone.

**Sub-milestones:**

**6a: WASM emitter**

- Binary encoding of WASM sections
- Type section, function section, export section, code section
- WASM-GC specific: struct types, array types, ref types

**6b: Basic codegen**

- Functions, parameters, locals
- Arithmetic, comparisons, control flow
- Variable declarations and assignments
- Function calls

**6c: Classes and objects**

- Struct allocation and field access
- Method dispatch (static and virtual via vtables)
- Constructors
- Interface fat pointers

**6d: Advanced features**

- Generics (monomorphization via checker types)
- Closures (context structs via capture analysis)
- Pattern matching
- Exceptions (WASM exception handling)
- String operations

**6e: Standard library integration**

- Wire up stdlib imports
- Host interop (`@external`, `@expose`)
- WASI support

**Deliverable:** `compile(modules, semanticModel, analysisResults): Uint8Array`
producing valid WASM-GC binaries.

### Milestone 7: Self-Hosting ✅ Complete

**Status:** Complete. The compiler compiles itself, and the fixpoint is
exact: stage-2 output is byte-identical to stage-1 (verified in CI-adjacent
gates on every codegen change).

**Depends on:** Milestone 6

**Scope:** The self-hosted compiler can compile itself.

- Compile the Zena compiler using the TypeScript compiler
- Run the resulting WASM compiler on its own source
- Verify the output matches (or is equivalent to) the TypeScript-compiled output

---

## Data Structure Design Details

### AST Nodes

Keep the existing class hierarchy approach (it's working well in the parser),
but ensure immutability:

```
abstract class Node {
  id: i32
  kind: NodeKind
  loc: SourceLoc
}

abstract class Expression extends Node { }
abstract class Statement extends Node { }
abstract class TypeAnnotation extends Node { }
abstract class Pattern extends Node { }

class BinaryExpression extends Expression {
  left: Expression
  op: BinaryOperator
  right: Expression
}

class ClassDeclaration extends Statement {
  name: String
  typeParameters: Array<TypeParameter>
  superClass: TypeAnnotation?
  interfaces: Array<TypeAnnotation>
  mixins: Array<TypeAnnotation>
  members: Array<ClassMember>
  // No inferredType! That goes in SemanticModel.
}
```

**Comments:** Attach comments to the nearest following AST node (leading
comments) or store them in a separate side table indexed by source position.
The formatter needs comments; the checker doesn't.

### Semantic Model

```zena
class SemanticModel {
  // Type context (interning, factory methods)
  types: TypeContext

  // Per-node semantic info
  nodeTypes: Map<i32, Type>        // expression/declaration → type
  bindings: Map<i32, Binding>      // identifier → what it resolves to

  // Per-module info
  moduleExports: Map<String, Map<String, ExportedSymbol>>

  // Global class/interface registry
  classHierarchy: ClassHierarchy

  // Diagnostics (errors, warnings)
  diagnostics: Array<Diagnostic>
}
```

### Type Context and Interning

```zena
class TypeContext {
  // All types live here; interned by structural equality
  #interned: Map<String, Type>
  #nextId: i32

  // Primitive singletons
  i32Type: NumberType
  i64Type: NumberType
  f32Type: NumberType
  f64Type: NumberType
  booleanType: BooleanType
  stringType: ClassType
  voidType: VoidType
  nullType: NullType
  neverType: NeverType

  // Create or retrieve interned types
  classType(decl: i32, name: String, ...): ClassType
  instantiate(template: ClassType, args: Array<Type>): ClassType
  union(members: Array<Type>): UnionType
  functionType(params: Array<Type>, ret: Type): FunctionType

  // Substitution (uses Type Visitor internally)
  substitute(type: Type, map: Map<TypeParameter, Type>): Type

  // Assignability
  isAssignableTo(source: Type, target: Type): boolean
}
```

### Class Hierarchy

A dedicated structure for navigating the class/interface graph:

```zena
class ClassHierarchy {
  // O(1) lookups
  superType(class: ClassType): ClassType?
  interfaces(class: ClassType): Array<InterfaceType>
  subclasses(class: ClassType): Array<ClassType>  // known direct subclasses

  // Vtable (semantic, not WASM-specific)
  vtableSlots(class: ClassType): Array<Member>
  vtableSlot(class: ClassType, method: String): i32

  // Interface conformance
  implementsInterface(class: ClassType, iface: InterfaceType): boolean
  interfaceMethodMapping(class: ClassType, iface: InterfaceType): Map<String, Member>
}
```

This consolidates vtable computation, subclass tracking, and interface
conformance into one place — rather than spreading them across ClassType,
CheckerContext, CodegenContext, and ClassInfo.

---

## What Changes From the TypeScript Compiler

### Things We Keep (port directly)

- Recursive descent parser strategy
- Token types and lexer logic
- Core type checking algorithms (assignability, inference, narrowing)
- WASM binary encoding logic (emitter)
- Expression codegen patterns (binary ops, calls, member access)
- Pattern matching compilation strategy
- Dead code elimination via reachability analysis
- Closure capture via context structs

### Things We Redesign

| Area            | Current (TS)                                 | Self-Hosted                                                        |
| --------------- | -------------------------------------------- | ------------------------------------------------------------------ |
| AST mutation    | Checker sets `inferredType` on nodes         | Checker writes to SemanticModel side table                         |
| Class members   | Spread across ClassType, ClassInfo, AST      | Single `members` map on ClassType; codegen adds indices separately |
| Type lookup     | Mix of name-based and identity-based         | Identity-only via interning                                        |
| Visitors        | 60-method optional interface + switch/cast   | Sealed `match` + thin `walk`/`walkChildren` utility                |
| Checker passes  | 5 passes over all modules together           | 2 phases: file-local, per-module (DAG); then analysis passes       |
| Generic context | `currentTypeParamMap` stack in codegen       | Type substitution via TypeContext.substitute()                     |
| Vtable layout   | Computed in both checker and codegen         | Computed once in ClassHierarchy                                    |
| Analysis passes | Ad-hoc (DCE in visitor, captures in codegen) | Structured passes between checker and codegen                      |

### Things We Defer

- IR / SSA (add only if optimization passes need it)
- Parallel compilation (design for it, don't implement it)
- Incremental recheck (design for it, implement in LSP milestone)
- Query-based architecture (a la rust-analyzer — maybe someday)

---

## Risk Assessment

### Low Risk

- **Parser port:** Nearly complete, well-tested, straightforward.
- **Formatter:** Operates only on AST, no semantic complexity.
- **WASM emitter:** Mostly mechanical binary encoding.

### Medium Risk

- **Type checker port:** Large and complex, but we have comprehensive tests.
  The main risk is subtle semantic differences between the TS and Zena
  implementations. Mitigation: run the same test suite against both.
- **Codegen port:** Large, but again well-tested. The main risk is that the
  new data structure layout requires significant re-plumbing of how codegen
  accesses type information.

### Higher Risk

- **LSP incrementality:** We haven't built this before. Start with a simple
  "recheck everything on change" and optimize later.
- **Phase 1/2 checker split:** Hard to know exactly where to draw the lines
  until we try it. Start with Phase 1 + Phase 2 combined (like the TS compiler),
  running per-module in dependency order, and refactor into separate phases
  once the basic checker works.

### Mitigations

- **Test suite is the safety net.** Every milestone must pass the existing test
  suite (adapted for the self-hosted compiler). This is non-negotiable.
- **Incremental delivery.** Each milestone is independently testable and useful.
  If we hit a wall on one milestone, the previous milestones still have value.
- **TypeScript compiler stays alive.** We don't delete the TypeScript compiler
  until the self-hosted one passes all tests and handles all features. Both
  coexist during the transition.

---

## Incremental Compilation & LSP Considerations

Even though we defer full incremental compilation, a few design choices now
will make it much easier later:

1. **Version-stamped source files.** Each `Module` AST stores the source text
   hash or version number. When re-parsing, compare versions to know if a file
   changed.

2. **Declaration signatures are the cache key.** If a module's exported type
   signatures haven't changed, its dependents don't need re-checking. This is
   how TypeScript's `--incremental` works.

3. **AST immutability enables sharing.** An unchanged module's AST can be reused
   across compilations. Since the checker doesn't mutate it, no copying needed.

4. **Diagnostics are per-module.** Store diagnostics separately per module so
   they can be invalidated and recomputed independently.

5. **File-independent checking.** The LSP should be able to check a single
   file using only the exported signatures of its imports (not their full ASTs).
   This means Phase 2 of the checker shouldn't depend on having the full AST
   of imported modules — only their semantic summaries (exported types and
   declarations).

---

## Parallelism Considerations

The architecture is designed so the following can eventually run in parallel:

| Phase                    | Parallelism                | Notes                                                               |
| ------------------------ | -------------------------- | ------------------------------------------------------------------- |
| Lexing                   | Per-file                   | Stateless, trivially parallel                                       |
| Parsing                  | Per-file                   | Stateless, trivially parallel                                       |
| Phase 1 checking         | Per-file                   | File-local scope + import/export catalog                            |
| Phase 2 checking         | Per-module (DAG)           | Parallelizable once dependencies are checked                        |
| Analysis (whole-program) | Sequential                 | DCE, devirtualization, effectively-final                            |
| Analysis (per-function)  | Per-function               | Capture analysis, boxing, mutability                                |
| Codegen                  | Per-function (potentially) | Function bodies are independent; type/struct registration is shared |

**Data structures for parallelism:**

- Node IDs (integers) instead of object references in side tables
- `SemanticModel` per module (merged in global pass)
- No mutable shared state during parallel phases

**Isolated modules (future consideration):**
TypeScript has `isolatedModules` and `isolatedDeclarations` modes that
constrain what a file can do in order to enable parallel/independent checking.
We may want something similar for large Zena codebases:

- **Declaration summaries:** After checking a module, emit a compact summary
  of its exported types (like a `.d.ts` but for Zena). Dependents can check
  against the summary without the full source or full `ModuleSemanticModel`.
  This would dramatically improve parallelism and enable caching.
- **Isolated declaration constraint:** Require that exported declarations have
  explicit type annotations (no inference leaking across module boundaries).
  This means a module's summary can be computed from Phase 1 alone, without
  waiting for Phase 2 type inference.
- **Not needed yet.** Start without this. But design the checker so that a
  module's exports are a well-defined concept (they already are), and ensure
  checking a module only needs the _exports_ of its dependencies, not their
  internals.

---

## Prelude: From Stubs to Real Stdlib

### The Problem

The self-hosted checker's `registerStandardPrelude()` is ~260 lines of
handcrafted type stubs that duplicate (a subset of) what the real stdlib
`.zena` files define. Every time a stdlib type gains a method, the stub
must be updated by hand. The stubs are always incomplete and always
drifting.

The bootstrap compiler already does this correctly: it compiles stdlib
modules through the normal pipeline and populates prelude types from
checked exports. The self-hosted compiler should do the same.

### Current State

The infrastructure is mostly in place:

- **Loading & parsing:** `compile()` already resolves prelude specifiers
  (`"zena:string"`, etc.) through `ModuleResolver`, loads and parses the
  stdlib `.zena` files via `LibraryLoader`, and includes them in the
  topo-sorted dependency graph.
- **Scope analysis:** `#resolveScopes()` runs on stdlib files. They get
  `scopeResult` populated with exports.
- **Cross-module wiring:** `checkFile()` already passes stdlib scope
  exports as `depExports` to user files.

But then two things go wrong:

1. `checkCompilation()` **skips stdlib files** with
   `if (file.isStdlib) { continue; }` — they're never type-checked.
2. `checkModule()` calls `registerStandardPrelude()`, which creates
   hardcoded stubs that shadow any real stdlib types.

### Target State

As described in §4 (Checker: On-Demand Type Resolution), prelude types
should be implicit imports in the scope chain — not special-cased. The
checker resolves `String` the same way it resolves any imported name:
via the dependency's `SemanticModel`.

Well-known type identity checks (e.g. "is this the stdlib `Array`?") use
a `WELL_KNOWN_TYPE_MODULES` map that looks up the canonical module's
checked exports by path, matching the bootstrap compiler's approach:

```
WELL_KNOWN_TYPE_MODULES = {
  "String"     → "zena:string",
  "FixedArray" → "zena:fixed-array",
  "Array"      → "zena:growable-array",
  "HashMap"    → "zena:map",
  "HashSet"    → "zena:set",
  "Error"      → "zena:error",
  "Iterable"   → "zena:iterator",
  "BoundedRange" → "zena:range",
  "FromRange"    → "zena:range",
  "ToRange"      → "zena:range",
  "FullRange"    → "zena:range",
}
```

### Migration Plan

**Phase 1 — Check stdlib modules through the normal pipeline.**
Remove the `isStdlib` skip in `checkCompilation()`. Stdlib files go
through `checkFile()` in topo order like everything else. Their
`CheckResult`s go into `allResults`, so downstream files get `depModels`
for stdlib deps.

**Phase 2 — Populate prelude from checked exports.**
After checking prelude modules, iterate their exports and populate
`#preludeTypes`/`#preludeValues` from the real `CheckResult.model` data.
Remove corresponding entries from `registerStandardPrelude()` one module
at a time.

**Phase 3 — Well-known type lookups.**
Add the `WELL_KNOWN_TYPE_MODULES` map. Replace `resolvePreludeType("Iterable")`
and `isPreludeClassType()` calls with lookups against checked module exports
by canonical path.

**Phase 4 — Delete `registerStandardPrelude()`.**
Once all prelude types come from real checked modules, the function is empty
and can be removed.

### Practical Blocker

The self-hosted checker doesn't yet support all language features used in
stdlib: `interface` + `implements`, `extension class`, `@intrinsic`/
`@external` decorators, `operator` overloading, `declare` methods. The
simpler stdlib files (`error.zena`, `range.zena`, `option.zena`) would
work today, but the core collection types (`fixed-array`, `growable-array`,
`map`, `set`) need these features.

The pragmatic path is incremental: check the simple stdlib files first,
stub only what can't yet be checked, and replace stubs with real checked
modules as checker features land.

---

## Open Questions

1. **Comment preservation strategy?** Store comments in AST nodes (simpler) or
   in a separate table (cleaner for the checker, more work for the formatter)?
   Leaning toward a side table: `comments: Map<i32, Array<Comment>>` keyed by
   the AST node ID that the comment is attached to.

2. **Error recovery in parser?** The TypeScript parser has minimal error
   recovery. For LSP usage, we'll want better recovery (parse partial/invalid
   syntax and still produce a useful AST). Not needed for Milestone 0, but
   factor it into the AST design.

3. **How much of the checker's backend-agnostic analysis layer do we keep?**
   The TS compiler has `analyzeBoxing()`, `analyzeMethodDispatch()`, etc. These
   are useful for multiple backends. Port them as part of Milestone 5 or fold
   them into codegen?

4. **Should `TypeContext` own the class hierarchy, or should it be separate?**
   Leaning toward separate: `TypeContext` handles interning and type creation;
   `ClassHierarchy` handles inheritance relationships. This keeps
   responsibilities clear.

5. **When to introduce a config/options system?** The TS compiler has an
   `options` bag passed everywhere. Design a clean options type early (Milestone 0) so all phases can reference it consistently.

6. **Analysis pass boundaries.** Where exactly does Phase 2 (per-module
   checking) end and analysis passes begin? Some analyses blur the line. For
   example, vtable layout needs the full class hierarchy, which is built
   incrementally across modules during Phase 2. The rule of thumb: if it
   produces type errors, it's checking. If it produces optimization or
   codegen-preparation information, it's an analysis pass.

---

## Compiler Host API

### Current Design ✅ Implemented

The self-hosted compiler has a clean host abstraction:

```zena
interface CompilerHost {
  readFile(path: String): String
}
```

Module resolution is handled separately by `ModuleResolver`, which takes a
package map and resolves specifiers to canonical paths. The `LibraryLoader`
combines both: it uses `ModuleResolver` for resolution and `CompilerHost` for
source loading. The `Compiler` class wires everything together via
`createCompiler(host, options)`.

This separation works well: CLI implements `CompilerHost` with filesystem I/O,
tests implement it with `MockHost` backed by `HashMap<String, String>`.

### What We Need for the Self-Hosted Compiler

The current interface is close to sufficient but needs a few additions for
broader use cases:

**1. Output handling.** The current compiler returns `Uint8Array` from codegen
and the caller writes it wherever they want. This is good — the compiler
should not assume it can write to a filesystem. Keep this.

**2. Diagnostic reporting.** The current compiler returns diagnostics as data
(error messages with source locations). The host decides how to display them.
Keep this.

**3. Async loading.** For web-based compilation (e.g., a playground or
in-browser IDE), module loading may need to be asynchronous (fetching files
over HTTP). The current `load` is synchronous. Options:

- Make `load` return `String | Promise<String>` — messy but pragmatic.
- Make the entire compilation async — clean but Zena doesn't have `async` yet.
- Require the host to pre-load all files and provide them synchronously —
  works for playgrounds, messy for large projects.

For now, keep synchronous loading. When we need async, the host can
pre-populate a cache. When Zena gains async support, make the API async.

**4. Module resolution strategies.** Different hosts have different resolution
rules:

- CLI: Filesystem paths, `node_modules`-style resolution, stdlib bundled
- Web playground: All files in a virtual FS, stdlib pre-loaded
- LSP: Files open in the editor override disk versions
- Testing: In-memory file maps

The current `resolve(specifier, referrer): String` is flexible enough for
all of these. The host controls the resolution logic entirely.

**5. File watching (LSP).** The LSP needs to know when files change on disk.
This is outside the compiler's scope — the LSP host watches files and tells
the compiler to re-check.

### Proposed Self-Hosted Host Interface

```
interface CompilerHost {
  // Module resolution: specifier (e.g., './math', 'zena:array') + referrer
  // → canonical path (e.g., '/project/src/math.zena', 'zena:array')
  resolve(specifier: String, referrer: String): String

  // Load source text for a canonical path
  load(path: String): String

  // Optional: check if a path exists (useful for resolution)
  exists(path: String): boolean

  // Optional: file version/hash for incremental compilation
  // Returns null if versioning is not supported
  version(path: String): String?
}
```

The `exists` method avoids the "try to load, catch error" pattern during
resolution. The `version` method enables incremental compilation — if a
file's version hasn't changed, its AST and semantic model can be reused.

### Web Playground Scenario

A web-based playground would implement `CompilerHost` with:

- A `Map<String, String>` of virtual files (editor contents)
- Pre-bundled stdlib source (loaded at page init)
- `resolve` maps `'zena:*'` to stdlib, `'./*'` to virtual files
- `load` reads from the map
- `exists` checks the map
- `version` returns a hash of the source text

The compiler runs synchronously on the pre-loaded files. No network I/O
during compilation. The host handles the async loading _before_ invoking the
compiler.

### LSP / IDE Scenario

An LSP host would implement `CompilerHost` with:

- Open editor buffers override filesystem reads
- `version` returns the editor's version number for open buffers, and
  filesystem mtime for disk files
- The LSP watches for file changes and triggers re-compilation
- For incremental checking, the compiler compares versions and skips
  unchanged modules

### Testing Scenario

Test hosts (like the current `InMemoryHost`) work as-is. Provide a
`Map<String, String>` and the compiler operates on it. No changes needed.

---

## Next Steps

1. Harden the formatter (Milestone 1) — `packages/zena-formatter`
   exists but is lightly tested; run it over the compiler's own source
   and expand its test coverage.
2. LSP maturation (Milestone 4) — `packages/language-service` runs the
   self-hosted compiler; feature coverage is the open end.
3. Retire the bootstrap compiler: with self-hosting exact, the TS
   compiler's remaining duty is stage-0 builds. Several language
   rulings in BUGS.md are deferred to this retirement so they are
   implemented once, not twice.
4. ZIR optimization loop (ir.md §9/§14 M3) — inline, devirtualize,
   SRoA, SCCP.
