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, -- mentioned below: hasMoreBoxityInfo,
25 -- exports from this module:
28 mkTyVarTy, mkTyVarTys, getTyVar, getTyVar_maybe, isTyVarTy,
30 mkAppTy, mkAppTys, splitAppTy, splitAppTys, splitAppTy_maybe,
32 mkFunTy, mkFunTys, splitFunTy, splitFunTy_maybe, splitFunTys, splitFunTysN,
33 funResultTy, funArgTy, zipFunTys,
35 mkTyConApp, mkTyConTy, splitTyConApp_maybe,
36 splitAlgTyConApp_maybe, splitAlgTyConApp,
37 mkDictTy, mkPredTy, splitPredTy_maybe, splitDictTy_maybe, isDictTy,
39 mkSynTy, isSynTy, deNoteType,
41 repType, splitRepFunTys, splitNewType_maybe, typePrimRep,
43 UsageAnn(..), mkUsgTy, isUsgTy{- dont use -}, isNotUsgTy, splitUsgTy, unUsgTy, tyUsg,
44 mkUsForAllTy, mkUsForAllTys, splitUsForAllTys, substUsTy,
46 mkForAllTy, mkForAllTys, splitForAllTy_maybe, splitForAllTys,
47 isForAllTy, applyTy, applyTys, mkPiType, hoistForAllTys,
49 TauType, RhoType, SigmaType, PredType(..), ThetaType,
50 ClassPred, ClassContext, mkClassPred,
51 getClassTys_maybe, ipName_maybe, classesToPreds, classesOfPreds,
52 isTauTy, mkRhoTy, splitRhoTy,
53 mkSigmaTy, splitSigmaTy,
56 isUnLiftedType, isUnboxedType, isUnboxedTupleType, isAlgType, isDataType, isNewType,
59 tyVarsOfType, tyVarsOfTypes, tyVarsOfPred, tyVarsOfTheta,
60 namesOfType, typeKind, addFreeTyVars,
62 -- Tidying up for printing
64 tidyOpenType, tidyOpenTypes,
65 tidyTyVar, tidyTyVars,
73 #include "HsVersions.h"
75 -- We import the representation and primitive functions from TypeRep.
76 -- Many things are reexported, but not the representation!
82 import {-# SOURCE #-} DataCon( DataCon, dataConRepType )
83 import {-# SOURCE #-} PprType( pprType, pprPred ) -- Only called in debug messages
84 import {-# SOURCE #-} Subst ( mkTyVarSubst, substTy )
87 import Var ( TyVar, Var, UVar,
88 tyVarKind, tyVarName, setTyVarName, isId, idType,
93 import Name ( Name, NamedThing(..), mkLocalName, tidyOccName
96 import Class ( classTyCon, Class )
98 isUnboxedTupleTyCon, isUnLiftedTyCon,
99 isFunTyCon, isDataTyCon, isNewTyCon, newTyConRep,
100 isAlgTyCon, isSynTyCon, tyConArity,
101 tyConKind, tyConDataCons, getSynTyConDefn,
102 tyConPrimRep, tyConClass_maybe
106 import SrcLoc ( noSrcLoc )
107 import Maybes ( maybeToBool )
108 import PrimRep ( PrimRep(..), isFollowableRep )
109 import Unique ( Uniquable(..) )
110 import Util ( mapAccumL, seqList )
112 import UniqSet ( sizeUniqSet ) -- Should come via VarSet
116 %************************************************************************
118 \subsection{Stuff to do with kinds.}
120 %************************************************************************
123 hasMoreBoxityInfo :: Kind -> Kind -> Bool
124 hasMoreBoxityInfo k1 k2
125 | k2 == openTypeKind = ASSERT( is_type_kind k1) True
126 | otherwise = k1 == k2
128 -- Returns true for things of form (Type x)
129 is_type_kind k = case splitTyConApp_maybe k of
130 Just (tc,[_]) -> tc == typeCon
135 %************************************************************************
137 \subsection{Constructor-specific functions}
139 %************************************************************************
142 ---------------------------------------------------------------------
146 mkTyVarTy :: TyVar -> Type
149 mkTyVarTys :: [TyVar] -> [Type]
150 mkTyVarTys = map mkTyVarTy -- a common use of mkTyVarTy
152 getTyVar :: String -> Type -> TyVar
153 getTyVar msg (TyVarTy tv) = tv
154 getTyVar msg (NoteTy _ t) = getTyVar msg t
155 getTyVar msg other = panic ("getTyVar: " ++ msg)
157 getTyVar_maybe :: Type -> Maybe TyVar
158 getTyVar_maybe (TyVarTy tv) = Just tv
159 getTyVar_maybe (NoteTy _ t) = getTyVar_maybe t
160 getTyVar_maybe other = Nothing
162 isTyVarTy :: Type -> Bool
163 isTyVarTy (TyVarTy tv) = True
164 isTyVarTy (NoteTy _ ty) = isTyVarTy ty
165 isTyVarTy other = False
169 ---------------------------------------------------------------------
172 We need to be pretty careful with AppTy to make sure we obey the
173 invariant that a TyConApp is always visibly so. mkAppTy maintains the
177 mkAppTy orig_ty1 orig_ty2 = ASSERT2( isNotUsgTy orig_ty1 && isNotUsgTy orig_ty2, pprType orig_ty1 <+> text "to" <+> pprType orig_ty2 )
180 mk_app (NoteTy _ ty1) = mk_app ty1
181 mk_app (TyConApp tc tys) = mkTyConApp tc (tys ++ [orig_ty2])
182 mk_app ty1 = AppTy orig_ty1 orig_ty2
184 mkAppTys :: Type -> [Type] -> Type
185 mkAppTys orig_ty1 [] = orig_ty1
186 -- This check for an empty list of type arguments
187 -- avoids the needless of a type synonym constructor.
188 -- For example: mkAppTys Rational []
189 -- returns to (Ratio Integer), which has needlessly lost
190 -- the Rational part.
191 mkAppTys orig_ty1 orig_tys2 = ASSERT2( isNotUsgTy orig_ty1, pprType orig_ty1 )
194 mk_app (NoteTy _ ty1) = mk_app ty1
195 mk_app (TyConApp tc tys) = mkTyConApp tc (tys ++ orig_tys2)
196 mk_app ty1 = ASSERT2( all isNotUsgTy orig_tys2, pprType orig_ty1 <+> text "to" <+> hsep (map pprType orig_tys2) )
197 foldl AppTy orig_ty1 orig_tys2
199 splitAppTy_maybe :: Type -> Maybe (Type, Type)
200 splitAppTy_maybe (FunTy ty1 ty2) = Just (TyConApp funTyCon [ty1], ty2)
201 splitAppTy_maybe (AppTy ty1 ty2) = Just (ty1, ty2)
202 splitAppTy_maybe (NoteTy _ ty) = splitAppTy_maybe ty
203 splitAppTy_maybe (TyConApp tc []) = Nothing
204 splitAppTy_maybe (TyConApp tc tys) = split tys []
206 split [ty2] acc = Just (TyConApp tc (reverse acc), ty2)
207 split (ty:tys) acc = split tys (ty:acc)
209 splitAppTy_maybe other = Nothing
211 splitAppTy :: Type -> (Type, Type)
212 splitAppTy ty = case splitAppTy_maybe ty of
214 Nothing -> panic "splitAppTy"
216 splitAppTys :: Type -> (Type, [Type])
217 splitAppTys ty = split ty ty []
219 split orig_ty (AppTy ty arg) args = split ty ty (arg:args)
220 split orig_ty (NoteTy _ ty) args = split orig_ty ty args
221 split orig_ty (FunTy ty1 ty2) args = ASSERT( null args )
222 (TyConApp funTyCon [], [ty1,ty2])
223 split orig_ty (TyConApp tc tc_args) args = (TyConApp tc [], tc_args ++ args)
224 split orig_ty ty args = (orig_ty, args)
228 ---------------------------------------------------------------------
233 mkFunTy :: Type -> Type -> Type
234 mkFunTy arg res = FunTy arg res
236 mkFunTys :: [Type] -> Type -> Type
237 mkFunTys tys ty = foldr FunTy ty tys
239 splitFunTy :: Type -> (Type, Type)
240 splitFunTy (FunTy arg res) = (arg, res)
241 splitFunTy (NoteTy _ ty) = splitFunTy ty
243 splitFunTy_maybe :: Type -> Maybe (Type, Type)
244 splitFunTy_maybe (FunTy arg res) = Just (arg, res)
245 splitFunTy_maybe (NoteTy _ ty) = splitFunTy_maybe ty
246 splitFunTy_maybe other = Nothing
248 splitFunTys :: Type -> ([Type], Type)
249 splitFunTys ty = split [] ty ty
251 split args orig_ty (FunTy arg res) = split (arg:args) res res
252 split args orig_ty (NoteTy _ ty) = split args orig_ty ty
253 split args orig_ty ty = (reverse args, orig_ty)
255 splitFunTysN :: String -> Int -> Type -> ([Type], Type)
256 splitFunTysN msg orig_n orig_ty = split orig_n [] orig_ty orig_ty
258 split 0 args syn_ty ty = (reverse args, syn_ty)
259 split n args syn_ty (FunTy arg res) = split (n-1) (arg:args) res res
260 split n args syn_ty (NoteTy _ ty) = split n args syn_ty ty
261 split n args syn_ty ty = pprPanic ("splitFunTysN: " ++ msg) (int orig_n <+> pprType orig_ty)
263 zipFunTys :: Outputable a => [a] -> Type -> ([(a,Type)], Type)
264 zipFunTys orig_xs orig_ty = split [] orig_xs orig_ty orig_ty
266 split acc [] nty ty = (reverse acc, nty)
267 split acc (x:xs) nty (FunTy arg res) = split ((x,arg):acc) xs res res
268 split acc xs nty (NoteTy _ ty) = split acc xs nty ty
269 split acc (x:xs) nty ty = pprPanic "zipFunTys" (ppr orig_xs <+> pprType orig_ty)
271 funResultTy :: Type -> Type
272 funResultTy (FunTy arg res) = res
273 funResultTy (NoteTy _ ty) = funResultTy ty
274 funResultTy ty = pprPanic "funResultTy" (pprType ty)
276 funArgTy :: Type -> Type
277 funArgTy (FunTy arg res) = arg
278 funArgTy (NoteTy _ ty) = funArgTy ty
279 funArgTy ty = pprPanic "funArgTy" (pprType ty)
283 ---------------------------------------------------------------------
288 mkTyConApp :: TyCon -> [Type] -> Type
290 | isFunTyCon tycon && length tys == 2
292 (ty1:ty2:_) -> FunTy ty1 ty2
295 = ASSERT(not (isSynTyCon tycon))
298 mkTyConTy :: TyCon -> Type
299 mkTyConTy tycon = ASSERT( not (isSynTyCon tycon) )
302 -- splitTyConApp "looks through" synonyms, because they don't
303 -- mean a distinct type, but all other type-constructor applications
304 -- including functions are returned as Just ..
306 splitTyConApp_maybe :: Type -> Maybe (TyCon, [Type])
307 splitTyConApp_maybe (TyConApp tc tys) = Just (tc, tys)
308 splitTyConApp_maybe (FunTy arg res) = Just (funTyCon, [arg,res])
309 splitTyConApp_maybe (NoteTy _ ty) = splitTyConApp_maybe ty
310 splitTyConApp_maybe other = Nothing
312 -- splitAlgTyConApp_maybe looks for
313 -- *saturated* applications of *algebraic* data types
314 -- "Algebraic" => newtype, data type, or dictionary (not function types)
315 -- We return the constructors too.
317 splitAlgTyConApp_maybe :: Type -> Maybe (TyCon, [Type], [DataCon])
318 splitAlgTyConApp_maybe (TyConApp tc tys)
320 tyConArity tc == length tys = Just (tc, tys, tyConDataCons tc)
321 splitAlgTyConApp_maybe (NoteTy _ ty) = splitAlgTyConApp_maybe ty
322 splitAlgTyConApp_maybe other = Nothing
324 splitAlgTyConApp :: Type -> (TyCon, [Type], [DataCon])
325 -- Here the "algebraic" property is an *assertion*
326 splitAlgTyConApp (TyConApp tc tys) = ASSERT( isAlgTyCon tc && tyConArity tc == length tys )
327 (tc, tys, tyConDataCons tc)
328 splitAlgTyConApp (NoteTy _ ty) = splitAlgTyConApp ty
331 "Dictionary" types are just ordinary data types, but you can
332 tell from the type constructor whether it's a dictionary or not.
335 mkDictTy :: Class -> [Type] -> Type
336 mkDictTy clas tys = TyConApp (classTyCon clas) tys
338 mkPredTy :: PredType -> Type
339 mkPredTy (Class clas tys) = TyConApp (classTyCon clas) tys
340 mkPredTy (IParam n ty) = NoteTy (IPNote n) ty
343 splitDictTy_maybe :: Type -> Maybe (Class, [Type])
344 splitDictTy_maybe (TyConApp tc tys)
345 | maybeToBool maybe_class
346 && tyConArity tc == length tys = Just (clas, tys)
348 maybe_class = tyConClass_maybe tc
349 Just clas = maybe_class
351 splitDictTy_maybe (NoteTy _ ty) = splitDictTy_maybe ty
352 splitDictTy_maybe other = Nothing
355 splitPredTy_maybe :: Type -> Maybe PredType
356 splitPredTy_maybe (TyConApp tc tys)
357 | maybeToBool maybe_class
358 && tyConArity tc == length tys = Just (Class clas tys)
360 maybe_class = tyConClass_maybe tc
361 Just clas = maybe_class
363 splitPredTy_maybe (NoteTy (IPNote n) ty)
365 splitPredTy_maybe (NoteTy _ ty) = splitPredTy_maybe ty
366 splitPredTy_maybe other = Nothing
368 splitDictTy_maybe :: Type -> Maybe (Class, [Type])
370 = case splitPredTy_maybe ty of
371 Just p -> getClassTys_maybe p
374 isDictTy :: Type -> Bool
375 -- This version is slightly more efficient than (maybeToBool . splitDictTy)
376 isDictTy (TyConApp tc tys)
377 | maybeToBool (tyConClass_maybe tc)
378 && tyConArity tc == length tys
380 isDictTy (NoteTy _ ty) = isDictTy ty
381 isDictTy other = False
384 ---------------------------------------------------------------------
389 mkSynTy syn_tycon tys
390 = ASSERT( isSynTyCon syn_tycon )
391 ASSERT( isNotUsgTy body )
392 ASSERT( length tyvars == length tys )
393 NoteTy (SynNote (TyConApp syn_tycon tys))
394 (substTy (mkTyVarSubst tyvars tys) body)
396 (tyvars, body) = getSynTyConDefn syn_tycon
398 isSynTy (NoteTy (SynNote _) _) = True
399 isSynTy other = False
401 deNoteType :: Type -> Type
402 -- Sorry for the cute name
403 deNoteType ty@(TyVarTy tyvar) = ty
404 deNoteType (TyConApp tycon tys) = TyConApp tycon (map deNoteType tys)
405 deNoteType (NoteTy _ ty) = deNoteType ty
406 deNoteType (AppTy fun arg) = AppTy (deNoteType fun) (deNoteType arg)
407 deNoteType (FunTy fun arg) = FunTy (deNoteType fun) (deNoteType arg)
408 deNoteType (ForAllTy tv ty) = ForAllTy tv (deNoteType ty)
411 Notes on type synonyms
412 ~~~~~~~~~~~~~~~~~~~~~~
413 The various "split" functions (splitFunTy, splitRhoTy, splitForAllTy) try
414 to return type synonyms whereever possible. Thus
419 splitFunTys (a -> Foo a) = ([a], Foo a)
422 The reason is that we then get better (shorter) type signatures in
423 interfaces. Notably this plays a role in tcTySigs in TcBinds.lhs.
429 repType looks through
433 It's useful in the back end where we're not
434 interested in newtypes anymore.
437 repType :: Type -> Type
438 repType (ForAllTy _ ty) = repType ty
439 repType (NoteTy _ ty) = repType ty
440 repType ty = case splitNewType_maybe ty of
441 Just ty' -> repType ty' -- Still re-apply repType in case of for-all
444 splitRepFunTys :: Type -> ([Type], Type)
445 -- Like splitFunTys, but looks through newtypes and for-alls
446 splitRepFunTys ty = split [] (repType ty)
448 split args (FunTy arg res) = split (arg:args) (repType res)
449 split args ty = (reverse args, ty)
451 typePrimRep :: Type -> PrimRep
452 typePrimRep ty = case repType ty of
453 TyConApp tc _ -> tyConPrimRep tc
455 AppTy _ _ -> PtrRep -- ??
458 splitNewType_maybe :: Type -> Maybe Type
459 -- Find the representation of a newtype, if it is one
460 -- Looks through multiple levels of newtype, but does not look through for-alls
461 splitNewType_maybe (NoteTy _ ty) = splitNewType_maybe ty
462 splitNewType_maybe (TyConApp tc tys) = case newTyConRep tc of
463 Just rep_ty -> ASSERT( length tys == tyConArity tc )
464 -- The assert should hold because repType should
465 -- only be applied to *types* (of kind *)
466 Just (applyTys rep_ty tys)
468 splitNewType_maybe other = Nothing
473 ---------------------------------------------------------------------
477 NB: Invariant: if present, usage note is at the very top of the type.
478 This should be carefully preserved.
480 In some parts of the compiler, comments use the _Once Upon a
481 Polymorphic Type_ (POPL'99) usage of "rho = generalised
482 usage-annotated type; sigma = usage-annotated type; tau =
483 usage-annotated type except on top"; unfortunately this conflicts with
484 the rho/tau/theta/sigma usage in the rest of the compiler. (KSW
488 mkUsgTy :: UsageAnn -> Type -> Type
490 mkUsgTy UsMany ty = ASSERT2( isNotUsgTy ty, pprType ty )
493 mkUsgTy usg ty = ASSERT2( isNotUsgTy ty, pprType ty )
494 NoteTy (UsgNote usg) ty
496 -- The isUsgTy function is utterly useless if UsManys are omitted.
497 -- Be warned! KSW 1999-04.
498 isUsgTy :: Type -> Bool
502 isUsgTy (NoteTy (UsgForAll _) ty) = isUsgTy ty
503 isUsgTy (NoteTy (UsgNote _) _ ) = True
504 isUsgTy other = False
507 -- The isNotUsgTy function may return a false True if UsManys are omitted;
508 -- in other words, A SSERT( isNotUsgTy ty ) may be useful but
509 -- A SSERT( not (isNotUsg ty) ) is asking for trouble. KSW 1999-04.
510 isNotUsgTy :: Type -> Bool
511 isNotUsgTy (NoteTy (UsgForAll _) _) = False
512 isNotUsgTy (NoteTy (UsgNote _) _) = False
513 isNotUsgTy other = True
515 -- splitUsgTy_maybe is not exported, since it is meaningless if
516 -- UsManys are omitted. It is used in several places in this module,
517 -- however. KSW 1999-04.
518 splitUsgTy_maybe :: Type -> Maybe (UsageAnn,Type)
519 splitUsgTy_maybe (NoteTy (UsgNote usg) ty2) = ASSERT( isNotUsgTy ty2 )
521 splitUsgTy_maybe ty@(NoteTy (UsgForAll _) _) = pprPanic "splitUsgTy_maybe:" $ pprType ty
522 splitUsgTy_maybe ty = Nothing
524 splitUsgTy :: Type -> (UsageAnn,Type)
525 splitUsgTy ty = case splitUsgTy_maybe ty of
531 pprPanic "splitUsgTy: no usage annot:" $ pprType ty
534 tyUsg :: Type -> UsageAnn
535 tyUsg = fst . splitUsgTy
537 unUsgTy :: Type -> Type
538 -- strip outer usage annotation if present
539 unUsgTy ty = case splitUsgTy_maybe ty of
540 Just (_,ty1) -> ASSERT2( isNotUsgTy ty1, pprType ty )
544 mkUsForAllTy :: UVar -> Type -> Type
545 mkUsForAllTy uv ty = NoteTy (UsgForAll uv) ty
547 mkUsForAllTys :: [UVar] -> Type -> Type
548 mkUsForAllTys uvs ty = foldr (NoteTy . UsgForAll) ty uvs
550 splitUsForAllTys :: Type -> ([UVar],Type)
551 splitUsForAllTys ty = split ty []
552 where split (NoteTy (UsgForAll u) ty) uvs = split ty (u:uvs)
553 split other_ty uvs = (reverse uvs, other_ty)
555 substUsTy :: VarEnv UsageAnn -> Type -> Type
556 -- assumes range is fresh uvars, so no conflicts
557 substUsTy ve (NoteTy note@(UsgNote (UsVar u))
558 ty ) = NoteTy (case lookupVarEnv ve u of
559 Just ua -> UsgNote ua
562 substUsTy ve (NoteTy note@(UsgNote _) ty ) = NoteTy note (substUsTy ve ty)
563 substUsTy ve (NoteTy note@(UsgForAll _) ty ) = NoteTy note (substUsTy ve ty)
564 substUsTy ve (NoteTy (SynNote ty1) ty2) = NoteTy (SynNote (substUsTy ve ty1))
566 substUsTy ve (NoteTy note@(FTVNote _) ty ) = NoteTy note (substUsTy ve ty)
567 substUsTy ve ty@(TyVarTy _ ) = ty
568 substUsTy ve (AppTy ty1 ty2) = AppTy (substUsTy ve ty1)
570 substUsTy ve (FunTy ty1 ty2) = FunTy (substUsTy ve ty1)
572 substUsTy ve (TyConApp tyc tys) = TyConApp tyc (map (substUsTy ve) tys)
573 substUsTy ve (ForAllTy yv ty ) = ForAllTy yv (substUsTy ve ty)
577 ---------------------------------------------------------------------
581 We need to be clever here with usage annotations; they need to be
582 lifted or lowered through the forall as appropriate.
585 mkForAllTy :: TyVar -> Type -> Type
586 mkForAllTy tyvar ty = case splitUsgTy_maybe ty of
587 Just (usg,ty') -> NoteTy (UsgNote usg)
589 Nothing -> ForAllTy tyvar ty
591 mkForAllTys :: [TyVar] -> Type -> Type
592 mkForAllTys tyvars ty = case splitUsgTy_maybe ty of
593 Just (usg,ty') -> NoteTy (UsgNote usg)
594 (foldr ForAllTy ty' tyvars)
595 Nothing -> foldr ForAllTy ty tyvars
597 splitForAllTy_maybe :: Type -> Maybe (TyVar, Type)
598 splitForAllTy_maybe ty = case splitUsgTy_maybe ty of
599 Just (usg,ty') -> do (tyvar,ty'') <- splitFAT_m ty'
600 return (tyvar, NoteTy (UsgNote usg) ty'')
601 Nothing -> splitFAT_m ty
603 splitFAT_m (NoteTy _ ty) = splitFAT_m ty
604 splitFAT_m (ForAllTy tyvar ty) = Just(tyvar, ty)
605 splitFAT_m _ = Nothing
607 isForAllTy :: Type -> Bool
608 isForAllTy (NoteTy _ ty) = isForAllTy ty
609 isForAllTy (ForAllTy tyvar ty) = True
612 splitForAllTys :: Type -> ([TyVar], Type)
613 splitForAllTys ty = case splitUsgTy_maybe ty of
614 Just (usg,ty') -> let (tvs,ty'') = split ty' ty' []
615 in (tvs, NoteTy (UsgNote usg) ty'')
616 Nothing -> split ty ty []
618 split orig_ty (ForAllTy tv ty) tvs = split ty ty (tv:tvs)
619 split orig_ty (NoteTy _ ty) tvs = split orig_ty ty tvs
620 split orig_ty t tvs = (reverse tvs, orig_ty)
623 @mkPiType@ makes a (->) type or a forall type, depending on whether
624 it is given a type variable or a term variable.
627 mkPiType :: Var -> Type -> Type -- The more polymorphic version doesn't work...
628 mkPiType v ty | isId v = mkFunTy (idType v) ty
629 | otherwise = mkForAllTy v ty
632 Applying a for-all to its arguments
635 applyTy :: Type -> Type -> Type
636 applyTy (NoteTy note@(UsgNote _) fun) arg = NoteTy note (applyTy fun arg)
637 applyTy (NoteTy note@(UsgForAll _) fun) arg = NoteTy note (applyTy fun arg)
638 applyTy (NoteTy _ fun) arg = applyTy fun arg
639 applyTy (ForAllTy tv ty) arg = ASSERT( isNotUsgTy arg )
640 substTy (mkTyVarSubst [tv] [arg]) ty
641 applyTy other arg = panic "applyTy"
643 applyTys :: Type -> [Type] -> Type
644 applyTys fun_ty arg_tys
645 = substTy (mkTyVarSubst tvs arg_tys) ty
647 (tvs, ty) = split fun_ty arg_tys
649 split fun_ty [] = ([], fun_ty)
650 split (NoteTy note@(UsgNote _) fun_ty)
651 args = case split fun_ty args of
652 (tvs, ty) -> (tvs, NoteTy note ty)
653 split (NoteTy note@(UsgForAll _) fun_ty)
654 args = case split fun_ty args of
655 (tvs, ty) -> (tvs, NoteTy note ty)
656 split (NoteTy _ fun_ty) args = split fun_ty args
657 split (ForAllTy tv fun_ty) (arg:args) = ASSERT2( isNotUsgTy arg, vcat (map pprType arg_tys) $$
658 text "in application of" <+> pprType fun_ty)
659 case split fun_ty args of
660 (tvs, ty) -> (tv:tvs, ty)
661 split other_ty args = panic "applyTys"
664 Note that we allow applications to be of usage-annotated- types, as an
665 extension: we handle them by lifting the annotation outside. The
666 argument, however, must still be unannotated.
669 hoistForAllTys :: Type -> Type
670 -- Move all the foralls to the top
671 -- e.g. T -> forall a. a ==> forall a. T -> a
673 = case hoist ty of { (tvs, body) -> mkForAllTys tvs body }
675 hoist :: Type -> ([TyVar], Type)
676 hoist ty = case splitFunTys ty of { (args, res) ->
677 case splitForAllTys res of {
678 ([], body) -> ([], ty) ;
679 (tvs1, body1) -> case hoist body1 of { (tvs2,body2) ->
680 (tvs1 ++ tvs2, mkFunTys args body2)
685 %************************************************************************
687 \subsection{Stuff to do with the source-language types}
689 PredType and ThetaType are used in types for expressions and bindings.
690 ClassPred and ClassContext are used in class and instance declarations.
692 %************************************************************************
697 data PredType = Class Class [Type]
699 type ThetaType = [PredType]
700 type ClassPred = (Class, [Type])
701 type ClassContext = [ClassPred]
702 type SigmaType = Type
706 instance Outputable PredType where
711 mkClassPred clas tys = Class clas tys
713 getClassTys_maybe :: PredType -> Maybe ClassPred
714 getClassTys_maybe (Class clas tys) = Just (clas, tys)
715 getClassTys_maybe _ = Nothing
717 ipName_maybe :: PredType -> Maybe Name
718 ipName_maybe (IParam n _) = Just n
719 ipName_maybe _ = Nothing
721 classesToPreds cts = map (uncurry Class) cts
723 classesOfPreds theta = concatMap cvt theta
724 where cvt (Class clas tys) = [(clas, tys)]
725 cvt (IParam _ _ ) = []
728 @isTauTy@ tests for nested for-alls.
731 isTauTy :: Type -> Bool
732 isTauTy (TyVarTy v) = True
733 isTauTy (TyConApp _ tys) = all isTauTy tys
734 isTauTy (AppTy a b) = isTauTy a && isTauTy b
735 isTauTy (FunTy a b) = isTauTy a && isTauTy b
736 isTauTy (NoteTy _ ty) = isTauTy ty
737 isTauTy other = False
741 mkRhoTy :: [PredType] -> Type -> Type
742 mkRhoTy theta ty = foldr (\p r -> FunTy (mkPredTy p) r) ty theta
744 splitRhoTy :: Type -> ([PredType], Type)
745 splitRhoTy ty = split ty ty []
747 split orig_ty (FunTy arg res) ts = case splitPredTy_maybe arg of
748 Just p -> split res res (p:ts)
749 Nothing -> (reverse ts, orig_ty)
750 split orig_ty (NoteTy _ ty) ts = split orig_ty ty ts
751 split orig_ty ty ts = (reverse ts, orig_ty)
757 mkSigmaTy tyvars theta tau = mkForAllTys tyvars (mkRhoTy theta tau)
759 splitSigmaTy :: Type -> ([TyVar], [PredType], Type)
763 (tyvars,rho) = splitForAllTys ty
764 (theta,tau) = splitRhoTy rho
768 %************************************************************************
770 \subsection{Kinds and free variables}
772 %************************************************************************
774 ---------------------------------------------------------------------
775 Finding the kind of a type
776 ~~~~~~~~~~~~~~~~~~~~~~~~~~
778 typeKind :: Type -> Kind
780 typeKind (TyVarTy tyvar) = tyVarKind tyvar
781 typeKind (TyConApp tycon tys) = foldr (\_ k -> funResultTy k) (tyConKind tycon) tys
782 typeKind (NoteTy _ ty) = typeKind ty
783 typeKind (AppTy fun arg) = funResultTy (typeKind fun)
785 typeKind (FunTy arg res) = boxedTypeKind -- A function is boxed regardless of its result type
786 -- No functions at the type level, hence we don't need
787 -- to say (typeKind res).
789 typeKind (ForAllTy tv ty) = typeKind ty
793 ---------------------------------------------------------------------
794 Free variables of a type
795 ~~~~~~~~~~~~~~~~~~~~~~~~
797 tyVarsOfType :: Type -> TyVarSet
799 tyVarsOfType (TyVarTy tv) = unitVarSet tv
800 tyVarsOfType (TyConApp tycon tys) = tyVarsOfTypes tys
801 tyVarsOfType (NoteTy (FTVNote tvs) ty2) = tvs
802 tyVarsOfType (NoteTy (SynNote ty1) ty2) = tyVarsOfType ty1
803 tyVarsOfType (NoteTy (UsgNote _) ty) = tyVarsOfType ty
804 tyVarsOfType (NoteTy (UsgForAll _) ty) = tyVarsOfType ty
805 tyVarsOfType (NoteTy (IPNote _) ty) = tyVarsOfType ty
806 tyVarsOfType (FunTy arg res) = tyVarsOfType arg `unionVarSet` tyVarsOfType res
807 tyVarsOfType (AppTy fun arg) = tyVarsOfType fun `unionVarSet` tyVarsOfType arg
808 tyVarsOfType (ForAllTy tyvar ty) = tyVarsOfType ty `minusVarSet` unitVarSet tyvar
810 tyVarsOfTypes :: [Type] -> TyVarSet
811 tyVarsOfTypes tys = foldr (unionVarSet.tyVarsOfType) emptyVarSet tys
813 tyVarsOfPred :: PredType -> TyVarSet
814 tyVarsOfPred (Class clas tys) = tyVarsOfTypes tys
815 tyVarsOfPred (IParam n ty) = tyVarsOfType ty
817 tyVarsOfTheta :: ThetaType -> TyVarSet
818 tyVarsOfTheta = foldr (unionVarSet . tyVarsOfPred) emptyVarSet
820 -- Add a Note with the free tyvars to the top of the type
821 -- (but under a usage if there is one)
822 addFreeTyVars :: Type -> Type
823 addFreeTyVars (NoteTy note@(UsgNote _) ty) = NoteTy note (addFreeTyVars ty)
824 addFreeTyVars (NoteTy note@(UsgForAll _) ty) = NoteTy note (addFreeTyVars ty)
825 addFreeTyVars ty@(NoteTy (FTVNote _) _) = ty
826 addFreeTyVars ty = NoteTy (FTVNote (tyVarsOfType ty)) ty
828 -- Find the free names of a type, including the type constructors and classes it mentions
829 namesOfType :: Type -> NameSet
830 namesOfType (TyVarTy tv) = unitNameSet (getName tv)
831 namesOfType (TyConApp tycon tys) = unitNameSet (getName tycon) `unionNameSets`
833 namesOfType (NoteTy (SynNote ty1) ty2) = namesOfType ty1
834 namesOfType (NoteTy other_note ty2) = namesOfType ty2
835 namesOfType (FunTy arg res) = namesOfType arg `unionNameSets` namesOfType res
836 namesOfType (AppTy fun arg) = namesOfType fun `unionNameSets` namesOfType arg
837 namesOfType (ForAllTy tyvar ty) = namesOfType ty `minusNameSet` unitNameSet (getName tyvar)
839 namesOfTypes tys = foldr (unionNameSets . namesOfType) emptyNameSet tys
843 %************************************************************************
845 \subsection{TidyType}
847 %************************************************************************
849 tidyTy tidies up a type for printing in an error message, or in
852 It doesn't change the uniques at all, just the print names.
855 tidyTyVar :: TidyEnv -> TyVar -> (TidyEnv, TyVar)
856 tidyTyVar env@(tidy_env, subst) tyvar
857 = case lookupVarEnv subst tyvar of
859 Just tyvar' -> -- Already substituted
862 Nothing -> -- Make a new nice name for it
864 case tidyOccName tidy_env (getOccName name) of
865 (tidy', occ') -> -- New occname reqd
866 ((tidy', subst'), tyvar')
868 subst' = extendVarEnv subst tyvar tyvar'
869 tyvar' = setTyVarName tyvar name'
870 name' = mkLocalName (getUnique name) occ' noSrcLoc
871 -- Note: make a *user* tyvar, so it printes nicely
872 -- Could extract src loc, but no need.
874 name = tyVarName tyvar
876 tidyTyVars env tyvars = mapAccumL tidyTyVar env tyvars
878 tidyType :: TidyEnv -> Type -> Type
879 tidyType env@(tidy_env, subst) ty
882 go (TyVarTy tv) = case lookupVarEnv subst tv of
883 Nothing -> TyVarTy tv
884 Just tv' -> TyVarTy tv'
885 go (TyConApp tycon tys) = let args = map go tys
886 in args `seqList` TyConApp tycon args
887 go (NoteTy note ty) = (NoteTy SAPPLY (go_note note)) SAPPLY (go ty)
888 go (AppTy fun arg) = (AppTy SAPPLY (go fun)) SAPPLY (go arg)
889 go (FunTy fun arg) = (FunTy SAPPLY (go fun)) SAPPLY (go arg)
890 go (ForAllTy tv ty) = ForAllTy tvp SAPPLY (tidyType envp ty)
892 (envp, tvp) = tidyTyVar env tv
894 go_note (SynNote ty) = SynNote SAPPLY (go ty)
895 go_note note@(FTVNote ftvs) = note -- No need to tidy the free tyvars
896 go_note note@(UsgNote _) = note -- Usage annotation is already tidy
897 go_note note@(UsgForAll _) = note -- Uvar binder is already tidy
898 go_note (IPNote n) = IPNote (tidyIPName n)
900 tidyTypes env tys = map (tidyType env) tys
904 @tidyOpenType@ grabs the free type variables, tidies them
905 and then uses @tidyType@ to work over the type itself
908 tidyOpenType :: TidyEnv -> Type -> (TidyEnv, Type)
910 = (env', tidyType env' ty)
912 env' = foldl go env (varSetElems (tyVarsOfType ty))
913 go env tyvar = fst (tidyTyVar env tyvar)
915 tidyOpenTypes :: TidyEnv -> [Type] -> (TidyEnv, [Type])
916 tidyOpenTypes env tys = mapAccumL tidyOpenType env tys
918 tidyTopType :: Type -> Type
919 tidyTopType ty = tidyType emptyTidyEnv ty
923 tidyIPName :: Name -> Name
925 = mkLocalName (getUnique name) (getOccName name) noSrcLoc
929 %************************************************************************
931 \subsection{Boxedness and liftedness}
933 %************************************************************************
936 isUnboxedType :: Type -> Bool
937 isUnboxedType ty = not (isFollowableRep (typePrimRep ty))
939 isUnLiftedType :: Type -> Bool
940 -- isUnLiftedType returns True for forall'd unlifted types:
941 -- x :: forall a. Int#
942 -- I found bindings like these were getting floated to the top level.
943 -- They are pretty bogus types, mind you. It would be better never to
946 isUnLiftedType (ForAllTy tv ty) = isUnLiftedType ty
947 isUnLiftedType (NoteTy _ ty) = isUnLiftedType ty
948 isUnLiftedType (TyConApp tc _) = isUnLiftedTyCon tc
949 isUnLiftedType other = False
951 isUnboxedTupleType :: Type -> Bool
952 isUnboxedTupleType ty = case splitTyConApp_maybe ty of
953 Just (tc, ty_args) -> isUnboxedTupleTyCon tc
956 -- Should only be applied to *types*; hence the assert
957 isAlgType :: Type -> Bool
958 isAlgType ty = case splitTyConApp_maybe ty of
959 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
963 -- Should only be applied to *types*; hence the assert
964 isDataType :: Type -> Bool
965 isDataType ty = case splitTyConApp_maybe ty of
966 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
970 isNewType :: Type -> Bool
971 isNewType ty = case splitTyConApp_maybe ty of
972 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
978 %************************************************************************
980 \subsection{Sequencing on types
982 %************************************************************************
985 seqType :: Type -> ()
986 seqType (TyVarTy tv) = tv `seq` ()
987 seqType (AppTy t1 t2) = seqType t1 `seq` seqType t2
988 seqType (FunTy t1 t2) = seqType t1 `seq` seqType t2
989 seqType (NoteTy note t2) = seqNote note `seq` seqType t2
990 seqType (TyConApp tc tys) = tc `seq` seqTypes tys
991 seqType (ForAllTy tv ty) = tv `seq` seqType ty
993 seqTypes :: [Type] -> ()
995 seqTypes (ty:tys) = seqType ty `seq` seqTypes tys
997 seqNote :: TyNote -> ()
998 seqNote (SynNote ty) = seqType ty
999 seqNote (FTVNote set) = sizeUniqSet set `seq` ()
1000 seqNote (UsgNote usg) = usg `seq` ()
1001 seqNote (IPNote nm) = nm `seq` ()