Further improvements to well-kinded types
[ghc.git] / compiler / typecheck / TcHsType.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4
5 \section[TcMonoType]{Typechecking user-specified @MonoTypes@}
6 -}
7
8 {-# LANGUAGE CPP, TupleSections, MultiWayIf, RankNTypes #-}
9
10 module TcHsType (
11 -- Type signatures
12 kcHsSigType, tcClassSigType,
13 tcHsSigType, tcHsSigWcType,
14 tcHsPartialSigType,
15 funsSigCtxt, addSigCtxt, pprSigCtxt,
16
17 tcHsClsInstType,
18 tcHsDeriv, tcHsVectInst,
19 tcHsTypeApp,
20 UserTypeCtxt(..),
21 tcImplicitTKBndrs, tcImplicitTKBndrsType, tcExplicitTKBndrs,
22
23 -- Type checking type and class decls
24 kcLookupTcTyCon, kcTyClTyVars, tcTyClTyVars,
25 tcDataKindSig,
26 DataKindCheck(..),
27
28 -- Kind-checking types
29 -- No kind generalisation, no checkValidType
30 kcLHsQTyVars, kcLHsTyVarBndrs,
31 tcWildCardBinders,
32 tcHsLiftedType, tcHsOpenType,
33 tcHsLiftedTypeNC, tcHsOpenTypeNC,
34 tcLHsType, tcLHsTypeUnsaturated, tcCheckLHsType,
35 tcHsMbContext, tcHsContext, tcLHsPredType, tcInferApps,
36 solveEqualities, -- useful re-export
37
38 typeLevelMode, kindLevelMode,
39
40 kindGeneralize, checkExpectedKindX, instantiateTyUntilN,
41 reportFloatingKvs,
42
43 -- Sort-checking kinds
44 tcLHsKindSig,
45
46 -- Pattern type signatures
47 tcHsPatSigType, tcPatSig, funAppCtxt
48 ) where
49
50 #include "HsVersions.h"
51
52 import GhcPrelude
53
54 import HsSyn
55 import TcRnMonad
56 import TcEvidence
57 import TcEnv
58 import TcMType
59 import TcValidity
60 import TcUnify
61 import TcIface
62 import TcSimplify ( solveEqualities )
63 import TcType
64 import TcHsSyn( zonkSigType )
65 import Inst ( tcInstBinders, tcInstBinder )
66 import Type
67 import Kind
68 import RdrName( lookupLocalRdrOcc )
69 import Var
70 import VarSet
71 import TyCon
72 import ConLike
73 import DataCon
74 import Class
75 import Name
76 import NameEnv
77 import NameSet
78 import VarEnv
79 import TysWiredIn
80 import BasicTypes
81 import SrcLoc
82 import Constants ( mAX_CTUPLE_SIZE )
83 import ErrUtils( MsgDoc )
84 import Unique
85 import Util
86 import UniqSupply
87 import Outputable
88 import FastString
89 import PrelNames hiding ( wildCardName )
90 import qualified GHC.LanguageExtensions as LangExt
91
92 import Maybes
93 import Data.List ( partition, zipWith4, mapAccumR )
94 import Control.Monad
95
96 {-
97 ----------------------------
98 General notes
99 ----------------------------
100
101 Unlike with expressions, type-checking types both does some checking and
102 desugars at the same time. This is necessary because we often want to perform
103 equality checks on the types right away, and it would be incredibly painful
104 to do this on un-desugared types. Luckily, desugared types are close enough
105 to HsTypes to make the error messages sane.
106
107 During type-checking, we perform as little validity checking as possible.
108 This is because some type-checking is done in a mutually-recursive knot, and
109 if we look too closely at the tycons, we'll loop. This is why we always must
110 use mkNakedTyConApp and mkNakedAppTys, etc., which never look at a tycon.
111 The mkNamed... functions don't uphold Type invariants, but zonkTcTypeToType
112 will repair this for us. Note that zonkTcType *is* safe within a knot, and
113 can be done repeatedly with no ill effect: it just squeezes out metavariables.
114
115 Generally, after type-checking, you will want to do validity checking, say
116 with TcValidity.checkValidType.
117
118 Validity checking
119 ~~~~~~~~~~~~~~~~~
120 Some of the validity check could in principle be done by the kind checker,
121 but not all:
122
123 - During desugaring, we normalise by expanding type synonyms. Only
124 after this step can we check things like type-synonym saturation
125 e.g. type T k = k Int
126 type S a = a
127 Then (T S) is ok, because T is saturated; (T S) expands to (S Int);
128 and then S is saturated. This is a GHC extension.
129
130 - Similarly, also a GHC extension, we look through synonyms before complaining
131 about the form of a class or instance declaration
132
133 - Ambiguity checks involve functional dependencies, and it's easier to wait
134 until knots have been resolved before poking into them
135
136 Also, in a mutually recursive group of types, we can't look at the TyCon until we've
137 finished building the loop. So to keep things simple, we postpone most validity
138 checking until step (3).
139
140 Knot tying
141 ~~~~~~~~~~
142 During step (1) we might fault in a TyCon defined in another module, and it might
143 (via a loop) refer back to a TyCon defined in this module. So when we tie a big
144 knot around type declarations with ARecThing, so that the fault-in code can get
145 the TyCon being defined.
146
147 %************************************************************************
148 %* *
149 Check types AND do validity checking
150 * *
151 ************************************************************************
152 -}
153
154 funsSigCtxt :: [Located Name] -> UserTypeCtxt
155 -- Returns FunSigCtxt, with no redundant-context-reporting,
156 -- form a list of located names
157 funsSigCtxt (L _ name1 : _) = FunSigCtxt name1 False
158 funsSigCtxt [] = panic "funSigCtxt"
159
160 addSigCtxt :: UserTypeCtxt -> LHsType GhcRn -> TcM a -> TcM a
161 addSigCtxt ctxt hs_ty thing_inside
162 = setSrcSpan (getLoc hs_ty) $
163 addErrCtxt (pprSigCtxt ctxt hs_ty) $
164 thing_inside
165
166 pprSigCtxt :: UserTypeCtxt -> LHsType GhcRn -> SDoc
167 -- (pprSigCtxt ctxt <extra> <type>)
168 -- prints In the type signature for 'f':
169 -- f :: <type>
170 -- The <extra> is either empty or "the ambiguity check for"
171 pprSigCtxt ctxt hs_ty
172 | Just n <- isSigMaybe ctxt
173 = hang (text "In the type signature:")
174 2 (pprPrefixOcc n <+> dcolon <+> ppr hs_ty)
175
176 | otherwise
177 = hang (text "In" <+> pprUserTypeCtxt ctxt <> colon)
178 2 (ppr hs_ty)
179
180 tcHsSigWcType :: UserTypeCtxt -> LHsSigWcType GhcRn -> TcM Type
181 -- This one is used when we have a LHsSigWcType, but in
182 -- a place where wildards aren't allowed. The renamer has
183 -- already checked this, so we can simply ignore it.
184 tcHsSigWcType ctxt sig_ty = tcHsSigType ctxt (dropWildCards sig_ty)
185
186 kcHsSigType :: [Located Name] -> LHsSigType GhcRn -> TcM ()
187 kcHsSigType names (HsIB { hsib_body = hs_ty
188 , hsib_vars = sig_vars })
189 = addSigCtxt (funsSigCtxt names) hs_ty $
190 discardResult $
191 tcImplicitTKBndrsType sig_vars $
192 tc_lhs_type typeLevelMode hs_ty liftedTypeKind
193
194 tcClassSigType :: [Located Name] -> LHsSigType GhcRn -> TcM Type
195 -- Does not do validity checking; this must be done outside
196 -- the recursive class declaration "knot"
197 tcClassSigType names sig_ty
198 = addSigCtxt (funsSigCtxt names) (hsSigType sig_ty) $
199 tc_hs_sig_type_and_gen sig_ty liftedTypeKind
200
201 tcHsSigType :: UserTypeCtxt -> LHsSigType GhcRn -> TcM Type
202 -- Does validity checking
203 tcHsSigType ctxt sig_ty
204 = addSigCtxt ctxt (hsSigType sig_ty) $
205 do { kind <- case expectedKindInCtxt ctxt of
206 AnythingKind -> newMetaKindVar
207 TheKind k -> return k
208 OpenKind -> newOpenTypeKind
209 -- The kind is checked by checkValidType, and isn't necessarily
210 -- of kind * in a Template Haskell quote eg [t| Maybe |]
211
212 -- Generalise here: see Note [Kind generalisation]
213 ; do_kind_gen <- decideKindGeneralisationPlan sig_ty
214 ; ty <- if do_kind_gen
215 then tc_hs_sig_type_and_gen sig_ty kind
216 else tc_hs_sig_type sig_ty kind >>= zonkTcType
217
218 ; checkValidType ctxt ty
219 ; return ty }
220
221 tc_hs_sig_type_and_gen :: LHsSigType GhcRn -> Kind -> TcM Type
222 -- Kind-checks/desugars an 'LHsSigType',
223 -- solve equalities,
224 -- and then kind-generalizes.
225 -- This will never emit constraints, as it uses solveEqualities interally.
226 -- No validity checking, but it does zonk en route to generalization
227 tc_hs_sig_type_and_gen hs_ty kind
228 = do { ty <- solveEqualities $
229 tc_hs_sig_type hs_ty kind
230 -- NB the call to solveEqualities, which unifies all those
231 -- kind variables floating about, immediately prior to
232 -- kind generalisation
233 ; kindGeneralizeType ty }
234
235 tc_hs_sig_type :: LHsSigType GhcRn -> Kind -> TcM Type
236 -- Kind-check/desugar a 'LHsSigType', but does not solve
237 -- the equalities that arise from doing so; instead it may
238 -- emit kind-equality constraints into the monad
239 -- No zonking or validity checking
240 tc_hs_sig_type (HsIB { hsib_vars = sig_vars
241 , hsib_body = hs_ty }) kind
242 = do { (tkvs, ty) <- tcImplicitTKBndrsType sig_vars $
243 tc_lhs_type typeLevelMode hs_ty kind
244 ; return (mkSpecForAllTys tkvs ty) }
245
246 -----------------
247 tcHsDeriv :: LHsSigType GhcRn -> TcM ([TyVar], Class, [Type], [Kind])
248 -- Like tcHsSigType, but for the ...deriving( C t1 ty2 ) clause
249 -- Returns the C, [ty1, ty2, and the kinds of C's remaining arguments
250 -- E.g. class C (a::*) (b::k->k)
251 -- data T a b = ... deriving( C Int )
252 -- returns ([k], C, [k, Int], [k->k])
253 tcHsDeriv hs_ty
254 = do { cls_kind <- newMetaKindVar
255 -- always safe to kind-generalize, because there
256 -- can be no covars in an outer scope
257 ; ty <- checkNoErrs $
258 -- avoid redundant error report with "illegal deriving", below
259 tc_hs_sig_type_and_gen hs_ty cls_kind
260 ; cls_kind <- zonkTcType cls_kind
261 ; let (tvs, pred) = splitForAllTys ty
262 ; let (args, _) = splitFunTys cls_kind
263 ; case getClassPredTys_maybe pred of
264 Just (cls, tys) -> return (tvs, cls, tys, args)
265 Nothing -> failWithTc (text "Illegal deriving item" <+> quotes (ppr hs_ty)) }
266
267 tcHsClsInstType :: UserTypeCtxt -- InstDeclCtxt or SpecInstCtxt
268 -> LHsSigType GhcRn
269 -> TcM ([TyVar], ThetaType, Class, [Type])
270 -- Like tcHsSigType, but for a class instance declaration
271 tcHsClsInstType user_ctxt hs_inst_ty
272 = setSrcSpan (getLoc (hsSigType hs_inst_ty)) $
273 do { inst_ty <- tc_hs_sig_type_and_gen hs_inst_ty constraintKind
274 ; checkValidInstance user_ctxt hs_inst_ty inst_ty }
275
276 -- Used for 'VECTORISE [SCALAR] instance' declarations
277 tcHsVectInst :: LHsSigType GhcRn -> TcM (Class, [Type])
278 tcHsVectInst ty
279 | let hs_cls_ty = hsSigType ty
280 , Just (L _ cls_name, tys) <- hsTyGetAppHead_maybe hs_cls_ty
281 -- Ignoring the binders looks pretty dodgy to me
282 = do { (cls, cls_kind) <- tcClass cls_name
283 ; (applied_class, _res_kind)
284 <- tcTyApps typeLevelMode hs_cls_ty (mkClassPred cls []) cls_kind tys
285 ; case tcSplitTyConApp_maybe applied_class of
286 Just (_tc, args) -> ASSERT( _tc == classTyCon cls )
287 return (cls, args)
288 _ -> failWithTc (text "Too many arguments passed to" <+> ppr cls_name) }
289 | otherwise
290 = failWithTc $ text "Malformed instance type"
291
292 ----------------------------------------------
293 -- | Type-check a visible type application
294 tcHsTypeApp :: LHsWcType GhcRn -> Kind -> TcM Type
295 tcHsTypeApp wc_ty kind
296 | HsWC { hswc_wcs = sig_wcs, hswc_body = hs_ty } <- wc_ty
297 = do { ty <- tcWildCardBindersX newWildTyVar sig_wcs $ \ _ ->
298 tcCheckLHsType hs_ty kind
299 ; ty <- zonkTcType ty
300 ; checkValidType TypeAppCtxt ty
301 ; return ty }
302 -- NB: we don't call emitWildcardHoleConstraints here, because
303 -- we want any holes in visible type applications to be used
304 -- without fuss. No errors, warnings, extensions, etc.
305
306 {-
307 ************************************************************************
308 * *
309 The main kind checker: no validity checks here
310 * *
311 ************************************************************************
312
313 First a couple of simple wrappers for kcHsType
314 -}
315
316 ---------------------------
317 tcHsOpenType, tcHsLiftedType,
318 tcHsOpenTypeNC, tcHsLiftedTypeNC :: LHsType GhcRn -> TcM TcType
319 -- Used for type signatures
320 -- Do not do validity checking
321 tcHsOpenType ty = addTypeCtxt ty $ tcHsOpenTypeNC ty
322 tcHsLiftedType ty = addTypeCtxt ty $ tcHsLiftedTypeNC ty
323
324 tcHsOpenTypeNC ty = do { ek <- newOpenTypeKind
325 ; tc_lhs_type typeLevelMode ty ek }
326 tcHsLiftedTypeNC ty = tc_lhs_type typeLevelMode ty liftedTypeKind
327
328 -- Like tcHsType, but takes an expected kind
329 tcCheckLHsType :: LHsType GhcRn -> Kind -> TcM TcType
330 tcCheckLHsType hs_ty exp_kind
331 = addTypeCtxt hs_ty $
332 tc_lhs_type typeLevelMode hs_ty exp_kind
333
334 tcLHsType :: LHsType GhcRn -> TcM (TcType, TcKind)
335 -- Called from outside: set the context
336 tcLHsType ty = addTypeCtxt ty (tc_infer_lhs_type typeLevelMode ty)
337
338 -- Like tcLHsType, but use it in a context where type synonyms and type families
339 -- do not need to be saturated, like in a GHCi :kind call
340 tcLHsTypeUnsaturated :: LHsType GhcRn -> TcM (TcType, TcKind)
341 tcLHsTypeUnsaturated ty = addTypeCtxt ty (tc_infer_lhs_type mode ty)
342 where
343 mode = allowUnsaturated typeLevelMode
344
345 ---------------------------
346 -- | Should we generalise the kind of this type signature?
347 -- We *should* generalise if the type is closed
348 -- or if NoMonoLocalBinds is set. Otherwise, nope.
349 -- See Note [Kind generalisation plan]
350 decideKindGeneralisationPlan :: LHsSigType GhcRn -> TcM Bool
351 decideKindGeneralisationPlan sig_ty@(HsIB { hsib_closed = closed })
352 = do { mono_locals <- xoptM LangExt.MonoLocalBinds
353 ; let should_gen = not mono_locals || closed
354 ; traceTc "decideKindGeneralisationPlan"
355 (ppr sig_ty $$ text "should gen?" <+> ppr should_gen)
356 ; return should_gen }
357
358 {- Note [Kind generalisation plan]
359 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
360 When should we do kind-generalisation for user-written type signature?
361 Answer: we use the same rule as for value bindings:
362
363 * We always kind-generalise if the type signature is closed
364 * Additionally, we attempt to generalise if we have NoMonoLocalBinds
365
366 Trac #13337 shows the problem if we kind-generalise an open type (i.e.
367 one that mentions in-scope tpe variable
368 foo :: forall k (a :: k) proxy. (Typeable k, Typeable a)
369 => proxy a -> String
370 foo _ = case eqT :: Maybe (k :~: Type) of
371 Nothing -> ...
372 Just Refl -> case eqT :: Maybe (a :~: Int) of ...
373
374 In the expression type sig on the last line, we have (a :: k)
375 but (Int :: Type). Since (:~:) is kind-homogeneous, this requires
376 k ~ *, which is true in the Refl branch of the outer case.
377
378 That equality will be solved if we allow it to float out to the
379 implication constraint for the Refl match, bnot not if we aggressively
380 attempt to solve all equalities the moment they occur; that is, when
381 checking (Maybe (a :~: Int)). (NB: solveEqualities fails unless it
382 solves all the kind equalities, which is the right thing at top level.)
383
384 So here the right thing is simply not to do kind generalisation!
385
386 ************************************************************************
387 * *
388 Type-checking modes
389 * *
390 ************************************************************************
391
392 The kind-checker is parameterised by a TcTyMode, which contains some
393 information about where we're checking a type.
394
395 The renamer issues errors about what it can. All errors issued here must
396 concern things that the renamer can't handle.
397
398 -}
399
400 -- | Info about the context in which we're checking a type. Currently,
401 -- differentiates only between types and kinds, but this will likely
402 -- grow, at least to include the distinction between patterns and
403 -- not-patterns.
404 data TcTyMode
405 = TcTyMode { mode_level :: TypeOrKind
406 , mode_unsat :: Bool -- True <=> allow unsaturated type families
407 }
408 -- The mode_unsat field is solely so that type families/synonyms can be unsaturated
409 -- in GHCi :kind calls
410
411 typeLevelMode :: TcTyMode
412 typeLevelMode = TcTyMode { mode_level = TypeLevel, mode_unsat = False }
413
414 kindLevelMode :: TcTyMode
415 kindLevelMode = TcTyMode { mode_level = KindLevel, mode_unsat = False }
416
417 allowUnsaturated :: TcTyMode -> TcTyMode
418 allowUnsaturated mode = mode { mode_unsat = True }
419
420 -- switch to kind level
421 kindLevel :: TcTyMode -> TcTyMode
422 kindLevel mode = mode { mode_level = KindLevel }
423
424 instance Outputable TcTyMode where
425 ppr = ppr . mode_level
426
427 {-
428 Note [Bidirectional type checking]
429 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
430 In expressions, whenever we see a polymorphic identifier, say `id`, we are
431 free to instantiate it with metavariables, knowing that we can always
432 re-generalize with type-lambdas when necessary. For example:
433
434 rank2 :: (forall a. a -> a) -> ()
435 x = rank2 id
436
437 When checking the body of `x`, we can instantiate `id` with a metavariable.
438 Then, when we're checking the application of `rank2`, we notice that we really
439 need a polymorphic `id`, and then re-generalize over the unconstrained
440 metavariable.
441
442 In types, however, we're not so lucky, because *we cannot re-generalize*!
443 There is no lambda. So, we must be careful only to instantiate at the last
444 possible moment, when we're sure we're never going to want the lost polymorphism
445 again. This is done in calls to tcInstBinders.
446
447 To implement this behavior, we use bidirectional type checking, where we
448 explicitly think about whether we know the kind of the type we're checking
449 or not. Note that there is a difference between not knowing a kind and
450 knowing a metavariable kind: the metavariables are TauTvs, and cannot become
451 forall-quantified kinds. Previously (before dependent types), there were
452 no higher-rank kinds, and so we could instantiate early and be sure that
453 no types would have polymorphic kinds, and so we could always assume that
454 the kind of a type was a fresh metavariable. Not so anymore, thus the
455 need for two algorithms.
456
457 For HsType forms that can never be kind-polymorphic, we implement only the
458 "down" direction, where we safely assume a metavariable kind. For HsType forms
459 that *can* be kind-polymorphic, we implement just the "up" (functions with
460 "infer" in their name) version, as we gain nothing by also implementing the
461 "down" version.
462
463 Note [Future-proofing the type checker]
464 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
465 As discussed in Note [Bidirectional type checking], each HsType form is
466 handled in *either* tc_infer_hs_type *or* tc_hs_type. These functions
467 are mutually recursive, so that either one can work for any type former.
468 But, we want to make sure that our pattern-matches are complete. So,
469 we have a bunch of repetitive code just so that we get warnings if we're
470 missing any patterns.
471
472 Note [The tcType invariant]
473 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
474 If tc_ty = tc_hs_type hs_ty exp_kind
475 then
476 typeKind tc_ty = exp_kind
477 without any zonking needed. The reason for this is that in
478 tcInferApps we see (F ty), and we kind-check 'ty' with an
479 expected-kind coming from F. Then, to make the resulting application
480 well kinded --- see Note [Ensure well-kinded types] in TcType --- we
481 need the kind-checked 'ty' to have exactly the kind that F expects,
482 with no funny zonking nonsense in between.
483
484 The tcType invariant also applies to checkExpectedKind: if
485 (tc_ty, _, _) = checkExpectedKind ty act_ki exp_ki
486 then
487 typeKind tc_ty = exp_ki
488 -}
489
490 ------------------------------------------
491 -- | Check and desugar a type, returning the core type and its
492 -- possibly-polymorphic kind. Much like 'tcInferRho' at the expression
493 -- level.
494 tc_infer_lhs_type :: TcTyMode -> LHsType GhcRn -> TcM (TcType, TcKind)
495 tc_infer_lhs_type mode (L span ty)
496 = setSrcSpan span $
497 do { (ty', kind) <- tc_infer_hs_type mode ty
498 ; return (ty', kind) }
499
500 -- | Infer the kind of a type and desugar. This is the "up" type-checker,
501 -- as described in Note [Bidirectional type checking]
502 tc_infer_hs_type :: TcTyMode -> HsType GhcRn -> TcM (TcType, TcKind)
503 tc_infer_hs_type mode (HsTyVar _ (L _ tv)) = tcTyVar mode tv
504 tc_infer_hs_type mode (HsAppTy ty1 ty2)
505 = do { let (fun_ty, arg_tys) = splitHsAppTys ty1 [ty2]
506 ; (fun_ty', fun_kind) <- tc_infer_lhs_type mode fun_ty
507 ; fun_kind' <- zonkTcType fun_kind
508 ; tcTyApps mode fun_ty fun_ty' fun_kind' arg_tys }
509 tc_infer_hs_type mode (HsParTy t) = tc_infer_lhs_type mode t
510 tc_infer_hs_type mode (HsOpTy lhs (L loc_op op) rhs)
511 | not (op `hasKey` funTyConKey)
512 = do { (op', op_kind) <- tcTyVar mode op
513 ; op_kind' <- zonkTcType op_kind
514 ; tcTyApps mode (noLoc $ HsTyVar NotPromoted (L loc_op op)) op' op_kind' [lhs, rhs] }
515 tc_infer_hs_type mode (HsKindSig ty sig)
516 = do { sig' <- tc_lhs_kind (kindLevel mode) sig
517 ; ty' <- tc_lhs_type mode ty sig'
518 ; return (ty', sig') }
519 -- HsSpliced is an annotation produced by 'RnSplice.rnSpliceType' to communicate
520 -- the splice location to the typechecker. Here we skip over it in order to have
521 -- the same kind inferred for a given expression whether it was produced from
522 -- splices or not.
523 --
524 -- See Note [Delaying modFinalizers in untyped splices].
525 tc_infer_hs_type mode (HsSpliceTy (HsSpliced _ (HsSplicedTy ty)) _)
526 = tc_infer_hs_type mode ty
527 tc_infer_hs_type mode (HsDocTy ty _) = tc_infer_lhs_type mode ty
528 tc_infer_hs_type _ (HsCoreTy ty) = return (ty, typeKind ty)
529 tc_infer_hs_type mode other_ty
530 = do { kv <- newMetaKindVar
531 ; ty' <- tc_hs_type mode other_ty kv
532 ; return (ty', kv) }
533
534 ------------------------------------------
535 tc_lhs_type :: TcTyMode -> LHsType GhcRn -> TcKind -> TcM TcType
536 tc_lhs_type mode (L span ty) exp_kind
537 = setSrcSpan span $
538 tc_hs_type mode ty exp_kind
539
540 ------------------------------------------
541 tc_fun_type :: TcTyMode -> LHsType GhcRn -> LHsType GhcRn -> TcKind
542 -> TcM TcType
543 tc_fun_type mode ty1 ty2 exp_kind = case mode_level mode of
544 TypeLevel ->
545 do { arg_k <- newOpenTypeKind
546 ; res_k <- newOpenTypeKind
547 ; ty1' <- tc_lhs_type mode ty1 arg_k
548 ; ty2' <- tc_lhs_type mode ty2 res_k
549 ; checkExpectedKind (HsFunTy ty1 ty2) (mkFunTy ty1' ty2') liftedTypeKind exp_kind }
550 KindLevel -> -- no representation polymorphism in kinds. yet.
551 do { ty1' <- tc_lhs_type mode ty1 liftedTypeKind
552 ; ty2' <- tc_lhs_type mode ty2 liftedTypeKind
553 ; checkExpectedKind (HsFunTy ty1 ty2) (mkFunTy ty1' ty2') liftedTypeKind exp_kind }
554
555 ------------------------------------------
556 tc_hs_type :: TcTyMode -> HsType GhcRn -> TcKind -> TcM TcType
557 -- See Note [The tcType invariant]
558 -- See Note [Bidirectional type checking]
559
560 tc_hs_type mode (HsParTy ty) exp_kind = tc_lhs_type mode ty exp_kind
561 tc_hs_type mode (HsDocTy ty _) exp_kind = tc_lhs_type mode ty exp_kind
562 tc_hs_type _ ty@(HsBangTy {}) _
563 -- While top-level bangs at this point are eliminated (eg !(Maybe Int)),
564 -- other kinds of bangs are not (eg ((!Maybe) Int)). These kinds of
565 -- bangs are invalid, so fail. (#7210)
566 = failWithTc (text "Unexpected strictness annotation:" <+> ppr ty)
567 tc_hs_type _ ty@(HsRecTy _) _
568 -- Record types (which only show up temporarily in constructor
569 -- signatures) should have been removed by now
570 = failWithTc (text "Record syntax is illegal here:" <+> ppr ty)
571
572 -- HsSpliced is an annotation produced by 'RnSplice.rnSpliceType'.
573 -- Here we get rid of it and add the finalizers to the global environment
574 -- while capturing the local environment.
575 --
576 -- See Note [Delaying modFinalizers in untyped splices].
577 tc_hs_type mode (HsSpliceTy (HsSpliced mod_finalizers (HsSplicedTy ty))
578 _
579 )
580 exp_kind
581 = do addModFinalizersWithLclEnv mod_finalizers
582 tc_hs_type mode ty exp_kind
583
584 -- This should never happen; type splices are expanded by the renamer
585 tc_hs_type _ ty@(HsSpliceTy {}) _exp_kind
586 = failWithTc (text "Unexpected type splice:" <+> ppr ty)
587
588 ---------- Functions and applications
589 tc_hs_type mode (HsFunTy ty1 ty2) exp_kind
590 = tc_fun_type mode ty1 ty2 exp_kind
591
592 tc_hs_type mode (HsOpTy ty1 (L _ op) ty2) exp_kind
593 | op `hasKey` funTyConKey
594 = tc_fun_type mode ty1 ty2 exp_kind
595
596 --------- Foralls
597 tc_hs_type mode (HsForAllTy { hst_bndrs = hs_tvs, hst_body = ty }) exp_kind
598 = fmap fst $
599 tcExplicitTKBndrs hs_tvs $ \ tvs' ->
600 -- Do not kind-generalise here! See Note [Kind generalisation]
601 -- Why exp_kind? See Note [Body kind of HsForAllTy]
602 do { ty' <- tc_lhs_type mode ty exp_kind
603 ; let bound_vars = allBoundVariables ty'
604 bndrs = mkTyVarBinders Specified tvs'
605 ; return (mkForAllTys bndrs ty', bound_vars) }
606
607 tc_hs_type mode (HsQualTy { hst_ctxt = ctxt, hst_body = ty }) exp_kind
608 | null (unLoc ctxt)
609 = tc_lhs_type mode ty exp_kind
610
611 | otherwise
612 = do { ctxt' <- tc_hs_context mode ctxt
613
614 -- See Note [Body kind of a HsQualTy]
615 ; ty' <- if isConstraintKind exp_kind
616 then tc_lhs_type mode ty constraintKind
617 else do { ek <- newOpenTypeKind
618 -- The body kind (result of the function)
619 -- can be * or #, hence newOpenTypeKind
620 ; ty' <- tc_lhs_type mode ty ek
621 ; checkExpectedKind (unLoc ty) ty' liftedTypeKind exp_kind }
622
623 ; return (mkPhiTy ctxt' ty') }
624
625 --------- Lists, arrays, and tuples
626 tc_hs_type mode rn_ty@(HsListTy elt_ty) exp_kind
627 = do { tau_ty <- tc_lhs_type mode elt_ty liftedTypeKind
628 ; checkWiredInTyCon listTyCon
629 ; checkExpectedKind rn_ty (mkListTy tau_ty) liftedTypeKind exp_kind }
630
631 tc_hs_type mode rn_ty@(HsPArrTy elt_ty) exp_kind
632 = do { MASSERT( isTypeLevel (mode_level mode) )
633 ; tau_ty <- tc_lhs_type mode elt_ty liftedTypeKind
634 ; checkWiredInTyCon parrTyCon
635 ; checkExpectedKind rn_ty (mkPArrTy tau_ty) liftedTypeKind exp_kind }
636
637 -- See Note [Distinguishing tuple kinds] in HsTypes
638 -- See Note [Inferring tuple kinds]
639 tc_hs_type mode rn_ty@(HsTupleTy HsBoxedOrConstraintTuple hs_tys) exp_kind
640 -- (NB: not zonking before looking at exp_k, to avoid left-right bias)
641 | Just tup_sort <- tupKindSort_maybe exp_kind
642 = traceTc "tc_hs_type tuple" (ppr hs_tys) >>
643 tc_tuple rn_ty mode tup_sort hs_tys exp_kind
644 | otherwise
645 = do { traceTc "tc_hs_type tuple 2" (ppr hs_tys)
646 ; (tys, kinds) <- mapAndUnzipM (tc_infer_lhs_type mode) hs_tys
647 ; kinds <- mapM zonkTcType kinds
648 -- Infer each arg type separately, because errors can be
649 -- confusing if we give them a shared kind. Eg Trac #7410
650 -- (Either Int, Int), we do not want to get an error saying
651 -- "the second argument of a tuple should have kind *->*"
652
653 ; let (arg_kind, tup_sort)
654 = case [ (k,s) | k <- kinds
655 , Just s <- [tupKindSort_maybe k] ] of
656 ((k,s) : _) -> (k,s)
657 [] -> (liftedTypeKind, BoxedTuple)
658 -- In the [] case, it's not clear what the kind is, so guess *
659
660 ; tys' <- sequence [ setSrcSpan loc $
661 checkExpectedKind hs_ty ty kind arg_kind
662 | ((L loc hs_ty),ty,kind) <- zip3 hs_tys tys kinds ]
663
664 ; finish_tuple rn_ty tup_sort tys' (map (const arg_kind) tys') exp_kind }
665
666
667 tc_hs_type mode rn_ty@(HsTupleTy hs_tup_sort tys) exp_kind
668 = tc_tuple rn_ty mode tup_sort tys exp_kind
669 where
670 tup_sort = case hs_tup_sort of -- Fourth case dealt with above
671 HsUnboxedTuple -> UnboxedTuple
672 HsBoxedTuple -> BoxedTuple
673 HsConstraintTuple -> ConstraintTuple
674 _ -> panic "tc_hs_type HsTupleTy"
675
676 tc_hs_type mode rn_ty@(HsSumTy hs_tys) exp_kind
677 = do { let arity = length hs_tys
678 ; arg_kinds <- mapM (\_ -> newOpenTypeKind) hs_tys
679 ; tau_tys <- zipWithM (tc_lhs_type mode) hs_tys arg_kinds
680 ; let arg_reps = map getRuntimeRepFromKind arg_kinds
681 arg_tys = arg_reps ++ tau_tys
682 ; checkExpectedKind rn_ty
683 (mkTyConApp (sumTyCon arity) arg_tys)
684 (unboxedSumKind arg_reps)
685 exp_kind
686 }
687
688 --------- Promoted lists and tuples
689 tc_hs_type mode rn_ty@(HsExplicitListTy _ _k tys) exp_kind
690 = do { tks <- mapM (tc_infer_lhs_type mode) tys
691 ; (taus', kind) <- unifyKinds tys tks
692 ; let ty = (foldr (mk_cons kind) (mk_nil kind) taus')
693 ; checkExpectedKind rn_ty ty (mkListTy kind) exp_kind }
694 where
695 mk_cons k a b = mkTyConApp (promoteDataCon consDataCon) [k, a, b]
696 mk_nil k = mkTyConApp (promoteDataCon nilDataCon) [k]
697
698 tc_hs_type mode rn_ty@(HsExplicitTupleTy _ tys) exp_kind
699 -- using newMetaKindVar means that we force instantiations of any polykinded
700 -- types. At first, I just used tc_infer_lhs_type, but that led to #11255.
701 = do { ks <- replicateM arity newMetaKindVar
702 ; taus <- zipWithM (tc_lhs_type mode) tys ks
703 ; let kind_con = tupleTyCon Boxed arity
704 ty_con = promotedTupleDataCon Boxed arity
705 tup_k = mkTyConApp kind_con ks
706 ; checkExpectedKind rn_ty (mkTyConApp ty_con (ks ++ taus)) tup_k exp_kind }
707 where
708 arity = length tys
709
710 --------- Constraint types
711 tc_hs_type mode rn_ty@(HsIParamTy (L _ n) ty) exp_kind
712 = do { MASSERT( isTypeLevel (mode_level mode) )
713 ; ty' <- tc_lhs_type mode ty liftedTypeKind
714 ; let n' = mkStrLitTy $ hsIPNameFS n
715 ; ipClass <- tcLookupClass ipClassName
716 ; checkExpectedKind rn_ty (mkClassPred ipClass [n',ty'])
717 constraintKind exp_kind }
718
719 tc_hs_type mode rn_ty@(HsEqTy ty1 ty2) exp_kind
720 = do { (ty1', kind1) <- tc_infer_lhs_type mode ty1
721 ; (ty2', kind2) <- tc_infer_lhs_type mode ty2
722 ; ty2'' <- checkExpectedKind (unLoc ty2) ty2' kind2 kind1
723 ; eq_tc <- tcLookupTyCon eqTyConName
724 ; let ty' = mkNakedTyConApp eq_tc [kind1, ty1', ty2'']
725 ; checkExpectedKind rn_ty ty' constraintKind exp_kind }
726
727 --------- Literals
728 tc_hs_type _ rn_ty@(HsTyLit (HsNumTy _ n)) exp_kind
729 = do { checkWiredInTyCon typeNatKindCon
730 ; checkExpectedKind rn_ty (mkNumLitTy n) typeNatKind exp_kind }
731
732 tc_hs_type _ rn_ty@(HsTyLit (HsStrTy _ s)) exp_kind
733 = do { checkWiredInTyCon typeSymbolKindCon
734 ; checkExpectedKind rn_ty (mkStrLitTy s) typeSymbolKind exp_kind }
735
736 --------- Potentially kind-polymorphic types: call the "up" checker
737 -- See Note [Future-proofing the type checker]
738 tc_hs_type mode ty@(HsTyVar {}) ek = tc_infer_hs_type_ek mode ty ek
739 tc_hs_type mode ty@(HsAppTy {}) ek = tc_infer_hs_type_ek mode ty ek
740 tc_hs_type mode ty@(HsOpTy {}) ek = tc_infer_hs_type_ek mode ty ek
741 tc_hs_type mode ty@(HsKindSig {}) ek = tc_infer_hs_type_ek mode ty ek
742 tc_hs_type mode ty@(HsCoreTy {}) ek = tc_infer_hs_type_ek mode ty ek
743
744 tc_hs_type _ (HsWildCardTy wc) exp_kind
745 = do { wc_tv <- tcWildCardOcc wc exp_kind
746 ; return (mkNakedCastTy (mkTyVarTy wc_tv)
747 (mkTcNomReflCo exp_kind))
748 -- Take care here! Even though the coercion is Refl,
749 -- we still need it to establish Note [The tcType invariant]
750 }
751
752 -- disposed of by renamer
753 tc_hs_type _ ty@(HsAppsTy {}) _
754 = pprPanic "tc_hs_tyep HsAppsTy" (ppr ty)
755
756 tcWildCardOcc :: HsWildCardInfo GhcRn -> Kind -> TcM TcTyVar
757 tcWildCardOcc wc_info exp_kind
758 = do { wc_tv <- tcLookupTyVar (wildCardName wc_info)
759 -- The wildcard's kind should be an un-filled-in meta tyvar
760 ; let Just wc_kind_var = tcGetTyVar_maybe (tyVarKind wc_tv)
761 ; writeMetaTyVar wc_kind_var exp_kind
762 ; return wc_tv }
763
764 ---------------------------
765 -- | Call 'tc_infer_hs_type' and check its result against an expected kind.
766 tc_infer_hs_type_ek :: TcTyMode -> HsType GhcRn -> TcKind -> TcM TcType
767 tc_infer_hs_type_ek mode hs_ty ek
768 = do { (ty, k) <- tc_infer_hs_type mode hs_ty
769 ; checkExpectedKind hs_ty ty k ek }
770
771 ---------------------------
772 tupKindSort_maybe :: TcKind -> Maybe TupleSort
773 tupKindSort_maybe k
774 | Just (k', _) <- splitCastTy_maybe k = tupKindSort_maybe k'
775 | Just k' <- tcView k = tupKindSort_maybe k'
776 | isConstraintKind k = Just ConstraintTuple
777 | isLiftedTypeKind k = Just BoxedTuple
778 | otherwise = Nothing
779
780 tc_tuple :: HsType GhcRn -> TcTyMode -> TupleSort -> [LHsType GhcRn] -> TcKind -> TcM TcType
781 tc_tuple rn_ty mode tup_sort tys exp_kind
782 = do { arg_kinds <- case tup_sort of
783 BoxedTuple -> return (nOfThem arity liftedTypeKind)
784 UnboxedTuple -> mapM (\_ -> newOpenTypeKind) tys
785 ConstraintTuple -> return (nOfThem arity constraintKind)
786 ; tau_tys <- zipWithM (tc_lhs_type mode) tys arg_kinds
787 ; finish_tuple rn_ty tup_sort tau_tys arg_kinds exp_kind }
788 where
789 arity = length tys
790
791 finish_tuple :: HsType GhcRn
792 -> TupleSort
793 -> [TcType] -- ^ argument types
794 -> [TcKind] -- ^ of these kinds
795 -> TcKind -- ^ expected kind of the whole tuple
796 -> TcM TcType
797 finish_tuple rn_ty tup_sort tau_tys tau_kinds exp_kind
798 = do { traceTc "finish_tuple" (ppr res_kind $$ ppr tau_kinds $$ ppr exp_kind)
799 ; let arg_tys = case tup_sort of
800 -- See also Note [Unboxed tuple RuntimeRep vars] in TyCon
801 UnboxedTuple -> tau_reps ++ tau_tys
802 BoxedTuple -> tau_tys
803 ConstraintTuple -> tau_tys
804 ; tycon <- case tup_sort of
805 ConstraintTuple
806 | arity > mAX_CTUPLE_SIZE
807 -> failWith (bigConstraintTuple arity)
808 | otherwise -> tcLookupTyCon (cTupleTyConName arity)
809 BoxedTuple -> do { let tc = tupleTyCon Boxed arity
810 ; checkWiredInTyCon tc
811 ; return tc }
812 UnboxedTuple -> return (tupleTyCon Unboxed arity)
813 ; checkExpectedKind rn_ty (mkTyConApp tycon arg_tys) res_kind exp_kind }
814 where
815 arity = length tau_tys
816 tau_reps = map getRuntimeRepFromKind tau_kinds
817 res_kind = case tup_sort of
818 UnboxedTuple -> unboxedTupleKind tau_reps
819 BoxedTuple -> liftedTypeKind
820 ConstraintTuple -> constraintKind
821
822 bigConstraintTuple :: Arity -> MsgDoc
823 bigConstraintTuple arity
824 = hang (text "Constraint tuple arity too large:" <+> int arity
825 <+> parens (text "max arity =" <+> int mAX_CTUPLE_SIZE))
826 2 (text "Instead, use a nested tuple")
827
828 ---------------------------
829 -- | Apply a type of a given kind to a list of arguments. This instantiates
830 -- invisible parameters as necessary. Always consumes all the arguments,
831 -- using matchExpectedFunKind as necessary.
832 -- This takes an optional @VarEnv Kind@ which maps kind variables to kinds.
833 -- These kinds should be used to instantiate invisible kind variables;
834 -- they come from an enclosing class for an associated type/data family.
835 tcInferApps :: TcTyMode
836 -> Maybe (VarEnv Kind) -- ^ Possibly, kind info (see above)
837 -> LHsType GhcRn -- ^ Function (for printing only)
838 -> TcType -- ^ Function (could be knot-tied)
839 -> TcKind -- ^ Function kind (zonked)
840 -> [LHsType GhcRn] -- ^ Args
841 -> TcM (TcType, [TcType], TcKind) -- ^ (f args, args, result kind)
842 tcInferApps mode mb_kind_info orig_hs_ty fun_ty fun_ki orig_hs_args
843 = do { traceTc "tcInferApps" (ppr orig_hs_ty $$ ppr orig_hs_args $$ ppr fun_ki)
844 ; go 1 [] empty_subst fun_ty orig_ki_binders orig_inner_ki orig_hs_args }
845 where
846 empty_subst = mkEmptyTCvSubst $ mkInScopeSet $
847 tyCoVarsOfType fun_ki
848 (orig_ki_binders, orig_inner_ki) = tcSplitPiTys fun_ki
849
850 go :: Int -- the # of the next argument
851 -> [TcType] -- already type-checked args, in reverse order
852 -> TCvSubst -- instantiating substitution
853 -> TcType -- function applied to some args, could be knot-tied
854 -> [TyBinder] -- binders in function kind (both vis. and invis.)
855 -> TcKind -- function kind body (not a Pi-type)
856 -> [LHsType GhcRn] -- un-type-checked args
857 -> TcM (TcType, [TcType], TcKind) -- same as overall return type
858
859 -- no user-written args left. We're done!
860 go _ acc_args subst fun ki_binders inner_ki []
861 = return (fun, reverse acc_args, substTy subst $ mkPiTys ki_binders inner_ki)
862
863 -- The function's kind has a binder. Is it visible or invisible?
864 go n acc_args subst fun (ki_binder:ki_binders) inner_ki
865 all_args@(arg:args)
866 | isInvisibleBinder ki_binder
867 -- It's invisible. Instantiate.
868 = do { traceTc "tcInferApps (invis)" (ppr ki_binder $$ ppr subst)
869 ; (subst', arg') <- tcInstBinder mb_kind_info subst ki_binder
870 ; go n (arg' : acc_args) subst' (mkNakedAppTy fun arg')
871 ki_binders inner_ki all_args }
872
873 | otherwise
874 -- It's visible. Check the next user-written argument
875 = do { traceTc "tcInferApps (vis)" (vcat [ ppr ki_binder, ppr arg
876 , ppr (tyBinderType ki_binder)
877 , ppr subst ])
878 ; arg' <- addErrCtxt (funAppCtxt orig_hs_ty arg n) $
879 tc_lhs_type mode arg (substTy subst $ tyBinderType ki_binder)
880 ; traceTc "tcInferApps (vis2)" (vcat [ ppr ki_binder, ppr arg
881 , ppr arg', ppr (typeKind arg')
882 , ppr (substTy subst $ tyBinderType ki_binder)
883 , ppr subst ])
884 ; let subst' = extendTvSubstBinderAndInScope subst ki_binder arg'
885 ; go (n+1) (arg' : acc_args) subst' (mkNakedAppTy fun arg')
886 ki_binders inner_ki args }
887
888 -- We've run out of known binders in the functions's kind.
889 go n acc_args subst fun [] inner_ki all_args
890 | not (null new_ki_binders)
891 -- But, after substituting, we have more binders.
892 = go n acc_args zapped_subst fun new_ki_binders new_inner_ki all_args
893
894 | otherwise
895 -- Even after substituting, still no binders. Use matchExpectedFunKind
896 = do { traceTc "tcInferApps (no binder)" (ppr new_inner_ki $$ ppr zapped_subst)
897 ; (co, arg_k, res_k) <- matchExpectedFunKind hs_ty substed_inner_ki
898 ; let new_in_scope = tyCoVarsOfTypes [arg_k, res_k]
899 subst' = zapped_subst `extendTCvInScopeSet` new_in_scope
900 ; go n acc_args subst'
901 (fun `mkNakedCastTy` co)
902 [mkAnonBinder arg_k]
903 res_k all_args }
904 where
905 substed_inner_ki = substTy subst inner_ki
906 (new_ki_binders, new_inner_ki) = tcSplitPiTys substed_inner_ki
907 zapped_subst = zapTCvSubst subst
908 hs_ty = mkHsAppTys orig_hs_ty (take (n-1) orig_hs_args)
909
910
911 -- | Applies a type to a list of arguments.
912 -- Always consumes all the arguments, using 'matchExpectedFunKind' as
913 -- necessary. If you wish to apply a type to a list of HsTypes, this is
914 -- your function.
915 -- Used for type-checking types only.
916 tcTyApps :: TcTyMode
917 -> LHsType GhcRn -- ^ Function (for printing only)
918 -> TcType -- ^ Function (could be knot-tied)
919 -> TcKind -- ^ Function kind (zonked)
920 -> [LHsType GhcRn] -- ^ Args
921 -> TcM (TcType, TcKind) -- ^ (f args, result kind)
922 tcTyApps mode orig_hs_ty ty ki args
923 = do { (ty', _args, ki') <- tcInferApps mode Nothing orig_hs_ty ty ki args
924 ; return (ty', ki') }
925
926 --------------------------
927 -- Like checkExpectedKindX, but returns only the final type; convenient wrapper
928 -- Obeys Note [The tcType invariant]
929 checkExpectedKind :: HsType GhcRn
930 -> TcType
931 -> TcKind
932 -> TcKind
933 -> TcM TcType
934 checkExpectedKind hs_ty ty act exp
935 = fstOf3 <$> checkExpectedKindX Nothing (ppr hs_ty) ty act exp
936
937 checkExpectedKindX :: Maybe (VarEnv Kind) -- Possibly, instantiations for kind vars
938 -> SDoc -- HsType whose kind we're checking
939 -> TcType -- the type whose kind we're checking
940 -> TcKind -- the known kind of that type, k
941 -> TcKind -- the expected kind, exp_kind
942 -> TcM (TcType, [TcType], TcCoercionN)
943 -- (the new args, the coercion)
944 -- Instantiate a kind (if necessary) and then call unifyType
945 -- (checkExpectedKind ty act_kind exp_kind)
946 -- checks that the actual kind act_kind is compatible
947 -- with the expected kind exp_kind
948 checkExpectedKindX mb_kind_env pp_hs_ty ty act_kind exp_kind
949 = do { -- We need to make sure that both kinds have the same number of implicit
950 -- foralls out front. If the actual kind has more, instantiate accordingly.
951 -- Otherwise, just pass the type & kind through: the errors are caught
952 -- in unifyType.
953 let (exp_bndrs, _) = splitPiTysInvisible exp_kind
954 n_exp = length exp_bndrs
955 ; (new_args, act_kind') <- instantiateTyUntilN mb_kind_env n_exp act_kind
956
957 ; let origin = TypeEqOrigin { uo_actual = act_kind'
958 , uo_expected = exp_kind
959 , uo_thing = Just pp_hs_ty
960 , uo_visible = True } -- the hs_ty is visible
961 ty' = mkNakedAppTys ty new_args
962
963 ; if act_kind' `tcEqType` exp_kind
964 then return (ty', new_args, mkTcNomReflCo exp_kind) -- This is very common
965 else do { co_k <- uType KindLevel origin act_kind' exp_kind
966 ; traceTc "checkExpectedKind" (vcat [ ppr act_kind
967 , ppr exp_kind
968 , ppr co_k ])
969 ; let result_ty = ty' `mkNakedCastTy` co_k
970 -- See Note [The tcType invariant]
971 ; return (result_ty, new_args, co_k) } }
972
973 -- | Instantiate @n@ invisible arguments to a type. If @n <= 0@, no instantiation
974 -- occurs. If @n@ is too big, then all available invisible arguments are instantiated.
975 -- (In other words, this function is very forgiving about bad values of @n@.)
976 instantiateTyN :: Maybe (VarEnv Kind) -- ^ Predetermined instantiations
977 -- (for assoc. type patterns)
978 -> Int -- ^ @n@
979 -> [TyBinder] -> TcKind -- ^ its kind
980 -> TcM ([TcType], TcKind) -- ^ The inst'ed type, new args, kind
981 instantiateTyN mb_kind_env n bndrs inner_ki
982 | n <= 0
983 = return ([], ki)
984
985 | otherwise
986 = do { (subst, inst_args) <- tcInstBinders empty_subst mb_kind_env inst_bndrs
987 ; let rebuilt_ki = mkPiTys leftover_bndrs inner_ki
988 ki' = substTy subst rebuilt_ki
989 ; traceTc "instantiateTyN" (vcat [ ppr ki
990 , ppr n
991 , ppr subst
992 , ppr rebuilt_ki
993 , ppr ki' ])
994 ; return (inst_args, ki') }
995 where
996 -- NB: splitAt is forgiving with invalid numbers
997 (inst_bndrs, leftover_bndrs) = splitAt n bndrs
998 ki = mkPiTys bndrs inner_ki
999 empty_subst = mkEmptyTCvSubst (mkInScopeSet (tyCoVarsOfType ki))
1000
1001 -- | Instantiate a type to have at most @n@ invisible arguments.
1002 instantiateTyUntilN :: Maybe (VarEnv Kind) -- ^ Possibly, instantiations for vars
1003 -> Int -- ^ @n@
1004 -> TcKind -- ^ its kind
1005 -> TcM ([TcType], TcKind) -- ^ The new args, final kind
1006 instantiateTyUntilN mb_kind_env n ki
1007 = let (bndrs, inner_ki) = splitPiTysInvisible ki
1008 num_to_inst = length bndrs - n
1009 in
1010 instantiateTyN mb_kind_env num_to_inst bndrs inner_ki
1011
1012 ---------------------------
1013 tcHsMbContext :: Maybe (LHsContext GhcRn) -> TcM [PredType]
1014 tcHsMbContext Nothing = return []
1015 tcHsMbContext (Just cxt) = tcHsContext cxt
1016
1017 tcHsContext :: LHsContext GhcRn -> TcM [PredType]
1018 tcHsContext = tc_hs_context typeLevelMode
1019
1020 tcLHsPredType :: LHsType GhcRn -> TcM PredType
1021 tcLHsPredType = tc_lhs_pred typeLevelMode
1022
1023 tc_hs_context :: TcTyMode -> LHsContext GhcRn -> TcM [PredType]
1024 tc_hs_context mode ctxt = mapM (tc_lhs_pred mode) (unLoc ctxt)
1025
1026 tc_lhs_pred :: TcTyMode -> LHsType GhcRn -> TcM PredType
1027 tc_lhs_pred mode pred = tc_lhs_type mode pred constraintKind
1028
1029 ---------------------------
1030 tcTyVar :: TcTyMode -> Name -> TcM (TcType, TcKind)
1031 -- See Note [Type checking recursive type and class declarations]
1032 -- in TcTyClsDecls
1033 tcTyVar mode name -- Could be a tyvar, a tycon, or a datacon
1034 = do { traceTc "lk1" (ppr name)
1035 ; thing <- tcLookup name
1036 ; case thing of
1037 ATyVar _ tv -> return (mkTyVarTy tv, tyVarKind tv)
1038
1039 ATcTyCon tc_tc -> do { -- See Note [GADT kind self-reference]
1040 unless
1041 (isTypeLevel (mode_level mode))
1042 (promotionErr name TyConPE)
1043 ; check_tc tc_tc
1044 ; tc <- get_loopy_tc name tc_tc
1045 ; handle_tyfams tc tc_tc }
1046 -- mkNakedTyConApp: see Note [Type-checking inside the knot]
1047 -- NB: we really should check if we're at the kind level
1048 -- and if the tycon is promotable if -XNoTypeInType is set.
1049 -- But this is a terribly large amount of work! Not worth it.
1050
1051 AGlobal (ATyCon tc)
1052 -> do { check_tc tc
1053 ; handle_tyfams tc tc }
1054
1055 AGlobal (AConLike (RealDataCon dc))
1056 -> do { data_kinds <- xoptM LangExt.DataKinds
1057 ; unless (data_kinds || specialPromotedDc dc) $
1058 promotionErr name NoDataKindsDC
1059 ; type_in_type <- xoptM LangExt.TypeInType
1060 ; unless ( type_in_type ||
1061 ( isTypeLevel (mode_level mode) &&
1062 isLegacyPromotableDataCon dc ) ||
1063 ( isKindLevel (mode_level mode) &&
1064 specialPromotedDc dc ) ) $
1065 promotionErr name NoTypeInTypeDC
1066 ; let tc = promoteDataCon dc
1067 ; return (mkNakedTyConApp tc [], tyConKind tc) }
1068
1069 APromotionErr err -> promotionErr name err
1070
1071 _ -> wrongThingErr "type" thing name }
1072 where
1073 check_tc :: TyCon -> TcM ()
1074 check_tc tc = do { type_in_type <- xoptM LangExt.TypeInType
1075 ; data_kinds <- xoptM LangExt.DataKinds
1076 ; unless (isTypeLevel (mode_level mode) ||
1077 data_kinds ||
1078 isKindTyCon tc) $
1079 promotionErr name NoDataKindsTC
1080 ; unless (isTypeLevel (mode_level mode) ||
1081 type_in_type ||
1082 isLegacyPromotableTyCon tc) $
1083 promotionErr name NoTypeInTypeTC }
1084
1085 -- if we are type-checking a type family tycon, we must instantiate
1086 -- any invisible arguments right away. Otherwise, we get #11246
1087 handle_tyfams :: TyCon -- the tycon to instantiate (might be loopy)
1088 -> TcTyCon -- a non-loopy version of the tycon
1089 -> TcM (TcType, TcKind)
1090 handle_tyfams tc tc_tc
1091 | mightBeUnsaturatedTyCon tc_tc || mode_unsat mode
1092 -- This is where mode_unsat is used
1093 = do { traceTc "tcTyVar2a" (ppr tc_tc $$ ppr tc_kind)
1094 ; return (mkNakedTyConApp tc [], tc_kind) }
1095
1096 | otherwise
1097 = do { (tc_args, kind) <- instantiateTyN Nothing (length (tyConBinders tc_tc))
1098 tc_kind_bndrs tc_inner_ki
1099 ; let tc_ty = mkNakedTyConApp tc tc_args
1100 -- tc and tc_ty must not be traced here, because that would
1101 -- force the evaluation of a potentially knot-tied variable (tc),
1102 -- and the typechecker would hang, as per #11708
1103 ; traceTc "tcTyVar2b" (vcat [ ppr tc_tc <+> dcolon <+> ppr tc_kind
1104 , ppr kind ])
1105 ; return (tc_ty, kind) }
1106 where
1107 tc_kind = tyConKind tc_tc
1108 (tc_kind_bndrs, tc_inner_ki) = splitPiTysInvisible tc_kind
1109
1110 get_loopy_tc :: Name -> TyCon -> TcM TyCon
1111 -- Return the knot-tied global TyCon if there is one
1112 -- Otherwise the local TcTyCon; we must be doing kind checking
1113 -- but we still want to return a TyCon of some sort to use in
1114 -- error messages
1115 get_loopy_tc name tc_tc
1116 = do { env <- getGblEnv
1117 ; case lookupNameEnv (tcg_type_env env) name of
1118 Just (ATyCon tc) -> return tc
1119 _ -> do { traceTc "lk1 (loopy)" (ppr name)
1120 ; return tc_tc } }
1121
1122 tcClass :: Name -> TcM (Class, TcKind)
1123 tcClass cls -- Must be a class
1124 = do { thing <- tcLookup cls
1125 ; case thing of
1126 ATcTyCon tc -> return (aThingErr "tcClass" cls, tyConKind tc)
1127 AGlobal (ATyCon tc)
1128 | Just cls <- tyConClass_maybe tc
1129 -> return (cls, tyConKind tc)
1130 _ -> wrongThingErr "class" thing cls }
1131
1132
1133 aThingErr :: String -> Name -> b
1134 -- The type checker for types is sometimes called simply to
1135 -- do *kind* checking; and in that case it ignores the type
1136 -- returned. Which is a good thing since it may not be available yet!
1137 aThingErr str x = pprPanic "AThing evaluated unexpectedly" (text str <+> ppr x)
1138
1139 {-
1140 Note [Type-checking inside the knot]
1141 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1142 Suppose we are checking the argument types of a data constructor. We
1143 must zonk the types before making the DataCon, because once built we
1144 can't change it. So we must traverse the type.
1145
1146 BUT the parent TyCon is knot-tied, so we can't look at it yet.
1147
1148 So we must be careful not to use "smart constructors" for types that
1149 look at the TyCon or Class involved.
1150
1151 * Hence the use of mkNakedXXX functions. These do *not* enforce
1152 the invariants (for example that we use (FunTy s t) rather
1153 than (TyConApp (->) [s,t])).
1154
1155 * The zonking functions establish invariants (even zonkTcType, a change from
1156 previous behaviour). So we must never inspect the result of a
1157 zonk that might mention a knot-tied TyCon. This is generally OK
1158 because we zonk *kinds* while kind-checking types. And the TyCons
1159 in kinds shouldn't be knot-tied, because they come from a previous
1160 mutually recursive group.
1161
1162 * TcHsSyn.zonkTcTypeToType also can safely check/establish
1163 invariants.
1164
1165 This is horribly delicate. I hate it. A good example of how
1166 delicate it is can be seen in Trac #7903.
1167
1168 Note [GADT kind self-reference]
1169 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1170
1171 A promoted type cannot be used in the body of that type's declaration.
1172 Trac #11554 shows this example, which made GHC loop:
1173
1174 import Data.Kind
1175 data P (x :: k) = Q
1176 data A :: Type where
1177 B :: forall (a :: A). P a -> A
1178
1179 In order to check the constructor B, we need to have the promoted type A, but in
1180 order to get that promoted type, B must first be checked. To prevent looping, a
1181 TyConPE promotion error is given when tcTyVar checks an ATcTyCon in kind mode.
1182 Any ATcTyCon is a TyCon being defined in the current recursive group (see data
1183 type decl for TcTyThing), and all such TyCons are illegal in kinds.
1184
1185 Trac #11962 proposes checking the head of a data declaration separately from
1186 its constructors. This would allow the example above to pass.
1187
1188 Note [Body kind of a HsForAllTy]
1189 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1190 The body of a forall is usually a type, but in principle
1191 there's no reason to prohibit *unlifted* types.
1192 In fact, GHC can itself construct a function with an
1193 unboxed tuple inside a for-all (via CPR analysis; see
1194 typecheck/should_compile/tc170).
1195
1196 Moreover in instance heads we get forall-types with
1197 kind Constraint.
1198
1199 It's tempting to check that the body kind is either * or #. But this is
1200 wrong. For example:
1201
1202 class C a b
1203 newtype N = Mk Foo deriving (C a)
1204
1205 We're doing newtype-deriving for C. But notice how `a` isn't in scope in
1206 the predicate `C a`. So we quantify, yielding `forall a. C a` even though
1207 `C a` has kind `* -> Constraint`. The `forall a. C a` is a bit cheeky, but
1208 convenient. Bottom line: don't check for * or # here.
1209
1210 Note [Body kind of a HsQualTy]
1211 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1212 If ctxt is non-empty, the HsQualTy really is a /function/, so the
1213 kind of the result really is '*', and in that case the kind of the
1214 body-type can be lifted or unlifted.
1215
1216 However, consider
1217 instance Eq a => Eq [a] where ...
1218 or
1219 f :: (Eq a => Eq [a]) => blah
1220 Here both body-kind of the HsQualTy is Constraint rather than *.
1221 Rather crudely we tell the difference by looking at exp_kind. It's
1222 very convenient to typecheck instance types like any other HsSigType.
1223
1224 Admittedly the '(Eq a => Eq [a]) => blah' case is erroneous, but it's
1225 better to reject in checkValidType. If we say that the body kind
1226 should be '*' we risk getting TWO error messages, one saying that Eq
1227 [a] doens't have kind '*', and one saying that we need a Constraint to
1228 the left of the outer (=>).
1229
1230 How do we figure out the right body kind? Well, it's a bit of a
1231 kludge: I just look at the expected kind. If it's Constraint, we
1232 must be in this instance situation context. It's a kludge because it
1233 wouldn't work if any unification was involved to compute that result
1234 kind -- but it isn't. (The true way might be to use the 'mode'
1235 parameter, but that seemed like a sledgehammer to crack a nut.)
1236
1237 Note [Inferring tuple kinds]
1238 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1239 Give a tuple type (a,b,c), which the parser labels as HsBoxedOrConstraintTuple,
1240 we try to figure out whether it's a tuple of kind * or Constraint.
1241 Step 1: look at the expected kind
1242 Step 2: infer argument kinds
1243
1244 If after Step 2 it's not clear from the arguments that it's
1245 Constraint, then it must be *. Once having decided that we re-check
1246 the Check the arguments again to give good error messages
1247 in eg. `(Maybe, Maybe)`
1248
1249 Note that we will still fail to infer the correct kind in this case:
1250
1251 type T a = ((a,a), D a)
1252 type family D :: Constraint -> Constraint
1253
1254 While kind checking T, we do not yet know the kind of D, so we will default the
1255 kind of T to * -> *. It works if we annotate `a` with kind `Constraint`.
1256
1257 Note [Desugaring types]
1258 ~~~~~~~~~~~~~~~~~~~~~~~
1259 The type desugarer is phase 2 of dealing with HsTypes. Specifically:
1260
1261 * It transforms from HsType to Type
1262
1263 * It zonks any kinds. The returned type should have no mutable kind
1264 or type variables (hence returning Type not TcType):
1265 - any unconstrained kind variables are defaulted to (Any *) just
1266 as in TcHsSyn.
1267 - there are no mutable type variables because we are
1268 kind-checking a type
1269 Reason: the returned type may be put in a TyCon or DataCon where
1270 it will never subsequently be zonked.
1271
1272 You might worry about nested scopes:
1273 ..a:kappa in scope..
1274 let f :: forall b. T '[a,b] -> Int
1275 In this case, f's type could have a mutable kind variable kappa in it;
1276 and we might then default it to (Any *) when dealing with f's type
1277 signature. But we don't expect this to happen because we can't get a
1278 lexically scoped type variable with a mutable kind variable in it. A
1279 delicate point, this. If it becomes an issue we might need to
1280 distinguish top-level from nested uses.
1281
1282 Moreover
1283 * it cannot fail,
1284 * it does no unifications
1285 * it does no validity checking, except for structural matters, such as
1286 (a) spurious ! annotations.
1287 (b) a class used as a type
1288
1289 Note [Kind of a type splice]
1290 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1291 Consider these terms, each with TH type splice inside:
1292 [| e1 :: Maybe $(..blah..) |]
1293 [| e2 :: $(..blah..) |]
1294 When kind-checking the type signature, we'll kind-check the splice
1295 $(..blah..); we want to give it a kind that can fit in any context,
1296 as if $(..blah..) :: forall k. k.
1297
1298 In the e1 example, the context of the splice fixes kappa to *. But
1299 in the e2 example, we'll desugar the type, zonking the kind unification
1300 variables as we go. When we encounter the unconstrained kappa, we
1301 want to default it to '*', not to (Any *).
1302
1303
1304 Help functions for type applications
1305 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1306 -}
1307
1308 addTypeCtxt :: LHsType GhcRn -> TcM a -> TcM a
1309 -- Wrap a context around only if we want to show that contexts.
1310 -- Omit invisible ones and ones user's won't grok
1311 addTypeCtxt (L _ ty) thing
1312 = addErrCtxt doc thing
1313 where
1314 doc = text "In the type" <+> quotes (ppr ty)
1315
1316 {-
1317 ************************************************************************
1318 * *
1319 Type-variable binders
1320 %* *
1321 %************************************************************************
1322
1323 Note [Scope-check inferred kinds]
1324 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1325 Consider
1326
1327 data SameKind :: k -> k -> *
1328 foo :: forall a (b :: Proxy a) (c :: Proxy d). SameKind b c
1329
1330 d has no binding site. So it gets bound implicitly, at the top. The
1331 problem is that d's kind mentions `a`. So it's all ill-scoped.
1332
1333 The way we check for this is to gather all variables *bound* in a
1334 type variable's scope. The type variable's kind should not mention
1335 any of these variables. That is, d's kind can't mention a, b, or c.
1336 We can't just check to make sure that d's kind is in scope, because
1337 we might be about to kindGeneralize.
1338
1339 A little messy, but it works.
1340
1341 Note [Dependent LHsQTyVars]
1342 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
1343 We track (in the renamer) which explicitly bound variables in a
1344 LHsQTyVars are manifestly dependent; only precisely these variables
1345 may be used within the LHsQTyVars. We must do this so that kcLHsQTyVars
1346 can produce the right TyConBinders, and tell Anon vs. Required.
1347
1348 Example data T k1 (a:k1) (b:k2) c
1349 = MkT (Proxy a) (Proxy b) (Proxy c)
1350
1351 Here
1352 (a:k1),(b:k2),(c:k3)
1353 are Anon (explicitly specified as a binder, not used
1354 in the kind of any other binder
1355 k1 is Required (explicitly specifed as a binder, but used
1356 in the kind of another binder i.e. dependently)
1357 k2 is Specified (not explicitly bound, but used in the kind
1358 of another binder)
1359 k3 in Inferred (not lexically in scope at all, but inferred
1360 by kind inference)
1361 and
1362 T :: forall {k3} k1. forall k3 -> k1 -> k2 -> k3 -> *
1363
1364 See Note [TyVarBndrs, TyVarBinders, TyConBinders, and visibility]
1365 in TyCoRep.
1366
1367 kcLHsQTyVars uses the hsq_dependent field to decide whether
1368 k1, a, b, c should be Required or Anon.
1369
1370 Earlier, thought it would work simply to do a free-variable check
1371 during kcLHsQTyVars, but this is bogus, because there may be
1372 unsolved equalities about. And we don't want to eagerly solve the
1373 equalities, because we may get further information after
1374 kcLHsQTyVars is called. (Recall that kcLHsQTyVars is usually
1375 called from getInitialKind. The only other case is in kcConDecl.)
1376 This is what implements the rule that all variables intended to be
1377 dependent must be manifestly so.
1378
1379 Sidenote: It's quite possible that later, we'll consider (t -> s)
1380 as a degenerate case of some (pi (x :: t) -> s) and then this will
1381 all get more permissive.
1382
1383 Note [Kind generalisation and SigTvs]
1384 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1385 Consider
1386 data T (a :: k1) x = MkT (S a ())
1387 data S (b :: k2) y = MkS (T b ())
1388
1389 While we are doing kind inference for the mutually-recursive S,T,
1390 we will end up unifying k1 and k2 together. So they can't be skolems.
1391 We therefore make them SigTvs, which can unify with type variables,
1392 but not with general types. All this is very similar at the level
1393 of terms: see Note [Quantified variables in partial type signatures]
1394 in TcBinds.
1395
1396 There are some wrinkles
1397
1398 * We always want to kind-generalise over SigTvs, and /not/ default
1399 them to Type. Another way to say this is: a SigTV should /never/
1400 stand for a type, even via defaulting. Hence the check in
1401 TcSimplify.defaultTyVarTcS, and TcMType.defaultTyVar. Here's
1402 another example (Trac #14555):
1403 data Exp :: [TYPE rep] -> TYPE rep -> Type where
1404 Lam :: Exp (a:xs) b -> Exp xs (a -> b)
1405 We want to kind-generalise over the 'rep' variable.
1406 Trac #14563 is another example.
1407
1408 * Consider Trac #11203
1409 data SameKind :: k -> k -> *
1410 data Q (a :: k1) (b :: k2) c = MkQ (SameKind a b)
1411 Here we will unify k1 with k2, but this time doing so is an error,
1412 because k1 and k2 are bound in the same delcaration.
1413
1414 We sort this out using findDupSigTvs, in TcTyClTyVars; very much
1415 as we do with partial type signatures in mk_psig_qtvs in
1416 TcBinds.chooseInferredQuantifiers
1417 -}
1418
1419 tcWildCardBinders :: [Name]
1420 -> ([(Name, TcTyVar)] -> TcM a)
1421 -> TcM a
1422 tcWildCardBinders = tcWildCardBindersX new_tv
1423 where
1424 new_tv name = do { kind <- newMetaKindVar
1425 ; newSkolemTyVar name kind }
1426
1427 tcWildCardBindersX :: (Name -> TcM TcTyVar)
1428 -> [Name]
1429 -> ([(Name, TcTyVar)] -> TcM a)
1430 -> TcM a
1431 tcWildCardBindersX new_wc wc_names thing_inside
1432 = do { wcs <- mapM new_wc wc_names
1433 ; let wc_prs = wc_names `zip` wcs
1434 ; tcExtendTyVarEnv2 wc_prs $
1435 thing_inside wc_prs }
1436
1437 -- | Kind-check a 'LHsQTyVars'. If the decl under consideration has a complete,
1438 -- user-supplied kind signature (CUSK), generalise the result.
1439 -- Used in 'getInitialKind' (for tycon kinds and other kinds)
1440 -- and in kind-checking (but not for tycon kinds, which are checked with
1441 -- tcTyClDecls). See also Note [Complete user-supplied kind signatures] in
1442 -- HsDecls.
1443 --
1444 -- This function does not do telescope checking.
1445 kcLHsQTyVars :: Name -- ^ of the thing being checked
1446 -> TyConFlavour -- ^ What sort of 'TyCon' is being checked
1447 -> Bool -- ^ True <=> the decl being checked has a CUSK
1448 -> Bool -- ^ True <=> all the hsq_implicit are *kind* vars
1449 -- (will give these kind * if -XNoTypeInType)
1450 -> LHsQTyVars GhcRn
1451 -> TcM (Kind, r) -- ^ The result kind, possibly with other info
1452 -> TcM (TcTyCon, r) -- ^ A suitably-kinded TcTyCon
1453 kcLHsQTyVars name flav cusk all_kind_vars
1454 (HsQTvs { hsq_implicit = kv_ns, hsq_explicit = hs_tvs
1455 , hsq_dependent = dep_names }) thing_inside
1456 | cusk
1457 = do { kv_kinds <- mk_kv_kinds
1458 ; lvl <- getTcLevel
1459 ; let scoped_kvs = zipWith (mk_skolem_tv lvl) kv_ns kv_kinds
1460 ; tcExtendTyVarEnv scoped_kvs $
1461 do { (tc_tvs, (res_kind, stuff))
1462 <- solveEqualities $
1463 kcLHsTyVarBndrs open_fam hs_tvs thing_inside
1464
1465 -- Now, because we're in a CUSK, quantify over the mentioned
1466 -- kind vars, in dependency order.
1467 ; tc_tvs <- mapM zonkTcTyVarToTyVar tc_tvs
1468 ; res_kind <- zonkTcType res_kind
1469 ; let tc_binders = zipWith mk_tc_binder hs_tvs tc_tvs
1470 qkvs = tyCoVarsOfTypeWellScoped (mkTyConKind tc_binders res_kind)
1471 -- the visibility of tvs doesn't matter here; we just
1472 -- want the free variables not to include the tvs
1473
1474 -- If there are any meta-tvs left, the user has
1475 -- lied about having a CUSK. Error.
1476 ; let (meta_tvs, good_tvs) = partition isMetaTyVar qkvs
1477 ; when (not (null meta_tvs)) $
1478 report_non_cusk_tvs (qkvs ++ tc_tvs)
1479
1480 -- If any of the scoped_kvs aren't actually mentioned in a binder's
1481 -- kind (or the return kind), then we're in the CUSK case from
1482 -- Note [Free-floating kind vars]
1483 ; let all_tc_tvs = good_tvs ++ tc_tvs
1484 all_mentioned_tvs = mapUnionVarSet (tyCoVarsOfType . tyVarKind)
1485 all_tc_tvs
1486 `unionVarSet` tyCoVarsOfType res_kind
1487 unmentioned_kvs = filterOut (`elemVarSet` all_mentioned_tvs)
1488 scoped_kvs
1489 ; reportFloatingKvs name flav all_tc_tvs unmentioned_kvs
1490
1491 ; let final_binders = map (mkNamedTyConBinder Specified) good_tvs
1492 ++ tc_binders
1493 tycon = mkTcTyCon name final_binders res_kind
1494 (mkTyVarNamePairs (scoped_kvs ++ tc_tvs))
1495 flav
1496 -- the tvs contain the binders already
1497 -- in scope from an enclosing class, but
1498 -- re-adding tvs to the env't doesn't cause
1499 -- harm
1500
1501 ; traceTc "kcLHsQTyVars: cusk" $
1502 vcat [ ppr name, ppr kv_ns, ppr hs_tvs, ppr dep_names
1503 , ppr tc_tvs, ppr (mkTyConKind final_binders res_kind)
1504 , ppr qkvs, ppr meta_tvs, ppr good_tvs, ppr final_binders ]
1505
1506 ; return (tycon, stuff) }}
1507
1508 | otherwise
1509 = do { kv_kinds <- mk_kv_kinds
1510 ; scoped_kvs <- zipWithM newSigTyVar kv_ns kv_kinds
1511 -- Why newSigTyVar? See Note [Kind generalisation and sigTvs]
1512 ; (tc_tvs, (res_kind, stuff))
1513 <- tcExtendTyVarEnv2 (kv_ns `zip` scoped_kvs) $
1514 kcLHsTyVarBndrs open_fam hs_tvs thing_inside
1515 ; let -- NB: Don't add scoped_kvs to tyConTyVars, because they
1516 -- must remain lined up with the binders
1517 tc_binders = zipWith mk_tc_binder hs_tvs tc_tvs
1518 tycon = mkTcTyCon name tc_binders res_kind
1519 (mkTyVarNamePairs (scoped_kvs ++ tc_tvs))
1520 flav
1521
1522 ; traceTc "kcLHsQTyVars: not-cusk" $
1523 vcat [ ppr name, ppr kv_ns, ppr hs_tvs, ppr dep_names
1524 , ppr tc_tvs, ppr (mkTyConKind tc_binders res_kind) ]
1525 ; return (tycon, stuff) }
1526 where
1527 open_fam = tcFlavourIsOpen flav
1528
1529 mk_tc_binder :: LHsTyVarBndr GhcRn -> TyVar -> TyConBinder
1530 -- See Note [Dependent LHsQTyVars]
1531 mk_tc_binder hs_tv tv
1532 | hsLTyVarName hs_tv `elemNameSet` dep_names
1533 = mkNamedTyConBinder Required tv
1534 | otherwise
1535 = mkAnonTyConBinder tv
1536
1537
1538 -- if -XNoTypeInType and we know all the implicits are kind vars,
1539 -- just give the kind *. This prevents test
1540 -- dependent/should_fail/KindLevelsB from compiling, as it should
1541 mk_kv_kinds :: TcM [Kind]
1542 mk_kv_kinds = do { typeintype <- xoptM LangExt.TypeInType
1543 ; if not typeintype && all_kind_vars
1544 then return (map (const liftedTypeKind) kv_ns)
1545 else mapM (const newMetaKindVar) kv_ns }
1546
1547 report_non_cusk_tvs all_tvs
1548 = do { all_tvs <- mapM zonkTyCoVarKind all_tvs
1549 ; let (_, tidy_tvs) = tidyOpenTyCoVars emptyTidyEnv all_tvs
1550 (meta_tvs, other_tvs) = partition isMetaTyVar tidy_tvs
1551
1552 ; addErr $
1553 vcat [ text "You have written a *complete user-suppled kind signature*,"
1554 , hang (text "but the following variable" <> plural meta_tvs <+>
1555 isOrAre meta_tvs <+> text "undetermined:")
1556 2 (vcat (map pp_tv meta_tvs))
1557 , text "Perhaps add a kind signature."
1558 , hang (text "Inferred kinds of user-written variables:")
1559 2 (vcat (map pp_tv other_tvs)) ] }
1560 where
1561 pp_tv tv = ppr tv <+> dcolon <+> ppr (tyVarKind tv)
1562
1563
1564 kcLHsTyVarBndrs :: Bool -- True <=> Default un-annotated tyvar
1565 -- binders to kind *
1566 -> [LHsTyVarBndr GhcRn]
1567 -> TcM r
1568 -> TcM ([TyVar], r)
1569 -- There may be dependency between the explicit "ty" vars.
1570 -- So, we have to handle them one at a time.
1571 kcLHsTyVarBndrs _ [] thing
1572 = do { stuff <- thing; return ([], stuff) }
1573
1574 kcLHsTyVarBndrs open_fam (L _ hs_tv : hs_tvs) thing
1575 = do { tv_pair@(tv, _) <- kc_hs_tv hs_tv
1576 -- NB: Bring all tvs into scope, even non-dependent ones,
1577 -- as they're needed in type synonyms, data constructors, etc.
1578
1579 ; (tvs, stuff) <- bind_unless_scoped tv_pair $
1580 kcLHsTyVarBndrs open_fam hs_tvs $
1581 thing
1582
1583 ; return ( tv : tvs, stuff ) }
1584 where
1585
1586 -- | Bind the tyvar in the env't unless the bool is True
1587 bind_unless_scoped :: (TcTyVar, Bool) -> TcM a -> TcM a
1588 bind_unless_scoped (_, True) thing_inside = thing_inside
1589 bind_unless_scoped (tv, False) thing_inside
1590 = tcExtendTyVarEnv [tv] thing_inside
1591
1592 kc_hs_tv :: HsTyVarBndr GhcRn -> TcM (TcTyVar, Bool)
1593 kc_hs_tv (UserTyVar lname@(L _ name))
1594 = do { tv_pair@(tv, in_scope) <- tcHsTyVarName Nothing name
1595
1596 -- Open type/data families default their variables to kind *.
1597 -- But don't default in-scope class tyvars, of course
1598 ; when (open_fam && not in_scope) $
1599 discardResult $ unifyKind (Just (HsTyVar NotPromoted lname)) liftedTypeKind
1600 (tyVarKind tv)
1601
1602 ; return tv_pair }
1603
1604 kc_hs_tv (KindedTyVar (L _ name) lhs_kind)
1605 = do { kind <- tcLHsKindSig lhs_kind
1606 ; tcHsTyVarName (Just kind) name }
1607
1608
1609 tcImplicitTKBndrs :: [Name]
1610 -> TcM (a, TyVarSet) -- vars are bound somewhere in the scope
1611 -- see Note [Scope-check inferred kinds]
1612 -> TcM ([TcTyVar], a)
1613 tcImplicitTKBndrs = tcImplicitTKBndrsX (tcHsTyVarName Nothing)
1614
1615 -- | Convenient specialization
1616 tcImplicitTKBndrsType :: [Name]
1617 -> TcM Type
1618 -> TcM ([TcTyVar], Type)
1619 tcImplicitTKBndrsType var_ns thing_inside
1620 = tcImplicitTKBndrs var_ns $
1621 do { res_ty <- thing_inside
1622 ; return (res_ty, allBoundVariables res_ty) }
1623
1624 -- this more general variant is needed in tcHsPatSigType.
1625 -- See Note [Pattern signature binders]
1626 tcImplicitTKBndrsX :: (Name -> TcM (TcTyVar, Bool)) -- new_tv function
1627 -> [Name]
1628 -> TcM (a, TyVarSet)
1629 -> TcM ([TcTyVar], a)
1630 -- Returned TcTyVars have the supplied Names,
1631 -- but may be in different order to the original [Name]
1632 -- (because of sorting to respect dependency)
1633 -- Returned TcTyVars have zonked kinds
1634 tcImplicitTKBndrsX new_tv var_ns thing_inside
1635 = do { tkvs_pairs <- mapM new_tv var_ns
1636 ; let must_scope_tkvs = [ tkv | (tkv, False) <- tkvs_pairs ]
1637 tkvs = map fst tkvs_pairs
1638 ; (result, bound_tvs) <- tcExtendTyVarEnv must_scope_tkvs $
1639 thing_inside
1640
1641 -- Check that the implicitly-bound kind variable
1642 -- really can go at the beginning.
1643 -- e.g. forall (a :: k) (b :: *). ...(forces k :: b)...
1644 ; tkvs <- mapM zonkTyCoVarKind tkvs
1645 -- NB: /not/ zonkTcTyVarToTyVar. tcImplicitTKBndrsX
1646 -- guarantees to return TcTyVars with the same Names
1647 -- as the var_ns. See [Pattern signature binders]
1648
1649 ; let extra = text "NB: Implicitly-bound variables always come" <+>
1650 text "before other ones."
1651 ; checkValidInferredKinds tkvs bound_tvs extra
1652
1653 ; let final_tvs = toposortTyVars tkvs
1654 ; traceTc "tcImplicitTKBndrs" (ppr var_ns $$ ppr final_tvs)
1655
1656 ; return (final_tvs, result) }
1657
1658 tcExplicitTKBndrs :: [LHsTyVarBndr GhcRn]
1659 -> ([TyVar] -> TcM (a, TyVarSet))
1660 -- ^ Thing inside returns the set of variables bound
1661 -- in the scope. See Note [Scope-check inferred kinds]
1662 -> TcM (a, TyVarSet) -- ^ returns augmented bound vars
1663 -- No cloning: returned TyVars have the same Name as the incoming LHsTyVarBndrs
1664 tcExplicitTKBndrs orig_hs_tvs thing_inside
1665 = tcExplicitTKBndrsX newSkolemTyVar orig_hs_tvs thing_inside
1666
1667 tcExplicitTKBndrsX :: (Name -> Kind -> TcM TyVar)
1668 -> [LHsTyVarBndr GhcRn]
1669 -> ([TyVar] -> TcM (a, TyVarSet))
1670 -- ^ Thing inside returns the set of variables bound
1671 -- in the scope. See Note [Scope-check inferred kinds]
1672 -> TcM (a, TyVarSet) -- ^ returns augmented bound vars
1673 tcExplicitTKBndrsX new_tv orig_hs_tvs thing_inside
1674 = go orig_hs_tvs $ \ tvs ->
1675 do { (result, bound_tvs) <- thing_inside tvs
1676
1677 -- Issue an error if the ordering is bogus.
1678 -- See Note [Bad telescopes] in TcValidity.
1679 ; tvs <- checkZonkValidTelescope (interppSP orig_hs_tvs) tvs empty
1680 ; checkValidInferredKinds tvs bound_tvs empty
1681
1682 ; traceTc "tcExplicitTKBndrs" $
1683 vcat [ text "Hs vars:" <+> ppr orig_hs_tvs
1684 , text "tvs:" <+> sep (map pprTyVar tvs) ]
1685
1686 ; return (result, bound_tvs `unionVarSet` mkVarSet tvs)
1687 }
1688 where
1689 go [] thing = thing []
1690 go (L _ hs_tv : hs_tvs) thing
1691 = do { tv <- tcHsTyVarBndr new_tv hs_tv
1692 ; tcExtendTyVarEnv [tv] $
1693 go hs_tvs $ \ tvs ->
1694 thing (tv : tvs) }
1695
1696 tcHsTyVarBndr :: (Name -> Kind -> TcM TyVar)
1697 -> HsTyVarBndr GhcRn -> TcM TcTyVar
1698 -- Return a SkolemTv TcTyVar, initialised with a kind variable.
1699 -- Typically the Kind inside the HsTyVarBndr will be a tyvar
1700 -- with a mutable kind in it.
1701 -- NB: These variables must not be in scope. This function
1702 -- is not appropriate for use with associated types, for example.
1703 --
1704 -- Returned TcTyVar has the same name; no cloning
1705 --
1706 -- See also Note [Associated type tyvar names] in Class
1707 --
1708 tcHsTyVarBndr new_tv (UserTyVar (L _ name))
1709 = do { kind <- newMetaKindVar
1710 ; new_tv name kind }
1711
1712 tcHsTyVarBndr new_tv (KindedTyVar (L _ name) kind)
1713 = do { kind <- tcLHsKindSig kind
1714 ; new_tv name kind }
1715
1716 newWildTyVar :: Name -> TcM TcTyVar
1717 -- ^ New unification variable for a wildcard
1718 newWildTyVar _name
1719 = do { kind <- newMetaKindVar
1720 ; uniq <- newUnique
1721 ; details <- newMetaDetails TauTv
1722 ; let name = mkSysTvName uniq (fsLit "w")
1723 ; return (mkTcTyVar name kind details) }
1724
1725 -- | Produce a tyvar of the given name (with the kind provided, or
1726 -- otherwise a meta-var kind). If
1727 -- the name is already in scope, return the scoped variable, checking
1728 -- to make sure the known kind matches any kind provided. The
1729 -- second return value says whether the variable is in scope (True)
1730 -- or not (False). (Use this for associated types, for example.)
1731 tcHsTyVarName :: Maybe Kind -> Name -> TcM (TcTyVar, Bool)
1732 tcHsTyVarName m_kind name
1733 = do { mb_tv <- tcLookupLcl_maybe name
1734 ; case mb_tv of
1735 Just (ATyVar _ tv)
1736 -> do { whenIsJust m_kind $ \ kind ->
1737 discardResult $
1738 unifyKind (Just (HsTyVar NotPromoted (noLoc name))) kind (tyVarKind tv)
1739 ; return (tv, True) }
1740 _ -> do { kind <- case m_kind of
1741 Just kind -> return kind
1742 Nothing -> newMetaKindVar
1743 ; tv <- newSkolemTyVar name kind
1744 ; return (tv, False) }}
1745
1746 -- makes a new skolem tv
1747 newSkolemTyVar :: Name -> Kind -> TcM TcTyVar
1748 newSkolemTyVar name kind = do { lvl <- getTcLevel
1749 ; return (mk_skolem_tv lvl name kind) }
1750
1751 mk_skolem_tv :: TcLevel -> Name -> Kind -> TcTyVar
1752 mk_skolem_tv lvl n k = mkTcTyVar n k (SkolemTv lvl False)
1753
1754 ------------------
1755 kindGeneralizeType :: Type -> TcM Type
1756 -- Result is zonked
1757 kindGeneralizeType ty
1758 = do { kvs <- kindGeneralize ty
1759 ; ty <- zonkSigType (mkInvForAllTys kvs ty)
1760 ; return ty }
1761
1762 kindGeneralize :: TcType -> TcM [KindVar]
1763 -- Quantify the free kind variables of a kind or type
1764 -- In the latter case the type is closed, so it has no free
1765 -- type variables. So in both cases, all the free vars are kind vars
1766 kindGeneralize kind_or_type
1767 = do { kvs <- zonkTcTypeAndFV kind_or_type
1768 ; let dvs = DV { dv_kvs = kvs, dv_tvs = emptyDVarSet }
1769 ; gbl_tvs <- tcGetGlobalTyCoVars -- Already zonked
1770 ; quantifyTyVars gbl_tvs dvs }
1771
1772 {-
1773 Note [Kind generalisation]
1774 ~~~~~~~~~~~~~~~~~~~~~~~~~~
1775 We do kind generalisation only at the outer level of a type signature.
1776 For example, consider
1777 T :: forall k. k -> *
1778 f :: (forall a. T a -> Int) -> Int
1779 When kind-checking f's type signature we generalise the kind at
1780 the outermost level, thus:
1781 f1 :: forall k. (forall (a:k). T k a -> Int) -> Int -- YES!
1782 and *not* at the inner forall:
1783 f2 :: (forall k. forall (a:k). T k a -> Int) -> Int -- NO!
1784 Reason: same as for HM inference on value level declarations,
1785 we want to infer the most general type. The f2 type signature
1786 would be *less applicable* than f1, because it requires a more
1787 polymorphic argument.
1788
1789 NB: There are no explicit kind variables written in f's signature.
1790 When there are, the renamer adds these kind variables to the list of
1791 variables bound by the forall, so you can indeed have a type that's
1792 higher-rank in its kind. But only by explicit request.
1793
1794 Note [Kinds of quantified type variables]
1795 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1796 tcTyVarBndrsGen quantifies over a specified list of type variables,
1797 *and* over the kind variables mentioned in the kinds of those tyvars.
1798
1799 Note that we must zonk those kinds (obviously) but less obviously, we
1800 must return type variables whose kinds are zonked too. Example
1801 (a :: k7) where k7 := k9 -> k9
1802 We must return
1803 [k9, a:k9->k9]
1804 and NOT
1805 [k9, a:k7]
1806 Reason: we're going to turn this into a for-all type,
1807 forall k9. forall (a:k7). blah
1808 which the type checker will then instantiate, and instantiate does not
1809 look through unification variables!
1810
1811 Hence using zonked_kinds when forming tvs'.
1812
1813 Note [Free-floating kind vars]
1814 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1815 Consider
1816
1817 data T = MkT (forall (a :: k). Proxy a)
1818 -- from test ghci/scripts/T7873
1819
1820 This is not an existential datatype, but a higher-rank one (the forall
1821 to the right of MkT). Also consider
1822
1823 data S a = MkS (Proxy (a :: k))
1824
1825 According to the rules around implicitly-bound kind variables, in both
1826 cases those k's scope over the whole declaration. The renamer grabs
1827 it and adds it to the hsq_implicits field of the HsQTyVars of the
1828 tycon. So it must be in scope during type-checking, but we want to
1829 reject T while accepting S.
1830
1831 Why reject T? Because the kind variable isn't fixed by anything. For
1832 a variable like k to be implicit, it needs to be mentioned in the kind
1833 of a tycon tyvar. But it isn't.
1834
1835 Why accept S? Because kind inference tells us that a has kind k, so it's
1836 all OK.
1837
1838 Our approach depends on whether or not the datatype has a CUSK.
1839
1840 Non-CUSK: In the first pass (kcTyClTyVars) we just bring
1841 k into scope. In the second pass (tcTyClTyVars),
1842 we check to make sure that k has been unified with some other variable
1843 (or generalized over, making k into a skolem). If it hasn't been, then
1844 it must be a free-floating kind var. Error.
1845
1846 CUSK: When we determine the tycon's final, never-to-be-changed kind
1847 in kcLHsQTyVars, we check to make sure all implicitly-bound kind
1848 vars are indeed mentioned in a kind somewhere. If not, error.
1849
1850 We also perform free-floating kind var analysis for type family instances
1851 (see #13985). Here is an interesting example:
1852
1853 type family T :: k
1854 type instance T = (Nothing :: Maybe a)
1855
1856 Upon a cursory glance, it may appear that the kind variable `a` is
1857 free-floating above, since there are no (visible) LHS patterns in `T`. However,
1858 there is an *invisible* pattern due to the return kind, so inside of GHC, the
1859 instance looks closer to this:
1860
1861 type family T @k :: k
1862 type instance T @(Maybe a) = (Nothing :: Maybe a)
1863
1864 Here, we can see that `a` really is bound by a LHS type pattern, so `a` is in
1865 fact not free-floating. Contrast that with this example:
1866
1867 type instance T = Proxy (Nothing :: Maybe a)
1868
1869 This would looks like this inside of GHC:
1870
1871 type instance T @(*) = Proxy (Nothing :: Maybe a)
1872
1873 So this time, `a` is neither bound by a visible nor invisible type pattern on
1874 the LHS, so it would be reported as free-floating.
1875
1876 Finally, here's one more brain-teaser (from #9574). In the example below:
1877
1878 class Funct f where
1879 type Codomain f :: *
1880 instance Funct ('KProxy :: KProxy o) where
1881 type Codomain 'KProxy = NatTr (Proxy :: o -> *)
1882
1883 As it turns out, `o` is not free-floating in this example. That is because `o`
1884 bound by the kind signature of the LHS type pattern 'KProxy. To make this more
1885 obvious, one can also write the instance like so:
1886
1887 instance Funct ('KProxy :: KProxy o) where
1888 type Codomain ('KProxy :: KProxy o) = NatTr (Proxy :: o -> *)
1889
1890 -}
1891
1892 --------------------
1893 -- getInitialKind has made a suitably-shaped kind for the type or class
1894 -- Look it up in the local environment. This is used only for tycons
1895 -- that we're currently type-checking, so we're sure to find a TcTyCon.
1896 kcLookupTcTyCon :: Name -> TcM TcTyCon
1897 kcLookupTcTyCon nm
1898 = do { tc_ty_thing <- tcLookup nm
1899 ; return $ case tc_ty_thing of
1900 ATcTyCon tc -> tc
1901 _ -> pprPanic "kcLookupTcTyCon" (ppr tc_ty_thing) }
1902
1903 -----------------------
1904 -- | Bring tycon tyvars into scope. This is used during the "kind-checking"
1905 -- pass in TcTyClsDecls. (Never in getInitialKind, never in the
1906 -- "type-checking"/desugaring pass.)
1907 -- Never emits constraints, though the thing_inside might.
1908 kcTyClTyVars :: Name -> TcM a -> TcM a
1909 kcTyClTyVars tycon_name thing_inside
1910 = do { tycon <- kcLookupTcTyCon tycon_name
1911 ; tcExtendTyVarEnv2 (tcTyConScopedTyVars tycon) $ thing_inside }
1912
1913 tcTyClTyVars :: Name
1914 -> ([TyConBinder] -> Kind -> TcM a) -> TcM a
1915 -- ^ Used for the type variables of a type or class decl
1916 -- on the second full pass (type-checking/desugaring) in TcTyClDecls.
1917 -- This is *not* used in the initial-kind run, nor in the "kind-checking" pass.
1918 -- Accordingly, everything passed to the continuation is fully zonked.
1919 --
1920 -- (tcTyClTyVars T [a,b] thing_inside)
1921 -- where T : forall k1 k2 (a:k1 -> *) (b:k1). k2 -> *
1922 -- calls thing_inside with arguments
1923 -- [k1,k2,a,b] [k1:*, k2:*, Anon (k1 -> *), Anon k1] (k2 -> *)
1924 -- having also extended the type environment with bindings
1925 -- for k1,k2,a,b
1926 --
1927 -- Never emits constraints.
1928 --
1929 -- The LHsTyVarBndrs is always user-written, and the full, generalised
1930 -- kind of the tycon is available in the local env.
1931 tcTyClTyVars tycon_name thing_inside
1932 = do { tycon <- kcLookupTcTyCon tycon_name
1933
1934 -- Do checks on scoped tyvars
1935 -- See Note [Free-floating kind vars]
1936 ; let scoped_prs = tcTyConScopedTyVars tycon
1937 scoped_tvs = map snd scoped_prs
1938 still_sig_tvs = filter isSigTyVar scoped_tvs
1939
1940 ; mapM_ report_sig_tv_err (findDupSigTvs scoped_prs)
1941
1942 ; checkNoErrs $ reportFloatingKvs tycon_name (tyConFlavour tycon)
1943 scoped_tvs still_sig_tvs
1944
1945 ; let res_kind = tyConResKind tycon
1946 binders = correct_binders (tyConBinders tycon) res_kind
1947 ; traceTc "tcTyClTyVars" (ppr tycon_name <+> ppr binders)
1948
1949 ; tcExtendTyVarEnv2 scoped_prs $
1950 thing_inside binders res_kind }
1951 where
1952 report_sig_tv_err (n1, n2)
1953 = setSrcSpan (getSrcSpan n2) $
1954 addErrTc (text "Couldn't match" <+> quotes (ppr n1)
1955 <+> text "with" <+> quotes (ppr n2))
1956
1957 -- Given some TyConBinders and a TyCon's result kind, make sure that the
1958 -- correct any wrong Named/Anon choices. For example, consider
1959 -- type Syn k = forall (a :: k). Proxy a
1960 -- At first, it looks like k should be named -- after all, it appears on the RHS.
1961 -- However, the correct kind for Syn is (* -> *).
1962 -- (Why? Because k is the kind of a type, so k's kind is *. And the RHS also has
1963 -- kind *.) See also #13963.
1964 correct_binders :: [TyConBinder] -> Kind -> [TyConBinder]
1965 correct_binders binders kind
1966 = binders'
1967 where
1968 (_, binders') = mapAccumR go (tyCoVarsOfType kind) binders
1969
1970 go :: TyCoVarSet -> TyConBinder -> (TyCoVarSet, TyConBinder)
1971 go fvs binder
1972 | isNamedTyConBinder binder
1973 , not (tv `elemVarSet` fvs)
1974 = (new_fvs, mkAnonTyConBinder tv)
1975
1976 | not (isNamedTyConBinder binder)
1977 , tv `elemVarSet` fvs
1978 = (new_fvs, mkNamedTyConBinder Required tv)
1979 -- always Required, because it was anonymous (i.e. visible) previously
1980
1981 | otherwise
1982 = (new_fvs, binder)
1983
1984 where
1985 tv = binderVar binder
1986 new_fvs = fvs `delVarSet` tv `unionVarSet` tyCoVarsOfType (tyVarKind tv)
1987
1988
1989
1990 -----------------------------------
1991 data DataKindCheck
1992 -- Plain old data type; better be lifted
1993 = LiftedDataKind
1994 -- Data families might have a variable return kind.
1995 -- See See Note [Arity of data families] in FamInstEnv for more info.
1996 | LiftedOrVarDataKind
1997 -- Abstract data in hsig files can have any kind at all;
1998 -- even unlifted. This is because they might not actually
1999 -- be implemented with a data declaration at the end of the day.
2000 | AnyDataKind
2001
2002 tcDataKindSig :: DataKindCheck -- ^ Do we require the result to be *?
2003 -> Kind -> TcM ([TyConBinder], Kind)
2004 -- GADT decls can have a (perhaps partial) kind signature
2005 -- e.g. data T :: * -> * -> * where ...
2006 -- This function makes up suitable (kinded) type variables for
2007 -- the argument kinds, and checks that the result kind is indeed * if requested.
2008 -- (Otherwise, checks to make sure that the result kind is either * or a type variable.)
2009 -- See Note [Arity of data families] in FamInstEnv for more info.
2010 -- We use it also to make up argument type variables for for data instances.
2011 -- Never emits constraints.
2012 -- Returns the new TyVars, the extracted TyBinders, and the new, reduced
2013 -- result kind (which should always be Type or a synonym thereof)
2014 tcDataKindSig kind_check kind
2015 = do { case kind_check of
2016 LiftedDataKind ->
2017 checkTc (isLiftedTypeKind res_kind)
2018 (badKindSig True kind)
2019 LiftedOrVarDataKind ->
2020 checkTc (isLiftedTypeKind res_kind || isJust (tcGetCastedTyVar_maybe res_kind))
2021 (badKindSig False kind)
2022 AnyDataKind -> return ()
2023 ; span <- getSrcSpanM
2024 ; us <- newUniqueSupply
2025 ; rdr_env <- getLocalRdrEnv
2026 ; let uniqs = uniqsFromSupply us
2027 occs = [ occ | str <- allNameStrings
2028 , let occ = mkOccName tvName str
2029 , isNothing (lookupLocalRdrOcc rdr_env occ) ]
2030 -- Note [Avoid name clashes for associated data types]
2031
2032 -- NB: Use the tv from a binder if there is one. Otherwise,
2033 -- we end up inventing a new Unique for it, and any other tv
2034 -- that mentions the first ends up with the wrong kind.
2035 extra_bndrs = zipWith4 mkTyBinderTyConBinder
2036 tv_bndrs (repeat span) uniqs occs
2037
2038 ; return (extra_bndrs, res_kind) }
2039 where
2040 (tv_bndrs, res_kind) = splitPiTys kind
2041
2042 badKindSig :: Bool -> Kind -> SDoc
2043 badKindSig check_for_type kind
2044 = hang (sep [ text "Kind signature on data type declaration has non-*"
2045 , (if check_for_type then empty else text "and non-variable") <+>
2046 text "return kind" ])
2047 2 (ppr kind)
2048
2049 {-
2050 Note [Avoid name clashes for associated data types]
2051 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2052 Consider class C a b where
2053 data D b :: * -> *
2054 When typechecking the decl for D, we'll invent an extra type variable
2055 for D, to fill out its kind. Ideally we don't want this type variable
2056 to be 'a', because when pretty printing we'll get
2057 class C a b where
2058 data D b a0
2059 (NB: the tidying happens in the conversion to IfaceSyn, which happens
2060 as part of pretty-printing a TyThing.)
2061
2062 That's why we look in the LocalRdrEnv to see what's in scope. This is
2063 important only to get nice-looking output when doing ":info C" in GHCi.
2064 It isn't essential for correctness.
2065
2066
2067 ************************************************************************
2068 * *
2069 Partial signatures
2070 * *
2071 ************************************************************************
2072
2073 -}
2074
2075 tcHsPartialSigType
2076 :: UserTypeCtxt
2077 -> LHsSigWcType GhcRn -- The type signature
2078 -> TcM ( [(Name, TcTyVar)] -- Wildcards
2079 , Maybe TcTyVar -- Extra-constraints wildcard
2080 , [TcTyVar] -- Implicitly and explicitly bound type variables
2081 , TcThetaType -- Theta part
2082 , TcType ) -- Tau part
2083 tcHsPartialSigType ctxt sig_ty
2084 | HsWC { hswc_wcs = sig_wcs, hswc_body = ib_ty } <- sig_ty
2085 , HsIB { hsib_vars = implicit_hs_tvs, hsib_body = hs_ty } <- ib_ty
2086 , (explicit_hs_tvs, L _ hs_ctxt, hs_tau) <- splitLHsSigmaTy hs_ty
2087 = addSigCtxt ctxt hs_ty $
2088 do { (implicit_tvs, (wcs, wcx, explicit_tvs, theta, tau))
2089 <- tcWildCardBindersX newWildTyVar sig_wcs $ \ wcs ->
2090 tcImplicitTKBndrsX new_implicit_tv implicit_hs_tvs $
2091 tcExplicitTKBndrsX newSigTyVar explicit_hs_tvs $ \ explicit_tvs ->
2092 -- Why newSigTyVar? See TcBinds
2093 -- Note [Quantified variables in partial type signatures]
2094 do { -- Instantiate the type-class context; but if there
2095 -- is an extra-constraints wildcard, just discard it here
2096 (theta, wcx) <- tcPartialContext hs_ctxt
2097
2098 ; tau <- tcHsOpenType hs_tau
2099
2100 ; let bound_tvs = unionVarSets [ allBoundVariables tau
2101 , mkVarSet explicit_tvs
2102 , mkVarSet (map snd wcs) ]
2103
2104 ; return ( (wcs, wcx, explicit_tvs, theta, tau)
2105 , bound_tvs) }
2106
2107 -- Spit out the wildcards (including the extra-constraints one)
2108 -- as "hole" constraints, so that they'll be reported if necessary
2109 -- See Note [Extra-constraint holes in partial type signatures]
2110 ; emitWildCardHoleConstraints wcs
2111
2112 ; explicit_tvs <- mapM zonkTyCoVarKind explicit_tvs
2113 ; let all_tvs = implicit_tvs ++ explicit_tvs
2114 -- The implicit_tvs already have zonked kinds
2115
2116 ; theta <- mapM zonkTcType theta
2117 ; tau <- zonkTcType tau
2118 ; checkValidType ctxt (mkSpecForAllTys all_tvs $ mkPhiTy theta tau)
2119
2120 ; traceTc "tcHsPartialSigType" (ppr all_tvs)
2121 ; return (wcs, wcx, all_tvs, theta, tau) }
2122 where
2123 new_implicit_tv name
2124 = do { kind <- newMetaKindVar
2125 ; tv <- newSigTyVar name kind
2126 -- Why newSigTyVar? See TcBinds
2127 -- Note [Quantified variables in partial type signatures]
2128 ; return (tv, False) }
2129
2130 tcPartialContext :: HsContext GhcRn -> TcM (TcThetaType, Maybe TcTyVar)
2131 tcPartialContext hs_theta
2132 | Just (hs_theta1, hs_ctxt_last) <- snocView hs_theta
2133 , L _ (HsWildCardTy wc) <- ignoreParens hs_ctxt_last
2134 = do { wc_tv <- tcWildCardOcc wc constraintKind
2135 ; theta <- mapM tcLHsPredType hs_theta1
2136 ; return (theta, Just wc_tv) }
2137 | otherwise
2138 = do { theta <- mapM tcLHsPredType hs_theta
2139 ; return (theta, Nothing) }
2140
2141 {- Note [Extra-constraint holes in partial type signatures]
2142 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2143 Consider
2144 f :: (_) => a -> a
2145 f x = ...
2146
2147 * The renamer makes a wildcard name for the "_", and puts it in
2148 the hswc_wcs field.
2149
2150 * Then, in tcHsPartialSigType, we make a new hole TcTyVar, in
2151 tcWildCardBindersX.
2152
2153 * TcBinds.chooseInferredQuantifiers fills in that hole TcTyVar
2154 with the inferred constraints, e.g. (Eq a, Show a)
2155
2156 * TcErrors.mkHoleError finally reports the error.
2157
2158 An annoying difficulty happens if there are more than 62 inferred
2159 constraints. Then we need to fill in the TcTyVar with (say) a 70-tuple.
2160 Where do we find the TyCon? For good reasons we only have constraint
2161 tuples up to 62 (see Note [How tuples work] in TysWiredIn). So how
2162 can we make a 70-tuple? This was the root cause of Trac #14217.
2163
2164 It's incredibly tiresome, because we only need this type to fill
2165 in the hole, to communicate to the error reporting machinery. Nothing
2166 more. So I use a HACK:
2167
2168 * I make an /ordinary/ tuple of the constraints, in
2169 TcBinds.chooseInferredQuantifiers. This is ill-kinded because
2170 ordinary tuples can't contain constraints, but it works fine. And for
2171 ordinary tuples we don't have the same limit as for constraint
2172 tuples (which need selectors and an assocated class).
2173
2174 * Because it is ill-kinded, it trips an assert in writeMetaTyVar,
2175 so now I disable the assertion if we are writing a type of
2176 kind Constraint. (That seldom/never normally happens so we aren't
2177 losing much.)
2178
2179 Result works fine, but it may eventually bite us.
2180
2181
2182 ************************************************************************
2183 * *
2184 Pattern signatures (i.e signatures that occur in patterns)
2185 * *
2186 ********************************************************************* -}
2187
2188 tcHsPatSigType :: UserTypeCtxt
2189 -> LHsSigWcType GhcRn -- The type signature
2190 -> TcM ( [(Name, TcTyVar)] -- Wildcards
2191 , [(Name, TcTyVar)] -- The new bit of type environment, binding
2192 -- the scoped type variables
2193 , TcType) -- The type
2194 -- Used for type-checking type signatures in
2195 -- (a) patterns e.g f (x::Int) = e
2196 -- (b) RULE forall bndrs e.g. forall (x::Int). f x = x
2197 --
2198 -- This may emit constraints
2199
2200 tcHsPatSigType ctxt sig_ty
2201 | HsWC { hswc_wcs = sig_wcs, hswc_body = ib_ty } <- sig_ty
2202 , HsIB { hsib_vars = sig_vars, hsib_body = hs_ty } <- ib_ty
2203 = addSigCtxt ctxt hs_ty $
2204 do { (implicit_tvs, (wcs, sig_ty))
2205 <- tcWildCardBindersX newWildTyVar sig_wcs $ \ wcs ->
2206 tcImplicitTKBndrsX new_implicit_tv sig_vars $
2207 do { sig_ty <- tcHsOpenType hs_ty
2208 ; return ((wcs, sig_ty), allBoundVariables sig_ty) }
2209
2210 ; emitWildCardHoleConstraints wcs
2211
2212 ; sig_ty <- zonkTcType sig_ty
2213 ; checkValidType ctxt sig_ty
2214
2215 ; tv_pairs <- mapM mk_tv_pair implicit_tvs
2216
2217 ; traceTc "tcHsPatSigType" (ppr sig_vars)
2218 ; return (wcs, tv_pairs, sig_ty) }
2219 where
2220 new_implicit_tv name = do { kind <- newMetaKindVar
2221 ; tv <- new_tv name kind
2222 ; return (tv, False) }
2223 -- "False" means that these tyvars aren't yet in scope
2224 new_tv = case ctxt of
2225 RuleSigCtxt {} -> newSkolemTyVar
2226 _ -> newSigTyVar
2227 -- See Note [Pattern signature binders]
2228 -- See Note [Unifying SigTvs]
2229
2230 mk_tv_pair tv = do { tv' <- zonkTcTyVarToTyVar tv
2231 ; return (tyVarName tv, tv') }
2232 -- The Name is one of sig_vars, the lexically scoped name
2233 -- But if it's a SigTyVar, it might have been unified
2234 -- with an existing in-scope skolem, so we must zonk
2235 -- here. See Note [Pattern signature binders]
2236
2237 tcPatSig :: Bool -- True <=> pattern binding
2238 -> LHsSigWcType GhcRn
2239 -> ExpSigmaType
2240 -> TcM (TcType, -- The type to use for "inside" the signature
2241 [(Name,TcTyVar)], -- The new bit of type environment, binding
2242 -- the scoped type variables
2243 [(Name,TcTyVar)], -- The wildcards
2244 HsWrapper) -- Coercion due to unification with actual ty
2245 -- Of shape: res_ty ~ sig_ty
2246 tcPatSig in_pat_bind sig res_ty
2247 = do { (sig_wcs, sig_tvs, sig_ty) <- tcHsPatSigType PatSigCtxt sig
2248 -- sig_tvs are the type variables free in 'sig',
2249 -- and not already in scope. These are the ones
2250 -- that should be brought into scope
2251
2252 ; if null sig_tvs then do {
2253 -- Just do the subsumption check and return
2254 wrap <- addErrCtxtM (mk_msg sig_ty) $
2255 tcSubTypeET PatSigOrigin PatSigCtxt res_ty sig_ty
2256 ; return (sig_ty, [], sig_wcs, wrap)
2257 } else do
2258 -- Type signature binds at least one scoped type variable
2259
2260 -- A pattern binding cannot bind scoped type variables
2261 -- It is more convenient to make the test here
2262 -- than in the renamer
2263 { when in_pat_bind (addErr (patBindSigErr sig_tvs))
2264
2265 -- Check that all newly-in-scope tyvars are in fact
2266 -- constrained by the pattern. This catches tiresome
2267 -- cases like
2268 -- type T a = Int
2269 -- f :: Int -> Int
2270 -- f (x :: T a) = ...
2271 -- Here 'a' doesn't get a binding. Sigh
2272 ; let bad_tvs = [ tv | (_,tv) <- sig_tvs
2273 , not (tv `elemVarSet` exactTyCoVarsOfType sig_ty) ]
2274 ; checkTc (null bad_tvs) (badPatSigTvs sig_ty bad_tvs)
2275
2276 -- Now do a subsumption check of the pattern signature against res_ty
2277 ; wrap <- addErrCtxtM (mk_msg sig_ty) $
2278 tcSubTypeET PatSigOrigin PatSigCtxt res_ty sig_ty
2279
2280 -- Phew!
2281 ; return (sig_ty, sig_tvs, sig_wcs, wrap)
2282 } }
2283 where
2284 mk_msg sig_ty tidy_env
2285 = do { (tidy_env, sig_ty) <- zonkTidyTcType tidy_env sig_ty
2286 ; res_ty <- readExpType res_ty -- should be filled in by now
2287 ; (tidy_env, res_ty) <- zonkTidyTcType tidy_env res_ty
2288 ; let msg = vcat [ hang (text "When checking that the pattern signature:")
2289 4 (ppr sig_ty)
2290 , nest 2 (hang (text "fits the type of its context:")
2291 2 (ppr res_ty)) ]
2292 ; return (tidy_env, msg) }
2293
2294 patBindSigErr :: [(Name,TcTyVar)] -> SDoc
2295 patBindSigErr sig_tvs
2296 = hang (text "You cannot bind scoped type variable" <> plural sig_tvs
2297 <+> pprQuotedList (map fst sig_tvs))
2298 2 (text "in a pattern binding signature")
2299
2300 {- Note [Pattern signature binders]
2301 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2302 Consider
2303 data T = forall a. T a (a->Int)
2304 f (T x (f :: b->Int)) = blah
2305
2306 Here
2307 * The pattern (T p1 p2) creates a *skolem* type variable 'a_sk',
2308 It must be a skolem so that that it retains its identity, and
2309 TcErrors.getSkolemInfo can thereby find the binding site for the skolem.
2310
2311 * The type signature pattern (f :: b->Int) makes a fresh meta-tyvar b_sig
2312 (a SigTv), and binds "b" :-> b_sig in the envt
2313
2314 * Then unification makes b_sig := a_sk
2315 That's why we must make b_sig a MetaTv (albeit a SigTv),
2316 not a SkolemTv, so that it can unify to a_sk.
2317
2318 * Finally, in 'blah' we must have the envt "b" :-> a_sk. The pair
2319 ("b" :-> a_sk) is returned by tcHsPatSigType, constructed by
2320 mk_tv_pair in that function.
2321
2322 Another example (Trac #13881):
2323 fl :: forall (l :: [a]). Sing l -> Sing l
2324 fl (SNil :: Sing (l :: [y])) = SNil
2325 When we reach the pattern signature, 'l' is in scope from the
2326 outer 'forall':
2327 "a" :-> a_sk :: *
2328 "l" :-> l_sk :: [a_sk]
2329 We make up a fresh meta-SigTv, y_sig, for 'y', and kind-check
2330 the pattern signature
2331 Sing (l :: [y])
2332 That unifies y_sig := a_sk. We return from tcHsPatSigType with
2333 the pair ("y" :-> a_sk).
2334
2335 For RULE binders, though, things are a bit different (yuk).
2336 RULE "foo" forall (x::a) (y::[a]). f x y = ...
2337 Here this really is the binding site of the type variable so we'd like
2338 to use a skolem, so that we get a complaint if we unify two of them
2339 together.
2340
2341 Note [Unifying SigTvs]
2342 ~~~~~~~~~~~~~~~~~~~~~~
2343 ALAS we have no decent way of avoiding two SigTvs getting unified.
2344 Consider
2345 f (x::(a,b)) (y::c)) = [fst x, y]
2346 Here we'd really like to complain that 'a' and 'c' are unified. But
2347 for the reasons above we can't make a,b,c into skolems, so they
2348 are just SigTvs that can unify. And indeed, this would be ok,
2349 f x (y::c) = case x of
2350 (x1 :: a1, True) -> [x,y]
2351 (x1 :: a2, False) -> [x,y,y]
2352 Here the type of x's first component is called 'a1' in one branch and
2353 'a2' in the other. We could try insisting on the same OccName, but
2354 they definitely won't have the sane lexical Name.
2355
2356 I think we could solve this by recording in a SigTv a list of all the
2357 in-scope variables that it should not unify with, but it's fiddly.
2358
2359
2360 ************************************************************************
2361 * *
2362 Checking kinds
2363 * *
2364 ************************************************************************
2365
2366 -}
2367
2368 unifyKinds :: [LHsType GhcRn] -> [(TcType, TcKind)] -> TcM ([TcType], TcKind)
2369 unifyKinds rn_tys act_kinds
2370 = do { kind <- newMetaKindVar
2371 ; let check rn_ty (ty, act_kind) = checkExpectedKind (unLoc rn_ty) ty act_kind kind
2372 ; tys' <- zipWithM check rn_tys act_kinds
2373 ; return (tys', kind) }
2374
2375 {-
2376 ************************************************************************
2377 * *
2378 Sort checking kinds
2379 * *
2380 ************************************************************************
2381
2382 tcLHsKindSig converts a user-written kind to an internal, sort-checked kind.
2383 It does sort checking and desugaring at the same time, in one single pass.
2384 -}
2385
2386 tcLHsKindSig :: LHsKind GhcRn -> TcM Kind
2387 tcLHsKindSig hs_kind
2388 = do { kind <- tc_lhs_kind kindLevelMode hs_kind
2389 ; zonkTcType kind }
2390 -- This zonk is very important in the case of higher rank kinds
2391 -- E.g. Trac #13879 f :: forall (p :: forall z (y::z). <blah>).
2392 -- <more blah>
2393 -- When instantiating p's kind at occurrences of p in <more blah>
2394 -- it's crucial that the kind we instantiate is fully zonked,
2395 -- else we may fail to substitute properly
2396
2397 tc_lhs_kind :: TcTyMode -> LHsKind GhcRn -> TcM Kind
2398 tc_lhs_kind mode k
2399 = addErrCtxt (text "In the kind" <+> quotes (ppr k)) $
2400 tc_lhs_type (kindLevel mode) k liftedTypeKind
2401
2402 promotionErr :: Name -> PromotionErr -> TcM a
2403 promotionErr name err
2404 = failWithTc (hang (pprPECategory err <+> quotes (ppr name) <+> text "cannot be used here")
2405 2 (parens reason))
2406 where
2407 reason = case err of
2408 FamDataConPE -> text "it comes from a data family instance"
2409 NoDataKindsTC -> text "Perhaps you intended to use DataKinds"
2410 NoDataKindsDC -> text "Perhaps you intended to use DataKinds"
2411 NoTypeInTypeTC -> text "Perhaps you intended to use TypeInType"
2412 NoTypeInTypeDC -> text "Perhaps you intended to use TypeInType"
2413 PatSynPE -> text "Pattern synonyms cannot be promoted"
2414 _ -> text "it is defined and used in the same recursive group"
2415
2416 {-
2417 ************************************************************************
2418 * *
2419 Scoped type variables
2420 * *
2421 ************************************************************************
2422 -}
2423
2424 badPatSigTvs :: TcType -> [TyVar] -> SDoc
2425 badPatSigTvs sig_ty bad_tvs
2426 = vcat [ fsep [text "The type variable" <> plural bad_tvs,
2427 quotes (pprWithCommas ppr bad_tvs),
2428 text "should be bound by the pattern signature" <+> quotes (ppr sig_ty),
2429 text "but are actually discarded by a type synonym" ]
2430 , text "To fix this, expand the type synonym"
2431 , text "[Note: I hope to lift this restriction in due course]" ]
2432
2433 {-
2434 ************************************************************************
2435 * *
2436 Error messages and such
2437 * *
2438 ************************************************************************
2439 -}
2440
2441 -- | Make an appropriate message for an error in a function argument.
2442 -- Used for both expressions and types.
2443 funAppCtxt :: (Outputable fun, Outputable arg) => fun -> arg -> Int -> SDoc
2444 funAppCtxt fun arg arg_no
2445 = hang (hsep [ text "In the", speakNth arg_no, ptext (sLit "argument of"),
2446 quotes (ppr fun) <> text ", namely"])
2447 2 (quotes (ppr arg))
2448
2449 -- See Note [Free-floating kind vars]
2450 reportFloatingKvs :: Name -- of the tycon
2451 -> TyConFlavour -- What sort of TyCon it is
2452 -> [TcTyVar] -- all tyvars, not necessarily zonked
2453 -> [TcTyVar] -- floating tyvars
2454 -> TcM ()
2455 reportFloatingKvs tycon_name flav all_tvs bad_tvs
2456 = unless (null bad_tvs) $ -- don't bother zonking if there's no error
2457 do { all_tvs <- mapM zonkTcTyVarToTyVar all_tvs
2458 ; bad_tvs <- mapM zonkTcTyVarToTyVar bad_tvs
2459 ; let (tidy_env, tidy_all_tvs) = tidyOpenTyCoVars emptyTidyEnv all_tvs
2460 tidy_bad_tvs = map (tidyTyVarOcc tidy_env) bad_tvs
2461 ; typeintype <- xoptM LangExt.TypeInType
2462 ; mapM_ (report typeintype tidy_all_tvs) tidy_bad_tvs }
2463 where
2464 report typeintype tidy_all_tvs tidy_bad_tv
2465 = addErr $
2466 vcat [ text "Kind variable" <+> quotes (ppr tidy_bad_tv) <+>
2467 text "is implicitly bound in" <+> ppr flav
2468 , quotes (ppr tycon_name) <> comma <+>
2469 text "but does not appear as the kind of any"
2470 , text "of its type variables. Perhaps you meant"
2471 , text "to bind it" <+> ppWhen (not typeintype)
2472 (text "(with TypeInType)") <+>
2473 text "explicitly somewhere?"
2474 , ppWhen (not (null tidy_all_tvs)) $
2475 hang (text "Type variables with inferred kinds:")
2476 2 (ppr_tv_bndrs tidy_all_tvs) ]
2477
2478 ppr_tv_bndrs tvs = sep (map pp_tv tvs)
2479 pp_tv tv = parens (ppr tv <+> dcolon <+> ppr (tyVarKind tv))