fix(ir): rename a Let's binders in scope order in freshenBinders - #347

Closes #345.

freshenBinders alpha-renames every binder bound inside an IR expression to a fresh, supply-minted name. The optimizer calls it whenever it pastes a copy of an expression somewhere else — the call-site inliners, the call-pattern specializer, and the substituteCopyM/substituteMoveM substitution pair all go through it — so that the copy's binders cannot collide with anything at the destination. Renaming a binder means rewriting the references that binder binds; references that are free in the expression belong to the enclosing scope and must survive untouched.

The Let case did not honour that. It collected every binder name of the Let into one rename map up front and then walked all the right-hand sides under that single map:

    Let ann binds body → do
      -- Under unique binders no Let name can be referenced before it is
      -- bound, so all the groupings can enter the rename map up front.
      -- …
      renames' ←
        foldlM
          ( \rs name → do
              name' ← freshNameFor name
              pure (Map.insert name name' rs)
          )
          renames
          (filter (/= discardName) (bindingNames =<< toList binds))
      let renameBound (bindAnn, name, expr) =
            (bindAnn,Map.findWithDefault name name renames',)
              <$> go renames' expr
      Let ann <$> traverse (traverse renameBound) binds <*> go renames' body

The comment states the precondition the shortcut needs, and it is exactly the one that fails here. The IR's scoping rule is sequential, like Scheme's let* — Note [Sequential scoping of Let bindings] in IR/Types.hs — and its first clause says a Standalone binding is non-recursive: its own name is not in scope in its right-hand side, so a reference to that name from its own right-hand side resolves to an outer binder. Because the binder's rename entry was already in the map when its own right-hand side was walked, such a free reference was renamed along with the binder and silently repointed at it.

The minimal shape is let x = x in y, where the right-hand-side x is free. Freshening it should rename the binder alone; instead it renamed both (verbatim from the guard added below, expected being the correct result and but got the pre-fix one):

       expected: Let Nothing (Standalone (Nothing, Name "x$0", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "y")))
        but got: Let Nothing (Standalone (Nothing, Name "x$0", Ref Nothing (Local (Name "x$0"))) :| []) (Ref Nothing (Local (Name "y")))

freshenBinders was the odd one out. alphaEq (structural equality modulo binder names) implements the sequential rule explicitly — it compares a Standalone right-hand side before binding the name, under the comment -- The RHS of a Standalone binding does not see its own binder: — and both free-reference counters, countFreeRefs and countFreeRefUsage, thread their bound-name set through the groupings the same way. Even freshenBinders' own LetValues case already got it right, for the same reason: -- The RHS is renamed under the incoming map — the binders scope over the body only. Only the Let case hoisted.

The fix

The rename map is threaded through the groupings in scope order instead of being hoisted:

    -- The groupings bind sequentially, so the map grows left to right.
    Let ann binds body → do
      (renames', binds') ← mapAccumM freshenGrouping renames binds
      Let ann binds' <$> go renames' body

  freshenGrouping renames = \case
    -- A Standalone binding is non-recursive: its RHS does not see its
    -- own binder, so the RHS is renamed under the incoming map and the
    -- binder enters only afterwards.
    Standalone (bindAnn, name, expr) → do
      expr' ← go renames expr
      (renames', name') ← bindFresh renames name
      pure (renames', Standalone (bindAnn, name', expr'))
    -- Every member of a recursive group is in scope in every member's
    -- RHS, so the whole group enters the map before any RHS is walked.
    RecursiveGroup members → do
      (renames', rebound) ← mapAccumM (\rs (bindAnn, name, expr) → do
          (rs', name') ← bindFresh rs name
          pure (rs', (bindAnn, name', expr))) renames members
      members' ← forM rebound \(bindAnn, name, expr) →
        (bindAnn,name,) <$> go renames' expr
      pure (renames', RecursiveGroup members')

The discard binder _ keeps its exemption, now expressed in bindFresh: it is exempt from the uniqueness invariant, so one Let can bind it several times (a magic-do-lowered thunk binds a run of statements to _), and a single name-keyed map entry would rename every one of them to the same fresh name — a genuine duplicate the exemption no longer covers. Nothing may reference it, so it takes no rename at all.

  bindFresh rs name
    | name == discardName = pure (rs, name)
    | otherwise = do
        name' ← freshNameFor name
        pure (Map.insert name name' rs, name')

How it showed up

As an intermittent red in the property IR Optimizer / inlines expressions referenced once. That test hands optimizedExpression, the optimizer's single-expression entry point, a generated and deliberately non-uniquified inlinee, lets it inline the used-once binding, and compares the pasted copy against the original up to alpha-equivalence. It fails exactly when the generator happens to draw the self-shadowing shape, which is why it is rare.

Fixing hspec's global seed makes it deterministic. --seed 328 on the pre-fix build draws let j = j in [] as the inlinee and fails verbatim:

           2154 ┃       inlinee ← forAll $ fmap optimizedExpression do
                ┃       │ Let
                ┃       │   Nothing
                ┃       │   (Standalone
                ┃       │      ( Nothing , Name "j" , Ref Nothing (Local (Name "j")) ) :|
                ┃       │      [])
                ┃       │   (LiteralArray Nothing [])
...
           2169 ┃       diff (optimizedExpression original) alphaEq expected
                ┃       │ ━━━ Failed (- lhs) (+ rhs) ━━━
                ┃       │ -     Standalone
                ┃       │ -       ( Nothing , Name "j$0" , Ref Nothing (Local (Name "j$0")) ) :|
                ┃       │ -       []
                ┃       │ +     Standalone
                ┃       │ +       ( Nothing , Name "j" , Ref Nothing (Local (Name "j")) ) :|
                ┃       │ +       []

Impact on emitted code: none

uniquifyNames is the pipeline's entry pass and the only one whose stated precondition is merely wellScoped; all nine passes behind it declare passRequires = guc, the global-uniqueness condition under which every binder in the program has a distinct name. Real compilation therefore never presents a shadowed shape to freshenBinders. The whole golden corpus — .ir, .lua and the hand-verified eval/golden.txt oracles alike — is byte-identical; the branch touches no generated file:

$ git diff --stat origin/main...HEAD
 ...29_120000_unisay_freshen_binders_scope_order.md | 34 ++++++++++
 lib/Language/PureScript/Backend/IR/CSE.hs          | 11 ++--
 lib/Language/PureScript/Backend/IR/Types.hs        | 72 ++++++++++++++--------
 test/Language/PureScript/Backend/IR/Types/Spec.hs  | 31 ++++++++++
 4 files changed, 117 insertions(+), 31 deletions(-)

(CSE.hs is comment-only: two remarks in the common-subexpression-elimination pass cited freshenBinders' hoisted map as precedent for its own, so they now state the assumption directly instead of pointing at code that no longer works that way.)

Verification

Two example-based guards were added first and confirmed red on the unmodified traversal. The first pins the acceptance criterion; the second pins the left-to-right ordering, which a "hoist everything except the current binder" implementation would still get wrong:

    leaves a free reference alone in the RHS of its own binder [✘]
    brings a Let's binders into scope left to right [✘]

  1) Types.freshenBinders leaves a free reference alone in the RHS of its own binder
       expected: Let Nothing (Standalone (Nothing, Name "x$0", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "y")))
        but got: Let Nothing (Standalone (Nothing, Name "x$0", Ref Nothing (Local (Name "x$0"))) :| []) (Ref Nothing (Local (Name "y")))

  2) Types.freshenBinders brings a Let's binders into scope left to right
       expected: Let Nothing (Standalone (Nothing, Name "x$0", Ref Nothing (Local (Name "y"))) :| [Standalone (Nothing, Name "y$1", Ref Nothing (Local (Name "x$0")))]) (Ref Nothing (Local (Name "y$1")))
        but got: Let Nothing (Standalone (Nothing, Name "x$0", Ref Nothing (Local (Name "y$1"))) :| [Standalone (Nothing, Name "y$1", Ref Nothing (Local (Name "x$0")))]) (Ref Nothing (Local (Name "y$1")))

