2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
5 \section[TypeRep]{Type - friends' interface}
10 Type(..), TyNote(..), -- Representation visible
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 )
65 %************************************************************************
67 \subsection{Type Classifications}
69 %************************************************************************
73 *unboxed* iff its representation is other than a pointer
74 Unboxed types are also unlifted.
76 *lifted* A type is lifted iff it has bottom as an element.
77 Closures always have lifted types: i.e. any
78 let-bound identifier in Core must have a lifted
79 type. Operationally, a lifted object is one that
82 Only lifted types may be unified with a type variable.
84 *algebraic* A type with one or more constructors, whether declared
85 with "data" or "newtype".
86 An algebraic type is one that can be deconstructed
87 with a case expression.
88 *NOT* the same as lifted types, because we also
89 include unboxed tuples in this classification.
91 *data* A type declared with "data". Also boxed tuples.
93 *primitive* iff it is a built-in type that can't be expressed
96 Currently, all primitive types are unlifted, but that's not necessarily
97 the case. (E.g. Int could be primitive.)
99 Some primitive types are unboxed, such as Int#, whereas some are boxed
100 but unlifted (such as ByteArray#). The only primitive types that we
101 classify as algebraic are the unboxed tuples.
103 examples of type classifications:
105 Type primitive boxed lifted algebraic
106 -----------------------------------------------------------------------------
108 ByteArray# Yes Yes No No
109 (# a, b #) Yes No No Yes
110 ( a, b ) No Yes Yes Yes
115 ----------------------
116 A note about newtypes
117 ----------------------
122 Then we want N to be represented as an Int, and that's what we arrange.
123 The front end of the compiler [TcType.lhs] treats N as opaque,
124 the back end treats it as transparent [Type.lhs].
126 There's a bit of a problem with recursive newtypes
128 newtype Q = MkQ (Q->Q)
130 Here the 'implicit expansion' we get from treating P and Q as transparent
131 would give rise to infinite types, which in turn makes eqType diverge.
132 Similarly splitForAllTys and splitFunTys can get into a loop.
136 * Newtypes are always represented using TyConApp.
138 * For non-recursive newtypes, P, treat P just like a type synonym after
139 type-checking is done; i.e. it's opaque during type checking (functions
140 from TcType) but transparent afterwards (functions from Type).
141 "Treat P as a type synonym" means "all functions expand NewTcApps
144 Applications of the data constructor P simply vanish:
148 * For recursive newtypes Q, treat the Q and its representation as
149 distinct right through the compiler. Applications of the data consructor
151 Q = \(x::Q->Q). coerce Q x
152 They are rare, so who cares if they are a tiny bit less efficient.
154 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
155 to cut all loops. The other members of the loop may be marked 'non-recursive'.
158 %************************************************************************
160 \subsection{The data type}
162 %************************************************************************
170 Type -- Function is *not* a TyConApp
171 Type -- It must be another AppTy, or TyVarTy
172 -- (or NoteTy of these)
174 | TyConApp -- Application of a TyCon, including newtypes *and* synonyms
175 TyCon -- *Invariant* saturated appliations of FunTyCon and
176 -- synonyms have their own constructors, below.
177 -- However, *unsaturated* FunTyCons do appear as TyConApps.
179 [Type] -- Might not be saturated.
180 -- Even type synonyms are not necessarily saturated;
181 -- for example unsaturated type synonyms can appear as the
182 -- RHS of a type synonym.
184 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
188 | ForAllTy -- A polymorphic type
192 | PredTy -- The type of evidence for a type predictate
193 PredType -- See Note [PredTy], and Note [Equality predicates]
194 -- NB: A PredTy (EqPred _ _) can appear only as the kind
195 -- of a coercion variable; never as the argument or result
196 -- of a FunTy (unlike ClassP, IParam)
198 | NoteTy -- A type with a note attached
200 Type -- The expanded version
202 type Kind = Type -- Invariant: a kind is always
204 -- or TyConApp PrimTyCon [...]
205 -- or TyVar kv (during inference only)
206 -- or ForAll ... (for top-level coercions)
208 type SuperKind = Type -- Invariant: a super kind is always
209 -- TyConApp SuperKindTyCon ...
211 data TyNote = FTVNote TyVarSet -- The free type variables of the noted expression
214 -------------------------------------
219 represents a value whose type is the Haskell predicate p,
220 where a predicate is what occurs before the '=>' in a Haskell type.
221 It can be expanded into its representation, but:
223 * The type checker must treat it as opaque
224 * The rest of the compiler treats it as transparent
226 Consider these examples:
227 f :: (Eq a) => a -> Int
228 g :: (?x :: Int -> Int) => a -> Int
229 h :: (r\l) => {r} => {l::Int | r}
231 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
232 Predicates are represented inside GHC by PredType:
236 = ClassP Class [Type] -- Class predicate
237 | IParam (IPName Name) Type -- Implicit parameter
238 | EqPred Type Type -- Equality predicate (ty1 ~ ty2)
240 type ThetaType = [PredType]
243 (We don't support TREX records yet, but the setup is designed
244 to expand to allow them.)
246 A Haskell qualified type, such as that for f,g,h above, is
248 * a FunTy for the double arrow
249 * with a PredTy as the function argument
251 The predicate really does turn into a real extra argument to the
252 function. If the argument has type (PredTy p) then the predicate p is
253 represented by evidence (a dictionary, for example, of type (predRepTy p).
255 Note [Equality predicates]
256 ~~~~~~~~~~~~~~~~~~~~~~~~~~
257 forall a b. (a ~ S b) => a -> b
258 could be represented by
259 ForAllTy a (ForAllTy b (FunTy (PredTy (EqPred a (S b))) ...))
261 ForAllTy a (ForAllTy b (ForAllTy (c::PredTy (EqPred a (S b))) ...))
263 The latter is what we do. (Unlike for class and implicit parameter
264 constraints, which do use FunTy.)
267 * FunTy is always a *value* function
268 * ForAllTy is discarded at runtime
270 We often need to make a "wildcard" (c::PredTy..). We always use the same
271 name (wildCoVarName), since it's not mentioned.
274 %************************************************************************
278 %************************************************************************
280 Despite the fact that DataCon has to be imported via a hi-boot route,
281 this module seems the right place for TyThing, because it's needed for
282 funTyCon and all the types in TysPrim.
285 data TyThing = AnId Id
290 instance Outputable TyThing where
293 pprTyThing :: TyThing -> SDoc
294 pprTyThing thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
296 pprTyThingCategory :: TyThing -> SDoc
297 pprTyThingCategory (ATyCon _) = ptext SLIT("Type constructor")
298 pprTyThingCategory (AClass _) = ptext SLIT("Class")
299 pprTyThingCategory (AnId _) = ptext SLIT("Identifier")
300 pprTyThingCategory (ADataCon _) = ptext SLIT("Data constructor")
302 instance NamedThing TyThing where -- Can't put this with the type
303 getName (AnId id) = getName id -- decl, because the DataCon instance
304 getName (ATyCon tc) = getName tc -- isn't visible there
305 getName (AClass cl) = getName cl
306 getName (ADataCon dc) = dataConName dc
310 %************************************************************************
312 Wired-in type constructors
314 %************************************************************************
316 We define a few wired-in type constructors here to avoid module knots
319 --------------------------
320 -- First the TyCons...
322 funTyCon, tySuperKindTyCon, coSuperKindTyCon, liftedTypeKindTyCon,
323 openTypeKindTyCon, unliftedTypeKindTyCon,
324 ubxTupleKindTyCon, argTypeKindTyCon
326 funTyConName, tySuperKindTyConName, coSuperKindTyConName, liftedTypeKindTyConName,
327 openTypeKindTyConName, unliftedTypeKindTyConName,
328 ubxTupleKindTyConName, argTypeKindTyConName
331 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
332 -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
333 -- But if we do that we get kind errors when saying
334 -- instance Control.Arrow (->)
335 -- becuase the expected kind is (*->*->*). The trouble is that the
336 -- expected/actual stuff in the unifier does not go contra-variant, whereas
337 -- the kind sub-typing does. Sigh. It really only matters if you use (->) in
338 -- a prefix way, thus: (->) Int# Int#. And this is unusual.
341 tySuperKindTyCon = mkSuperKindTyCon tySuperKindTyConName
342 coSuperKindTyCon = mkSuperKindTyCon coSuperKindTyConName
344 liftedTypeKindTyCon = mkKindTyCon liftedTypeKindTyConName
345 openTypeKindTyCon = mkKindTyCon openTypeKindTyConName
346 unliftedTypeKindTyCon = mkKindTyCon unliftedTypeKindTyConName
347 ubxTupleKindTyCon = mkKindTyCon ubxTupleKindTyConName
348 argTypeKindTyCon = mkKindTyCon argTypeKindTyConName
350 mkKindTyCon :: Name -> TyCon
351 mkKindTyCon name = mkVoidPrimTyCon name tySuperKind 0
353 --------------------------
354 -- ... and now their names
356 tySuperKindTyConName = mkPrimTyConName FSLIT("BOX") tySuperKindTyConKey tySuperKindTyCon
357 coSuperKindTyConName = mkPrimTyConName FSLIT("COERCION") coSuperKindTyConKey coSuperKindTyCon
358 liftedTypeKindTyConName = mkPrimTyConName FSLIT("*") liftedTypeKindTyConKey liftedTypeKindTyCon
359 openTypeKindTyConName = mkPrimTyConName FSLIT("?") openTypeKindTyConKey openTypeKindTyCon
360 unliftedTypeKindTyConName = mkPrimTyConName FSLIT("#") unliftedTypeKindTyConKey unliftedTypeKindTyCon
361 ubxTupleKindTyConName = mkPrimTyConName FSLIT("(#)") ubxTupleKindTyConKey ubxTupleKindTyCon
362 argTypeKindTyConName = mkPrimTyConName FSLIT("??") argTypeKindTyConKey argTypeKindTyCon
363 funTyConName = mkPrimTyConName FSLIT("(->)") funTyConKey funTyCon
365 mkPrimTyConName :: FastString -> Unique -> TyCon -> Name
366 mkPrimTyConName occ key tycon = mkWiredInName gHC_PRIM (mkOccNameFS tcName occ)
370 -- All of the super kinds and kinds are defined in Prim and use BuiltInSyntax,
371 -- because they are never in scope in the source
374 -- We also need Kinds and SuperKinds, locally and in TyCon
376 kindTyConType :: TyCon -> Type
377 kindTyConType kind = TyConApp kind []
379 liftedTypeKind, unliftedTypeKind, openTypeKind, argTypeKind, ubxTupleKind :: Kind
381 liftedTypeKind = kindTyConType liftedTypeKindTyCon
382 unliftedTypeKind = kindTyConType unliftedTypeKindTyCon
383 openTypeKind = kindTyConType openTypeKindTyCon
384 argTypeKind = kindTyConType argTypeKindTyCon
385 ubxTupleKind = kindTyConType ubxTupleKindTyCon
387 mkArrowKind :: Kind -> Kind -> Kind
388 mkArrowKind k1 k2 = FunTy k1 k2
390 mkArrowKinds :: [Kind] -> Kind -> Kind
391 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
393 tySuperKind, coSuperKind :: SuperKind
394 tySuperKind = kindTyConType tySuperKindTyCon
395 coSuperKind = kindTyConType coSuperKindTyCon
397 isTySuperKind :: SuperKind -> Bool
398 isTySuperKind (NoteTy _ ty) = isTySuperKind ty
399 isTySuperKind (TyConApp kc []) = kc `hasKey` tySuperKindTyConKey
400 isTySuperKind _ = False
402 isCoSuperKind :: SuperKind -> Bool
403 isCoSuperKind (NoteTy _ ty) = isCoSuperKind ty
404 isCoSuperKind (TyConApp kc []) = kc `hasKey` coSuperKindTyConKey
405 isCoSuperKind _ = False
408 -- Lastly we need a few functions on Kinds
410 isLiftedTypeKindCon :: TyCon -> Bool
411 isLiftedTypeKindCon tc = tc `hasKey` liftedTypeKindTyConKey
413 isLiftedTypeKind :: Kind -> Bool
414 isLiftedTypeKind (TyConApp tc []) = isLiftedTypeKindCon tc
415 isLiftedTypeKind _ = False
417 isCoercionKind :: Kind -> Bool
418 -- All coercions are of form (ty1 ~ ty2)
419 -- This function is here rather than in Coercion,
420 -- because it's used in a knot-tied way to enforce invariants in Var
421 isCoercionKind (NoteTy _ k) = isCoercionKind k
422 isCoercionKind (PredTy (EqPred {})) = True
423 isCoercionKind _ = False
425 coVarPred :: CoVar -> PredType
427 = ASSERT( isCoVar tv )
429 PredTy eq -> eq -- There shouldn't even be a NoteTy in the way
430 other -> pprPanic "coVarPred" (ppr tv $$ ppr other)
435 %************************************************************************
437 \subsection{The external interface}
439 %************************************************************************
441 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
442 defined to use this. @pprParendType@ is the same, except it puts
443 parens around the type, except for the atomic cases. @pprParendType@
444 works just by setting the initial context precedence very high.
447 data Prec = TopPrec -- No parens
448 | FunPrec -- Function args; no parens for tycon apps
449 | TyConPrec -- Tycon args; no parens for atomic
452 maybeParen :: Prec -> Prec -> SDoc -> SDoc
453 maybeParen ctxt_prec inner_prec pretty
454 | ctxt_prec < inner_prec = pretty
455 | otherwise = parens pretty
458 pprType, pprParendType :: Type -> SDoc
459 pprType ty = ppr_type TopPrec ty
460 pprParendType ty = ppr_type TyConPrec ty
462 pprTypeApp :: NamedThing a => a -> SDoc -> [Type] -> SDoc
463 -- The first arg is the tycon; it's used to arrange printing infix
464 -- if it looks like an operator
465 -- Second arg is the pretty-printed tycon
466 pprTypeApp tc pp_tc tys = ppr_type_app TopPrec (getName tc) pp_tc tys
469 pprPred :: PredType -> SDoc
470 pprPred (ClassP cls tys) = pprClassPred cls tys
471 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
472 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext SLIT("~")), ppr ty2]
473 pprClassPred :: Class -> [Type] -> SDoc
474 pprClassPred clas tys = ppr_type_app TopPrec (getName clas) (ppr clas) tys
476 pprTheta :: ThetaType -> SDoc
477 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
479 pprThetaArrow :: ThetaType -> SDoc
482 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
485 instance Outputable Type where
488 instance Outputable PredType where
491 instance Outputable name => OutputableBndr (IPName name) where
492 pprBndr _ n = ppr n -- Simple for now
495 -- OK, here's the main printer
497 pprKind, pprParendKind :: Kind -> SDoc
499 pprParendKind = pprParendType
501 ppr_type :: Prec -> Type -> SDoc
502 ppr_type _ (TyVarTy tv) = ppr tv
503 ppr_type _ (PredTy pred) = ifPprDebug (ptext SLIT("<pred>")) <> (ppr pred)
504 ppr_type p (NoteTy _ ty2) = ifPprDebug (ptext SLIT("<note>")) <> ppr_type p ty2
505 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
507 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
508 pprType t1 <+> ppr_type TyConPrec t2
510 ppr_type p ty@(ForAllTy _ _) = ppr_forall_type p ty
511 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
513 ppr_type p (FunTy ty1 ty2)
514 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
515 maybeParen p FunPrec $
516 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
518 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
519 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
521 ppr_forall_type :: Prec -> Type -> SDoc
523 = maybeParen p FunPrec $
524 sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
526 (tvs, rho) = split1 [] ty
527 (ctxt, tau) = split2 [] rho
529 -- We need to be extra careful here as equality constraints will occur as
530 -- type variables with an equality kind. So, while collecting quantified
531 -- variables, we separate the coercion variables out and turn them into
532 -- equality predicates.
533 split1 tvs (ForAllTy tv ty)
534 | not (isCoVar tv) = split1 (tv:tvs) ty
535 split1 tvs (NoteTy _ ty) = split1 tvs ty
536 split1 tvs ty = (reverse tvs, ty)
538 split2 ps (NoteTy _ arg -- Rather a disgusting case
539 `FunTy` res) = split2 ps (arg `FunTy` res)
540 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
541 split2 ps (ForAllTy tv ty)
542 | isCoVar tv = split2 (coVarPred tv : ps) ty
543 split2 ps (NoteTy _ ty) = split2 ps ty
544 split2 ps ty = (reverse ps, ty)
546 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
550 | tc `hasKey` listTyConKey = brackets (pprType ty)
551 | tc `hasKey` parrTyConKey = ptext SLIT("[:") <> pprType ty <> ptext SLIT(":]")
552 | tc `hasKey` liftedTypeKindTyConKey = ptext SLIT("*")
553 | tc `hasKey` unliftedTypeKindTyConKey = ptext SLIT("#")
554 | tc `hasKey` openTypeKindTyConKey = ptext SLIT("(?)")
555 | tc `hasKey` ubxTupleKindTyConKey = ptext SLIT("(#)")
556 | tc `hasKey` argTypeKindTyConKey = ptext SLIT("??")
559 | isTupleTyCon tc && tyConArity tc == length tys
560 = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
562 = ppr_type_app p (getName tc) (ppr_naked_tc tc) tys
564 ppr_type_app :: Prec -> Name -> SDoc -> [Type] -> SDoc
565 ppr_type_app p tc pp_tc tys
566 | is_sym_occ -- Print infix if possible
567 , [ty1,ty2] <- tys -- We know nothing of precedence though
568 = maybeParen p FunPrec (sep [ppr_type FunPrec ty1,
569 pp_tc <+> ppr_type FunPrec ty2])
571 = maybeParen p TyConPrec (hang paren_tc 2 (sep (map pprParendType tys)))
573 is_sym_occ = isSymOcc (getOccName tc)
574 paren_tc | is_sym_occ = parens pp_tc
577 ppr_tc :: TyCon -> SDoc
578 ppr_tc tc = parenSymOcc (getOccName tc) (ppr_naked_tc tc)
580 ppr_naked_tc :: TyCon -> SDoc -- No brackets for SymOcc
582 = pp_nt_debug <> ppr tc
584 pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
585 then ptext SLIT("<recnt>")
586 else ptext SLIT("<nt>"))
590 pprForAll :: [TyVar] -> SDoc
592 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
594 pprTvBndr :: TyVar -> SDoc
595 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
596 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)