2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 \section[Type]{Type - public interface}
8 -- re-exports from TypeRep:
12 superKind, superBoxity, -- KX and BX respectively
13 boxedBoxity, unboxedBoxity, -- :: BX
15 typeCon, -- :: BX -> KX
16 boxedTypeKind, unboxedTypeKind, openTypeKind, -- :: KX
17 mkArrowKind, mkArrowKinds, -- :: KX -> KX -> KX
21 -- exports from this module:
22 hasMoreBoxityInfo, defaultKind,
24 mkTyVarTy, mkTyVarTys, getTyVar, getTyVar_maybe, isTyVarTy,
26 mkAppTy, mkAppTys, splitAppTy, splitAppTys, splitAppTy_maybe,
28 mkFunTy, mkFunTys, splitFunTy, splitFunTy_maybe, splitFunTys, splitFunTysN,
29 funResultTy, funArgTy, zipFunTys,
31 mkTyConApp, mkTyConTy, splitTyConApp_maybe,
32 splitAlgTyConApp_maybe, splitAlgTyConApp,
33 mkDictTy, mkDictTys, mkPredTy, splitPredTy_maybe, splitDictTy_maybe, isDictTy,
35 mkSynTy, isSynTy, deNoteType,
37 repType, splitRepFunTys, splitNewType_maybe, typePrimRep,
39 UsageAnn(..), mkUsgTy, isUsgTy{- dont use -}, isNotUsgTy, splitUsgTy, unUsgTy, tyUsg,
40 mkUsForAllTy, mkUsForAllTys, splitUsForAllTys, substUsTy,
42 mkForAllTy, mkForAllTys, splitForAllTy_maybe, splitForAllTys,
43 applyTy, applyTys, hoistForAllTys,
45 TauType, RhoType, SigmaType, PredType(..), ThetaType,
46 ClassPred, ClassContext, mkClassPred,
47 getClassTys_maybe, ipName_maybe, classesToPreds, classesOfPreds,
48 isTauTy, mkRhoTy, splitRhoTy,
49 mkSigmaTy, isSigmaTy, splitSigmaTy,
52 isUnLiftedType, isUnboxedType, isUnboxedTupleType, isAlgType, isDataType, isNewType,
55 tyVarsOfType, tyVarsOfTypes, tyVarsOfPred, tyVarsOfTheta,
56 namesOfType, typeKind, addFreeTyVars,
58 -- Tidying up for printing
60 tidyOpenType, tidyOpenTypes,
61 tidyTyVar, tidyTyVars,
69 #include "HsVersions.h"
71 -- We import the representation and primitive functions from TypeRep.
72 -- Many things are reexported, but not the representation!
78 import {-# SOURCE #-} DataCon( DataCon, dataConRepType )
79 import {-# SOURCE #-} PprType( pprType, pprPred ) -- Only called in debug messages
80 import {-# SOURCE #-} Subst ( mkTyVarSubst, substTy )
83 import Var ( TyVar, Var, UVar,
84 tyVarKind, tyVarName, setTyVarName, isId, idType,
89 import Name ( Name, NamedThing(..), mkLocalName, tidyOccName
92 import Class ( classTyCon, Class, ClassPred, ClassContext )
94 isUnboxedTupleTyCon, isUnLiftedTyCon,
95 isFunTyCon, isDataTyCon, isNewTyCon, newTyConRep,
96 isAlgTyCon, isSynTyCon, tyConArity,
97 tyConKind, tyConDataCons, getSynTyConDefn,
98 tyConPrimRep, tyConClass_maybe
102 import SrcLoc ( noSrcLoc )
103 import Maybes ( maybeToBool )
104 import PrimRep ( PrimRep(..), isFollowableRep )
105 import Unique ( Uniquable(..) )
106 import Util ( mapAccumL, seqList )
108 import UniqSet ( sizeUniqSet ) -- Should come via VarSet
112 %************************************************************************
114 \subsection{Stuff to do with kinds.}
116 %************************************************************************
119 hasMoreBoxityInfo :: Kind -> Kind -> Bool
120 hasMoreBoxityInfo k1 k2
121 | k2 == openTypeKind = True
122 | otherwise = k1 == k2
124 defaultKind :: Kind -> Kind
125 -- Used when generalising: default kind '?' to '*'
126 defaultKind kind | kind == openTypeKind = boxedTypeKind
131 %************************************************************************
133 \subsection{Constructor-specific functions}
135 %************************************************************************
138 ---------------------------------------------------------------------
142 mkTyVarTy :: TyVar -> Type
145 mkTyVarTys :: [TyVar] -> [Type]
146 mkTyVarTys = map mkTyVarTy -- a common use of mkTyVarTy
148 getTyVar :: String -> Type -> TyVar
149 getTyVar msg (TyVarTy tv) = tv
150 getTyVar msg (NoteTy _ t) = getTyVar msg t
151 getTyVar msg other = panic ("getTyVar: " ++ msg)
153 getTyVar_maybe :: Type -> Maybe TyVar
154 getTyVar_maybe (TyVarTy tv) = Just tv
155 getTyVar_maybe (NoteTy _ t) = getTyVar_maybe t
156 getTyVar_maybe other = Nothing
158 isTyVarTy :: Type -> Bool
159 isTyVarTy (TyVarTy tv) = True
160 isTyVarTy (NoteTy _ ty) = isTyVarTy ty
161 isTyVarTy other = False
165 ---------------------------------------------------------------------
168 We need to be pretty careful with AppTy to make sure we obey the
169 invariant that a TyConApp is always visibly so. mkAppTy maintains the
173 mkAppTy orig_ty1 orig_ty2 = ASSERT2( isNotUsgTy orig_ty1 && isNotUsgTy orig_ty2, pprType orig_ty1 <+> text "to" <+> pprType orig_ty2 )
176 mk_app (NoteTy _ ty1) = mk_app ty1
177 mk_app (TyConApp tc tys) = mkTyConApp tc (tys ++ [orig_ty2])
178 mk_app ty1 = AppTy orig_ty1 orig_ty2
180 mkAppTys :: Type -> [Type] -> Type
181 mkAppTys orig_ty1 [] = orig_ty1
182 -- This check for an empty list of type arguments
183 -- avoids the needless of a type synonym constructor.
184 -- For example: mkAppTys Rational []
185 -- returns to (Ratio Integer), which has needlessly lost
186 -- the Rational part.
187 mkAppTys orig_ty1 orig_tys2 = ASSERT2( isNotUsgTy orig_ty1, pprType orig_ty1 )
190 mk_app (NoteTy _ ty1) = mk_app ty1
191 mk_app (TyConApp tc tys) = mkTyConApp tc (tys ++ orig_tys2)
192 mk_app ty1 = ASSERT2( all isNotUsgTy orig_tys2, pprType orig_ty1 <+> text "to" <+> hsep (map pprType orig_tys2) )
193 foldl AppTy orig_ty1 orig_tys2
195 splitAppTy_maybe :: Type -> Maybe (Type, Type)
196 splitAppTy_maybe (FunTy ty1 ty2) = Just (TyConApp funTyCon [ty1], ty2)
197 splitAppTy_maybe (AppTy ty1 ty2) = Just (ty1, ty2)
198 splitAppTy_maybe (NoteTy _ ty) = splitAppTy_maybe ty
199 splitAppTy_maybe (TyConApp tc []) = Nothing
200 splitAppTy_maybe (TyConApp tc tys) = split tys []
202 split [ty2] acc = Just (TyConApp tc (reverse acc), ty2)
203 split (ty:tys) acc = split tys (ty:acc)
205 splitAppTy_maybe other = Nothing
207 splitAppTy :: Type -> (Type, Type)
208 splitAppTy ty = case splitAppTy_maybe ty of
210 Nothing -> panic "splitAppTy"
212 splitAppTys :: Type -> (Type, [Type])
213 splitAppTys ty = split ty ty []
215 split orig_ty (AppTy ty arg) args = split ty ty (arg:args)
216 split orig_ty (NoteTy _ ty) args = split orig_ty ty args
217 split orig_ty (FunTy ty1 ty2) args = ASSERT( null args )
218 (TyConApp funTyCon [], [ty1,ty2])
219 split orig_ty (TyConApp tc tc_args) args = (TyConApp tc [], tc_args ++ args)
220 split orig_ty ty args = (orig_ty, args)
224 ---------------------------------------------------------------------
229 mkFunTy :: Type -> Type -> Type
230 mkFunTy arg res = FunTy arg res
232 mkFunTys :: [Type] -> Type -> Type
233 mkFunTys tys ty = foldr FunTy ty tys
235 splitFunTy :: Type -> (Type, Type)
236 splitFunTy (FunTy arg res) = (arg, res)
237 splitFunTy (NoteTy _ ty) = splitFunTy ty
239 splitFunTy_maybe :: Type -> Maybe (Type, Type)
240 splitFunTy_maybe (FunTy arg res) = Just (arg, res)
241 splitFunTy_maybe (NoteTy (IPNote _) ty) = Nothing
242 splitFunTy_maybe (NoteTy _ ty) = splitFunTy_maybe ty
243 splitFunTy_maybe other = Nothing
245 splitFunTys :: Type -> ([Type], Type)
246 splitFunTys ty = split [] ty ty
248 split args orig_ty (FunTy arg res) = split (arg:args) res res
249 split args orig_ty (NoteTy (IPNote _) ty)
250 = (reverse args, orig_ty)
251 split args orig_ty (NoteTy _ ty) = split args orig_ty ty
252 split args orig_ty ty = (reverse args, orig_ty)
254 splitFunTysN :: String -> Int -> Type -> ([Type], Type)
255 splitFunTysN msg orig_n orig_ty = split orig_n [] orig_ty orig_ty
257 split 0 args syn_ty ty = (reverse args, syn_ty)
258 split n args syn_ty (FunTy arg res) = split (n-1) (arg:args) res res
259 split n args syn_ty (NoteTy _ ty) = split n args syn_ty ty
260 split n args syn_ty ty = pprPanic ("splitFunTysN: " ++ msg) (int orig_n <+> pprType orig_ty)
262 zipFunTys :: Outputable a => [a] -> Type -> ([(a,Type)], Type)
263 zipFunTys orig_xs orig_ty = split [] orig_xs orig_ty orig_ty
265 split acc [] nty ty = (reverse acc, nty)
266 split acc (x:xs) nty (FunTy arg res) = split ((x,arg):acc) xs res res
267 split acc xs nty (NoteTy _ ty) = split acc xs nty ty
268 split acc (x:xs) nty ty = pprPanic "zipFunTys" (ppr orig_xs <+> pprType orig_ty)
270 funResultTy :: Type -> Type
271 funResultTy (FunTy arg res) = res
272 funResultTy (NoteTy _ ty) = funResultTy ty
273 funResultTy ty = pprPanic "funResultTy" (pprType ty)
275 funArgTy :: Type -> Type
276 funArgTy (FunTy arg res) = arg
277 funArgTy (NoteTy _ ty) = funArgTy ty
278 funArgTy ty = pprPanic "funArgTy" (pprType ty)
282 ---------------------------------------------------------------------
287 mkTyConApp :: TyCon -> [Type] -> Type
289 | isFunTyCon tycon && length tys == 2
291 (ty1:ty2:_) -> FunTy ty1 ty2
294 = ASSERT(not (isSynTyCon tycon))
297 mkTyConTy :: TyCon -> Type
298 mkTyConTy tycon = ASSERT( not (isSynTyCon tycon) )
301 -- splitTyConApp "looks through" synonyms, because they don't
302 -- mean a distinct type, but all other type-constructor applications
303 -- including functions are returned as Just ..
305 splitTyConApp_maybe :: Type -> Maybe (TyCon, [Type])
306 splitTyConApp_maybe (TyConApp tc tys) = Just (tc, tys)
307 splitTyConApp_maybe (FunTy arg res) = Just (funTyCon, [arg,res])
308 splitTyConApp_maybe (NoteTy _ ty) = splitTyConApp_maybe ty
309 splitTyConApp_maybe other = Nothing
311 -- splitAlgTyConApp_maybe looks for
312 -- *saturated* applications of *algebraic* data types
313 -- "Algebraic" => newtype, data type, or dictionary (not function types)
314 -- We return the constructors too, so there had better be some.
316 splitAlgTyConApp_maybe :: Type -> Maybe (TyCon, [Type], [DataCon])
317 splitAlgTyConApp_maybe (TyConApp tc tys)
319 tyConArity tc == length tys = Just (tc, tys, tyConDataCons tc)
320 splitAlgTyConApp_maybe (NoteTy (IPNote _) ty)
322 splitAlgTyConApp_maybe (NoteTy _ ty) = splitAlgTyConApp_maybe ty
323 splitAlgTyConApp_maybe other = Nothing
325 splitAlgTyConApp :: Type -> (TyCon, [Type], [DataCon])
326 -- Here the "algebraic" property is an *assertion*
327 splitAlgTyConApp (TyConApp tc tys) = ASSERT( isAlgTyCon tc && tyConArity tc == length tys )
328 (tc, tys, tyConDataCons tc)
329 splitAlgTyConApp (NoteTy _ ty) = splitAlgTyConApp ty
331 splitAlgTyConApp ty = pprPanic "splitAlgTyConApp" (pprType ty)
335 "Dictionary" types are just ordinary data types, but you can
336 tell from the type constructor whether it's a dictionary or not.
339 mkDictTy :: Class -> [Type] -> Type
340 mkDictTy clas tys = TyConApp (classTyCon clas) tys
342 mkDictTys :: ClassContext -> [Type]
343 mkDictTys cxt = [mkDictTy cls tys | (cls,tys) <- cxt]
345 mkPredTy :: PredType -> Type
346 mkPredTy (Class clas tys) = TyConApp (classTyCon clas) tys
347 mkPredTy (IParam n ty) = NoteTy (IPNote n) ty
349 splitPredTy_maybe :: Type -> Maybe PredType
350 splitPredTy_maybe (TyConApp tc tys)
351 | maybeToBool maybe_class
352 && tyConArity tc == length tys = Just (Class clas tys)
354 maybe_class = tyConClass_maybe tc
355 Just clas = maybe_class
357 splitPredTy_maybe (NoteTy (IPNote n) ty)
359 splitPredTy_maybe (NoteTy _ ty) = splitPredTy_maybe ty
360 splitPredTy_maybe other = Nothing
362 splitDictTy_maybe :: Type -> Maybe (Class, [Type])
364 = case splitPredTy_maybe ty of
365 Just p -> getClassTys_maybe p
368 isDictTy :: Type -> Bool
369 -- This version is slightly more efficient than (maybeToBool . splitDictTy)
370 isDictTy (TyConApp tc tys)
371 | maybeToBool (tyConClass_maybe tc)
372 && tyConArity tc == length tys
374 isDictTy (NoteTy _ ty) = isDictTy ty
375 isDictTy other = False
378 ---------------------------------------------------------------------
383 mkSynTy syn_tycon tys
384 = ASSERT( isSynTyCon syn_tycon )
385 ASSERT( isNotUsgTy body )
386 ASSERT( length tyvars == length tys )
387 NoteTy (SynNote (TyConApp syn_tycon tys))
388 (substTy (mkTyVarSubst tyvars tys) body)
390 (tyvars, body) = getSynTyConDefn syn_tycon
392 isSynTy (NoteTy (SynNote _) _) = True
393 isSynTy other = False
395 deNoteType :: Type -> Type
396 -- Sorry for the cute name
397 deNoteType ty@(TyVarTy tyvar) = ty
398 deNoteType (TyConApp tycon tys) = TyConApp tycon (map deNoteType tys)
399 deNoteType (NoteTy _ ty) = deNoteType ty
400 deNoteType (AppTy fun arg) = AppTy (deNoteType fun) (deNoteType arg)
401 deNoteType (FunTy fun arg) = FunTy (deNoteType fun) (deNoteType arg)
402 deNoteType (ForAllTy tv ty) = ForAllTy tv (deNoteType ty)
405 Notes on type synonyms
406 ~~~~~~~~~~~~~~~~~~~~~~
407 The various "split" functions (splitFunTy, splitRhoTy, splitForAllTy) try
408 to return type synonyms whereever possible. Thus
413 splitFunTys (a -> Foo a) = ([a], Foo a)
416 The reason is that we then get better (shorter) type signatures in
417 interfaces. Notably this plays a role in tcTySigs in TcBinds.lhs.
423 repType looks through
427 It's useful in the back end where we're not
428 interested in newtypes anymore.
431 repType :: Type -> Type
432 repType (ForAllTy _ ty) = repType ty
433 repType (NoteTy _ ty) = repType ty
434 repType ty = case splitNewType_maybe ty of
435 Just ty' -> repType ty' -- Still re-apply repType in case of for-all
438 splitRepFunTys :: Type -> ([Type], Type)
439 -- Like splitFunTys, but looks through newtypes and for-alls
440 splitRepFunTys ty = split [] (repType ty)
442 split args (FunTy arg res) = split (arg:args) (repType res)
443 split args ty = (reverse args, ty)
445 typePrimRep :: Type -> PrimRep
446 typePrimRep ty = case repType ty of
447 TyConApp tc _ -> tyConPrimRep tc
449 AppTy _ _ -> PtrRep -- ??
452 splitNewType_maybe :: Type -> Maybe Type
453 -- Find the representation of a newtype, if it is one
454 -- Looks through multiple levels of newtype, but does not look through for-alls
455 splitNewType_maybe (NoteTy (IPNote _) ty)
457 splitNewType_maybe (NoteTy _ ty) = splitNewType_maybe ty
458 splitNewType_maybe (TyConApp tc tys) = case newTyConRep tc of
459 Just rep_ty -> ASSERT( length tys == tyConArity tc )
460 -- The assert should hold because repType should
461 -- only be applied to *types* (of kind *)
462 Just (applyTys rep_ty tys)
464 splitNewType_maybe other = Nothing
469 ---------------------------------------------------------------------
473 NB: Invariant: if present, usage note is at the very top of the type.
474 This should be carefully preserved.
476 In some parts of the compiler, comments use the _Once Upon a
477 Polymorphic Type_ (POPL'99) usage of "rho = generalised
478 usage-annotated type; sigma = usage-annotated type; tau =
479 usage-annotated type except on top"; unfortunately this conflicts with
480 the rho/tau/theta/sigma usage in the rest of the compiler. (KSW
484 mkUsgTy :: UsageAnn -> Type -> Type
486 mkUsgTy UsMany ty = ASSERT2( isNotUsgTy ty, pprType ty )
489 mkUsgTy usg ty = ASSERT2( isNotUsgTy ty, pprType ty )
490 NoteTy (UsgNote usg) ty
492 -- The isUsgTy function is utterly useless if UsManys are omitted.
493 -- Be warned! KSW 1999-04.
494 isUsgTy :: Type -> Bool
498 isUsgTy (NoteTy (UsgForAll _) ty) = isUsgTy ty
499 isUsgTy (NoteTy (UsgNote _) _ ) = True
500 isUsgTy other = False
503 -- The isNotUsgTy function may return a false True if UsManys are omitted;
504 -- in other words, A SSERT( isNotUsgTy ty ) may be useful but
505 -- A SSERT( not (isNotUsg ty) ) is asking for trouble. KSW 1999-04.
506 isNotUsgTy :: Type -> Bool
507 isNotUsgTy (NoteTy (UsgForAll _) _) = False
508 isNotUsgTy (NoteTy (UsgNote _) _) = False
509 isNotUsgTy other = True
511 -- splitUsgTy_maybe is not exported, since it is meaningless if
512 -- UsManys are omitted. It is used in several places in this module,
513 -- however. KSW 1999-04.
514 splitUsgTy_maybe :: Type -> Maybe (UsageAnn,Type)
515 splitUsgTy_maybe (NoteTy (UsgNote usg) ty2) = ASSERT( isNotUsgTy ty2 )
517 splitUsgTy_maybe ty@(NoteTy (UsgForAll _) _) = pprPanic "splitUsgTy_maybe:" $ pprType ty
518 splitUsgTy_maybe ty = Nothing
520 splitUsgTy :: Type -> (UsageAnn,Type)
521 splitUsgTy ty = case splitUsgTy_maybe ty of
527 pprPanic "splitUsgTy: no usage annot:" $ pprType ty
530 tyUsg :: Type -> UsageAnn
531 tyUsg = fst . splitUsgTy
533 unUsgTy :: Type -> Type
534 -- strip outer usage annotation if present
535 unUsgTy ty = case splitUsgTy_maybe ty of
536 Just (_,ty1) -> ASSERT2( isNotUsgTy ty1, pprType ty )
540 mkUsForAllTy :: UVar -> Type -> Type
541 mkUsForAllTy uv ty = NoteTy (UsgForAll uv) ty
543 mkUsForAllTys :: [UVar] -> Type -> Type
544 mkUsForAllTys uvs ty = foldr (NoteTy . UsgForAll) ty uvs
546 splitUsForAllTys :: Type -> ([UVar],Type)
547 splitUsForAllTys ty = split ty []
548 where split (NoteTy (UsgForAll u) ty) uvs = split ty (u:uvs)
549 split other_ty uvs = (reverse uvs, other_ty)
551 substUsTy :: VarEnv UsageAnn -> Type -> Type
552 -- assumes range is fresh uvars, so no conflicts
553 substUsTy ve (NoteTy note@(UsgNote (UsVar u))
554 ty ) = NoteTy (case lookupVarEnv ve u of
555 Just ua -> UsgNote ua
558 substUsTy ve (NoteTy note@(UsgNote _) ty ) = NoteTy note (substUsTy ve ty)
559 substUsTy ve (NoteTy note@(UsgForAll _) ty ) = NoteTy note (substUsTy ve ty)
560 substUsTy ve (NoteTy (SynNote ty1) ty2) = NoteTy (SynNote (substUsTy ve ty1))
562 substUsTy ve (NoteTy note@(FTVNote _) ty ) = NoteTy note (substUsTy ve ty)
563 substUsTy ve ty@(TyVarTy _ ) = ty
564 substUsTy ve (AppTy ty1 ty2) = AppTy (substUsTy ve ty1)
566 substUsTy ve (FunTy ty1 ty2) = FunTy (substUsTy ve ty1)
568 substUsTy ve (TyConApp tyc tys) = TyConApp tyc (map (substUsTy ve) tys)
569 substUsTy ve (ForAllTy yv ty ) = ForAllTy yv (substUsTy ve ty)
573 ---------------------------------------------------------------------
577 We need to be clever here with usage annotations; they need to be
578 lifted or lowered through the forall as appropriate.
581 mkForAllTy :: TyVar -> Type -> Type
582 mkForAllTy tyvar ty = case splitUsgTy_maybe ty of
583 Just (usg,ty') -> NoteTy (UsgNote usg)
585 Nothing -> ForAllTy tyvar ty
587 mkForAllTys :: [TyVar] -> Type -> Type
588 mkForAllTys tyvars ty = case splitUsgTy_maybe ty of
589 Just (usg,ty') -> NoteTy (UsgNote usg)
590 (foldr ForAllTy ty' tyvars)
591 Nothing -> foldr ForAllTy ty tyvars
593 splitForAllTy_maybe :: Type -> Maybe (TyVar, Type)
594 splitForAllTy_maybe ty = case splitUsgTy_maybe ty of
595 Just (usg,ty') -> do (tyvar,ty'') <- splitFAT_m ty'
596 return (tyvar, NoteTy (UsgNote usg) ty'')
597 Nothing -> splitFAT_m ty
599 splitFAT_m (NoteTy (IPNote _) ty) = Nothing
600 splitFAT_m (NoteTy _ ty) = splitFAT_m ty
601 splitFAT_m (ForAllTy tyvar ty) = Just(tyvar, ty)
602 splitFAT_m _ = Nothing
604 splitForAllTys :: Type -> ([TyVar], Type)
605 splitForAllTys ty = case splitUsgTy_maybe ty of
606 Just (usg,ty') -> let (tvs,ty'') = split ty' ty' []
607 in (tvs, NoteTy (UsgNote usg) ty'')
608 Nothing -> split ty ty []
610 split orig_ty (ForAllTy tv ty) tvs = split ty ty (tv:tvs)
611 split orig_ty (NoteTy (IPNote _) ty) tvs = (reverse tvs, orig_ty)
612 split orig_ty (NoteTy _ ty) tvs = split orig_ty ty tvs
613 split orig_ty t tvs = (reverse tvs, orig_ty)
616 -- (mkPiType now in CoreUtils)
618 Applying a for-all to its arguments
621 applyTy :: Type -> Type -> Type
622 applyTy (NoteTy note@(UsgNote _) fun) arg = NoteTy note (applyTy fun arg)
623 applyTy (NoteTy note@(UsgForAll _) fun) arg = NoteTy note (applyTy fun arg)
624 applyTy (NoteTy _ fun) arg = applyTy fun arg
625 applyTy (ForAllTy tv ty) arg = ASSERT( isNotUsgTy arg )
626 substTy (mkTyVarSubst [tv] [arg]) ty
627 applyTy other arg = panic "applyTy"
629 applyTys :: Type -> [Type] -> Type
630 applyTys fun_ty arg_tys
631 = substTy (mkTyVarSubst tvs arg_tys) ty
633 (tvs, ty) = split fun_ty arg_tys
635 split fun_ty [] = ([], fun_ty)
636 split (NoteTy note@(UsgNote _) fun_ty)
637 args = case split fun_ty args of
638 (tvs, ty) -> (tvs, NoteTy note ty)
639 split (NoteTy note@(UsgForAll _) fun_ty)
640 args = case split fun_ty args of
641 (tvs, ty) -> (tvs, NoteTy note ty)
642 split (NoteTy _ fun_ty) args = split fun_ty args
643 split (ForAllTy tv fun_ty) (arg:args) = ASSERT2( isNotUsgTy arg, vcat (map pprType arg_tys) $$
644 text "in application of" <+> pprType fun_ty)
645 case split fun_ty args of
646 (tvs, ty) -> (tv:tvs, ty)
647 split other_ty args = panic "applyTys"
650 Note that we allow applications to be of usage-annotated- types, as an
651 extension: we handle them by lifting the annotation outside. The
652 argument, however, must still be unannotated.
655 hoistForAllTys :: Type -> Type
656 -- Move all the foralls to the top
657 -- e.g. T -> forall a. a ==> forall a. T -> a
659 = case hoist ty of { (tvs, body) -> mkForAllTys tvs body }
661 hoist :: Type -> ([TyVar], Type)
662 hoist ty = case splitFunTys ty of { (args, res) ->
663 case splitForAllTys res of {
664 ([], body) -> ([], ty) ;
665 (tvs1, body1) -> case hoist body1 of { (tvs2,body2) ->
666 (tvs1 ++ tvs2, mkFunTys args body2)
671 %************************************************************************
673 \subsection{Stuff to do with the source-language types}
675 PredType and ThetaType are used in types for expressions and bindings.
676 ClassPred and ClassContext are used in class and instance declarations.
678 %************************************************************************
681 data PredType = Class Class [Type]
685 type ThetaType = [PredType]
688 type SigmaType = Type
692 instance Outputable PredType where
697 mkClassPred clas tys = Class clas tys
699 getClassTys_maybe :: PredType -> Maybe ClassPred
700 getClassTys_maybe (Class clas tys) = Just (clas, tys)
701 getClassTys_maybe _ = Nothing
703 ipName_maybe :: PredType -> Maybe Name
704 ipName_maybe (IParam n _) = Just n
705 ipName_maybe _ = Nothing
707 classesToPreds cts = map (uncurry Class) cts
709 classesOfPreds :: ThetaType -> ClassContext
710 classesOfPreds theta = [(clas,tys) | Class clas tys <- theta]
713 @isTauTy@ tests for nested for-alls.
716 isTauTy :: Type -> Bool
717 isTauTy (TyVarTy v) = True
718 isTauTy (TyConApp _ tys) = all isTauTy tys
719 isTauTy (AppTy a b) = isTauTy a && isTauTy b
720 isTauTy (FunTy a b) = isTauTy a && isTauTy b
721 isTauTy (NoteTy (IPNote _) ty) = False
722 isTauTy (NoteTy _ ty) = isTauTy ty
723 isTauTy other = False
727 mkRhoTy :: [PredType] -> Type -> Type
728 mkRhoTy theta ty = foldr (\p r -> FunTy (mkPredTy p) r) ty theta
730 splitRhoTy :: Type -> ([PredType], Type)
731 splitRhoTy ty = split ty ty []
733 split orig_ty (FunTy arg res) ts = case splitPredTy_maybe arg of
734 Just p -> split res res (p:ts)
735 Nothing -> (reverse ts, orig_ty)
736 split orig_ty (NoteTy (IPNote _) ty) ts = (reverse ts, orig_ty)
737 split orig_ty (NoteTy _ ty) ts = split orig_ty ty ts
738 split orig_ty ty ts = (reverse ts, orig_ty)
744 mkSigmaTy tyvars theta tau = mkForAllTys tyvars (mkRhoTy theta tau)
746 isSigmaTy :: Type -> Bool
747 isSigmaTy (FunTy a b) = isPredTy a
748 where isPredTy (NoteTy (IPNote _) _) = True
749 -- JRL could be a dict ty, but that would be polymorphic,
750 -- and thus there would have been an outer ForAllTy
752 isSigmaTy (NoteTy (IPNote _) _) = False
753 isSigmaTy (NoteTy _ ty) = isSigmaTy ty
754 isSigmaTy (ForAllTy tyvar ty) = True
757 splitSigmaTy :: Type -> ([TyVar], [PredType], Type)
761 (tyvars,rho) = splitForAllTys ty
762 (theta,tau) = splitRhoTy rho
766 %************************************************************************
768 \subsection{Kinds and free variables}
770 %************************************************************************
772 ---------------------------------------------------------------------
773 Finding the kind of a type
774 ~~~~~~~~~~~~~~~~~~~~~~~~~~
776 typeKind :: Type -> Kind
778 typeKind (TyVarTy tyvar) = tyVarKind tyvar
779 typeKind (TyConApp tycon tys) = foldr (\_ k -> funResultTy k) (tyConKind tycon) tys
780 typeKind (NoteTy _ ty) = typeKind ty
781 typeKind (AppTy fun arg) = funResultTy (typeKind fun)
783 typeKind (FunTy arg res) = fix_up (typeKind res)
785 fix_up kind = case splitTyConApp_maybe kind of
786 Just (tycon, [_]) | tycon == typeCon -> boxedTypeKind
788 -- The basic story is
789 -- typeKind (FunTy arg res) = typeKind res
790 -- But a function is boxed regardless of its result type
791 -- Hencd the strange fix-up
793 typeKind (ForAllTy tv ty) = typeKind ty
797 ---------------------------------------------------------------------
798 Free variables of a type
799 ~~~~~~~~~~~~~~~~~~~~~~~~
801 tyVarsOfType :: Type -> TyVarSet
803 tyVarsOfType (TyVarTy tv) = unitVarSet tv
804 tyVarsOfType (TyConApp tycon tys) = tyVarsOfTypes tys
805 tyVarsOfType (NoteTy (FTVNote tvs) ty2) = tvs
806 tyVarsOfType (NoteTy (SynNote ty1) ty2) = tyVarsOfType ty1
807 tyVarsOfType (NoteTy (UsgNote _) ty) = tyVarsOfType ty
808 tyVarsOfType (NoteTy (UsgForAll _) ty) = tyVarsOfType ty
809 tyVarsOfType (NoteTy (IPNote _) ty) = tyVarsOfType ty
810 tyVarsOfType (FunTy arg res) = tyVarsOfType arg `unionVarSet` tyVarsOfType res
811 tyVarsOfType (AppTy fun arg) = tyVarsOfType fun `unionVarSet` tyVarsOfType arg
812 tyVarsOfType (ForAllTy tyvar ty) = tyVarsOfType ty `minusVarSet` unitVarSet tyvar
814 tyVarsOfTypes :: [Type] -> TyVarSet
815 tyVarsOfTypes tys = foldr (unionVarSet.tyVarsOfType) emptyVarSet tys
817 tyVarsOfPred :: PredType -> TyVarSet
818 tyVarsOfPred (Class clas tys) = tyVarsOfTypes tys
819 tyVarsOfPred (IParam n ty) = tyVarsOfType ty
821 tyVarsOfTheta :: ThetaType -> TyVarSet
822 tyVarsOfTheta = foldr (unionVarSet . tyVarsOfPred) emptyVarSet
824 -- Add a Note with the free tyvars to the top of the type
825 -- (but under a usage if there is one)
826 addFreeTyVars :: Type -> Type
827 addFreeTyVars (NoteTy note@(UsgNote _) ty) = NoteTy note (addFreeTyVars ty)
828 addFreeTyVars (NoteTy note@(UsgForAll _) ty) = NoteTy note (addFreeTyVars ty)
829 addFreeTyVars ty@(NoteTy (FTVNote _) _) = ty
830 addFreeTyVars ty = NoteTy (FTVNote (tyVarsOfType ty)) ty
832 -- Find the free names of a type, including the type constructors and classes it mentions
833 namesOfType :: Type -> NameSet
834 namesOfType (TyVarTy tv) = unitNameSet (getName tv)
835 namesOfType (TyConApp tycon tys) = unitNameSet (getName tycon) `unionNameSets`
837 namesOfType (NoteTy (SynNote ty1) ty2) = namesOfType ty1
838 namesOfType (NoteTy other_note ty2) = namesOfType ty2
839 namesOfType (FunTy arg res) = namesOfType arg `unionNameSets` namesOfType res
840 namesOfType (AppTy fun arg) = namesOfType fun `unionNameSets` namesOfType arg
841 namesOfType (ForAllTy tyvar ty) = namesOfType ty `minusNameSet` unitNameSet (getName tyvar)
843 namesOfTypes tys = foldr (unionNameSets . namesOfType) emptyNameSet tys
847 %************************************************************************
849 \subsection{TidyType}
851 %************************************************************************
853 tidyTy tidies up a type for printing in an error message, or in
856 It doesn't change the uniques at all, just the print names.
859 tidyTyVar :: TidyEnv -> TyVar -> (TidyEnv, TyVar)
860 tidyTyVar env@(tidy_env, subst) tyvar
861 = case lookupVarEnv subst tyvar of
863 Just tyvar' -> -- Already substituted
866 Nothing -> -- Make a new nice name for it
868 case tidyOccName tidy_env (getOccName name) of
869 (tidy', occ') -> -- New occname reqd
870 ((tidy', subst'), tyvar')
872 subst' = extendVarEnv subst tyvar tyvar'
873 tyvar' = setTyVarName tyvar name'
874 name' = mkLocalName (getUnique name) occ' noSrcLoc
875 -- Note: make a *user* tyvar, so it printes nicely
876 -- Could extract src loc, but no need.
878 name = tyVarName tyvar
880 tidyTyVars env tyvars = mapAccumL tidyTyVar env tyvars
882 tidyType :: TidyEnv -> Type -> Type
883 tidyType env@(tidy_env, subst) ty
886 go (TyVarTy tv) = case lookupVarEnv subst tv of
887 Nothing -> TyVarTy tv
888 Just tv' -> TyVarTy tv'
889 go (TyConApp tycon tys) = let args = map go tys
890 in args `seqList` TyConApp tycon args
891 go (NoteTy note ty) = (NoteTy SAPPLY (go_note note)) SAPPLY (go ty)
892 go (AppTy fun arg) = (AppTy SAPPLY (go fun)) SAPPLY (go arg)
893 go (FunTy fun arg) = (FunTy SAPPLY (go fun)) SAPPLY (go arg)
894 go (ForAllTy tv ty) = ForAllTy tvp SAPPLY (tidyType envp ty)
896 (envp, tvp) = tidyTyVar env tv
898 go_note (SynNote ty) = SynNote SAPPLY (go ty)
899 go_note note@(FTVNote ftvs) = note -- No need to tidy the free tyvars
900 go_note note@(UsgNote _) = note -- Usage annotation is already tidy
901 go_note note@(UsgForAll _) = note -- Uvar binder is already tidy
902 go_note (IPNote n) = IPNote (tidyIPName n)
904 tidyTypes env tys = map (tidyType env) tys
908 @tidyOpenType@ grabs the free type variables, tidies them
909 and then uses @tidyType@ to work over the type itself
912 tidyOpenType :: TidyEnv -> Type -> (TidyEnv, Type)
914 = (env', tidyType env' ty)
916 env' = foldl go env (varSetElems (tyVarsOfType ty))
917 go env tyvar = fst (tidyTyVar env tyvar)
919 tidyOpenTypes :: TidyEnv -> [Type] -> (TidyEnv, [Type])
920 tidyOpenTypes env tys = mapAccumL tidyOpenType env tys
922 tidyTopType :: Type -> Type
923 tidyTopType ty = tidyType emptyTidyEnv ty
927 tidyIPName :: Name -> Name
929 = mkLocalName (getUnique name) (getOccName name) noSrcLoc
933 %************************************************************************
935 \subsection{Boxedness and liftedness}
937 %************************************************************************
940 isUnboxedType :: Type -> Bool
941 isUnboxedType ty = not (isFollowableRep (typePrimRep ty))
943 isUnLiftedType :: Type -> Bool
944 -- isUnLiftedType returns True for forall'd unlifted types:
945 -- x :: forall a. Int#
946 -- I found bindings like these were getting floated to the top level.
947 -- They are pretty bogus types, mind you. It would be better never to
950 isUnLiftedType (ForAllTy tv ty) = isUnLiftedType ty
951 isUnLiftedType (NoteTy _ ty) = isUnLiftedType ty
952 isUnLiftedType (TyConApp tc _) = isUnLiftedTyCon tc
953 isUnLiftedType other = False
955 isUnboxedTupleType :: Type -> Bool
956 isUnboxedTupleType ty = case splitTyConApp_maybe ty of
957 Just (tc, ty_args) -> isUnboxedTupleTyCon tc
960 -- Should only be applied to *types*; hence the assert
961 isAlgType :: Type -> Bool
962 isAlgType ty = case splitTyConApp_maybe ty of
963 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
967 -- Should only be applied to *types*; hence the assert
968 isDataType :: Type -> Bool
969 isDataType ty = case splitTyConApp_maybe ty of
970 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
974 isNewType :: Type -> Bool
975 isNewType ty = case splitTyConApp_maybe ty of
976 Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
982 %************************************************************************
984 \subsection{Sequencing on types
986 %************************************************************************
989 seqType :: Type -> ()
990 seqType (TyVarTy tv) = tv `seq` ()
991 seqType (AppTy t1 t2) = seqType t1 `seq` seqType t2
992 seqType (FunTy t1 t2) = seqType t1 `seq` seqType t2
993 seqType (NoteTy note t2) = seqNote note `seq` seqType t2
994 seqType (TyConApp tc tys) = tc `seq` seqTypes tys
995 seqType (ForAllTy tv ty) = tv `seq` seqType ty
997 seqTypes :: [Type] -> ()
999 seqTypes (ty:tys) = seqType ty `seq` seqTypes tys
1001 seqNote :: TyNote -> ()
1002 seqNote (SynNote ty) = seqType ty
1003 seqNote (FTVNote set) = sizeUniqSet set `seq` ()
1004 seqNote (UsgNote usg) = usg `seq` ()
1005 seqNote (IPNote nm) = nm `seq` ()