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

17 files changed, 61 insertions, 61 deletions

diff --git a/testsuite/tests/typecheck/should_compile/T10971a.stderr b/testsuite/tests/typecheck/should_compile/T10971a.stderr
index 0702b32384..72c675aa8c 100644
--- a/testsuite/tests/typecheck/should_compile/T10971a.stderr
+++ b/testsuite/tests/typecheck/should_compile/T10971a.stderr
@@ -11,7 +11,7 @@ T10971a.hs:7:11: warning: [-Wtype-defaults (in -Wall)]
 
 T10971a.hs:8:1: warning: [-Wmissing-signatures (in -Wall)]
     Top-level binding with no type signature:
-      g :: forall a b. (a -> b) -> [a] -> [b]
+      g :: forall b a. (a -> b) -> [a] -> [b]
 
 T10971a.hs:8:6: warning: [-Wname-shadowing (in -Wall)]
     This binding for ‘f’ shadows the existing binding
diff --git a/testsuite/tests/typecheck/should_compile/tc141.stderr b/testsuite/tests/typecheck/should_compile/tc141.stderr
index 15bdad80c3..49a26d6363 100644
--- a/testsuite/tests/typecheck/should_compile/tc141.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc141.stderr
@@ -35,7 +35,7 @@ tc141.hs:13:13: error:
         in v
 
 tc141.hs:15:18: error:
-    • Couldn't match expected type ‘a1’ with actual type ‘t1’
+    • Couldn't match expected type ‘a1’ with actual type ‘t’
         because type variable ‘a1’ would escape its scope
       This (rigid, skolem) type variable is bound by
         the type signature for:
@@ -50,5 +50,5 @@ tc141.hs:15:18: error:
         in v
     • Relevant bindings include
         v :: a1 (bound at tc141.hs:15:14)
-        b :: t1 (bound at tc141.hs:13:5)
-        g :: t -> t1 -> forall a. a (bound at tc141.hs:13:1)
+        b :: t (bound at tc141.hs:13:5)
+        g :: t1 -> t -> forall a. a (bound at tc141.hs:13:1)
diff --git a/testsuite/tests/typecheck/should_compile/tc168.stderr b/testsuite/tests/typecheck/should_compile/tc168.stderr
index 16ba4b0446..5bcce5b457 100644
--- a/testsuite/tests/typecheck/should_compile/tc168.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc168.stderr
@@ -9,4 +9,4 @@ tc168.hs:17:1: error:
     • In the ambiguity check for the inferred type for ‘g’
       To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
       When checking the inferred type
-        g :: forall a b a1. C a1 (a, b) => a1 -> a
+        g :: forall b a a1. C a1 (a, b) => a1 -> a
diff --git a/testsuite/tests/typecheck/should_compile/tc231.stderr b/testsuite/tests/typecheck/should_compile/tc231.stderr
index dd5624849a..daa77b3313 100644
--- a/testsuite/tests/typecheck/should_compile/tc231.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc231.stderr
@@ -2,7 +2,7 @@ TYPE SIGNATURES
   Node :: forall s a chain. s -> a -> chain -> Q s a chain
   Z :: forall a. a -> Z a
   foo ::
-    forall s b chain.
+    forall chain s b.
     Zork s (Z [Char]) b =>
     Q s (Z [Char]) chain -> ST s ()
   huh ::
diff --git a/testsuite/tests/typecheck/should_fail/T5853.stderr b/testsuite/tests/typecheck/should_fail/T5853.stderr
index d9a8244483..c95dc53d1c 100644
--- a/testsuite/tests/typecheck/should_fail/T5853.stderr
+++ b/testsuite/tests/typecheck/should_fail/T5853.stderr
@@ -1,23 +1,23 @@
 
 T5853.hs:15:46: error:
-    • Could not deduce: Subst t1 (Elem t2) ~ t2
+    • Could not deduce: Subst t (Elem t2) ~ t2
         arising from a use of ‘<$>’
