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

2 files changed, 85 insertions, 85 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