Use UniqDFM for InstEnv

Rationale in the comment.
Also updates submodule array with test output changes.

GHC Trac: #4012

10 files changed, 82 insertions, 67 deletions

diff --git a/compiler/types/InstEnv.hs b/compiler/types/InstEnv.hs
index e214f12a65..a8b5f0f8ff 100644
--- a/compiler/types/InstEnv.hs
+++ b/compiler/types/InstEnv.hs
@@ -41,7 +41,7 @@ import Unify
 import Outputable
 import ErrUtils
 import BasicTypes
-import UniqFM
+import UniqDFM
 import Util
 import Id
 import Data.Data        ( Data )
@@ -330,7 +330,21 @@ or, to put it another way, we have
 -}
 
 ---------------------------------------------------
-type InstEnv = UniqFM ClsInstEnv        -- Maps Class to instances for that class
+{-
+Note [InstEnv determinism]
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+We turn InstEnvs into a list in some places that don't directly affect
+the ABI. That happens when we create output for `:info`.
+Unfortunately that nondeterminism is nonlocal and it's hard to tell what it
+affects without following a chain of functions. It's also easy to accidentally
+make that nondeterminism affect the ABI. Furthermore the envs should be
+relatively small, so it should be free to use deterministic maps here.
+Testing with nofib and validate detected no difference between UniqFM and
+UniqDFM. See also Note [Deterministic UniqFM]
+-}
+
+type InstEnv = UniqDFM ClsInstEnv      -- Maps Class to instances for that class
+  -- See Note [InstEnv determinism]
 
 -- | 'InstEnvs' represents the combination of the global type class instance
 -- environment, the local type class instance environment, and the set of
@@ -365,10 +379,11 @@ instance Outputable ClsInstEnv where
 -- the dfun type.
 
 emptyInstEnv :: InstEnv
-emptyInstEnv = emptyUFM
+emptyInstEnv = emptyUDFM
 
 instEnvElts :: InstEnv -> [ClsInst]
-instEnvElts ie = [elt | ClsIE elts <- eltsUFM ie, elt <- elts]
+instEnvElts ie = [elt | ClsIE elts <- eltsUDFM ie, elt <- elts]
+  -- See Note [InstEnv determinism]
 
 -- | Test if an instance is visible, by checking that its origin module
 -- is in 'VisibleOrphanModules'.
@@ -388,7 +403,7 @@ classInstances :: InstEnvs -> Class -> [ClsInst]
 classInstances (InstEnvs { ie_global = pkg_ie, ie_local = home_ie, ie_visible = vis_mods }) cls
   = get home_ie ++ get pkg_ie
   where
-    get env = case lookupUFM env cls of
+    get env = case lookupUDFM env cls of
                 Just (ClsIE insts) -> filter (instIsVisible vis_mods) insts
                 Nothing            -> []
 
@@ -397,20 +412,20 @@ classInstances (InstEnvs { ie_global = pkg_ie, ie_local = home_ie, ie_visible =
 memberInstEnv :: InstEnv -> ClsInst -> Bool
 memberInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm } ) =
     maybe False (\(ClsIE items) -> any (identicalClsInstHead ins_item) items)
-          (lookupUFM inst_env cls_nm)
+          (lookupUDFM inst_env cls_nm)
 
 extendInstEnvList :: InstEnv -> [ClsInst] -> InstEnv
 extendInstEnvList inst_env ispecs = foldl extendInstEnv inst_env ispecs
 
 extendInstEnv :: InstEnv -> ClsInst -> InstEnv
 extendInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
-  = addToUFM_C add inst_env cls_nm (ClsIE [ins_item])
+  = addToUDFM_C add inst_env cls_nm (ClsIE [ins_item])
   where
     add (ClsIE cur_insts) _ = ClsIE (ins_item : cur_insts)
 
 deleteFromInstEnv :: InstEnv -> ClsInst -> InstEnv
 deleteFromInstEnv inst_env ins_item@(ClsInst { is_cls_nm = cls_nm })
