M2compiler-V3/docs/plan-two-phase-parse.md

Two-phase parse (design) — eliminating the forward mechanism

Goal

Delete SymTab.FwdVarRef/FwdVarName/FwdVarResolve, Check.NoteForward/ FlushForward and the Design forward branch, plus the Op=1 marker — by binding names before they are checked.

Why post-parse checking is not enough

Design defers a name it cannot find inside a procedure because it may be a module-level declaration that appears later in the file. The resolve/check pass happens after the parse, so it cannot help with binding: binding happens during the parse, and the declaration simply has not been read yet. The only fix is to read the declarations before the bodies — a two-phase (or two-pass) parse.

Design A (recommended): module-level body deferral + re-scan

The grammar/parser stays almost entirely as-is; only the order in which the parser visits text changes.

1. Skip module-level procedure bodies. When ProcDecl sees a module-level PROCEDURE, record the body's source span and consume its tokens without parsing them, then carry on with the remaining declarations. Result: every module-level name is in SymTab once the module's declarations are done.
2. Re-scan and parse the bodies. At the end of the module, for each recorded span: seek the scanner to its start and parse the body with the existing Block production. Every module-level name now resolves, so no forward reference is ever created.

Consequences:

• Design's forward branch never fires → the whole FwdVar* path is dead and removable.
• The body productions are reused unchanged (both the skip and the re-parse reuse existing machinery), unlike Design B below.

Pieces

