M2compiler-V3/docs/plan-resolve-check.md

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.
2. Types: move type-constructor checks (Type/Array/Record/ Set/Pointer) into Check, deleting them from the actions. One constructor kind per commit.
3. Expressions: move Expr-family typing; store AST.SetTy; make Lower read AST.Ty.
4. Statements & calls: move assignment/control-flow/arity checks.
5. 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.
6. Cleanup: try -resolve/legacy byte-compare over the suite to prove equivalence, then remove the flag and the old path.

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.