-  = adjustUFM adjust inst_env cls_nm
+  = adjustUDFM adjust inst_env cls_nm
   where
     adjust (ClsIE items) = ClsIE (filterOut (identicalClsInstHead ins_item) items)
 
@@ -702,7 +717,7 @@ lookupInstEnv' ie vis_mods cls tys
     all_tvs    = all isNothing rough_tcs
 
     --------------
-    lookup env = case lookupUFM env cls of
+    lookup env = case lookupUDFM env cls of
                    Nothing -> ([],[])   -- No instances for this class
                    Just (ClsIE insts) -> find [] [] insts
 
diff --git a/libraries/array b/libraries/array
-Subproject 6026ba0e6e94e5199e6c678a8e2110ed43fc1a5
+Subproject 049db4ac25dd8d21b3a1bba6fe6dfab05d0e3d4
diff --git a/testsuite/tests/ghci/scripts/T4175.stdout b/testsuite/tests/ghci/scripts/T4175.stdout
index f76feb6194..d96a2ef9eb 100644
--- a/testsuite/tests/ghci/scripts/T4175.stdout
+++ b/testsuite/tests/ghci/scripts/T4175.stdout
@@ -18,37 +18,37 @@ type family E a :: *
   	-- Defined at T4175.hs:24:1
 data () = () 	-- Defined in ‘GHC.Tuple’
 instance C () -- Defined at T4175.hs:21:10
+instance Monoid () -- Defined in ‘GHC.Base’
 instance Bounded () -- Defined in ‘GHC.Enum’
 instance Enum () -- Defined in ‘GHC.Enum’
+instance Read () -- Defined in ‘GHC.Read’
 instance Eq () -- Defined in ‘GHC.Classes’
 instance Ord () -- Defined in ‘GHC.Classes’
-instance Read () -- Defined in ‘GHC.Read’
 instance Show () -- Defined in ‘GHC.Show’
-instance Monoid () -- Defined in ‘GHC.Base’
 type instance D () a = Bool 	-- Defined at T4175.hs:22:10
 data instance B () = MkB 	-- Defined at T4175.hs:13:15
 data Maybe a = Nothing | Just a 	-- Defined in ‘GHC.Base’
-instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Base’
-instance Monad Maybe -- Defined in ‘GHC.Base’
-instance Functor Maybe -- Defined in ‘GHC.Base’
-instance Ord a => Ord (Maybe a) -- Defined in ‘GHC.Base’
-instance Read a => Read (Maybe a) -- Defined in ‘GHC.Read’
-instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’
-instance Applicative Maybe -- Defined in ‘GHC.Base’
 instance Foldable Maybe -- Defined in ‘Data.Foldable’
 instance Traversable Maybe -- Defined in ‘Data.Traversable’
 instance Monoid a => Monoid (Maybe a) -- Defined in ‘GHC.Base’
+instance Read a => Read (Maybe a) -- Defined in ‘GHC.Read’
+instance Applicative Maybe -- Defined in ‘GHC.Base’
+instance Functor Maybe -- Defined in ‘GHC.Base’
+instance Monad Maybe -- Defined in ‘GHC.Base’
+instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Base’
+instance Ord a => Ord (Maybe a) -- Defined in ‘GHC.Base’
+instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’
 type instance A (Maybe a) a = a 	-- Defined at T4175.hs:9:15
 data Int = I# Int# 	-- Defined in ‘GHC.Types’
 instance C Int -- Defined at T4175.hs:18:10
+instance Integral Int -- Defined in ‘GHC.Real’
+instance Num Int -- Defined in ‘GHC.Num’
+instance Real Int -- Defined in ‘GHC.Real’
 instance Bounded Int -- Defined in ‘GHC.Enum’
 instance Enum Int -- Defined in ‘GHC.Enum’
+instance Read Int -- Defined in ‘GHC.Read’
 instance Eq Int -- Defined in ‘GHC.Classes’
