mirrored from https://gitlab.haskell.org/ghc/ghc.git
-
Notifications
You must be signed in to change notification settings - Fork 704
/
TcHsType.lhs
1855 lines (1574 loc) · 72.3 KB
/
TcHsType.lhs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
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
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
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
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%
% (c) The University of Glasgow 2006
% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
\section[TcMonoType]{Typechecking user-specified @MonoTypes@}
\begin{code}
{-# OPTIONS -fno-warn-tabs #-}
-- The above warning supression flag is a temporary kludge.
-- While working on this module you are encouraged to remove it and
-- detab the module (please do the detabbing in a separate patch). See
-- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#TabsvsSpaces
-- for details
module TcHsType (
tcHsSigType, tcHsSigTypeNC, tcHsDeriv, tcHsVectInst,
tcHsInstHead,
UserTypeCtxt(..),
-- Type checking type and class decls
kcLookupKind, kcTyClTyVars, tcTyClTyVars,
tcHsConArgType, tcDataKindSig,
tcClassSigType,
-- Kind-checking types
-- No kind generalisation, no checkValidType
KindCheckingStrategy(..), kcStrategy, kcStrategyFamDecl,
kcHsTyVarBndrs, tcHsTyVarBndrs,
tcHsLiftedType, tcHsOpenType,
tcLHsType, tcCheckLHsType,
tcHsContext, tcInferApps, tcHsArgTys,
kindGeneralize, checkKind,
-- Sort-checking kinds
tcLHsKind,
-- Pattern type signatures
tcHsPatSigType, tcPatSig
) where
#include "HsVersions.h"
#ifdef GHCI /* Only if bootstrapped */
import {-# SOURCE #-} TcSplice( tcSpliceType )
#endif
import HsSyn
import TcRnMonad
import TcEvidence( HsWrapper )
import TcEnv
import TcMType
import TcValidity
import TcUnify
import TcIface
import TcType
import Type
import TypeRep( Type(..) ) -- For the mkNakedXXX stuff
import Kind
import Var
import VarSet
import TyCon
import DataCon
import TysPrim ( liftedTypeKindTyConName, constraintKindTyConName )
import Class
import Name
import NameEnv
import TysWiredIn
import BasicTypes
import SrcLoc
import ErrUtils ( isEmptyMessages )
import DynFlags ( ExtensionFlag( Opt_DataKinds ), getDynFlags )
import Unique
import UniqSupply
import Outputable
import FastString
import Util
import Control.Monad ( unless, when, zipWithM )
import PrelNames( ipClassName, funTyConKey )
\end{code}
----------------------------
General notes
----------------------------
Generally speaking we now type-check types in three phases
1. kcHsType: kind check the HsType
*includes* performing any TH type splices;
so it returns a translated, and kind-annotated, type
2. dsHsType: convert from HsType to Type:
perform zonking
expand type synonyms [mkGenTyApps]
hoist the foralls [tcHsType]
3. checkValidType: check the validity of the resulting type
Often these steps are done one after the other (tcHsSigType).
But in mutually recursive groups of type and class decls we do
1 kind-check the whole group
2 build TyCons/Classes in a knot-tied way
3 check the validity of types in the now-unknotted TyCons/Classes
For example, when we find
(forall a m. m a -> m a)
we bind a,m to kind varibles and kind-check (m a -> m a). This makes
a get kind *, and m get kind *->*. Now we typecheck (m a -> m a) in
an environment that binds a and m suitably.
The kind checker passed to tcHsTyVars needs to look at enough to
establish the kind of the tyvar:
* For a group of type and class decls, it's just the group, not
the rest of the program
* For a tyvar bound in a pattern type signature, its the types
mentioned in the other type signatures in that bunch of patterns
* For a tyvar bound in a RULE, it's the type signatures on other
universally quantified variables in the rule
Note that this may occasionally give surprising results. For example:
data T a b = MkT (a b)
Here we deduce a::*->*, b::*
But equally valid would be a::(*->*)-> *, b::*->*
Validity checking
~~~~~~~~~~~~~~~~~
Some of the validity check could in principle be done by the kind checker,
but not all:
- During desugaring, we normalise by expanding type synonyms. Only
after this step can we check things like type-synonym saturation
e.g. type T k = k Int
type S a = a
Then (T S) is ok, because T is saturated; (T S) expands to (S Int);
and then S is saturated. This is a GHC extension.
- Similarly, also a GHC extension, we look through synonyms before complaining
about the form of a class or instance declaration
- Ambiguity checks involve functional dependencies, and it's easier to wait
until knots have been resolved before poking into them
Also, in a mutually recursive group of types, we can't look at the TyCon until we've
finished building the loop. So to keep things simple, we postpone most validity
checking until step (3).
Knot tying
~~~~~~~~~~
During step (1) we might fault in a TyCon defined in another module, and it might
(via a loop) refer back to a TyCon defined in this module. So when we tie a big
knot around type declarations with ARecThing, so that the fault-in code can get
the TyCon being defined.
%************************************************************************
%* *
Check types AND do validity checking
%* *
%************************************************************************
\begin{code}
tcHsSigType, tcHsSigTypeNC :: UserTypeCtxt -> LHsType Name -> TcM Type
-- NB: it's important that the foralls that come from the top-level
-- HsForAllTy in hs_ty occur *first* in the returned type.
-- See Note [Scoped] with TcSigInfo
tcHsSigType ctxt hs_ty
= addErrCtxt (pprHsSigCtxt ctxt hs_ty) $
tcHsSigTypeNC ctxt hs_ty
tcHsSigTypeNC ctxt (L loc hs_ty)
= setSrcSpan loc $ -- The "In the type..." context
-- comes from the caller; hence "NC"
do { kind <- case expectedKindInCtxt ctxt of
Nothing -> newMetaKindVar
Just k -> return k
-- The kind is checked by checkValidType, and isn't necessarily
-- of kind * in a Template Haskell quote eg [t| Maybe |]
-- Generalise here: see Note [Kind generalisation]
; ty <- tcCheckHsTypeAndGen hs_ty kind
-- Zonk to expose kind information to checkValidType
; ty <- zonkSigType ty
; checkValidType ctxt ty
; return ty }
-----------------
tcHsInstHead :: UserTypeCtxt -> LHsType Name -> TcM ([TyVar], ThetaType, Class, [Type])
-- Like tcHsSigTypeNC, but for an instance head.
tcHsInstHead user_ctxt lhs_ty@(L loc hs_ty)
= setSrcSpan loc $ -- The "In the type..." context comes from the caller
do { inst_ty <- tc_inst_head hs_ty
; kvs <- zonkTcTypeAndFV inst_ty
; kvs <- kindGeneralize kvs
; inst_ty <- zonkSigType (mkForAllTys kvs inst_ty)
; checkValidInstance user_ctxt lhs_ty inst_ty }
tc_inst_head :: HsType Name -> TcM TcType
tc_inst_head (HsForAllTy _ hs_tvs hs_ctxt hs_ty)
= tcHsTyVarBndrs hs_tvs $ \ tvs ->
do { ctxt <- tcHsContext hs_ctxt
; ty <- tc_lhs_type hs_ty ekConstraint -- Body for forall has kind Constraint
; return (mkSigmaTy tvs ctxt ty) }
tc_inst_head hs_ty
= tc_hs_type hs_ty ekConstraint
-----------------
tcHsDeriv :: HsType Name -> TcM ([TyVar], Class, [Type])
-- Like tcHsSigTypeNC, but for the ...deriving( ty ) clause
tcHsDeriv hs_ty
= do { kind <- newMetaKindVar
; ty <- tcCheckHsTypeAndGen hs_ty kind
-- Funny newtype deriving form
-- forall a. C [a]
-- where C has arity 2. Hence any-kinded result
; ty <- zonkSigType ty
; let (tvs, pred) = splitForAllTys ty
; case getClassPredTys_maybe pred of
Just (cls, tys) -> return (tvs, cls, tys)
Nothing -> failWithTc (ptext (sLit "Illegal deriving item") <+> quotes (ppr hs_ty)) }
-- Used for 'VECTORISE [SCALAR] instance' declarations
--
tcHsVectInst :: LHsType Name -> TcM (Class, [Type])
tcHsVectInst ty
| Just (L _ cls_name, tys) <- splitLHsClassTy_maybe ty
= do { (cls, cls_kind) <- tcClass cls_name
; (arg_tys, _res_kind) <- tcInferApps cls_name cls_kind tys
; return (cls, arg_tys) }
| otherwise
= failWithTc $ ptext (sLit "Malformed instance type")
\end{code}
These functions are used during knot-tying in
type and class declarations, when we have to
separate kind-checking, desugaring, and validity checking
%************************************************************************
%* *
The main kind checker: no validity checks here
%* *
%************************************************************************
First a couple of simple wrappers for kcHsType
\begin{code}
tcClassSigType :: LHsType Name -> TcM Type
tcClassSigType lhs_ty@(L _ hs_ty)
= addTypeCtxt lhs_ty $
do { ty <- tcCheckHsTypeAndGen hs_ty liftedTypeKind
; zonkSigType ty }
tcHsConArgType :: NewOrData -> LHsType Name -> TcM Type
-- Permit a bang, but discard it
tcHsConArgType NewType bty = tcHsLiftedType (getBangType bty)
-- Newtypes can't have bangs, but we don't check that
-- until checkValidDataCon, so do not want to crash here
tcHsConArgType DataType bty = tcHsOpenType (getBangType bty)
-- Can't allow an unlifted type for newtypes, because we're effectively
-- going to remove the constructor while coercing it to a lifted type.
-- And newtypes can't be bang'd
---------------------------
tcHsArgTys :: SDoc -> [LHsType Name] -> [Kind] -> TcM [TcType]
tcHsArgTys what tys kinds
= sequence [ addTypeCtxt ty $
tc_lhs_type ty (expArgKind what kind n)
| (ty,kind,n) <- zip3 tys kinds [1..] ]
tc_hs_arg_tys :: SDoc -> [LHsType Name] -> [Kind] -> TcM [TcType]
-- Just like tcHsArgTys but without the addTypeCtxt
tc_hs_arg_tys what tys kinds
= sequence [ tc_lhs_type ty (expArgKind what kind n)
| (ty,kind,n) <- zip3 tys kinds [1..] ]
---------------------------
tcHsOpenType, tcHsLiftedType :: LHsType Name -> TcM TcType
-- Used for type signatures
-- Do not do validity checking
tcHsOpenType ty = addTypeCtxt ty $ tc_lhs_type ty ekOpen
tcHsLiftedType ty = addTypeCtxt ty $ tc_lhs_type ty ekLifted
-- Like tcHsType, but takes an expected kind
tcCheckLHsType :: LHsType Name -> Kind -> TcM Type
tcCheckLHsType hs_ty exp_kind
= addTypeCtxt hs_ty $
tc_lhs_type hs_ty (EK exp_kind expectedKindMsg)
tcLHsType :: LHsType Name -> TcM (TcType, TcKind)
-- Called from outside: set the context
tcLHsType ty = addTypeCtxt ty (tc_infer_lhs_type ty)
---------------------------
tcCheckHsTypeAndGen :: HsType Name -> Kind -> TcM Type
-- Input type is HsType, not LhsType; the caller adds the context
-- Typecheck a type signature, and kind-generalise it
-- The result is not necessarily zonked, and has not been checked for validity
tcCheckHsTypeAndGen hs_ty kind
= do { ty <- tc_hs_type hs_ty (EK kind expectedKindMsg)
; traceTc "tcCheckHsTypeAndGen" (ppr hs_ty)
; traceTc "tcCheckHsTypeAndGen" (ppr ty)
; kvs <- zonkTcTypeAndFV ty
; kvs <- kindGeneralize kvs
; return (mkForAllTys kvs ty) }
\end{code}
Like tcExpr, tc_hs_type takes an expected kind which it unifies with
the kind it figures out. When we don't know what kind to expect, we use
tc_lhs_type_fresh, to first create a new meta kind variable and use that as
the expected kind.
\begin{code}
tc_infer_lhs_type :: LHsType Name -> TcM (TcType, TcKind)
tc_infer_lhs_type ty =
do { kv <- newMetaKindVar
; r <- tc_lhs_type ty (EK kv expectedKindMsg)
; return (r, kv) }
tc_lhs_type :: LHsType Name -> ExpKind -> TcM TcType
tc_lhs_type (L span ty) exp_kind
= setSrcSpan span $
do { traceTc "tc_lhs_type:" (ppr ty $$ ppr exp_kind)
; tc_hs_type ty exp_kind }
tc_lhs_types :: [(LHsType Name, ExpKind)] -> TcM [TcType]
tc_lhs_types tys_w_kinds = mapM (uncurry tc_lhs_type) tys_w_kinds
------------------------------------------
tc_fun_type :: HsType Name -> LHsType Name -> LHsType Name -> ExpKind -> TcM TcType
-- We need to recognise (->) so that we can construct a FunTy,
-- *and* we need to do by looking at the Name, not the TyCon
-- (see Note [Zonking inside the knot]). For example,
-- consider f :: (->) Int Int (Trac #7312)
tc_fun_type ty ty1 ty2 exp_kind@(EK _ ctxt)
= do { ty1' <- tc_lhs_type ty1 (EK openTypeKind ctxt)
; ty2' <- tc_lhs_type ty2 (EK openTypeKind ctxt)
; checkExpectedKind ty liftedTypeKind exp_kind
; return (mkFunTy ty1' ty2') }
------------------------------------------
tc_hs_type :: HsType Name -> ExpKind -> TcM TcType
tc_hs_type (HsParTy ty) exp_kind = tc_lhs_type ty exp_kind
tc_hs_type (HsDocTy ty _) exp_kind = tc_lhs_type ty exp_kind
tc_hs_type (HsQuasiQuoteTy {}) _ = panic "tc_hs_type: qq" -- Eliminated by renamer
tc_hs_type ty@(HsBangTy {}) _
-- 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)
= failWithTc (ptext (sLit "Unexpected strictness annotation:") <+> ppr ty)
tc_hs_type (HsRecTy _) _ = panic "tc_hs_type: record" -- Unwrapped by con decls
-- Record types (which only show up temporarily in constructor
-- signatures) should have been removed by now
---------- Functions and applications
tc_hs_type hs_ty@(HsTyVar name) exp_kind
= do { (ty, k) <- tcTyVar name
; checkExpectedKind hs_ty k exp_kind
; return ty }
tc_hs_type ty@(HsFunTy ty1 ty2) exp_kind
= tc_fun_type ty ty1 ty2 exp_kind
tc_hs_type hs_ty@(HsOpTy ty1 (_, l_op@(L _ op)) ty2) exp_kind
| op `hasKey` funTyConKey
= tc_fun_type hs_ty ty1 ty2 exp_kind
| otherwise
= do { (op', op_kind) <- tcTyVar op
; tys' <- tcCheckApps hs_ty l_op op_kind [ty1,ty2] exp_kind
; return (mkNakedAppTys op' tys') }
-- mkNakedAppTys: see Note [Zonking inside the knot]
tc_hs_type hs_ty@(HsAppTy ty1 ty2) exp_kind
-- | L _ (HsTyVar fun) <- fun_ty
-- , fun `hasKey` funTyConKey
-- , [fty1,fty2] <- arg_tys
-- = tc_fun_type hs_ty fty1 fty2 exp_kind
-- | otherwise
= do { (fun_ty', fun_kind) <- tc_infer_lhs_type fun_ty
; arg_tys' <- tcCheckApps hs_ty fun_ty fun_kind arg_tys exp_kind
; return (mkNakedAppTys fun_ty' arg_tys') }
-- mkNakedAppTys: see Note [Zonking inside the knot]
-- This looks fragile; how do we *know* that fun_ty isn't
-- a TyConApp, say (which is never supposed to appear in the
-- function position of an AppTy)?
where
(fun_ty, arg_tys) = splitHsAppTys ty1 [ty2]
--------- Foralls
tc_hs_type hs_ty@(HsForAllTy _ hs_tvs context ty) exp_kind
= tcHsTyVarBndrs hs_tvs $ \ tvs' ->
-- Do not kind-generalise here! See Note [Kind generalisation]
do { ctxt' <- tcHsContext context
; ty' <- if null (unLoc context) then -- Plain forall, no context
tc_lhs_type ty exp_kind -- Why exp_kind? See Note [Body kind of forall]
else
-- If there is a context, then this forall is really a
-- _function_, so the kind of the result really is *
-- The body kind (result of the function can be * or #, hence ekOpen
do { checkExpectedKind hs_ty liftedTypeKind exp_kind
; tc_lhs_type ty ekOpen }
; return (mkSigmaTy tvs' ctxt' ty') }
--------- Lists, arrays, and tuples
tc_hs_type hs_ty@(HsListTy elt_ty) exp_kind
= do { tau_ty <- tc_lhs_type elt_ty ekLifted
; checkExpectedKind hs_ty liftedTypeKind exp_kind
; checkWiredInTyCon listTyCon
; return (mkListTy tau_ty) }
tc_hs_type hs_ty@(HsPArrTy elt_ty) exp_kind
= do { tau_ty <- tc_lhs_type elt_ty ekLifted
; checkExpectedKind hs_ty liftedTypeKind exp_kind
; checkWiredInTyCon parrTyCon
; return (mkPArrTy tau_ty) }
-- See Note [Distinguishing tuple kinds] in HsTypes
-- See Note [Inferring tuple kinds]
tc_hs_type hs_ty@(HsTupleTy HsBoxedOrConstraintTuple tys) exp_kind@(EK exp_k _ctxt)
-- (NB: not zonking before looking at exp_k, to avoid left-right bias)
| isConstraintKind exp_k = tc_tuple hs_ty HsConstraintTuple tys exp_kind
| isLiftedTypeKind exp_k = tc_tuple hs_ty HsBoxedTuple tys exp_kind
| otherwise
= do { k <- newMetaKindVar
; (msgs, mb_tau_tys) <- tryTc (tc_hs_arg_tys (ptext (sLit "a tuple")) tys (repeat k))
; k <- zonkTcKind k
-- Do the experiment inside a 'tryTc' because errors can be
-- confusing. Eg Trac #7410 (Either Int, Int), we do not want to get
-- an error saying "the second argument of a tuple should have kind *->*"
; case mb_tau_tys of
Just tau_tys
| not (isEmptyMessages msgs) -> try_again k
| isConstraintKind k -> go_for HsConstraintTuple tau_tys
| isLiftedTypeKind k -> go_for HsBoxedTuple tau_tys
| otherwise -> try_again k
Nothing -> try_again k }
where
go_for sort tau_tys = finish_tuple hs_ty sort tau_tys exp_kind
try_again k
| isConstraintKind k = tc_tuple hs_ty HsConstraintTuple tys exp_kind
| otherwise = tc_tuple hs_ty HsBoxedTuple tys exp_kind
-- It's not clear what the kind is, so make best guess and
-- check the arguments again to give good error messages
-- in eg. `(Maybe, Maybe)`
tc_hs_type hs_ty@(HsTupleTy tup_sort tys) exp_kind
= tc_tuple hs_ty tup_sort tys exp_kind
--------- Promoted lists and tuples
tc_hs_type hs_ty@(HsExplicitListTy _k tys) exp_kind
= do { tks <- mapM tc_infer_lhs_type tys
; let taus = map fst tks
; kind <- unifyKinds (ptext (sLit "In a promoted list")) tks
; checkExpectedKind hs_ty (mkPromotedListTy kind) exp_kind
; return (foldr (mk_cons kind) (mk_nil kind) taus) }
where
mk_cons k a b = mkTyConApp (promoteDataCon consDataCon) [k, a, b]
mk_nil k = mkTyConApp (promoteDataCon nilDataCon) [k]
tc_hs_type hs_ty@(HsExplicitTupleTy _ tys) exp_kind
= do { tks <- mapM tc_infer_lhs_type tys
; let n = length tys
kind_con = promotedTupleTyCon BoxedTuple n
ty_con = promotedTupleDataCon BoxedTuple n
(taus, ks) = unzip tks
tup_k = mkTyConApp kind_con ks
; checkExpectedKind hs_ty tup_k exp_kind
; return (mkTyConApp ty_con (ks ++ taus)) }
--------- Constraint types
tc_hs_type ipTy@(HsIParamTy n ty) exp_kind
= do { ty' <- tc_lhs_type ty ekLifted
; checkExpectedKind ipTy constraintKind exp_kind
; ipClass <- tcLookupClass ipClassName
; let n' = mkStrLitTy $ hsIPNameFS n
; return (mkClassPred ipClass [n',ty'])
}
tc_hs_type ty@(HsEqTy ty1 ty2) exp_kind
= do { (ty1', kind1) <- tc_infer_lhs_type ty1
; (ty2', kind2) <- tc_infer_lhs_type ty2
; checkExpectedKind ty2 kind2
(EK kind1 msg_fn)
; checkExpectedKind ty constraintKind exp_kind
; return (mkNakedTyConApp eqTyCon [kind1, ty1', ty2']) }
where
msg_fn pkind = ptext (sLit "The left argument of the equality had kind")
<+> quotes (pprKind pkind)
--------- Misc
tc_hs_type (HsKindSig ty sig_k) exp_kind
= do { sig_k' <- tcLHsKind sig_k
; checkExpectedKind ty sig_k' exp_kind
; tc_lhs_type ty (EK sig_k' msg_fn) }
where
msg_fn pkind = ptext (sLit "The signature specified kind")
<+> quotes (pprKind pkind)
tc_hs_type (HsCoreTy ty) exp_kind
= do { checkExpectedKind ty (typeKind ty) exp_kind
; return ty }
#ifdef GHCI /* Only if bootstrapped */
-- This looks highly suspect to me
-- It will really only be fixed properly when we do the TH
-- reorganisation so that type splices happen in the renamer
tc_hs_type hs_ty@(HsSpliceTy sp fvs _) exp_kind
= do { s <- getStage
; traceTc "tc_hs_type: splice" (ppr sp $$ ppr s)
; (ty, kind) <- tcSpliceType sp fvs
; checkExpectedKind hs_ty kind exp_kind
-- -- See Note [Kind of a type splice]
; return ty }
#else
tc_hs_type ty@(HsSpliceTy {}) _exp_kind
= failWithTc (ptext (sLit "Unexpected type splice:") <+> ppr ty)
#endif
tc_hs_type (HsWrapTy {}) _exp_kind
= panic "tc_hs_type HsWrapTy" -- We kind checked something twice
tc_hs_type hs_ty@(HsTyLit (HsNumTy n)) exp_kind
= do { checkExpectedKind hs_ty typeNatKind exp_kind
; checkWiredInTyCon typeNatKindCon
; return (mkNumLitTy n) }
tc_hs_type hs_ty@(HsTyLit (HsStrTy s)) exp_kind
= do { checkExpectedKind hs_ty typeSymbolKind exp_kind
; checkWiredInTyCon typeSymbolKindCon
; return (mkStrLitTy s) }
---------------------------
tc_tuple :: HsType Name -> HsTupleSort -> [LHsType Name] -> ExpKind -> TcM TcType
-- Invariant: tup_sort is not HsBoxedOrConstraintTuple
tc_tuple hs_ty tup_sort tys exp_kind
= do { tau_tys <- tc_hs_arg_tys cxt_doc tys (repeat arg_kind)
; finish_tuple hs_ty tup_sort tau_tys exp_kind }
where
arg_kind = case tup_sort of
HsBoxedTuple -> liftedTypeKind
HsUnboxedTuple -> openTypeKind
HsConstraintTuple -> constraintKind
_ -> panic "tc_hs_type arg_kind"
cxt_doc = case tup_sort of
HsBoxedTuple -> ptext (sLit "a tuple")
HsUnboxedTuple -> ptext (sLit "an unboxed tuple")
HsConstraintTuple -> ptext (sLit "a constraint tuple")
_ -> panic "tc_hs_type tup_sort"
finish_tuple :: HsType Name -> HsTupleSort -> [TcType] -> ExpKind -> TcM TcType
finish_tuple hs_ty tup_sort tau_tys exp_kind
= do { checkExpectedKind hs_ty res_kind exp_kind
; checkWiredInTyCon tycon
; return (mkTyConApp tycon tau_tys) }
where
tycon = tupleTyCon con (length tau_tys)
con = case tup_sort of
HsUnboxedTuple -> UnboxedTuple
HsBoxedTuple -> BoxedTuple
HsConstraintTuple -> ConstraintTuple
_ -> panic "tc_hs_type HsTupleTy"
res_kind = case tup_sort of
HsUnboxedTuple -> unliftedTypeKind
HsBoxedTuple -> liftedTypeKind
HsConstraintTuple -> constraintKind
_ -> panic "tc_hs_type arg_kind"
---------------------------
tcInferApps :: Outputable a
=> a
-> TcKind -- Function kind
-> [LHsType Name] -- Arg types
-> TcM ([TcType], TcKind) -- Kind-checked args
tcInferApps the_fun fun_kind args
= do { (args_w_kinds, res_kind) <- splitFunKind (ppr the_fun) fun_kind args
; args' <- tc_lhs_types args_w_kinds
; return (args', res_kind) }
tcCheckApps :: Outputable a
=> HsType Name -- The type being checked (for err messages only)
-> a -- The function
-> TcKind -> [LHsType Name] -- Fun kind and arg types
-> ExpKind -- Expected kind
-> TcM [TcType]
tcCheckApps hs_ty the_fun fun_kind args exp_kind
= do { (arg_tys, res_kind) <- tcInferApps the_fun fun_kind args
; checkExpectedKind hs_ty res_kind exp_kind
; return arg_tys }
---------------------------
splitFunKind :: SDoc -> TcKind -> [b] -> TcM ([(b,ExpKind)], TcKind)
splitFunKind the_fun fun_kind args
= go 1 fun_kind args
where
go _ fk [] = return ([], fk)
go arg_no fk (arg:args)
= do { mb_fk <- matchExpectedFunKind fk
; case mb_fk of
Nothing -> failWithTc too_many_args
Just (ak,fk') -> do { (aks, rk) <- go (arg_no+1) fk' args
; let exp_kind = expArgKind (quotes the_fun) ak arg_no
; return ((arg, exp_kind) : aks, rk) } }
too_many_args = quotes the_fun <+>
ptext (sLit "is applied to too many type arguments")
---------------------------
tcHsContext :: LHsContext Name -> TcM [PredType]
tcHsContext ctxt = mapM tcHsLPredType (unLoc ctxt)
tcHsLPredType :: LHsType Name -> TcM PredType
tcHsLPredType pred = tc_lhs_type pred ekConstraint
---------------------------
tcTyVar :: Name -> TcM (TcType, TcKind)
-- See Note [Type checking recursive type and class declarations]
-- in TcTyClsDecls
tcTyVar name -- Could be a tyvar, a tycon, or a datacon
= do { traceTc "lk1" (ppr name)
; thing <- tcLookup name
; traceTc "lk2" (ppr name <+> ppr thing)
; case thing of
ATyVar _ tv
| isKindVar tv
-> failWithTc (ptext (sLit "Kind variable") <+> quotes (ppr tv)
<+> ptext (sLit "used as a type"))
| otherwise
-> return (mkTyVarTy tv, tyVarKind tv)
AThing kind -> do { tc <- get_loopy_tc name
; inst_tycon (mkNakedTyConApp tc) kind }
-- mkNakedTyConApp: see Note [Zonking inside the knot]
AGlobal (ATyCon tc) -> inst_tycon (mkTyConApp tc) (tyConKind tc)
AGlobal (ADataCon dc)
| Just tc <- promoteDataCon_maybe dc
-> do { data_kinds <- xoptM Opt_DataKinds
; unless data_kinds $ promotionErr name NoDataKinds
; inst_tycon (mkTyConApp tc) (tyConKind tc) }
| otherwise -> failWithTc (ptext (sLit "Data constructor") <+> quotes (ppr dc)
<+> ptext (sLit "comes from an un-promotable type")
<+> quotes (ppr (dataConTyCon dc)))
APromotionErr err -> promotionErr name err
_ -> wrongThingErr "type" thing name }
where
get_loopy_tc name
= do { env <- getGblEnv
; case lookupNameEnv (tcg_type_env env) name of
Just (ATyCon tc) -> return tc
_ -> return (aThingErr "tcTyVar" name) }
inst_tycon :: ([Type] -> Type) -> Kind -> TcM (Type, Kind)
-- Instantiate the polymorphic kind
-- Lazy in the TyCon
inst_tycon mk_tc_app kind
| null kvs
= return (mk_tc_app [], ki_body)
| otherwise
= do { traceTc "lk4" (ppr name <+> dcolon <+> ppr kind)
; ks <- mapM (const newMetaKindVar) kvs
; return (mk_tc_app ks, substKiWith kvs ks ki_body) }
where
(kvs, ki_body) = splitForAllTys kind
tcClass :: Name -> TcM (Class, TcKind)
tcClass cls -- Must be a class
= do { thing <- tcLookup cls
; case thing of
AThing kind -> return (aThingErr "tcClass" cls, kind)
AGlobal (ATyCon tc)
| Just cls <- tyConClass_maybe tc
-> return (cls, tyConKind tc)
_ -> wrongThingErr "class" thing cls }
aThingErr :: String -> Name -> b
-- The type checker for types is sometimes called simply to
-- do *kind* checking; and in that case it ignores the type
-- returned. Which is a good thing since it may not be available yet!
aThingErr str x = pprPanic "AThing evaluated unexpectedly" (text str <+> ppr x)
\end{code}
Note [Zonking inside the knot]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Suppose we are checking the argument types of a data constructor. We
must zonk the types before making the DataCon, because once built we
can't change it. So we must traverse the type.
BUT the parent TyCon is knot-tied, so we can't look at it yet.
So we must be careful not to use "smart constructors" for types that
look at the TyCon or Class involved.
* Hence the use of mkNakedXXX functions. These do *not* enforce
the invariants (for example that we use (FunTy s t) rather
than (TyConApp (->) [s,t])).
* Ditto in zonkTcType (which may be applied more than once, eg to
squeeze out kind meta-variables), we are careful not to look at
the TyCon.
* We arrange to call zonkSigType *once* right at the end, and it
does establish the invariants. But in exchange we can't look
at the result (not even its structure) until we have emerged
from the "knot".
* TcHsSyn.zonkTcTypeToType also can safely check/establish
invariants.
This is horribly delicate. I hate it. A good example of how
delicate it is can be seen in Trac #7903.
\begin{code}
mkNakedTyConApp :: TyCon -> [Type] -> Type
-- Builds a TyConApp
-- * without being strict in TyCon,
-- * without satisfying the invariants of TyConApp
-- A subsequent zonking will establish the invariants
mkNakedTyConApp tc tys = TyConApp tc tys
mkNakedAppTys :: Type -> [Type] -> Type
mkNakedAppTys ty1 [] = ty1
mkNakedAppTys (TyConApp tc tys1) tys2 = mkNakedTyConApp tc (tys1 ++ tys2)
mkNakedAppTys ty1 tys2 = foldl AppTy ty1 tys2
zonkSigType :: TcType -> TcM TcType
-- Zonk the result of type-checking a user-written type signature
-- It may have kind varaibles in it, but no meta type variables
-- Because of knot-typing (see Note [Zonking inside the knot])
-- it may need to establish the Type invariants;
-- hence the use of mkTyConApp and mkAppTy
zonkSigType ty
= go ty
where
go (TyConApp tc tys) = do tys' <- mapM go tys
return (mkTyConApp tc tys')
-- Key point: establish Type invariants!
-- See Note [Zonking inside the knot]
go (LitTy n) = return (LitTy n)
go (FunTy arg res) = do arg' <- go arg
res' <- go res
return (FunTy arg' res')
go (AppTy fun arg) = do fun' <- go fun
arg' <- go arg
return (mkAppTy fun' arg')
-- NB the mkAppTy; we might have instantiated a
-- type variable to a type constructor, so we need
-- to pull the TyConApp to the top.
-- The two interesting cases!
go (TyVarTy tyvar) | isTcTyVar tyvar = zonkTcTyVar tyvar
| otherwise = TyVarTy <$> updateTyVarKindM go tyvar
-- Ordinary (non Tc) tyvars occur inside quantified types
go (ForAllTy tv ty) = do { tv' <- zonkTcTyVarBndr tv
; ty' <- go ty
; return (ForAllTy tv' ty') }
\end{code}
Note [Body kind of a forall]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The body of a forall is usually a type, but in principle
there's no reason to prohibit *unlifted* types.
In fact, GHC can itself construct a function with an
unboxed tuple inside a for-all (via CPR analyis; see
typecheck/should_compile/tc170).
Moreover in instance heads we get forall-types with
kind Constraint.
Moreover if we have a signature
f :: Int#
then we represent it as (HsForAll Implicit [] [] Int#). And this must
be legal! We can't drop the empty forall until *after* typechecking
the body because of kind polymorphism:
Typeable :: forall k. k -> Constraint
data Apply f t = Apply (f t)
-- Apply :: forall k. (k -> *) -> k -> *
instance Typeable Apply where ...
Then the dfun has type
df :: forall k. Typeable ((k->*) -> k -> *) (Apply k)
f :: Typeable Apply
f :: forall (t:k->*) (a:k). t a -> t a
class C a b where
op :: a b -> Typeable Apply
data T a = MkT (Typeable Apply)
| T2 a
T :: * -> *
MkT :: forall k. (Typeable ((k->*) -> k -> *) (Apply k)) -> T a
f :: (forall (k:BOX). forall (t:: k->*) (a:k). t a -> t a) -> Int
f :: (forall a. a -> Typeable Apply) -> Int
So we *must* keep the HsForAll on the instance type
HsForAll Implicit [] [] (Typeable Apply)
so that we do kind generalisation on it.
Really we should check that it's a type of value kind
{*, Constraint, #}, but I'm not doing that yet
Example that should be rejected:
f :: (forall (a:*->*). a) Int
Note [Inferring tuple kinds]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Give a tuple type (a,b,c), which the parser labels as HsBoxedOrConstraintTuple,
we try to figure out whether it's a tuple of kind * or Constraint.
Step 1: look at the expected kind
Step 2: infer argument kinds
If after Step 2 it's not clear from the arguments that it's
Constraint, then it must be *. Once having decided that we re-check
the Check the arguments again to give good error messages
in eg. `(Maybe, Maybe)`
Note that we will still fail to infer the correct kind in this case:
type T a = ((a,a), D a)
type family D :: Constraint -> Constraint
While kind checking T, we do not yet know the kind of D, so we will default the
kind of T to * -> *. It works if we annotate `a` with kind `Constraint`.
Note [Desugaring types]
~~~~~~~~~~~~~~~~~~~~~~~
The type desugarer is phase 2 of dealing with HsTypes. Specifically:
* It transforms from HsType to Type
* It zonks any kinds. The returned type should have no mutable kind
or type variables (hence returning Type not TcType):
- any unconstrained kind variables are defaulted to AnyK just
as in TcHsSyn.
- there are no mutable type variables because we are
kind-checking a type
Reason: the returned type may be put in a TyCon or DataCon where
it will never subsequently be zonked.
You might worry about nested scopes:
..a:kappa in scope..
let f :: forall b. T '[a,b] -> Int
In this case, f's type could have a mutable kind variable kappa in it;
and we might then default it to AnyK when dealing with f's type
signature. But we don't expect this to happen because we can't get a
lexically scoped type variable with a mutable kind variable in it. A
delicate point, this. If it becomes an issue we might need to
distinguish top-level from nested uses.
Moreover
* it cannot fail,
* it does no unifications
* it does no validity checking, except for structural matters, such as
(a) spurious ! annotations.
(b) a class used as a type
Note [Kind of a type splice]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider these terms, each with TH type splice inside:
[| e1 :: Maybe $(..blah..) |]
[| e2 :: $(..blah..) |]
When kind-checking the type signature, we'll kind-check the splice
$(..blah..); we want to give it a kind that can fit in any context,
as if $(..blah..) :: forall k. k.
In the e1 example, the context of the splice fixes kappa to *. But
in the e2 example, we'll desugar the type, zonking the kind unification
variables as we go. When we encournter the unconstrained kappa, we
want to default it to '*', not to AnyK.
Help functions for type applications
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\begin{code}
addTypeCtxt :: LHsType Name -> TcM a -> TcM a
-- Wrap a context around only if we want to show that contexts.
-- Omit invisble ones and ones user's won't grok
addTypeCtxt (L _ ty) thing
= addErrCtxt doc thing
where
doc = ptext (sLit "In the type") <+> quotes (ppr ty)
\end{code}
%************************************************************************
%* *
Type-variable binders
%* *
%************************************************************************
Note [Kind-checking kind-polymorphic types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider:
f :: forall (f::k -> *) a. f a -> Int
Here, the [LHsTyVarBndr Name] of the forall type will be [f,a], where
a is a UserTyVar -> type variable without kind annotation
f is a KindedTyVar -> type variable with kind annotation
If were were to allow binding sites for kind variables, thus
f :: forall @k (f :: k -> *) a. f a -> Int
then we'd also need
k is a UserKiVar -> kind variable (they don't need annotation,
since we only have BOX for a super kind)
Note [Kind-checking strategies]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
There are three main declarations that we have to kind check carefully in the
presence of -XPolyKinds: classes, datatypes, and data/type families. They each
have a different kind-checking strategy (labeled in the parentheses above each
section). This should potentially be cleaned up in the future, but this is how
it stands now (June 2013).
Classes (ParametricKinds):
- kind-polymorphic by default
- each un-annotated type variable is given a fresh meta kind variable
- every explicit kind variable becomes a SigTv during inference
- no generalisation is done while kind-checking the recursive group
Taken together, this means that classes cannot participate in polymorphic
recursion. Thus, the following is not definable:
class Fugly (a :: k) where
foo :: forall (b :: k -> *). Fugly b => b a
But, because explicit kind variables are SigTvs, it is OK for the kind to
be forced to be the same kind that is used in a separate declaration. See
test case polykinds/T7020.hs.
Datatypes:
Here we have two cases, whether or not a Full Kind Signature is provided.
A Full Kind Signature means that there is a top-level :: in the definition
of the datatype. For example:
data T1 :: k -> Bool -> * where ... -- YES
data T2 (a :: k) :: Bool -> * where ... -- YES
data T3 (a :: k) (b :: Bool) :: * where ... -- YES
data T4 (a :: k) (b :: Bool) where ... -- NO
Kind signatures are not allowed on datatypes declared in the H98 style,
so those always have no Full Kind Signature.
Full Kind Signature (FullKindSignature):
- each un-annotated type variable defaults to *
- every explicit kind variable becomes a skolem during type inference
- these kind variables are generalised *before* kind-checking the group
With these rules, polymorphic recursion is possible. This is essentially
because of the generalisation step before kind-checking the group -- it
gives the kind-checker enough flexibility to supply the right kind arguments
to support polymorphic recursion.
no Full Kind Signature (ParametricKinds):
- kind-polymorphic by default
- each un-annotated type variable is given a fresh meta kind variable
- every explicit kind variable becomes a SigTv during inference
- no generalisation is done while kind-checking the recursive group
Thus, no polymorphic recursion in this case. See also Trac #6093 & #6049.
Type families:
Here we have three cases: open top-level families, closed top-level families,
and open associated types. (There are no closed associated types, for good
reason.)
Open top-level families (FullKindSignature):
- All open top-level families are considered to have a Full Kind Signature
- All arguments and the result default to *
- All kind variables are skolems
- All kind variables are generalised before kind-checking the group
This behaviour supports kind-indexed type and data families, because we
need to have generalised before kind-checking for this to work. For example:
type family F (a :: k)
type instance F Int = Bool
type instance F Maybe = Char
type instance F (x :: * -> * -> *) = Double