Title: renameShadowedNames miscompiles local recursive groups: member order reversed, member RHSs renamed in the wrong scope · Issue #133 · purescript-lua/purescript-lua · GitHub
Open Graph Title: renameShadowedNames miscompiles local recursive groups: member order reversed, member RHSs renamed in the wrong scope · Issue #133 · purescript-lua/purescript-lua
X Title: renameShadowedNames miscompiles local recursive groups: member order reversed, member RHSs renamed in the wrong scope · Issue #133 · purescript-lua/purescript-lua
Description: Two related defects in renameShadowedNamesInExpr (lib/Language/PureScript/Backend/IR/Optimizer.hs), both in the RecursiveGroup branch of the Let case. Both produce wrong runtime behavior without any compile-time error. Bug 1: member orde...
Open Graph Description: Two related defects in renameShadowedNamesInExpr (lib/Language/PureScript/Backend/IR/Optimizer.hs), both in the RecursiveGroup branch of the Let case. Both produce wrong runtime behavior without an...
X Description: Two related defects in renameShadowedNamesInExpr (lib/Language/PureScript/Backend/IR/Optimizer.hs), both in the RecursiveGroup branch of the Let case. Both produce wrong runtime behavior without an...
Opengraph URL: https://github.com/purescript-lua/purescript-lua/issues/133
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"renameShadowedNames miscompiles local recursive groups: member order reversed, member RHSs renamed in the wrong scope","articleBody":"Two related defects in `renameShadowedNamesInExpr` (`lib/Language/PureScript/Backend/IR/Optimizer.hs`), both in the `RecursiveGroup` branch of the `Let` case. Both produce wrong runtime behavior without any compile-time error.\n\n## Bug 1: member order of every local `RecursiveGroup` is reversed\n\nThe fold over group members conses each processed member onto an accumulator and the result is never reversed back:\n\n```haskell\nRecursiveGroup (toList → recGroup) →\n (: bs) . RecursiveGroup . NE.fromList \u003c$> foldl' g (sc, []) recGroup\n where\n g (sc', recBinds) (ann', name, expr) =\n ... (sc'', (ann', name', expr') : recBinds) -- cons, no reverse afterwards\n```\n\nThe sibling code path for `Let` groupings does compensate (`NE.fromList (reverse binds')`); the member list inside a group does not. So every `RecursiveGroup` inside an expression comes out of `renameShadowedNames` with its members in reverse order, unconditionally.\n\nMember order is not cosmetic: it is the initialization order computed by the laziness transform (`Language.PureScript.CoreFn.Laziness.applyLazinessTransform` reorders the group so that statically orderable bindings initialize before their dependents), and the Lua codegen emits the group's assignments in member order. Reversing it undoes the laziness analysis.\n\n### Repro (full pipeline)\n\n```haskell\n-- A laziness-ordered eager group: x must initialize before y,\n-- because y reads x immediately (delay 0), while x only refers to y under a lambda.\nlet x = Name \"x\"; y = Name \"y\"\nlet recGroup = RecursiveGroup\n ( (noAnn, x, abstraction paramUnused (refLocal y 0))\n :| [(noAnn, y, literalObject [(PropName \"foo\", refLocal x 0)])] )\nlet uber = UberModule [] [] [(Name \"main\", lets (recGroup :| []) (refLocal y 0))]\nuberModuleExports (optimizedUberModule uber)\n```\n\nThe group comes out as `[y, x]`, so the generated Lua is:\n\n```lua\nlocal x\nlocal y\ny = { foo = x } -- x is still nil here\nx = function() return y end\n```\n\n`y.foo` is `nil` at runtime. The corresponding PureScript shape is ordinary code, e.g. in a `let`/`where` block:\n\n```purescript\nx = \\_ -> y\ny = { foo: x }\n```\n\nThe reversal is already visible in a committed golden: `test/ps/output/Golden.RecursiveBindings.Test/golden.ir` has the `a`/`b` group in the reverse of the order the laziness transform emits. It happens to be harmless there because both members are lambdas, so their initialization order doesn't matter.\n\nTop-level recursive groups are not affected (`renameShadowedNames` maps over top-level binding expressions individually and never touches grouping order); only `Let ... RecursiveGroup` inside expressions.\n\n## Bug 2: member RHSs are renamed in a scope that lacks the group's own renames\n\n`g` renames each member's RHS with `sc'`, the scope accumulated over the *previous* members only. But recursive-group scoping (Note [Sequential scoping of Let bindings]) makes every member visible in every member's RHS, itself included. When a group member shadows an outer binder, self-references and forward references inside the group keep the old name while the binder gets renamed, so they quietly rebind to the outer binder.\n\n### Repro\n\n```haskell\n-- \\x -> let rec x = f x@0 in x@0 (the member's RHS refers to itself)\nrenameShadowedNamesInExpr mempty $\n abstraction (paramNamed x) $\n lets (RecursiveGroup ((noAnn, x, application (exception \"f\") (refLocal x 0)) :| []) :| [])\n (refLocal x 0)\n```\n\nActual result: the binder becomes `x1` and the body reference follows, but the RHS still says `Ref (Local x) 0`, which now resolves to the outer lambda parameter. The recursion is severed:\n\n```haskell\nAbs (ParamNamed x) (Let (RecursiveGroup ((x1, App (Exception \"f\") (Ref x 0)) :| [])) (Ref x1 0))\n```\n\nForward references hit the same problem: with members `[(y, refLocal x 0), (x, literalInt 1)]` under an outer binder `x`, the member `x` is renamed to `x1` but `y`'s reference stays `x` and rebinds to the outer binder. A shadowing name in a local recursive group is common (`go`, `f` in nested `where` blocks), so this is reachable from ordinary source code.\n\n## Fix sketch\n\n- Bug 1: reverse the member list after the fold, symmetrically with the groupings fix-up.\n- Bug 2: process each group in two passes: first run `withScopedName` for all members to build the group's complete scope, then rename every member's RHS in that scope.\n\nBoth fixes should come with red-first regression tests in `test/Language/PureScript/Backend/IR/Optimizer/Spec.hs` (the repros above are ready to be turned into cases under the \"renames shadowed names\" describe block), plus an eval golden for the order-sensitive group so the runtime consequence stays pinned.\n\nFound during a backend audit on 2026-07-02; bug 2 confirms a hypothesis first noted during the issue #37 work.\n","author":{"url":"https://github.com/Unisay","@type":"Person","name":"Unisay"},"datePublished":"2026-07-02T08:17:45Z","url":"https://github.com/purescript-lua/purescript-lua/issues/133"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:0df7959a-13c3-79d9-3724-b5f0fefc63d8 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | 9EF2:2E7EBB:9EBCBA:C9CCDD:6B00EF35 |
| html-safe-nonce | bb523866a5e81013f75b1fd55007e22bb5c4588e6ac8b206919798c8435dbc25 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI5RUYyOjJFN0VCQjo5RUJDQkE6QzlDQ0REOjZCMDBFRjM1IiwidmlzaXRvcl9pZCI6IjQ4NjU3NzU2MTk3MzQwNDAzNzMiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | eacc6463398d1c58eb437b8332dbd947444428b4a149cead3d217fe8da0328b9 |
| hovercard-subject-tag | issue:4792582699 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/purescript-lua/purescript-lua/133/issue_layout |
| twitter:image | https://opengraph.githubassets.com/b1d29479aeb1c4d6cbc7e412b8170a6f6a0c71537ce72ff8ee0f4b8bc1255d05/purescript-lua/purescript-lua/issues/133 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/b1d29479aeb1c4d6cbc7e412b8170a6f6a0c71537ce72ff8ee0f4b8bc1255d05/purescript-lua/purescript-lua/issues/133 |
| og:image:alt | Two related defects in renameShadowedNamesInExpr (lib/Language/PureScript/Backend/IR/Optimizer.hs), both in the RecursiveGroup branch of the Let case. Both produce wrong runtime behavior without an... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | Unisay |
| hostname | github.com |
| expected-hostname | github.com |
| None | 4ef498cbabcbe3c50befc7a5b743e7072ee770b4daf0e15e54801180d1fa91fc |
| turbo-cache-control | no-preview |
| go-import | github.com/purescript-lua/purescript-lua git https://github.com/purescript-lua/purescript-lua.git |
| octolytics-dimension-user_id | 131581790 |
| octolytics-dimension-user_login | purescript-lua |
| octolytics-dimension-repository_id | 587200487 |
| octolytics-dimension-repository_nwo | purescript-lua/purescript-lua |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 587200487 |
| octolytics-dimension-repository_network_root_nwo | purescript-lua/purescript-lua |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 9983dd5da06943f833c971dd5b6bc988e2858be5 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width