-instance Integral Int -- Defined in ‘GHC.Real’
-instance Num Int -- Defined in ‘GHC.Num’
 instance Ord Int -- Defined in ‘GHC.Classes’
-instance Read Int -- Defined in ‘GHC.Read’
-instance Real Int -- Defined in ‘GHC.Real’
 instance Show Int -- Defined in ‘GHC.Show’
 type instance D Int b = String 	-- Defined at T4175.hs:19:10
 type instance A Int Int = () 	-- Defined at T4175.hs:8:15
diff --git a/testsuite/tests/ghci/scripts/T7627.stdout b/testsuite/tests/ghci/scripts/T7627.stdout
index 2dfae3749f..b577bdf403 100644
--- a/testsuite/tests/ghci/scripts/T7627.stdout
+++ b/testsuite/tests/ghci/scripts/T7627.stdout
@@ -1,30 +1,30 @@
 data () = () 	-- Defined in ‘GHC.Tuple’
+instance Monoid () -- Defined in ‘GHC.Base’
 instance Bounded () -- Defined in ‘GHC.Enum’
+instance Read () -- Defined in ‘GHC.Read’
 instance Enum () -- Defined in ‘GHC.Enum’
+instance Show () -- Defined in ‘GHC.Show’
 instance Eq () -- Defined in ‘GHC.Classes’
 instance Ord () -- Defined in ‘GHC.Classes’
