GitLab

Simon Jakobi pushed to branch wip/sjakobi/T27459 at Glasgow Haskell Compiler / GHC

Commits:

449e126a

by Simon Jakobi at 2026-08-13T10:05:41+02:00

Enumerate RoughMap unifiers non-deterministically

The wildcard case of lookupRM' enumerated potential unifiers with a
deterministic fold, which must inspect every entry of rm_known before
producing the first element. This defeats the laziness that
Note [Matches vs Unifiers] relies on: hot consumers such as matchInstEnv
only test whether the unifier list is empty, yet paid for deterministic
iteration over the whole map (#27459).

Enumerate the unifiers with a new lazy nonDetFoldUDFM instead, so the
emptiness test can stop at the first unifier. Matches are still
enumerated deterministically. Unifier order is now restored at the
error-rendering sites: class-instance overlap errors already sort with
fuzzyClsInstCmp, and reportConflictInstErr now picks the reported
conflict deterministically. See Note [Matches vs Unifiers].

-------------------------
Metric Decrease:
    InstanceMatching
    InstanceMatching1

Assisted-by: Claude Fable 5

4 changed files:

compiler/GHC/Core/RoughMap.hs
compiler/GHC/Tc/Instance/Family.hs
compiler/GHC/Types/Name/Env.hs
compiler/GHC/Types/Unique/DFM.hs

Changes:

compiler/GHC/Core/RoughMap.hs

@@ -168,6 +168,16 @@ each candidate. We only need the full list of unifiers when displaying error mes
  Therefore the list is computed lazily so much work can be avoided constructing the
  list in the first place.
 +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
 +deterministically.
++
  Note [Simple Matching Semantics]
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Suppose `rm` is a RoughMap representing a set of (key,vals) pairs,
@@ -420,15 +430,18 @@ lookupRM' (RML_NoKnownTc : tcs) rm =
  lookupRM' (RML_WildCard : tcs)    rm  =
  --  pprTrace "RM wild" (ppr tcs $$ ppr (eltsDNameEnv (rm_known rm))) $
 -  let (m, u)     = foldDNameEnv add_one (emptyBag, []) (rm_known rm)
 +  let m = foldDNameEnv (\rm' acc -> fst (lookupRM' tcs rm') `unionBags` acc)
 +                       emptyBag (rm_known rm)
 +      -- The unifiers are enumerated non-deterministically: hot consumers
 +      -- only test whether the list is empty, and the lazy fold lets that
 +      -- test stop at the first unifier instead of paying for deterministic
 +      -- iteration over the whole map (#27459).
 +      -- See Note [Matches vs Unifiers].
 +      u = nonDetFoldDNameEnv (\rm' acc -> snd (lookupRM' tcs rm') ++ acc)
 +                             [] (rm_known rm)
        (u_m, u_u) = lookupRM' tcs (rm_wild rm)
    in ( rm_empty rm `unionBags` u_m `unionBags` m
       , bagToList (rm_empty rm) ++ u_u ++ u )
 -  where
 -     add_one :: RoughMap a -> (Bag a, [a]) -> (Bag a, [a])
 -     add_one rm ~(m2, u2) = (m1 `unionBags` m2, u1 ++ u2)
 -                          where
 -                            (m1,u1) = lookupRM' tcs rm
  unionRM :: RoughMap a -> RoughMap a -> RoughMap a
  unionRM RMEmpty a = a

compiler/GHC/Tc/Instance/Family.hs

@@ -939,11 +939,18 @@ buildInjectivityError mkErr fam_tc branches
  reportConflictInstErr :: FamInst -> [FamInst] -> TcRn ()
  reportConflictInstErr _ []
    = return ()  -- No conflicts
 -reportConflictInstErr fam_inst (conf_inst : _) =
 +reportConflictInstErr fam_inst (conf_inst1 : conf_insts) =
 +   -- The conflicts are enumerated in non-deterministic order (see
 +   -- Note [Matches vs Unifiers] in GHC.Core.RoughMap), so pick the one to
 +   -- report deterministically.
     -- The sortBy just arranges that instances are displayed in order
     -- of source location, which reduced wobbling in error messages,
     -- and is better for users
 -  let   sorted  = NE.sortBy (SrcLoc.leftmost_smallest `on` getSpan) (fam_inst NE.:| [conf_inst])
 +  let   conf_inst = minimumBy cmp_inst (conf_inst1 :| conf_insts)
 +        cmp_inst f1 f2 = case (SrcLoc.leftmost_smallest `on` getSpan) f1 f2 of
 +                           EQ -> (stableNameCmp `on` (getName . famInstAxiom)) f1 f2
 +                           o  -> o
 +        sorted  = NE.sortBy (SrcLoc.leftmost_smallest `on` getSpan) (fam_inst NE.:| [conf_inst])
          fi1     = NE.head sorted
          span    = coAxBranchSpan (coAxiomSingleBranch (famInstAxiom fi1))
          getSpan = getSrcSpan . famInstAxiom

compiler/GHC/Types/Name/Env.hs

@@ -40,6 +40,7 @@ module GHC.Types.Name.Env (
          plusDNameEnv_C,
          foldDNameEnv,
          nonDetStrictFoldDNameEnv,
 +        nonDetFoldDNameEnv,
          -- ** Dependency analysis
          depAnal
      ) where
@@ -224,3 +225,7 @@ plusDNameEnv_C = plusUDFM_C
  nonDetStrictFoldDNameEnv :: (a -> b -> b) -> b -> DNameEnv a -> b
  nonDetStrictFoldDNameEnv = nonDetStrictFoldUDFM
 +-- | Lazy nondeterministic fold; can stream and short-circuit.
 +nonDetFoldDNameEnv :: (a -> b -> b) -> b -> DNameEnv a -> b
 +nonDetFoldDNameEnv = nonDetFoldUDFM
++

compiler/GHC/Types/Unique/DFM.hs

@@ -66,6 +66,7 @@ module GHC.Types.Unique.DFM (
          udfmToList,
          udfmToUfm,
          nonDetStrictFoldUDFM,
 +        nonDetFoldUDFM,
          unsafeCastUDFMKey,
          alwaysUnsafeUfmToUdfm,
      ) where
@@ -378,6 +379,15 @@ nonDetStrictFoldUDFM k z (UDFM m _i) = foldl' k' z m
    where
      k' acc (TaggedVal v _) = k v acc
 +-- | Performs a nondeterministic lazy right fold over the UniqDFM.
 +-- It's O(n), and lazy in the accumulator, so unlike 'foldUDFM' it can
 +-- stream and short-circuit; see Note [Cost of deterministic iteration].
 +-- If you use this please provide a justification why it doesn't introduce
 +-- nondeterminism.
 +nonDetFoldUDFM :: (elt -> a -> a) -> a -> UniqDFM key elt -> a
 +{-# INLINE nonDetFoldUDFM #-}
 +nonDetFoldUDFM k z (UDFM m _i) = M.foldr (k . taggedFst) z m
++
  {- Note [Cost of deterministic iteration]
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Deterministic iteration -- foldUDFM, eltsUDFM, udfmToList, and everything
@@ -392,7 +402,8 @@ whether the result was non-empty.
  So: to test for emptiness, use isNullUDFM rather than null on eltsUDFM;
  for order-oblivious queries, prefer short-circuiting anyUDFM/allUDFM; and
 -if you don't need the deterministic order at all, use nonDetStrictFoldUDFM.
 +if you don't need the deterministic order at all, use nonDetStrictFoldUDFM
 +(or nonDetFoldUDFM when the fold should stream or short-circuit).
  -}
  -- | Deterministic, in order of insertion.