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

8 files changed, 77 insertions, 77 deletions

diff --git a/testsuite/tests/partial-sigs/should_compile/ExtraConstraints3.stderr b/testsuite/tests/partial-sigs/should_compile/ExtraConstraints3.stderr
index c34b1396c7..ee31ed289c 100644
--- a/testsuite/tests/partial-sigs/should_compile/ExtraConstraints3.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/ExtraConstraints3.stderr
@@ -1,28 +1,28 @@
 TYPE SIGNATURES
   !! :: forall a. [a] -> Int -> a
-  $ :: forall a b. (a -> b) -> a -> b
-  $! :: forall a b. (a -> b) -> a -> b
+  $ :: forall b a. (a -> b) -> a -> b
+  $! :: forall b a. (a -> b) -> a -> b
   && :: Bool -> Bool -> Bool
   * :: forall a. Num a => a -> a -> a
   ** :: forall a. Floating a => a -> a -> a
   + :: forall a. Num a => a -> a -> a
   ++ :: forall a. [a] -> [a] -> [a]
   - :: forall a. Num a => a -> a -> a
-  . :: forall b c a. (b -> c) -> (a -> b) -> a -> c
+  . :: forall a c b. (b -> c) -> (a -> b) -> a -> c
   / :: forall a. Fractional a => a -> a -> a
   /= :: forall a. Eq a => a -> a -> Bool
   < :: forall a. Ord a => a -> a -> Bool
   <= :: forall a. Ord a => a -> a -> Bool
   =<< ::
-    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
+    forall (m :: * -> *) b a. Monad m => (a -> m b) -> m a -> m b
   == :: forall a. Eq a => a -> a -> Bool
   > :: forall a. Ord a => a -> a -> Bool
   >= :: forall a. Ord a => a -> a -> Bool
-  >> :: forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
+  >> :: forall b (m :: * -> *) a. Monad m => m a -> m b -> m b
   >>= ::
-    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
-  ^ :: forall a b. (Num a, Integral b) => a -> b -> a
-  ^^ :: forall a b. (Integral b, Fractional a) => a -> b -> a
+    forall b (m :: * -> *) a. Monad m => m a -> (a -> m b) -> m b
+  ^ :: forall b a. (Num a, Integral b) => a -> b -> a
+  ^^ :: forall b a. (Integral b, Fractional a) => a -> b -> a
   abs :: forall a. Num a => a -> a
   acos :: forall a. Floating a => a -> a
   acosh :: forall a. Floating a => a -> a
@@ -39,22 +39,22 @@ TYPE SIGNATURES
   atan2 :: forall a. RealFloat a => a -> a -> a
   atanh :: forall a. Floating a => a -> a
   break :: forall a. (a -> Bool) -> [a] -> ([a], [a])
-  ceiling :: forall a b. (RealFrac a, Integral b) => a -> b
+  ceiling :: forall b a. (RealFrac a, Integral b) => a -> b
   compare :: forall a. Ord a => a -> a -> Ordering
   concat :: forall (t :: * -> *) a. P.Foldable t => t [a] -> [a]
   concatMap ::
-    forall (t :: * -> *) a b. P.Foldable t => (a -> [b]) -> t a -> [b]
-  const :: forall a b. a -> b -> a
+    forall (t :: * -> *) b a. P.Foldable t => (a -> [b]) -> t a -> [b]
+  const :: forall b a. a -> b -> a
   cos :: forall a. Floating a => a -> a
   cosh :: forall a. Floating a => a -> a
-  curry :: forall a b c. ((a, b) -> c) -> a -> b -> c
+  curry :: forall c a b. ((a, b) -> c) -> a -> b -> c
   cycle :: forall a. [a] -> [a]
   decodeFloat :: forall a. RealFloat a => a -> (Integer, Int)
   div :: forall a. Integral a => a -> a -> a
   divMod :: forall a. Integral a => a -> a -> (a, a)
   drop :: forall a. Int -> [a] -> [a]
   dropWhile :: forall a. (a -> Bool) -> [a] -> [a]
-  either :: forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
+  either :: forall b c a. (a -> c) -> (b -> c) -> Either a b -> c
   elem ::
     forall (t :: * -> *) a. (P.Foldable t, Eq a) => a -> t a -> Bool
   encodeFloat :: forall a. RealFloat a => Integer -> Int -> a
