Kill varSetElemsWellScoped in quantifyTyVars

varSetElemsWellScoped introduces unnecessary non-determinism in
inferred type signatures.
Removing this instance required changing the representation of
TcDepVars to use deterministic sets.
This is the last occurence of varSetElemsWellScoped, allowing me to
finally remove it.

Test Plan:
./validate
I will update the expected outputs when commiting, some reordering
of type variables in types is expected.

Reviewers: goldfire, simonpj, austin, bgamari

Reviewed By: simonpj

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2135

GHC Trac Issues: #4012

3 files changed, 21 insertions, 4 deletions

diff --git a/compiler/utils/UniqDFM.hs b/compiler/utils/UniqDFM.hs
index c41e00469b..1b3cade93a 100644
--- a/compiler/utils/UniqDFM.hs
+++ b/compiler/utils/UniqDFM.hs
@@ -44,6 +44,7 @@ module UniqDFM (
         intersectsUDFM,
         disjointUDFM,
         minusUDFM,
+        udfmMinusUFM,
         partitionUDFM,
 
         udfmToList,
@@ -59,7 +60,7 @@ import Data.Typeable
 import Data.Data
 import Data.List (sortBy)
 import Data.Function (on)
-import UniqFM (UniqFM, listToUFM_Directly, ufmToList)
+import UniqFM (UniqFM, listToUFM_Directly, ufmToList, ufmToIntMap)
 
 -- Note [Deterministic UniqFM]
 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~
@@ -239,6 +240,11 @@ minusUDFM (UDFM x i) (UDFM y _j) = UDFM (M.difference x y) i
   -- M.difference returns a subset of a left set, so `i` is a good upper
   -- bound.
 
+udfmMinusUFM :: UniqDFM elt1 -> UniqFM elt2 -> UniqDFM elt1
+udfmMinusUFM (UDFM x i) y = UDFM (M.difference x (ufmToIntMap y)) i
+  -- M.difference returns a subset of a left set, so `i` is a good upper
+  -- bound.
+
 -- | Partition UniqDFM into two UniqDFMs according to the predicate
 partitionUDFM :: (elt -> Bool) -> UniqDFM elt -> (UniqDFM elt, UniqDFM elt)
 partitionUDFM p (UDFM m i) =
@@ -283,6 +289,10 @@ alterUDFM f (UDFM m i) k =
 mapUDFM :: (elt1 -> elt2) -> UniqDFM elt1 -> UniqDFM elt2
 mapUDFM f (UDFM m i) = UDFM (M.map (fmap f) m) i
 
+instance Monoid (UniqDFM a) where
+  mempty = emptyUDFM
+  mappend = plusUDFM
+
 -- This should not be used in commited code, provided for convenience to
 -- make ad-hoc conversions when developing
 alwaysUnsafeUfmToUdfm :: UniqFM elt -> UniqDFM elt
diff --git a/compiler/utils/UniqDSet.hs b/compiler/utils/UniqDSet.hs
index 45ed241df1..90e9996d1a 100644
--- a/compiler/utils/UniqDSet.hs
+++ b/compiler/utils/UniqDSet.hs
@@ -19,7 +19,7 @@ module UniqDSet (
         mkUniqDSet,
         addOneToUniqDSet, addListToUniqDSet,
         unionUniqDSets, unionManyUniqDSets,
-        minusUniqDSet,
+        minusUniqDSet, uniqDSetMinusUniqSet,
         intersectUniqDSets,
         intersectsUniqDSets,
         foldUniqDSet,
@@ -33,6 +33,7 @@ module UniqDSet (
     ) where
 
 import UniqDFM
+import UniqSet
 import Unique
 
 type UniqDSet a = UniqDFM a
@@ -65,9 +66,12 @@ unionManyUniqDSets :: [UniqDSet a] -> UniqDSet a
 unionManyUniqDSets [] = emptyUniqDSet
 unionManyUniqDSets sets = foldr1 unionUniqDSets sets
 
-minusUniqDSet  :: UniqDSet a -> UniqDSet a -> UniqDSet a
+minusUniqDSet :: UniqDSet a -> UniqDSet a -> UniqDSet a
 minusUniqDSet = minusUDFM
 
+uniqDSetMinusUniqSet :: UniqDSet a -> UniqSet a -> UniqDSet a
+uniqDSetMinusUniqSet = udfmMinusUFM
+
 intersectUniqDSets :: UniqDSet a -> UniqDSet a -> UniqDSet a
 intersectUniqDSets = intersectUDFM
 
diff --git a/compiler/utils/UniqFM.hs b/compiler/utils/UniqFM.hs
index 3632926d91..10cc179910 100644
--- a/compiler/utils/UniqFM.hs
+++ b/compiler/utils/UniqFM.hs
@@ -66,7 +66,7 @@ module UniqFM (
         lookupWithDefaultUFM, lookupWithDefaultUFM_Directly,
         eltsUFM, keysUFM, splitUFM,
         ufmToSet_Directly,
-        ufmToList,
+        ufmToList, ufmToIntMap,
         joinUFM, pprUniqFM, pprUFM, pluralUFM
     ) where
 
@@ -298,6 +298,9 @@ eltsUFM (UFM m) = M.elems m
 ufmToSet_Directly (UFM m) = M.keysSet m
 ufmToList (UFM m) = map (\(k, v) -> (getUnique k, v)) $ M.toList m
 
+ufmToIntMap :: UniqFM elt -> M.IntMap elt
+ufmToIntMap (UFM m) = m
+
 -- Hoopl
 joinUFM :: JoinFun v -> JoinFun (UniqFM v)
 joinUFM eltJoin l (OldFact old) (NewFact new) = foldUFM_Directly add (NoChange, old) new