ghc/compiler/types/Type.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
   3 %
   4 \section[Type]{Type - public interface}
   5
   6 \begin{code}
   7 module Type (
   8         -- re-exports from TypeRep:
   9         Type,
  10         Kind, TyVarSubst,
  11
  12         superKind, superBoxity,                         -- KX and BX respectively
  13         boxedBoxity, unboxedBoxity,                     -- :: BX
  14         openKindCon,                                    -- :: KX
  15         typeCon,                                        -- :: BX -> KX
  16         boxedTypeKind, unboxedTypeKind, openTypeKind,   -- :: KX
  17         mkArrowKind, mkArrowKinds,                      -- :: KX -> KX -> KX
  18
  19         funTyCon,
  20
  21         -- exports from this module:
  22         hasMoreBoxityInfo, defaultKind,
  23
  24         mkTyVarTy, mkTyVarTys, getTyVar, getTyVar_maybe, isTyVarTy,
  25
  26         mkAppTy, mkAppTys, splitAppTy, splitAppTys, splitAppTy_maybe,
  27
  28         mkFunTy, mkFunTys, splitFunTy, splitFunTy_maybe, splitFunTys, splitFunTysN,
  29         funResultTy, funArgTy, zipFunTys,
  30
  31         mkTyConApp, mkTyConTy, splitTyConApp_maybe,
  32         splitAlgTyConApp_maybe, splitAlgTyConApp,
  33         mkDictTy, mkDictTys, mkPredTy, splitPredTy_maybe, splitDictTy_maybe, isDictTy,
  34
  35         mkSynTy, isSynTy, deNoteType,
  36
  37         repType, splitRepFunTys, splitNewType_maybe, typePrimRep,
  38
  39         UsageAnn(..), mkUsgTy, isUsgTy{- dont use -}, isNotUsgTy, splitUsgTy, unUsgTy, tyUsg,
  40         mkUsForAllTy, mkUsForAllTys, splitUsForAllTys, substUsTy,
  41
  42         mkForAllTy, mkForAllTys, splitForAllTy_maybe, splitForAllTys,
  43         applyTy, applyTys, hoistForAllTys,
  44
  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,
  50         getDFunTyKey,
  51
  52         -- Lifting and boxity
  53         isUnLiftedType, isUnboxedType, isUnboxedTupleType, isAlgType, isDataType, isNewType,
  54
  55         -- Free variables
  56         tyVarsOfType, tyVarsOfTypes, tyVarsOfPred, tyVarsOfTheta,
  57         namesOfType, typeKind, addFreeTyVars,
  58
  59         -- Tidying up for printing
  60         tidyType,     tidyTypes,
  61         tidyOpenType, tidyOpenTypes,
  62         tidyTyVar,    tidyTyVars,
  63         tidyTopType,
  64
  65         -- Seq
  66         seqType, seqTypes
  67
  68     ) where
  69
  70 #include "HsVersions.h"
  71
  72 -- We import the representation and primitive functions from TypeRep.
  73 -- Many things are reexported, but not the representation!
  74
  75 import TypeRep
  76
  77 -- Other imports:
  78
  79 import {-# SOURCE #-}   DataCon( DataCon, dataConRepType )
  80 import {-# SOURCE #-}   PprType( pprType, pprPred )     -- Only called in debug messages
  81 import {-# SOURCE #-}   Subst  ( mkTyVarSubst, substTy )
  82
  83 -- friends:
  84 import Var      ( TyVar, Var, UVar,
  85                   tyVarKind, tyVarName, setTyVarName, isId, idType,
  86                 )
  87 import VarEnv
  88 import VarSet
  89
  90 import Name     ( Name, NamedThing(..), OccName, mkLocalName, tidyOccName )
  91 import NameSet
  92 import Class    ( classTyCon, Class, ClassPred, ClassContext )
  93 import TyCon    ( TyCon,
  94                   isUnboxedTupleTyCon, isUnLiftedTyCon,
  95                   isFunTyCon, isDataTyCon, isNewTyCon, newTyConRep,
  96                   isAlgTyCon, isSynTyCon, tyConArity,
  97                   tyConKind, tyConDataCons, getSynTyConDefn,
  98                   tyConPrimRep, tyConClass_maybe
  99                 )
 100
 101 -- others
 102 import SrcLoc           ( noSrcLoc )
 103 import Maybes           ( maybeToBool )
 104 import PrimRep          ( PrimRep(..), isFollowableRep )
 105 import Unique           ( Uniquable(..) )
 106 import Util             ( mapAccumL, seqList )
 107 import Outputable
 108 import UniqSet          ( sizeUniqSet )         -- Should come via VarSet
 109 \end{code}
 110
 111
 112 %************************************************************************
 113 %*                                                                      *
 114 \subsection{Stuff to do with kinds.}
 115 %*                                                                      *
 116 %************************************************************************
 117
 118 \begin{code}
 119 hasMoreBoxityInfo :: Kind -> Kind -> Bool
 120 hasMoreBoxityInfo k1 k2
 121   | k2 == openTypeKind = True
 122   | otherwise          = k1 == k2
 123
 124 defaultKind :: Kind -> Kind
 125 -- Used when generalising: default kind '?' to '*'
 126 defaultKind kind | kind == openTypeKind = boxedTypeKind
 127                  | otherwise            = kind
 128 \end{code}
 129
 130
 131 %************************************************************************
 132 %*                                                                      *
 133 \subsection{Constructor-specific functions}
 134 %*                                                                      *
 135 %************************************************************************
 136
 137
 138 ---------------------------------------------------------------------
 139                                 TyVarTy
 140                                 ~~~~~~~
 141 \begin{code}
 142 mkTyVarTy  :: TyVar   -> Type
 143 mkTyVarTy  = TyVarTy
 144
 145 mkTyVarTys :: [TyVar] -> [Type]
 146 mkTyVarTys = map mkTyVarTy -- a common use of mkTyVarTy
 147
 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)
 152
 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
 157
 158 isTyVarTy :: Type -> Bool
 159 isTyVarTy (TyVarTy tv)  = True
 160 isTyVarTy (NoteTy _ ty) = isTyVarTy ty
 161 isTyVarTy other         = False
 162 \end{code}
 163
 164
 165 ---------------------------------------------------------------------
 166                                 AppTy
 167                                 ~~~~~
 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
 170 invariant: use it.
 171
 172 \begin{code}
 173 mkAppTy orig_ty1 orig_ty2 = ASSERT2( isNotUsgTy orig_ty1 && isNotUsgTy orig_ty2, pprType orig_ty1 <+> text "to" <+> pprType orig_ty2 )
 174                             mk_app orig_ty1
 175   where
 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
 179
 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 )
 188                               mk_app orig_ty1
 189   where
 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
 194
 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 []
 201                             where
 202                                split [ty2]    acc = Just (TyConApp tc (reverse acc), ty2)
 203                                split (ty:tys) acc = split tys (ty:acc)
 204
 205 splitAppTy_maybe other            = Nothing
 206
 207 splitAppTy :: Type -> (Type, Type)
 208 splitAppTy ty = case splitAppTy_maybe ty of
 209                         Just pr -> pr
 210                         Nothing -> panic "splitAppTy"
 211
 212 splitAppTys :: Type -> (Type, [Type])
 213 splitAppTys ty = split ty ty []
 214   where
 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)
 221 \end{code}
 222
 223
 224 ---------------------------------------------------------------------
 225                                 FunTy
 226                                 ~~~~~
 227
 228 \begin{code}
 229 mkFunTy :: Type -> Type -> Type
 230 mkFunTy arg res = FunTy arg res
 231
 232 mkFunTys :: [Type] -> Type -> Type
 233 mkFunTys tys ty = foldr FunTy ty tys
 234
 235 splitFunTy :: Type -> (Type, Type)
 236 splitFunTy (FunTy arg res) = (arg, res)
 237 splitFunTy (NoteTy _ ty)   = splitFunTy ty
 238
 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
 244
 245 splitFunTys :: Type -> ([Type], Type)
 246 splitFunTys ty = split [] ty ty
 247   where
 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)
 253
 254 splitFunTysN :: String -> Int -> Type -> ([Type], Type)
 255 splitFunTysN msg orig_n orig_ty = split orig_n [] orig_ty orig_ty
 256   where
 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)
 261
 262 zipFunTys :: Outputable a => [a] -> Type -> ([(a,Type)], Type)
 263 zipFunTys orig_xs orig_ty = split [] orig_xs orig_ty orig_ty
 264   where
 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)
 269
 270 funResultTy :: Type -> Type
 271 funResultTy (FunTy arg res) = res
 272 funResultTy (NoteTy _ ty)   = funResultTy ty
 273 funResultTy ty              = pprPanic "funResultTy" (pprType ty)
 274
 275 funArgTy :: Type -> Type
 276 funArgTy (FunTy arg res) = arg
 277 funArgTy (NoteTy _ ty)   = funArgTy ty
 278 funArgTy ty              = pprPanic "funArgTy" (pprType ty)
 279 \end{code}
 280
 281
 282 ---------------------------------------------------------------------
 283                                 TyConApp
 284                                 ~~~~~~~~
 285
 286 \begin{code}
 287 mkTyConApp :: TyCon -> [Type] -> Type
 288 mkTyConApp tycon tys
 289   | isFunTyCon tycon && length tys == 2
 290   = case tys of
 291         (ty1:ty2:_) -> FunTy ty1 ty2
 292
 293   | otherwise
 294   = ASSERT(not (isSynTyCon tycon))
 295     TyConApp tycon tys
 296
 297 mkTyConTy :: TyCon -> Type
 298 mkTyConTy tycon = ASSERT( not (isSynTyCon tycon) )
 299                   TyConApp tycon []
 300
 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 ..
 304
 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
 310
 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.
 315
 316 splitAlgTyConApp_maybe :: Type -> Maybe (TyCon, [Type], [DataCon])
 317 splitAlgTyConApp_maybe (TyConApp tc tys)
 318   | isAlgTyCon tc &&
 319     tyConArity tc == length tys      = Just (tc, tys, tyConDataCons tc)
 320 splitAlgTyConApp_maybe (NoteTy (IPNote _) ty)
 321                                      = Nothing
 322 splitAlgTyConApp_maybe (NoteTy _ ty) = splitAlgTyConApp_maybe ty
 323 splitAlgTyConApp_maybe other         = Nothing
 324
 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
 330 #ifdef DEBUG
 331 splitAlgTyConApp ty = pprPanic "splitAlgTyConApp" (pprType ty)
 332 #endif
 333 \end{code}
 334
 335 "Dictionary" types are just ordinary data types, but you can
 336 tell from the type constructor whether it's a dictionary or not.
 337
 338 \begin{code}
 339 mkDictTy :: Class -> [Type] -> Type
 340 mkDictTy clas tys = TyConApp (classTyCon clas) tys
 341
 342 mkDictTys :: ClassContext -> [Type]
 343 mkDictTys cxt = [mkDictTy cls tys | (cls,tys) <- cxt]
 344
 345 mkPredTy :: PredType -> Type
 346 mkPredTy (Class clas tys) = TyConApp (classTyCon clas) tys
 347 mkPredTy (IParam n ty)    = NoteTy (IPNote n) ty
 348
 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)
 353   where
 354      maybe_class = tyConClass_maybe tc
 355      Just clas   = maybe_class
 356
 357 splitPredTy_maybe (NoteTy (IPNote n) ty)
 358                                 = Just (IParam n ty)
 359 splitPredTy_maybe (NoteTy _ ty) = splitPredTy_maybe ty
 360 splitPredTy_maybe other         = Nothing
 361
 362 splitDictTy_maybe :: Type -> Maybe (Class, [Type])
 363 splitDictTy_maybe ty
 364   = case splitPredTy_maybe ty of
 365     Just p  -> getClassTys_maybe p
 366     Nothing -> Nothing
 367
 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
 373   = True
 374 isDictTy (NoteTy _ ty)  = isDictTy ty
 375 isDictTy other          = False
 376 \end{code}
 377
 378 ---------------------------------------------------------------------
 379                                 SynTy
 380                                 ~~~~~
 381
 382 \begin{code}
 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)
 389   where
 390     (tyvars, body) = getSynTyConDefn syn_tycon
 391
 392 isSynTy (NoteTy (SynNote _) _) = True
 393 isSynTy other                  = False
 394
 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)
 403 \end{code}
 404
 405 Notes on type synonyms
 406 ~~~~~~~~~~~~~~~~~~~~~~
 407 The various "split" functions (splitFunTy, splitRhoTy, splitForAllTy) try
 408 to return type synonyms whereever possible. Thus
 409
 410         type Foo a = a -> a
 411
 412 we want
 413         splitFunTys (a -> Foo a) = ([a], Foo a)
 414 not                                ([a], a -> a)
 415
 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.
 418
 419
 420                 Representation types
 421                 ~~~~~~~~~~~~~~~~~~~~
 422
 423 repType looks through
 424         (a) for-alls, and
 425         (b) newtypes
 426         (c) synonyms
 427 It's useful in the back end where we're not
 428 interested in newtypes anymore.
 429
 430 \begin{code}
 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
 436                             Nothing  -> ty
 437
 438 splitRepFunTys :: Type -> ([Type], Type)
 439 -- Like splitFunTys, but looks through newtypes and for-alls
 440 splitRepFunTys ty = split [] (repType ty)
 441   where
 442     split args (FunTy arg res)  = split (arg:args) (repType res)
 443     split args ty               = (reverse args, ty)
 444
 445 typePrimRep :: Type -> PrimRep
 446 typePrimRep ty = case repType ty of
 447                    TyConApp tc _ -> tyConPrimRep tc
 448                    FunTy _ _     -> PtrRep
 449                    AppTy _ _     -> PtrRep      -- ??
 450                    TyVarTy _     -> PtrRep
 451
 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)
 456                                      = Nothing
 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)
 463                                          Nothing     -> Nothing
 464 splitNewType_maybe other             = Nothing
 465 \end{code}
 466
 467
 468
 469 ---------------------------------------------------------------------
 470                                 UsgNote
 471                                 ~~~~~~~
 472
 473 NB: Invariant: if present, usage note is at the very top of the type.
 474 This should be carefully preserved.
 475
 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
 481 1999-07)
 482
 483 \begin{code}
 484 mkUsgTy :: UsageAnn -> Type -> Type
 485 #ifndef USMANY
 486 mkUsgTy UsMany ty = ASSERT2( isNotUsgTy ty, pprType ty )
 487                     ty
 488 #endif
 489 mkUsgTy usg    ty = ASSERT2( isNotUsgTy ty, pprType ty )
 490                     NoteTy (UsgNote usg) ty
 491
 492 -- The isUsgTy function is utterly useless if UsManys are omitted.
 493 -- Be warned!  KSW 1999-04.
 494 isUsgTy :: Type -> Bool
 495 #ifndef USMANY
 496 isUsgTy _ = True
 497 #else
 498 isUsgTy (NoteTy (UsgForAll _) ty) = isUsgTy ty
 499 isUsgTy (NoteTy (UsgNote   _) _ ) = True
 500 isUsgTy other                     = False
 501 #endif
 502
 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
 510
 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 )
 516                                               Just (usg,ty2)
 517 splitUsgTy_maybe ty@(NoteTy (UsgForAll _) _) = pprPanic "splitUsgTy_maybe:" $ pprType ty
 518 splitUsgTy_maybe ty                          = Nothing
 519
 520 splitUsgTy :: Type -> (UsageAnn,Type)
 521 splitUsgTy ty = case splitUsgTy_maybe ty of
 522                   Just ans -> ans
 523                   Nothing  ->
 524 #ifndef USMANY
 525                               (UsMany,ty)
 526 #else
 527                               pprPanic "splitUsgTy: no usage annot:" $ pprType ty
 528 #endif
 529
 530 tyUsg :: Type -> UsageAnn
 531 tyUsg = fst . splitUsgTy
 532
 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 )
 537                                ty1
 538                Nothing      -> ty
 539
 540 mkUsForAllTy :: UVar -> Type -> Type
 541 mkUsForAllTy uv ty = NoteTy (UsgForAll uv) ty
 542
 543 mkUsForAllTys :: [UVar] -> Type -> Type
 544 mkUsForAllTys uvs ty = foldr (NoteTy . UsgForAll) ty uvs
 545
 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)
 550
 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
 556                                                              Nothing -> note)
 557                                                           (substUsTy ve ty)
 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))
 561                                                           (substUsTy ve ty2)
 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)
 565                                                          (substUsTy ve ty2)
 566 substUsTy ve    (FunTy   ty1                ty2) = FunTy (substUsTy ve ty1)
 567                                                          (substUsTy ve ty2)
 568 substUsTy ve    (TyConApp tyc               tys) = TyConApp tyc (map (substUsTy ve) tys)
 569 substUsTy ve    (ForAllTy yv                ty ) = ForAllTy yv (substUsTy ve ty)
 570 \end{code}
 571
 572
 573 ---------------------------------------------------------------------
 574                                 ForAllTy
 575                                 ~~~~~~~~
 576
 577 We need to be clever here with usage annotations; they need to be
 578 lifted or lowered through the forall as appropriate.
 579
 580 \begin{code}
 581 mkForAllTy :: TyVar -> Type -> Type
 582 mkForAllTy tyvar ty = case splitUsgTy_maybe ty of
 583                         Just (usg,ty') -> NoteTy (UsgNote usg)
 584                                                  (ForAllTy tyvar ty')
 585                         Nothing        -> ForAllTy tyvar ty
 586
 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
 592
 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
 598   where
 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
 603
 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 []
 609    where
 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)
 614 \end{code}
 615
 616 -- (mkPiType now in CoreUtils)
 617
 618 Applying a for-all to its arguments
 619
 620 \begin{code}
 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"
 628
 629 applyTys :: Type -> [Type] -> Type
 630 applyTys fun_ty arg_tys
 631  = substTy (mkTyVarSubst tvs arg_tys) ty
 632  where
 633    (tvs, ty) = split fun_ty arg_tys
 634
 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"
 648 \end{code}
 649
 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.
 653
 654 \begin{code}
 655 hoistForAllTys :: Type -> Type
 656         -- Move all the foralls to the top
 657         -- e.g.  T -> forall a. a  ==>   forall a. T -> a
 658 hoistForAllTys ty
 659   = case hoist ty of { (tvs, body) -> mkForAllTys tvs body }
 660   where
 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)
 667                }}}
 668 \end{code}
 669
 670
 671 %************************************************************************
 672 %*                                                                      *
 673 \subsection{Stuff to do with the source-language types}
 674
 675 PredType and ThetaType are used in types for expressions and bindings.
 676 ClassPred and ClassContext are used in class and instance declarations.
 677 %*                                                                      *
 678 %************************************************************************
 679
 680 \begin{code}
 681 data PredType  = Class  Class [Type]
 682                | IParam Name  Type
 683                deriving( Eq, Ord )
 684
 685 type ThetaType    = [PredType]
 686 type RhoType      = Type
 687 type TauType      = Type
 688 type SigmaType    = Type
 689 \end{code}
 690
 691 \begin{code}
 692 instance Outputable PredType where
 693     ppr = pprPred
 694 \end{code}
 695
 696 \begin{code}
 697 mkClassPred clas tys = Class clas tys
 698
 699 getClassTys_maybe :: PredType -> Maybe ClassPred
 700 getClassTys_maybe (Class clas tys) = Just (clas, tys)
 701 getClassTys_maybe _                = Nothing
 702
 703 ipName_maybe :: PredType -> Maybe Name
 704 ipName_maybe (IParam n _) = Just n
 705 ipName_maybe _            = Nothing
 706
 707 classesToPreds cts = map (uncurry Class) cts
 708
 709 classesOfPreds :: ThetaType -> ClassContext
 710 classesOfPreds theta = [(clas,tys) | Class clas tys <- theta]
 711 \end{code}
 712
 713 @isTauTy@ tests for nested for-alls.
 714
 715 \begin{code}
 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
 724 \end{code}
 725
 726 \begin{code}
 727 mkRhoTy :: [PredType] -> Type -> Type
 728 mkRhoTy theta ty = foldr (\p r -> FunTy (mkPredTy p) r) ty theta
 729
 730 splitRhoTy :: Type -> ([PredType], Type)
 731 splitRhoTy ty = split ty ty []
 732  where
 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)
 739 \end{code}
 740
 741
 742
 743 \begin{code}
 744 mkSigmaTy tyvars theta tau = mkForAllTys tyvars (mkRhoTy theta tau)
 745
 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
 751           isPredTy _                     = False
 752 isSigmaTy (NoteTy (IPNote _) _) = False
 753 isSigmaTy (NoteTy _ ty)         = isSigmaTy ty
 754 isSigmaTy (ForAllTy tyvar ty)   = True
 755 isSigmaTy _                     = False
 756
 757 splitSigmaTy :: Type -> ([TyVar], [PredType], Type)
 758 splitSigmaTy ty =
 759   (tyvars, theta, tau)
 760  where
 761   (tyvars,rho) = splitForAllTys ty
 762   (theta,tau)  = splitRhoTy rho
 763 \end{code}
 764
 765 \begin{code}
 766 getDFunTyKey :: Type -> OccName -- Get some string from a type, to be used to
 767                                 -- construct a dictionary function name
 768 getDFunTyKey (TyVarTy tv)    = getOccName tv
 769 getDFunTyKey (TyConApp tc _) = getOccName tc
 770 getDFunTyKey (AppTy fun _)   = getDFunTyKey fun
 771 getDFunTyKey (NoteTy _ t)    = getDFunTyKey t
 772 getDFunTyKey (FunTy arg _)   = getOccName funTyCon
 773 getDFunTyKey (ForAllTy _ t)  = getDFunTyKey t
 774 \end{code}
 775
 776
 777 %************************************************************************
 778 %*                                                                      *
 779 \subsection{Kinds and free variables}
 780 %*                                                                      *
 781 %************************************************************************
 782
 783 ---------------------------------------------------------------------
 784                 Finding the kind of a type
 785                 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 786 \begin{code}
 787 typeKind :: Type -> Kind
 788
 789 typeKind (TyVarTy tyvar)        = tyVarKind tyvar
 790 typeKind (TyConApp tycon tys)   = foldr (\_ k -> funResultTy k) (tyConKind tycon) tys
 791 typeKind (NoteTy _ ty)          = typeKind ty
 792 typeKind (AppTy fun arg)        = funResultTy (typeKind fun)
 793
 794 typeKind (FunTy arg res)        = fix_up (typeKind res)
 795                                 where
 796                                   fix_up (TyConApp tycon _) |  tycon == typeCon
 797                                                             || tycon == openKindCon = boxedTypeKind
 798                                   fix_up (NoteTy _ kind) = fix_up kind
 799                                   fix_up kind            = kind
 800                 -- The basic story is
 801                 --      typeKind (FunTy arg res) = typeKind res
 802                 -- But a function is boxed regardless of its result type
 803                 -- Hence the strange fix-up.
 804                 -- Note that 'res', being the result of a FunTy, can't have
 805                 -- a strange kind like (*->*).
 806
 807 typeKind (ForAllTy tv ty)       = typeKind ty
 808 \end{code}
 809
 810
 811 ---------------------------------------------------------------------
 812                 Free variables of a type
 813                 ~~~~~~~~~~~~~~~~~~~~~~~~
 814 \begin{code}
 815 tyVarsOfType :: Type -> TyVarSet
 816
 817 tyVarsOfType (TyVarTy tv)               = unitVarSet tv
 818 tyVarsOfType (TyConApp tycon tys)       = tyVarsOfTypes tys
 819 tyVarsOfType (NoteTy (FTVNote tvs) ty2) = tvs
 820 tyVarsOfType (NoteTy (SynNote ty1) ty2) = tyVarsOfType ty1
 821 tyVarsOfType (NoteTy (UsgNote _) ty)    = tyVarsOfType ty
 822 tyVarsOfType (NoteTy (UsgForAll _) ty)  = tyVarsOfType ty
 823 tyVarsOfType (NoteTy (IPNote _) ty)     = tyVarsOfType ty
 824 tyVarsOfType (FunTy arg res)            = tyVarsOfType arg `unionVarSet` tyVarsOfType res
 825 tyVarsOfType (AppTy fun arg)            = tyVarsOfType fun `unionVarSet` tyVarsOfType arg
 826 tyVarsOfType (ForAllTy tyvar ty)        = tyVarsOfType ty `minusVarSet` unitVarSet tyvar
 827
 828 tyVarsOfTypes :: [Type] -> TyVarSet
 829 tyVarsOfTypes tys = foldr (unionVarSet.tyVarsOfType) emptyVarSet tys
 830
 831 tyVarsOfPred :: PredType -> TyVarSet
 832 tyVarsOfPred (Class clas tys) = tyVarsOfTypes tys
 833 tyVarsOfPred (IParam n ty)    = tyVarsOfType ty
 834
 835 tyVarsOfTheta :: ThetaType -> TyVarSet
 836 tyVarsOfTheta = foldr (unionVarSet . tyVarsOfPred) emptyVarSet
 837
 838 -- Add a Note with the free tyvars to the top of the type
 839 -- (but under a usage if there is one)
 840 addFreeTyVars :: Type -> Type
 841 addFreeTyVars (NoteTy note@(UsgNote   _) ty) = NoteTy note (addFreeTyVars ty)
 842 addFreeTyVars (NoteTy note@(UsgForAll _) ty) = NoteTy note (addFreeTyVars ty)
 843 addFreeTyVars ty@(NoteTy (FTVNote _) _)      = ty
 844 addFreeTyVars ty                             = NoteTy (FTVNote (tyVarsOfType ty)) ty
 845
 846 -- Find the free names of a type, including the type constructors and classes it mentions
 847 namesOfType :: Type -> NameSet
 848 namesOfType (TyVarTy tv)                = unitNameSet (getName tv)
 849 namesOfType (TyConApp tycon tys)        = unitNameSet (getName tycon) `unionNameSets`
 850                                           namesOfTypes tys
 851 namesOfType (NoteTy (SynNote ty1) ty2)  = namesOfType ty1
 852 namesOfType (NoteTy other_note    ty2)  = namesOfType ty2
 853 namesOfType (FunTy arg res)             = namesOfType arg `unionNameSets` namesOfType res
 854 namesOfType (AppTy fun arg)             = namesOfType fun `unionNameSets` namesOfType arg
 855 namesOfType (ForAllTy tyvar ty)         = namesOfType ty `minusNameSet` unitNameSet (getName tyvar)
 856
 857 namesOfTypes tys = foldr (unionNameSets . namesOfType) emptyNameSet tys
 858 \end{code}
 859
 860
 861 %************************************************************************
 862 %*                                                                      *
 863 \subsection{TidyType}
 864 %*                                                                      *
 865 %************************************************************************
 866
 867 tidyTy tidies up a type for printing in an error message, or in
 868 an interface file.
 869
 870 It doesn't change the uniques at all, just the print names.
 871
 872 \begin{code}
 873 tidyTyVar :: TidyEnv -> TyVar -> (TidyEnv, TyVar)
 874 tidyTyVar env@(tidy_env, subst) tyvar
 875   = case lookupVarEnv subst tyvar of
 876
 877         Just tyvar' ->  -- Already substituted
 878                 (env, tyvar')
 879
 880         Nothing ->      -- Make a new nice name for it
 881
 882                 case tidyOccName tidy_env (getOccName name) of
 883                     (tidy', occ') ->    -- New occname reqd
 884                                 ((tidy', subst'), tyvar')
 885                               where
 886                                 subst' = extendVarEnv subst tyvar tyvar'
 887                                 tyvar' = setTyVarName tyvar name'
 888                                 name'  = mkLocalName (getUnique name) occ' noSrcLoc
 889                                         -- Note: make a *user* tyvar, so it printes nicely
 890                                         -- Could extract src loc, but no need.
 891   where
 892     name = tyVarName tyvar
 893
 894 tidyTyVars env tyvars = mapAccumL tidyTyVar env tyvars
 895
 896 tidyType :: TidyEnv -> Type -> Type
 897 tidyType env@(tidy_env, subst) ty
 898   = go ty
 899   where
 900     go (TyVarTy tv)         = case lookupVarEnv subst tv of
 901                                 Nothing  -> TyVarTy tv
 902                                 Just tv' -> TyVarTy tv'
 903     go (TyConApp tycon tys) = let args = map go tys
 904                               in args `seqList` TyConApp tycon args
 905     go (NoteTy note ty)     = (NoteTy SAPPLY (go_note note)) SAPPLY (go ty)
 906     go (AppTy fun arg)      = (AppTy SAPPLY (go fun)) SAPPLY (go arg)
 907     go (FunTy fun arg)      = (FunTy SAPPLY (go fun)) SAPPLY (go arg)
 908     go (ForAllTy tv ty)     = ForAllTy tvp SAPPLY (tidyType envp ty)
 909                               where
 910                                 (envp, tvp) = tidyTyVar env tv
 911
 912     go_note (SynNote ty)        = SynNote SAPPLY (go ty)
 913     go_note note@(FTVNote ftvs) = note  -- No need to tidy the free tyvars
 914     go_note note@(UsgNote _)    = note  -- Usage annotation is already tidy
 915     go_note note@(UsgForAll _)  = note  -- Uvar binder is already tidy
 916     go_note (IPNote n)          = IPNote (tidyIPName n)
 917
 918 tidyTypes  env tys    = map (tidyType env) tys
 919 \end{code}
 920
 921
 922 @tidyOpenType@ grabs the free type variables, tidies them
 923 and then uses @tidyType@ to work over the type itself
 924
 925 \begin{code}
 926 tidyOpenType :: TidyEnv -> Type -> (TidyEnv, Type)
 927 tidyOpenType env ty
 928   = (env', tidyType env' ty)
 929   where
 930     env'         = foldl go env (varSetElems (tyVarsOfType ty))
 931     go env tyvar = fst (tidyTyVar env tyvar)
 932
 933 tidyOpenTypes :: TidyEnv -> [Type] -> (TidyEnv, [Type])
 934 tidyOpenTypes env tys = mapAccumL tidyOpenType env tys
 935
 936 tidyTopType :: Type -> Type
 937 tidyTopType ty = tidyType emptyTidyEnv ty
 938 \end{code}
 939
 940 \begin{code}
 941 tidyIPName :: Name -> Name
 942 tidyIPName name
 943   = mkLocalName (getUnique name) (getOccName name) noSrcLoc
 944 \end{code}
 945
 946
 947 %************************************************************************
 948 %*                                                                      *
 949 \subsection{Boxedness and liftedness}
 950 %*                                                                      *
 951 %************************************************************************
 952
 953 \begin{code}
 954 isUnboxedType :: Type -> Bool
 955 isUnboxedType ty = not (isFollowableRep (typePrimRep ty))
 956
 957 isUnLiftedType :: Type -> Bool
 958         -- isUnLiftedType returns True for forall'd unlifted types:
 959         --      x :: forall a. Int#
 960         -- I found bindings like these were getting floated to the top level.
 961         -- They are pretty bogus types, mind you.  It would be better never to
 962         -- construct them
 963
 964 isUnLiftedType (ForAllTy tv ty) = isUnLiftedType ty
 965 isUnLiftedType (NoteTy _ ty)    = isUnLiftedType ty
 966 isUnLiftedType (TyConApp tc _)  = isUnLiftedTyCon tc
 967 isUnLiftedType other            = False
 968
 969 isUnboxedTupleType :: Type -> Bool
 970 isUnboxedTupleType ty = case splitTyConApp_maybe ty of
 971                            Just (tc, ty_args) -> isUnboxedTupleTyCon tc
 972                            other              -> False
 973
 974 -- Should only be applied to *types*; hence the assert
 975 isAlgType :: Type -> Bool
 976 isAlgType ty = case splitTyConApp_maybe ty of
 977                         Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
 978                                               isAlgTyCon tc
 979                         other              -> False
 980
 981 -- Should only be applied to *types*; hence the assert
 982 isDataType :: Type -> Bool
 983 isDataType ty = case splitTyConApp_maybe ty of
 984                         Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
 985                                               isDataTyCon tc
 986                         other              -> False
 987
 988 isNewType :: Type -> Bool
 989 isNewType ty = case splitTyConApp_maybe ty of
 990                         Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
 991                                               isNewTyCon tc
 992                         other              -> False
 993 \end{code}
 994
 995
 996 %************************************************************************
 997 %*                                                                      *
 998 \subsection{Sequencing on types
 999 %*                                                                      *
1000 %************************************************************************
1001
1002 \begin{code}
1003 seqType :: Type -> ()
1004 seqType (TyVarTy tv)      = tv `seq` ()
1005 seqType (AppTy t1 t2)     = seqType t1 `seq` seqType t2
1006 seqType (FunTy t1 t2)     = seqType t1 `seq` seqType t2
1007 seqType (NoteTy note t2)  = seqNote note `seq` seqType t2
1008 seqType (TyConApp tc tys) = tc `seq` seqTypes tys
1009 seqType (ForAllTy tv ty)  = tv `seq` seqType ty
1010
1011 seqTypes :: [Type] -> ()
1012 seqTypes []       = ()
1013 seqTypes (ty:tys) = seqType ty `seq` seqTypes tys
1014
1015 seqNote :: TyNote -> ()
1016 seqNote (SynNote ty)  = seqType ty
1017 seqNote (FTVNote set) = sizeUniqSet set `seq` ()
1018 seqNote (UsgNote usg) = usg `seq` ()
1019 seqNote (IPNote nm)   = nm `seq` ()
1020 \end{code}