@@ -68,28 +68,28 @@ TYPE SIGNATURES
   exponent :: forall a. RealFloat a => a -> Int
   fail :: forall (m :: * -> *) a. Monad m => String -> m a
   filter :: forall a. (a -> Bool) -> [a] -> [a]
-  flip :: forall a b c. (a -> b -> c) -> b -> a -> c
+  flip :: forall c b a. (a -> b -> c) -> b -> a -> c
   floatDigits :: forall a. RealFloat a => a -> Int
   floatRadix :: forall a. RealFloat a => a -> Integer
   floatRange :: forall a. RealFloat a => a -> (Int, Int)
-  floor :: forall a b. (RealFrac a, Integral b) => a -> b
+  floor :: forall b a. (RealFrac a, Integral b) => a -> b
   fmap ::
-    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
+    forall (f :: * -> *) b a. Functor f => (a -> b) -> f a -> f b
   foldl ::
-    forall (t :: * -> *) b a.
+    forall (t :: * -> *) a b.
     P.Foldable t =>
     (b -> a -> b) -> b -> t a -> b
   foldl1 ::
     forall (t :: * -> *) a. P.Foldable t => (a -> a -> a) -> t a -> a
   foldr ::
-    forall (t :: * -> *) a b.
+    forall (t :: * -> *) b a.
     P.Foldable t =>
     (a -> b -> b) -> b -> t a -> b
   foldr1 ::
     forall (t :: * -> *) a. P.Foldable t => (a -> a -> a) -> t a -> a
   fromEnum :: forall a. Enum a => a -> Int
   fromInteger :: forall a. Num a => Integer -> a
-  fromIntegral :: forall a b. (Num b, Integral a) => a -> b
+  fromIntegral :: forall b a. (Num b, Integral a) => a -> b
   fromRational :: forall a. Fractional a => Rational -> a
   fst :: forall a b. (a, b) -> a
   gcd :: forall a. Integral a => a -> a -> a
@@ -114,21 +114,21 @@ TYPE SIGNATURES
   lines :: String -> [String]
   log :: forall a. Floating a => a -> a
   logBase :: forall a. Floating a => a -> a -> a
-  lookup :: forall a b. Eq a => a -> [(a, b)] -> Maybe b
-  map :: forall a b. (a -> b) -> [a] -> [b]
+  lookup :: forall b a. Eq a => a -> [(a, b)] -> Maybe b
+  map :: forall b a. (a -> b) -> [a] -> [b]
   mapM ::
-    forall (t :: * -> *) (m :: * -> *) a b.
+    forall (t :: * -> *) (m :: * -> *) b a.
     (P.Traversable t, Monad m) =>
     (a -> m b) -> t a -> m (t b)
   mapM_ ::
-    forall (t :: * -> *) (m :: * -> *) a b.
+    forall (t :: * -> *) (m :: * -> *) b a.
     (P.Foldable t, Monad m) =>
     (a -> m b) -> t a -> m ()
   max :: forall a. Ord a => a -> a -> a
   maxBound :: forall t. Bounded t => t
   maximum ::
     forall (t :: * -> *) a. (P.Foldable t, Ord a) => t a -> a
-  maybe :: forall b a. b -> (a -> b) -> Maybe a -> b
+  maybe :: forall a b. b -> (a -> b) -> Maybe a -> b
   min :: forall a. Ord a => a -> a -> a
   minBound :: forall t. Bounded t => t
   minimum ::
@@ -148,7 +148,7 @@ TYPE SIGNATURES
   product ::
     forall (t :: * -> *) a. (P.Foldable t, Num a) => t a -> a
   properFraction ::
-    forall a b. (RealFrac a, Integral b) => a -> (b, a)
+    forall b a. (RealFrac a, Integral b) => a -> (b, a)
   putChar :: Char -> IO ()
   putStr :: String -> IO ()
   putStrLn :: String -> IO ()
@@ -162,20 +162,20 @@ TYPE SIGNATURES
   readParen :: forall a. Bool -> ReadS a -> ReadS a
   reads :: forall a. Read a => ReadS a
   readsPrec :: forall a. Read a => Int -> ReadS a
-  realToFrac :: forall a b. (Real a, Fractional b) => a -> b
+  realToFrac :: forall b a. (Real a, Fractional b) => a -> b
   recip :: forall a. Fractional a => a -> a
   rem :: forall a. Integral a => a -> a -> a
   repeat :: forall a. a -> [a]
   replicate :: forall a. Int -> a -> [a]
   return :: forall (m :: * -> *) a. Monad m => a -> m a
   reverse :: forall a. [a] -> [a]
