2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 \section[TypeRep]{Type - friends' interface}
8 Type(..), TyNote(..), UsageAnn(..), -- Representation visible to friends
11 superKind, superBoxity, -- :: SuperKind
13 boxedKind, -- :: Kind :: BX
14 anyBoxKind, -- :: Kind :: BX
15 typeCon, -- :: KindCon :: BX -> KX
16 anyBoxCon, -- :: KindCon :: BX
18 boxedTypeKind, unboxedTypeKind, openTypeKind, -- Kind :: superKind
20 mkArrowKind, mkArrowKinds,
25 #include "HsVersions.h"
28 import Var ( TyVar, UVar )
32 import Name ( Provenance(..), ExportFlag(..),
33 mkWiredInTyConName, mkGlobalName, mkKindOccFS, tcName,
35 import TyCon ( TyCon, KindCon,
36 mkFunTyCon, mkKindCon, mkSuperKindCon,
40 import SrcLoc ( mkBuiltinSrcLoc )
41 import PrelMods ( pREL_GHC )
42 import Unique -- quite a few *Keys
43 import Util ( thenCmp )
46 %************************************************************************
48 \subsection{Type Classifications}
50 %************************************************************************
54 *unboxed* iff its representation is other than a pointer
55 Unboxed types cannot instantiate a type variable.
56 Unboxed types are always unlifted.
58 *lifted* A type is lifted iff it has bottom as an element.
59 Closures always have lifted types: i.e. any
60 let-bound identifier in Core must have a lifted
61 type. Operationally, a lifted object is one that
63 (NOTE: previously "pointed").
65 *algebraic* A type with one or more constructors, whether declared
66 with "data" or "newtype".
67 An algebraic type is one that can be deconstructed
68 with a case expression.
69 *NOT* the same as lifted types, because we also
70 include unboxed tuples in this classification.
72 *data* A type declared with "data". Also boxed tuples.
74 *primitive* iff it is a built-in type that can't be expressed
77 Currently, all primitive types are unlifted, but that's not necessarily
78 the case. (E.g. Int could be primitive.)
80 Some primitive types are unboxed, such as Int#, whereas some are boxed
81 but unlifted (such as ByteArray#). The only primitive types that we
82 classify as algebraic are the unboxed tuples.
84 examples of type classifications:
86 Type primitive boxed lifted algebraic
87 -----------------------------------------------------------------------------
89 ByteArray# Yes Yes No No
90 (# a, b #) Yes No No Yes
91 ( a, b ) No Yes Yes Yes
94 %************************************************************************
96 \subsection{The data type}
98 %************************************************************************
102 type SuperKind = Type
105 type TyVarSubst = TyVarEnv Type
111 Type -- Function is *not* a TyConApp
114 | TyConApp -- Application of a TyCon
115 TyCon -- *Invariant* saturated appliations of FunTyCon and
116 -- synonyms have their own constructors, below.
117 [Type] -- Might not be saturated.
119 | FunTy -- Special case of TyConApp: TyConApp FunTyCon [t1,t2]
123 | NoteTy -- Saturated application of a type synonym
125 Type -- The expanded version
132 = SynNote Type -- The unexpanded version of the type synonym; always a TyConApp
133 | FTVNote TyVarSet -- The free type variables of the noted expression
134 | UsgNote UsageAnn -- The usage annotation at this node
135 | UsgForAll UVar -- Annotation variable binder
138 = UsOnce -- Used at most once
139 | UsMany -- Used possibly many times (no info; this annotation can be omitted)
140 | UsVar UVar -- Annotation is variable (unbound OK only inside analysis)
144 %************************************************************************
148 %************************************************************************
156 kv :: KX is a kind variable
162 | AnyBox -- Used *only* for special built-in things
163 -- like error :: forall (a::*?). String -> a
164 -- Here, the 'a' can be instantiated to a boxed or
168 bxv :: BX is a boxity variable
172 | sk -> sk -- In ptic (BX -> KX)
175 mk_kind_name key str = mkGlobalName key pREL_GHC (mkKindOccFS tcName str)
176 (LocalDef mkBuiltinSrcLoc NotExported)
177 -- mk_kind_name is a bit of a hack
178 -- The LocalDef means that we print the name without
179 -- a qualifier, which is what we want for these kinds.
180 -- It's used for both Kinds and Boxities
186 superKind :: SuperKind -- KX, the type of all kinds
187 superKindName = mk_kind_name kindConKey SLIT("KX")
188 superKind = TyConApp (mkSuperKindCon superKindName) []
190 superBoxity :: SuperKind -- BX, the type of all boxities
191 superBoxityName = mk_kind_name boxityConKey SLIT("BX")
192 superBoxity = TyConApp (mkSuperKindCon superBoxityName) []
195 Define Boxed, Unboxed, AnyBox
198 boxedKind, unboxedKind, anyBoxKind :: Kind -- Of superkind superBoxity
200 boxedConName = mk_kind_name boxedConKey SLIT("*")
201 boxedKind = TyConApp (mkKindCon boxedConName superBoxity) []
203 unboxedConName = mk_kind_name unboxedConKey SLIT("#")
204 unboxedKind = TyConApp (mkKindCon unboxedConName superBoxity) []
206 anyBoxConName = mk_kind_name anyBoxConKey SLIT("?")
207 anyBoxCon = mkKindCon anyBoxConName superBoxity -- A kind of wild card
208 anyBoxKind = TyConApp anyBoxCon []
215 typeConName = mk_kind_name typeConKey SLIT("Type")
216 typeCon = mkKindCon typeConName (superBoxity `FunTy` superKind)
219 Define (Type Boxed), (Type Unboxed), (Type AnyBox)
222 boxedTypeKind, unboxedTypeKind, openTypeKind :: Kind
223 boxedTypeKind = TyConApp typeCon [boxedKind]
224 unboxedTypeKind = TyConApp typeCon [unboxedKind]
225 openTypeKind = TyConApp typeCon [anyBoxKind]
227 mkArrowKind :: Kind -> Kind -> Kind
228 mkArrowKind k1 k2 = k1 `FunTy` k2
230 mkArrowKinds :: [Kind] -> Kind -> Kind
231 mkArrowKinds arg_kinds result_kind = foldr mkArrowKind result_kind arg_kinds
235 %************************************************************************
237 \subsection{Wired-in type constructors
239 %************************************************************************
241 We define a few wired-in type constructors here to avoid module knots
244 funTyConName = mkWiredInTyConName funTyConKey pREL_GHC SLIT("(->)") funTyCon
245 funTyCon = mkFunTyCon funTyConName (mkArrowKinds [boxedTypeKind, boxedTypeKind] boxedTypeKind)
249 %************************************************************************
251 \subsection{Equality on types}
253 %************************************************************************
255 For the moment at least, type comparisons don't work if
256 there are embedded for-alls.
259 instance Eq Type where
260 ty1 == ty2 = case ty1 `cmpTy` ty2 of { EQ -> True; other -> False }
262 instance Ord Type where
263 compare ty1 ty2 = cmpTy ty1 ty2
265 cmpTy :: Type -> Type -> Ordering
267 = cmp emptyVarEnv ty1 ty2
269 -- The "env" maps type variables in ty1 to type variables in ty2
270 -- So when comparing for-alls.. (forall tv1 . t1) (forall tv2 . t2)
271 -- we in effect substitute tv2 for tv1 in t1 before continuing
272 lookup env tv1 = case lookupVarEnv env tv1 of
277 cmp env (NoteTy _ ty1) ty2 = cmp env ty1 ty2
278 cmp env ty1 (NoteTy _ ty2) = cmp env ty1 ty2
280 -- Deal with equal constructors
281 cmp env (TyVarTy tv1) (TyVarTy tv2) = lookup env tv1 `compare` tv2
282 cmp env (AppTy f1 a1) (AppTy f2 a2) = cmp env f1 f2 `thenCmp` cmp env a1 a2
283 cmp env (FunTy f1 a1) (FunTy f2 a2) = cmp env f1 f2 `thenCmp` cmp env a1 a2
284 cmp env (TyConApp tc1 tys1) (TyConApp tc2 tys2) = (tc1 `compare` tc2) `thenCmp` (cmps env tys1 tys2)
285 cmp env (ForAllTy tv1 t1) (ForAllTy tv2 t2) = cmp (extendVarEnv env tv1 tv2) t1 t2
287 -- Deal with the rest: TyVarTy < AppTy < FunTy < TyConApp < ForAllTy
288 cmp env (AppTy _ _) (TyVarTy _) = GT
290 cmp env (FunTy _ _) (TyVarTy _) = GT
291 cmp env (FunTy _ _) (AppTy _ _) = GT
293 cmp env (TyConApp _ _) (TyVarTy _) = GT
294 cmp env (TyConApp _ _) (AppTy _ _) = GT
295 cmp env (TyConApp _ _) (FunTy _ _) = GT
297 cmp env (ForAllTy _ _) other = GT
302 cmps env (t:ts) [] = GT
303 cmps env [] (t:ts) = LT
304 cmps env (t1:t1s) (t2:t2s) = cmp env t1 t2 `thenCmp` cmps env t1s t2s