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. (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.