-  round :: forall a b. (RealFrac a, Integral b) => a -> b
+  round :: forall b a. (RealFrac a, Integral b) => a -> b
   scaleFloat :: forall a. RealFloat a => Int -> a -> a
-  scanl :: forall b a. (b -> a -> b) -> b -> [a] -> [b]
+  scanl :: forall a b. (b -> a -> b) -> b -> [a] -> [b]
   scanl1 :: forall a. (a -> a -> a) -> [a] -> [a]
-  scanr :: forall a b. (a -> b -> b) -> b -> [a] -> [b]
+  scanr :: forall b a. (a -> b -> b) -> b -> [a] -> [b]
   scanr1 :: forall a. (a -> a -> a) -> [a] -> [a]
-  seq :: forall a b. a -> b -> b
+  seq :: forall b a. a -> b -> b
   sequence ::
     forall (t :: * -> *) (m :: * -> *) a.
     (P.Traversable t, Monad m) =>
@@ -210,8 +210,8 @@ TYPE SIGNATURES
   toEnum :: forall a. Enum a => Int -> a
   toInteger :: forall a. Integral a => a -> Integer
   toRational :: forall a. Real a => a -> Rational
-  truncate :: forall a b. (RealFrac a, Integral b) => a -> b
-  uncurry :: forall a b c. (a -> b -> c) -> (a, b) -> c
+  truncate :: forall b a. (RealFrac a, Integral b) => a -> b
+  uncurry :: forall c b a. (a -> b -> c) -> (a, b) -> c
   undefined :: forall t. t
   unlines :: [String] -> String
   until :: forall a. (a -> Bool) -> (a -> a) -> a -> a
@@ -221,11 +221,11 @@ TYPE SIGNATURES
   userError :: String -> IOError
   words :: String -> [String]
   writeFile :: FilePath -> String -> IO ()
-  zip :: forall a b. [a] -> [b] -> [(a, b)]
-  zip3 :: forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
-  zipWith :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
+  zip :: forall b a. [a] -> [b] -> [(a, b)]
+  zip3 :: forall c b a. [a] -> [b] -> [c] -> [(a, b, c)]
+  zipWith :: forall c b a. (a -> b -> c) -> [a] -> [b] -> [c]
   zipWith3 ::
-    forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
+    forall d c b a. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
   || :: Bool -> Bool -> Bool
 TYPE CONSTRUCTORS
 COERCION AXIOMS
diff --git a/testsuite/tests/partial-sigs/should_compile/NamedTyVar.stderr b/testsuite/tests/partial-sigs/should_compile/NamedTyVar.stderr
index 88cf133f15..3e0743702f 100644
--- a/testsuite/tests/partial-sigs/should_compile/NamedTyVar.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/NamedTyVar.stderr
@@ -1,7 +1,7 @@
 TYPE SIGNATURES
-  foo :: forall b a. (a, b) -> (a, b)
+  foo :: forall a b. (a, b) -> (a, b)
 TYPE CONSTRUCTORS
 COERCION AXIOMS
 Dependent modules: []
 Dependent packages: [base-4.9.0.0, ghc-prim-0.5.0.0,
-                     integer-gmp-1.0.0.0]
+                     integer-gmp-1.0.0.1]
diff --git a/testsuite/tests/partial-sigs/should_compile/SkipMany.stderr b/testsuite/tests/partial-sigs/should_compile/SkipMany.stderr
index 5b94077eb0..6209498942 100644
--- a/testsuite/tests/partial-sigs/should_compile/SkipMany.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/SkipMany.stderr
@@ -2,7 +2,7 @@ TYPE SIGNATURES
   SkipMany.GenParser ::
     forall tok st a. tok -> st -> a -> GenParser tok st a
   skipMany ::
-    forall tok st a. GenParser tok st a -> GenParser tok st ()
+    forall a tok st. GenParser tok st a -> GenParser tok st ()
   skipMany' ::
     forall tok st a. GenParser tok st a -> GenParser tok st ()
 TYPE CONSTRUCTORS
