TcHsType.hs 104 KB
Newer Older
Austin Seipp's avatar
Austin Seipp committed
1
2
3
4
{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998

5
\section[TcMonoType]{Typechecking user-specified @MonoTypes@}
Austin Seipp's avatar
Austin Seipp committed
6
-}
7

Richard Eisenberg's avatar
Richard Eisenberg committed
8
{-# LANGUAGE CPP, TupleSections, MultiWayIf, RankNTypes #-}
Ian Lynagh's avatar
Ian Lynagh committed
9

10
module TcHsType (
11
        -- Type signatures
Alan Zimmerman's avatar
Alan Zimmerman committed
12
        kcHsSigType, tcClassSigType,
13
        tcHsSigType, tcHsSigWcType,
14
15
        tcHsPartialSigType,
        funsSigCtxt, addSigCtxt, pprSigCtxt,
16
17
18

        tcHsClsInstType,
        tcHsDeriv, tcHsVectInst,
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
19
        tcHsTypeApp,
20
        UserTypeCtxt(..),
21
        tcImplicitTKBndrs, tcImplicitTKBndrsType, tcExplicitTKBndrs,
22

23
                -- Type checking type and class decls
24
        kcLookupTcTyCon, kcTyClTyVars, tcTyClTyVars,
25
        tcDataKindSig,
Edward Z. Yang's avatar
Edward Z. Yang committed
26
        DataKindCheck(..),
dreixel's avatar
dreixel committed
27

28
29
        -- Kind-checking types
        -- No kind generalisation, no checkValidType
Simon Peyton Jones's avatar
Simon Peyton Jones committed
30
        kcLHsQTyVars, kcLHsTyVarBndrs,
31
32
33
        tcWildCardBinders,
        tcHsLiftedType,   tcHsOpenType,
        tcHsLiftedTypeNC, tcHsOpenTypeNC,
Richard Eisenberg's avatar
Richard Eisenberg committed
34
        tcLHsType, tcLHsTypeUnsaturated, tcCheckLHsType,
35
        tcHsMbContext, tcHsContext, tcLHsPredType, tcInferApps,
36
        solveEqualities, -- useful re-export
batterseapower's avatar
batterseapower committed
37

38
39
40
        typeLevelMode, kindLevelMode,

        kindGeneralize, checkExpectedKindX, instantiateTyUntilN,
41
42
        reportFloatingKvs,

43
        -- Sort-checking kinds
44
        tcLHsKindSig,
45

46
        -- Pattern type signatures
47
        tcHsPatSigType, tcPatSig, funAppCtxt
48
49
50
51
   ) where

#include "HsVersions.h"

52
53
import GhcPrelude

54
import HsSyn
55
import TcRnMonad
56
import TcEvidence
57
58
import TcEnv
import TcMType
59
import TcValidity
60
61
import TcUnify
import TcIface
Richard Eisenberg's avatar
Richard Eisenberg committed
62
import TcSimplify ( solveEqualities )
63
import TcType
64
import TcHsSyn( zonkSigType )
65
import Inst   ( tcInstBinders, tcInstBinder )
66
import Type
dreixel's avatar
dreixel committed
67
import Kind
68
import RdrName( lookupLocalRdrOcc )
69
import Var
70
import VarSet
71
import TyCon
Gergő Érdi's avatar
Gergő Érdi committed
72
import ConLike
73
import DataCon
74
75
import Class
import Name
76
import NameEnv
77
78
import NameSet
import VarEnv
79
80
81
import TysWiredIn
import BasicTypes
import SrcLoc
82
83
import Constants ( mAX_CTUPLE_SIZE )
import ErrUtils( MsgDoc )
84
import Unique
85
import Util
86
import UniqSupply
87
import Outputable
88
import FastString
89
import PrelNames hiding ( wildCardName )
90
import qualified GHC.LanguageExtensions as LangExt
91

eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
92
import Maybes
Richard Eisenberg's avatar
Richard Eisenberg committed
93
import Data.List ( partition, zipWith4, mapAccumR )
94
import Control.Monad
95

Austin Seipp's avatar
Austin Seipp committed
96
{-
97
98
99
        ----------------------------
                General notes
        ----------------------------
100

101
102
103
104
105
Unlike with expressions, type-checking types both does some checking and
desugars at the same time. This is necessary because we often want to perform
equality checks on the types right away, and it would be incredibly painful
to do this on un-desugared types. Luckily, desugared types are close enough
to HsTypes to make the error messages sane.
106

107
108
109
110
111
112
113
During type-checking, we perform as little validity checking as possible.
This is because some type-checking is done in a mutually-recursive knot, and
if we look too closely at the tycons, we'll loop. This is why we always must
use mkNakedTyConApp and mkNakedAppTys, etc., which never look at a tycon.
The mkNamed... functions don't uphold Type invariants, but zonkTcTypeToType
will repair this for us. Note that zonkTcType *is* safe within a knot, and
can be done repeatedly with no ill effect: it just squeezes out metavariables.
114

115
116
Generally, after type-checking, you will want to do validity checking, say
with TcValidity.checkValidType.
117
118
119

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

- During desugaring, we normalise by expanding type synonyms.  Only
  after this step can we check things like type-synonym saturation
125
126
  e.g.  type T k = k Int
        type S a = a
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
  Then (T S) is ok, because T is saturated; (T S) expands to (S Int);
  and then S is saturated.  This is a GHC extension.

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

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

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

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

147
148
%************************************************************************
%*                                                                      *
149
              Check types AND do validity checking
Austin Seipp's avatar
Austin Seipp committed
150
151
152
*                                                                      *
************************************************************************
-}
153

154
155
156
157
158
159
funsSigCtxt :: [Located Name] -> UserTypeCtxt
-- Returns FunSigCtxt, with no redundant-context-reporting,
-- form a list of located names
funsSigCtxt (L _ name1 : _) = FunSigCtxt name1 False
funsSigCtxt []              = panic "funSigCtxt"

160
addSigCtxt :: UserTypeCtxt -> LHsType GhcRn -> TcM a -> TcM a
161
162
163
addSigCtxt ctxt hs_ty thing_inside
  = setSrcSpan (getLoc hs_ty) $
    addErrCtxt (pprSigCtxt ctxt hs_ty) $
164
165
    thing_inside

166
pprSigCtxt :: UserTypeCtxt -> LHsType GhcRn -> SDoc
167
168
169
170
171
172
173
174
175
176
177
178
179
-- (pprSigCtxt ctxt <extra> <type>)
-- prints    In the type signature for 'f':
--              f :: <type>
-- The <extra> is either empty or "the ambiguity check for"
pprSigCtxt ctxt hs_ty
  | Just n <- isSigMaybe ctxt
  = hang (text "In the type signature:")
       2 (pprPrefixOcc n <+> dcolon <+> ppr hs_ty)

  | otherwise
  = hang (text "In" <+> pprUserTypeCtxt ctxt <> colon)
       2 (ppr hs_ty)

180
tcHsSigWcType :: UserTypeCtxt -> LHsSigWcType GhcRn -> TcM Type
181
182
-- This one is used when we have a LHsSigWcType, but in
-- a place where wildards aren't allowed. The renamer has
Gabor Greif's avatar
Gabor Greif committed
183
-- already checked this, so we can simply ignore it.
184
185
tcHsSigWcType ctxt sig_ty = tcHsSigType ctxt (dropWildCards sig_ty)

186
kcHsSigType :: [Located Name] -> LHsSigType GhcRn -> TcM ()
Alan Zimmerman's avatar
Alan Zimmerman committed
187
kcHsSigType names (HsIB { hsib_body = hs_ty
188
                        , hsib_vars = sig_vars })
189
  = addSigCtxt (funsSigCtxt names) hs_ty $
190
191
192
    discardResult $
    tcImplicitTKBndrsType sig_vars $
    tc_lhs_type typeLevelMode hs_ty liftedTypeKind
193

194
tcClassSigType :: [Located Name] -> LHsSigType GhcRn -> TcM Type
195
196
197
198
-- Does not do validity checking; this must be done outside
-- the recursive class declaration "knot"
tcClassSigType names sig_ty
  = addSigCtxt (funsSigCtxt names) (hsSigType sig_ty) $
Richard Eisenberg's avatar
Richard Eisenberg committed
199
    tc_hs_sig_type_and_gen sig_ty liftedTypeKind
200

201
tcHsSigType :: UserTypeCtxt -> LHsSigType GhcRn -> TcM Type
202
203
204
205
-- Does validity checking
tcHsSigType ctxt sig_ty
  = addSigCtxt ctxt (hsSigType sig_ty) $
    do { kind <- case expectedKindInCtxt ctxt of
206
207
                    AnythingKind -> newMetaKindVar
                    TheKind k    -> return k
208
                    OpenKind     -> newOpenTypeKind
209
210
211
              -- The kind is checked by checkValidType, and isn't necessarily
              -- of kind * in a Template Haskell quote eg [t| Maybe |]

212
          -- Generalise here: see Note [Kind generalisation]
Richard Eisenberg's avatar
Richard Eisenberg committed
213
       ; do_kind_gen <- decideKindGeneralisationPlan sig_ty
214
       ; ty <- if do_kind_gen
Richard Eisenberg's avatar
Richard Eisenberg committed
215
216
               then tc_hs_sig_type_and_gen sig_ty kind
               else tc_hs_sig_type         sig_ty kind >>= zonkTcType
217

218
219
220
       ; checkValidType ctxt ty
       ; return ty }

221
tc_hs_sig_type_and_gen :: LHsSigType GhcRn -> Kind -> TcM Type
222
223
224
-- Kind-checks/desugars an 'LHsSigType',
--   solve equalities,
--   and then kind-generalizes.
Richard Eisenberg's avatar
Richard Eisenberg committed
225
226
-- This will never emit constraints, as it uses solveEqualities interally.
-- No validity checking, but it does zonk en route to generalization
227
228
229
230
231
232
tc_hs_sig_type_and_gen hs_ty kind
  = do { ty <- solveEqualities $
               tc_hs_sig_type hs_ty kind
         -- NB the call to solveEqualities, which unifies all those
         --    kind variables floating about, immediately prior to
         --    kind generalisation
Richard Eisenberg's avatar
Richard Eisenberg committed
233
234
       ; kindGeneralizeType ty }

235
tc_hs_sig_type :: LHsSigType GhcRn -> Kind -> TcM Type
236
237
238
-- Kind-check/desugar a 'LHsSigType', but does not solve
-- the equalities that arise from doing so; instead it may
-- emit kind-equality constraints into the monad
Richard Eisenberg's avatar
Richard Eisenberg committed
239
-- No zonking or validity checking
240
241
242
tc_hs_sig_type (HsIB { hsib_vars = sig_vars
                     , hsib_body = hs_ty }) kind
  = do { (tkvs, ty) <- tcImplicitTKBndrsType sig_vars $
243
                       tc_lhs_type typeLevelMode hs_ty kind
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
244
       ; return (mkSpecForAllTys tkvs ty) }
batterseapower's avatar
batterseapower committed
245

246
-----------------
247
tcHsDeriv :: LHsSigType GhcRn -> TcM ([TyVar], Class, [Type], [Kind])
248
-- Like tcHsSigType, but for the ...deriving( C t1 ty2 ) clause
249
-- Returns the C, [ty1, ty2, and the kinds of C's remaining arguments
250
251
-- E.g.    class C (a::*) (b::k->k)
--         data T a b = ... deriving( C Int )
252
--    returns ([k], C, [k, Int], [k->k])
253
tcHsDeriv hs_ty
254
  = do { cls_kind <- newMetaKindVar
255
256
257
258
                    -- always safe to kind-generalize, because there
                    -- can be no covars in an outer scope
       ; ty <- checkNoErrs $
                 -- avoid redundant error report with "illegal deriving", below
Richard Eisenberg's avatar
Richard Eisenberg committed
259
               tc_hs_sig_type_and_gen hs_ty cls_kind
260
       ; cls_kind <- zonkTcType cls_kind
261
       ; let (tvs, pred) = splitForAllTys ty
262
       ; let (args, _) = splitFunTys cls_kind
263
       ; case getClassPredTys_maybe pred of
264
           Just (cls, tys) -> return (tvs, cls, tys, args)
265
           Nothing -> failWithTc (text "Illegal deriving item" <+> quotes (ppr hs_ty)) }
266

267
tcHsClsInstType :: UserTypeCtxt    -- InstDeclCtxt or SpecInstCtxt
268
                -> LHsSigType GhcRn
269
270
                -> TcM ([TyVar], ThetaType, Class, [Type])
-- Like tcHsSigType, but for a class instance declaration
271
272
tcHsClsInstType user_ctxt hs_inst_ty
  = setSrcSpan (getLoc (hsSigType hs_inst_ty)) $
Richard Eisenberg's avatar
Richard Eisenberg committed
273
    do { inst_ty <- tc_hs_sig_type_and_gen hs_inst_ty constraintKind
274
275
       ; checkValidInstance user_ctxt hs_inst_ty inst_ty }

276
-- Used for 'VECTORISE [SCALAR] instance' declarations
277
tcHsVectInst :: LHsSigType GhcRn -> TcM (Class, [Type])
278
tcHsVectInst ty
279
280
  | let hs_cls_ty = hsSigType ty
  , Just (L _ cls_name, tys) <- hsTyGetAppHead_maybe hs_cls_ty
281
    -- Ignoring the binders looks pretty dodgy to me
282
  = do { (cls, cls_kind) <- tcClass cls_name
283
       ; (applied_class, _res_kind)
284
           <- tcTyApps typeLevelMode hs_cls_ty (mkClassPred cls []) cls_kind tys
285
286
287
288
       ; case tcSplitTyConApp_maybe applied_class of
           Just (_tc, args) -> ASSERT( _tc == classTyCon cls )
                               return (cls, args)
           _ -> failWithTc (text "Too many arguments passed to" <+> ppr cls_name) }
289
  | otherwise
290
  = failWithTc $ text "Malformed instance type"
291

eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
292
293
----------------------------------------------
-- | Type-check a visible type application
294
tcHsTypeApp :: LHsWcType GhcRn -> Kind -> TcM Type
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
295
tcHsTypeApp wc_ty kind
296
  | HsWC { hswc_wcs = sig_wcs, hswc_body = hs_ty } <- wc_ty
Richard Eisenberg's avatar
Richard Eisenberg committed
297
  = do { ty <- tcWildCardBindersX newWildTyVar sig_wcs $ \ _ ->
298
               tcCheckLHsType hs_ty kind
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
299
300
301
302
303
304
305
       ; ty <- zonkTcType ty
       ; checkValidType TypeAppCtxt ty
       ; return ty }
        -- NB: we don't call emitWildcardHoleConstraints here, because
        -- we want any holes in visible type applications to be used
        -- without fuss. No errors, warnings, extensions, etc.

Austin Seipp's avatar
Austin Seipp committed
306
307
308
{-
************************************************************************
*                                                                      *
309
            The main kind checker: no validity checks here
Richard Eisenberg's avatar
Richard Eisenberg committed
310
311
*                                                                      *
************************************************************************
312
313

        First a couple of simple wrappers for kcHsType
Austin Seipp's avatar
Austin Seipp committed
314
-}
315

dreixel's avatar
dreixel committed
316
---------------------------
317
tcHsOpenType, tcHsLiftedType,
318
  tcHsOpenTypeNC, tcHsLiftedTypeNC :: LHsType GhcRn -> TcM TcType
319
320
-- Used for type signatures
-- Do not do validity checking
321
322
323
tcHsOpenType ty   = addTypeCtxt ty $ tcHsOpenTypeNC ty
tcHsLiftedType ty = addTypeCtxt ty $ tcHsLiftedTypeNC ty

324
tcHsOpenTypeNC   ty = do { ek <- newOpenTypeKind
325
326
                         ; tc_lhs_type typeLevelMode ty ek }
tcHsLiftedTypeNC ty = tc_lhs_type typeLevelMode ty liftedTypeKind
327
328

-- Like tcHsType, but takes an expected kind
329
tcCheckLHsType :: LHsType GhcRn -> Kind -> TcM TcType
330
tcCheckLHsType hs_ty exp_kind
331
  = addTypeCtxt hs_ty $
332
    tc_lhs_type typeLevelMode hs_ty exp_kind
333

334
tcLHsType :: LHsType GhcRn -> TcM (TcType, TcKind)
335
-- Called from outside: set the context
336
tcLHsType ty = addTypeCtxt ty (tc_infer_lhs_type typeLevelMode ty)
dreixel's avatar
dreixel committed
337

Richard Eisenberg's avatar
Richard Eisenberg committed
338
339
340
341
342
343
344
-- Like tcLHsType, but use it in a context where type synonyms and type families
-- do not need to be saturated, like in a GHCi :kind call
tcLHsTypeUnsaturated :: LHsType GhcRn -> TcM (TcType, TcKind)
tcLHsTypeUnsaturated ty = addTypeCtxt ty (tc_infer_lhs_type mode ty)
  where
    mode = allowUnsaturated typeLevelMode

345
---------------------------
346
-- | Should we generalise the kind of this type signature?
Richard Eisenberg's avatar
Richard Eisenberg committed
347
-- We *should* generalise if the type is closed
348
-- or if NoMonoLocalBinds is set. Otherwise, nope.
349
-- See Note [Kind generalisation plan]
350
decideKindGeneralisationPlan :: LHsSigType GhcRn -> TcM Bool
Richard Eisenberg's avatar
Richard Eisenberg committed
351
decideKindGeneralisationPlan sig_ty@(HsIB { hsib_closed = closed })
352
  = do { mono_locals <- xoptM LangExt.MonoLocalBinds
Richard Eisenberg's avatar
Richard Eisenberg committed
353
       ; let should_gen = not mono_locals || closed
354
       ; traceTc "decideKindGeneralisationPlan"
Richard Eisenberg's avatar
Richard Eisenberg committed
355
           (ppr sig_ty $$ text "should gen?" <+> ppr should_gen)
356
357
       ; return should_gen }

358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
{- Note [Kind generalisation plan]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When should we do kind-generalisation for user-written type signature?
Answer: we use the same rule as for value bindings:

 * We always kind-generalise if the type signature is closed
 * Additionally, we attempt to generalise if we have NoMonoLocalBinds

Trac #13337 shows the problem if we kind-generalise an open type (i.e.
one that mentions in-scope tpe variable
  foo :: forall k (a :: k) proxy. (Typeable k, Typeable a)
      => proxy a -> String
  foo _ = case eqT :: Maybe (k :~: Type) of
            Nothing   -> ...
            Just Refl -> case eqT :: Maybe (a :~: Int) of ...

In the expression type sig on the last line, we have (a :: k)
but (Int :: Type).  Since (:~:) is kind-homogeneous, this requires
k ~ *, which is true in the Refl branch of the outer case.

That equality will be solved if we allow it to float out to the
implication constraint for the Refl match, bnot not if we aggressively
attempt to solve all equalities the moment they occur; that is, when
checking (Maybe (a :~: Int)).   (NB: solveEqualities fails unless it
solves all the kind equalities, which is the right thing at top level.)

So here the right thing is simply not to do kind generalisation!

386
387
388
389
390
391
392
393
394
395
396
397
************************************************************************
*                                                                      *
      Type-checking modes
*                                                                      *
************************************************************************

The kind-checker is parameterised by a TcTyMode, which contains some
information about where we're checking a type.

The renamer issues errors about what it can. All errors issued here must
concern things that the renamer can't handle.

Austin Seipp's avatar
Austin Seipp committed
398
-}
399

eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
400
401
402
403
-- | Info about the context in which we're checking a type. Currently,
-- differentiates only between types and kinds, but this will likely
-- grow, at least to include the distinction between patterns and
-- not-patterns.
Richard Eisenberg's avatar
Richard Eisenberg committed
404
405
406
data TcTyMode
  = TcTyMode { mode_level :: TypeOrKind
             , mode_unsat :: Bool        -- True <=> allow unsaturated type families
407
             }
Richard Eisenberg's avatar
Richard Eisenberg committed
408
409
 -- The mode_unsat field is solely so that type families/synonyms can be unsaturated
 -- in GHCi :kind calls
410
411

typeLevelMode :: TcTyMode
Richard Eisenberg's avatar
Richard Eisenberg committed
412
typeLevelMode = TcTyMode { mode_level = TypeLevel, mode_unsat = False }
413
414

kindLevelMode :: TcTyMode
Richard Eisenberg's avatar
Richard Eisenberg committed
415
416
417
418
kindLevelMode = TcTyMode { mode_level = KindLevel, mode_unsat = False }

allowUnsaturated :: TcTyMode -> TcTyMode
allowUnsaturated mode = mode { mode_unsat = True }
419
420
421
422
423

-- switch to kind level
kindLevel :: TcTyMode -> TcTyMode
kindLevel mode = mode { mode_level = KindLevel }

eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
424
425
426
instance Outputable TcTyMode where
  ppr = ppr . mode_level

427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
{-
Note [Bidirectional type checking]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In expressions, whenever we see a polymorphic identifier, say `id`, we are
free to instantiate it with metavariables, knowing that we can always
re-generalize with type-lambdas when necessary. For example:

  rank2 :: (forall a. a -> a) -> ()
  x = rank2 id

When checking the body of `x`, we can instantiate `id` with a metavariable.
Then, when we're checking the application of `rank2`, we notice that we really
need a polymorphic `id`, and then re-generalize over the unconstrained
metavariable.

In types, however, we're not so lucky, because *we cannot re-generalize*!
There is no lambda. So, we must be careful only to instantiate at the last
possible moment, when we're sure we're never going to want the lost polymorphism
445
again. This is done in calls to tcInstBinders.
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470

To implement this behavior, we use bidirectional type checking, where we
explicitly think about whether we know the kind of the type we're checking
or not. Note that there is a difference between not knowing a kind and
knowing a metavariable kind: the metavariables are TauTvs, and cannot become
forall-quantified kinds. Previously (before dependent types), there were
no higher-rank kinds, and so we could instantiate early and be sure that
no types would have polymorphic kinds, and so we could always assume that
the kind of a type was a fresh metavariable. Not so anymore, thus the
need for two algorithms.

For HsType forms that can never be kind-polymorphic, we implement only the
"down" direction, where we safely assume a metavariable kind. For HsType forms
that *can* be kind-polymorphic, we implement just the "up" (functions with
"infer" in their name) version, as we gain nothing by also implementing the
"down" version.

Note [Future-proofing the type checker]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As discussed in Note [Bidirectional type checking], each HsType form is
handled in *either* tc_infer_hs_type *or* tc_hs_type. These functions
are mutually recursive, so that either one can work for any type former.
But, we want to make sure that our pattern-matches are complete. So,
we have a bunch of repetitive code just so that we get warnings if we're
missing any patterns.
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487

Note [The tcType invariant]
~~~~~~~~~~~~~~~~~~~~~~~~~~~
If    tc_ty = tc_hs_type hs_ty exp_kind
then
      typeKind tc_ty = exp_kind
without any zonking needed.  The reason for this is that in
tcInferApps we see (F ty), and we kind-check 'ty' with an
expected-kind coming from F.  Then, to make the resulting application
well kinded --- see Note [Ensure well-kinded types] in TcType --- we
need the kind-checked 'ty' to have exactly the kind that F expects,
with no funny zonking nonsense in between.

The tcType invariant also applies to checkExpectedKind: if
    (tc_ty, _, _) = checkExpectedKind ty act_ki exp_ki
then
    typeKind tc_ty = exp_ki
488
-}
489

490
------------------------------------------
491
492
493
-- | Check and desugar a type, returning the core type and its
-- possibly-polymorphic kind. Much like 'tcInferRho' at the expression
-- level.
494
tc_infer_lhs_type :: TcTyMode -> LHsType GhcRn -> TcM (TcType, TcKind)
495
496
tc_infer_lhs_type mode (L span ty)
  = setSrcSpan span $
497
498
    do { (ty', kind) <- tc_infer_hs_type mode ty
       ; return (ty', kind) }
499
500
501

-- | Infer the kind of a type and desugar. This is the "up" type-checker,
-- as described in Note [Bidirectional type checking]
502
tc_infer_hs_type :: TcTyMode -> HsType GhcRn -> TcM (TcType, TcKind)
Ben Gamari's avatar
Ben Gamari committed
503
504
tc_infer_hs_type mode (HsTyVar _ (L _ tv)) = tcTyVar mode tv
tc_infer_hs_type mode (HsAppTy ty1 ty2)
505
506
507
  = do { let (fun_ty, arg_tys) = splitHsAppTys ty1 [ty2]
       ; (fun_ty', fun_kind) <- tc_infer_lhs_type mode fun_ty
       ; fun_kind' <- zonkTcType fun_kind
508
       ; tcTyApps mode fun_ty fun_ty' fun_kind' arg_tys }
Ben Gamari's avatar
Ben Gamari committed
509
510
tc_infer_hs_type mode (HsParTy t)     = tc_infer_lhs_type mode t
tc_infer_hs_type mode (HsOpTy lhs (L loc_op op) rhs)
511
512
513
  | not (op `hasKey` funTyConKey)
  = do { (op', op_kind) <- tcTyVar mode op
       ; op_kind' <- zonkTcType op_kind
Ben Gamari's avatar
Ben Gamari committed
514
515
       ; tcTyApps mode (noLoc $ HsTyVar NotPromoted (L loc_op op)) op' op_kind' [lhs, rhs] }
tc_infer_hs_type mode (HsKindSig ty sig)
516
517
518
  = do { sig' <- tc_lhs_kind (kindLevel mode) sig
       ; ty' <- tc_lhs_type mode ty sig'
       ; return (ty', sig') }
519
520
521
522
523
524
-- HsSpliced is an annotation produced by 'RnSplice.rnSpliceType' to communicate
-- the splice location to the typechecker. Here we skip over it in order to have
-- the same kind inferred for a given expression whether it was produced from
-- splices or not.
--
-- See Note [Delaying modFinalizers in untyped splices].
Ben Gamari's avatar
Ben Gamari committed
525
tc_infer_hs_type mode (HsSpliceTy (HsSpliced _ (HsSplicedTy ty)) _)
526
  = tc_infer_hs_type mode ty
Ben Gamari's avatar
Ben Gamari committed
527
528
tc_infer_hs_type mode (HsDocTy ty _) = tc_infer_lhs_type mode ty
tc_infer_hs_type _    (HsCoreTy ty)  = return (ty, typeKind ty)
529
530
531
532
533
tc_infer_hs_type mode other_ty
  = do { kv <- newMetaKindVar
       ; ty' <- tc_hs_type mode other_ty kv
       ; return (ty', kv) }

534
------------------------------------------
535
tc_lhs_type :: TcTyMode -> LHsType GhcRn -> TcKind -> TcM TcType
536
tc_lhs_type mode (L span ty) exp_kind
537
  = setSrcSpan span $
538
    tc_hs_type mode ty exp_kind
539

540
------------------------------------------
541
542
tc_fun_type :: TcTyMode -> LHsType GhcRn -> LHsType GhcRn -> TcKind
            -> TcM TcType
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
543
544
tc_fun_type mode ty1 ty2 exp_kind = case mode_level mode of
  TypeLevel ->
545
546
547
548
    do { arg_k <- newOpenTypeKind
       ; res_k <- newOpenTypeKind
       ; ty1' <- tc_lhs_type mode ty1 arg_k
       ; ty2' <- tc_lhs_type mode ty2 res_k
Ben Gamari's avatar
Ben Gamari committed
549
       ; checkExpectedKind (HsFunTy ty1 ty2) (mkFunTy ty1' ty2') liftedTypeKind exp_kind }
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
550
551
552
  KindLevel ->  -- no representation polymorphism in kinds. yet.
    do { ty1' <- tc_lhs_type mode ty1 liftedTypeKind
       ; ty2' <- tc_lhs_type mode ty2 liftedTypeKind
Ben Gamari's avatar
Ben Gamari committed
553
       ; checkExpectedKind (HsFunTy ty1 ty2) (mkFunTy ty1' ty2') liftedTypeKind exp_kind }
554

555
------------------------------------------
556
tc_hs_type :: TcTyMode -> HsType GhcRn -> TcKind -> TcM TcType
557
558
559
-- See Note [The tcType invariant]
-- See Note [Bidirectional type checking]

Ben Gamari's avatar
Ben Gamari committed
560
561
tc_hs_type mode (HsParTy ty)   exp_kind = tc_lhs_type mode ty exp_kind
tc_hs_type mode (HsDocTy ty _) exp_kind = tc_lhs_type mode ty exp_kind
562
tc_hs_type _ ty@(HsBangTy {}) _
563
564
565
    -- While top-level bangs at this point are eliminated (eg !(Maybe Int)),
    -- other kinds of bangs are not (eg ((!Maybe) Int)). These kinds of
    -- bangs are invalid, so fail. (#7210)
566
    = failWithTc (text "Unexpected strictness annotation:" <+> ppr ty)
Ben Gamari's avatar
Ben Gamari committed
567
tc_hs_type _ ty@(HsRecTy _)      _
568
      -- Record types (which only show up temporarily in constructor
569
      -- signatures) should have been removed by now
570
    = failWithTc (text "Record syntax is illegal here:" <+> ppr ty)
571

572
573
574
575
576
-- HsSpliced is an annotation produced by 'RnSplice.rnSpliceType'.
-- Here we get rid of it and add the finalizers to the global environment
-- while capturing the local environment.
--
-- See Note [Delaying modFinalizers in untyped splices].
Ben Gamari's avatar
Ben Gamari committed
577
578
579
tc_hs_type mode (HsSpliceTy (HsSpliced mod_finalizers (HsSplicedTy ty))
                            _
                )
580
581
582
583
           exp_kind
  = do addModFinalizersWithLclEnv mod_finalizers
       tc_hs_type mode ty exp_kind

584
585
-- This should never happen; type splices are expanded by the renamer
tc_hs_type _ ty@(HsSpliceTy {}) _exp_kind
586
  = failWithTc (text "Unexpected type splice:" <+> ppr ty)
587

588
---------- Functions and applications
Ben Gamari's avatar
Ben Gamari committed
589
tc_hs_type mode (HsFunTy ty1 ty2) exp_kind
590
  = tc_fun_type mode ty1 ty2 exp_kind
591

Ben Gamari's avatar
Ben Gamari committed
592
tc_hs_type mode (HsOpTy ty1 (L _ op) ty2) exp_kind
593
  | op `hasKey` funTyConKey
594
  = tc_fun_type mode ty1 ty2 exp_kind
595
596

--------- Foralls
597
tc_hs_type mode (HsForAllTy { hst_bndrs = hs_tvs, hst_body = ty }) exp_kind
598
  = fmap fst $
599
    tcExplicitTKBndrs hs_tvs $ \ tvs' ->
600
    -- Do not kind-generalise here!  See Note [Kind generalisation]
601
    -- Why exp_kind?  See Note [Body kind of HsForAllTy]
602
603
    do { ty' <- tc_lhs_type mode ty exp_kind
       ; let bound_vars = allBoundVariables ty'
Simon Peyton Jones's avatar
Simon Peyton Jones committed
604
             bndrs      = mkTyVarBinders Specified tvs'
605
       ; return (mkForAllTys bndrs ty', bound_vars) }
606

607
tc_hs_type mode (HsQualTy { hst_ctxt = ctxt, hst_body = ty }) exp_kind
608
609
610
611
  | null (unLoc ctxt)
  = tc_lhs_type mode ty exp_kind

  | otherwise
612
  = do { ctxt' <- tc_hs_context mode ctxt
613
614
615
616

         -- See Note [Body kind of a HsQualTy]
       ; ty' <- if isConstraintKind exp_kind
                then tc_lhs_type mode ty constraintKind
617
618
619
                else do { ek <- newOpenTypeKind
                                -- The body kind (result of the function)
                                -- can be * or #, hence newOpenTypeKind
620
621
                        ; ty' <- tc_lhs_type mode ty ek
                        ; checkExpectedKind (unLoc ty) ty' liftedTypeKind exp_kind }
622
623

       ; return (mkPhiTy ctxt' ty') }
624
625

--------- Lists, arrays, and tuples
Ben Gamari's avatar
Ben Gamari committed
626
tc_hs_type mode rn_ty@(HsListTy elt_ty) exp_kind
627
  = do { tau_ty <- tc_lhs_type mode elt_ty liftedTypeKind
628
       ; checkWiredInTyCon listTyCon
629
       ; checkExpectedKind rn_ty (mkListTy tau_ty) liftedTypeKind exp_kind }
630

Ben Gamari's avatar
Ben Gamari committed
631
tc_hs_type mode rn_ty@(HsPArrTy elt_ty) exp_kind
632
633
  = do { MASSERT( isTypeLevel (mode_level mode) )
       ; tau_ty <- tc_lhs_type mode elt_ty liftedTypeKind
634
       ; checkWiredInTyCon parrTyCon
635
       ; checkExpectedKind rn_ty (mkPArrTy tau_ty) liftedTypeKind exp_kind }
636

dreixel's avatar
dreixel committed
637
-- See Note [Distinguishing tuple kinds] in HsTypes
638
-- See Note [Inferring tuple kinds]
Ben Gamari's avatar
Ben Gamari committed
639
tc_hs_type mode rn_ty@(HsTupleTy HsBoxedOrConstraintTuple hs_tys) exp_kind
640
     -- (NB: not zonking before looking at exp_k, to avoid left-right bias)
641
  | Just tup_sort <- tupKindSort_maybe exp_kind
642
  = traceTc "tc_hs_type tuple" (ppr hs_tys) >>
643
    tc_tuple rn_ty mode tup_sort hs_tys exp_kind
dreixel's avatar
dreixel committed
644
  | otherwise
Austin Seipp's avatar
Austin Seipp committed
645
  = do { traceTc "tc_hs_type tuple 2" (ppr hs_tys)
646
647
       ; (tys, kinds) <- mapAndUnzipM (tc_infer_lhs_type mode) hs_tys
       ; kinds <- mapM zonkTcType kinds
648
649
650
651
652
653
           -- Infer each arg type separately, because errors can be
           -- confusing if we give them a shared kind.  Eg Trac #7410
           -- (Either Int, Int), we do not want to get an error saying
           -- "the second argument of a tuple should have kind *->*"

       ; let (arg_kind, tup_sort)
654
655
656
               = case [ (k,s) | k <- kinds
                              , Just s <- [tupKindSort_maybe k] ] of
                    ((k,s) : _) -> (k,s)
657
                    [] -> (liftedTypeKind, BoxedTuple)
658
659
         -- In the [] case, it's not clear what the kind is, so guess *

660
       ; tys' <- sequence [ setSrcSpan loc $
661
662
                            checkExpectedKind hs_ty ty kind arg_kind
                          | ((L loc hs_ty),ty,kind) <- zip3 hs_tys tys kinds ]
663

664
       ; finish_tuple rn_ty tup_sort tys' (map (const arg_kind) tys') exp_kind }
665

dreixel's avatar
dreixel committed
666

Ben Gamari's avatar
Ben Gamari committed
667
tc_hs_type mode rn_ty@(HsTupleTy hs_tup_sort tys) exp_kind
668
  = tc_tuple rn_ty mode tup_sort tys exp_kind
669
670
671
672
673
674
675
  where
    tup_sort = case hs_tup_sort of  -- Fourth case dealt with above
                  HsUnboxedTuple    -> UnboxedTuple
                  HsBoxedTuple      -> BoxedTuple
                  HsConstraintTuple -> ConstraintTuple
                  _                 -> panic "tc_hs_type HsTupleTy"

Ben Gamari's avatar
Ben Gamari committed
676
tc_hs_type mode rn_ty@(HsSumTy hs_tys) exp_kind
677
  = do { let arity = length hs_tys
678
679
       ; arg_kinds <- mapM (\_ -> newOpenTypeKind) hs_tys
       ; tau_tys   <- zipWithM (tc_lhs_type mode) hs_tys arg_kinds
680
       ; let arg_reps = map getRuntimeRepFromKind arg_kinds
Richard Eisenberg's avatar
Richard Eisenberg committed
681
             arg_tys  = arg_reps ++ tau_tys
682
683
       ; checkExpectedKind rn_ty
                           (mkTyConApp (sumTyCon arity) arg_tys)
Richard Eisenberg's avatar
Richard Eisenberg committed
684
685
                           (unboxedSumKind arg_reps)
                           exp_kind
686
       }
dreixel's avatar
dreixel committed
687

688
--------- Promoted lists and tuples
Ben Gamari's avatar
Ben Gamari committed
689
tc_hs_type mode rn_ty@(HsExplicitListTy _ _k tys) exp_kind
690
  = do { tks <- mapM (tc_infer_lhs_type mode) tys
691
       ; (taus', kind) <- unifyKinds tys tks
692
       ; let ty = (foldr (mk_cons kind) (mk_nil kind) taus')
693
       ; checkExpectedKind rn_ty ty (mkListTy kind) exp_kind }
694
  where
695
696
    mk_cons k a b = mkTyConApp (promoteDataCon consDataCon) [k, a, b]
    mk_nil  k     = mkTyConApp (promoteDataCon nilDataCon) [k]
697

698
tc_hs_type mode rn_ty@(HsExplicitTupleTy _ tys) exp_kind
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
699
700
701
702
703
704
  -- using newMetaKindVar means that we force instantiations of any polykinded
  -- types. At first, I just used tc_infer_lhs_type, but that led to #11255.
  = do { ks   <- replicateM arity newMetaKindVar
       ; taus <- zipWithM (tc_lhs_type mode) tys ks
       ; let kind_con   = tupleTyCon           Boxed arity
             ty_con     = promotedTupleDataCon Boxed arity
705
             tup_k      = mkTyConApp kind_con ks
706
       ; checkExpectedKind rn_ty (mkTyConApp ty_con (ks ++ taus)) tup_k exp_kind }
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
707
708
  where
    arity = length tys
709
710

--------- Constraint types
Ben Gamari's avatar
Ben Gamari committed
711
tc_hs_type mode rn_ty@(HsIParamTy (L _ n) ty) exp_kind
712
713
  = do { MASSERT( isTypeLevel (mode_level mode) )
       ; ty' <- tc_lhs_type mode ty liftedTypeKind
714
       ; let n' = mkStrLitTy $ hsIPNameFS n
715
       ; ipClass <- tcLookupClass ipClassName
716
       ; checkExpectedKind rn_ty (mkClassPred ipClass [n',ty'])
717
718
           constraintKind exp_kind }

Ben Gamari's avatar
Ben Gamari committed
719
tc_hs_type mode rn_ty@(HsEqTy ty1 ty2) exp_kind
720
721
  = do { (ty1', kind1) <- tc_infer_lhs_type mode ty1
       ; (ty2', kind2) <- tc_infer_lhs_type mode ty2
722
       ; ty2'' <- checkExpectedKind (unLoc ty2) ty2' kind2 kind1
723
724
       ; eq_tc <- tcLookupTyCon eqTyConName
       ; let ty' = mkNakedTyConApp eq_tc [kind1, ty1', ty2'']
725
       ; checkExpectedKind rn_ty ty' constraintKind exp_kind }
726
727

--------- Literals
Ben Gamari's avatar
Ben Gamari committed
728
tc_hs_type _ rn_ty@(HsTyLit (HsNumTy _ n)) exp_kind
729
  = do { checkWiredInTyCon typeNatKindCon
730
       ; checkExpectedKind rn_ty (mkNumLitTy n) typeNatKind exp_kind }
731

Ben Gamari's avatar
Ben Gamari committed
732
tc_hs_type _ rn_ty@(HsTyLit (HsStrTy _ s)) exp_kind
733
  = do { checkWiredInTyCon typeSymbolKindCon
734
       ; checkExpectedKind rn_ty (mkStrLitTy s) typeSymbolKind exp_kind }
735
736
737
738
739
740
741

--------- Potentially kind-polymorphic types: call the "up" checker
-- See Note [Future-proofing the type checker]
tc_hs_type mode ty@(HsTyVar {})   ek = tc_infer_hs_type_ek mode ty ek
tc_hs_type mode ty@(HsAppTy {})   ek = tc_infer_hs_type_ek mode ty ek
tc_hs_type mode ty@(HsOpTy {})    ek = tc_infer_hs_type_ek mode ty ek
tc_hs_type mode ty@(HsKindSig {}) ek = tc_infer_hs_type_ek mode ty ek
Ben Gamari's avatar
Ben Gamari committed
742
tc_hs_type mode ty@(HsCoreTy {})  ek = tc_infer_hs_type_ek mode ty ek
743
744

tc_hs_type _ (HsWildCardTy wc) exp_kind
745
  = do { wc_tv <- tcWildCardOcc wc exp_kind
746
747
748
749
750
       ; return (mkNakedCastTy (mkTyVarTy wc_tv)
                               (mkTcNomReflCo exp_kind))
         -- Take care here! Even though the coercion is Refl,
         -- we still need it to establish Note [The tcType invariant]
       }
751
752
753
754
755

-- disposed of by renamer
tc_hs_type _ ty@(HsAppsTy {}) _
  = pprPanic "tc_hs_tyep HsAppsTy" (ppr ty)

756
tcWildCardOcc :: HsWildCardInfo GhcRn -> Kind -> TcM TcTyVar
757
758
759
760
761
762
763
tcWildCardOcc wc_info exp_kind
  = do { wc_tv <- tcLookupTyVar (wildCardName wc_info)
          -- The wildcard's kind should be an un-filled-in meta tyvar
       ; let Just wc_kind_var = tcGetTyVar_maybe (tyVarKind wc_tv)
       ; writeMetaTyVar wc_kind_var exp_kind
       ; return wc_tv }

764
765
---------------------------
-- | Call 'tc_infer_hs_type' and check its result against an expected kind.
766
tc_infer_hs_type_ek :: TcTyMode -> HsType GhcRn -> TcKind -> TcM TcType
Simon Peyton Jones's avatar
Simon Peyton Jones committed
767
768
769
tc_infer_hs_type_ek mode hs_ty ek
  = do { (ty, k) <- tc_infer_hs_type mode hs_ty
       ; checkExpectedKind hs_ty ty k ek }
thomasw's avatar
thomasw committed
770

771
---------------------------
772
tupKindSort_maybe :: TcKind -> Maybe TupleSort
773
tupKindSort_maybe k
Simon Peyton Jones's avatar
Simon Peyton Jones committed
774
  | Just (k', _) <- splitCastTy_maybe k = tupKindSort_maybe k'
Ben Gamari's avatar
Ben Gamari committed
775
  | Just k'      <- tcView k            = tupKindSort_maybe k'
776
777
  | isConstraintKind k = Just ConstraintTuple
  | isLiftedTypeKind k = Just BoxedTuple
778
779
  | otherwise          = Nothing

780
781
tc_tuple :: HsType GhcRn -> TcTyMode -> TupleSort -> [LHsType GhcRn] -> TcKind -> TcM TcType
tc_tuple rn_ty mode tup_sort tys exp_kind
782
783
  = do { arg_kinds <- case tup_sort of
           BoxedTuple      -> return (nOfThem arity liftedTypeKind)
784
           UnboxedTuple    -> mapM (\_ -> newOpenTypeKind) tys
785
786
           ConstraintTuple -> return (nOfThem arity constraintKind)
       ; tau_tys <- zipWithM (tc_lhs_type mode) tys arg_kinds
787
       ; finish_tuple rn_ty tup_sort tau_tys arg_kinds exp_kind }
dreixel's avatar
dreixel committed
788
  where
789
790
    arity   = length tys

791
792
finish_tuple :: HsType GhcRn
             -> TupleSort
793
794
795
796
             -> [TcType]    -- ^ argument types
             -> [TcKind]    -- ^ of these kinds
             -> TcKind      -- ^ expected kind of the whole tuple
             -> TcM TcType
797
finish_tuple rn_ty tup_sort tau_tys tau_kinds exp_kind
798
799
  = do { traceTc "finish_tuple" (ppr res_kind $$ ppr tau_kinds $$ ppr exp_kind)
       ; let arg_tys  = case tup_sort of
800
                   -- See also Note [Unboxed tuple RuntimeRep vars] in TyCon
Richard Eisenberg's avatar
Richard Eisenberg committed
801
                 UnboxedTuple    -> tau_reps ++ tau_tys
802
803
                 BoxedTuple      -> tau_tys
                 ConstraintTuple -> tau_tys
804
       ; tycon <- case tup_sort of
805
806
807
808
809
810
811
812
           ConstraintTuple
             | arity > mAX_CTUPLE_SIZE
                         -> failWith (bigConstraintTuple arity)
             | otherwise -> tcLookupTyCon (cTupleTyConName arity)
           BoxedTuple    -> do { let tc = tupleTyCon Boxed arity
                               ; checkWiredInTyCon tc
                               ; return tc }
           UnboxedTuple  -> return (tupleTyCon Unboxed arity)
813
       ; checkExpectedKind rn_ty (mkTyConApp tycon arg_tys) res_kind exp_kind }
814
  where
815
    arity = length tau_tys
816
    tau_reps = map getRuntimeRepFromKind tau_kinds
817
    res_kind = case tup_sort of
Richard Eisenberg's avatar
Richard Eisenberg committed
818
                 UnboxedTuple    -> unboxedTupleKind tau_reps
819
820
                 BoxedTuple      -> liftedTypeKind
                 ConstraintTuple -> constraintKind
821

822
823
bigConstraintTuple :: Arity -> MsgDoc
bigConstraintTuple arity
824
825
826
  = hang (text "Constraint tuple arity too large:" <+> int arity
          <+> parens (text "max arity =" <+> int mAX_CTUPLE_SIZE))
       2 (text "Instead, use a nested tuple")
827

828
---------------------------
829
830
831
832
833
834
-- | Apply a type of a given kind to a list of arguments. This instantiates
-- invisible parameters as necessary. Always consumes all the arguments,
-- using matchExpectedFunKind as necessary.
-- This takes an optional @VarEnv Kind@ which maps kind variables to kinds.
-- These kinds should be used to instantiate invisible kind variables;
-- they come from an enclosing class for an associated type/data family.
835
tcInferApps :: TcTyMode
836
            -> Maybe (VarEnv Kind)  -- ^ Possibly, kind info (see above)
837
            -> LHsType GhcRn        -- ^ Function (for printing only)
838
839
            -> TcType               -- ^ Function (could be knot-tied)
            -> TcKind               -- ^ Function kind (zonked)
840
            -> [LHsType GhcRn]      -- ^ Args
841
            -> TcM (TcType, [TcType], TcKind) -- ^ (f args, args, result kind)
Simon Peyton Jones's avatar
Simon Peyton Jones committed
842
tcInferApps mode mb_kind_info orig_hs_ty fun_ty fun_ki orig_hs_args
Simon Peyton Jones's avatar
Simon Peyton Jones committed
843
844
845
846
  = do { traceTc "tcInferApps {" (ppr orig_hs_ty $$ ppr orig_hs_args $$ ppr fun_ki)
       ; stuff <- go 1 [] empty_subst fun_ty orig_ki_binders orig_inner_ki orig_hs_args
       ; traceTc "tcInferApps }" empty
       ; return stuff }
847
  where
Simon Peyton Jones's avatar
Simon Peyton Jones committed
848
849
850
    empty_subst                      = mkEmptyTCvSubst $ mkInScopeSet $
                                       tyCoVarsOfType fun_ki
    (orig_ki_binders, orig_inner_ki) = tcSplitPiTys fun_ki
Richard Eisenberg's avatar
Richard Eisenberg committed
851

Simon Peyton Jones's avatar
Simon Peyton Jones committed
852
    go :: Int             -- the # of the next argument
Richard Eisenberg's avatar
Richard Eisenberg committed
853
854
855
856
857
858
859
860
861
       -> [TcType]        -- already type-checked args, in reverse order
       -> TCvSubst        -- instantiating substitution
       -> TcType          -- function applied to some args, could be knot-tied
       -> [TyBinder]      -- binders in function kind (both vis. and invis.)
       -> TcKind          -- function kind body (not a Pi-type)
       -> [LHsType GhcRn] -- un-type-checked args
       -> TcM (TcType, [TcType], TcKind)  -- same as overall return type

      -- no user-written args left. We're done!
Simon Peyton Jones's avatar
Simon Peyton Jones committed
862
    go _ acc_args subst fun ki_binders inner_ki []
Richard Eisenberg's avatar
Richard Eisenberg committed
863
864
865
      = return (fun, reverse acc_args, substTy subst $ mkPiTys ki_binders inner_ki)

      -- The function's kind has a binder. Is it visible or invisible?
Simon Peyton Jones's avatar
Simon Peyton Jones committed
866
867
    go n acc_args subst fun (ki_binder:ki_binders) inner_ki
       all_args@(arg:args)
Richard Eisenberg's avatar
Richard Eisenberg committed
868
869
870
871
      | isInvisibleBinder ki_binder
        -- It's invisible. Instantiate.
      = do { traceTc "tcInferApps (invis)" (ppr ki_binder $$ ppr subst)
           ; (subst', arg') <- tcInstBinder mb_kind_info subst ki_binder
Simon Peyton Jones's avatar
Simon Peyton Jones committed
872
873
           ; go n (arg' : acc_args) subst' (mkNakedAppTy fun arg')
                ki_binders inner_ki all_args }
Richard Eisenberg's avatar
Richard Eisenberg committed
874
875
876

      | otherwise
        -- It's visible. Check the next user-written argument
Simon Peyton Jones's avatar
Simon Peyton Jones committed
877
878
879
880
      = do { traceTc "tcInferApps (vis)" (vcat [ ppr ki_binder, ppr arg
                                               , ppr (tyBinderType ki_binder)
                                               , ppr subst ])
           ; arg' <- addErrCtxt (funAppCtxt orig_hs_ty arg n) $
Richard Eisenberg's avatar
Richard Eisenberg committed
881
882
                     tc_lhs_type mode arg (substTy subst $ tyBinderType ki_binder)
           ; let subst' = extendTvSubstBinderAndInScope subst ki_binder arg'
Simon Peyton Jones's avatar
Simon Peyton Jones committed
883
884
           ; go (n+1) (arg' : acc_args) subst' (mkNakedAppTy fun arg')
                ki_binders inner_ki args }
Richard Eisenberg's avatar
Richard Eisenberg committed
885
886

       -- We've run out of known binders in the functions's kind.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
887
    go n acc_args subst fun [] inner_ki all_args
Richard Eisenberg's avatar
Richard Eisenberg committed
888
889
      | not (null new_ki_binders)
         -- But, after substituting, we have more binders.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
890
      = go n acc_args zapped_subst fun new_ki_binders new_inner_ki all_args
Richard Eisenberg's avatar
Richard Eisenberg committed
891
892
893
894

      | otherwise
         -- Even after substituting, still no binders. Use matchExpectedFunKind
      = do { traceTc "tcInferApps (no binder)" (ppr new_inner_ki $$ ppr zapped_subst)
895
896
897
898
           ; (co, arg_k, res_k) <- matchExpectedFunKind hs_ty substed_inner_ki
           ; let new_in_scope = tyCoVarsOfTypes [arg_k, res_k]
                 subst'       = zapped_subst `extendTCvInScopeSet` new_in_scope
           ; go n acc_args subst'
899
                (fun `mkNakedCastTy` co)
900
901
                [mkAnonBinder arg_k]
                res_k all_args }
Richard Eisenberg's avatar
Richard Eisenberg committed
902
903
904
905
      where
        substed_inner_ki               = substTy subst inner_ki
        (new_ki_binders, new_inner_ki) = tcSplitPiTys substed_inner_ki
        zapped_subst                   = zapTCvSubst subst
906
907
        hs_ty = mkHsAppTys orig_hs_ty (take (n-1) orig_hs_args)

908