1. Scanner seek (scanner.frm, and expose it in M2S.def's template): PROCEDURE SeekTo (p: INT32) — set bp0/bp/nextPos to p and recompute line/col (scan from offset 0 counting CHR(10); CharAt already indexes the in-memory buffer, so this is O(p)).
2. Token-level body skipper (grammar helper): starting at the PROCEDURE keyword, consume tokens counting block openers {PROCEDURE, IF, CASE, WHILE, FOR, LOOP, WITH, RECORD}; stop when the count returns to 0 — that END closes the procedure. BEGIN is not an opener (a block's BEGIN…END shares the declaration's END), and REPEAT…UNTIL/EXIT/RETURN are not counted. Verify afterwards that the token is END and the following identifier equals the procedure name (guards a mis-skip).
3. Deferral in ProcDecl (module level only): skip + record the span; the declaration node is a placeholder NkProcDecl.
4. Body re-parse: a new grammar entry (reusing Block) driven at the end of Unit, walking the recorded spans.
5. Flag: all of this behind -twophase (default off) until the suite and the fixpoint are byte-identical, then flip.

Design B (rejected): syntax-only bodies + binding walk

Make every expression/statement action resolution-free and bind/type/ check in Check, walking with scopes mirrored from the AST. This is the "true" two-phase and is much larger: it touches every body action, and parse decisions that need types (typed brace literals, method calls, L.x qualified names, HIGH/LEN) would have to be deferred too.

Risks / open questions

• Skipper exactness. A mis-count mis-skips to the wrong END. The post-skip check (END + name) turns this into a clear error rather than silent corruption.
• Scanner state after a seek (line, col, lookahead) and error positions inside re-parsed bodies.
• AST/Lower ordering. Bodies are parsed after the declarations, so node allocation order changes. Lower walks by structure (order- independent), but any parse-time ordinal that assumes file order must be re-checked.
• Nested procedures are inside the deferred span, so they are re-parsed with the same mechanism (their own locals are declared before their statements, so they need no deferral themselves).

Milestones (each with the fixpoint green)

1. SeekTo + the skipper behind the flag; inert.
2. Module-level deferral + body re-parse; byte-compare against the default across the suite.
3. Flip the default; delete FwdVarRef/FwdVarName/FwdVarResolve and Check.NoteForward/FlushForward, the Design forward branch, and the Op=1 marker.

Cost

Pieces 1–2 are a few hundred lines across the scanner frame, the grammar and the driver, and are the largest single change in the resolve/check thread — the reason FwdVar* could not be deleted by moving checks alone.

Progress

• 2026-10-15, milestone 1 (probe behind -twophase, inert). Each outermost procedure/method body is shadow-skipped at the token level and the skip verified before the body parses normally:
  • scanner.frm: PushPos/PopPos save and restore the full scanner state (cursor + all published positions + errors, so a re-scanned bad character cannot double-count). 1-deep use, 8-deep stack.
  • M2.atg: SetTwoPhase switch, procNest counter (hooked once in Block, so ProcDecl and method bodies are both covered), TokIs (compares token text, immune to token renumbering) and ProbeBody (opener counting + END <name> check, silent on success, twophase probe mismatch to StdOut otherwise — never into the listing).
  • compiler.frm + parser.frm: -twophase flag plumbed to M2P.SetTwoPhase at both driver Parse sites.
  • Openers counted: MODULE (nested modules), PROCEDURE, CLASS (incl. CLASS IMPLEMENTATION), RECORD (incl. variant CASE), IF, CASE, WHILE, FOR, LOOP, WITH. BEGIN is not an opener; REPEAT…UNTIL needs none.
  • run_tests.sh gains a twophase_same gate (3 procedure-heavy files byte-compared flag-off vs flag-on).
  • Verified: suite 196/196 (193 + 3 probe gates); all 142 single-file tests plus session spot-checks (incl. Library1) and the compiler's own sources produce byte-identical .ssa with the flag on and zero mismatches; fixpoint OK (3,517,333 bytes).
• Finding (V3 name resolution). The first cut called the frame's Get from the new atg helper. gm2 accepts it (whole-scope), but the self-hosted V3 compiler resolves single-pass: the bare Get bound the imported M2S.Get(VAR sym) and stage 2 failed with 233s (plus knock-on 201s at END M2P). Fix: the helper advances via Adv (M2S.Get(sym); INC(errDist) — exactly the frame's Get body for a pragma-free grammar, where the scanner never returns a token above maxT). Rule going forward: atg helpers must never call a later-declared frame procedure by a name that collides with an import.
• Next: milestone 2 — record body spans during the probe, add the body-entry production, and re-parse bodies after the declarations (driver-level restart), byte-compared against the default.
• 2026-10-16, milestone 2a (spans + SeekTo, still inert).
  • scanner.frm: SeekTo(p) — replays NextCh from offset 0 over the in-memory buffer (O(p), no file I/O), so curLine/lineStart/ lastCh match a fresh parse exactly. Published pos/len still describe the previous token afterwards — caller must Get immediately (same contract as the priming Get in Parse).
  • M2.atg: span table (nSpans/spanName/spanStart, per-parse, 1024 entries) recorded in ProbeBody; a SeekTo(start)+Adv round-trip check per body (sym/nextPos equality) whose side effects the trailing PopPos discards — mismatch prints twophase seek mismatch, silent otherwise.
  • Verified: 142-file sweep, zero probe/seek mismatches, zero .ssa diffs; suite 196/196 (gate now greps both mismatch kinds); fixpoint OK (3,584,690 bytes). Positive controls: temp print showed the check firing per body with the flag on (reverted), and a truncated file reports probe mismatch.
  • Finding (sharpened V3 rule). The first 2a cut called NoteSpan (defined after ProbeBody, not in M2P.def) and stage 2 failed 233 + END M2P knock-ons. Bisected to the rule: V3 has no forward procedure tolerance at all — even P; with P declared two lines later is 233 (+201 at EOF). The existing sources self-compile only because every .mod is paired with its .def, which the driver parses first (so e.g. SemError is already declared when NoteLabel's body compiles), plus strict declaration-before-use inside modules. Fix was ordering (declare NoteSpan before its caller), same as the CopyNm precedent. The FwdVar tolerance covers module-level variables only.
• Next: milestone 2b — SymTab save/re-enter-body-scope primitive (no re-push exists today; all resumes allocate fresh scopes — mapping in subagent record ses_ebc94df66ffeTZpjrrFnZS1GsF) plus the closer-split (phase-1 skip must replicate CloseProc/EndFunc/ ScopeLeave effects without a body); then 2c deferral wiring (skip + placeholder + end-of-unit re-parse worklist, nested spans append during phase 2), byte-compared; then 2d flip + delete.
• 2026-10-16, milestone 2b (scope primitives, still inert).
  • Audit (record ses_ebc7fa941ffeeUpNEqm1Crqav5): suppressed inline emit = emission only — every QbeGen counter still advances and is discarded per unit by RestoreSession, while Lower's tables are permanent session state. Per-proc call shapes mapped for heading/FORWARD/EXTERNAL/body/method/DefUnit cases.
  • SymTab: DeferReset (per-parse, from the M2 action), DeferBody() (saves curProc + curScope at skip time, returns index / 65535), ReenterDeferred(idx) (restores saved proc scope — params visible, locals entered once — and re-arms procStk), ParamName (i-th formal name, for the re-parse QbeGen replay). Index-keyed (no nested same-name ambiguity); no SymDesc layout change (side table, like fwdVarScope).
  • Lower: ReenterScopeProc(ty) — pushes current owner, resumes a noted entry without re-registering, so the re-parse Block-end ScopeLeave pops back and nested notes attach correctly.
  • M2.atg: spanIdx table fed by DeferBody() in NoteSpan.
  • Verified: suite 196/196; fixpoint OK (3,592,783 bytes); 142-file flag-on sweep byte-identical, zero mismatches; positive control showed defer <name> firing in order per body (reverted).
  • Key design settled for 2c: opens/closes pair within each pass (skip pairs heading-opens with the AbortFunc close per the FORWARD convention; re-parse replays BeginFunc+FuncParams and pairs with EndFunc); registrations run once (skip pass) with the re-parse on resume paths; nested spans append to the table during phase 2 (worklist); DefUnit/EXTERNAL/FORWARD paths unchanged.
• 2026-10-16, milestone 2c (real deferral + repass, behind -twophase).
  • Phase 1: DeferSkip (from Block, only for plain ProcDecl bodies — methods stay inline) skips the body for real, leaves the scanner at the matching END so Block's trailing END ident consumes it, records the span, and ProcDecl closes like FORWARD (AbortFunc, no body node). Phase 2: an inlined loop at both module ends (ProgModule/ImplUnit) SeekTos each span, re-arms SymTab/Lower/QbeGen, parses Block, attaches body + block decls to the proc node, and closes with ScopeLeave/CloseProc/ EndFunc. Scanner/parser state and the unit's astDecl/astStmt are saved and restored around the loop.
  • Two bugs found and fixed: the loop clobbered the unit's astDecl/astStmt (now saved/restored), and PopPos restored errors, wiping every diagnostic recorded during the repass (now the post-loop count is re-instated — this had silently dropped 210/232 etc. in deferred bodies).
  • Verified: suite 199/199 (twophase gates: identity on forward-free files, functional -> 42 on t_fwdvar/t_fwdsel/ t_fwdprop, incompatible assignment on t_bad_fwd); fixpoint OK (3,620,461 bytes).
  • Measured: all 142 single-file tests run under -twophase with zero signals; 138/142 byte-identical. The 4 that differ are exactly the forward-reference tests (t_fwdvar/t_fwdsel/ t_fwdprop/t_bad_fwd): deferral makes a forward variable ordinary, so it compiles like a normally-ordered one — the legacy FwdVar path is the divergent one (it drops a loadw). Deferred output for those matches the normal codegen (verified against a reordered fixture) and runs to 42. Sessions DBasicProg/TString/ Showcase12 byte-identical.
  • Known gap (why this is not flipped). On some multi-module implementation sessions (e.g. Conversions.mod in the Library1 session), -twophase records a spurious ident expected whose position lands inside a repassed body, even though the emitted .ssa is identical to the default. So the repass parses to the correct AST but trips one extra SynError. Next: locate it (the candidates are the pos/len "previous token" model interacting with SeekTo, or a construct where the repass consumes one token more). Until then the pass stays opt-in and the default path (which never defers) is what ships.
• 2026-10-16, milestone 2c fix + flip (default on).
  • Root cause of the spurious ident expected: DeferSkip does a PushPos for its failure-restore, but on its success path it left the scanner at END and never popped — leaking one snapshot per deferred body until PushPos started failing (8-deep), after which the module-end PopPos restored a stale slot and the parser's SynError read a stale nextPos (hence a bogus position inside an earlier body). Fixed with a new scanner.DropPos (discard the top snapshot without restoring), called on DeferSkip's success path. Also removed the now-dead ProbeBody (superseded by DeferSkip).
  • Flip: with the fix, deferral is byte-clean on Library1, and the whole suite passes with deferral on. doTwoPhase now defaults to TRUE; -notwophase restores the old inline parse (debug escape); -twophase is still accepted.
  • Verified: suite 199/199 with deferral on (all session tests exercise the deferred path); fixpoint OK with deferral on (3,611,981 bytes) — the self-hosted compiler self-compiles byte-identically under the deferral; forward tests run to 42 and t_bad_fwd still errors; -notwophase reproduces the legacy output for forward-free code (gate).
  • Not yet deleted: FwdVar*/NoteForward/FlushForward and the Design forward branch. They remain exercised by nested-local forwards (a nested proc's body naming a parent local declared later), which the module-level deferral does not cover. That case is a pre-existing limitation too (it fails to link under -notwophase as well), so deleting FwdVar* needs either nested deferral or accepting the limitation — a separate step.
• 2026-10-16, milestone 2d — the forward machinery is deleted.
  • Nested deferral was tried and reverted: allowing deferral during the repass (the loop already grows as spans append) fixes nothing for nested-local forwards and regresses nested-proc codegen (t_nestdeep/showcase10 produced wrong results), so deferral stays module-level.
  • Deleted: SymTab.FwdVarRef/FwdVarName/FwdVarResolve and their tables; Check.NoteForward/FlushForward (and the nFwd bookkeeping); the Design forward branch (FwdVarRef + Check. NoteForward + Op=1 marker) — an undeclared name inside a procedure is now a plain 201; plus the dead Check.SelType/ LeafName.
  • Language effects: a module-level body may now call a procedure declared later in the module (no FORWARD needed) — the deferral makes forward procedure calls ordinary too; a nested proc naming a parent local declared later is a clean 201 (was a broken image).
  • Verified: suite 201/201 (new t_fwdproc -> 7, t_bad_nestfwd undeclared identifier); fixpoint OK (3,574,843 bytes); corpus 365 OK vs 358 with -notwophase (+7 files, 0 regressions, 0 crashes).
  • The two-phase thread's original goal — delete the forward-reference machinery — is achieved. Remaining cleanup (separate): Check is now mostly a vestigial walk (PropNode/EvalExpr/CheckAssign re-type/ re-check nothing once no node is Ty = -1).
• 2026-10-16, cleanup — Check removed, scaffolding dropped.
  • Measured first: instrumenting PropNode showed it did re-type Ty = -1 nodes in 31 tests, but gutting Resolve left the emitted .ssa byte-identical across all 141 suite files (and 201/201). So the walk was cosmetic: Lower recomputes what it needs, and Check emitted no diagnostics (its only source, CheckAssign, was reachable only via the deleted Op=1 marker).
  • Deleted Check.def/Check.mod outright, its driver calls, the -noresolve option (it only gated that pass), and the atg import. build.sh drops Check; fixpoint.sh needs nothing (it stages src/*.def/*.mod dynamically). Also removed the now-unused procNest and the always-true L7 scaffolding flag twoPhase (13 sites in the atg, all inert guards around AST building).
  • Verified: suite 201/201; fixpoint OK (3,555,791 bytes); .ssa byte-identical on spot-checks and the 141-file set.
  • The pipeline is now Parse (builds AST; bodies deferred and re-parsed at unit end) -> Lower -> Emit. There is no separate resolve/check pass because binding is late by construction.