Create a deterministic version of tyVarsOfType

I've run into situations where I need deterministic `tyVarsOfType` and
this implementation achieves that and also brings an algorithmic
improvement.  Union of two `VarSet`s takes linear time the size of the
sets and in the worst case we can have `n` unions of sets of sizes
`(n-1, 1), (n-2, 1)...` making it quadratic.

One reason why we need deterministic `tyVarsOfType` is in `abstractVars`
in `SetLevels`. When we abstract type variables when floating we want
them to be abstracted in deterministic order.

Test Plan: harbormaster

Reviewers: simonpj, goldfire, austin, hvr, simonmar, bgamari

Reviewed By: simonmar

Subscribers: thomie

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

GHC Trac Issues: #4012

4 files changed, 109 insertions, 109 deletions

diff --git a/testsuite/tests/partial-sigs/should_compile/T10403.stderr b/testsuite/tests/partial-sigs/should_compile/T10403.stderr
index 8af7da3d81..bfd5367bcd 100644
--- a/testsuite/tests/partial-sigs/should_compile/T10403.stderr
+++ b/testsuite/tests/partial-sigs/should_compile/T10403.stderr
@@ -1,39 +1,39 @@
-

-T10403.hs:15:7: warning:

-    Found hole ‘_’ with inferred constraints: Functor f

-    In the type signature for:

-      h1 :: _ => _

-

-T10403.hs:15:12: warning:

-    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’

-    Where: ‘f’ is a rigid type variable bound by

-               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:17:1

-           ‘b’ is a rigid type variable bound by

-               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:17:1

-           ‘a’ is a rigid type variable bound by

-               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:17:1

-    In the type signature for:

-      h1 :: _ => _

-

-T10403.hs:19:7: warning:

-    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’

-    Where: ‘f’ is a rigid type variable bound by

-               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:21:1

-           ‘b’ is a rigid type variable bound by

-               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:21:1

-           ‘a’ is a rigid type variable bound by

-               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f

-               at T10403.hs:21:1

-    In the type signature for:

-      h2 :: _

-

-T10403.hs:21:1: warning:

-    No instance for (Functor f)

-    When checking that ‘h2’ has the inferred type

-      h2 :: forall (f :: * -> *) b a. (a -> b) -> f a -> H f

-    Probable cause: the inferred type is ambiguous

+
+T10403.hs:15:7: warning:
+    Found hole ‘_’ with inferred constraints: Functor f
+    In the type signature for:
+      h1 :: _ => _
+
+T10403.hs:15:12: warning:
+    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’
+    Where: ‘b’ is a rigid type variable bound by
+               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:17:1
+           ‘a’ is a rigid type variable bound by
+               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:17:1
+           ‘f’ is a rigid type variable bound by
+               the inferred type of h1 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:17:1
+    In the type signature for:
+      h1 :: _ => _
+
+T10403.hs:19:7: warning:
+    Found type wildcard ‘_’ standing for ‘(a -> b) -> f a -> H f’
+    Where: ‘b’ is a rigid type variable bound by
+               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:21:1
+           ‘a’ is a rigid type variable bound by
+               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:21:1
+           ‘f’ is a rigid type variable bound by
+               the inferred type of h2 :: Functor f => (a -> b) -> f a -> H f
+               at T10403.hs:21:1
+    In the type signature for:
+      h2 :: _
+
+T10403.hs:21:1: warning:
+    No instance for (Functor f)
+    When checking that ‘h2’ has the inferred type
+      h2 :: forall (f :: * -> *) b a. (a -> b) -> f a -> H f
+    Probable cause: the inferred type is ambiguous
diff --git a/testsuite/tests/partial-sigs/should_fail/Trac10045.stderr b/testsuite/tests/partial-sigs/should_fail/Trac10045.stderr
index da0f8c78b7..7eb8b3eebd 100644
--- a/testsuite/tests/partial-sigs/should_fail/Trac10045.stderr
+++ b/testsuite/tests/partial-sigs/should_fail/Trac10045.stderr
@@ -1,46 +1,46 @@
-

-Trac10045.hs:6:17: error:

-    Found type wildcard ‘_’ standing for ‘t1 -> a -> t2’

-    Where: ‘t1’ is a rigid type variable bound by

-                the inferred type of copy :: Num a => t1 -> a -> t2

-                at Trac10045.hs:7:9

-           ‘t2’ is a rigid type variable bound by

-                the inferred type of copy :: Num a => t1 -> a -> t2

-                at Trac10045.hs:7:9

-           ‘a’ is a rigid type variable bound by

-               the inferred type of copy :: Num a => t1 -> a -> t2

-               at Trac10045.hs:7:9

-    To use the inferred type, enable PartialTypeSignatures

-    Relevant bindings include

-      ws1 :: () (bound at Trac10045.hs:5:11)

-      foo :: Meta -> t (bound at Trac10045.hs:5:1)

-    In the type signature for:

-      copy :: _

-    In the expression:

-      let

-        copy :: _

-        copy w from = copy w 1

-      in copy ws1 1

