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 -> [Type] -> SDoc
452 -- The first arg is the tycon, or sometimes class
453 -- Print infix if the tycon/class looks like an operator
454 pprTypeApp tc tys = ppr_type_app TopPrec (getName tc) tys
457 pprPred :: PredType -> SDoc
458 pprPred (ClassP cls tys) = pprClassPred cls tys
459 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
460 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext (sLit "~")), ppr ty2]
461 pprClassPred :: Class -> [Type] -> SDoc
462 pprClassPred clas tys = ppr_type_app TopPrec (getName clas) tys
464 pprTheta :: ThetaType -> SDoc
465 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
467 pprThetaArrow :: ThetaType -> SDoc
470 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext (sLit "=>")
473 instance Outputable Type where
476 instance Outputable PredType where
479 instance Outputable name => OutputableBndr (IPName name) where
480 pprBndr _ n = ppr n -- Simple for now
483 -- OK, here's the main printer
485 pprKind, pprParendKind :: Kind -> SDoc
487 pprParendKind = pprParendType
489 ppr_type :: Prec -> Type -> SDoc
490 ppr_type _ (TyVarTy tv) = ppr tv
491 ppr_type _ (PredTy pred) = ifPprDebug (ptext (sLit "<pred>")) <> (ppr pred)
492 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
494 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
495 pprType t1 <+> ppr_type TyConPrec t2
497 ppr_type p ty@(ForAllTy _ _) = ppr_forall_type p ty
498 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
500 ppr_type p (FunTy ty1 ty2)
501 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
502 maybeParen p FunPrec $
503 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
505 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
506 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
508 ppr_forall_type :: Prec -> Type -> SDoc
510 = maybeParen p FunPrec $
511 sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
513 (tvs, rho) = split1 [] ty
514 (ctxt, tau) = split2 [] rho
516 -- We need to be extra careful here as equality constraints will occur as
517 -- type variables with an equality kind. So, while collecting quantified
518 -- variables, we separate the coercion variables out and turn them into
519 -- equality predicates.
520 split1 tvs (ForAllTy tv ty)
521 | not (isCoVar tv) = split1 (tv:tvs) ty
522 split1 tvs ty = (reverse tvs, ty)
524 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
525 split2 ps (ForAllTy tv ty)
526 | isCoVar tv = split2 (coVarPred tv : ps) ty
527 split2 ps ty = (reverse ps, ty)
529 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
533 | tc `hasKey` listTyConKey = brackets (pprType ty)
534 | tc `hasKey` parrTyConKey = ptext (sLit "[:") <> pprType ty <> ptext (sLit ":]")
535 | tc `hasKey` liftedTypeKindTyConKey = ptext (sLit "*")
536 | tc `hasKey` unliftedTypeKindTyConKey = ptext (sLit "#")
537 | tc `hasKey` openTypeKindTyConKey = ptext (sLit "(?)")
538 | tc `hasKey` ubxTupleKindTyConKey = ptext (sLit "(#)")
539 | tc `hasKey` argTypeKindTyConKey = ptext (sLit "??")
542 | isTupleTyCon tc && tyConArity tc == length tys
543 = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
545 = ppr_type_app p (getName tc) tys
547 ppr_type_app :: Prec -> Name -> [Type] -> SDoc
548 -- Used for classes as well as types; that's why it's separate from ppr_tc_app
549 ppr_type_app p 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 pprInfixVar True (ppr tc) <+> ppr_type FunPrec ty2])
555 = maybeParen p TyConPrec (hang (pprPrefixVar is_sym_occ (ppr tc))
556 2 (sep (map pprParendType tys)))
558 is_sym_occ = isSymOcc (getOccName tc)
560 ppr_tc :: TyCon -> SDoc -- No brackets for SymOcc
562 = pp_nt_debug <> ppr tc
564 pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
565 then ptext (sLit "<recnt>")
566 else ptext (sLit "<nt>"))
570 pprForAll :: [TyVar] -> SDoc
572 pprForAll tvs = ptext (sLit "forall") <+> sep (map pprTvBndr tvs) <> dot
574 pprTvBndr :: TyVar -> SDoc
575 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
576 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)