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