freshenBinders renames a free reference sharing its Standalone Let binder's name #345

Problem

freshenBinders — the traversal that alpha-renames an expression's binders before a copy of it is pasted somewhere else — renames the binders of a Let by collecting every binder name of the Let into a rename map up front, then renaming all the right-hand sides and the body under that one map. It says so itself:

    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 (…) 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

That is sound only under the global uniqueness condition (GUC), which the comment names. The IR's scoping rule is sequential — Note [Sequential scoping of Let bindings] — 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 RHS resolves to an outer binder. Under GUC no free variable can share a binder's name, so hoisting the map cannot capture anything. On input that is not GUC, it can: the binder's rename entry is already in the map when its own RHS is walked, so a free occurrence that happens to share the binder's name is renamed along with the binder, silently repointing it.

The minimal shape is let x = x in l, where the x on the right is free. Freshening it should rename only the binder, but renames both:

      Let
-       Standalone ( Nothing , Name "x$0" , Ref Nothing (Local (Name "x$0")) )   -- actual
+       Standalone ( Nothing , Name "x"   , Ref Nothing (Local (Name "x"))   )   -- expected
        Ref Nothing (Local (Name "l"))

freshenBinders is the odd one out here. alphaEq implements the sequential rule explicitly — it compares a Standalone right-hand side before binding the name, with the comment -- The RHS of a Standalone binding does not see its own binder: — and countFreeRefs does the same. Even freshenBinders' own LetValues case threads the map correctly, for the same reason: -- The RHS is renamed under the incoming map — the binders scope over the body only. Only the Let case hoists.

How it shows up

As an intermittent failure of the property IR Optimizer / inlines expressions referenced once, at roughly 1 run in 100. That test feeds optimizedExpression generated expressions that are deliberately not uniquified, inlines a once-used binding, and compares the pasted copy to the original up to alpha-equivalence. It fails exactly when the generator happens to produce the degenerate self-shadowing shape above, which is why the rate is low.

The failure reproduces on unmodified main (245 examples, same test) at the same rate, so it is not new. It also needs the whole IR Optimizer group to run — 200 runs of the test in isolation never reproduced it, because the group's global seed drives which hedgehog seeds this test receives.

Impact

None on emitted code. uniquifyNames is the pipeline's entry pass and every pass declares passRequires = guc, so real compilation never presents non-GUC input to freshenBinders. The cost is a test suite that reddens ~1% of the time, which trains everyone to re-run rather than read.

Approach

Thread the rename map through the groupings instead of hoisting it, matching the scoping rule the rest of the codebase implements: a Standalone right-hand side is renamed under the incoming map and only then does its binder enter; a RecursiveGroup's members all enter before any of their right-hand sides are walked.

    Let ann binds body → do
      (renames', binds') ← mapAccumM freshenGrouping renames binds
      Let ann binds' <$> go renames' body

  freshenGrouping renames = \case
    Standalone (bindAnn, name, expr) → do
      expr' ← go renames expr                    -- before the binder is in scope
      (renames', name') ← bindFresh renames name
      pure (renames', Standalone (bindAnn, name', expr'))
    RecursiveGroup members → do
      (renames', names) ←
        mapAccumM (\rs (_, n, _) → bindFresh rs n) renames members
      members' ← forM (NE.zip members names) \((bindAnn, _, expr), name') →
        (bindAnn, name',) <$> go renames' expr
      pure (renames', RecursiveGroup members')

bindFresh keeps the existing discardName exemption, which must survive: a magic-do-lowered thunk binds several Let statements to _, and a single name-keyed entry would send them all to the same fresh name. mapAccumM is already the idiom the AbsN case uses for parameters.

Verification

The change is a no-op on GUC input, where the two orders provably agree, so the whole golden corpus should stay byte-identical and the suite green — that is the check that no caller (substituteCopyM / substituteMoveM, the call-pattern specializer, and the five call-site inliners in the optimizer) relied on the hoisted behaviour.

The existing prop "is an alpha-renaming of GUC-shaped input" deliberately restricts itself to uniquified input, so it cannot catch this. A non-GUC sibling is the red-first test: assert that freshening let x = x in l leaves the free x alone.

Prerequisites / Relations

Independent — nothing needs to land first. Surfaced while implementing #251 (PR #344), but not caused by it: the flake reproduces identically on the main commit before that change. The fix touches freshenBinders, which every call-site inliner and the call-pattern specializer go through, so it wants its own diff rather than riding along with feature work.

Acceptance criteria

• Freshening a Standalone binding renames the binder without touching a free reference of the same name in its own right-hand side.
• The discard binder exemption still holds.
• IR Optimizer / inlines expressions referenced once survives a few hundred consecutive runs of the whole spec group.