Add kind equalities to GHC.

This implements the ideas originally put forward in
"System FC with Explicit Kind Equality" (ICFP'13).

There are several noteworthy changes with this patch:
 * We now have casts in types. These change the kind
   of a type. See new constructor `CastTy`.

 * All types and all constructors can be promoted.
   This includes GADT constructors. GADT pattern matches
   take place in type family equations. In Core,
   types can now be applied to coercions via the
   `CoercionTy` constructor.

 * Coercions can now be heterogeneous, relating types
   of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2`
   proves both that `t1` and `t2` are the same and also that
   `k1` and `k2` are the same.

 * The `Coercion` type has been significantly enhanced.
   The documentation in `docs/core-spec/core-spec.pdf` reflects
   the new reality.

 * The type of `*` is now `*`. No more `BOX`.

 * Users can write explicit kind variables in their code,
   anywhere they can write type variables. For backward compatibility,
   automatic inference of kind-variable binding is still permitted.

 * The new extension `TypeInType` turns on the new user-facing
   features.

 * Type families and synonyms are now promoted to kinds. This causes
   trouble with parsing `*`, leading to the somewhat awkward new
   `HsAppsTy` constructor for `HsType`. This is dispatched with in
   the renamer, where the kind `*` can be told apart from a
   type-level multiplication operator. Without `-XTypeInType` the
   old behavior persists. With `-XTypeInType`, you need to import
   `Data.Kind` to get `*`, also known as `Type`.

 * The kind-checking algorithms in TcHsType have been significantly
   rewritten to allow for enhanced kinds.

 * The new features are still quite experimental and may be in flux.

 * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203.

 * TODO: Update user manual.

Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142.
Updates Haddock submodule.

13 files changed, 129 insertions, 128 deletions

diff --git a/testsuite/tests/typecheck/should_compile/T5581.hs b/testsuite/tests/typecheck/should_compile/T5581.hs
index 074a2babcd..f7762831b3 100644
--- a/testsuite/tests/typecheck/should_compile/T5581.hs
+++ b/testsuite/tests/typecheck/should_compile/T5581.hs
@@ -3,7 +3,7 @@
 
 module TcShouldTerminate where
 
-import GHC.Prim (Constraint)
+import Data.Kind (Constraint)
 
 class C (p :: Constraint)
 class D (p :: Constraint)
diff --git a/testsuite/tests/typecheck/should_compile/T5655.hs b/testsuite/tests/typecheck/should_compile/T5655.hs
index c2eed90abc..8db7a485a3 100644
--- a/testsuite/tests/typecheck/should_compile/T5655.hs
+++ b/testsuite/tests/typecheck/should_compile/T5655.hs
@@ -1,7 +1,7 @@
 {-# LANGUAGE TypeFamilies, GADTs, ConstraintKinds, RankNTypes #-}
 module T5655 where
 
-import GHC.Prim (Constraint)
+import Data.Kind (Constraint)
 
 class Show a => Twice a where twice :: a -> a
 
diff --git a/testsuite/tests/typecheck/should_compile/T9834.stderr b/testsuite/tests/typecheck/should_compile/T9834.stderr
index 3ce53a0c51..b3a6240a6b 100644
--- a/testsuite/tests/typecheck/should_compile/T9834.stderr
+++ b/testsuite/tests/typecheck/should_compile/T9834.stderr
@@ -1,71 +1,71 @@
-

-T9834.hs:23:10: warning:

-    Couldn't match type ‘p’ with ‘(->) (p a0)’

-    ‘p’ is a rigid type variable bound by

-      the class declaration for ‘ApplicativeFix’ at T9834.hs:21:39

-    Expected type: (forall (q :: * -> *).

-                    Applicative q =>

-                    Comp p q a -> Comp p q a)

-                   -> p a

-      Actual type: (forall (q :: * -> *).

-                    Applicative q =>

-                    Nat (Comp p q) (Comp p q))

-                   -> p a0 -> p a0

-    In the expression: wrapIdComp

-    In an equation for ‘afix’: afix = wrapIdComp

-    Relevant bindings include

-      afix :: (forall (q :: * -> *).

-               Applicative q =>

-               Comp p q a -> Comp p q a)

-              -> p a

-        (bound at T9834.hs:23:3)

-

-T9834.hs:23:10: warning:

-    Couldn't match type ‘a’ with ‘p a0’

-    ‘a’ is a rigid type variable bound by

-      the type signature for:

-        afix :: forall a.

-                (forall (q :: * -> *). Applicative q => Comp p q a -> Comp p q a)

-                -> p a

-      at T9834.hs:22:11

-    Expected type: (forall (q :: * -> *).

-                    Applicative q =>

-                    Comp p q a -> Comp p q a)

-                   -> p a

-      Actual type: (forall (q :: * -> *).

-                    Applicative q =>

-                    Nat (Comp p q) (Comp p q))

-                   -> p a0 -> p a0

-    In the expression: wrapIdComp

-    In an equation for ‘afix’: afix = wrapIdComp

-    Relevant bindings include

-      afix :: (forall (q :: * -> *).

-               Applicative q =>

-               Comp p q a -> Comp p q a)

-              -> p a

-        (bound at T9834.hs:23:3)

-

-T9834.hs:23:10: warning:

-    Couldn't match type ‘a’ with ‘a1’

-    ‘a’ is a rigid type variable bound by

-      the type signature for:

-        afix :: forall a.

-                (forall (q :: * -> *). Applicative q => Comp p q a -> Comp p q a)

-                -> p a

-      at T9834.hs:22:11

-    ‘a1’ is a rigid type variable bound by

-      a type expected by the context:

-        forall (q :: * -> *) a1.

-        Applicative q =>

-        Comp p q a1 -> Comp p q a1

-      at T9834.hs:23:10

-    Expected type: Comp p q a1 -> Comp p q a1

-      Actual type: Comp p q a -> Comp p q a

-    In the expression: wrapIdComp

-    In an equation for ‘afix’: afix = wrapIdComp

-    Relevant bindings include

-      afix :: (forall (q :: * -> *).

-               Applicative q =>

-               Comp p q a -> Comp p q a)

-              -> p a

-        (bound at T9834.hs:23:3)

+
+T9834.hs:23:10: warning:
+    • Couldn't match type ‘a’ with ‘p a0’
+      ‘a’ is a rigid type variable bound by
+        the type signature for:
+          afix :: forall a.
+                  (forall (q :: * -> *). Applicative q => Comp p q a -> Comp p q a)
+                  -> p a
+        at T9834.hs:22:11
+         Expected type: (forall (q :: * -> *).
+                         Applicative q =>
+                         Comp p q a -> Comp p q a)
+                        -> p a
+           Actual type: (forall (q :: * -> *).
+                         Applicative q =>
+                         Nat (Comp p q) (Comp p q))
+                        -> p a0 -> p a0
+    • In the expression: wrapIdComp
+      In an equation for ‘afix’: afix = wrapIdComp
+    • Relevant bindings include
+        afix :: (forall (q :: * -> *).
+                 Applicative q =>
+                 Comp p q a -> Comp p q a)
+                -> p a
+          (bound at T9834.hs:23:3)
+
+T9834.hs:23:10: warning:
+    • Couldn't match type ‘p’ with ‘(->) (p a0)’
+      ‘p’ is a rigid type variable bound by
+        the class declaration for ‘ApplicativeFix’ at T9834.hs:21:39
+         Expected type: (forall (q :: * -> *).
+                         Applicative q =>
+                         Comp p q a -> Comp p q a)
+                        -> p a
+           Actual type: (forall (q :: * -> *).
+                         Applicative q =>
+                         Nat (Comp p q) (Comp p q))
+                        -> p a0 -> p a0
+    • In the expression: wrapIdComp
+      In an equation for ‘afix’: afix = wrapIdComp
+    • Relevant bindings include
+        afix :: (forall (q :: * -> *).
+                 Applicative q =>
+                 Comp p q a -> Comp p q a)
+                -> p a
+          (bound at T9834.hs:23:3)
+
+T9834.hs:23:10: warning:
+    • Couldn't match type ‘a’ with ‘a1’
+      ‘a’ is a rigid type variable bound by
+        the type signature for:
+          afix :: forall a.
+                  (forall (q :: * -> *). Applicative q => Comp p q a -> Comp p q a)
+                  -> p a
+        at T9834.hs:22:11
+      ‘a1’ is a rigid type variable bound by
+        a type expected by the context:
+          forall (q :: * -> *) a1.
+          Applicative q =>
+          Comp p q a1 -> Comp p q a1
+        at T9834.hs:23:10
+         Expected type: Comp p q a1 -> Comp p q a1
+           Actual type: Comp p q a -> Comp p q a
+    • In the expression: wrapIdComp
+      In an equation for ‘afix’: afix = wrapIdComp
+    • Relevant bindings include
+        afix :: (forall (q :: * -> *).
+                 Applicative q =>
+                 Comp p q a -> Comp p q a)
+                -> p a
+          (bound at T9834.hs:23:3)
diff --git a/testsuite/tests/typecheck/should_compile/T9939.stderr b/testsuite/tests/typecheck/should_compile/T9939.stderr
index 86decf0a5e..106335e8ba 100644
--- a/testsuite/tests/typecheck/should_compile/T9939.stderr
+++ b/testsuite/tests/typecheck/should_compile/T9939.stderr
@@ -1,20 +1,20 @@
-

-T9939.hs:5:1: warning:

-    Redundant constraint: Eq a

-    In the type signature for:

-         f1 :: (Eq a, Ord a) => a -> a -> Bool

-

-T9939.hs:9:1: warning:

-    Redundant constraint: Eq a

-    In the type signature for:

-         f2 :: (Eq a, Ord a) => a -> a -> Bool

-

-T9939.hs:13:1: warning:

-    Redundant constraint: Eq b

-    In the type signature for:

-         f3 :: (Eq a, a ~ b, Eq b) => a -> b -> Bool

-

-T9939.hs:20:1: warning:

-    Redundant constraint: Eq b

-    In the type signature for:

-         f4 :: (Eq a, Eq b) => a -> b -> Equal a b -> Bool

+
+T9939.hs:5:1: warning:
+    • Redundant constraint: Eq a
+    • In the type signature for:
+           f1 :: (Eq a, Ord a) => a -> a -> Bool
+
+T9939.hs:9:1: warning:
+    • Redundant constraint: Eq a
+    • In the type signature for:
+           f2 :: (Eq a, Ord a) => a -> a -> Bool
+
+T9939.hs:13:1: warning:
+    • Redundant constraint: Eq b
+    • In the type signature for:
+           f3 :: (Eq a, a ~ b, Eq b) => a -> b -> Bool
+
+T9939.hs:20:1: warning:
+    • Redundant constraint: Eq a
+    • In the type signature for:
+           f4 :: (Eq a, Eq b) => a -> b -> Equal a b -> Bool
diff --git a/testsuite/tests/typecheck/should_compile/tc141.stderr b/testsuite/tests/typecheck/should_compile/tc141.stderr
index b5ee77b689..96858b1d3c 100644
--- a/testsuite/tests/typecheck/should_compile/tc141.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc141.stderr
@@ -7,11 +7,11 @@ tc141.hs:11:12: error:
       In a pattern binding: (p :: a, q :: a) = x
 
 tc141.hs:11:31: error:
-    • Couldn't match expected type ‘a1’ with actual type ‘a’
-        because type variable ‘a1’ would escape its scope
+    • 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:
-          a1
+          a2
         at tc141.hs:11:31-34
     • In the expression: q :: a
       In the expression: (q :: a, p)
@@ -19,7 +19,7 @@ tc141.hs:11:31: error:
         p :: a (bound at tc141.hs:11:12)
         q :: a (bound at tc141.hs:11:17)
         x :: (a, a) (bound at tc141.hs:11:3)
-        f :: (a, a) -> (t, a) (bound at tc141.hs:11:1)
+        f :: (a, a) -> (a1, a) (bound at tc141.hs:11:1)
 
 tc141.hs:13:13: error:
     • You cannot bind scoped type variable ‘a’
@@ -34,15 +34,15 @@ tc141.hs:13:13: error:
         in v
 
 tc141.hs:15:18: error:
-    • Couldn't match expected type ‘a2’ with actual type ‘t’
-        because type variable ‘a2’ would escape its scope
+    • Couldn't match expected type ‘a1’ with actual type ‘r1’
+        because type variable ‘a1’ would escape its scope
       This (rigid, skolem) type variable is bound by
         the type signature for:
-          v :: a2
+          v :: a1
         at tc141.hs:14:14-19
     • In the expression: b
       In an equation for ‘v’: v = b
     • Relevant bindings include
-        v :: a2 (bound at tc141.hs:15:14)
-        b :: t (bound at tc141.hs:13:5)
-        g :: a -> t -> a1 (bound at tc141.hs:13:1)
+        v :: a1 (bound at tc141.hs:15:14)
+        b :: r1 (bound at tc141.hs:13:5)
+        g :: r -> r1 -> a (bound at tc141.hs:13:1)
diff --git a/testsuite/tests/typecheck/should_compile/tc167.stderr b/testsuite/tests/typecheck/should_compile/tc167.stderr
index 5d869af801..634b50dd5b 100644
--- a/testsuite/tests/typecheck/should_compile/tc167.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc167.stderr
@@ -1,5 +1,6 @@
-

-tc167.hs:8:15:

-    Expecting a lifted type, but ‘Int#’ is unlifted

-    In the type ‘(->) Int#’

-    In the type declaration for ‘T’

+
+tc167.hs:8:15:
+    Expecting a lifted type, but ‘Int#’ is unlifted
+    In the first argument of ‘(->)’, namely ‘Int#’
+    In the type ‘(->) Int#’
+    In the type declaration for ‘T’
diff --git a/testsuite/tests/typecheck/should_compile/tc211.stderr b/testsuite/tests/typecheck/should_compile/tc211.stderr
index 34a35f1781..d802dffe4e 100644
--- a/testsuite/tests/typecheck/should_compile/tc211.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc211.stderr
@@ -1,5 +1,5 @@
 
-tc211.hs:17:8:
+tc211.hs:17:8: error:
     Couldn't match expected type ‘forall a. a -> a’
                 with actual type ‘a2 -> a2’
     In the expression:
@@ -10,17 +10,17 @@ tc211.hs:17:8:
          (forall a. a -> a) -> [forall a. a -> a] -> [forall a. a -> a])
         (head foo) foo
 
-tc211.hs:18:22:
+tc211.hs:18:22: error:
     Couldn't match type ‘forall a3. a3 -> a3’ with ‘a -> a’
-    Expected type: [a -> a]
-      Actual type: [forall a. a -> a]
+       Expected type: [a -> a]
+         Actual type: [forall a. a -> a]
     In the first argument of ‘head’, namely ‘foo’
     In the first argument of ‘(:) ::
                                 (forall a. a -> a)
                                 -> [forall a. a -> a] -> [forall a. a -> a]’, namely
       ‘(head foo)’
 
-tc211.hs:59:18:
+tc211.hs:59:18: error:
     Couldn't match expected type ‘forall a. a -> a’
                 with actual type ‘a1 -> a1’
     In the expression:
@@ -33,7 +33,7 @@ tc211.hs:59:18:
               (forall a. a -> a)
               -> List (forall a. a -> a) -> List (forall a. a -> a)
 
-tc211.hs:65:8:
+tc211.hs:65:8: error:
     Couldn't match expected type ‘forall a. a -> a’
                 with actual type ‘a0 -> a0’
     In the expression:
@@ -46,11 +46,11 @@ tc211.hs:65:8:
          -> List (forall a. a -> a) -> List (forall a. a -> a))
         (\ x -> x) Nil
 
-tc211.hs:73:9:
+tc211.hs:73:9: error:
     Couldn't match type ‘forall a4. a4 -> a4’ with ‘a3 -> a3’
-    Expected type: List (forall a. a -> a)
-                   -> (forall a. a -> a) -> a3 -> a3
-      Actual type: List (a3 -> a3) -> (a3 -> a3) -> a3 -> a3
+       Expected type: List (forall a. a -> a)
+                      -> (forall a. a -> a) -> a3 -> a3
+         Actual type: List (a3 -> a3) -> (a3 -> a3) -> a3 -> a3
     In the expression:
         foo2 ::
           List (forall a. a -> a) -> (forall a. a -> a) -> (forall a. a -> a)
diff --git a/testsuite/tests/typecheck/should_compile/tc231.stderr b/testsuite/tests/typecheck/should_compile/tc231.stderr
index 2377c13a0f..85ccc32954 100644
--- a/testsuite/tests/typecheck/should_compile/tc231.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc231.stderr
@@ -6,9 +6,9 @@ TYPE SIGNATURES
   s :: forall t t1. Q t (Z [Char]) t1 -> Q t (Z [Char]) t1
 TYPE CONSTRUCTORS
   data Q s a chain = Node s a chain
-    Promotable
+    Kind: * -> * -> * -> *
   data Z a = Z a
-    Promotable
+    Kind: * -> *
   class Zork s a b | a -> b where
     huh :: Q s a chain -> ST s ()
     {-# MINIMAL huh #-}
diff --git a/testsuite/tests/typecheck/should_compile/tc243.stderr b/testsuite/tests/typecheck/should_compile/tc243.stderr
index 31cc3c9fd2..98e0f5ae1e 100644
--- a/testsuite/tests/typecheck/should_compile/tc243.stderr
+++ b/testsuite/tests/typecheck/should_compile/tc243.stderr
@@ -1,3 +1,3 @@
-

-tc243.hs:10:1: Warning:

-    Top-level binding with no type signature: (.+.) :: forall t. t

+
+tc243.hs:10:1: Warning:
+    Top-level binding with no type signature: (.+.) :: forall r. r
diff --git a/testsuite/tests/typecheck/should_compile/tc255.hs b/testsuite/tests/typecheck/should_compile/tc255.hs
index d77a7b688b..e5690bb08d 100644
--- a/testsuite/tests/typecheck/should_compile/tc255.hs
+++ b/testsuite/tests/typecheck/should_compile/tc255.hs
@@ -1,7 +1,7 @@
 {-# LANGUAGE TypeFamilies, ConstraintKinds, UndecidableInstances #-}
 module Ctx where
 
-import GHC.Prim( Constraint )
+import Data.Kind ( Constraint )
 
 type family Indirect :: * -> Constraint
 type instance Indirect = Show
diff --git a/testsuite/tests/typecheck/should_compile/tc256.hs b/testsuite/tests/typecheck/should_compile/tc256.hs
index f06eabf1c3..d33f7a6401 100644
--- a/testsuite/tests/typecheck/should_compile/tc256.hs
+++ b/testsuite/tests/typecheck/should_compile/tc256.hs
@@ -1,7 +1,7 @@
 {-# LANGUAGE TypeFamilies, ConstraintKinds, UndecidableInstances #-}
 module Ctx where
 
-import GHC.Prim( Constraint )
+import Data.Kind ( Constraint )
 
 type family Indirect :: * -> Constraint
 type instance Indirect = Show
diff --git a/testsuite/tests/typecheck/should_compile/tc257.hs b/testsuite/tests/typecheck/should_compile/tc257.hs
index efab2df224..d5742aa779 100644
--- a/testsuite/tests/typecheck/should_compile/tc257.hs
+++ b/testsuite/tests/typecheck/should_compile/tc257.hs
@@ -1,7 +1,7 @@
 {-# LANGUAGE KindSignatures, ConstraintKinds, MultiParamTypeClasses, FlexibleInstances, UndecidableInstances #-}
 module Ctx where
 
-import GHC.Prim( Constraint )
+import Data.Kind ( Constraint )
 
 data Proxy (ctxt :: * -> Constraint) = Proxy
 
@@ -22,4 +22,4 @@ instance ctxt Int => Foo ctxt Int where
 -- from the context (ctxt Int)
 
 -- The problem was that irreducible evidence did not interact with
--- evidence of equal type.
\ No newline at end of file
+-- evidence of equal type.
diff --git a/testsuite/tests/typecheck/should_compile/tc258.hs b/testsuite/tests/typecheck/should_compile/tc258.hs
index 353ec94c43..a4dca19526 100644
--- a/testsuite/tests/typecheck/should_compile/tc258.hs
+++ b/testsuite/tests/typecheck/should_compile/tc258.hs
@@ -2,7 +2,7 @@
 
 module AltPrelude where
 
-import GHC.Prim (Constraint)
+import Data.Kind (Constraint)
 
 class MyFunctor f where
        type FunctorCtxt f a :: Constraint