2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
5 \section[TypeRep]{Type - friends' interface}
9 -- The above warning supression flag is a temporary kludge.
10 -- While working on this module you are encouraged to remove it and fix
11 -- any warnings in the module. See
12 -- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
17 Type(..), TyNote(..), -- Representation visible
18 PredType(..), -- to friends
20 Kind, ThetaType, -- Synonyms
25 pprType, pprParendType, pprTypeApp,
26 pprTyThing, pprTyThingCategory,
27 pprPred, pprTheta, pprForAll, pprThetaArrow, pprClassPred,
30 liftedTypeKind, unliftedTypeKind, openTypeKind,
31 argTypeKind, ubxTupleKind,
32 isLiftedTypeKindCon, isLiftedTypeKind,
33 mkArrowKind, mkArrowKinds, isCoercionKind,
35 -- Kind constructors...
36 liftedTypeKindTyCon, openTypeKindTyCon, unliftedTypeKindTyCon,
37 argTypeKindTyCon, ubxTupleKindTyCon,
40 unliftedTypeKindTyConName, openTypeKindTyConName,
41 ubxTupleKindTyConName, argTypeKindTyConName,
42 liftedTypeKindTyConName,
45 tySuperKind, coSuperKind,
46 isTySuperKind, isCoSuperKind,
47 tySuperKindTyCon, coSuperKindTyCon,
49 pprKind, pprParendKind
52 #include "HsVersions.h"
54 import {-# SOURCE #-} DataCon( DataCon, dataConName )
70 %************************************************************************
72 \subsection{Type Classifications}
74 %************************************************************************
78 *unboxed* iff its representation is other than a pointer
79 Unboxed types are also unlifted.
81 *lifted* A type is lifted iff it has bottom as an element.
82 Closures always have lifted types: i.e. any
83 let-bound identifier in Core must have a lifted
84 type. Operationally, a lifted object is one that
87 Only lifted types may be unified with a type variable.
89 *algebraic* A type with one or more constructors, whether declared
90 with "data" or "newtype".
91 An algebraic type is one that can be deconstructed
92 with a case expression.
93 *NOT* the same as lifted types, because we also
94 include unboxed tuples in this classification.
96 *data* A type declared with "data". Also boxed tuples.
98 *primitive* iff it is a built-in type that can't be expressed
101 Currently, all primitive types are unlifted, but that's not necessarily
102 the case. (E.g. Int could be primitive.)
104 Some primitive types are unboxed, such as Int#, whereas some are boxed
105 but unlifted (such as ByteArray#). The only primitive types that we
106 classify as algebraic are the unboxed tuples.
108 examples of type classifications:
110 Type primitive boxed lifted algebraic
111 -----------------------------------------------------------------------------
113 ByteArray# Yes Yes No No
114 (# a, b #) Yes No No Yes
115 ( a, b ) No Yes Yes Yes
120 ----------------------
121 A note about newtypes
122 ----------------------
127 Then we want N to be represented as an Int, and that's what we arrange.
128 The front end of the compiler [TcType.lhs] treats N as opaque,
129 the back end treats it as transparent [Type.lhs].
131 There's a bit of a problem with recursive newtypes
133 newtype Q = MkQ (Q->Q)
135 Here the 'implicit expansion' we get from treating P and Q as transparent
136 would give rise to infinite types, which in turn makes eqType diverge.
137 Similarly splitForAllTys and splitFunTys can get into a loop.
141 * Newtypes are always represented using TyConApp.
143 * For non-recursive newtypes, P, treat P just like a type synonym after
144 type-checking is done; i.e. it's opaque during type checking (functions
145 from TcType) but transparent afterwards (functions from Type).
146 "Treat P as a type synonym" means "all functions expand NewTcApps
149 Applications of the data constructor P simply vanish:
153 * For recursive newtypes Q, treat the Q and its representation as
154 distinct right through the compiler. Applications of the data consructor
156 Q = \(x::Q->Q). coerce Q x
157 They are rare, so who cares if they are a tiny bit less efficient.
159 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
160 to cut all loops. The other members of the loop may be marked 'non-recursive'.
163 %************************************************************************
165 \subsection{The data type}
167 %************************************************************************
175 Type -- Function is *not* a TyConApp
176 Type -- It must be another AppTy, or TyVarTy
177 -- (or NoteTy of these)
179 | TyConApp -- Application of a TyCon, including newtypes *and* synonyms
180 TyCon -- *Invariant* saturated appliations of FunTyCon and
181 -- synonyms have their own constructors, below.
182 -- However, *unsaturated* FunTyCons do appear as TyConApps.
184 [Type] -- Might not be saturated.
185 -- Even type synonyms are not necessarily saturated;
186 -- for example unsaturated type synonyms can appear as the
187 -- RHS of a type synonym.
189 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
193 | ForAllTy -- A polymorphic type
197 | PredTy -- The type of evidence for a type predictate
198 PredType -- See Note [PredTy], and Note [Equality predicates]
199 -- NB: A PredTy (EqPred _ _) can appear only as the kind
200 -- of a coercion variable; never as the argument or result
201 -- of a FunTy (unlike ClassP, IParam)
203 | NoteTy -- A type with a note attached
205 Type -- The expanded version
207 type Kind = Type -- Invariant: a kind is always
209 -- or TyConApp PrimTyCon [...]
210 -- or TyVar kv (during inference only)
211 -- or ForAll ... (for top-level coercions)
213 type SuperKind = Type -- Invariant: a super kind is always
214 -- TyConApp SuperKindTyCon ...
216 data TyNote = FTVNote TyVarSet -- The free type variables of the noted expression
219 -------------------------------------
224 represents a value whose type is the Haskell predicate p,
225 where a predicate is what occurs before the '=>' in a Haskell type.
226 It can be expanded into its representation, but:
228 * The type checker must treat it as opaque
229 * The rest of the compiler treats it as transparent
231 Consider these examples:
232 f :: (Eq a) => a -> Int
233 g :: (?x :: Int -> Int) => a -> Int
234 h :: (r\l) => {r} => {l::Int | r}
236 Here the "Eq a" and "?x :: Int -> Int" and "r\l" are all called *predicates*
237 Predicates are represented inside GHC by PredType:
241 = ClassP Class [Type] -- Class predicate
242 | IParam (IPName Name) Type -- Implicit parameter
243 | EqPred Type Type -- Equality predicate (ty1 ~ ty2)
245 type ThetaType = [PredType]
248 (We don't support TREX records yet, but the setup is designed
249 to expand to allow them.)
251 A Haskell qualified type, such as that for f,g,h above, is
253 * a FunTy for the double arrow
254 * with a PredTy as the function argument
256 The predicate really does turn into a real extra argument to the
257 function. If the argument has type (PredTy p) then the predicate p is
258 represented by evidence (a dictionary, for example, of type (predRepTy p).
260 Note [Equality predicates]
261 ~~~~~~~~~~~~~~~~~~~~~~~~~~
262 forall a b. (a ~ S b) => a -> b
263 could be represented by
264 ForAllTy a (ForAllTy b (FunTy (PredTy (EqPred a (S b))) ...))
266 ForAllTy a (ForAllTy b (ForAllTy (c::PredTy (EqPred a (S b))) ...))
268 The latter is what we do. (Unlike for class and implicit parameter
269 constraints, which do use FunTy.)
272 * FunTy is always a *value* function
273 * ForAllTy is discarded at runtime
275 We often need to make a "wildcard" (c::PredTy..). We always use the same
276 name (wildCoVarName), since it's not mentioned.
279 %************************************************************************
283 %************************************************************************
285 Despite the fact that DataCon has to be imported via a hi-boot route,
286 this module seems the right place for TyThing, because it's needed for
287 funTyCon and all the types in TysPrim.
290 data TyThing = AnId Id
295 instance Outputable TyThing where
298 pprTyThing :: TyThing -> SDoc
299 pprTyThing thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
301 pprTyThingCategory :: TyThing -> SDoc
302 pprTyThingCategory (ATyCon _) = ptext SLIT("Type constructor")
303 pprTyThingCategory (AClass _) = ptext SLIT("Class")
304 pprTyThingCategory (AnId _) = ptext SLIT("Identifier")
305 pprTyThingCategory (ADataCon _) = ptext SLIT("Data constructor")
307 instance NamedThing TyThing where -- Can't put this with the type
308 getName (AnId id) = getName id -- decl, because the DataCon instance
309 getName (ATyCon tc) = getName tc -- isn't visible there
310 getName (AClass cl) = getName cl
311 getName (ADataCon dc) = dataConName dc
315 %************************************************************************
317 Wired-in type constructors
319 %************************************************************************
321 We define a few wired-in type constructors here to avoid module knots
324 --------------------------
325 -- First the TyCons...
327 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
328 -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
329 -- But if we do that we get kind errors when saying
330 -- instance Control.Arrow (->)
331 -- becuase the expected kind is (*->*->*). The trouble is that the
332 -- expected/actual stuff in the unifier does not go contra-variant, whereas
333 -- the kind sub-typing does. Sigh. It really only matters if you use (->) in
334 -- a prefix way, thus: (->) Int# Int#. And this is unusual.
337 tySuperKindTyCon = mkSuperKindTyCon tySuperKindTyConName
338 coSuperKindTyCon = mkSuperKindTyCon coSuperKindTyConName
340 liftedTypeKindTyCon = mkKindTyCon liftedTypeKindTyConName
341 openTypeKindTyCon = mkKindTyCon openTypeKindTyConName
342 unliftedTypeKindTyCon = mkKindTyCon unliftedTypeKindTyConName
343 ubxTupleKindTyCon = mkKindTyCon ubxTupleKindTyConName
344 argTypeKindTyCon = mkKindTyCon argTypeKindTyConName
346 mkKindTyCon :: Name -> TyCon
347 mkKindTyCon name = mkVoidPrimTyCon name tySuperKind 0
349 --------------------------
350 -- ... and now their names
352 tySuperKindTyConName = mkPrimTyConName FSLIT("BOX") tySuperKindTyConKey tySuperKindTyCon
353 coSuperKindTyConName = mkPrimTyConName FSLIT("COERCION") coSuperKindTyConKey coSuperKindTyCon
354 liftedTypeKindTyConName = mkPrimTyConName FSLIT("*") liftedTypeKindTyConKey liftedTypeKindTyCon
355 openTypeKindTyConName = mkPrimTyConName FSLIT("?") openTypeKindTyConKey openTypeKindTyCon
356 unliftedTypeKindTyConName = mkPrimTyConName FSLIT("#") unliftedTypeKindTyConKey unliftedTypeKindTyCon
357 ubxTupleKindTyConName = mkPrimTyConName FSLIT("(#)") ubxTupleKindTyConKey ubxTupleKindTyCon
358 argTypeKindTyConName = mkPrimTyConName FSLIT("??") argTypeKindTyConKey argTypeKindTyCon
359 funTyConName = mkPrimTyConName FSLIT("(->)") funTyConKey funTyCon
361 mkPrimTyConName occ key tycon = mkWiredInName gHC_PRIM (mkOccNameFS tcName occ)
365 -- All of the super kinds and kinds are defined in Prim and use BuiltInSyntax,
366 -- because they are never in scope in the source
369 -- We also need Kinds and SuperKinds, locally and in TyCon
371 kindTyConType :: TyCon -> Type
372 kindTyConType kind = TyConApp kind []
374 liftedTypeKind = kindTyConType liftedTypeKindTyCon
375 unliftedTypeKind = kindTyConType unliftedTypeKindTyCon
376 openTypeKind = kindTyConType openTypeKindTyCon
377 argTypeKind = kindTyConType argTypeKindTyCon
378 ubxTupleKind = kindTyConType ubxTupleKindTyCon
380 mkArrowKind :: Kind -> Kind -> Kind
381 mkArrowKind k1 k2 = FunTy k1 k2
383 mkArrowKinds :: [Kind] -> Kind -> Kind
384 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
386 tySuperKind, coSuperKind :: SuperKind
387 tySuperKind = kindTyConType tySuperKindTyCon
388 coSuperKind = kindTyConType coSuperKindTyCon
390 isTySuperKind (NoteTy _ ty) = isTySuperKind ty
391 isTySuperKind (TyConApp kc []) = kc `hasKey` tySuperKindTyConKey
392 isTySuperKind other = False
394 isCoSuperKind :: SuperKind -> Bool
395 isCoSuperKind (NoteTy _ ty) = isCoSuperKind ty
396 isCoSuperKind (TyConApp kc []) = kc `hasKey` coSuperKindTyConKey
397 isCoSuperKind other = False
400 -- Lastly we need a few functions on Kinds
402 isLiftedTypeKindCon tc = tc `hasKey` liftedTypeKindTyConKey
404 isLiftedTypeKind :: Kind -> Bool
405 isLiftedTypeKind (TyConApp tc []) = isLiftedTypeKindCon tc
406 isLiftedTypeKind other = False
408 isCoercionKind :: Kind -> Bool
409 -- All coercions are of form (ty1 ~ ty2)
410 -- This function is here rather than in Coercion,
411 -- because it's used in a knot-tied way to enforce invariants in Var
412 isCoercionKind (NoteTy _ k) = isCoercionKind k
413 isCoercionKind (PredTy (EqPred {})) = True
414 isCoercionKind other = False
419 %************************************************************************
421 \subsection{The external interface}
423 %************************************************************************
425 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
426 defined to use this. @pprParendType@ is the same, except it puts
427 parens around the type, except for the atomic cases. @pprParendType@
428 works just by setting the initial context precedence very high.
431 data Prec = TopPrec -- No parens
432 | FunPrec -- Function args; no parens for tycon apps
433 | TyConPrec -- Tycon args; no parens for atomic
436 maybeParen :: Prec -> Prec -> SDoc -> SDoc
437 maybeParen ctxt_prec inner_prec pretty
438 | ctxt_prec < inner_prec = pretty
439 | otherwise = parens pretty
442 pprType, pprParendType :: Type -> SDoc
443 pprType ty = ppr_type TopPrec ty
444 pprParendType ty = ppr_type TyConPrec ty
446 pprTypeApp :: NamedThing a => a -> SDoc -> [Type] -> SDoc
447 -- The first arg is the tycon; it's used to arrange printing infix
448 -- if it looks like an operator
449 -- Second arg is the pretty-printed tycon
450 pprTypeApp tc pp_tc tys = ppr_type_app TopPrec (getName tc) pp_tc tys
453 pprPred :: PredType -> SDoc
454 pprPred (ClassP cls tys) = pprClassPred cls tys
455 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
456 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext SLIT("~")), ppr ty2]
457 pprClassPred :: Class -> [Type] -> SDoc
458 pprClassPred clas tys = ppr_type_app TopPrec (getName clas) (ppr clas) tys
460 pprTheta :: ThetaType -> SDoc
461 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
463 pprThetaArrow :: ThetaType -> SDoc
466 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
469 instance Outputable Type where
472 instance Outputable PredType where
475 instance Outputable name => OutputableBndr (IPName name) where
476 pprBndr _ n = ppr n -- Simple for now
479 -- OK, here's the main printer
482 pprParendKind = pprParendType
484 ppr_type :: Prec -> Type -> SDoc
485 ppr_type p (TyVarTy tv) = ppr tv
486 ppr_type p (PredTy pred) = ifPprDebug (ptext SLIT("<pred>")) <> (ppr pred)
487 ppr_type p (NoteTy other ty2) = ppr_type p ty2
488 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
490 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
491 pprType t1 <+> ppr_type TyConPrec t2
493 ppr_type p ty@(ForAllTy _ _) = ppr_forall_type p ty
494 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
496 ppr_type p (FunTy ty1 ty2)
497 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
498 maybeParen p FunPrec $
499 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
501 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
502 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
504 ppr_forall_type :: Prec -> Type -> SDoc
506 = maybeParen p FunPrec $
507 sep [pprForAll tvs, pprThetaArrow (ctxt1 ++ ctxt2), pprType tau]
509 (tvs, ctxt1, rho) = split1 [] [] ty
510 (ctxt2, tau) = split2 [] rho
512 -- We need to be extra careful here as equality constraints will occur as
513 -- type variables with an equality kind. So, while collecting quantified
514 -- variables, we separate the coercion variables out and turn them into
515 -- equality predicates.
516 split1 tvs eqs (ForAllTy tv ty)
517 | isCoVar tv = split1 tvs (eq:eqs) ty
518 | otherwise = split1 (tv:tvs) eqs ty
520 PredTy eq = tyVarKind tv
521 split1 tvs eqs (NoteTy _ ty) = split1 tvs eqs ty
522 split1 tvs eqs ty = (reverse tvs, reverse eqs, ty)
524 split2 ps (NoteTy _ arg -- Rather a disgusting case
525 `FunTy` res) = split2 ps (arg `FunTy` res)
526 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
527 split2 ps (NoteTy _ ty) = split2 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>"))
575 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
577 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
578 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)