-instance Read () -- Defined in ‘GHC.Read’
-instance Show () -- Defined in ‘GHC.Show’
-instance Monoid () -- Defined in ‘GHC.Base’
 data (##) = (##) 	-- Defined in ‘GHC.Prim’
 () :: ()
 (##) :: (# #)
 (   ) :: ()
 (#   #) :: (# #)
 data (,) a b = (,) a b 	-- Defined in ‘GHC.Tuple’
+instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
+instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
+instance (Monoid a, Monoid b) => Monoid (a, b)
+  -- Defined in ‘GHC.Base’
 instance (Bounded a, Bounded b) => Bounded (a, b)
   -- Defined in ‘GHC.Enum’
 instance (Eq a, Eq b) => Eq (a, b) -- Defined in ‘GHC.Classes’
-instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
-instance Functor ((,) a) -- Defined in ‘GHC.Base’
 instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
 instance (Read a, Read b) => Read (a, b) -- Defined in ‘GHC.Read’
 instance (Show a, Show b) => Show (a, b) -- Defined in ‘GHC.Show’
 instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
-instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
-instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
-instance (Monoid a, Monoid b) => Monoid (a, b)
-  -- Defined in ‘GHC.Base’
+instance Functor ((,) a) -- Defined in ‘GHC.Base’
+instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
 data (#,#) (a :: TYPE k0) (b :: TYPE k1) = (#,#) a b
   	-- Defined in ‘GHC.Prim’
 (,) :: a -> b -> (a, b)
diff --git a/testsuite/tests/ghci/scripts/T8469.stdout b/testsuite/tests/ghci/scripts/T8469.stdout
index cd7966ee66..0bbaaedfbe 100644
--- a/testsuite/tests/ghci/scripts/T8469.stdout
+++ b/testsuite/tests/ghci/scripts/T8469.stdout
@@ -1,10 +1,10 @@
 data Int = GHC.Types.I# GHC.Prim.Int# 	-- Defined in ‘GHC.Types’
 instance Bounded Int -- Defined in ‘GHC.Enum’
+instance Read Int -- Defined in ‘GHC.Read’
 instance Enum Int -- Defined in ‘GHC.Enum’
-instance Eq Int -- Defined in ‘GHC.Classes’
 instance Integral Int -- Defined in ‘GHC.Real’
 instance Num Int -- Defined in ‘GHC.Num’
-instance Ord Int -- Defined in ‘GHC.Classes’
-instance Read Int -- Defined in ‘GHC.Read’
 instance Real Int -- Defined in ‘GHC.Real’
 instance Show Int -- Defined in ‘GHC.Show’
+instance Eq Int -- Defined in ‘GHC.Classes’
+instance Ord Int -- Defined in ‘GHC.Classes’
diff --git a/testsuite/tests/ghci/scripts/T8535.stdout b/testsuite/tests/ghci/scripts/T8535.stdout
index 2f35e23a77..7245bf2d3d 100644
--- a/testsuite/tests/ghci/scripts/T8535.stdout
+++ b/testsuite/tests/ghci/scripts/T8535.stdout
@@ -1,6 +1,6 @@
 data (->) a b 	-- Defined in ‘GHC.Prim’
 infixr 0 `(->)`
-instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Functor ((->) r) -- Defined in ‘GHC.Base’
-instance Applicative ((->) a) -- Defined in ‘GHC.Base’
 instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Applicative ((->) a) -- Defined in ‘GHC.Base’
+instance Functor ((->) r) -- Defined in ‘GHC.Base’
+instance Monad ((->) r) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/scripts/T9881.stdout b/testsuite/tests/ghci/scripts/T9881.stdout
index 6866a6a79c..a73f0e8fb8 100644
--- a/testsuite/tests/ghci/scripts/T9881.stdout
+++ b/testsuite/tests/ghci/scripts/T9881.stdout
@@ -3,15 +3,15 @@ data Data.ByteString.Lazy.ByteString
   | Data.ByteString.Lazy.Internal.Chunk {-# UNPACK #-}Data.ByteString.ByteString
                                         Data.ByteString.Lazy.ByteString
   	-- Defined in ‘Data.ByteString.Lazy.Internal’
-instance Eq Data.ByteString.Lazy.ByteString
-  -- Defined in ‘Data.ByteString.Lazy.Internal’
-instance Ord Data.ByteString.Lazy.ByteString
+instance Monoid Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
 instance Read Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
 instance Show Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
-instance Monoid Data.ByteString.Lazy.ByteString
+instance Eq Data.ByteString.Lazy.ByteString
+  -- Defined in ‘Data.ByteString.Lazy.Internal’
+instance Ord Data.ByteString.Lazy.ByteString
   -- Defined in ‘Data.ByteString.Lazy.Internal’
 
 data Data.ByteString.ByteString
@@ -20,13 +20,13 @@ data Data.ByteString.ByteString
                                 {-# UNPACK #-}Int
                                 {-# UNPACK #-}Int
   	-- Defined in ‘Data.ByteString.Internal’
-instance Eq Data.ByteString.ByteString
-  -- Defined in ‘Data.ByteString.Internal’
-instance Ord Data.ByteString.ByteString
+instance Monoid Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
 instance Read Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
 instance Show Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
-instance Monoid Data.ByteString.ByteString
+instance Eq Data.ByteString.ByteString
+  -- Defined in ‘Data.ByteString.Internal’
+instance Ord Data.ByteString.ByteString
   -- Defined in ‘Data.ByteString.Internal’
diff --git a/testsuite/tests/ghci/scripts/ghci011.stdout b/testsuite/tests/ghci/scripts/ghci011.stdout
index 8042757541..0bffb9720c 100644
--- a/testsuite/tests/ghci/scripts/ghci011.stdout
+++ b/testsuite/tests/ghci/scripts/ghci011.stdout
@@ -1,33 +1,33 @@
 data [] a = [] | a : [a] 	-- Defined in ‘GHC.Types’
-instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
-instance Monad [] -- Defined in ‘GHC.Base’
-instance Functor [] -- Defined in ‘GHC.Base’
-instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
+instance Monoid [a] -- Defined in ‘GHC.Base’
+instance Foldable [] -- Defined in ‘Data.Foldable’
+instance Traversable [] -- Defined in ‘Data.Traversable’
 instance Read a => Read [a] -- Defined in ‘GHC.Read’
 instance Show a => Show [a] -- Defined in ‘GHC.Show’
 instance Applicative [] -- Defined in ‘GHC.Base’
-instance Foldable [] -- Defined in ‘Data.Foldable’
-instance Traversable [] -- Defined in ‘Data.Traversable’
-instance Monoid [a] -- Defined in ‘GHC.Base’
+instance Functor [] -- Defined in ‘GHC.Base’
+instance Monad [] -- Defined in ‘GHC.Base’
+instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
+instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
 data () = () 	-- Defined in ‘GHC.Tuple’
+instance Monoid () -- Defined in ‘GHC.Base’
+instance Read () -- Defined in ‘GHC.Read’
 instance Bounded () -- Defined in ‘GHC.Enum’
 instance Enum () -- Defined in ‘GHC.Enum’
-instance Eq () -- Defined in ‘GHC.Classes’
 instance Ord () -- Defined in ‘GHC.Classes’
-instance Read () -- Defined in ‘GHC.Read’
 instance Show () -- Defined in ‘GHC.Show’
-instance Monoid () -- Defined in ‘GHC.Base’
+instance Eq () -- Defined in ‘GHC.Classes’
 data (,) a b = (,) a b 	-- Defined in ‘GHC.Tuple’
+instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
+instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
+instance (Monoid a, Monoid b) => Monoid (a, b)
+  -- Defined in ‘GHC.Base’
 instance (Bounded a, Bounded b) => Bounded (a, b)
   -- Defined in ‘GHC.Enum’
 instance (Eq a, Eq b) => Eq (a, b) -- Defined in ‘GHC.Classes’
-instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
-instance Functor ((,) a) -- Defined in ‘GHC.Base’
 instance (Ord a, Ord b) => Ord (a, b) -- Defined in ‘GHC.Classes’
 instance (Read a, Read b) => Read (a, b) -- Defined in ‘GHC.Read’
 instance (Show a, Show b) => Show (a, b) -- Defined in ‘GHC.Show’
 instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
-instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
-instance Traversable ((,) a) -- Defined in ‘Data.Traversable’
-instance (Monoid a, Monoid b) => Monoid (a, b)
-  -- Defined in ‘GHC.Base’
+instance Functor ((,) a) -- Defined in ‘GHC.Base’
+instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/scripts/ghci020.stdout b/testsuite/tests/ghci/scripts/ghci020.stdout
index 2f35e23a77..7245bf2d3d 100644
--- a/testsuite/tests/ghci/scripts/ghci020.stdout
+++ b/testsuite/tests/ghci/scripts/ghci020.stdout
@@ -1,6 +1,6 @@
 data (->) a b 	-- Defined in ‘GHC.Prim’
 infixr 0 `(->)`
-instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Functor ((->) r) -- Defined in ‘GHC.Base’
-instance Applicative ((->) a) -- Defined in ‘GHC.Base’
 instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Applicative ((->) a) -- Defined in ‘GHC.Base’
+instance Functor ((->) r) -- Defined in ‘GHC.Base’
+instance Monad ((->) r) -- Defined in ‘GHC.Base’
diff --git a/testsuite/tests/ghci/should_run/T10145.stdout b/testsuite/tests/ghci/should_run/T10145.stdout
index 2f35e23a77..7245bf2d3d 100644
--- a/testsuite/tests/ghci/should_run/T10145.stdout
+++ b/testsuite/tests/ghci/should_run/T10145.stdout
@@ -1,6 +1,6 @@
 data (->) a b 	-- Defined in ‘GHC.Prim’
 infixr 0 `(->)`
-instance Monad ((->) r) -- Defined in ‘GHC.Base’
-instance Functor ((->) r) -- Defined in ‘GHC.Base’
-instance Applicative ((->) a) -- Defined in ‘GHC.Base’
 instance Monoid b => Monoid (a -> b) -- Defined in ‘GHC.Base’
+instance Applicative ((->) a) -- Defined in ‘GHC.Base’
+instance Functor ((->) r) -- Defined in ‘GHC.Base’
+instance Monad ((->) r) -- Defined in ‘GHC.Base’