diff --git a/testsuite/tests/partial-sigs/should_compile/T10438.stderr b/testsuite/tests/partial-sigs/should_compile/T10438.stderr
index 3871a6345e..0742250be3 100644
--- a/testsuite/tests/partial-sigs/should_compile/T10438.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/T10438.stderr
@@ -24,5 +24,5 @@ T10438.hs:7:22: warning: [-Wpartial-type-signatures (in -Wdefault)]
         x :: t2 (bound at T10438.hs:8:17)
         r :: t2 (bound at T10438.hs:6:11)
         g :: t2 -> t2 (bound at T10438.hs:6:9)
-        f :: t (bound at T10438.hs:5:5)
-        foo :: t -> forall t1. t1 -> t1 (bound at T10438.hs:5:1)
+        f :: t1 (bound at T10438.hs:5:5)
+        foo :: t1 -> forall t. t -> t (bound at T10438.hs:5:1)
diff --git a/testsuite/tests/partial-sigs/should_compile/UncurryNamed.stderr b/testsuite/tests/partial-sigs/should_compile/UncurryNamed.stderr
index 58116f8b16..2ff8d3da3f 100644
--- a/testsuite/tests/partial-sigs/should_compile/UncurryNamed.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/UncurryNamed.stderr
@@ -1,5 +1,5 @@
 TYPE SIGNATURES
-  unc :: forall t a b. (a -> b -> t) -> (a, b) -> t
+  unc :: forall a b t. (a -> b -> t) -> (a, b) -> t
 TYPE CONSTRUCTORS
 COERCION AXIOMS
 Dependent modules: []
diff --git a/testsuite/tests/partial-sigs/should_compile/WarningWildcardInstantiations.stderr b/testsuite/tests/partial-sigs/should_compile/WarningWildcardInstantiations.stderr
index 7013696580..b5268acb60 100644
--- a/testsuite/tests/partial-sigs/should_compile/WarningWildcardInstantiations.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/WarningWildcardInstantiations.stderr
@@ -1,5 +1,5 @@
 TYPE SIGNATURES
-  bar :: forall t t1. t1 -> (t1 -> t) -> t
+  bar :: forall t t1. t -> (t -> t1) -> t1
   foo :: forall a. (Show a, Enum a) => a -> String
 TYPE CONSTRUCTORS
 COERCION AXIOMS
