TcHsType.lhs 52.8 KB
Newer Older
1 2
%
% (c) The University of Glasgow 2006
3 4 5 6 7
% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
\section[TcMonoType]{Typechecking user-specified @MonoTypes@}

\begin{code}
Ian Lynagh's avatar
Ian Lynagh committed
8 9 10 11 12 13 14
{-# OPTIONS -fno-warn-tabs #-}
-- The above warning supression flag is a temporary kludge.
-- While working on this module you are encouraged to remove it and
-- detab the module (please do the detabbing in a separate patch). See
--     http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#TabsvsSpaces
-- for details

15
module TcHsType (
16
	tcHsSigType, tcHsSigTypeNC, tcHsDeriv, tcHsVectInst, 
17
	tcHsInstHead, tcHsQuantifiedType,
18 19 20 21
	UserTypeCtxt(..), 

		-- Kind checking
	kcHsTyVars, kcHsSigType, kcHsLiftedSigType, 
22
	kcLHsType, kcCheckLHsType, kcHsContext, kcApps,
dreixel's avatar
dreixel committed
23 24 25 26 27 28 29 30 31 32
        kindGeneralizeKind, kindGeneralizeKinds,

		-- Sort checking
	scDsLHsKind, scDsLHsMaybeKind,

                -- Typechecking kinded types
	tcHsType, tcCheckHsType,
        tcHsKindedContext, tcHsKindedType, tcHsBangType,
	tcTyVarBndrs, tcTyVarBndrsKindGen, dsHsType,
	tcDataKindSig, tcTyClTyVars,
batterseapower's avatar
batterseapower committed
33

dreixel's avatar
dreixel committed
34
        ExpKind(..), ekConstraint, expArgKind, checkExpectedKind,
35

36 37
		-- Pattern type signatures
	tcHsPatSigType, tcPatSig
38 39 40 41
   ) where

#include "HsVersions.h"

42 43 44 45
#ifdef GHCI 	/* Only if bootstrapped */
import {-# SOURCE #-}	TcSplice( kcSpliceType )
#endif

46 47
import HsSyn
import RnHsSyn
48
import TcRnMonad
dreixel's avatar
dreixel committed
49 50
import RnEnv   ( polyKindsErr )
import TcHsSyn ( mkZonkTcTyVar )
51
import TcEvidence( HsWrapper )
52 53 54 55 56 57
import TcEnv
import TcMType
import TcUnify
import TcIface
import TcType
import {- Kind parts of -} Type
dreixel's avatar
dreixel committed
58
import Kind
59
import Var
60
import VarSet
61
import TyCon
dreixel's avatar
dreixel committed
62 63
import DataCon ( DataCon, dataConUserType )
import TysPrim ( liftedTypeKindTyConName, constraintKindTyConName )
64
import Class
dreixel's avatar
dreixel committed
65
import RdrName ( rdrNameSpace, nameRdrName )
66
import Name
67
import NameSet
68 69 70
import TysWiredIn
import BasicTypes
import SrcLoc
dreixel's avatar
dreixel committed
71
import DynFlags ( ExtensionFlag( Opt_DataKinds ) )
72
import Util
73
import UniqSupply
74
import Outputable
dreixel's avatar
dreixel committed
75
import BuildTyCl ( buildPromotedDataTyCon )
76
import FastString
dreixel's avatar
dreixel committed
77
import Control.Monad ( unless )
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
\end{code}


	----------------------------
		General notes
	----------------------------

Generally speaking we now type-check types in three phases

  1.  kcHsType: kind check the HsType
	*includes* performing any TH type splices;
	so it returns a translated, and kind-annotated, type

  2.  dsHsType: convert from HsType to Type:
	perform zonking
	expand type synonyms [mkGenTyApps]
	hoist the foralls [tcHsType]

  3.  checkValidType: check the validity of the resulting type

Often these steps are done one after the other (tcHsSigType).
But in mutually recursive groups of type and class decls we do
	1 kind-check the whole group
	2 build TyCons/Classes in a knot-tied way
	3 check the validity of types in the now-unknotted TyCons/Classes

For example, when we find
	(forall a m. m a -> m a)
we bind a,m to kind varibles and kind-check (m a -> m a).  This makes
a get kind *, and m get kind *->*.  Now we typecheck (m a -> m a) in
an environment that binds a and m suitably.

The kind checker passed to tcHsTyVars needs to look at enough to
establish the kind of the tyvar:
  * For a group of type and class decls, it's just the group, not
	the rest of the program
  * For a tyvar bound in a pattern type signature, its the types
	mentioned in the other type signatures in that bunch of patterns
  * For a tyvar bound in a RULE, it's the type signatures on other
	universally quantified variables in the rule

Note that this may occasionally give surprising results.  For example:

	data T a b = MkT (a b)

Here we deduce			a::*->*,       b::*
But equally valid would be	a::(*->*)-> *, b::*->*


Validity checking
~~~~~~~~~~~~~~~~~
Some of the validity check could in principle be done by the kind checker, 
but not all:

- During desugaring, we normalise by expanding type synonyms.  Only
  after this step can we check things like type-synonym saturation
  e.g. 	type T k = k Int
	type S a = a
  Then (T S) is ok, because T is saturated; (T S) expands to (S Int);
  and then S is saturated.  This is a GHC extension.

- Similarly, also a GHC extension, we look through synonyms before complaining
  about the form of a class or instance declaration

- Ambiguity checks involve functional dependencies, and it's easier to wait
  until knots have been resolved before poking into them

Also, in a mutually recursive group of types, we can't look at the TyCon until we've
finished building the loop.  So to keep things simple, we postpone most validity
checking until step (3).

Knot tying
~~~~~~~~~~
During step (1) we might fault in a TyCon defined in another module, and it might
(via a loop) refer back to a TyCon defined in this module. So when we tie a big
knot around type declarations with ARecThing, so that the fault-in code can get
the TyCon being defined.


%************************************************************************
%*									*
\subsection{Checking types}
%*									*
%************************************************************************

\begin{code}
164
tcHsSigType, tcHsSigTypeNC :: UserTypeCtxt -> LHsType Name -> TcM Type
165
  -- Do kind checking, and hoist for-alls to the top
166 167 168
  -- NB: it's important that the foralls that come from the top-level
  --	 HsForAllTy in hs_ty occur *first* in the returned type.
  --     See Note [Scoped] with TcSigInfo
169
tcHsSigType ctxt hs_ty 
170
  = addErrCtxt (pprHsSigCtxt ctxt hs_ty) $
171 172 173
    tcHsSigTypeNC ctxt hs_ty

tcHsSigTypeNC ctxt hs_ty
dreixel's avatar
dreixel committed
174 175
  = do  { kinded_ty <- case expectedKindInCtxt ctxt of
                         Nothing -> fmap fst (kc_lhs_type_fresh hs_ty)
dreixel's avatar
dreixel committed
176
                         Just k  -> kc_lhs_type hs_ty (EK k (ptext (sLit "Expected")))
177 178 179 180 181
          -- The kind is checked by checkValidType, and isn't necessarily
          -- of kind * in a Template Haskell quote eg [t| Maybe |]
        ; ty <- tcHsKindedType kinded_ty
        ; checkValidType ctxt ty
        ; return ty }
182

dreixel's avatar
dreixel committed
183 184 185
-- Like tcHsType, but takes an expected kind
tcCheckHsType :: LHsType Name -> Kind -> TcM Type
tcCheckHsType hs_ty exp_kind
dreixel's avatar
dreixel committed
186
  = do { kinded_ty <- kcCheckLHsType hs_ty (EK exp_kind (ptext (sLit "Expected")))
dreixel's avatar
dreixel committed
187 188 189 190 191 192 193
       ; ty <- tcHsKindedType kinded_ty
       ; return ty }

tcHsType :: LHsType Name -> TcM Type
-- kind check and desugar
-- no validity checking because of knot-tying
tcHsType hs_ty
dreixel's avatar
dreixel committed
194
  = do { (kinded_ty, _) <- kc_lhs_type_fresh hs_ty
dreixel's avatar
dreixel committed
195 196 197 198
       ; ty <- tcHsKindedType kinded_ty
       ; return ty }

tcHsInstHead :: UserTypeCtxt -> LHsType Name -> TcM ([TyVar], ThetaType, Class, [Type])
199 200
-- Typecheck an instance head.  We can't use 
-- tcHsSigType, because it's not a valid user type.
dreixel's avatar
dreixel committed
201
tcHsInstHead ctxt lhs_ty@(L loc hs_ty)
202
  = setSrcSpan loc   $	-- No need for an "In the type..." context
203
                        -- because that comes from the caller
dreixel's avatar
dreixel committed
204
    do { kinded_ty <- kc_hs_type hs_ty ekConstraint
dreixel's avatar
dreixel committed
205 206 207 208 209 210
       ; ty <- ds_type kinded_ty
       ; let (tvs, theta, tau) = tcSplitSigmaTy ty
       ; case getClassPredTys_maybe tau of
           Nothing          -> failWithTc (ptext (sLit "Malformed instance type"))
           Just (clas,tys)  -> do { checkValidInstance ctxt lhs_ty tvs theta clas tys
                                  ; return (tvs, theta, clas, tys) } }
211 212 213 214 215 216 217 218 219 220 221

tcHsQuantifiedType :: [LHsTyVarBndr Name] -> LHsType Name -> TcM ([TyVar], Type)
-- Behave very like type-checking (HsForAllTy sig_tvs hs_ty),
-- except that we want to keep the tvs separate
tcHsQuantifiedType tv_names hs_ty
  = kcHsTyVars tv_names $ \ tv_names' ->
    do	{ kc_ty <- kcHsSigType hs_ty
    	; tcTyVarBndrs tv_names' $ \ tvs ->
    do	{ ty <- dsHsType kc_ty
    	; return (tvs, ty) } }

222
-- Used for the deriving(...) items
223 224
tcHsDeriv :: HsType Name -> TcM ([TyVar], Class, [Type])
tcHsDeriv = tc_hs_deriv []
225

Ian Lynagh's avatar
Ian Lynagh committed
226 227
tc_hs_deriv :: [LHsTyVarBndr Name] -> HsType Name
            -> TcM ([TyVar], Class, [Type])
228 229 230 231 232 233
tc_hs_deriv tv_names1 (HsForAllTy _ tv_names2 (L _ []) (L _ ty))
  = 	-- Funny newtype deriving form
	-- 	forall a. C [a]
	-- where C has arity 2.  Hence can't use regular functions
    tc_hs_deriv (tv_names1 ++ tv_names2) ty

batterseapower's avatar
batterseapower committed
234 235 236 237 238
tc_hs_deriv tv_names ty
  | Just (cls_name, hs_tys) <- splitHsClassTy_maybe ty
  = kcHsTyVars tv_names                 $ \ tv_names' ->
    do  { cls_kind <- kcClass cls_name
        ; (tys, _res_kind) <- kcApps cls_name cls_kind hs_tys
dreixel's avatar
dreixel committed
239
        ; tcTyVarBndrsKindGen tv_names'        $ \ tyvars ->
batterseapower's avatar
batterseapower committed
240 241 242 243 244 245
    do  { arg_tys <- dsHsTypes tys
        ; cls <- tcLookupClass cls_name
        ; return (tyvars, cls, arg_tys) }}

  | otherwise
  = failWithTc (ptext (sLit "Illegal deriving item") <+> ppr ty)
246 247 248 249 250 251 252 253 254 255 256 257 258 259

-- Used for 'VECTORISE [SCALAR] instance' declarations
--
tcHsVectInst :: LHsType Name -> TcM (Class, [Type])
tcHsVectInst ty
  | Just (L _ cls_name, tys) <- splitLHsClassTy_maybe ty
  = do { cls_kind <- kcClass cls_name
       ; (tys, _res_kind) <- kcApps cls_name cls_kind tys
       ; arg_tys <- dsHsTypes tys
       ; cls <- tcLookupClass cls_name
       ; return (cls, arg_tys)
       }
  | otherwise
  = failWithTc $ ptext (sLit "Malformed instance type")
260 261 262 263 264 265 266
\end{code}

	These functions are used during knot-tying in
	type and class declarations, when we have to
 	separate kind-checking, desugaring, and validity checking

\begin{code}
267
kcHsSigType, kcHsLiftedSigType :: LHsType Name -> TcM (LHsType Name)
268
	-- Used for type signatures
dreixel's avatar
dreixel committed
269
kcHsSigType ty 	     = addKcTypeCtxt ty $ kcArgType ty
270
kcHsLiftedSigType ty = addKcTypeCtxt ty $ kcLiftedType ty
271

272
tcHsKindedType :: LHsType Name -> TcM Type
273
  -- Don't do kind checking, nor validity checking.
274 275 276
  -- This is used in type and class decls, where kinding is
  -- done in advance, and validity checking is done later
  -- [Validity checking done later because of knot-tying issues.]
277
tcHsKindedType hs_ty = dsHsType hs_ty
278

279 280
tcHsBangType :: LHsType Name -> TcM Type
-- Permit a bang, but discard it
dreixel's avatar
dreixel committed
281
-- Input type has already been kind-checked
Ian Lynagh's avatar
Ian Lynagh committed
282 283
tcHsBangType (L _ (HsBangTy _ ty)) = tcHsKindedType ty
tcHsBangType ty                    = tcHsKindedType ty
284

285
tcHsKindedContext :: LHsContext Name -> TcM ThetaType
286 287
-- Used when we are expecting a ClassContext (i.e. no implicit params)
-- Does not do validity checking, like tcHsKindedType
batterseapower's avatar
batterseapower committed
288
tcHsKindedContext hs_theta = addLocM (mapM dsHsType) hs_theta
289 290 291 292 293 294 295 296 297 298 299 300 301
\end{code}


%************************************************************************
%*									*
		The main kind checker: kcHsType
%*									*
%************************************************************************
	
	First a couple of simple wrappers for kcHsType

\begin{code}
---------------------------
302
kcLiftedType :: LHsType Name -> TcM (LHsType Name)
303
-- The type ty must be a *lifted* *type*
dreixel's avatar
dreixel committed
304
kcLiftedType ty = kc_lhs_type ty ekLifted
305
    
306 307
kcArgs :: SDoc -> [LHsType Name] -> Kind -> TcM [LHsType Name]
kcArgs what tys kind 
dreixel's avatar
dreixel committed
308
  = sequence [ kc_lhs_type ty (expArgKind what kind n)
309 310
             | (ty,n) <- tys `zip` [1..] ]

dreixel's avatar
dreixel committed
311 312 313
---------------------------
kcArgType :: LHsType Name -> TcM (LHsType Name)
-- The type ty must be an *arg* *type* (lifted or unlifted)
dreixel's avatar
dreixel committed
314
kcArgType ty = kc_lhs_type ty ekArg
dreixel's avatar
dreixel committed
315

316
---------------------------
317
kcCheckLHsType :: LHsType Name -> ExpKind -> TcM (LHsType Name)
dreixel's avatar
dreixel committed
318
kcCheckLHsType ty kind = addKcTypeCtxt ty $ kc_lhs_type ty kind
319 320
\end{code}

dreixel's avatar
dreixel committed
321 322 323 324
Like tcExpr, kc_hs_type takes an expected kind which it unifies with
the kind it figures out. When we don't know what kind to expect, we use
kc_lhs_type_fresh, to first create a new meta kind variable and use that as
the expected kind.
325 326

\begin{code}
327 328
kcLHsType :: LHsType Name -> TcM (LHsType Name, TcKind)
-- Called from outside: set the context
dreixel's avatar
dreixel committed
329 330 331 332 333
kcLHsType ty = addKcTypeCtxt ty (kc_lhs_type_fresh ty)

kc_lhs_type_fresh :: LHsType Name -> TcM (LHsType Name, TcKind)
kc_lhs_type_fresh ty =  do
  kv <- newMetaKindVar
dreixel's avatar
dreixel committed
334
  r <- kc_lhs_type ty (EK kv (ptext (sLit "Expected")))
dreixel's avatar
dreixel committed
335
  return (r, kv)
336

dreixel's avatar
dreixel committed
337 338 339 340 341
kc_lhs_types :: [(LHsType Name, ExpKind)] -> TcM [LHsType Name]
kc_lhs_types tys_w_kinds = mapM (uncurry kc_lhs_type) tys_w_kinds

kc_lhs_type :: LHsType Name -> ExpKind -> TcM (LHsType Name)
kc_lhs_type (L span ty) exp_kind
342
  = setSrcSpan span $
dreixel's avatar
dreixel committed
343 344 345
    do { traceTc "kc_lhs_type" (ppr ty <+> ppr exp_kind)
       ; ty' <- kc_hs_type ty exp_kind
       ; return (L span ty') }
346

dreixel's avatar
dreixel committed
347 348 349 350
kc_hs_type :: HsType Name -> ExpKind -> TcM (HsType Name)
kc_hs_type (HsParTy ty) exp_kind = do
   ty' <- kc_lhs_type ty exp_kind
   return (HsParTy ty')
351

352 353 354 355
kc_hs_type (HsTyVar name) exp_kind = do
   (ty, k) <- kcTyVar name
   checkExpectedKind ty k exp_kind
   return ty
356

dreixel's avatar
dreixel committed
357
kc_hs_type (HsListTy ty) exp_kind = do
358
    ty' <- kcLiftedType ty
dreixel's avatar
dreixel committed
359 360
    checkExpectedKind ty liftedTypeKind exp_kind
    return (HsListTy ty')
361

dreixel's avatar
dreixel committed
362
kc_hs_type (HsPArrTy ty) exp_kind = do
363
    ty' <- kcLiftedType ty
dreixel's avatar
dreixel committed
364 365
    checkExpectedKind ty liftedTypeKind exp_kind
    return (HsPArrTy ty')
366

dreixel's avatar
dreixel committed
367 368
kc_hs_type (HsKindSig ty sig_k) exp_kind = do
    sig_k' <- scDsLHsKind sig_k
dreixel's avatar
dreixel committed
369 370
    ty' <- kc_lhs_type ty
             (EK sig_k' (ptext (sLit "An enclosing kind signature specified")))
dreixel's avatar
dreixel committed
371 372
    checkExpectedKind ty sig_k' exp_kind
    return (HsKindSig ty' sig_k)
373

dreixel's avatar
dreixel committed
374
-- See Note [Distinguishing tuple kinds] in HsTypes
dreixel's avatar
dreixel committed
375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
kc_hs_type ty@(HsTupleTy HsBoxedOrConstraintTuple tys) exp_kind@(EK exp_k _ctxt)
  | isConstraintOrLiftedKind exp_k -- (NB: not zonking, to avoid left-right bias)
  = do { tys' <- kcArgs (ptext (sLit "a tuple")) tys exp_k
       ; return $ if isConstraintKind exp_k
                    then HsTupleTy HsConstraintTuple tys'
                    else HsTupleTy HsBoxedTuple      tys' }
  | otherwise
  -- It is not clear from the context if it's * or Constraint, 
  -- so we infer the kind from the arguments
  = do { k <- newMetaKindVar
       ; tys' <- kcArgs (ptext (sLit "a tuple")) tys k 
       ; k' <- zonkTcKind k
       ; if isConstraintKind k'
         then do { checkExpectedKind ty k' exp_kind
                 ; return (HsTupleTy HsConstraintTuple tys') }
         -- If it's not clear from the arguments that it's Constraint, then
         -- it must be *. Check the arguments again to give good error messages
         -- in eg. `(Maybe, Maybe)`
         else do { tys'' <- kcArgs (ptext (sLit "a tuple")) tys liftedTypeKind
                 ; checkExpectedKind ty liftedTypeKind exp_kind
                 ; return (HsTupleTy HsBoxedTuple tys'') } }
{-
Note that we will still fail to infer the correct kind in this case:

  type T a = ((a,a), D a)
  type family D :: Constraint -> Constraint

While kind checking T, we do not yet know the kind of D, so we will default the
kind of T to * -> *. It works if we annotate `a` with kind `Constraint`.
-}

kc_hs_type ty@(HsTupleTy tup_sort tys) exp_kind
  = do { tys' <- kcArgs cxt_doc tys arg_kind
       ; checkExpectedKind ty out_kind exp_kind
       ; return (HsTupleTy tup_sort tys') }
  where
    arg_kind = case tup_sort of
                 HsBoxedTuple      -> liftedTypeKind
                 HsUnboxedTuple    -> argTypeKind
                 HsConstraintTuple -> constraintKind
                 _                 -> panic "kc_hs_type arg_kind"
    out_kind = case tup_sort of
                 HsUnboxedTuple    -> ubxTupleKind
                 _                 -> arg_kind
    cxt_doc = case tup_sort of
                 HsBoxedTuple      -> ptext (sLit "a tuple")
                 HsUnboxedTuple    -> ptext (sLit "an unboxed tuple")
                 HsConstraintTuple -> ptext (sLit "a constraint tuple")
                 _                 -> panic "kc_hs_type tup_sort"
424

dreixel's avatar
dreixel committed
425 426 427
kc_hs_type ty@(HsFunTy ty1 ty2) exp_kind@(EK _ ctxt) = do
    ty1' <- kc_lhs_type ty1 (EK argTypeKind  ctxt)
    ty2' <- kc_lhs_type ty2 (EK openTypeKind ctxt)
dreixel's avatar
dreixel committed
428
    checkExpectedKind ty liftedTypeKind exp_kind
dreixel's avatar
dreixel committed
429
    return (HsFunTy ty1' ty2')
430

dreixel's avatar
dreixel committed
431
kc_hs_type ty@(HsOpTy ty1 (_, l_op@(L loc op)) ty2) exp_kind = do
dreixel's avatar
dreixel committed
432
    (wop, op_kind) <- kcTyVar op
dreixel's avatar
dreixel committed
433
    [ty1',ty2'] <- kcCheckApps l_op op_kind [ty1,ty2] ty exp_kind
dreixel's avatar
dreixel committed
434 435 436 437
    let op' = case wop of
                HsTyVar name -> (WpKiApps [], L loc name)
                HsWrapTy wrap (HsTyVar name) -> (wrap, L loc name)
                _ -> panic "kc_hs_type HsOpTy"
dreixel's avatar
dreixel committed
438
    return (HsOpTy ty1' op' ty2')
439

dreixel's avatar
dreixel committed
440
kc_hs_type ty@(HsAppTy ty1 ty2) exp_kind = do
441
    let (fun_ty, arg_tys) = splitHsAppTys ty1 [ty2]
dreixel's avatar
dreixel committed
442 443 444 445 446
    (fun_ty', fun_kind) <- kc_lhs_type_fresh fun_ty
    arg_tys' <- kcCheckApps fun_ty fun_kind arg_tys ty exp_kind
    return (mkHsAppTys fun_ty' arg_tys')

kc_hs_type ipTy@(HsIParamTy n ty) exp_kind = do
dreixel's avatar
dreixel committed
447 448 449
    ty' <- kc_lhs_type ty 
             (EK liftedTypeKind 
               (ptext (sLit "The type argument of the implicit parameter had")))
dreixel's avatar
dreixel committed
450
    checkExpectedKind ipTy constraintKind exp_kind
dreixel's avatar
dreixel committed
451 452 453 454 455
    return (HsIParamTy n ty')

kc_hs_type ty@(HsEqTy ty1 ty2) exp_kind = do
    (ty1', kind1) <- kc_lhs_type_fresh ty1
    (ty2', kind2) <- kc_lhs_type_fresh ty2
dreixel's avatar
dreixel committed
456 457
    checkExpectedKind ty2 kind2
      (EK kind1 (ptext (sLit "The left argument of the equality predicate had")))
dreixel's avatar
dreixel committed
458
    checkExpectedKind ty constraintKind exp_kind
dreixel's avatar
dreixel committed
459
    return (HsEqTy ty1' ty2')
460

dreixel's avatar
dreixel committed
461 462 463
kc_hs_type (HsCoreTy ty) exp_kind = do
    checkExpectedKind ty (typeKind ty) exp_kind
    return (HsCoreTy ty)
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
464

dreixel's avatar
dreixel committed
465
kc_hs_type (HsForAllTy exp tv_names context ty) exp_kind
466
  = kcHsTyVars tv_names         $ \ tv_names' ->
467
    do	{ ctxt' <- kcHsContext context
dreixel's avatar
dreixel committed
468
	; ty'   <- kc_lhs_type ty exp_kind
469 470 471 472
	     -- The body of a forall is usually a type, but in principle
	     -- there's no reason to prohibit *unlifted* types.
	     -- In fact, GHC can itself construct a function with an
	     -- unboxed tuple inside a for-all (via CPR analyis; see 
dreixel's avatar
dreixel committed
473 474 475 476
	     -- typecheck/should_compile/tc170).
             --
             -- Moreover in instance heads we get forall-types with
             -- kind Constraint.  
477
	     --
dreixel's avatar
dreixel committed
478 479 480 481
	     -- Really we should check that it's a type of value kind
             -- {*, Constraint, #}, but I'm not doing that yet
             -- Example that should be rejected:  
             --          f :: (forall (a:*->*). a) Int
dreixel's avatar
dreixel committed
482
  	; return (HsForAllTy exp tv_names' ctxt' ty') }
483

dreixel's avatar
dreixel committed
484 485 486
kc_hs_type (HsBangTy b ty) exp_kind
  = do { ty' <- kc_lhs_type ty exp_kind
       ; return (HsBangTy b ty') }
487

dreixel's avatar
dreixel committed
488
kc_hs_type ty@(HsRecTy _) _exp_kind
489 490 491
  = failWithTc (ptext (sLit "Unexpected record type") <+> ppr ty)
      -- Record types (which only show up temporarily in constructor signatures) 
      -- should have been removed by now
492

493
#ifdef GHCI	/* Only if bootstrapped */
dreixel's avatar
dreixel committed
494 495
kc_hs_type (HsSpliceTy sp fvs _) exp_kind = do
    (ty, k) <- kcSpliceType sp fvs
dreixel's avatar
dreixel committed
496
    checkExpectedKind ty k exp_kind
dreixel's avatar
dreixel committed
497
    return ty
498
#else
dreixel's avatar
dreixel committed
499 500
kc_hs_type ty@(HsSpliceTy {}) _exp_kind =
    failWithTc (ptext (sLit "Unexpected type splice:") <+> ppr ty)
501
#endif
502

dreixel's avatar
dreixel committed
503 504
kc_hs_type (HsQuasiQuoteTy {}) _exp_kind =
    panic "kc_hs_type"  -- Eliminated by renamer
505

dreixel's avatar
dreixel committed
506 507 508 509
-- Remove the doc nodes here, no need to worry about the location since
-- it's the same for a doc node and its child type node
kc_hs_type (HsDocTy ty _) exp_kind
  = kc_hs_type (unLoc ty) exp_kind
510

dreixel's avatar
dreixel committed
511 512
kc_hs_type ty@(HsExplicitListTy _k tys) exp_kind
  = do { ty_k_s <- mapM kc_lhs_type_fresh tys
dreixel's avatar
dreixel committed
513
       ; kind <- unifyKinds (ptext (sLit "In a promoted list")) ty_k_s
dreixel's avatar
dreixel committed
514
       ; checkExpectedKind ty (mkListTy kind) exp_kind
dreixel's avatar
dreixel committed
515 516 517 518 519
       ; return (HsExplicitListTy kind (map fst ty_k_s)) }

kc_hs_type ty@(HsExplicitTupleTy _ tys) exp_kind = do
  ty_k_s <- mapM kc_lhs_type_fresh tys
  let tupleKi = mkTyConApp (tupleTyCon BoxedTuple (length tys)) (map snd ty_k_s)
dreixel's avatar
dreixel committed
520
  checkExpectedKind ty tupleKi exp_kind
dreixel's avatar
dreixel committed
521
  return (HsExplicitTupleTy (map snd ty_k_s) (map fst ty_k_s))
dreixel's avatar
dreixel committed
522

dreixel's avatar
dreixel committed
523 524
kc_hs_type (HsWrapTy {}) _exp_kind =
    panic "kc_hs_type HsWrapTy"  -- We kind checked something twice
dreixel's avatar
dreixel committed
525

526
---------------------------
527 528 529
kcApps :: Outputable a
       => a 
       -> TcKind			-- Function kind
530 531
       -> [LHsType Name]		-- Arg types
       -> TcM ([LHsType Name], TcKind)	-- Kind-checked args
532
kcApps the_fun fun_kind args
533
  = do { (args_w_kinds, res_kind) <- splitFunKind (ppr the_fun) 1 fun_kind args
dreixel's avatar
dreixel committed
534
       ; args' <- kc_lhs_types args_w_kinds
535 536 537 538
       ; return (args', res_kind) }

kcCheckApps :: Outputable a => a -> TcKind -> [LHsType Name]
	    -> HsType Name     -- The type being checked (for err messages only)
539
	    -> ExpKind 	       -- Expected kind
dreixel's avatar
dreixel committed
540
	    -> TcM ([LHsType Name])
541
kcCheckApps the_fun fun_kind args ty exp_kind
542
  = do { (args_w_kinds, res_kind) <- splitFunKind (ppr the_fun) 1 fun_kind args
dreixel's avatar
dreixel committed
543
       ; args_w_kinds' <- kc_lhs_types args_w_kinds
dreixel's avatar
dreixel committed
544
       ; checkExpectedKind ty res_kind exp_kind
dreixel's avatar
dreixel committed
545
       ; return args_w_kinds' }
546

547

548
---------------------------
549 550 551
splitFunKind :: SDoc -> Int -> TcKind -> [b] -> TcM ([(b,ExpKind)], TcKind)
splitFunKind _       _      fk [] = return ([], fk)
splitFunKind the_fun arg_no fk (arg:args)
552
  = do { mb_fk <- matchExpectedFunKind fk
553 554
       ; case mb_fk of
            Nothing       -> failWithTc too_many_args 
555
            Just (ak,fk') -> do { (aks, rk) <- splitFunKind the_fun (arg_no+1) fk' args
dreixel's avatar
dreixel committed
556 557 558
                                ; return ((arg
                                          ,expArgKind (quotes the_fun) ak arg_no)
                                         :aks ,rk) } }
559
  where
560
    too_many_args = quotes the_fun <+>
Ian Lynagh's avatar
Ian Lynagh committed
561
		    ptext (sLit "is applied to too many type arguments")
562 563

---------------------------
564
kcHsContext :: LHsContext Name -> TcM (LHsContext Name)
batterseapower's avatar
batterseapower committed
565
kcHsContext ctxt = wrapLocM (mapM kcHsLPredType) ctxt
566

batterseapower's avatar
batterseapower committed
567
kcHsLPredType :: LHsType Name -> TcM (LHsType Name)
dreixel's avatar
dreixel committed
568
kcHsLPredType pred = kc_lhs_type pred ekConstraint
569 570

---------------------------
dreixel's avatar
dreixel committed
571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606
kcTyVar :: Name -> TcM (HsType Name, TcKind)
-- See Note [Type checking recursive type and class declarations]
-- in TcTyClsDecls
kcTyVar name         -- Could be a tyvar, a tycon, or a datacon
  = do { traceTc "lk1" (ppr name)
       ; thing <- tcLookup name
       ; traceTc "lk2" (ppr name <+> ppr thing)
       ; case thing of
           ATyVar _ ty           -> wrap_mono (typeKind ty)
           AThing kind           -> wrap_poly kind
           AGlobal (ATyCon tc)   -> wrap_poly (tyConKind tc)
           AGlobal (ADataCon dc) -> kcDataCon dc >>= wrap_poly
           _                     -> wrongThingErr "type" thing name }
  where
    wrap_mono kind = do { traceTc "lk3" (ppr name <+> dcolon <+> ppr kind)
                        ; return (HsTyVar name, kind) }
    wrap_poly kind
      | null kvs = wrap_mono kind
      | otherwise
      = do { traceTc "lk4" (ppr name <+> dcolon <+> ppr kind)
           ; kvs' <- mapM (const newMetaKindVar) kvs
           ; let ki = substKiWith kvs kvs' ki_body
           ; return (HsWrapTy (WpKiApps kvs') (HsTyVar name), ki) }
      where (kvs, ki_body) = splitForAllTys kind

-- IA0_TODO: this function should disapear, and use the dcPromoted field of DataCon
kcDataCon :: DataCon -> TcM TcKind
kcDataCon dc = do
  let ty = dataConUserType dc
  unless (isPromotableType ty) $ promoteErr dc ty
  let ki = promoteType ty
  traceTc "prm" (ppr ty <+> ptext (sLit "~~>") <+> ppr ki)
  return ki
  where
    promoteErr dc ty = failWithTc (quotes (ppr dc) <+> ptext (sLit "of type")
      <+> quotes (ppr ty) <+> ptext (sLit "is not promotable"))
607 608

kcClass :: Name -> TcM TcKind
609 610
kcClass cls = do	-- Must be a class
    thing <- tcLookup cls
611
    case thing of
batterseapower's avatar
batterseapower committed
612 613 614 615
        AThing kind                         -> return kind
        AGlobal (ATyCon tc)
          | Just cls <- tyConClass_maybe tc -> return (tyConKind (classTyCon cls))
        _                                   -> wrongThingErr "class" thing cls
616 617 618 619 620 621 622 623 624
\end{code}


%************************************************************************
%*									*
		Desugaring
%*									*
%************************************************************************

dreixel's avatar
dreixel committed
625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653
Note [Desugaring types]
~~~~~~~~~~~~~~~~~~~~~~~
The type desugarer is phase 2 of dealing with HsTypes.  Specifically:

  * It transforms from HsType to Type

  * It zonks any kinds.  The returned type should have no mutable kind
    or type variables (hence returning Type not TcType):
      - any unconstrained kind variables are defaulted to AnyK just 
        as in TcHsSyn. 
      - there are no mutable type variables because we are 
        kind-checking a type
    Reason: the returned type may be put in a TyCon or DataCon where
    it will never subsequently be zonked.

You might worry about nested scopes:
        ..a:kappa in scope..
            let f :: forall b. T '[a,b] -> Int
In this case, f's type could have a mutable kind variable kappa in it;
and we might then default it to AnyK when dealing with f's type
signature.  But we don't expect this to happen because we can't get a
lexically scoped type variable with a mutable kind variable in it.  A
delicate point, this.  If it becomes an issue we might need to
distinguish top-level from nested uses.

Moreover
  * it cannot fail, 
  * it does no unifications
  * it does no validity checking, except for structural matters, such as
654 655
	(a) spurious ! annotations.
	(b) a class used as a type
656 657

\begin{code}
dreixel's avatar
dreixel committed
658 659 660 661 662

zonkTcKindToKind :: TcKind -> TcM Kind
-- When zonking a TcKind to a kind we instantiate kind variables to AnyK
zonkTcKindToKind = zonkType (mkZonkTcTyVar (\ _ -> return anyKind) mkTyVarTy)

663 664
dsHsType :: LHsType Name -> TcM Type
-- All HsTyVarBndrs in the intput type are kind-annotated
dreixel's avatar
dreixel committed
665
-- See Note [Desugaring types]
666
dsHsType ty = ds_type (unLoc ty)
667

Ian Lynagh's avatar
Ian Lynagh committed
668
ds_type :: HsType Name -> TcM Type
dreixel's avatar
dreixel committed
669
-- See Note [Desugaring types]
Ian Lynagh's avatar
Ian Lynagh committed
670
ds_type ty@(HsTyVar _)
671 672
  = ds_app ty []

673
ds_type (HsParTy ty)		-- Remove the parentheses markers
674 675
  = dsHsType ty

676
ds_type ty@(HsBangTy {})    -- No bangs should be here
Ian Lynagh's avatar
Ian Lynagh committed
677
  = failWithTc (ptext (sLit "Unexpected strictness annotation:") <+> ppr ty)
678

679 680 681
ds_type ty@(HsRecTy {})	    -- No bangs should be here
  = failWithTc (ptext (sLit "Unexpected record type:") <+> ppr ty)

Ian Lynagh's avatar
Ian Lynagh committed
682
ds_type (HsKindSig ty _)
683 684
  = dsHsType ty	-- Kind checking done already

685 686 687 688
ds_type (HsListTy ty) = do
    tau_ty <- dsHsType ty
    checkWiredInTyCon listTyCon
    return (mkListTy tau_ty)
689

690 691 692 693
ds_type (HsPArrTy ty) = do
    tau_ty <- dsHsType ty
    checkWiredInTyCon parrTyCon
    return (mkPArrTy tau_ty)
694

batterseapower's avatar
batterseapower committed
695 696
ds_type (HsTupleTy hs_con tys) = do
    con <- case hs_con of
dreixel's avatar
dreixel committed
697 698 699 700 701
        HsUnboxedTuple    -> return UnboxedTuple
        HsBoxedTuple      -> return BoxedTuple
        HsConstraintTuple -> return ConstraintTuple
        _ -> panic "ds_type HsTupleTy"
        -- failWithTc (ptext (sLit "Unexpected tuple component kind:") <+> ppr kind')
batterseapower's avatar
batterseapower committed
702
    let tycon = tupleTyCon con (length tys)
703 704 705
    tau_tys <- dsHsTypes tys
    checkWiredInTyCon tycon
    return (mkTyConApp tycon tau_tys)
706

707 708 709 710
ds_type (HsFunTy ty1 ty2) = do
    tau_ty1 <- dsHsType ty1
    tau_ty2 <- dsHsType ty2
    return (mkFunTy tau_ty1 tau_ty2)
711

dreixel's avatar
dreixel committed
712 713
ds_type (HsOpTy ty1 (wrap, (L span op)) ty2) =
    setSrcSpan span (ds_app (HsWrapTy wrap (HsTyVar op)) [ty1,ty2])
714

715 716
ds_type ty@(HsAppTy _ _)
  = ds_app ty []
717

batterseapower's avatar
batterseapower committed
718 719 720 721 722 723 724 725
ds_type (HsIParamTy n ty) = do
    tau_ty <- dsHsType ty
    return (mkIPPred n tau_ty)

ds_type (HsEqTy ty1 ty2) = do
    tau_ty1 <- dsHsType ty1
    tau_ty2 <- dsHsType ty2
    return (mkEqPred (tau_ty1, tau_ty2))
726

Ian Lynagh's avatar
Ian Lynagh committed
727
ds_type (HsForAllTy _ tv_names ctxt ty)
dreixel's avatar
dreixel committed
728
  = tcTyVarBndrsKindGen tv_names $ \ tyvars -> do
batterseapower's avatar
batterseapower committed
729
    theta <- mapM dsHsType (unLoc ctxt)
730 731
    tau <- dsHsType ty
    return (mkSigmaTy tyvars theta tau)
732

733 734 735
ds_type (HsDocTy ty _)  -- Remove the doc comment
  = dsHsType ty

736
ds_type (HsSpliceTy _ _ kind) 
dreixel's avatar
dreixel committed
737 738 739
  = do { kind' <- zonkType (mkZonkTcTyVar (\ _ -> return liftedTypeKind) mkTyVarTy) 
                           kind
                     -- See Note [Kind of a type splice]
740 741
       ; newFlexiTyVarTy kind' }

742
ds_type (HsQuasiQuoteTy {}) = panic "ds_type"	-- Eliminated by renamer
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
743
ds_type (HsCoreTy ty)       = return ty
744

dreixel's avatar
dreixel committed
745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762
ds_type (HsExplicitListTy kind tys) = do
  kind' <- zonkTcKindToKind kind
  ds_tys <- mapM dsHsType tys
  return $
   foldr (\a b -> mkTyConApp (buildPromotedDataTyCon consDataCon) [kind', a, b])
         (mkTyConApp (buildPromotedDataTyCon nilDataCon) [kind']) ds_tys

ds_type (HsExplicitTupleTy kis tys) = do
  MASSERT( length kis == length tys )
  kis' <- mapM zonkTcKindToKind kis
  tys' <- mapM dsHsType tys
  return $ mkTyConApp (buildPromotedDataTyCon (tupleCon BoxedTuple (length kis'))) (kis' ++ tys')

ds_type (HsWrapTy (WpKiApps kappas) ty) = do
  tau <- ds_type ty
  kappas' <- mapM zonkTcKindToKind kappas
  return (mkAppTys tau kappas')

Ian Lynagh's avatar
Ian Lynagh committed
763
dsHsTypes :: [LHsType Name] -> TcM [Type]
764
dsHsTypes arg_tys = mapM dsHsType arg_tys
765 766
\end{code}

dreixel's avatar
dreixel committed
767 768 769 770 771 772 773 774 775 776 777 778 779 780 781
Note [Kind of a type splice]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider these terms, each with TH type splice inside:
     [| e1 :: Maybe $(..blah..) |]
     [| e2 :: $(..blah..) |]
When kind-checking the type signature, we'll kind-check the splice
$(..blah..); we want to give it a kind that can fit in any context,
as if $(..blah..) :: forall k. k.  

In the e1 example, the context of the splice fixes kappa to *.  But
in the e2 example, we'll desugar the type, zonking the kind unification
variables as we go.  When we encournter the unconstrained kappa, we
want to default it to '*', not to AnyK.


782 783 784 785
Help functions for type applications
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\begin{code}
786
ds_app :: HsType Name -> [LHsType Name] -> TcM Type
787
ds_app (HsAppTy ty1 ty2) tys
788
  = ds_app (unLoc ty1) (ty2:tys)
789

790 791
ds_app ty tys = do
    arg_tys <- dsHsTypes tys
792 793
    case ty of
	HsTyVar fun -> ds_var_app fun arg_tys
Ian Lynagh's avatar
Ian Lynagh committed
794
	_           -> do fun_ty <- ds_type ty
795
                          return (mkAppTys fun_ty arg_tys)
796 797

ds_var_app :: Name -> [Type] -> TcM Type
dreixel's avatar
dreixel committed
798 799 800 801 802 803 804 805 806 807 808 809 810 811 812
-- See Note [Type checking recursive type and class declarations]
-- in TcTyClsDecls
ds_var_app name arg_tys 
  | isTvNameSpace (rdrNameSpace (nameRdrName name))
  = do { thing <- tcLookup name
       ; case thing of
           ATyVar _ ty -> return (mkAppTys ty arg_tys)
	   _           -> wrongThingErr "type" thing name }

  | otherwise
  = do { thing <- tcLookupGlobal name
       ; case thing of
           ATyCon tc   -> return (mkTyConApp tc arg_tys)
           ADataCon dc -> return (mkTyConApp (buildPromotedDataTyCon dc) arg_tys) 
	   _           -> wrongThingErr "type" (AGlobal thing) name }
813

814 815
addKcTypeCtxt :: LHsType Name -> TcM a -> TcM a
	-- Wrap a context around only if we want to show that contexts.  
batterseapower's avatar
batterseapower committed
816
	-- Omit invisble ones and ones user's won't grok
817 818
addKcTypeCtxt (L _ other_ty) thing = addErrCtxt (typeCtxt other_ty) thing

Ian Lynagh's avatar
Ian Lynagh committed
819
typeCtxt :: HsType Name -> SDoc
Ian Lynagh's avatar
Ian Lynagh committed
820
typeCtxt ty = ptext (sLit "In the type") <+> quotes (ppr ty)
821
\end{code}
822 823 824 825 826 827 828

%************************************************************************
%*									*
		Type-variable binders
%*									*
%************************************************************************

dreixel's avatar
dreixel committed
829 830 831 832 833 834 835 836 837 838 839 840 841 842
Note [Kind-checking kind-polymorphic types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider:
  f :: forall (f::k -> *) a. f a -> Int

Here, the [LHsTyVarBndr Name] of the forall type will be [f,a], where
  a is a  UserTyVar   -> type variable without kind annotation
  f is a  KindedTyVar -> type variable with kind annotation

If were were to allow binding sites for kind variables, thus
  f :: forall @k (f :: k -> *) a. f a -> Int
then we'd also need
  k is a   UserKiVar   -> kind variable (they don't need annotation,
                          since we only have BOX for a super kind)
843 844

\begin{code}
845 846
kcHsTyVars :: [LHsTyVarBndr Name] 
	   -> ([LHsTyVarBndr Name] -> TcM r) 	-- These binders are kind-annotated
847 848
						-- They scope over the thing inside
	   -> TcM r
849 850 851
kcHsTyVars tvs thing_inside
  = do { kinded_tvs <- mapM (wrapLocM kcHsTyVar) tvs
       ; tcExtendKindEnvTvs kinded_tvs thing_inside }
852 853

kcHsTyVar :: HsTyVarBndr Name -> TcM (HsTyVarBndr Name)
dreixel's avatar
dreixel committed
854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875
-- Return a *kind-annotated* binder, whose PostTcKind is
-- initialised with a kind variable.
-- Typically the Kind inside the KindedTyVar will be a tyvar with a mutable kind 
-- in it. We aren't yet sure whether the binder is a *type* variable or a *kind*
-- variable. See Note [Kind-checking kind-polymorphic types]
--
-- If the variable is already in scope return it, instead of introducing a new
-- one. This can occur in 
--   instance C (a,b) where
--     type F (a,b) c = ...
-- Here a,b will be in scope when processing the associated type instance for F.
kcHsTyVar tyvar = do in_scope <- getInLocalScope
                     if in_scope (hsTyVarName tyvar)
                      then do inscope_tyvar <- tcLookupTyVar (hsTyVarName tyvar)
                              return (UserTyVar (tyVarName inscope_tyvar)
                                (tyVarKind inscope_tyvar)) 
                       else kcHsTyVar' tyvar
    where
        kcHsTyVar' (UserTyVar name _)        = UserTyVar name <$> newMetaKindVar
        kcHsTyVar' (KindedTyVar name kind _) = do
          kind' <- scDsLHsKind kind
          return (KindedTyVar name kind kind')
876 877

------------------
dreixel's avatar
dreixel committed
878 879 880
tcTyVarBndrs :: [LHsTyVarBndr Name] -- Kind-annotated binders, which need kind-zonking
             -> ([TyVar] -> TcM r)
             -> TcM r
881 882
-- Used when type-checking types/classes/type-decls
-- Brings into scope immutable TyVars, not mutable ones that require later zonking
dreixel's avatar
dreixel committed
883
-- Fix #5426: avoid abstraction over kinds containing # or (#)
884
tcTyVarBndrs bndrs thing_inside = do
dreixel's avatar
dreixel committed
885
    tyvars <- mapM (zonk . hsTyVarNameKind . unLoc) bndrs
886 887
    tcExtendTyVarEnv tyvars (thing_inside tyvars)
  where
dreixel's avatar
dreixel committed
888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979
    zonk (name, kind)
      = do { kind' <- zonkTcKind kind
           ; checkTc (noHashInKind kind') (ptext (sLit "Kind signature contains # or (#)"))
           ; return (mkTyVar name kind') }

tcTyVarBndrsKindGen :: [LHsTyVarBndr Name] -> ([TyVar] -> TcM r) -> TcM r
-- tcTyVarBndrsKindGen [(f :: ?k -> *), (a :: ?k)] thing_inside
-- calls thing_inside with [(k :: BOX), (f :: k -> *), (a :: k)]
tcTyVarBndrsKindGen bndrs thing_inside
  = do { let kinds = map (hsTyVarKind . unLoc) bndrs
       ; (kvs, zonked_kinds) <- kindGeneralizeKinds kinds
       ; let tyvars = zipWith mkTyVar (map hsLTyVarName bndrs) zonked_kinds
             ktvs = kvs ++ tyvars     -- See Note [Kinds of quantified type variables]
       ; traceTc "tcTyVarBndrsKindGen" (ppr (bndrs, kvs, tyvars))
       ; tcExtendTyVarEnv ktvs (thing_inside ktvs) }
\end{code}

Note [Kinds of quantified type variables]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tcTyVarBndrsKindGen quantifies over a specified list of type variables,
*and* over the kind variables mentioned in the kinds of those tyvars.

Note that we must zonk those kinds (obviously) but less obviously, we
must return type variables whose kinds are zonked too. Example
    (a :: k7)  where  k7 := k9 -> k9
We must return
    [k9, a:k9->k9]
and NOT 
    [k9, a:k7]
Reason: we're going to turn this into a for-all type, 
   forall k9. forall (a:k7). blah
which the type checker will then instantiate, and instantiate does not
look through unification variables!  

Hence using zonked_kinds when forming 'tyvars'.

\begin{code}
tcTyClTyVars :: Name -> [LHsTyVarBndr Name]	-- LHS of the type or class decl
             -> ([TyVar] -> Kind -> TcM a) -> TcM a
-- tcTyClTyVars T [a,b] calls thing_inside with
-- [k1,k2,a,b] (k2 -> *)  where T : forall k1 k2 (a:k1 -> *) (b:k1). k2 -> *
--
-- No need to freshen the k's because they are just skolem 
-- constants here, and we are at top level anyway.
tcTyClTyVars tycon tyvars thing_inside
  = do { thing <- tcLookup tycon
       ; let { kind =
                 case thing of
                   AThing kind -> kind
                   _ -> panic "tcTyClTyVars"
                     -- We only call tcTyClTyVars during typechecking in
                     -- TcTyClDecls, where the local env is extended with
                     -- the generalized_env (mapping Names to AThings).
             ; (kvs, body) = splitForAllTys kind
             ; (kinds, res) = splitKindFunTysN (length names) body
             ; names = hsLTyVarNames tyvars
             ; tvs = zipWith mkTyVar names kinds
             ; all_vs = kvs ++ tvs }
       ; tcExtendTyVarEnv all_vs (thing_inside all_vs res) }

-- Used when generalizing binders and type family patterns
-- It takes a kind from the type checker (like `k0 -> *`), and returns the 
-- final, kind-generalized kind (`forall k::BOX. k -> *`)
kindGeneralizeKinds :: [TcKind] -> TcM ([KindVar], [Kind])
-- INVARIANT: the returned kinds are zonked, and
--            mention the returned kind variables
kindGeneralizeKinds kinds 
  = do { -- Quantify over kind variables free in
         -- the kinds, and *not* in the environment
       ; zonked_kinds <- mapM zonkTcKind kinds
       ; gbl_tvs <- tcGetGlobalTyVars -- Already zonked
       ; let kvs_to_quantify = tyVarsOfTypes zonked_kinds 
                               `minusVarSet` gbl_tvs

       ; kvs <- ASSERT2 (all isKiVar (varSetElems kvs_to_quantify), ppr kvs_to_quantify)
                zonkQuantifiedTyVars kvs_to_quantify

         -- Zonk the kinds again, to pick up either the kind 
         -- variables we quantify over, or *, depending on whether
         -- zonkQuantifiedTyVars decided to generalise (which in
         -- turn depends on PolyKinds)
       ; final_kinds <- mapM zonkTcKind zonked_kinds

       ; traceTc "generalizeKind" (    ppr kinds <+> ppr kvs_to_quantify
                                   <+> ppr kvs   <+> ppr final_kinds)
       ; return (kvs, final_kinds) }

kindGeneralizeKind :: TcKind -> TcM ( [KindVar]  -- these were flexi kind vars
                                    , Kind )     -- this is the old kind where flexis got zonked
kindGeneralizeKind kind = do
  (kvs, [kind']) <- kindGeneralizeKinds [kind]
  return (kvs, kind')
980 981

-----------------------------------
dreixel's avatar
dreixel committed
982
tcDataKindSig :: Kind -> TcM [TyVar]
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
983
-- GADT decls can have a (perhaps partial) kind signature
984 985
--	e.g.  data T :: * -> * -> * where ...
-- This function makes up suitable (kinded) type variables for 
986 987
-- the argument kinds, and checks that the result kind is indeed *.
-- We use it also to make up argument type variables for for data instances.
dreixel's avatar
dreixel committed
988
tcDataKindSig kind
989 990 991
  = do	{ checkTc (isLiftedTypeKind res_kind) (badKindSig kind)
	; span <- getSrcSpanM
	; us   <- newUniqueSupply 
992 993
	; let uniqs = uniqsFromSupply us
	; return [ mk_tv span uniq str kind 
994
		 | ((kind, str), uniq) <- arg_kinds `zip` dnames `zip` uniqs ] }
995 996 997 998 999 1000
  where
    (arg_kinds, res_kind) = splitKindFunTys kind
    mk_tv loc uniq str kind = mkTyVar name kind
	where
	   name = mkInternalName uniq occ loc
	   occ  = mkOccName tvName str
1001 1002
	  
    dnames = map ('$' :) names	-- Note [Avoid name clashes for associated data types]
1003

1004
    names :: [String]
1005 1006 1007 1008
    names = [ c:cs | cs <- "" : names, c <- ['a'..'z'] ] 

badKindSig :: Kind -> SDoc
badKindSig kind 
Ian Lynagh's avatar
Ian Lynagh committed
1009
 = hang (ptext (sLit "Kind signature on data type declaration has non-* return kind"))
1010
	2 (ppr kind)
1011 1012
\end{code}

1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030
Note [Avoid name clashes for associated data types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider    class C a b where
               data D b :: * -> *
When typechecking the decl for D, we'll invent an extra type variable for D,
to fill out its kind.  We *don't* want this type variable to be 'a', because
in an .hi file we'd get
            class C a b where
               data D b a 
which makes it look as if there are *two* type indices.  But there aren't!
So we use $a instead, which cannot clash with a user-written type variable.
Remember that type variable binders in interface files are just FastStrings,
not proper Names.

(The tidying phase can't help here because we don't tidy TyCons.  Another
alternative would be to record the number of indexing parameters in the 
interface file.)

1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071

%************************************************************************
%*									*
		Scoped type variables
%*									*
%************************************************************************


tcAddScopedTyVars is used for scoped type variables added by pattern
type signatures
	e.g.  \ ((x::a), (y::a)) -> x+y
They never have explicit kinds (because this is source-code only)
They are mutable (because they can get bound to a more specific type).

Usually we kind-infer and expand type splices, and then
tupecheck/desugar the type.  That doesn't work well for scoped type
variables, because they scope left-right in patterns.  (e.g. in the
example above, the 'a' in (y::a) is bound by the 'a' in (x::a).

The current not-very-good plan is to
  * find all the types in the patterns
  * find their free tyvars
  * do kind inference
  * bring the kinded type vars into scope
  * BUT throw away the kind-checked type
  	(we'll kind-check it again when we type-check the pattern)

This is bad because throwing away the kind checked type throws away
its splices.  But too bad for now.  [July 03]

Historical note:
    We no longer specify that these type variables must be univerally 
    quantified (lots of email on the subject).  If you want to put that 
    back in, you need to
	a) Do a checkSigTyVars after thing_inside
	b) More insidiously, don't pass in expected_ty, else
	   we unify with it too early and checkSigTyVars barfs
	   Instead you have to pass in a fresh ty var, and unify
	   it with expected_ty afterwards

\begin{code}
1072 1073 1074 1075 1076 1077 1078 1079
tcHsPatSigType :: UserTypeCtxt
	       -> LHsType Name 		-- The type signature
	       -> TcM ([TyVar], 	-- Newly in-scope type variables
			Type)		-- The signature
-- Used for type-checking type signatures in
-- (a) patterns 	  e.g  f (x::Int) = e
-- (b) result signatures  e.g. g x :: Int = e
-- (c) RULE forall bndrs  e.g. forall (x::Int). f x = x
1080

1081 1082 1083 1084 1085 1086 1087
tcHsPatSigType ctxt hs_ty 
  = addErrCtxt (pprHsSigCtxt ctxt hs_ty) $
    do	{ 	-- Find the type variables that are mentioned in the type
		-- but not already in scope.  These are the ones that
		-- should be bound by the pattern signature
 	  in_scope <- getInLocalScope
	; let span = getLoc hs_ty
1088 1089 1090
	      sig_tvs = userHsTyVarBndrs $ map (L span) $ 
			filterOut in_scope $
                        nameSetToList (extractHsTyVars hs_ty)
1091

1092
	; (tyvars, sig_ty) <- tcHsQuantifiedType sig_tvs hs_ty
1093 1094
	; checkValidType ctxt sig_ty 
	; return (tyvars, sig_ty)
1095
      }
1096 1097 1098

tcPatSig :: UserTypeCtxt
	 -> LHsType Name
1099
	 -> TcSigmaType
1100
	 -> TcM (TcType,	   -- The type to use for "inside" the signature
1101
		 [(Name, TcType)], -- The new bit of type environment, binding
1102
				   -- the scoped type variables
1103
                 HsWrapper)        -- Coercion due to unification with actual ty
1104
                                   -- Of shape:  res_ty ~ sig_ty
1105 1106
tcPatSig ctxt sig res_ty
  = do	{ (sig_tvs, sig_ty) <- tcHsPatSigType ctxt sig
1107 1108 1109
    	-- sig_tvs are the type variables free in 'sig', 
	-- and not already in scope. These are the ones
	-- that should be brought into scope
1110 1111

	; if null sig_tvs then do {
1112
		-- Just do the subsumption check and return
1113
                  wrap <- tcSubType PatSigOrigin ctxt res_ty sig_ty
1114
		; return (sig_ty, [], wrap)
1115
        } else do {
1116 1117 1118 1119 1120 1121 1122 1123
		-- Type signature binds at least one scoped type variable
	
		-- A pattern binding cannot bind scoped type variables
		-- The renamer fails with a name-out-of-scope error 
		-- if a pattern binding tries to bind a type variable,
		-- So we just have an ASSERT here
	; let in_pat_bind = case ctxt of
				BindPatSigCtxt -> True
Ian Lynagh's avatar
Ian Lynagh committed
1124
				_              -> False
1125 1126
	; ASSERT( not in_pat_bind || null sig_tvs ) return ()

1127 1128 1129 1130 1131 1132 1133 1134 1135 1136
		-- Check that all newly-in-scope tyvars are in fact
		-- constrained by the pattern.  This catches tiresome
		-- cases like	
		--	type T a = Int
		--	f :: Int -> Int
		-- 	f (x :: T a) = ...
		-- Here 'a' doesn't get a binding.  Sigh
	; let bad_tvs = filterOut (`elemVarSet` exactTyVarsOfType sig_ty) sig_tvs
	; checkTc (null bad_tvs) (badPatSigTvs sig_ty bad_tvs)

1137
	-- Now do a subsumption check of the pattern signature against res_ty
1138
        ; sig_tvs' <- tcInstSigTyVars sig_tvs
1139 1140
        ; let sig_ty' = substTyWith sig_tvs sig_tv_tys' sig_ty
              sig_tv_tys' = mkTyVarTys sig_tvs'
1141
	; wrap <- tcSubType PatSigOrigin ctxt res_ty sig_ty'
1142 1143 1144

	-- Check that each is bound to a distinct type variable,
	-- and one that is not already in scope
1145
        ; binds_in_scope <- getScopedTyVarBinds
1146
	; let tv_binds = map tyVarName sig_tvs `zip` sig_tv_tys'
1147 1148
	; check binds_in_scope tv_binds