-      from the context: (F t,
-                         Elem t ~ Elem t,
-                         Elem t2 ~ Elem t2,
-                         Subst t (Elem t2) ~ t2,
-                         Subst t2 (Elem t) ~ t,
-                         F t1,
+      from the context: (F t1,
                          Elem t1 ~ Elem t1,
+                         Elem t2 ~ Elem t2,
+                         Subst t1 (Elem t2) ~ t2,
+                         Subst t2 (Elem t1) ~ t1,
+                         F t,
                          Elem t ~ Elem t,
-                         Subst t1 (Elem t) ~ t,
-                         Subst t (Elem t1) ~ t1)
+                         Elem t1 ~ Elem t1,
+                         Subst t (Elem t1) ~ t1,
+                         Subst t1 (Elem t) ~ t)
         bound by the RULE "map/map" at T5853.hs:15:2-57
       ‘t2’ is a rigid type variable bound by
         the RULE "map/map" at T5853.hs:15:2
     • In the expression: (f . g) <$> xs
       When checking the transformation rule "map/map"
     • Relevant bindings include
-        f :: Elem t -> Elem t2 (bound at T5853.hs:15:19)
-        g :: Elem t1 -> Elem t (bound at T5853.hs:15:21)
-        xs :: t1 (bound at T5853.hs:15:23)
+        f :: Elem t1 -> Elem t2 (bound at T5853.hs:15:19)
+        g :: Elem t -> Elem t1 (bound at T5853.hs:15:21)
+        xs :: t (bound at T5853.hs:15:23)
diff --git a/testsuite/tests/typecheck/should_fail/T6018fail.stderr b/testsuite/tests/typecheck/should_fail/T6018fail.stderr
index c20c9ecc89..3bd6b40a82 100644
--- a/testsuite/tests/typecheck/should_fail/T6018fail.stderr
+++ b/testsuite/tests/typecheck/should_fail/T6018fail.stderr
@@ -79,7 +79,7 @@ T6018fail.hs:66:15: error:
     Kind variable ‘k’ cannot be inferred from the right-hand side.
     Use -fprint-explicit-kinds to see the kind arguments
     In the type family equation:
-      forall k (a :: k) (b :: k).
+      forall k (b :: k) (a :: k).
         Fc a b = Int -- Defined at T6018fail.hs:66:15
 
 T6018fail.hs:70:15: error:
@@ -88,7 +88,7 @@ T6018fail.hs:70:15: error:
     cannot be inferred from the right-hand side.
     Use -fprint-explicit-kinds to see the kind arguments
     In the type family equation:
-      forall k (a :: k) (b :: k).
+      forall k (b :: k) (a :: k).
         Gc a b = Int -- Defined at T6018fail.hs:70:15
 
 T6018fail.hs:74:15: error:
@@ -145,7 +145,7 @@ T6018fail.hs:118:15: error:
     cannot be inferred from the right-hand side.
     Use -fprint-explicit-kinds to see the kind arguments
     In the type family equation:
-      forall k a b (c :: k).
+      forall k (c :: k) b a.
         G7 a b c = [G7a a b c] -- Defined at T6018fail.hs:118:15
 
 T6018fail.hs:129:1: error:
diff --git a/testsuite/tests/typecheck/should_fail/T6018failclosed.stderr b/testsuite/tests/typecheck/should_fail/T6018failclosed.stderr
index 6cc0c3700e..7a0146d7d7 100644
--- a/testsuite/tests/typecheck/should_fail/T6018failclosed.stderr
+++ b/testsuite/tests/typecheck/should_fail/T6018failclosed.stderr
@@ -24,11 +24,11 @@ T6018failclosed.hs:19:5: error:
 
 T6018failclosed.hs:25:5: error:
     • Type family equation violates injectivity annotation.
-      Type and kind variables ‘k’, ‘b’
+      Type and kind variables ‘k1’, ‘b’
       cannot be inferred from the right-hand side.
       Use -fprint-explicit-kinds to see the kind arguments
       In the type family equation:
-        forall k k1 (b :: k) (c :: k1).
+        forall k k1 (c :: k) (b :: k1).
           JClosed Int b c = Char -- Defined at T6018failclosed.hs:25:5
     • In the equations for closed type family ‘JClosed’
       In the type family declaration for ‘JClosed’
@@ -90,7 +90,7 @@ T6018failclosed.hs:66:5: error:
       Kind variable ‘k’ cannot be inferred from the right-hand side.
       Use -fprint-explicit-kinds to see the kind arguments
       In the type family equation:
-        forall k (a :: k) (b :: k).
+        forall k (b :: k) (a :: k).
           Gc a b = Int -- Defined at T6018failclosed.hs:66:5
     • In the equations for closed type family ‘Gc’
       In the type family declaration for ‘Gc’
diff --git a/testsuite/tests/typecheck/should_fail/T7453.stderr b/testsuite/tests/typecheck/should_fail/T7453.stderr
index bcb2df84c8..6b8e920004 100644
--- a/testsuite/tests/typecheck/should_fail/T7453.stderr
+++ b/testsuite/tests/typecheck/should_fail/T7453.stderr
@@ -28,14 +28,14 @@ T7453.hs:9:15: error:
         cast1 :: t -> a (bound at T7453.hs:7:1)
 
 T7453.hs:15:15: error:
-    • Couldn't match type ‘t’ with ‘t2’
+    • Couldn't match type ‘t1’ with ‘t2’
         because type variable ‘t2’ would escape its scope
       This (rigid, skolem) type variable is bound by
         the type signature for:
           z :: () -> t2
         at T7453.hs:14:11-22
       Expected type: () -> t2
-        Actual type: () -> t
+        Actual type: () -> t1
     • In the expression: aux
       In an equation for ‘z’:
           z = aux
@@ -50,13 +50,13 @@ T7453.hs:15:15: error:
                   where
                       aux = const v
     • Relevant bindings include
-        aux :: forall b. b -> t (bound at T7453.hs:16:21)
+        aux :: forall b. b -> t1 (bound at T7453.hs:16:21)
         z :: () -> t2 (bound at T7453.hs:15:11)
-        v :: t (bound at T7453.hs:13:7)
-        cast2 :: t -> t1 (bound at T7453.hs:13:1)
+        v :: t1 (bound at T7453.hs:13:7)
+        cast2 :: t1 -> t (bound at T7453.hs:13:1)
 
 T7453.hs:21:15: error:
-    • Couldn't match expected type ‘t2’ with actual type ‘t’
+    • Couldn't match expected type ‘t2’ with actual type ‘t1’
         because type variable ‘t2’ would escape its scope
       This (rigid, skolem) type variable is bound by
         the type signature for:
@@ -76,7 +76,7 @@ T7453.hs:21:15: error:
                   where
                       aux = const v
     • Relevant bindings include
-        aux :: forall b. b -> t (bound at T7453.hs:22:21)
+        aux :: forall b. b -> t1 (bound at T7453.hs:22:21)
         z :: t2 (bound at T7453.hs:21:11)
-        v :: t (bound at T7453.hs:19:7)
-        cast3 :: t -> forall t1. t1 (bound at T7453.hs:19:1)
+        v :: t1 (bound at T7453.hs:19:7)
+        cast3 :: t1 -> forall t. t (bound at T7453.hs:19:1)
diff --git a/testsuite/tests/typecheck/should_fail/T7734.stderr b/testsuite/tests/typecheck/should_fail/T7734.stderr
index 1b1716bfc5..8553fdb888 100644
--- a/testsuite/tests/typecheck/should_fail/T7734.stderr
+++ b/testsuite/tests/typecheck/should_fail/T7734.stderr
@@ -1,18 +1,18 @@
 
 T7734.hs:4:13: error:
-    • Occurs check: cannot construct the infinite type: t1 ~ t1 -> t2
+    • Occurs check: cannot construct the infinite type: t2 ~ t2 -> t1
     • In the first argument of ‘x’, namely ‘x’
       In the expression: x x
       In an equation for ‘f’: x `f` y = x x
     • Relevant bindings include
-        x :: t1 -> t2 (bound at T7734.hs:4:1)
-        f :: (t1 -> t2) -> t -> t2 (bound at T7734.hs:4:3)
+        x :: t2 -> t1 (bound at T7734.hs:4:1)
+        f :: (t2 -> t1) -> t -> t1 (bound at T7734.hs:4:3)
 
 T7734.hs:5:13: error:
-    • Occurs check: cannot construct the infinite type: t1 ~ t1 -> t2
+    • Occurs check: cannot construct the infinite type: t2 ~ t2 -> t1
     • In the first argument of ‘x’, namely ‘x’
       In the expression: x x
       In an equation for ‘&’: (&) x y = x x
     • Relevant bindings include
