ed6b480a
by Simon Jakobi at 2026-10-08T23:12:37+02:00
Rename: Build every HsGroup list in source order in findSplice
Since 24e89c40b77 replaced the Bag of bindings with a list, add_bind
appended each top-level binding with `bs ++ [VbBind b]`. For a module
with n top-level bindings that is O(n^2) allocation, and the n-deep
chain of thunks needs O(n) stack to force (#27804).
findSplice now walks the declarations once, accumulating the group's
prefix in reverse, and then conses each declaration onto its list with
a strict fold. Every list in the HsGroup ends up in source order with
O(1) work per declaration and constant stack. Previously the bindings
were in source order and all other lists reversed.
The order of the bindings matters: the specialiser, CSE and error
recovery all follow it, and tests such as T21848, T9441a and
T26098_local change behaviour when it is reversed. The order of the
other lists only decides which of several duplicate declarations an
error points at, the order of dumps and splices, and unique numbering,
which is what the updated expected outputs reflect. One real
difference: reify now lists a class's instances in a different order,
because the instance environment is keyed by insertion order. T11629
hard-coded the old order and now checks membership instead.
On my machine, with a quick-flavour build, bytes allocated for the
ticket's 16000-binding reproducer go from about 68 GB to 46 GB, the
same 22 GB saving the ticket attributes to the append.
Fixes #27804.
Assisted-by: Claude Fable 5.1