GitLab

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

 +{-# 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

 +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

 +test('determ026',
 +     [extra_files(['A.hs']), req_th],
 +     makefile_test, ['determ026'])