Simon Jakobi pushed to branch wip/sjakobi/T27459 at Glasgow Haskell Compiler / GHC Commits: 125d9c16 by Simon Jakobi at 2026-08-22T17:03:19+02:00 Sort the unifiers in getCoherentUnifiers Enumerating the unifiers non-deterministically (62cc6594f5e) exposed unique-dependent instance order to every consumer of the full list. The error-message sites re-sort for display, but Template Haskell's reifyInstances (and lookupThInstName) passed the list on unsorted, so a splice reifying instances at a type variable could generate code in unique-dependent order — an ABI-relevant leak. Sort in getCoherentUnifiers itself, so every external consumer gets a deterministic order. The internal construction sites keep the lazy, unsorted list via the unexported nonDetCoherentUnifiers. See Note [Matches vs Unifiers] in GHC.Core.RoughMap. Also add determ026, which reifies the Show instances at a type variable under two different unique supplies and compares the output. It fails without the sort. Context: #27459 Assisted-by: Claude Fable 5 - - - - - 5 changed files: - compiler/GHC/Core/InstEnv.hs - compiler/GHC/Core/RoughMap.hs - + testsuite/tests/determinism/determ026/A.hs - + testsuite/tests/determinism/determ026/Makefile - + testsuite/tests/determinism/determ026/all.T Changes: ===================================== compiler/GHC/Core/InstEnv.hs ===================================== @@ -53,6 +53,8 @@ import GHC.Types.Name import GHC.Types.Name.Set import GHC.Types.Id import GHC.Generics (Generic) +import Data.Function ( on ) +import Data.List ( sortBy ) import Data.List.NonEmpty ( NonEmpty (..), nonEmpty ) import qualified Data.List.NonEmpty as NE import Data.Maybe ( isJust ) @@ -1122,6 +1124,9 @@ data PotentialUnifiers -- printing an error message. It can be expensive to compute all -- the unifiers because if you are matching something like C a[sk] then -- all instances will unify. + -- CQ-REF[coherent-unifiers-sort] + -- D~ "when printing an error message" is incomplete: TH's + -- reifyInstances also consumes the full list. {- Note [Recording coherence information in `PotentialUnifiers`] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -1167,11 +1172,24 @@ instance Semigroup PotentialUnifiers where NoUnifiers c1 <> NoUnifiers c2 = NoUnifiers (c1 `andCanEv` c2) NoUnifiers _ <> u = u OneOrMoreUnifiers (unifier :| unifiers) <> u - = OneOrMoreUnifiers (unifier :| (unifiers <> getCoherentUnifiers u)) - + = OneOrMoreUnifiers (unifier :| (unifiers <> nonDetCoherentUnifiers u)) + +-- CQ[coherent-unifiers-sort] +-- Q: Why does the exported accessor sort, and why is there a raw +-- (non-deterministic, unexported) variant? +-- A~ The unifiers are enumerated in non-deterministic order (see +-- Note [Matches vs Unifiers] in GHC.Core.RoughMap). Sorting here makes +-- the order deterministic for every external consumer (error messages, +-- TH's reifyInstances). The internal construction sites (the Semigroup +-- instance, add_unifier) must use the raw variant: they build the list +-- incrementally, and sorting a partial list would both be wasted work +-- and force the lazily-enumerated tail. getCoherentUnifiers :: PotentialUnifiers -> [ClsInst] -getCoherentUnifiers NoUnifiers{} = [] -getCoherentUnifiers (OneOrMoreUnifiers cls) = NE.toList cls +getCoherentUnifiers = sortBy (stableNameCmp `on` is_dfun_name) . nonDetCoherentUnifiers + +nonDetCoherentUnifiers :: PotentialUnifiers -> [ClsInst] +nonDetCoherentUnifiers NoUnifiers{} = [] +nonDetCoherentUnifiers (OneOrMoreUnifiers cls) = NE.toList cls -- | Are there no *coherent* unifiers? nullUnifiers :: PotentialUnifiers -> Bool @@ -1262,7 +1280,7 @@ instEnvMatchesAndUnifiers (InstEnv rm) vis_mods cls tys -- Note [Coherence and specialisation: overview] add_unifier item other_unifiers | not (isIncoherent item) - = OneOrMoreUnifiers (item :| getCoherentUnifiers other_unifiers) + = OneOrMoreUnifiers (item :| nonDetCoherentUnifiers other_unifiers) -- So `item` is incoherent; see Note [Incoherent instances] | otherwise ===================================== compiler/GHC/Core/RoughMap.hs ===================================== @@ -172,12 +172,19 @@ For the same reason the unifiers are enumerated in non-deterministic order (see the RML_WildCard case of lookupRM'): a deterministic fold would have to inspect every entry of rm_known before it could produce the first unifier, defeating that laziness (#27459; see Note [Cost of deterministic iteration] in -GHC.Types.Unique.DFM). The order is observable only where error messages are -rendered, so those sites must sort the unifiers they display; see -fuzzyClsInstCmp in GHC.Core.InstEnv and reportConflictInstErr in -GHC.Tc.Instance.Family. The matches, by contrast, are still enumerated +GHC.Types.Unique.DFM). The matches, by contrast, are still enumerated deterministically. +CQ[unifier-order-consumers] +Q: Where does the non-deterministic unifier order become user-visible, and + who restores determinism? +A~ Wherever the full list is consumed: class-instance consumers (error + messages, TH's reifyInstances — see #27459 review finding) all go through + getCoherentUnifiers in GHC.Core.InstEnv, which sorts; family-instance + conflicts are sorted where displayed, see reportConflictInstErr in + GHC.Tc.Instance.Family. Consumers that only test emptiness (the hot + paths) never observe the order. + Note [Simple Matching Semantics] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose `rm` is a RoughMap representing a set of (key,vals) pairs, ===================================== testsuite/tests/determinism/determ026/A.hs ===================================== @@ -0,0 +1,24 @@ +{-# LANGUAGE TemplateHaskell #-} +module A where + +-- reifyInstances at a bare type variable returns the unifying instances, +-- whose order must not depend on the order of Uniques (#27459). +-- +-- The printed heads avoid pprint/show of anything containing a NameU: +-- those embed uniques and would differ between the two runs regardless +-- of instance order. + +import Language.Haskell.TH + +$(do let headName :: Type -> String + headName (AppT f _) = headName f + headName (ConT n) = show n + headName ListT = "[]" + headName (TupleT i) = "Tuple" ++ show i + headName ArrowT = "->" + headName _ = "<other-type>" + instHead (InstanceD _ _ (AppT _ arg) _) = headName arg + instHead _ = "<other-dec>" + insts <- reifyInstances ''Show [VarT (mkName "a")] + runIO (mapM_ (putStrLn . instHead) insts) + return []) ===================================== testsuite/tests/determinism/determ026/Makefile ===================================== @@ -0,0 +1,13 @@ +TOP=../../.. +include $(TOP)/mk/boilerplate.mk +include $(TOP)/mk/test.mk + +# Check that the instance order returned by TH's reifyInstances doesn't +# depend on the order of Uniques (#27459): run a splice that prints the +# instances with two unique supplies and compare the output. +determ026: + $(RM) A.hi A.o + '$(TEST_HC)' $(TEST_HC_OPTS) -v0 -dinitial-unique=0 -dunique-increment=1 A.hs > A.out.normal + $(RM) A.hi A.o + '$(TEST_HC)' $(TEST_HC_OPTS) -v0 -dinitial-unique=16777215 -dunique-increment=-1 A.hs > A.out.reversed + diff A.out.normal A.out.reversed ===================================== testsuite/tests/determinism/determ026/all.T ===================================== @@ -0,0 +1,3 @@ +test('determ026', + [extra_files(['A.hs']), req_th], + makefile_test, ['determ026']) View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/125d9c16c79ebccfb8f516b69c04cca9... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/125d9c16c79ebccfb8f516b69c04cca9... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help