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/WorkingConventions#Warnings
17 Type(..), TyNote(..), -- Representation visible
18 PredType(..), -- to friends
20 Kind, ThetaType, -- Synonyms
25 pprType, pprParendType, pprTypeApp,
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
296 ppr thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
298 pprTyThingCategory :: TyThing -> SDoc
299 pprTyThingCategory (ATyCon _) = ptext SLIT("Type constructor")
300 pprTyThingCategory (AClass _) = ptext SLIT("Class")
301 pprTyThingCategory (AnId _) = ptext SLIT("Identifier")
302 pprTyThingCategory (ADataCon _) = ptext SLIT("Data constructor")
304 instance NamedThing TyThing where -- Can't put this with the type
305 getName (AnId id) = getName id -- decl, because the DataCon instance
306 getName (ATyCon tc) = getName tc -- isn't visible there
307 getName (AClass cl) = getName cl
308 getName (ADataCon dc) = dataConName dc
312 %************************************************************************
314 Wired-in type constructors
316 %************************************************************************
318 We define a few wired-in type constructors here to avoid module knots
321 --------------------------
322 -- First the TyCons...
324 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [argTypeKind, openTypeKind] liftedTypeKind)
325 -- You might think that (->) should have type (?? -> ? -> *), and you'd be right
326 -- But if we do that we get kind errors when saying
327 -- instance Control.Arrow (->)
328 -- becuase the expected kind is (*->*->*). The trouble is that the
329 -- expected/actual stuff in the unifier does not go contra-variant, whereas
330 -- the kind sub-typing does. Sigh. It really only matters if you use (->) in
331 -- a prefix way, thus: (->) Int# Int#. And this is unusual.
334 tySuperKindTyCon = mkSuperKindTyCon tySuperKindTyConName
335 coSuperKindTyCon = mkSuperKindTyCon coSuperKindTyConName
337 liftedTypeKindTyCon = mkKindTyCon liftedTypeKindTyConName
338 openTypeKindTyCon = mkKindTyCon openTypeKindTyConName
339 unliftedTypeKindTyCon = mkKindTyCon unliftedTypeKindTyConName
340 ubxTupleKindTyCon = mkKindTyCon ubxTupleKindTyConName
341 argTypeKindTyCon = mkKindTyCon argTypeKindTyConName
343 mkKindTyCon :: Name -> TyCon
344 mkKindTyCon name = mkVoidPrimTyCon name tySuperKind 0
346 --------------------------
347 -- ... and now their names
349 tySuperKindTyConName = mkPrimTyConName FSLIT("BOX") tySuperKindTyConKey tySuperKindTyCon
350 coSuperKindTyConName = mkPrimTyConName FSLIT("COERCION") coSuperKindTyConKey coSuperKindTyCon
351 liftedTypeKindTyConName = mkPrimTyConName FSLIT("*") liftedTypeKindTyConKey liftedTypeKindTyCon
352 openTypeKindTyConName = mkPrimTyConName FSLIT("?") openTypeKindTyConKey openTypeKindTyCon
353 unliftedTypeKindTyConName = mkPrimTyConName FSLIT("#") unliftedTypeKindTyConKey unliftedTypeKindTyCon
354 ubxTupleKindTyConName = mkPrimTyConName FSLIT("(#)") ubxTupleKindTyConKey ubxTupleKindTyCon
355 argTypeKindTyConName = mkPrimTyConName FSLIT("??") argTypeKindTyConKey argTypeKindTyCon
356 funTyConName = mkPrimTyConName FSLIT("(->)") funTyConKey funTyCon
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 = kindTyConType liftedTypeKindTyCon
372 unliftedTypeKind = kindTyConType unliftedTypeKindTyCon
373 openTypeKind = kindTyConType openTypeKindTyCon
374 argTypeKind = kindTyConType argTypeKindTyCon
375 ubxTupleKind = kindTyConType ubxTupleKindTyCon
377 mkArrowKind :: Kind -> Kind -> Kind
378 mkArrowKind k1 k2 = FunTy k1 k2
380 mkArrowKinds :: [Kind] -> Kind -> Kind
381 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
383 tySuperKind, coSuperKind :: SuperKind
384 tySuperKind = kindTyConType tySuperKindTyCon
385 coSuperKind = kindTyConType coSuperKindTyCon
387 isTySuperKind (NoteTy _ ty) = isTySuperKind ty
388 isTySuperKind (TyConApp kc []) = kc `hasKey` tySuperKindTyConKey
389 isTySuperKind other = False
391 isCoSuperKind :: SuperKind -> Bool
392 isCoSuperKind (NoteTy _ ty) = isCoSuperKind ty
393 isCoSuperKind (TyConApp kc []) = kc `hasKey` coSuperKindTyConKey
394 isCoSuperKind other = False
397 -- Lastly we need a few functions on Kinds
399 isLiftedTypeKindCon tc = tc `hasKey` liftedTypeKindTyConKey
401 isLiftedTypeKind :: Kind -> Bool
402 isLiftedTypeKind (TyConApp tc []) = isLiftedTypeKindCon tc
403 isLiftedTypeKind other = False
405 isCoercionKind :: Kind -> Bool
406 -- All coercions are of form (ty1 ~ ty2)
407 -- This function is here rather than in Coercion,
408 -- because it's used in a knot-tied way to enforce invariants in Var
409 isCoercionKind (NoteTy _ k) = isCoercionKind k
410 isCoercionKind (PredTy (EqPred {})) = True
411 isCoercionKind other = False
416 %************************************************************************
418 \subsection{The external interface}
420 %************************************************************************
422 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
423 defined to use this. @pprParendType@ is the same, except it puts
424 parens around the type, except for the atomic cases. @pprParendType@
425 works just by setting the initial context precedence very high.
428 data Prec = TopPrec -- No parens
429 | FunPrec -- Function args; no parens for tycon apps
430 | TyConPrec -- Tycon args; no parens for atomic
433 maybeParen :: Prec -> Prec -> SDoc -> SDoc
434 maybeParen ctxt_prec inner_prec pretty
435 | ctxt_prec < inner_prec = pretty
436 | otherwise = parens pretty
439 pprType, pprParendType :: Type -> SDoc
440 pprType ty = ppr_type TopPrec ty
441 pprParendType ty = ppr_type TyConPrec ty
443 pprTypeApp :: NamedThing a => a -> SDoc -> [Type] -> SDoc
444 -- The first arg is the tycon; it's used to arrange printing infix
445 -- if it looks like an operator
446 -- Second arg is the pretty-printed tycon
447 pprTypeApp tc pp_tc tys = ppr_type_app TopPrec (getName tc) pp_tc tys
450 pprPred :: PredType -> SDoc
451 pprPred (ClassP cls tys) = pprClassPred cls tys
452 pprPred (IParam ip ty) = ppr ip <> dcolon <> pprType ty
453 pprPred (EqPred ty1 ty2) = sep [ppr ty1, nest 2 (ptext SLIT("~")), ppr ty2]
454 pprClassPred :: Class -> [Type] -> SDoc
455 pprClassPred clas tys = ppr_type_app TopPrec (getName clas) (ppr clas) tys
457 pprTheta :: ThetaType -> SDoc
458 pprTheta theta = parens (sep (punctuate comma (map pprPred theta)))
460 pprThetaArrow :: ThetaType -> SDoc
463 | otherwise = parens (sep (punctuate comma (map pprPred theta))) <+> ptext SLIT("=>")
466 instance Outputable Type where
469 instance Outputable PredType where
472 instance Outputable name => OutputableBndr (IPName name) where
473 pprBndr _ n = ppr n -- Simple for now
476 -- OK, here's the main printer
479 pprParendKind = pprParendType
481 ppr_type :: Prec -> Type -> SDoc
482 ppr_type p (TyVarTy tv) = ppr tv
483 ppr_type p (PredTy pred) = ifPprDebug (ptext SLIT("<pred>")) <> (ppr pred)
484 ppr_type p (NoteTy other ty2) = ppr_type p ty2
485 ppr_type p (TyConApp tc tys) = ppr_tc_app p tc tys
487 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
488 pprType t1 <+> ppr_type TyConPrec t2
490 ppr_type p ty@(ForAllTy _ _) = ppr_forall_type p ty
491 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
493 ppr_type p (FunTy ty1 ty2)
494 = -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
495 maybeParen p FunPrec $
496 sep (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
498 ppr_fun_tail (FunTy ty1 ty2) = (arrow <+> ppr_type FunPrec ty1) : ppr_fun_tail ty2
499 ppr_fun_tail other_ty = [arrow <+> pprType other_ty]
501 ppr_forall_type :: Prec -> Type -> SDoc
503 = maybeParen p FunPrec $
504 sep [pprForAll tvs, pprThetaArrow ctxt, pprType tau]
506 (tvs, rho) = split1 [] ty
507 (ctxt, tau) = split2 [] rho
509 split1 tvs (ForAllTy tv ty) = split1 (tv:tvs) ty
510 split1 tvs (NoteTy _ ty) = split1 tvs ty
511 split1 tvs ty = (reverse tvs, ty)
513 split2 ps (NoteTy _ arg -- Rather a disgusting case
514 `FunTy` res) = split2 ps (arg `FunTy` res)
515 split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
516 split2 ps (NoteTy _ ty) = split2 ps ty
517 split2 ps ty = (reverse ps, ty)
519 ppr_tc_app :: Prec -> TyCon -> [Type] -> SDoc
523 | tc `hasKey` listTyConKey = brackets (pprType ty)
524 | tc `hasKey` parrTyConKey = ptext SLIT("[:") <> pprType ty <> ptext SLIT(":]")
525 | tc `hasKey` liftedTypeKindTyConKey = ptext SLIT("*")
526 | tc `hasKey` unliftedTypeKindTyConKey = ptext SLIT("#")
527 | tc `hasKey` openTypeKindTyConKey = ptext SLIT("(?)")
528 | tc `hasKey` ubxTupleKindTyConKey = ptext SLIT("(#)")
529 | tc `hasKey` argTypeKindTyConKey = ptext SLIT("??")
532 | isTupleTyCon tc && tyConArity tc == length tys
533 = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map pprType tys)))
535 = ppr_type_app p (getName tc) (ppr_naked_tc tc) tys
537 ppr_type_app :: Prec -> Name -> SDoc -> [Type] -> SDoc
538 ppr_type_app p tc pp_tc tys
539 | is_sym_occ -- Print infix if possible
540 , [ty1,ty2] <- tys -- We know nothing of precedence though
541 = maybeParen p FunPrec (sep [ppr_type FunPrec ty1,
542 pp_tc <+> ppr_type FunPrec ty2])
544 = maybeParen p TyConPrec (hang paren_tc 2 (sep (map pprParendType tys)))
546 is_sym_occ = isSymOcc (getOccName tc)
547 paren_tc | is_sym_occ = parens pp_tc
550 ppr_tc :: TyCon -> SDoc
551 ppr_tc tc = parenSymOcc (getOccName tc) (ppr_naked_tc tc)
553 ppr_naked_tc :: TyCon -> SDoc -- No brackets for SymOcc
555 = pp_nt_debug <> ppr tc
557 pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
558 then ptext SLIT("<recnt>")
559 else ptext SLIT("<nt>"))
564 pprForAll tvs = ptext SLIT("forall") <+> sep (map pprTvBndr tvs) <> dot
566 pprTvBndr tv | isLiftedTypeKind kind = ppr tv
567 | otherwise = parens (ppr tv <+> dcolon <+> pprKind kind)