-        x :: t1 -> t2 (bound at T7734.hs:5:5)
-        (&) :: (t1 -> t2) -> t -> t2 (bound at T7734.hs:5:1)
+        x :: t2 -> t1 (bound at T7734.hs:5:5)
+        (&) :: (t2 -> t1) -> t -> t1 (bound at T7734.hs:5:1)
diff --git a/testsuite/tests/typecheck/should_fail/T8142.stderr b/testsuite/tests/typecheck/should_fail/T8142.stderr
index 3faa530996..53e6798a5e 100644
--- a/testsuite/tests/typecheck/should_fail/T8142.stderr
+++ b/testsuite/tests/typecheck/should_fail/T8142.stderr
@@ -8,7 +8,7 @@ T8142.hs:6:18: error:
     • In the ambiguity check for the inferred type for ‘h’
       To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
       When checking the inferred type
-        h :: forall t (g :: * -> *). Nu ((,) t) -> Nu g
+        h :: forall (g :: * -> *) t. Nu ((,) t) -> Nu g
       In an equation for ‘tracer’:
           tracer
             = h
diff --git a/testsuite/tests/typecheck/should_fail/T9109.stderr b/testsuite/tests/typecheck/should_fail/T9109.stderr
index 6a08318ac0..71d88efdc8 100644
--- a/testsuite/tests/typecheck/should_fail/T9109.stderr
+++ b/testsuite/tests/typecheck/should_fail/T9109.stderr
@@ -1,15 +1,15 @@
 
 T9109.hs:8:13: error:
-    • Couldn't match expected type ‘t1’ with actual type ‘Bool’
-        ‘t1’ is untouchable
-          inside the constraints: t ~ Bool
+    • Couldn't match expected type ‘t’ with actual type ‘Bool’
+        ‘t’ is untouchable
+          inside the constraints: t1 ~ Bool
           bound by a pattern with constructor: GBool :: G Bool,
                    in an equation for ‘foo’
           at T9109.hs:8:5-9
-      ‘t1’ is a rigid type variable bound by
-        the inferred type of foo :: G t -> t1 at T9109.hs:8:1
+      ‘t’ is a rigid type variable bound by
+        the inferred type of foo :: G t1 -> t at T9109.hs:8:1
       Possible fix: add a type signature for ‘foo’
     • In the expression: True
       In an equation for ‘foo’: foo GBool = True
     • Relevant bindings include
-        foo :: G t -> t1 (bound at T9109.hs:8:1)
+        foo :: G t1 -> t (bound at T9109.hs:8:1)
diff --git a/testsuite/tests/typecheck/should_fail/tcfail004.stderr b/testsuite/tests/typecheck/should_fail/tcfail004.stderr
index c575129cf5..41a55c1ea9 100644
--- a/testsuite/tests/typecheck/should_fail/tcfail004.stderr
+++ b/testsuite/tests/typecheck/should_fail/tcfail004.stderr
@@ -1,9 +1,9 @@
 
 tcfail004.hs:3:9: error:
-    • Couldn't match expected type ‘(t, t1)’
+    • Couldn't match expected type ‘(t1, t)’
                   with actual type ‘(Integer, Integer, Integer)’
     • In the expression: (1, 2, 3)
       In a pattern binding: (f, g) = (1, 2, 3)
     • Relevant bindings include
-        f :: t (bound at tcfail004.hs:3:2)
-        g :: t1 (bound at tcfail004.hs:3:4)
+        f :: t1 (bound at tcfail004.hs:3:2)
+        g :: t (bound at tcfail004.hs:3:4)
diff --git a/testsuite/tests/typecheck/should_fail/tcfail033.stderr b/testsuite/tests/typecheck/should_fail/tcfail033.stderr
index 94e998f05f..e349ab1116 100644
--- a/testsuite/tests/typecheck/should_fail/tcfail033.stderr
+++ b/testsuite/tests/typecheck/should_fail/tcfail033.stderr
@@ -1,10 +1,10 @@
 
 tcfail033.hs:4:12: error:
-    • Occurs check: cannot construct the infinite type: t ~ (t, t1)
+    • Occurs check: cannot construct the infinite type: t1 ~ (t1, t)
     • In the expression: x
       In the expression: [x | (x, y) <- buglet]
       In an equation for ‘buglet’: buglet = [x | (x, y) <- buglet]
     • Relevant bindings include