-    In an equation for ‘foo’:

-        foo (Meta ws1)

-          = let

-              copy :: _

-              copy w from = copy w 1

-            in copy ws1 1

-

-Trac10045.hs:7:9: error:

-    No instance for (Num a)

-    When checking that ‘copy’ has the inferred type

-      copy :: forall t t1 a. t -> a -> t1

-    Probable cause: the inferred type is ambiguous

-    In the expression:

-      let

-        copy :: _

-        copy w from = copy w 1

-      in copy ws1 1

-    In an equation for ‘foo’:

-        foo (Meta ws1)

-          = let

-              copy :: _

-              copy w from = copy w 1

-            in copy ws1 1

+
+Trac10045.hs:6:17: error:
+    Found type wildcard ‘_’ standing for ‘t1 -> a -> t2’
+    Where: ‘t1’ is a rigid type variable bound by
+                the inferred type of copy :: Num a => t1 -> a -> t2
+                at Trac10045.hs:7:9
+           ‘a’ is a rigid type variable bound by
+               the inferred type of copy :: Num a => t1 -> a -> t2
+               at Trac10045.hs:7:9
+           ‘t2’ is a rigid type variable bound by
+                the inferred type of copy :: Num a => t1 -> a -> t2
+                at Trac10045.hs:7:9
+    To use the inferred type, enable PartialTypeSignatures
+    Relevant bindings include
+      ws1 :: () (bound at Trac10045.hs:5:11)
+      foo :: Meta -> t (bound at Trac10045.hs:5:1)
+    In the type signature for:
+      copy :: _
+    In the expression:
+      let
+        copy :: _
+        copy w from = copy w 1
+      in copy ws1 1
+    In an equation for ‘foo’:
+        foo (Meta ws1)
+          = let
+              copy :: _
+              copy w from = copy w 1
+            in copy ws1 1
+
+Trac10045.hs:7:9: error:
+    No instance for (Num a)
+    When checking that ‘copy’ has the inferred type
+      copy :: forall t t1 a. t -> a -> t1
+    Probable cause: the inferred type is ambiguous
+    In the expression:
+      let
+        copy :: _
+        copy w from = copy w 1
+      in copy ws1 1
+    In an equation for ‘foo’:
+        foo (Meta ws1)
+          = let
+              copy :: _
+              copy w from = copy w 1
+            in copy ws1 1
diff --git a/testsuite/tests/perf/should_run/T10359 b/testsuite/tests/perf/should_run/T10359
new file mode 100755
index 0000000000..4968e1b1db
--- /dev/null
+++ b/testsuite/tests/perf/should_run/T10359
diff --git a/testsuite/tests/polykinds/T9222.stderr b/testsuite/tests/polykinds/T9222.stderr
index 1d1a1df779..a5b35ee2b1 100644
--- a/testsuite/tests/polykinds/T9222.stderr
+++ b/testsuite/tests/polykinds/T9222.stderr
@@ -1,24 +1,24 @@
-

-T9222.hs:13:3: error:

-    Couldn't match type ‘b0’ with ‘b’

-      ‘b0’ is untouchable

-        inside the constraints: a ~ '(b0, c0)

-        bound by the type of the constructor ‘Want’:

-                   (a ~ '(b0, c0)) => Proxy b0

-        at T9222.hs:13:3

-      ‘b’ is a rigid type variable bound by

-          the type of the constructor ‘Want’:

-            ((a ~ '(b, c)) => Proxy b) -> Want a

-          at T9222.hs:13:3

-    Expected type: '(b, c)

-      Actual type: a

-    In the ambiguity check for the type of the constructor ‘Want’:

-      Want :: forall (k :: BOX)

-                     (k1 :: BOX)

-                     (a :: (,) k k1)

-                     (b :: k)

-                     (c :: k1).

-              ((a ~ '(b, c)) => Proxy b) -> Want a

-    To defer the ambiguity check to use sites, enable AllowAmbiguousTypes

-    In the definition of data constructor ‘Want’

-    In the data type declaration for ‘Want’

+
+T9222.hs:13:3: error:
+    Couldn't match type ‘b0’ with ‘b’
+      ‘b0’ is untouchable
+        inside the constraints: a ~ '(b0, c0)
+        bound by the type of the constructor ‘Want’:
+                   (a ~ '(b0, c0)) => Proxy b0
+        at T9222.hs:13:3
+    ‘b’ is a rigid type variable bound by
+        the type of the constructor ‘Want’:
+          ((a ~ '(b, c)) => Proxy b) -> Want a
+        at T9222.hs:13:3
+    Expected type: '(b, c)
+      Actual type: a
+    In the ambiguity check for the type of the constructor ‘Want’:
+      Want :: forall (k :: BOX)
+                     (k1 :: BOX)
+                     (a :: (,) k k1)
+                     (b :: k)
+                     (c :: k1).
+              ((a ~ '(b, c)) => Proxy b) -> Want a
+    To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
+    In the definition of data constructor ‘Want’
+    In the data type declaration for ‘Want’