2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 \section[Type]{Type - public interface}
8 -- re-exports from TypeRep:
12 superKind, superBoxity, -- :: SuperKind
14 boxedKind, -- :: Kind :: BX
15 anyBoxKind, -- :: Kind :: BX
16 typeCon, -- :: KindCon :: BX -> KX
17 anyBoxCon, -- :: KindCon :: BX
19 boxedTypeKind, unboxedTypeKind, openTypeKind, -- Kind :: superKind
21 mkArrowKind, mkArrowKinds, hasMoreBoxityInfo,
25 -- exports from this module:
28 mkTyVarTy, mkTyVarTys, getTyVar, getTyVar_maybe, isTyVarTy,
30 mkAppTy, mkAppTys, splitAppTy, splitAppTys, splitAppTy_maybe,
32 mkFunTy, mkFunTys, splitFunTy_maybe, splitFunTys, splitFunTysN,
33 funResultTy, funArgTy, zipFunTys,
35 mkTyConApp, mkTyConTy, splitTyConApp_maybe,
36 splitAlgTyConApp_maybe, splitAlgTyConApp,
37 mkDictTy, splitDictTy_maybe, isDictTy,
39 mkSynTy, isSynTy, deNoteType, repType, splitNewType_maybe,
41 UsageAnn(..), mkUsgTy, isUsgTy{- dont use -}, isNotUsgTy, splitUsgTy, unUsgTy, tyUsg,
42 mkUsForAllTy, mkUsForAllTys, splitUsForAllTys, substUsTy,
44 mkForAllTy, mkForAllTys, splitForAllTy_maybe, splitForAllTys,
45 isForAllTy, applyTy, applyTys, mkPiType,
47 TauType, RhoType, SigmaType, ThetaType,
50 mkSigmaTy, splitSigmaTy,
53 isUnLiftedType, isUnboxedType, isUnboxedTupleType, isAlgType, isDataType, isNewType,
57 tyVarsOfType, tyVarsOfTypes, namesOfType, typeKind,
60 -- Tidying up for printing
62 tidyOpenType, tidyOpenTypes,
63 tidyTyVar, tidyTyVars,
71 #include "HsVersions.h"
73 -- We import the representation and primitive functions from TypeRep.
74 -- Many things are reexported, but not the representation!
80 import {-# SOURCE #-} DataCon( DataCon, dataConType )
81 import {-# SOURCE #-} PprType( pprType ) -- Only called in debug messages
82 import {-# SOURCE #-} Subst ( mkTyVarSubst, substTy )
85 import Var ( TyVar, IdOrTyVar, UVar,
86 tyVarKind, tyVarName, setTyVarName, isId, idType,
91 import Name ( NamedThing(..), mkLocalName, tidyOccName,
94 import Class ( classTyCon, Class )
96 isUnboxedTupleTyCon, isUnLiftedTyCon,
97 isFunTyCon, isDataTyCon, isNewTyCon,
98 isAlgTyCon, isSynTyCon, tyConArity,
99 tyConKind, tyConDataCons, getSynTyConDefn,
100 tyConPrimRep, tyConClass_maybe
104 import SrcLoc ( noSrcLoc )
105 import Maybes ( maybeToBool )
106 import PrimRep ( PrimRep(..), isFollowableRep )
107 import Unique ( Uniquable(..) )
108 import Util ( mapAccumL, seqList )
110 import UniqSet ( sizeUniqSet ) -- Should come via VarSet
114 %************************************************************************
116 \subsection{Stuff to do with kinds.}
118 %************************************************************************
121 hasMoreBoxityInfo :: Kind -> Kind -> Bool
122 hasMoreBoxityInfo k1 k2
123 | k2 == openTypeKind = ASSERT( is_type_kind k1) True
124 | otherwise = k1 == k2
126 -- Returns true for things of form (Type x)
127 is_type_kind k = case splitTyConApp_maybe k of
128 Just (tc,[_]) -> tc == typeCon
133 %************************************************************************
135 \subsection{Constructor-specific functions}
137 %************************************************************************
140 ---------------------------------------------------------------------
144 mkTyVarTy :: TyVar -> Type
147 mkTyVarTys :: [TyVar] -> [Type]
148 mkTyVarTys = map mkTyVarTy -- a common use of mkTyVarTy
150 getTyVar :: String -> Type -> TyVar
151 getTyVar msg (TyVarTy tv) = tv
152 getTyVar msg (NoteTy _ t) = getTyVar msg t
153 getTyVar msg other = panic ("getTyVar: " ++ msg)
155 getTyVar_maybe :: Type -> Maybe TyVar
156 getTyVar_maybe (TyVarTy tv) = Just tv
157 getTyVar_maybe (NoteTy _ t) = getTyVar_maybe t
158 getTyVar_maybe other = Nothing
160 isTyVarTy :: Type -> Bool
161 isTyVarTy (TyVarTy tv) = True
162 isTyVarTy (NoteTy _ ty) = isTyVarTy ty
163 isTyVarTy other = False
167 ---------------------------------------------------------------------
170 We need to be pretty careful with AppTy to make sure we obey the
171 invariant that a TyConApp is always visibly so. mkAppTy maintains the
175 mkAppTy orig_ty1 orig_ty2 = ASSERT2( isNotUsgTy orig_ty1 && isNotUsgTy orig_ty2, pprType orig_ty1 <+> text "to" <+> pprType orig_ty2 )
178 mk_app (NoteTy _ ty1) = mk_app ty1
179 mk_app (TyConApp tc tys) = mkTyConApp tc (tys ++ [orig_ty2])
180 mk_app ty1 = AppTy orig_ty1 orig_ty2
182 mkAppTys :: Type -> [Type] -> Type
183 mkAppTys orig_ty1 [] = orig_ty1
184 -- This check for an empty list of type arguments
185 -- avoids the needless of a type synonym constructor.
186 -- For example: mkAppTys Rational []
187 -- returns to (Ratio Integer), which has needlessly lost
188 -- the Rational part.
189 mkAppTys orig_ty1 orig_tys2 = ASSERT2( isNotUsgTy orig_ty1, pprType orig_ty1 )
192 mk_app (NoteTy _ ty1) = mk_app ty1
193 mk_app (TyConApp tc tys) = mkTyConApp tc (tys ++ orig_tys2)
194 mk_app ty1 = ASSERT2( all isNotUsgTy orig_tys2, pprType orig_ty1 <+> text "to" <+> hsep (map pprType orig_tys2) )
195 foldl AppTy orig_ty1 orig_tys2
197 splitAppTy_maybe :: Type -> Maybe (Type, Type)
198 splitAppTy_maybe (FunTy ty1 ty2) = Just (TyConApp funTyCon [ty1], ty2)
199 splitAppTy_maybe (AppTy ty1 ty2) = Just (ty1, ty2)
200 splitAppTy_maybe (NoteTy _ ty) = splitAppTy_maybe ty
201 splitAppTy_maybe (TyConApp tc []) = Nothing
202 splitAppTy_maybe (TyConApp tc tys) = split tys []
204 split [ty2] acc = Just (TyConApp tc (reverse acc), ty2)
205 split (ty:tys) acc = split tys (ty:acc)
207 splitAppTy_maybe other = Nothing
209 splitAppTy :: Type -> (Type, Type)
210 splitAppTy ty = case splitAppTy_maybe ty of
212 Nothing -> panic "splitAppTy"
214 splitAppTys :: Type -> (Type, [Type])
215 splitAppTys ty = split ty ty []
217 split orig_ty (AppTy ty arg) args = split ty ty (arg:args)
218 split orig_ty (NoteTy _ ty) args = split orig_ty ty args
219 split orig_ty (FunTy ty1 ty2) args = ASSERT( null args )
220 (TyConApp funTyCon [], [ty1,ty2])
221 split orig_ty (TyConApp tc tc_args) args = (TyConApp tc [], tc_args ++ args)
222 split orig_ty ty args = (orig_ty, args)
226 ---------------------------------------------------------------------
231 mkFunTy :: Type -> Type -> Type
232 mkFunTy arg res = FunTy arg res
234 mkFunTys :: [Type] -> Type -> Type
235 mkFunTys tys ty = foldr FunTy ty tys
237 splitFunTy_maybe :: Type -> Maybe (Type, Type)
238 splitFunTy_maybe (FunTy arg res) = Just (arg, res)
239 splitFunTy_maybe (NoteTy _ ty) = splitFunTy_maybe ty
240 splitFunTy_maybe other = Nothing
242 splitFunTys :: Type -> ([Type], Type)
243 splitFunTys ty = split [] ty ty
245 split args orig_ty (FunTy arg res) = split (arg:args) res res
246 split args orig_ty (NoteTy _ ty) = split args orig_ty ty
247 split args orig_ty ty = (reverse args, orig_ty)
249 splitFunTysN :: String -> Int -> Type -> ([Type], Type)
250 splitFunTysN msg orig_n orig_ty = split orig_n [] orig_ty orig_ty
252 split 0 args syn_ty ty = (reverse args, syn_ty)
253 split n args syn_ty (FunTy arg res) = split (n-1) (arg:args) res res
254 split n args syn_ty (NoteTy _ ty) = split n args syn_ty ty
255 split n args syn_ty ty = pprPanic ("splitFunTysN: " ++ msg) (int orig_n <+> pprType orig_ty)
257 zipFunTys :: Outputable a => [a] -> Type -> ([(a,Type)], Type)
258 zipFunTys orig_xs orig_ty = split [] orig_xs orig_ty orig_ty
260 split acc [] nty ty = (reverse acc, nty)
261 split acc (x:xs) nty (FunTy arg res) = split ((x,arg):acc) xs res res
262 split acc xs nty (NoteTy _ ty) = split acc xs nty ty
263 split acc (x:xs) nty ty = pprPanic "zipFunTys" (ppr orig_xs <+> pprType orig_ty)
265 funResultTy :: Type -> Type
266 funResultTy (FunTy arg res) = res
267 funResultTy (NoteTy _ ty) = funResultTy ty
268 funResultTy ty = pprPanic "funResultTy" (pprType ty)
270 funArgTy :: Type -> Type
271 funArgTy (FunTy arg res) = arg
272 funArgTy (NoteTy _ ty) = funArgTy ty
273 funArgTy ty = pprPanic "funArgTy" (pprType ty)
277 ---------------------------------------------------------------------
282 mkTyConApp :: TyCon -> [Type] -> Type
284 | isFunTyCon tycon && length tys == 2
286 (ty1:ty2:_) -> FunTy ty1 ty2
289 = ASSERT(not (isSynTyCon tycon))
292 mkTyConTy :: TyCon -> Type
293 mkTyConTy tycon = ASSERT( not (isSynTyCon tycon) )
296 -- splitTyConApp "looks through" synonyms, because they don't
297 -- mean a distinct type, but all other type-constructor applications
298 -- including functions are returned as Just ..
300 splitTyConApp_maybe :: Type -> Maybe (TyCon, [Type])
301 splitTyConApp_maybe (TyConApp tc tys) = Just (tc, tys)
302 splitTyConApp_maybe (FunTy arg res) = Just (funTyCon, [arg,res])
303 splitTyConApp_maybe (NoteTy _ ty) = splitTyConApp_maybe ty
304 splitTyConApp_maybe other = Nothing
306 -- splitAlgTyConApp_maybe looks for
307 -- *saturated* applications of *algebraic* data types
308 -- "Algebraic" => newtype, data type, or dictionary (not function types)
309 -- We return the constructors too.
311 splitAlgTyConApp_maybe :: Type -> Maybe (TyCon, [Type], [DataCon])
312 splitAlgTyConApp_maybe (TyConApp tc tys)
314 tyConArity tc == length tys = Just (tc, tys, tyConDataCons tc)
315 splitAlgTyConApp_maybe (NoteTy _ ty) = splitAlgTyConApp_maybe ty
316 splitAlgTyConApp_maybe other = Nothing
318 splitAlgTyConApp :: Type -> (TyCon, [Type], [DataCon])
319 -- Here the "algebraic" property is an *assertion*
320 splitAlgTyConApp (TyConApp tc tys) = ASSERT( isAlgTyCon tc && tyConArity tc == length tys )
321 (tc, tys, tyConDataCons tc)
322 splitAlgTyConApp (NoteTy _ ty) = splitAlgTyConApp ty
325 "Dictionary" types are just ordinary data types, but you can
326 tell from the type constructor whether it's a dictionary or not.
329 mkDictTy :: Class -> [Type] -> Type
330 mkDictTy clas tys = TyConApp (classTyCon clas) tys
332 splitDictTy_maybe :: Type -> Maybe (Class, [Type])
333 splitDictTy_maybe (TyConApp tc tys)
334 | maybeToBool maybe_class
335 && tyConArity tc == length tys = Just (clas, tys)
337 maybe_class = tyConClass_maybe tc
338 Just clas = maybe_class
340 splitDictTy_maybe (NoteTy _ ty) = splitDictTy_maybe ty
341 splitDictTy_maybe other = Nothing
343 isDictTy :: Type -> Bool
344 -- This version is slightly more efficient than (maybeToBool . splitDictTy)
345 isDictTy (TyConApp tc tys)
346 | maybeToBool (tyConClass_maybe tc)
347 && tyConArity tc == length tys
349 isDictTy (NoteTy _ ty) = isDictTy ty
350 isDictTy other = False
353 ---------------------------------------------------------------------
358 mkSynTy syn_tycon tys
359 = ASSERT( isSynTyCon syn_tycon )
360 ASSERT( isNotUsgTy body )
361 ASSERT( length tyvars == length tys )
362 NoteTy (SynNote (TyConApp syn_tycon tys))
363 (substTy (mkTyVarSubst tyvars tys) body)
365 (tyvars, body) = getSynTyConDefn syn_tycon
367 isSynTy (NoteTy (SynNote _) _) = True
368 isSynTy other = False
370 deNoteType :: Type -> Type
371 -- Sorry for the cute name
372 deNoteType ty@(TyVarTy tyvar) = ty
373 deNoteType (TyConApp tycon tys) = TyConApp tycon (map deNoteType tys)
374 deNoteType (NoteTy _ ty) = deNoteType ty
375 deNoteType (AppTy fun arg) = AppTy (deNoteType fun) (deNoteType arg)
376 deNoteType (FunTy fun arg) = FunTy (deNoteType fun) (deNoteType arg)
377 deNoteType (ForAllTy tv ty) = ForAllTy tv (deNoteType ty)
380 Notes on type synonyms
381 ~~~~~~~~~~~~~~~~~~~~~~
382 The various "split" functions (splitFunTy, splitRhoTy, splitForAllTy) try
383 to return type synonyms whereever possible. Thus
388 splitFunTys (a -> Foo a) = ([a], Foo a)
391 The reason is that we then get better (shorter) type signatures in
392 interfaces. Notably this plays a role in tcTySigs in TcBinds.lhs.
396 repType looks through
399 in addition to synonyms. It's useful in the back end where we're not
400 interested in newtypes anymore.
403 repType :: Type -> Type
404 repType (NoteTy _ ty) = repType ty
405 repType (ForAllTy _ ty) = repType ty
406 repType (TyConApp tc tys) | isNewTyCon tc = repType (new_type_rep tc tys)
407 repType other_ty = other_ty
409 splitNewType_maybe :: Type -> Maybe Type
410 -- Find the representation of a newtype, if it is one
411 -- Looks through multiple levels of newtype
412 splitNewType_maybe (NoteTy _ ty) = splitNewType_maybe ty
413 splitNewType_maybe (TyConApp tc tys) | isNewTyCon tc = case splitNewType_maybe rep_ty of
414 Just rep_ty' -> Just rep_ty'
415 Nothing -> Just rep_ty
417 rep_ty = new_type_rep tc tys
419 splitNewType_maybe other = Nothing
421 new_type_rep :: TyCon -> [Type] -> Type
422 -- The representation type for (T t1 .. tn), where T is a newtype
423 -- Looks through one layer only
425 = ASSERT( isNewTyCon tc )
426 case splitFunTy_maybe (applyTys (dataConType (head (tyConDataCons tc))) tys) of
427 Just (rep_ty, _) -> rep_ty
432 ---------------------------------------------------------------------
436 NB: Invariant: if present, usage note is at the very top of the type.
437 This should be carefully preserved.
439 In some parts of the compiler, comments use the _Once Upon a
440 Polymorphic Type_ (POPL'99) usage of "rho = generalised
441 usage-annotated type; sigma = usage-annotated type; tau =
442 usage-annotated type except on top"; unfortunately this conflicts with
443 the rho/tau/theta/sigma usage in the rest of the compiler. (KSW
447 mkUsgTy :: UsageAnn -> Type -> Type
449 mkUsgTy UsMany ty = ASSERT2( isNotUsgTy ty, pprType ty )
452 mkUsgTy usg ty = ASSERT2( isNotUsgTy ty, pprType ty )
453 NoteTy (UsgNote usg) ty
455 -- The isUsgTy function is utterly useless if UsManys are omitted.
456 -- Be warned! KSW 1999-04.
457 isUsgTy :: Type -> Bool
461 isUsgTy (NoteTy (UsgForAll _) ty) = isUsgTy ty
462 isUsgTy (NoteTy (UsgNote _) _ ) = True
463 isUsgTy other = False
466 -- The isNotUsgTy function may return a false True if UsManys are omitted;
467 -- in other words, A SSERT( isNotUsgTy ty ) may be useful but
468 -- A SSERT( not (isNotUsg ty) ) is asking for trouble. KSW 1999-04.
469 isNotUsgTy :: Type -> Bool
470 isNotUsgTy (NoteTy (UsgForAll _) _) = False
471 isNotUsgTy (NoteTy (UsgNote _) _) = False
472 isNotUsgTy other = True
474 -- splitUsgTy_maybe is not exported, since it is meaningless if
475 -- UsManys are omitted. It is used in several places in this module,
476 -- however. KSW 1999-04.
477 splitUsgTy_maybe :: Type -> Maybe (UsageAnn,Type)
478 splitUsgTy_maybe (NoteTy (UsgNote usg) ty2) = ASSERT( isNotUsgTy ty2 )
480 splitUsgTy_maybe ty@(NoteTy (UsgForAll _) _) = pprPanic "splitUsgTy_maybe:" $ pprType ty
481 splitUsgTy_maybe ty = Nothing
483 splitUsgTy :: Type -> (UsageAnn,Type)
484 splitUsgTy ty = case splitUsgTy_maybe ty of
490 pprPanic "splitUsgTy: no usage annot:" $ pprType ty
493 tyUsg :: Type -> UsageAnn
494 tyUsg = fst . splitUsgTy
496 unUsgTy :: Type -> Type
497 -- strip outer usage annotation if present
498 unUsgTy ty = case splitUsgTy_maybe ty of
499 Just (_,ty1) -> ASSERT2( isNotUsgTy ty1, pprType ty )
503 mkUsForAllTy :: UVar -> Type -> Type
504 mkUsForAllTy uv ty = NoteTy (UsgForAll uv) ty
506 mkUsForAllTys :: [UVar] -> Type -> Type
507 mkUsForAllTys uvs ty = foldr (NoteTy . UsgForAll) ty uvs
509 splitUsForAllTys :: Type -> ([UVar],Type)
510 splitUsForAllTys ty = split ty []
511 where split (NoteTy (UsgForAll u) ty) uvs = split ty (u:uvs)
512 split other_ty uvs = (reverse uvs, other_ty)
514 substUsTy :: VarEnv UsageAnn -> Type -> Type
515 -- assumes range is fresh uvars, so no conflicts
516 substUsTy ve (NoteTy note@(UsgNote (UsVar u))
517 ty ) = NoteTy (case lookupVarEnv ve u of
518 Just ua -> UsgNote ua
521 substUsTy ve (NoteTy note@(UsgNote _) ty ) = NoteTy note (substUsTy ve ty)
522 substUsTy ve (NoteTy note@(UsgForAll _) ty ) = NoteTy note (substUsTy ve ty)
523 substUsTy ve (NoteTy (SynNote ty1) ty2) = NoteTy (SynNote (substUsTy ve ty1))
525 substUsTy ve (NoteTy note@(FTVNote _) ty ) = NoteTy note (substUsTy ve ty)
526 substUsTy ve ty@(TyVarTy _ ) = ty
527 substUsTy ve (AppTy ty1 ty2) = AppTy (substUsTy ve ty1)
529 substUsTy ve (FunTy ty1 ty2) = FunTy (substUsTy ve ty1)
531 substUsTy ve (TyConApp tyc tys) = TyConApp tyc (map (substUsTy ve) tys)
532 substUsTy ve (ForAllTy yv ty ) = ForAllTy yv (substUsTy ve ty)
536 ---------------------------------------------------------------------
540 We need to be clever here with usage annotations; they need to be
541 lifted or lowered through the forall as appropriate.
544 mkForAllTy :: TyVar -> Type -> Type
545 mkForAllTy tyvar ty = case splitUsgTy_maybe ty of
546 Just (usg,ty') -> NoteTy (UsgNote usg)
548 Nothing -> ForAllTy tyvar ty
550 mkForAllTys :: [TyVar] -> Type -> Type
551 mkForAllTys tyvars ty = case splitUsgTy_maybe ty of
552 Just (usg,ty') -> NoteTy (UsgNote usg)
553 (foldr ForAllTy ty' tyvars)
554 Nothing -> foldr ForAllTy ty tyvars
556 splitForAllTy_maybe :: Type -> Maybe (TyVar, Type)
557 splitForAllTy_maybe ty = case splitUsgTy_maybe ty of
558 Just (usg,ty') -> do (tyvar,ty'') <- splitFAT_m ty'
559 return (tyvar, NoteTy (UsgNote usg) ty'')
560 Nothing -> splitFAT_m ty
562 splitFAT_m (NoteTy _ ty) = splitFAT_m ty
563 splitFAT_m (ForAllTy tyvar ty) = Just(tyvar, ty)
564 splitFAT_m _ = Nothing
566 isForAllTy :: Type -> Bool
567 isForAllTy (NoteTy _ ty) = isForAllTy ty
568 isForAllTy (ForAllTy tyvar ty) = True
571 splitForAllTys :: Type -> ([TyVar], Type)
572 splitForAllTys ty = case splitUsgTy_maybe ty of
573 Just (usg,ty') -> let (tvs,ty'') = split ty' ty' []
574 in (tvs, NoteTy (UsgNote usg) ty'')
575 Nothing -> split ty ty []
577 split orig_ty (ForAllTy tv ty) tvs = split ty ty (tv:tvs)
578 split orig_ty (NoteTy _ ty) tvs = split orig_ty ty tvs
579 split orig_ty t tvs = (reverse tvs, orig_ty)
582 @mkPiType@ makes a (->) type or a forall type, depending on whether
583 it is given a type variable or a term variable.
586 mkPiType :: IdOrTyVar -> Type -> Type -- The more polymorphic version doesn't work...
587 mkPiType v ty | isId v = mkFunTy (idType v) ty
588 | otherwise = mkForAllTy v ty
591 Applying a for-all to its arguments
594 applyTy :: Type -> Type -> Type
595 applyTy (NoteTy note@(UsgNote _) fun) arg = NoteTy note (applyTy fun arg)
596 applyTy (NoteTy note@(UsgForAll _) fun) arg = NoteTy note (applyTy fun arg)
597 applyTy (NoteTy _ fun) arg = applyTy fun arg
598 applyTy (ForAllTy tv ty) arg = ASSERT( isNotUsgTy arg )
599 substTy (mkTyVarSubst [tv] [arg]) ty
600 applyTy other arg = panic "applyTy"
602 applyTys :: Type -> [Type] -> Type
603 applyTys fun_ty arg_tys
604 = substTy (mkTyVarSubst tvs arg_tys) ty
606 (tvs, ty) = split fun_ty arg_tys
608 split fun_ty [] = ([], fun_ty)
609 split (NoteTy note@(UsgNote _) fun_ty)
610 args = case split fun_ty args of
611 (tvs, ty) -> (tvs, NoteTy note ty)
612 split (NoteTy note@(UsgForAll _) fun_ty)
613 args = case split fun_ty args of
614 (tvs, ty) -> (tvs, NoteTy note ty)
615 split (NoteTy _ fun_ty) args = split fun_ty args
616 split (ForAllTy tv fun_ty) (arg:args) = ASSERT2( isNotUsgTy arg, vcat (map pprType arg_tys) $$
617 text "in application of" <+> pprType fun_ty)
618 case split fun_ty args of
619 (tvs, ty) -> (tv:tvs, ty)
620 split other_ty args = panic "applyTys"
623 Note that we allow applications to be of usage-annotated- types, as an
624 extension: we handle them by lifting the annotation outside. The
625 argument, however, must still be unannotated.
628 %************************************************************************
630 \subsection{Stuff to do with the source-language types}
632 %************************************************************************
637 type ThetaType = [(Class, [Type])]
638 type SigmaType = Type
641 @isTauTy@ tests for nested for-alls.
644 isTauTy :: Type -> Bool
645 isTauTy (TyVarTy v) = True
646 isTauTy (TyConApp _ tys) = all isTauTy tys
647 isTauTy (AppTy a b) = isTauTy a && isTauTy b
648 isTauTy (FunTy a b) = isTauTy a && isTauTy b
649 isTauTy (NoteTy _ ty) = isTauTy ty
650 isTauTy other = False
654 mkRhoTy :: [(Class, [Type])] -> Type -> Type
655 mkRhoTy theta ty = foldr (\(c,t) r -> FunTy (mkDictTy c t) r) ty theta
657 splitRhoTy :: Type -> ([(Class, [Type])], Type)
658 splitRhoTy ty = split ty ty []
660 split orig_ty (FunTy arg res) ts = case splitDictTy_maybe arg of
661 Just pair -> split res res (pair:ts)
662 Nothing -> (reverse ts, orig_ty)
663 split orig_ty (NoteTy _ ty) ts = split orig_ty ty ts
664 split orig_ty ty ts = (reverse ts, orig_ty)
670 mkSigmaTy tyvars theta tau = mkForAllTys tyvars (mkRhoTy theta tau)
672 splitSigmaTy :: Type -> ([TyVar], [(Class, [Type])], Type)
676 (tyvars,rho) = splitForAllTys ty
677 (theta,tau) = splitRhoTy rho
681 %************************************************************************
683 \subsection{Kinds and free variables}
685 %************************************************************************
687 ---------------------------------------------------------------------
688 Finding the kind of a type
689 ~~~~~~~~~~~~~~~~~~~~~~~~~~
691 typeKind :: Type -> Kind
693 typeKind (TyVarTy tyvar) = tyVarKind tyvar
694 typeKind (TyConApp tycon tys) = foldr (\_ k -> funResultTy k) (tyConKind tycon) tys
695 typeKind (NoteTy _ ty) = typeKind ty
696 typeKind (AppTy fun arg) = funResultTy (typeKind fun)
698 typeKind (FunTy arg res) = boxedTypeKind -- A function is boxed regardless of its result type
699 -- No functions at the type level, hence we don't need
700 -- to say (typeKind res).
702 typeKind (ForAllTy tv ty) = typeKind ty
706 ---------------------------------------------------------------------
707 Free variables of a type
708 ~~~~~~~~~~~~~~~~~~~~~~~~
710 tyVarsOfType :: Type -> TyVarSet
712 tyVarsOfType (TyVarTy tv) = unitVarSet tv
713 tyVarsOfType (TyConApp tycon tys) = tyVarsOfTypes tys
714 tyVarsOfType (NoteTy (FTVNote tvs) ty2) = tvs
715 tyVarsOfType (NoteTy (SynNote ty1) ty2) = tyVarsOfType ty1
716 tyVarsOfType (NoteTy (UsgNote _) ty) = tyVarsOfType ty
717 tyVarsOfType (NoteTy (UsgForAll _) ty) = tyVarsOfType ty
718 tyVarsOfType (FunTy arg res) = tyVarsOfType arg `unionVarSet` tyVarsOfType res
719 tyVarsOfType (AppTy fun arg) = tyVarsOfType fun `unionVarSet` tyVarsOfType arg
720 tyVarsOfType (ForAllTy tyvar ty) = tyVarsOfType ty `minusVarSet` unitVarSet tyvar
722 tyVarsOfTypes :: [Type] -> TyVarSet
723 tyVarsOfTypes tys = foldr (unionVarSet.tyVarsOfType) emptyVarSet tys
725 -- Add a Note with the free tyvars to the top of the type
726 -- (but under a usage if there is one)
727 addFreeTyVars :: Type -> Type
728 addFreeTyVars (NoteTy note@(UsgNote _) ty) = NoteTy note (addFreeTyVars ty)
729 addFreeTyVars (NoteTy note@(UsgForAll _) ty) = NoteTy note (addFreeTyVars ty)
730 addFreeTyVars ty@(NoteTy (FTVNote _) _) = ty
731 addFreeTyVars ty = NoteTy (FTVNote (tyVarsOfType ty)) ty
733 -- Find the free names of a type, including the type constructors and classes it mentions
734 namesOfType :: Type -> NameSet
735 namesOfType (TyVarTy tv) = unitNameSet (getName tv)
736 namesOfType (TyConApp tycon tys) = unitNameSet (getName tycon) `unionNameSets`
738 namesOfType (NoteTy (SynNote ty1) ty2) = namesOfType ty1
739 namesOfType (NoteTy other_note ty2) = namesOfType ty2
740 namesOfType (FunTy arg res) = namesOfType arg `unionNameSets` namesOfType res
741 namesOfType (AppTy fun arg) = namesOfType fun `unionNameSets` namesOfType arg
742 namesOfType (ForAllTy tyvar ty) = namesOfType ty `minusNameSet` unitNameSet (getName tyvar)
744 namesOfTypes tys = foldr (unionNameSets . namesOfType) emptyNameSet tys
748 %************************************************************************
750 \subsection{TidyType}
752 %************************************************************************
754 tidyTy tidies up a type for printing in an error message, or in
757 It doesn't change the uniques at all, just the print names.
760 tidyTyVar :: TidyEnv -> TyVar -> (TidyEnv, TyVar)
761 tidyTyVar env@(tidy_env, subst) tyvar
762 = case lookupVarEnv subst tyvar of
764 Just tyvar' -> -- Already substituted
767 Nothing -> -- Make a new nice name for it
769 case tidyOccName tidy_env (getOccName name) of
770 (tidy', occ') -> -- New occname reqd
771 ((tidy', subst'), tyvar')
773 subst' = extendVarEnv subst tyvar tyvar'
774 tyvar' = setTyVarName tyvar name'
775 name' = mkLocalName (getUnique name) occ' noSrcLoc
776 -- Note: make a *user* tyvar, so it printes nicely
777 -- Could extract src loc, but no need.
779 name = tyVarName tyvar
781 tidyTyVars env tyvars = mapAccumL tidyTyVar env tyvars
783 tidyType :: TidyEnv -> Type -> Type
784 tidyType env@(tidy_env, subst) ty
787 go (TyVarTy tv) = case lookupVarEnv subst tv of
788 Nothing -> TyVarTy tv
789 Just tv' -> TyVarTy tv'
790 go (TyConApp tycon tys) = let args = map go tys
791 in args `seqList` TyConApp tycon args
792 go (NoteTy note ty) = (NoteTy $! (go_note note)) $! (go ty)
793 go (AppTy fun arg) = (AppTy $! (go fun)) $! (go arg)
794 go (FunTy fun arg) = (FunTy $! (go fun)) $! (go arg)
795 go (ForAllTy tv ty) = ForAllTy tv' $! (tidyType env' ty)
797 (env', tv') = tidyTyVar env tv
799 go_note (SynNote ty) = SynNote $! (go ty)
800 go_note note@(FTVNote ftvs) = note -- No need to tidy the free tyvars
801 go_note note@(UsgNote _) = note -- Usage annotation is already tidy
802 go_note note@(UsgForAll _) = note -- Uvar binder is already tidy
804 tidyTypes env tys = map (tidyType env) tys
808 @tidyOpenType@ grabs the free type varibles, tidies them
809 and then uses @tidyType@ to work over the type itself
812 tidyOpenType :: TidyEnv -> Type -> (TidyEnv, Type)
814 = (env', tidyType env' ty)
816 env' = foldl go env (varSetElems (tyVarsOfType ty))
817 go env tyvar = fst (tidyTyVar env tyvar)
819 tidyOpenTypes :: TidyEnv -> [Type] -> (TidyEnv, [Type])
820 tidyOpenTypes env tys = mapAccumL tidyOpenType env tys
822 tidyTopType :: Type -> Type
823 tidyTopType ty = tidyType emptyTidyEnv ty
827 %************************************************************************
829 \subsection{Boxedness and liftedness}
831 %************************************************************************
834 isUnboxedType :: Type -> Bool
835 isUnboxedType ty = not (isFollowableRep (typePrimRep ty))
837 isUnLiftedType :: Type -> Bool
838 isUnLiftedType ty = case splitTyConApp_maybe ty of
839 Just (tc, ty_args) -> isUnLiftedTyCon tc
842 isUnboxedTupleType :: Type -> Bool
843 isUnboxedTupleType ty = case splitTyConApp_maybe ty of
844 Just (tc, ty_args) -> isUnboxedTupleTyCon tc
847 -- Should only be applied to *types*; hence the assert
848 isAlgType :: Type -> Bool
849 isAlgType ty = case splitTyConApp_maybe ty of
850 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
854 -- Should only be applied to *types*; hence the assert
855 isDataType :: Type -> Bool
856 isDataType ty = case splitTyConApp_maybe ty of
857 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
861 isNewType :: Type -> Bool
862 isNewType ty = case splitTyConApp_maybe ty of
863 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
867 typePrimRep :: Type -> PrimRep
868 typePrimRep ty = case splitTyConApp_maybe ty of
869 Just (tc, ty_args) -> tyConPrimRep tc
874 %************************************************************************
876 \subsection{Sequencing on types
878 %************************************************************************
881 seqType :: Type -> ()
882 seqType (TyVarTy tv) = tv `seq` ()
883 seqType (AppTy t1 t2) = seqType t1 `seq` seqType t2
884 seqType (FunTy t1 t2) = seqType t1 `seq` seqType t2
885 seqType (NoteTy note t2) = seqNote note `seq` seqType t2
886 seqType (TyConApp tc tys) = tc `seq` seqTypes tys
887 seqType (ForAllTy tv ty) = tv `seq` seqType ty
889 seqTypes :: [Type] -> ()
891 seqTypes (ty:tys) = seqType ty `seq` seqTypes tys
893 seqNote :: TyNote -> ()
894 seqNote (SynNote ty) = seqType ty
895 seqNote (FTVNote set) = sizeUniqSet set `seq` ()
896 seqNote (UsgNote usg) = usg `seq` ()