# Two-phase, part 2 — the resolve / check pass (design)

Part 1 (`docs/plan-two-phase.md`) gave the compiler an AST: parsing now
builds nodes and `Lower` emits from them.  What is still **not** split
is *semantic analysis*: name binding, type resolution and all 2xx
diagnostics still run **during parse**, inside the grammar's actions.

This document designs the second split, which removes the last
forward-reference machinery and makes forward references ordinary.

## 1. Why

Forward references — a body naming a global, a `CONST` naming a later
type — are still special-cased:

- the grammar's `Design` **tolerates** an undeclared name inside a
  procedure, creates a placeholder alias (`SymTab.FwdVarRef`) and emits
  an `@` marker;
- the placeholder is `ClPtr`-shaped, so the type checks must be made
  **lenient** (`IsFwdVar` guards in `Assignable`, `ArithCheck`,
  `OrdCheck`, `Expr`);
- a module-end sweep (`FwdVarFlush`) reports the ones that never
  resolve (201).

All of that exists only because checks run **before** the module's later
declarations are known.  A resolve/check pass that runs *after* parsing
would let every reference bind first and check second, so the mechanism
could be deleted.  It would also unlock what depends on it: aggregate
(`SET`/record) values in `CONST`, forward *procedures* without a
DEFINITION, and a cleaner statement-context story.

## 2. Current architecture (measured)

