2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
5 \section[TypeRep]{Type - friends' interface}
11 PredType(..), -- to friends
13 Kind, ThetaType, -- Synonyms
18 pprType, pprParendType, pprTypeApp,
19 pprTyThing, pprTyThingCategory,
20 pprPred, pprTheta, pprForAll, pprThetaArrow, pprClassPred,
23 liftedTypeKind, unliftedTypeKind, openTypeKind,
24 argTypeKind, ubxTupleKind,
25 isLiftedTypeKindCon, isLiftedTypeKind,
26 mkArrowKind, mkArrowKinds, isCoercionKind,
29 -- Kind constructors...
30 liftedTypeKindTyCon, openTypeKindTyCon, unliftedTypeKindTyCon,
31 argTypeKindTyCon, ubxTupleKindTyCon,
34 unliftedTypeKindTyConName, openTypeKindTyConName,
35 ubxTupleKindTyConName, argTypeKindTyConName,
36 liftedTypeKindTyConName,
39 tySuperKind, coSuperKind,
40 isTySuperKind, isCoSuperKind,
41 tySuperKindTyCon, coSuperKindTyCon,
43 pprKind, pprParendKind
46 #include "HsVersions.h"
48 import {-# SOURCE #-} DataCon( DataCon, dataConName )
64 %************************************************************************
66 \subsection{Type Classifications}
68 %************************************************************************
72 *unboxed* iff its representation is other than a pointer
73 Unboxed types are also unlifted.
75 *lifted* A type is lifted iff it has bottom as an element.
76 Closures always have lifted types: i.e. any
77 let-bound identifier in Core must have a lifted
78 type. Operationally, a lifted object is one that
81 Only lifted types may be unified with a type variable.
83 *algebraic* A type with one or more constructors, whether declared
84 with "data" or "newtype".
85 An algebraic type is one that can be deconstructed
86 with a case expression.
87 *NOT* the same as lifted types, because we also
88 include unboxed tuples in this classification.
90 *data* A type declared with "data". Also boxed tuples.
92 *primitive* iff it is a built-in type that can't be expressed
95 Currently, all primitive types are unlifted, but that's not necessarily
96 the case. (E.g. Int could be primitive.)
98 Some primitive types are unboxed, such as Int#, whereas some are boxed
99 but unlifted (such as ByteArray#). The only primitive types that we
100 classify as algebraic are the unboxed tuples.
102 examples of type classifications:
104 Type primitive boxed lifted algebraic
105 -----------------------------------------------------------------------------
107 ByteArray# Yes Yes No No
108 (# a, b #) Yes No No Yes
109 ( a, b ) No Yes Yes Yes
114 ----------------------
115 A note about newtypes
116 ----------------------
121 Then we want N to be represented as an Int, and that's what we arrange.
122 The front end of the compiler [TcType.lhs] treats N as opaque,
123 the back end treats it as transparent [Type.lhs].
125 There's a bit of a problem with recursive newtypes
127 newtype Q = MkQ (Q->Q)
129 Here the 'implicit expansion' we get from treating P and Q as transparent
130 would give rise to infinite types, which in turn makes eqType diverge.
131 Similarly splitForAllTys and splitFunTys can get into a loop.
135 * Newtypes are always represented using TyConApp.
137 * For non-recursive newtypes, P, treat P just like a type synonym after
138 type-checking is done; i.e. it's opaque during type checking (functions
139 from TcType) but transparent afterwards (functions from Type).
140 "Treat P as a type synonym" means "all functions expand NewTcApps
143 Applications of the data constructor P simply vanish:
147 * For recursive newtypes Q, treat the Q and its representation as
148 distinct right through the compiler. Applications of the data consructor
150 Q = \(x::Q->Q). coerce Q x
151 They are rare, so who cares if they are a tiny bit less efficient.
153 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
154 to cut all loops. The other members of the loop may be marked 'non-recursive'.
157 %************************************************************************
159 \subsection{The data type}
161 %************************************************************************
169 Type -- Function is *not* a TyConApp
170 Type -- It must be another AppTy, or TyVarTy
172 | TyConApp -- Application of a TyCon, including newtypes *and* synonyms
173 TyCon -- *Invariant* saturated appliations of FunTyCon and
174 -- synonyms have their own constructors, below.
175 -- However, *unsaturated* FunTyCons do appear as TyConApps.
177 [Type] -- Might not be saturated.
178 -- Even type synonyms are not necessarily saturated;
179 -- for example unsaturated type synonyms can appear as the
180 -- RHS of a type synonym.
182 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
186 | ForAllTy -- A polymorphic type
190 | PredTy -- The type of evidence for a type predictate
191 PredType -- See Note [PredTy], and Note [Equality predicates]
192 -- NB: A PredTy (EqPred _ _) can appear only as the kind
193 -- of a coercion variable; never as the argument or result
194 -- of a FunTy (unlike ClassP, IParam)
196 type Kind = Type -- Invariant: a kind is always
198 -- or TyConApp PrimTyCon [...]
199 -- or TyVar kv (during inference only)
200 -- or ForAll ... (for top-level coercions)
202 type SuperKind = Type -- Invariant: a super kind is always
203 -- TyConApp SuperKindTyCon ...
206 -------------------------------------
211 represents a value whose type is the Haskell predicate p,
212 where a predicate is what occurs before the '=>' in a Haskell type.
213 It can be expanded into its representation, but:
215 * The type checker must treat it as opaque
216 * The rest of the compiler treats it as transparent
218 Consider these examples:
219 f :: (Eq a) => a -> Int
220 g :: (?x :: Int -> Int) => a -> Int
221 h :: (r\l) => {r} => {l::Int | r}
223 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
224 Predicates are represented inside GHC by PredType:
228 = ClassP Class [Type] -- Class predicate
229 | IParam (IPName Name) Type -- Implicit parameter
230 | EqPred Type Type -- Equality predicate (ty1 ~ ty2)
232 type ThetaType = [PredType]
235 (We don't support TREX records yet, but the setup is designed
236 to expand to allow them.)
238 A Haskell qualified type, such as that for f,g,h above, is
240 * a FunTy for the double arrow
241 * with a PredTy as the function argument
243 The predicate really does turn into a real extra argument to the
244 function. If the argument has type (PredTy p) then the predicate p is
245 represented by evidence (a dictionary, for example, of type (predRepTy p).
247 Note [Equality predicates]
248 ~~~~~~~~~~~~~~~~~~~~~~~~~~
249 forall a b. (a ~ S b) => a -> b
250 could be represented by
251 ForAllTy a (ForAllTy b (FunTy (PredTy (EqPred a (S b))) ...))
253 ForAllTy a (ForAllTy b (ForAllTy (c::PredTy (EqPred a (S b))) ...))
255 The latter is what we do. (Unlike for class and implicit parameter
256 constraints, which do use FunTy.)
259 * FunTy is always a *value* function
260 * ForAllTy is discarded at runtime
262 We often need to make a "wildcard" (c::PredTy..). We always use the same
263 name (wildCoVarName), since it's not mentioned.
266 %************************************************************************
270 %************************************************************************
272 Despite the fact that DataCon has to be imported via a hi-boot route,
273 this module seems the right place for TyThing, because it's needed for
274 funTyCon and all the types in TysPrim.
277 data TyThing = AnId Id
282 instance Outputable TyThing where
285 pprTyThing :: TyThing -> SDoc
286 pprTyThing thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
288 pprTyThingCategory :: TyThing -> SDoc
289 pprTyThingCategory (ATyCon _) = ptext (sLit "Type constructor")
290 pprTyThingCategory (AClass _) = ptext (sLit "Class")
291 pprTyThingCategory (AnId _) = ptext (sLit "Identifier")
292 pprTyThingCategory (ADataCon _) = ptext (sLit "Data constructor")
294 instance NamedThing TyThing where -- Can't put this with the type
295 getName (AnId id) = getName id -- decl, because the DataCon instance
296 getName (ATyCon tc) = getName tc -- isn't visible there
297 getName (AClass cl) = getName cl
298 getName (ADataCon dc) = dataConName dc
302 %************************************************************************
304 Wired-in type constructors
306 %************************************************************************
308 We define a few wired-in type constructors here to avoid module knots
311 --------------------------
312 -- First the TyCons...
314 funTyCon, tySuperKindTyCon, coSuperKindTyCon, liftedTypeKindTyCon,
315 openTypeKindTyCon, unliftedTypeKindTyCon,
316 ubxTupleKindTyCon, argTypeKindTyCon
318 funTyConName, tySuperKindTyConName, coSuperKindTyConName, liftedTypeKindTyConName,
319 openTypeKindTyConName, unliftedTypeKindTyConName,
320 ubxTupleKindTyConName, argTypeKindTyConName
323 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
324 -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
325 -- But if we do that we get kind errors when saying
326 -- instance Control.Arrow (->)
327 -- becuase the expected kind is (*->*->*). The trouble is that the
328 -- expected/actual stuff in the unifier does not go contra-variant, whereas
329 -- the kind sub-typing does. Sigh. It really only matters if you use (->) in
330 -- a prefix way, thus: (->) Int# Int#. And this is unusual.
333 tySuperKindTyCon = mkSuperKindTyCon tySuperKindTyConName
334 coSuperKindTyCon = mkSuperKindTyCon coSuperKindTyConName
336 liftedTypeKindTyCon = mkKindTyCon liftedTypeKindTyConName
337 openTypeKindTyCon = mkKindTyCon openTypeKindTyConName
338 unliftedTypeKindTyCon = mkKindTyCon unliftedTypeKindTyConName
339 ubxTupleKindTyCon = mkKindTyCon ubxTupleKindTyConName
340 argTypeKindTyCon = mkKindTyCon argTypeKindTyConName
342 mkKindTyCon :: Name -> TyCon
343 mkKindTyCon name = mkVoidPrimTyCon name tySuperKind 0
345 --------------------------
346 -- ... and now their names
348 tySuperKindTyConName = mkPrimTyConName (fsLit "BOX") tySuperKindTyConKey tySuperKindTyCon
349 coSuperKindTyConName = mkPrimTyConName (fsLit "COERCION") coSuperKindTyConKey coSuperKindTyCon
350 liftedTypeKindTyConName = mkPrimTyConName (fsLit "*") liftedTypeKindTyConKey liftedTypeKindTyCon
351 openTypeKindTyConName = mkPrimTyConName (fsLit "?") openTypeKindTyConKey openTypeKindTyCon
352 unliftedTypeKindTyConName = mkPrimTyConName (fsLit "#") unliftedTypeKindTyConKey unliftedTypeKindTyCon
353 ubxTupleKindTyConName = mkPrimTyConName (fsLit "(#)") ubxTupleKindTyConKey ubxTupleKindTyCon
354 argTypeKindTyConName = mkPrimTyConName (fsLit "??") argTypeKindTyConKey argTypeKindTyCon
355 funTyConName = mkPrimTyConName (fsLit "(->)") funTyConKey funTyCon
357 mkPrimTyConName :: FastString -> Unique -> TyCon -> Name
358 mkPrimTyConName occ key tycon = mkWiredInName gHC_PRIM (mkOccNameFS tcName occ)
362 -- All of the super kinds and kinds are defined in Prim and use BuiltInSyntax,
363 -- because they are never in scope in the source
366 -- We also need Kinds and SuperKinds, locally and in TyCon
368 kindTyConType :: TyCon -> Type
369 kindTyConType kind = TyConApp kind []
371 liftedTypeKind, unliftedTypeKind, openTypeKind, argTypeKind, ubxTupleKind :: Kind
373 liftedTypeKind = kindTyConType liftedTypeKindTyCon
374 unliftedTypeKind = kindTyConType unliftedTypeKindTyCon
375 openTypeKind = kindTyConType openTypeKindTyCon
376 argTypeKind = kindTyConType argTypeKindTyCon
377 ubxTupleKind = kindTyConType ubxTupleKindTyCon
379 mkArrowKind :: Kind -> Kind -> Kind
380 mkArrowKind k1 k2 = FunTy k1 k2
382 mkArrowKinds :: [Kind] -> Kind -> Kind
383 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
385 tySuperKind, coSuperKind :: SuperKind
386 tySuperKind = kindTyConType tySuperKindTyCon
387 coSuperKind = kindTyConType coSuperKindTyCon
389 isTySuperKind :: SuperKind -> Bool
390 isTySuperKind (TyConApp kc []) = kc `hasKey` tySuperKindTyConKey
391 isTySuperKind _ = False
393 isCoSuperKind :: SuperKind -> Bool
394 isCoSuperKind (TyConApp kc []) = kc `hasKey` coSuperKindTyConKey
395 isCoSuperKind _ = False
398 -- Lastly we need a few functions on Kinds
400 isLiftedTypeKindCon :: TyCon -> Bool
401 isLiftedTypeKindCon tc = tc `hasKey` liftedTypeKindTyConKey
403 isLiftedTypeKind :: Kind -> Bool
404 isLiftedTypeKind (TyConApp tc []) = isLiftedTypeKindCon tc
405 isLiftedTypeKind _ = False
407 isCoercionKind :: Kind -> Bool
408 -- All coercions are of form (ty1 ~ ty2)
409 -- This function is here rather than in Coercion,
410 -- because it's used in a knot-tied way to enforce invariants in Var
411 isCoercionKind (PredTy (EqPred {})) = True
412 isCoercionKind _ = False
414 coVarPred :: CoVar -> PredType
416 = ASSERT( isCoVar tv )
419 other -> pprPanic "coVarPred" (ppr tv $$ ppr other)
424 %************************************************************************
426 \subsection{The external interface}
428 %************************************************************************
430 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
431 defined to use this. @pprParendType@ is the same, except it puts
432 parens around the type, except for the atomic cases. @pprParendType@
433 works just by setting the initial context precedence very high.
436 data Prec = TopPrec -- No parens
437 | FunPrec -- Function args; no parens for tycon apps
438 | TyConPrec -- Tycon args; no parens for atomic
441 maybeParen :: Prec -> Prec -> SDoc -> SDoc
442 maybeParen ctxt_prec inner_prec pretty
443 | ctxt_prec < inner_prec = pretty
444 | otherwise = parens pretty
447 pprType, pprParendType :: Type -> SDoc
448 pprType ty = ppr_type TopPrec ty
449 pprParendType ty = ppr_type TyConPrec ty
451 pprTypeApp :: NamedThing a => a -> SDoc -> [Type] -> SDoc
452 -- The first arg is the tycon; it's used to arrange printing infix
453 -- if it looks like an operator
454 -- Second arg is the pretty-printed tycon
455 pprTypeApp tc pp_tc tys = ppr_type_app TopPrec (getName tc) pp_tc tys
458 pprPred :: PredType -> SDoc
459 pprPred (ClassP cls tys) = pprClassPred cls tys
460 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
461 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext (sLit "~")), ppr ty2]
462 pprClassPred :: Class -> [Type] -> SDoc
463 pprClassPred clas tys = ppr_type_app TopPrec (getName clas) (ppr clas) tys
465 pprTheta :: ThetaType -> SDoc
466 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
468 pprThetaArrow :: ThetaType -> SDoc
471 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext (sLit "=>")
474 instance Outputable Type where
477 instance Outputable PredType where
480 instance Outputable name => OutputableBndr (IPName name) where
481 pprBndr _ n = ppr n -- Simple for now
484 -- OK, here's the main printer
486 pprKind, pprParendKind :: Kind -> SDoc
488 pprParendKind = pprParendType
490 ppr_type :: Prec -> Type -> SDoc
491 ppr_type _ (TyVarTy tv) = ppr tv
492 ppr_type _ (PredTy pred) = ifPprDebug (ptext (sLit "<pred>")) <> (ppr pred)
493 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
495 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
496 pprType t1 <+> ppr_type TyConPrec t2
498 ppr_type p ty@(ForAllTy _ _) = ppr_forall_type p ty
499 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
501 ppr_type p (FunTy ty1 ty2)
502 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
503 maybeParen p FunPrec $
504 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
506 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
507 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
509 ppr_forall_type :: Prec -> Type -> SDoc
511 = maybeParen p FunPrec $
512 sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
514 (tvs, rho) = split1 [] ty
515 (ctxt, tau) = split2 [] rho
517 -- We need to be extra careful here as equality constraints will occur as
518 -- type variables with an equality kind. So, while collecting quantified
519 -- variables, we separate the coercion variables out and turn them into
520 -- equality predicates.
521 split1 tvs (ForAllTy tv ty)
522 | not (isCoVar tv) = split1 (tv:tvs) ty
523 split1 tvs ty = (reverse tvs, ty)
525 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
526 split2 ps (ForAllTy tv ty)
527 | isCoVar tv = split2 (coVarPred tv : ps) ty
528 split2 ps ty = (reverse ps, ty)
530 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
534 | tc `hasKey` listTyConKey = brackets (pprType ty)
535 | tc `hasKey` parrTyConKey = ptext (sLit "[:") <> pprType ty <> ptext (sLit ":]")
536 | tc `hasKey` liftedTypeKindTyConKey = ptext (sLit "*")
537 | tc `hasKey` unliftedTypeKindTyConKey = ptext (sLit "#")
538 | tc `hasKey` openTypeKindTyConKey = ptext (sLit "(?)")
539 | tc `hasKey` ubxTupleKindTyConKey = ptext (sLit "(#)")
540 | tc `hasKey` argTypeKindTyConKey = ptext (sLit "??")
543 | isTupleTyCon tc && tyConArity tc == length tys
544 = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
546 = ppr_type_app p (getName tc) (ppr_naked_tc tc) tys
548 ppr_type_app :: Prec -> Name -> SDoc -> [Type] -> SDoc
549 ppr_type_app p tc pp_tc tys
550 | is_sym_occ -- Print infix if possible
551 , [ty1,ty2] <- tys -- We know nothing of precedence though
552 = maybeParen p FunPrec (sep [ppr_type FunPrec ty1,
553 pp_tc <+> ppr_type FunPrec ty2])
555 = maybeParen p TyConPrec (hang paren_tc 2 (sep (map pprParendType tys)))
557 is_sym_occ = isSymOcc (getOccName tc)
558 paren_tc | is_sym_occ = parens pp_tc
561 ppr_tc :: TyCon -> SDoc
562 ppr_tc tc = parenSymOcc (getOccName tc) (ppr_naked_tc tc)
564 ppr_naked_tc :: TyCon -> SDoc -- No brackets for SymOcc
566 = pp_nt_debug <> ppr tc
568 pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
569 then ptext (sLit "<recnt>")
570 else ptext (sLit "<nt>"))
574 pprForAll :: [TyVar] -> SDoc
576 pprForAll tvs = ptext (sLit "forall") <+> sep (map pprTvBndr tvs) <> dot
578 pprTvBndr :: TyVar -> SDoc
579 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
580 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)