-        y :: t1 (bound at tcfail033.hs:4:19)
-        x :: t (bound at tcfail033.hs:4:17)
-        buglet :: [(t, t1)] (bound at tcfail033.hs:4:1)
+        y :: t (bound at tcfail033.hs:4:19)
+        x :: t1 (bound at tcfail033.hs:4:17)
+        buglet :: [(t1, t)] (bound at tcfail033.hs:4:1)
diff --git a/testsuite/tests/typecheck/should_fail/tcfail049.stderr b/testsuite/tests/typecheck/should_fail/tcfail049.stderr
index 1b74ce0070..ec83902d6f 100644
--- a/testsuite/tests/typecheck/should_fail/tcfail049.stderr
+++ b/testsuite/tests/typecheck/should_fail/tcfail049.stderr
@@ -1,2 +1,2 @@
 
-tcfail049.hs:3:7: error: Variable not in scope: g :: t -> t1
+tcfail049.hs:3:7: error: Variable not in scope: g :: t1 -> t
diff --git a/testsuite/tests/typecheck/should_fail/tcfail050.stderr b/testsuite/tests/typecheck/should_fail/tcfail050.stderr
index 2ca5065938..9d6a0c06b2 100644
--- a/testsuite/tests/typecheck/should_fail/tcfail050.stderr
+++ b/testsuite/tests/typecheck/should_fail/tcfail050.stderr
@@ -1,3 +1,3 @@
 
 tcfail050.hs:3:7: error:
-    Data constructor not in scope: B :: t -> t1
+    Data constructor not in scope: B :: t1 -> t
diff --git a/testsuite/tests/typecheck/should_fail/tcfail140.stderr b/testsuite/tests/typecheck/should_fail/tcfail140.stderr
index 4c3fecec43..f75f77c38a 100644
--- a/testsuite/tests/typecheck/should_fail/tcfail140.stderr
+++ b/testsuite/tests/typecheck/should_fail/tcfail140.stderr
@@ -9,14 +9,14 @@ tcfail140.hs:10:7: error:
     • Relevant bindings include bar :: t (bound at tcfail140.hs:10:1)
 
 tcfail140.hs:12:10: error:
-    • Couldn't match expected type ‘Integer -> t1’
+    • Couldn't match expected type ‘Integer -> t’
                   with actual type ‘Int’
     • The operator ‘f’ takes two arguments,
       but its type ‘Int -> Int’ has only one
       In the expression: 3 `f` 4
       In an equation for ‘rot’: rot xs = 3 `f` 4
     • Relevant bindings include
-        rot :: t -> t1 (bound at tcfail140.hs:12:1)
+        rot :: t1 -> t (bound at tcfail140.hs:12:1)
 
 tcfail140.hs:14:15: error:
     • Couldn't match expected type ‘t -> b’ with actual type ‘Int’
diff --git a/testsuite/tests/typecheck/should_fail/tcfail198.stderr b/testsuite/tests/typecheck/should_fail/tcfail198.stderr
index 88469939f3..51aaf1d58e 100644
--- a/testsuite/tests/typecheck/should_fail/tcfail198.stderr
+++ b/testsuite/tests/typecheck/should_fail/tcfail198.stderr
@@ -1,6 +1,6 @@
 
 tcfail198.hs:6:36: error:
-    • Couldn't match expected type ‘a2’ with actual type ‘a1’
+    • Couldn't match expected type ‘a2’ with actual type ‘a’
         because type variable ‘a2’ would escape its scope
       This (rigid, skolem) type variable is bound by
         an expression type signature:
@@ -10,6 +10,6 @@ tcfail198.hs:6:36: error:
       In the second argument of ‘(++)’, namely ‘[x :: a]’
       In the expression: xs ++ [x :: a]
     • Relevant bindings include
-        xs :: [a1] (bound at tcfail198.hs:6:21)
-        x :: a1 (bound at tcfail198.hs:6:19)
-        f3 :: [a1] -> [a1] (bound at tcfail198.hs:6:6)
+        xs :: [a] (bound at tcfail198.hs:6:21)
+        x :: a (bound at tcfail198.hs:6:19)
+        f3 :: [a] -> [a] (bound at tcfail198.hs:6:6)