@@ -30,37 +30,37 @@ WarningWildcardInstantiations.hs:5:30: warning: [-Wpartial-type-signatures (in -
         foo :: a -> String (bound at WarningWildcardInstantiations.hs:6:1)
 
 WarningWildcardInstantiations.hs:8:8: warning: [-Wpartial-type-signatures (in -Wdefault)]
-    • Found type wildcard ‘_’ standing for ‘t1’
-      Where: ‘t1’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+    • Found type wildcard ‘_’ standing for ‘t’
+      Where: ‘t’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WarningWildcardInstantiations.hs:9:1
     • In the type signature:
         bar :: _ -> _ -> _
     • Relevant bindings include
-        bar :: t1 -> (t1 -> t) -> t
+        bar :: t -> (t -> t1) -> t1
           (bound at WarningWildcardInstantiations.hs:9:1)
 
 WarningWildcardInstantiations.hs:8:13: warning: [-Wpartial-type-signatures (in -Wdefault)]
-    • Found type wildcard ‘_’ standing for ‘t1 -> t’
-      Where: ‘t’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+    • Found type wildcard ‘_’ standing for ‘t -> t1’
+      Where: ‘t1’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WarningWildcardInstantiations.hs:9:1
-             ‘t1’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+             ‘t’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WarningWildcardInstantiations.hs:9:1
     • In the type signature:
         bar :: _ -> _ -> _
     • Relevant bindings include
-        bar :: t1 -> (t1 -> t) -> t
+        bar :: t -> (t -> t1) -> t1
           (bound at WarningWildcardInstantiations.hs:9:1)
 
 WarningWildcardInstantiations.hs:8:18: warning: [-Wpartial-type-signatures (in -Wdefault)]
-    • Found type wildcard ‘_’ standing for ‘t’
-      Where: ‘t’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+    • Found type wildcard ‘_’ standing for ‘t1’
+      Where: ‘t1’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WarningWildcardInstantiations.hs:9:1
     • In the type signature:
         bar :: _ -> _ -> _
     • Relevant bindings include
-        bar :: t1 -> (t1 -> t) -> t
+        bar :: t -> (t -> t1) -> t1
           (bound at WarningWildcardInstantiations.hs:9:1)
diff --git a/testsuite/tests/partial-sigs/should_fail/T10045.stderr b/testsuite/tests/partial-sigs/should_fail/T10045.stderr
index 42218b5fe9..d6a3a5ac37 100644
--- a/testsuite/tests/partial-sigs/should_fail/T10045.stderr
+++ b/testsuite/tests/partial-sigs/should_fail/T10045.stderr
@@ -1,10 +1,10 @@
 
 T10045.hs:6:18: error:
-    • Found type wildcard ‘_’ standing for ‘t1 -> Bool -> t2’
-      Where: ‘t2’ is a rigid type variable bound by
-               the inferred type of copy :: t1 -> Bool -> t2 at T10045.hs:7:10
-             ‘t1’ is a rigid type variable bound by
-               the inferred type of copy :: t1 -> Bool -> t2 at T10045.hs:7:10
+    • Found type wildcard ‘_’ standing for ‘t2 -> Bool -> t1’
+      Where: ‘t1’ is a rigid type variable bound by
+               the inferred type of copy :: t2 -> Bool -> t1 at T10045.hs:7:10
+             ‘t2’ is a rigid type variable bound by
+               the inferred type of copy :: t2 -> Bool -> t1 at T10045.hs:7:10
       To use the inferred type, enable PartialTypeSignatures
     • In the type signature:
         copy :: _
@@ -20,6 +20,6 @@ T10045.hs:6:18: error:
                 copy w from = copy w True
               in copy ws1 False
     • Relevant bindings include
-        copy :: t1 -> Bool -> t2 (bound at T10045.hs:7:10)
+        copy :: t2 -> Bool -> t1 (bound at T10045.hs:7:10)
         ws1 :: () (bound at T10045.hs:5:11)
         foo :: Meta -> t (bound at T10045.hs:5:1)
diff --git a/testsuite/tests/partial-sigs/should_fail/WildcardInstantiations.stderr b/testsuite/tests/partial-sigs/should_fail/WildcardInstantiations.stderr
index ff18935c8d..63058a9781 100644
--- a/testsuite/tests/partial-sigs/should_fail/WildcardInstantiations.stderr
+++ b/testsuite/tests/partial-sigs/should_fail/WildcardInstantiations.stderr
@@ -25,40 +25,40 @@ WildcardInstantiations.hs:5:30: error:
         foo :: a -> String (bound at WildcardInstantiations.hs:6:1)
 
 WildcardInstantiations.hs:8:8: error:
-    • Found type wildcard ‘_’ standing for ‘t1’
-      Where: ‘t1’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+    • Found type wildcard ‘_’ standing for ‘t’
+      Where: ‘t’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WildcardInstantiations.hs:9:1
       To use the inferred type, enable PartialTypeSignatures
     • In the type signature:
         bar :: _ -> _ -> _
     • Relevant bindings include
-        bar :: t1 -> (t1 -> t) -> t
+        bar :: t -> (t -> t1) -> t1
           (bound at WildcardInstantiations.hs:9:1)
 
 WildcardInstantiations.hs:8:13: error:
-    • Found type wildcard ‘_’ standing for ‘t1 -> t’
-      Where: ‘t’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+    • Found type wildcard ‘_’ standing for ‘t -> t1’
+      Where: ‘t1’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WildcardInstantiations.hs:9:1
-             ‘t1’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+             ‘t’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WildcardInstantiations.hs:9:1
       To use the inferred type, enable PartialTypeSignatures
     • In the type signature:
         bar :: _ -> _ -> _
     • Relevant bindings include
-        bar :: t1 -> (t1 -> t) -> t
+        bar :: t -> (t -> t1) -> t1
           (bound at WildcardInstantiations.hs:9:1)
 
 WildcardInstantiations.hs:8:18: error:
-    • Found type wildcard ‘_’ standing for ‘t’
-      Where: ‘t’ is a rigid type variable bound by
-               the inferred type of bar :: t1 -> (t1 -> t) -> t
+    • Found type wildcard ‘_’ standing for ‘t1’
+      Where: ‘t1’ is a rigid type variable bound by
+               the inferred type of bar :: t -> (t -> t1) -> t1
                at WildcardInstantiations.hs:9:1
       To use the inferred type, enable PartialTypeSignatures
     • In the type signature:
         bar :: _ -> _ -> _
     • Relevant bindings include
-        bar :: t1 -> (t1 -> t) -> t
+        bar :: t -> (t -> t1) -> t1
           (bound at WildcardInstantiations.hs:9:1)