Skip to content

fix: preserve order and scope of recursive groups in renameShadowedNames #147

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
Unisay merged 2 commits into from
Jul 2, 2026
Merged

fix: preserve order and scope of recursive groups in renameShadowedNames #147

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
32899b0
fix: preserve order and scope of recursive groups in renameShadowedNa…
Unisay Jul 2, 2026
41eccea
docs: changelog fragment for the recursive-group rename fix (#133)
Unisay Jul 2, 2026
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
12 changes: 12 additions & 0 deletions changelog.d/20260702_120000_unisay_rename_rec_groups.md
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,12 @@
### Fixed

- `renameShadowedNames` no longer miscompiles local recursive groups. The
member list of every local `RecursiveGroup` came out reversed, undoing the
initialization order computed by the laziness transform, so an eager member
(such as the `name = Lazy_name(0)` forcing binding of a runtime-lazy group)
could run before the member it reads was assigned and crash with an
"attempt to call a nil value" at runtime. Additionally, when a group member
shadowed an outer binder, self- and forward references inside the group kept
the old name and silently rebound to the outer binder, severing the
recursion. Member RHSs are now renamed in the complete group scope and the
member order is preserved (#133).
39 changes: 28 additions & 11 deletions lib/Language/PureScript/Backend/IR/Optimizer.hs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -184,16 +184,29 @@ renameShadowedNamesInExpr scope = go
let expr' = renameShadowedNamesInExpr sc expr
in (sc', Standalone (ann', name', expr') : bs)
RecursiveGroup (toList → recGroup) →
(: bs) . RecursiveGroup . NE.fromList <$> foldl' g (sc, []) recGroup
-- Every member's RHS sees every member of its own group, itself
-- included (see Note [Sequential scoping of Let bindings]), so
-- first bring all the members into scope, then rename the RHSs.
-- Member order is preserved: it is the initialization order
-- computed by the laziness transform.
(groupScope, RecursiveGroup (NE.fromList recGroup') : bs)
where
g
∷ (RenamesInScope, [(Ann, Name, Exp)])
→ (Ann, Name, Exp)
→ (RenamesInScope, [(Ann, Name, Exp)])
g (sc', recBinds) (ann', name, expr) =
withScopedName expr sc' name & \(name', sc'') →
let expr' = renameShadowedNamesInExpr sc' expr
in (sc'', (ann', name', expr') : recBinds)
boundNames ∷ Set Name
boundNames =
foldMap (\(_ann, _name, expr) → collectBoundNames expr) recGroup
groupScope ∷ RenamesInScope
names' ∷ [Name]
(groupScope, reverse → names') = foldl' g (sc, []) recGroup
g (sc', names) (_ann, name, _expr) =
withScopedNameAvoiding boundNames sc' name & \(name', sc'') →
(sc'', name' : names)
recGroup' =
zipWith
( \name' (ann', _name, expr) →
(ann', name', renameShadowedNamesInExpr groupScope expr)
)
names'
recGroup
body' = renameShadowedNamesInExpr scope' body
IfThenElse ann i t e →
IfThenElse ann (go i) (go t) (go e)
Expand All @@ -205,7 +218,11 @@ renameShadowedNamesInExpr scope = go
ForeignImport ann m p ns
where
withScopedName ∷ Exp → Map Name [Name] → Name → (Name, Map Name [Name])
withScopedName e sc name =
withScopedName e = withScopedNameAvoiding (collectBoundNames e)

withScopedNameAvoiding
∷ Set Name → Map Name [Name] → Name → (Name, Map Name [Name])
withScopedNameAvoiding boundNames sc name =
case Map.lookup name sc of
Nothing → (name, Map.insert name [name] sc)
Just renames →
Expand All @@ -214,7 +231,7 @@ renameShadowedNamesInExpr scope = go
)
where
nextIndex = length renames
usedNames = Map.keysSet sc <> collectBoundNames e
usedNames = Map.keysSet sc <> boundNames
rename = uniqueName usedNames name nextIndex

uniqueName ∷ Set Name → Name → Int → Name
Expand Down
63 changes: 63 additions & 0 deletions test/Language/PureScript/Backend/IR/Optimizer/Spec.hs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -29,6 +29,7 @@ import Language.PureScript.Backend.IR.Types
, abstraction
, application
, eq
, exception
, ifThenElse
, isLiteral
, lets
Expand Down Expand Up @@ -475,6 +476,68 @@ spec = describe "IR Optimizer" do
)
renameShadowedNamesInExpr mempty original === renamed

-- Member order of a recursive group is the initialization order
-- computed by the laziness transform; renaming must not disturb it.
test "preserves member order of local recursive groups" do
let x = Name "x"
y = Name "y"
original =
lets
( RecursiveGroup
( (noAnn, x, abstraction paramUnused (refLocal y 0))
:| [(noAnn, y, literalObject [(PropName "foo", refLocal x 0)])]
)
:| []
)
(refLocal y 0)
renameShadowedNamesInExpr mempty original === original

-- See Note [Sequential scoping of Let bindings]: a recursive group
-- member's RHS sees every member of its own group, itself included,
-- so renaming the binder must rename those references too.
test "renames self-references inside a shadowing recursive group" do
let x = Name "x"
x1 = Name "x1"
original =
abstraction (paramNamed x) $
lets
( RecursiveGroup
((noAnn, x, application (exception "f") (refLocal x 0)) :| [])
:| []
)
(refLocal x 0)
renamed =
abstraction (paramNamed x) $
lets
( RecursiveGroup
((noAnn, x1, application (exception "f") (refLocal x1 0)) :| [])
:| []
)
(refLocal x1 0)
renameShadowedNamesInExpr mempty original === renamed

test "renames forward references inside a shadowing recursive group" do
let x = Name "x"
y = Name "y"
x1 = Name "x1"
original =
abstraction (paramNamed x) $
lets
( RecursiveGroup
((noAnn, y, refLocal x 0) :| [(noAnn, x, literalInt 1)])
:| []
)
(application (refLocal y 0) (refLocal x 1))
renamed =
abstraction (paramNamed x) $
lets
( RecursiveGroup
((noAnn, y, refLocal x1 0) :| [(noAnn, x1, literalInt 1)])
:| []
)
(application (refLocal y 0) (refLocal x 0))
renameShadowedNamesInExpr mempty original === renamed

--------------------------------------------------------------------------------
-- Helpers ---------------------------------------------------------------------

Expand Down
1 change: 1 addition & 0 deletions test/ps/output/Golden.RecGroupOrder.Test/corefn.json
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
{"builtWith":"0.15.16","comments":[],"decls":[{"annotation":{"meta":null,"sourceSpan":{"end":[8,70],"start":[8,1]}},"bindType":"NonRec","expression":{"annotation":{"meta":null,"sourceSpan":{"end":[8,70],"start":[8,1]}},"argument":"f","body":{"annotation":{"meta":null,"sourceSpan":{"end":[9,33],"start":[9,11]}},"type":"Literal","value":{"literalType":"ObjectLiteral","value":[["run",{"annotation":{"meta":null,"sourceSpan":{"end":[9,19],"start":[9,18]}},"type":"Var","value":{"identifier":"f","sourcePos":[9,1]}}],["tag",{"annotation":{"meta":null,"sourceSpan":{"end":[9,31],"start":[9,26]}},"type":"Literal","value":{"literalType":"StringLiteral","value":"ok!"}}]]}},"type":"Abs"},"identifier":"store"},{"annotation":{"meta":null,"sourceSpan":{"end":[11,20],"start":[11,1]}},"bindType":"NonRec","expression":{"annotation":{"meta":null,"sourceSpan":{"end":[14,38],"start":[13,3]}},"binds":[{"bindType":"Rec","binds":[{"annotation":{"meta":null,"sourceSpan":{"end":[14,38],"start":[14,5]}},"expression":{"abstraction":{"annotation":{"meta":null,"sourceSpan":{"end":[14,19],"start":[14,14]}},"type":"Var","value":{"identifier":"store","moduleName":["Golden","RecGroupOrder","Test"]}},"annotation":{"meta":null,"sourceSpan":{"end":[14,38],"start":[14,14]}},"argument":{"annotation":{"meta":null,"sourceSpan":{"end":[14,37],"start":[14,21]}},"argument":"v","body":{"annotation":{"meta":null,"sourceSpan":{"end":[14,37],"start":[14,27]}},"expression":{"annotation":{"meta":null,"sourceSpan":{"end":[14,33],"start":[14,27]}},"type":"Var","value":{"identifier":"record","sourcePos":[14,5]}},"fieldName":"tag","type":"Accessor"},"type":"Abs"},"type":"App"},"identifier":"record"}]}],"expression":{"abstraction":{"annotation":{"meta":{"metaType":"IsForeign"},"sourceSpan":{"end":[15,6],"start":[15,3]}},"type":"Var","value":{"identifier":"log","moduleName":["Effect","Console"]}},"annotation":{"meta":null,"sourceSpan":{"end":[15,24],"start":[15,3]}},"argument":{"abstraction":{"annotation":{"meta":null,"sourceSpan":{"end":[15,18],"start":[15,8]}},"expression":{"annotation":{"meta":null,"sourceSpan":{"end":[15,14],"start":[15,8]}},"type":"Var","value":{"identifier":"record","sourcePos":[14,5]}},"fieldName":"run","type":"Accessor"},"annotation":{"meta":null,"sourceSpan":{"end":[15,23],"start":[15,8]}},"argument":{"annotation":{"meta":{"metaType":"IsForeign"},"sourceSpan":{"end":[15,23],"start":[15,19]}},"type":"Var","value":{"identifier":"unit","moduleName":["Data","Unit"]}},"type":"App"},"type":"App"},"type":"Let"},"identifier":"main"}],"exports":["store","main"],"foreign":[],"imports":[{"annotation":{"meta":null,"sourceSpan":{"end":[15,24],"start":[1,1]}},"moduleName":["Data","Unit"]},{"annotation":{"meta":null,"sourceSpan":{"end":[5,23],"start":[5,1]}},"moduleName":["Effect"]},{"annotation":{"meta":null,"sourceSpan":{"end":[15,24],"start":[1,1]}},"moduleName":["Effect","Console"]},{"annotation":{"meta":null,"sourceSpan":{"end":[15,24],"start":[1,1]}},"moduleName":["Golden","RecGroupOrder","Test"]},{"annotation":{"meta":null,"sourceSpan":{"end":[3,15],"start":[3,1]}},"moduleName":["Prelude"]},{"annotation":{"meta":null,"sourceSpan":{"end":[15,24],"start":[1,1]}},"moduleName":["Prim"]}],"moduleName":["Golden","RecGroupOrder","Test"],"modulePath":"src/Golden/RecGroupOrder/Test.purs","reExports":{},"sourceSpan":{"end":[15,24],"start":[1,1]}}
1 change: 1 addition & 0 deletions test/ps/output/Golden.RecGroupOrder.Test/eval/.gitignore
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
actual.txt
1 change: 1 addition & 0 deletions test/ps/output/Golden.RecGroupOrder.Test/eval/golden.txt
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
ok!
74 changes: 74 additions & 0 deletions test/ps/output/Golden.RecGroupOrder.Test/golden.ir
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,74 @@
UberModule
{ uberModuleBindings =
[ Standalone
( QName
{ qnameModuleName = ModuleName "Golden.RecGroupOrder.Test", qnameName = Name "store"
}, Abs Nothing
( ParamNamed Nothing ( Name "f" ) )
( LiteralObject Nothing
[
( PropName "run", Ref Nothing ( Local ( Name "f" ) ) 0 ),
( PropName "tag", LiteralString Nothing "ok!" )
]
)
)
], uberModuleForeigns = [], uberModuleExports =
[
( Name "store", Ref Nothing
( Imported ( ModuleName "Golden.RecGroupOrder.Test" ) ( Name "store" ) ) 0
),
( Name "main", Let Nothing
( RecursiveGroup
(
( Nothing, Name "Lazy_record", App Nothing
( App Nothing
( Ref Nothing ( Local ( Name "PSLUA_runtime_lazy" ) ) 0 )
( LiteralString Nothing "record" )
)
( Abs Nothing ( ParamUnused Nothing )
( App Nothing
( Ref Nothing
( Imported ( ModuleName "Golden.RecGroupOrder.Test" ) ( Name "store" ) ) 0
)
( Abs Nothing ( ParamUnused Nothing )
( ObjectProp Nothing
( App Nothing
( Ref Nothing ( Local ( Name "Lazy_record" ) ) 0 )
( LiteralInt Nothing 0 )
)
( PropName "tag" )
)
)
)
)
) :|
[
( Nothing, Name "record", App Nothing
( Ref Nothing ( Local ( Name "Lazy_record" ) ) 0 )
( LiteralInt Nothing 0 )
)
]
) :| []
)
( App Nothing
( ObjectProp ( Just Always )
( ForeignImport Nothing
( ModuleName "Effect.Console" ) ".spago/p/console/f82835a0b873aafe6bd7b14dd30cc150553d4ab9/src/Effect/Console.purs"
[ ( Nothing, Name "log" ) ]
)
( PropName "log" )
)
( App Nothing
( ObjectProp Nothing ( Ref Nothing ( Local ( Name "record" ) ) 0 ) ( PropName "run" ) )
( ObjectProp ( Just Always )
( ForeignImport Nothing
( ModuleName "Data.Unit" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Unit.purs"
[ ( Just Always, Name "unit" ) ]
)
( PropName "unit" )
)
)
)
)
]
}
35 changes: 35 additions & 0 deletions test/ps/output/Golden.RecGroupOrder.Test/golden.lua
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,35 @@
local function PSLUA_runtime_lazy(name)
return function(init)
local state = 0
local val = nil
return function()
if state == 2 then
return val
else
if state == 1 then
return error(name .. " was needed before it finished initializing")
else
state = 1
val = init()
state = 2
return val
end
end
end
end
end
local M = {}
M.Golden_RecGroupOrder_Test_store = function(f)
return { run = f, tag = "ok!" }
end
return (function()
local Lazy_record
local record
Lazy_record = PSLUA_runtime_lazy("record")(function()
return M.Golden_RecGroupOrder_Test_store(function()
return (Lazy_record(0)).tag
end)
end)
record = Lazy_record(0)
return (function(s) return function() print(s) end end)(record.run({}))
end)()()
32 changes: 16 additions & 16 deletions test/ps/output/Golden.RecursiveBindings.Test/golden.ir
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,38 +4,38 @@ UberModule
( Name "letRec", Let Nothing
( RecursiveGroup
(
( Nothing, Name "no", Abs Nothing
( Nothing, Name "yes", Abs Nothing
( ParamNamed Nothing ( Name "v" ) )
( IfThenElse Nothing
( Ref Nothing ( Local ( Name "v" ) ) 0 )
( App Nothing
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing False )
)
( IfThenElse Nothing
( Eq Nothing ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "v" ) ) 0 )
)
( App Nothing
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing True )
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing True )
)
( Exception Nothing "No patterns matched" )
)
)
) :|
[
( Nothing, Name "yes", Abs Nothing
( Nothing, Name "no", Abs Nothing
( ParamNamed Nothing ( Name "v" ) )
( IfThenElse Nothing
( Ref Nothing ( Local ( Name "v" ) ) 0 )
( App Nothing
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing False )
)
( IfThenElse Nothing
( Eq Nothing ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "v" ) ) 0 )
)
( App Nothing
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing True )
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing True )
)
( Exception Nothing "No patterns matched" )
)
Expand All @@ -49,38 +49,38 @@ UberModule
( Name "whereRec", Let Nothing
( RecursiveGroup
(
( Nothing, Name "no", Abs Nothing
( Nothing, Name "yes", Abs Nothing
( ParamNamed Nothing ( Name "v" ) )
( IfThenElse Nothing
( Ref Nothing ( Local ( Name "v" ) ) 0 )
( App Nothing
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing False )
)
( IfThenElse Nothing
( Eq Nothing ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "v" ) ) 0 )
)
( App Nothing
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing True )
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing True )
)
( Exception Nothing "No patterns matched" )
)
)
) :|
[
( Nothing, Name "yes", Abs Nothing
( Nothing, Name "no", Abs Nothing
( ParamNamed Nothing ( Name "v" ) )
( IfThenElse Nothing
( Ref Nothing ( Local ( Name "v" ) ) 0 )
( App Nothing
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing False )
)
( IfThenElse Nothing
( Eq Nothing ( LiteralBool Nothing False )
( Ref Nothing ( Local ( Name "v" ) ) 0 )
)
( App Nothing
( Ref Nothing ( Local ( Name "no" ) ) 0 ) ( LiteralBool Nothing True )
( Ref Nothing ( Local ( Name "yes" ) ) 0 ) ( LiteralBool Nothing True )
)
( Exception Nothing "No patterns matched" )
)
Expand All @@ -96,16 +96,16 @@ UberModule
( Nothing, Name "z", LiteralInt Nothing 1 ) :|
[ RecursiveGroup
(
( Nothing, Name "a", Abs Nothing ( ParamUnused Nothing )
( Nothing, Name "b", Abs Nothing ( ParamUnused Nothing )
( App Nothing
( Ref Nothing ( Local ( Name "b" ) ) 0 )
( Ref Nothing ( Local ( Name "a" ) ) 0 )
( Ref Nothing ( Local ( Name "z" ) ) 0 )
)
) :|
[
( Nothing, Name "b", Abs Nothing ( ParamUnused Nothing )
( Nothing, Name "a", Abs Nothing ( ParamUnused Nothing )
( App Nothing
( Ref Nothing ( Local ( Name "a" ) ) 0 )
( Ref Nothing ( Local ( Name "b" ) ) 0 )
( Ref Nothing ( Local ( Name "z" ) ) 0 )
)
)
Expand Down
Loading
Loading