Both pass after the change, alongside the existing discard-binder and GUC-alpha-renaming guards:

  freshenBinders
    renames binders and their references, not free references [✔]
    freshens a previously-freshened binder without compounding the suffix [✔]
    is an alpha-renaming of GUC-shaped input [✔]
        ✓ property passed 100 tests.
    leaves a free reference alone in the RHS of its own binder [✔]
    brings a Let's binders into scope left to right [✔]
    keeps the discard binders of a Let apart [✔]

The flake itself was measured as a differential: the IR Optimizer group was run over hspec seeds 1–500 with the pre-fix and post-fix binaries, on the same seeds.

unfixed (this branch with the fix commit reverted): seeds 1..500 -> ok=495 assertion-failures=2 timeouts=3
fixed:                                              seeds 1..500 -> ok=497 assertion-failures=0 timeouts=3

The two assertion failures are seeds 328 and 379, both the self-shadowing shape quoted above; 379 buries it one Let deeper, inside let z = 0 (pink.y) in let x = x in '…', and repoints that inner x the same way:

                ┃       │ -       Standalone
                ┃       │ -         ( Nothing , Name "x$1" , Ref Nothing (Local (Name "x$1")) ) :|
                ┃       │ -         []
                ┃       │ +       Standalone
                ┃       │ +         ( Nothing , Name "x" , Ref Nothing (Local (Name "x")) ) :|
                ┃       │ +         []

(The surrounding z$0-vs-z lines in that rendering are a plain binder rename, which alphaEq tolerates; hedgehog's structural diff shows them regardless.) Neither seed reproduces after the change.

cabal test all is green — 1232 examples, 0 failures — from a cabal clean rebuild that emits no compiler warnings, and hlint lib/ exe/ test/ reports no hints.

One unrelated observation

The three timeouts are the same seeds on both binaries — 109, 152 and 478 — so they are not this bug. Each stalls in the property optimization keeps expressions well-scoped, immediately after blanking an unused shadowing binder keeps outer references bound, where a normal run of the whole group takes 0.35 s. That property runs the full optimizedUberModule pipeline, whose entry pass is uniquifyNames, so it never sees a shadowed shape and cannot be reached by this fix. It is a second, independent source of intermittent redness in the same group and gets its own issue.