`compiler/src/M2.atg` is 3,489 lines with **171 `SemError` sites** and
**~1,061 `SymTab.*` call sites** (190 distinct procedures) across its
production actions.  `Lower.mod` (2,337 lines) emits from the AST and
already does *some* late binding (e.g. it resolves a forward
designator's name at lower time), but it is an **emitter**, not a
checker: it assumes the `SymTab` entries are already correct.

So the work is a **relocation**: move the semantic decisions out of the
per-production actions into a walk over the AST, run after the unit's
declarations are complete.

## 3. Target pass structure

```
per unit:
  1. Parse        -> AST + a *declaration* skeleton in SymTab
                     (names and kinds only; no type checks, no forward
                     errors)
  2. Resolve/Check-> walk the AST: bind identifiers to symbols, resolve
                     and complete types, check assignments/arity/2xx,
                     emit all diagnostics
  3. Lower        -> walk the AST (unchanged) and emit QBE
  4. Emit         -> unchanged (buffered image, EndModule)
```

The crucial ordering change: **step 2 runs after the whole unit (and its
imports) are parsed**, so a forward reference simply binds to a symbol
that now exists.

## 4. What must move

Grouped by where the check lives today:

| Category | Today (grammar actions) | Notes |
| --- | --- | --- |
| Declaration entry | `SymTab.Enter`/`EnterPending`/`FixPending` in `ConstDecl`/`TypeItem`/`VarDecl`/`ProcHeading` | keep in parse: names/kinds are the skeleton |
| Type constructor checks | `Type`/`ArrayType`/`RecordType`/`SetType`/`PointerType` actions | move: bounds, element/base resolution, 230s |
| Expression typing | `Expr`/`SimExpr`/`Term`/`Fact`/`Design` sets `t` on every node | move: fill `AST.SetTy`, `ArithCheck`/`RelCheck`/`Assignable` |
| Statement checks | `AssOrCall`/`IfStat`/`WhileStat`/`ForStat`/`CaseStat`/`ReturnStat` | move: lvalue/type/232/214 checks |
| Call checks | `ArgList`/`ActParam` (arity 233, formal type, VAR-ness) | move: against the bound callee |
| Class/method checks | `MethodHeading`/`ClassItem`/method binding in `Design` | move: method lookup, vtable slots |
| Forward tolerance | `Design` placeholder + `IsFwdVar` + `FwdVarFlush` | **delete** once 1–7 are late |

`Lower` currently re-derives a little of this (it calls `ClassOf`,
`ArrayElem`, ...).  After the split, `Lower` should read the **types the
checker stored** (`AST.Ty`) instead of re-deriving, so the two agree.

## 5. Resolve/check walk design

- **Binding**: each `NkIdent`/`NkDesignator` gets its resolved symbol
  recorded on the node (a new `AST` field, e.g. `sym`/`uid`), not
  re-looked-up repeatedly.  A designator that never binds is **201**
  here (replacing `FwdVarFlush`).
- **Types**: each expression node already has a `ty` slot; the walk sets
  it.  Aggregates get their descriptor type; sets their word count.
- **Scopes**: the walk mirrors the AST's lexical structure
  (unit → declarations → procedure → block), pushing SymTab scopes as it
  descends.  Declarations were entered during parse in the same order,
  so the walk can look them up directly (no `Enter`).
- **Diagnostics**: all `SemError(n)` for 210–222, 231–235 move to the
  walk.  Parse-time errors stay: 200 (duplicate), 201 for a *declared*
  name that is malformed, 202 (module name).

## 6. Flag strategy and increment order

Keep the old (parse-time) check path until the new one passes, exactly
as the L7 flip did.

Branch `resolve-check` off `v3-generics-inc2`.

1. **Scaffold**: add `proc Resolve(n: AST.Node)` (and helpers) in a new
   `Check.def`/`Check.mod`; call it from the driver between `Parse` and
   `Lower.LowerUnitNow`, gated by a flag.  It starts as a no-op.
   **(done — `compiler/src/Check.*`, gate `-noresolve`, `50df067`.)**
2. **Expressions & designators**: move the `Expr`-family typing and
   `Design` name binding into `Check`; store the resolved symbol and
   type on the AST node (new `AST` field); make `Lower` read them.
   Forward references in a proc body (see §11) are *bound* here, not
   patched.
3. **Statements & calls**: move assignment/control-flow/arity checks.
4. **Forward rebind**: with names now bound late, delete the `Design`
   forward branch, `FwdVarRef`/`FwdVarName`/`FwdVarType`/
   `FwdVarResolve`, `IsFwdVar` and its guards, the grammar's
   `FwdVarNote`/`FwdVarFlush`, and the `@` marker.
5. **Cleanup**: try `-resolve`/legacy byte-compare over the suite to
   prove equivalence, then remove the flag and the old path.

(Step numbering changed 2026-10-15 — see §11.  Type-constructor checks
are **not** a prerequisite and stay parse-time.)

## 7. Verification gates

- **Fixpoint** `./bootstrap/fixpoint.sh` — byte-identical stage2/stage3.
  The hard gate, as always.
- **Suite** `run_tests.sh` (190/190 today) after every increment.
- **Corpus** `tools/v3-corpus/corpus.sh` — the `undeclared identifier` /
  forward-reference buckets should shrink; track compile-OK counts.
- **Byte-compare** (steps 2–5): with the flag on and off, the emitted
  `.ssa` for the whole suite should match until a feature deliberately
  changes.

## 8. Risks and mitigations

- **Sheer size** (~1,000 check sites) — do it category by category, one
  commit each, with the flag; never a big-bang.
- **Two checkers diverging** — byte-compare during the transition.
- **Self-hosting order**: the *old* compiler keeps compiling `Check.mod`
  and `M2.atg` until the flip, so `Check` must respect
  declaration-before-use and the array/`VAR`-formal limitations that bit
  us in inc2.
- **`Lower` reading unchecked types** during the transition — keep
  `Lower` deriving what the checker has not yet moved.

## 9. Delete list (after step 5)

`SymTab.FwdVarRef`, `FwdVarName`, `FwdVarType`, `FwdVarResolve`,
`IsFwdVar`; the grammar's `FwdVarNote`/`FwdVarFlush`/`nFvarRefs` and the
`Design` forward branch; the `@` marker in `Lower`; the `IsFwdVar`
guards in `SymTab.{Assignable,ArithCheck,UnaryCheck,OrdCheck,EqCheck}`
and in `Expr`.

## 10. Entry point

Branch `resolve-check` off `v3-generics-inc2` (`ba9d042`).  Baseline:
suite 190/190, fixpoint OK (3,472,663 bytes).  Start with §6 step 1.

## 11. Revision 2026-10-15 — findings from starting the work

Measured while scaffolding (branch `resolve-check`):

- **The AST is not a typed IR.**  The parser never builds
  `NkArray`/`NkRecord`/`NkPointer`/`NkEnum`/`NkTypeIdent`/`NkProcType`
  (0 sites in `M2.atg` *and* `Lower.mod`); only `NkSubrange` and (one)
  `NkSet` appear.  Constructed types live **only in SymTab** (resolved
  `TypeIndex`), and `Lower` reads them from there.  So the original §6
  step 2 ("walk the type AST") had no data to walk and would have
  needed the parser extended to build a type AST first — a large
  prerequisite that duplicates SymTab for no two-phase benefit.
- **The forward mechanism is narrow.**  `Design`'s fallback fires only
  inside a procedure (`SymTab.InProc()`), only for a name not found,
  and assumes a **module-level variable declared later**.  It creates a
  placeholder symbol (`FwdVarRef`, `ClPtr`-shaped) plus an `@`-marker
  node, and `FwdVarFlush` (module end) patches the placeholder to the
  real symbol/type before `Lower` runs.  Empirically:
  `PROCEDURE P; BEGIN x := 7 END P; VAR x: INTEGER;` compiles, while a
  never-declared `y` is 201.
- **Consequence.**  Removing `FwdVar*` requires binding *after* the
  unit's declarations are all parsed — i.e. the expression/statement
  walk (new §6 steps 2–3) — and **not** the type-constructor checks,
  which can stay parse-time indefinitely.  The AST *does* carry
  expression structure (`NkDesignator`/`NkSelector`/`NkBinExpr`/
  `NkIdent`/literals), and every type the walk needs is available in
  SymTab, so a walk keyed on the AST + SymTab is the tractable target.
- **What step 2 must add to `AST`**: a per-node resolved `TypeIndex`
  (exists — `AST.SetTy`/`AST.Ty`) and, for an identifier/designator
  base, its resolved symbol (needs a new field, or reuse the existing
  node-id slot) so `Lower` can stop re-deriving.

### Progress

- **2026-10-15 (`f34ca98`)** — the forward-reference *resolution* half
  moved out of the grammar into `Check` (`NoteForward`/`FlushForward`,
  driven from `Resolve`, which the driver calls for every unit).  To run
  it post-parse, resolution is now scope-independent: `SymTab` records
  the scope at `FwdVarRef` time (`fwdVarScope`) and `FwdVarResolve`
  walks up from it via a new `FindScope` (`Find` is a thin wrapper).
  The grammar's `FwdVarNote`/`FwdVarFlush`, `nFvarRefs`/`fvarId`/
  `fvarSlot` and its four flush call sites are gone; `SymTab.FwdVarType`
  was dead and is removed.
- **Consequences for §9**: step 4 must also delete `Check.NoteForward`/
  `FlushForward` (replaced by real binding in the walk).
- **Note**: `-noresolve` now disables the forward fix-up too (it turns
  off the whole `Check` pass); on forward-free code it stays
  byte-identical, so the suite gate is unaffected.

- **2026-10-15 (`7ca434b`)** — revised step 2 proper (the expression
  walk) turned out to be blocked: `Lower.LowerExprFull` interleaves
  type *construction* with emission (it calls `SymTab.NewSet` /
  `NewStr` / `NewUStr` while emitting), so there is no clean
  "type-only" path to share with a checker, and the AST carries no
  per-expression type to walk.  Took a more direct deletion instead:
  the forward operand is now **`InvalidType`**, so the generic "skip
  checks on an unknown type" rule (which every check already has)
  replaces the purpose-built `IsFwdVar` leniency.  Deleted
  `SymTab.IsFwdVar`, `FwdVarType`, the `fwdVarT` table and the five
  guards; `FwdVarRef` no longer allocates a placeholder alias.
  Suite 190/190; fixpoint OK (3,466,859 bytes).
- **Remaining for step 4**: `SymTab.FwdVarRef`/`FwdVarName`/
  `FwdVarResolve` and `Check.NoteForward`/`FlushForward` still exist,
  but they now only *resolve a name* (no patching).  To delete them,
  `Design` must stop deferring at all — which needs the expression and
  statement checks moved out of the actions, i.e. the walk, still
  blocked on `Lower`'s type/emit split.

- **2026-10-15 (`5703b27`, step 4a)** — expression types are now stored
  on the AST (`SetTy` at the Expr/SimExpr/Term/Fact levels).  Findings
  that shape the split:
  - `Lower.LowerExprFull` **constructs** types while emitting
    (`NewStr`/`NewUStr`/`NewSet`/`NewSubR`) and those do **not** dedup
    (`NewDesc` always allocates).  A type must therefore be constructed
    exactly once and cached on the node; the parser *already* computes
    (and for literals constructs) the same type at parse time — now
    stored — so `Lower` can read `AST.Ty(n)` instead of reconstructing,
    which also removes a duplicate construction per string/set literal.
  - `AST.Ty` defaults to `-1` (= `InvalidType`), so "unset/unknown" is
    distinguishable from a real index; `Lower` can read it with a
    fallback while the split is in progress.
  - the forward **tolerance is a tested feature**: `tests/t_fwdvar.mod`
    (and `Showcase22`) rely on a procedure body referencing a
    module-level variable declared later — including through an
    **array-index selector** (`label[0] := "o"`).  An experiment that
    replaced the tolerance with an immediate 201 failed exactly those
    two tests.  So `FwdVar*` can only go once `Design`'s binding is
    genuinely late, and the walk must keep forward refs *with selectors*.
  - **the missing piece of the split** is a designator *resolver*: the
    type half of `LowerDesign` (~line 690), which `Check` would run
    after resolving forward references and store on the node
    (`AST.SetTy`) for `Lower` to read.  Designator nodes are the only
    expressions whose parse-time type is `-1` (forward/undefined).

- **2026-10-15 (`192ad55`, step 4b)** — the designator resolver exists:
  `Check` resolves a *forward* designator's full type — the base symbol
  (from the scope recorded at reference time) plus its selectors, via
  `SelType` over `SymTab.FieldType`/`ArrayElem`/`PtrBase` — and stores
  it on the node with `AST.SetTy`.  `SymTab.FwdVarResolve` now also
  returns the resolved type, and `Design` attaches the designator node
  to the forward note.  Verified with a temporary differential
  instrument in `LowerDesign` (which computes the same type
  independently): clean across the suite, and it fires (299) when the
  resolver is deliberately broken.  New regression test `t_fwdsel.mod`
  (forward ref through an array-index selector).  Suite 191/191;
  fixpoint OK (3,474,750 bytes).
- **Next**: forward designators are now typed, but an expression
  *containing* one (e.g. `arr[0] + arr[1]`) is still typed `InvalidType`
  at parse time — the walk must propagate the resolved types up the
  tree and then take over the statement/expression checks.  Only then
  can `Design` stop deferring and `FwdVar*` go.

- **2026-10-15 (`9dc2ed7`, step 4c)** — resolved types now propagate up
  the expression tree: `Check.PropNode` walks the unit post-order and
  `EvalExpr` re-types any node still `-1`, combining its operands by the
  operator rules (reusing `SymTab.ArithCheck`/`RelCheck`/`InCheck`/
  `BoolCheck`).  Leaf kinds must be skipped — their `child 0` is a text
  index, not a node (descending into it segfaulted).  First half of the
  `Lower` split too: string and set literals now read the type the
  parser stored instead of constructing a second one.  Verified by the
  differential instrument (compared by class); regression tests
  `t_fwdsel.mod` and `t_fwdprop.mod`; suite 192/192.
- **Remaining**: the *checks* themselves (assignment, control flow,
  calls) are still parse-time and lenient for forwards, so `Design`
  still defers; moving them into the walk is what finally lets
  `FwdVar*` go.  The instrument also exposed a pre-existing, harmless
  divergence: a procedure value's type is `ClProc` at parse time but
  `ClInvalid` in `Lower`.

- **2026-10-15 (`8efae2e`, step 4d)** — the first check moves to the
  walk: an assignment whose operand was a forward reference is now
  type-checked *after* resolution.  `PropNode` returns "touched by a
  forward reference" (a forward designator node is marked `Op=1`; a node
  `PropNode` re-types also counts), and `CheckAssign` re-checks such an
  assignment (`Assignable` / class class).  Previously `n := "abc"` with
  a later `VAR n : INTEGER` was **silently accepted**.  Non-forward
  assignments keep the parser's check, so there are no duplicate
  diagnostics and `-noresolve` still checks fully.  New `expect_fail`
  test `t_bad_fwd.mod`; suite 193/193.
- **Pattern for the remaining checks**: the same shape — a check the
  parser had to skip for a forward operand is re-run in `PropNode` for a
  touched subtree (control-flow conditions, `RETURN`, arity, …).
- **Architectural conclusion**: `FwdVar*`/`NoteForward` *cannot* be
  deleted this way.  Even with every check moved, `Design` must still
  bind a not-yet-declared name — which needs the compiler to parse
  declarations before bodies (a genuinely two-phase parse).  The
  resolve/check pass improves *diagnostics* for forward references and
  gives the type layer; the deletion needs the parse restructure.