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,                         -- :: SuperKind
  13
  14         boxedKind,                                      -- :: Kind :: BX
  15         anyBoxKind,                                     -- :: Kind :: BX
  16         typeCon,                                        -- :: KindCon :: BX -> KX
  17         anyBoxCon,                                      -- :: KindCon :: BX
  18
  19         boxedTypeKind, unboxedTypeKind, openTypeKind,   -- Kind :: superKind
  20
  21         mkArrowKind, mkArrowKinds, -- mentioned below: hasMoreBoxityInfo,
  22
  23         funTyCon,
  24
  25         -- exports from this module:
  26         hasMoreBoxityInfo,
  27
  28         mkTyVarTy, mkTyVarTys, getTyVar, getTyVar_maybe, isTyVarTy,
  29
  30         mkAppTy, mkAppTys, splitAppTy, splitAppTys, splitAppTy_maybe,
  31
  32         mkFunTy, mkFunTys, splitFunTy, splitFunTy_maybe, splitFunTys, splitFunTysN,
  33         funResultTy, funArgTy, zipFunTys,
  34
  35         mkTyConApp, mkTyConTy, splitTyConApp_maybe,
  36         splitAlgTyConApp_maybe, splitAlgTyConApp,
  37         mkDictTy, mkDictTys, mkPredTy, splitPredTy_maybe, splitDictTy_maybe, isDictTy,
  38
  39         mkSynTy, isSynTy, deNoteType,
  40
  41         repType, splitRepFunTys, splitNewType_maybe, typePrimRep,
  42
  43         UsageAnn(..), mkUsgTy, isUsgTy{- dont use -}, isNotUsgTy, splitUsgTy, unUsgTy, tyUsg,
  44         mkUsForAllTy, mkUsForAllTys, splitUsForAllTys, substUsTy,
  45
  46         mkForAllTy, mkForAllTys, splitForAllTy_maybe, splitForAllTys,
  47         applyTy, applyTys, mkPiType, hoistForAllTys,
  48
  49         TauType, RhoType, SigmaType, PredType(..), ThetaType,
  50         ClassPred, ClassContext, mkClassPred,
  51         getClassTys_maybe, ipName_maybe, classesToPreds, classesOfPreds,
  52         isTauTy, mkRhoTy, splitRhoTy,
  53         mkSigmaTy, isSigmaTy, splitSigmaTy,
  54
  55         -- Lifting and boxity
  56         isUnLiftedType, isUnboxedType, isUnboxedTupleType, isAlgType, isDataType, isNewType,
  57
  58         -- Free variables
  59         tyVarsOfType, tyVarsOfTypes, tyVarsOfPred, tyVarsOfTheta,
  60         namesOfType, typeKind, addFreeTyVars,
  61
  62         -- Tidying up for printing
  63         tidyType,     tidyTypes,
  64         tidyOpenType, tidyOpenTypes,
  65         tidyTyVar,    tidyTyVars,
  66         tidyTopType,
  67
  68         -- Seq
  69         seqType, seqTypes
  70
  71     ) where
  72
  73 #include "HsVersions.h"
  74
  75 -- We import the representation and primitive functions from TypeRep.
  76 -- Many things are reexported, but not the representation!
  77
  78 import TypeRep
  79
  80 -- Other imports:
  81
  82 import {-# SOURCE #-}   DataCon( DataCon, dataConRepType )
  83 import {-# SOURCE #-}   PprType( pprType, pprPred )     -- Only called in debug messages
  84 import {-# SOURCE #-}   Subst  ( mkTyVarSubst, substTy )
  85
  86 -- friends:
  87 import Var      ( TyVar, Var, UVar,
  88                   tyVarKind, tyVarName, setTyVarName, isId, idType,
  89                 )
  90 import VarEnv
  91 import VarSet
  92
  93 import Name     ( Name, NamedThing(..), mkLocalName, tidyOccName
  94                 )
  95 import NameSet
  96 import Class    ( classTyCon, Class, ClassPred, ClassContext )
  97 import TyCon    ( TyCon,
  98                   isUnboxedTupleTyCon, isUnLiftedTyCon,
  99                   isFunTyCon, isDataTyCon, isNewTyCon, newTyConRep,
 100                   isAlgTyCon, isSynTyCon, tyConArity,
 101                   tyConKind, tyConDataCons, getSynTyConDefn,
 102                   tyConPrimRep, tyConClass_maybe
 103                 )
 104
 105 -- others
 106 import SrcLoc           ( noSrcLoc )
 107 import Maybes           ( maybeToBool )
 108 import PrimRep          ( PrimRep(..), isFollowableRep )
 109 import Unique           ( Uniquable(..) )
 110 import Util             ( mapAccumL, seqList )
 111 import Outputable
 112 import UniqSet          ( sizeUniqSet )         -- Should come via VarSet
 113 \end{code}
 114
 115
 116 %************************************************************************
 117 %*                                                                      *
 118 \subsection{Stuff to do with kinds.}
 119 %*                                                                      *
 120 %************************************************************************
 121
 122 \begin{code}
 123 hasMoreBoxityInfo :: Kind -> Kind -> Bool
 124 hasMoreBoxityInfo k1 k2
 125   | k2 == openTypeKind = ASSERT( is_type_kind k1) True
 126   | otherwise          = k1 == k2
 127   where
 128         -- Returns true for things of form (Type x)
 129     is_type_kind k = case splitTyConApp_maybe k of
 130                         Just (tc,[_]) -> tc == typeCon
 131                         Nothing       -> False
 132 \end{code}
 133
 134
 135 %************************************************************************
 136 %*                                                                      *
 137 \subsection{Constructor-specific functions}
 138 %*                                                                      *
 139 %************************************************************************
 140
 141
 142 ---------------------------------------------------------------------
 143                                 TyVarTy
 144                                 ~~~~~~~
 145 \begin{code}
 146 mkTyVarTy  :: TyVar   -> Type
 147 mkTyVarTy  = TyVarTy
 148
 149 mkTyVarTys :: [TyVar] -> [Type]
 150 mkTyVarTys = map mkTyVarTy -- a common use of mkTyVarTy
 151
 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)
 156
 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
 161
 162 isTyVarTy :: Type -> Bool
 163 isTyVarTy (TyVarTy tv)  = True
 164 isTyVarTy (NoteTy _ ty) = isTyVarTy ty
 165 isTyVarTy other         = False
 166 \end{code}
 167
 168
 169 ---------------------------------------------------------------------
 170                                 AppTy
 171                                 ~~~~~
 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
 174 invariant: use it.
 175
 176 \begin{code}
 177 mkAppTy orig_ty1 orig_ty2 = ASSERT2( isNotUsgTy orig_ty1 && isNotUsgTy orig_ty2, pprType orig_ty1 <+> text "to" <+> pprType orig_ty2 )
 178                             mk_app orig_ty1
 179   where
 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
 183
 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 )
 192                               mk_app orig_ty1
 193   where
 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
 198
 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 []
 205                             where
 206                                split [ty2]    acc = Just (TyConApp tc (reverse acc), ty2)
 207                                split (ty:tys) acc = split tys (ty:acc)
 208
 209 splitAppTy_maybe other            = Nothing
 210
 211 splitAppTy :: Type -> (Type, Type)
 212 splitAppTy ty = case splitAppTy_maybe ty of
 213                         Just pr -> pr
 214                         Nothing -> panic "splitAppTy"
 215
 216 splitAppTys :: Type -> (Type, [Type])
 217 splitAppTys ty = split ty ty []
 218   where
 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)
 225 \end{code}
 226
 227
 228 ---------------------------------------------------------------------
 229                                 FunTy
 230                                 ~~~~~
 231
 232 \begin{code}
 233 mkFunTy :: Type -> Type -> Type
 234 mkFunTy arg res = FunTy arg res
 235
 236 mkFunTys :: [Type] -> Type -> Type
 237 mkFunTys tys ty = foldr FunTy ty tys
 238
 239 splitFunTy :: Type -> (Type, Type)
 240 splitFunTy (FunTy arg res) = (arg, res)
 241 splitFunTy (NoteTy _ ty)   = splitFunTy ty
 242
 243 splitFunTy_maybe :: Type -> Maybe (Type, Type)
 244 splitFunTy_maybe (FunTy arg res)        = Just (arg, res)
 245 splitFunTy_maybe (NoteTy (IPNote _) ty) = Nothing
 246 splitFunTy_maybe (NoteTy _ ty)          = splitFunTy_maybe ty
 247 splitFunTy_maybe other                  = Nothing
 248
 249 splitFunTys :: Type -> ([Type], Type)
 250 splitFunTys ty = split [] ty ty
 251   where
 252     split args orig_ty (FunTy arg res) = split (arg:args) res res
 253     split args orig_ty (NoteTy (IPNote _) ty)
 254                                        = (reverse args, orig_ty)
 255     split args orig_ty (NoteTy _ ty)   = split args orig_ty ty
 256     split args orig_ty ty              = (reverse args, orig_ty)
 257
 258 splitFunTysN :: String -> Int -> Type -> ([Type], Type)
 259 splitFunTysN msg orig_n orig_ty = split orig_n [] orig_ty orig_ty
 260   where
 261     split 0 args syn_ty ty              = (reverse args, syn_ty)
 262     split n args syn_ty (FunTy arg res) = split (n-1) (arg:args) res    res
 263     split n args syn_ty (NoteTy _ ty)   = split n     args       syn_ty ty
 264     split n args syn_ty ty              = pprPanic ("splitFunTysN: " ++ msg) (int orig_n <+> pprType orig_ty)
 265
 266 zipFunTys :: Outputable a => [a] -> Type -> ([(a,Type)], Type)
 267 zipFunTys orig_xs orig_ty = split [] orig_xs orig_ty orig_ty
 268   where
 269     split acc []     nty ty              = (reverse acc, nty)
 270     split acc (x:xs) nty (FunTy arg res) = split ((x,arg):acc) xs res res
 271     split acc xs     nty (NoteTy _ ty)   = split acc           xs nty ty
 272     split acc (x:xs) nty ty              = pprPanic "zipFunTys" (ppr orig_xs <+> pprType orig_ty)
 273
 274 funResultTy :: Type -> Type
 275 funResultTy (FunTy arg res) = res
 276 funResultTy (NoteTy _ ty)   = funResultTy ty
 277 funResultTy ty              = pprPanic "funResultTy" (pprType ty)
 278
 279 funArgTy :: Type -> Type
 280 funArgTy (FunTy arg res) = arg
 281 funArgTy (NoteTy _ ty)   = funArgTy ty
 282 funArgTy ty              = pprPanic "funArgTy" (pprType ty)
 283 \end{code}
 284
 285
 286 ---------------------------------------------------------------------
 287                                 TyConApp
 288                                 ~~~~~~~~
 289
 290 \begin{code}
 291 mkTyConApp :: TyCon -> [Type] -> Type
 292 mkTyConApp tycon tys
 293   | isFunTyCon tycon && length tys == 2
 294   = case tys of
 295         (ty1:ty2:_) -> FunTy ty1 ty2
 296
 297   | otherwise
 298   = ASSERT(not (isSynTyCon tycon))
 299     TyConApp tycon tys
 300
 301 mkTyConTy :: TyCon -> Type
 302 mkTyConTy tycon = ASSERT( not (isSynTyCon tycon) )
 303                   TyConApp tycon []
 304
 305 -- splitTyConApp "looks through" synonyms, because they don't
 306 -- mean a distinct type, but all other type-constructor applications
 307 -- including functions are returned as Just ..
 308
 309 splitTyConApp_maybe :: Type -> Maybe (TyCon, [Type])
 310 splitTyConApp_maybe (TyConApp tc tys)      = Just (tc, tys)
 311 splitTyConApp_maybe (FunTy arg res)        = Just (funTyCon, [arg,res])
 312 splitTyConApp_maybe (NoteTy (IPNote _) ty) = Nothing
 313 splitTyConApp_maybe (NoteTy _ ty)          = splitTyConApp_maybe ty
 314 splitTyConApp_maybe other                  = Nothing
 315
 316 -- splitAlgTyConApp_maybe looks for
 317 --      *saturated* applications of *algebraic* data types
 318 -- "Algebraic" => newtype, data type, or dictionary (not function types)
 319 -- We return the constructors too, so there had better be some.
 320
 321 splitAlgTyConApp_maybe :: Type -> Maybe (TyCon, [Type], [DataCon])
 322 splitAlgTyConApp_maybe (TyConApp tc tys)
 323   | isAlgTyCon tc &&
 324     tyConArity tc == length tys      = Just (tc, tys, tyConDataCons tc)
 325 splitAlgTyConApp_maybe (NoteTy (IPNote _) ty)
 326                                      = Nothing
 327 splitAlgTyConApp_maybe (NoteTy _ ty) = splitAlgTyConApp_maybe ty
 328 splitAlgTyConApp_maybe other         = Nothing
 329
 330 splitAlgTyConApp :: Type -> (TyCon, [Type], [DataCon])
 331         -- Here the "algebraic" property is an *assertion*
 332 splitAlgTyConApp (TyConApp tc tys) = ASSERT( isAlgTyCon tc && tyConArity tc == length tys )
 333                                      (tc, tys, tyConDataCons tc)
 334 splitAlgTyConApp (NoteTy _ ty)     = splitAlgTyConApp ty
 335 #ifdef DEBUG
 336 splitAlgTyConApp ty = pprPanic "splitAlgTyConApp" (pprType ty)
 337 #endif
 338 \end{code}
 339
 340 "Dictionary" types are just ordinary data types, but you can
 341 tell from the type constructor whether it's a dictionary or not.
 342
 343 \begin{code}
 344 mkDictTy :: Class -> [Type] -> Type
 345 mkDictTy clas tys = TyConApp (classTyCon clas) tys
 346
 347 mkDictTys :: ClassContext -> [Type]
 348 mkDictTys cxt = [mkDictTy cls tys | (cls,tys) <- cxt]
 349
 350 mkPredTy :: PredType -> Type
 351 mkPredTy (Class clas tys) = TyConApp (classTyCon clas) tys
 352 mkPredTy (IParam n ty)    = NoteTy (IPNote n) ty
 353
 354 splitPredTy_maybe :: Type -> Maybe PredType
 355 splitPredTy_maybe (TyConApp tc tys)
 356   |  maybeToBool maybe_class
 357   && tyConArity tc == length tys = Just (Class clas tys)
 358   where
 359      maybe_class = tyConClass_maybe tc
 360      Just clas   = maybe_class
 361
 362 splitPredTy_maybe (NoteTy (IPNote n) ty)
 363                                 = Just (IParam n ty)
 364 splitPredTy_maybe (NoteTy _ ty) = splitPredTy_maybe ty
 365 splitPredTy_maybe other         = Nothing
 366
 367 splitDictTy_maybe :: Type -> Maybe (Class, [Type])
 368 splitDictTy_maybe ty
 369   = case splitPredTy_maybe ty of
 370     Just p  -> getClassTys_maybe p
 371     Nothing -> Nothing
 372
 373 isDictTy :: Type -> Bool
 374         -- This version is slightly more efficient than (maybeToBool . splitDictTy)
 375 isDictTy (TyConApp tc tys)
 376   |  maybeToBool (tyConClass_maybe tc)
 377   && tyConArity tc == length tys
 378   = True
 379 isDictTy (NoteTy _ ty)  = isDictTy ty
 380 isDictTy other          = False
 381 \end{code}
 382
 383 ---------------------------------------------------------------------
 384                                 SynTy
 385                                 ~~~~~
 386
 387 \begin{code}
 388 mkSynTy syn_tycon tys
 389   = ASSERT( isSynTyCon syn_tycon )
 390     ASSERT( isNotUsgTy body )
 391     ASSERT( length tyvars == length tys )
 392     NoteTy (SynNote (TyConApp syn_tycon tys))
 393            (substTy (mkTyVarSubst tyvars tys) body)
 394   where
 395     (tyvars, body) = getSynTyConDefn syn_tycon
 396
 397 isSynTy (NoteTy (SynNote _) _) = True
 398 isSynTy other                  = False
 399
 400 deNoteType :: Type -> Type
 401         -- Sorry for the cute name
 402 deNoteType ty@(TyVarTy tyvar)   = ty
 403 deNoteType (TyConApp tycon tys) = TyConApp tycon (map deNoteType tys)
 404 deNoteType (NoteTy _ ty)        = deNoteType ty
 405 deNoteType (AppTy fun arg)      = AppTy (deNoteType fun) (deNoteType arg)
 406 deNoteType (FunTy fun arg)      = FunTy (deNoteType fun) (deNoteType arg)
 407 deNoteType (ForAllTy tv ty)     = ForAllTy tv (deNoteType ty)
 408 \end{code}
 409
 410 Notes on type synonyms
 411 ~~~~~~~~~~~~~~~~~~~~~~
 412 The various "split" functions (splitFunTy, splitRhoTy, splitForAllTy) try
 413 to return type synonyms whereever possible. Thus
 414
 415         type Foo a = a -> a
 416
 417 we want
 418         splitFunTys (a -> Foo a) = ([a], Foo a)
 419 not                                ([a], a -> a)
 420
 421 The reason is that we then get better (shorter) type signatures in
 422 interfaces.  Notably this plays a role in tcTySigs in TcBinds.lhs.
 423
 424
 425                 Representation types
 426                 ~~~~~~~~~~~~~~~~~~~~
 427
 428 repType looks through
 429         (a) for-alls, and
 430         (b) newtypes
 431         (c) synonyms
 432 It's useful in the back end where we're not
 433 interested in newtypes anymore.
 434
 435 \begin{code}
 436 repType :: Type -> Type
 437 repType (ForAllTy _ ty) = repType ty
 438 repType (NoteTy   _ ty) = repType ty
 439 repType ty              = case splitNewType_maybe ty of
 440                             Just ty' -> repType ty'     -- Still re-apply repType in case of for-all
 441                             Nothing  -> ty
 442
 443 splitRepFunTys :: Type -> ([Type], Type)
 444 -- Like splitFunTys, but looks through newtypes and for-alls
 445 splitRepFunTys ty = split [] (repType ty)
 446   where
 447     split args (FunTy arg res)  = split (arg:args) (repType res)
 448     split args ty               = (reverse args, ty)
 449
 450 typePrimRep :: Type -> PrimRep
 451 typePrimRep ty = case repType ty of
 452                    TyConApp tc _ -> tyConPrimRep tc
 453                    FunTy _ _     -> PtrRep
 454                    AppTy _ _     -> PtrRep      -- ??
 455                    TyVarTy _     -> PtrRep
 456
 457 splitNewType_maybe :: Type -> Maybe Type
 458 -- Find the representation of a newtype, if it is one
 459 -- Looks through multiple levels of newtype, but does not look through for-alls
 460 splitNewType_maybe (NoteTy (IPNote _) ty)
 461                                      = Nothing
 462 splitNewType_maybe (NoteTy _ ty)     = splitNewType_maybe ty
 463 splitNewType_maybe (TyConApp tc tys) = case newTyConRep tc of
 464                                          Just rep_ty -> ASSERT( length tys == tyConArity tc )
 465                                                 -- The assert should hold because repType should
 466                                                 -- only be applied to *types* (of kind *)
 467                                                         Just (applyTys rep_ty tys)
 468                                          Nothing     -> Nothing
 469 splitNewType_maybe other             = Nothing
 470 \end{code}
 471
 472
 473
 474 ---------------------------------------------------------------------
 475                                 UsgNote
 476                                 ~~~~~~~
 477
 478 NB: Invariant: if present, usage note is at the very top of the type.
 479 This should be carefully preserved.
 480
 481 In some parts of the compiler, comments use the _Once Upon a
 482 Polymorphic Type_ (POPL'99) usage of "rho = generalised
 483 usage-annotated type; sigma = usage-annotated type; tau =
 484 usage-annotated type except on top"; unfortunately this conflicts with
 485 the rho/tau/theta/sigma usage in the rest of the compiler.  (KSW
 486 1999-07)
 487
 488 \begin{code}
 489 mkUsgTy :: UsageAnn -> Type -> Type
 490 #ifndef USMANY
 491 mkUsgTy UsMany ty = ASSERT2( isNotUsgTy ty, pprType ty )
 492                     ty
 493 #endif
 494 mkUsgTy usg    ty = ASSERT2( isNotUsgTy ty, pprType ty )
 495                     NoteTy (UsgNote usg) ty
 496
 497 -- The isUsgTy function is utterly useless if UsManys are omitted.
 498 -- Be warned!  KSW 1999-04.
 499 isUsgTy :: Type -> Bool
 500 #ifndef USMANY
 501 isUsgTy _ = True
 502 #else
 503 isUsgTy (NoteTy (UsgForAll _) ty) = isUsgTy ty
 504 isUsgTy (NoteTy (UsgNote   _) _ ) = True
 505 isUsgTy other                     = False
 506 #endif
 507
 508 -- The isNotUsgTy function may return a false True if UsManys are omitted;
 509 -- in other words, A SSERT( isNotUsgTy ty ) may be useful but
 510 -- A SSERT( not (isNotUsg ty) ) is asking for trouble.  KSW 1999-04.
 511 isNotUsgTy :: Type -> Bool
 512 isNotUsgTy (NoteTy (UsgForAll _) _) = False
 513 isNotUsgTy (NoteTy (UsgNote   _) _) = False
 514 isNotUsgTy other                    = True
 515
 516 -- splitUsgTy_maybe is not exported, since it is meaningless if
 517 -- UsManys are omitted.  It is used in several places in this module,
 518 -- however.  KSW 1999-04.
 519 splitUsgTy_maybe :: Type -> Maybe (UsageAnn,Type)
 520 splitUsgTy_maybe (NoteTy (UsgNote usg) ty2) = ASSERT( isNotUsgTy ty2 )
 521                                               Just (usg,ty2)
 522 splitUsgTy_maybe ty@(NoteTy (UsgForAll _) _) = pprPanic "splitUsgTy_maybe:" $ pprType ty
 523 splitUsgTy_maybe ty                          = Nothing
 524
 525 splitUsgTy :: Type -> (UsageAnn,Type)
 526 splitUsgTy ty = case splitUsgTy_maybe ty of
 527                   Just ans -> ans
 528                   Nothing  ->
 529 #ifndef USMANY
 530                               (UsMany,ty)
 531 #else
 532                               pprPanic "splitUsgTy: no usage annot:" $ pprType ty
 533 #endif
 534
 535 tyUsg :: Type -> UsageAnn
 536 tyUsg = fst . splitUsgTy
 537
 538 unUsgTy :: Type -> Type
 539 -- strip outer usage annotation if present
 540 unUsgTy ty = case splitUsgTy_maybe ty of
 541                Just (_,ty1) -> ASSERT2( isNotUsgTy ty1, pprType ty )
 542                                ty1
 543                Nothing      -> ty
 544
 545 mkUsForAllTy :: UVar -> Type -> Type
 546 mkUsForAllTy uv ty = NoteTy (UsgForAll uv) ty
 547
 548 mkUsForAllTys :: [UVar] -> Type -> Type
 549 mkUsForAllTys uvs ty = foldr (NoteTy . UsgForAll) ty uvs
 550
 551 splitUsForAllTys :: Type -> ([UVar],Type)
 552 splitUsForAllTys ty = split ty []
 553   where split (NoteTy (UsgForAll u) ty) uvs = split ty (u:uvs)
 554         split other_ty                  uvs = (reverse uvs, other_ty)
 555
 556 substUsTy :: VarEnv UsageAnn -> Type -> Type
 557 -- assumes range is fresh uvars, so no conflicts
 558 substUsTy ve    (NoteTy  note@(UsgNote (UsVar u))
 559                                             ty ) = NoteTy (case lookupVarEnv ve u of
 560                                                              Just ua -> UsgNote ua
 561                                                              Nothing -> note)
 562                                                           (substUsTy ve ty)
 563 substUsTy ve    (NoteTy  note@(UsgNote   _) ty ) = NoteTy note (substUsTy ve ty)
 564 substUsTy ve    (NoteTy  note@(UsgForAll _) ty ) = NoteTy note (substUsTy ve ty)
 565 substUsTy ve    (NoteTy  (SynNote ty1)      ty2) = NoteTy (SynNote (substUsTy ve ty1))
 566                                                           (substUsTy ve ty2)
 567 substUsTy ve    (NoteTy  note@(FTVNote _)   ty ) = NoteTy note (substUsTy ve ty)
 568 substUsTy ve ty@(TyVarTy _                     ) = ty
 569 substUsTy ve    (AppTy   ty1                ty2) = AppTy (substUsTy ve ty1)
 570                                                          (substUsTy ve ty2)
 571 substUsTy ve    (FunTy   ty1                ty2) = FunTy (substUsTy ve ty1)
 572                                                          (substUsTy ve ty2)
 573 substUsTy ve    (TyConApp tyc               tys) = TyConApp tyc (map (substUsTy ve) tys)
 574 substUsTy ve    (ForAllTy yv                ty ) = ForAllTy yv (substUsTy ve ty)
 575 \end{code}
 576
 577
 578 ---------------------------------------------------------------------
 579                                 ForAllTy
 580                                 ~~~~~~~~
 581
 582 We need to be clever here with usage annotations; they need to be
 583 lifted or lowered through the forall as appropriate.
 584
 585 \begin{code}
 586 mkForAllTy :: TyVar -> Type -> Type
 587 mkForAllTy tyvar ty = case splitUsgTy_maybe ty of
 588                         Just (usg,ty') -> NoteTy (UsgNote usg)
 589                                                  (ForAllTy tyvar ty')
 590                         Nothing        -> ForAllTy tyvar ty
 591
 592 mkForAllTys :: [TyVar] -> Type -> Type
 593 mkForAllTys tyvars ty = case splitUsgTy_maybe ty of
 594                           Just (usg,ty') -> NoteTy (UsgNote usg)
 595                                                    (foldr ForAllTy ty' tyvars)
 596                           Nothing        -> foldr ForAllTy ty tyvars
 597
 598 splitForAllTy_maybe :: Type -> Maybe (TyVar, Type)
 599 splitForAllTy_maybe ty = case splitUsgTy_maybe ty of
 600                            Just (usg,ty') -> do (tyvar,ty'') <- splitFAT_m ty'
 601                                                 return (tyvar, NoteTy (UsgNote usg) ty'')
 602                            Nothing        -> splitFAT_m ty
 603   where
 604     splitFAT_m (NoteTy (IPNote _) ty)   = Nothing
 605     splitFAT_m (NoteTy _ ty)            = splitFAT_m ty
 606     splitFAT_m (ForAllTy tyvar ty)      = Just(tyvar, ty)
 607     splitFAT_m _                        = Nothing
 608
 609 splitForAllTys :: Type -> ([TyVar], Type)
 610 splitForAllTys ty = case splitUsgTy_maybe ty of
 611                       Just (usg,ty') -> let (tvs,ty'') = split ty' ty' []
 612                                         in  (tvs, NoteTy (UsgNote usg) ty'')
 613                       Nothing        -> split ty ty []
 614    where
 615      split orig_ty (ForAllTy tv ty)       tvs = split ty ty (tv:tvs)
 616      split orig_ty (NoteTy (IPNote _) ty) tvs = (reverse tvs, orig_ty)
 617      split orig_ty (NoteTy _ ty)          tvs = split orig_ty ty tvs
 618      split orig_ty t                      tvs = (reverse tvs, orig_ty)
 619 \end{code}
 620
 621 @mkPiType@ makes a (->) type or a forall type, depending on whether
 622 it is given a type variable or a term variable.
 623
 624 \begin{code}
 625 mkPiType :: Var -> Type -> Type         -- The more polymorphic version doesn't work...
 626 mkPiType v ty | isId v    = mkFunTy (idType v) ty
 627               | otherwise = mkForAllTy v ty
 628 \end{code}
 629
 630 Applying a for-all to its arguments
 631
 632 \begin{code}
 633 applyTy :: Type -> Type -> Type
 634 applyTy (NoteTy note@(UsgNote   _) fun) arg = NoteTy note (applyTy fun arg)
 635 applyTy (NoteTy note@(UsgForAll _) fun) arg = NoteTy note (applyTy fun arg)
 636 applyTy (NoteTy _ fun)                  arg = applyTy fun arg
 637 applyTy (ForAllTy tv ty)                arg = ASSERT( isNotUsgTy arg )
 638                                               substTy (mkTyVarSubst [tv] [arg]) ty
 639 applyTy other                           arg = panic "applyTy"
 640
 641 applyTys :: Type -> [Type] -> Type
 642 applyTys fun_ty arg_tys
 643  = substTy (mkTyVarSubst tvs arg_tys) ty
 644  where
 645    (tvs, ty) = split fun_ty arg_tys
 646
 647    split fun_ty               []         = ([], fun_ty)
 648    split (NoteTy note@(UsgNote   _) fun_ty)
 649                               args       = case split fun_ty args of
 650                                              (tvs, ty) -> (tvs, NoteTy note ty)
 651    split (NoteTy note@(UsgForAll _) fun_ty)
 652                               args       = case split fun_ty args of
 653                                              (tvs, ty) -> (tvs, NoteTy note ty)
 654    split (NoteTy _ fun_ty)    args       = split fun_ty args
 655    split (ForAllTy tv fun_ty) (arg:args) = ASSERT2( isNotUsgTy arg, vcat (map pprType arg_tys) $$
 656                                                                     text "in application of" <+> pprType fun_ty)
 657                                            case split fun_ty args of
 658                                                   (tvs, ty) -> (tv:tvs, ty)
 659    split other_ty             args       = panic "applyTys"
 660 \end{code}
 661
 662 Note that we allow applications to be of usage-annotated- types, as an
 663 extension: we handle them by lifting the annotation outside.  The
 664 argument, however, must still be unannotated.
 665
 666 \begin{code}
 667 hoistForAllTys :: Type -> Type
 668         -- Move all the foralls to the top
 669         -- e.g.  T -> forall a. a  ==>   forall a. T -> a
 670 hoistForAllTys ty
 671   = case hoist ty of { (tvs, body) -> mkForAllTys tvs body }
 672   where
 673     hoist :: Type -> ([TyVar], Type)
 674     hoist ty = case splitFunTys    ty  of { (args, res) ->
 675                case splitForAllTys res of {
 676                   ([], body)  -> ([], ty) ;
 677                   (tvs1, body1) -> case hoist body1 of { (tvs2,body2) ->
 678                                    (tvs1 ++ tvs2, mkFunTys args body2)
 679                }}}
 680 \end{code}
 681
 682
 683 %************************************************************************
 684 %*                                                                      *
 685 \subsection{Stuff to do with the source-language types}
 686
 687 PredType and ThetaType are used in types for expressions and bindings.
 688 ClassPred and ClassContext are used in class and instance declarations.
 689 %*                                                                      *
 690 %************************************************************************
 691
 692 \begin{code}
 693 data PredType  = Class  Class [Type]
 694                | IParam Name  Type
 695                deriving( Eq, Ord )
 696
 697 type ThetaType    = [PredType]
 698 type RhoType      = Type
 699 type TauType      = Type
 700 type SigmaType    = Type
 701 \end{code}
 702
 703 \begin{code}
 704 instance Outputable PredType where
 705     ppr = pprPred
 706 \end{code}
 707
 708 \begin{code}
 709 mkClassPred clas tys = Class clas tys
 710
 711 getClassTys_maybe :: PredType -> Maybe ClassPred
 712 getClassTys_maybe (Class clas tys) = Just (clas, tys)
 713 getClassTys_maybe _                = Nothing
 714
 715 ipName_maybe :: PredType -> Maybe Name
 716 ipName_maybe (IParam n _) = Just n
 717 ipName_maybe _            = Nothing
 718
 719 classesToPreds cts = map (uncurry Class) cts
 720
 721 classesOfPreds theta = concatMap cvt theta
 722     where cvt (Class clas tys) = [(clas, tys)]
 723           cvt (IParam _   _  ) = []
 724 \end{code}
 725
 726 @isTauTy@ tests for nested for-alls.
 727
 728 \begin{code}
 729 isTauTy :: Type -> Bool
 730 isTauTy (TyVarTy v)             = True
 731 isTauTy (TyConApp _ tys)        = all isTauTy tys
 732 isTauTy (AppTy a b)             = isTauTy a && isTauTy b
 733 isTauTy (FunTy a b)             = isTauTy a && isTauTy b
 734 isTauTy (NoteTy (IPNote _) ty)  = False
 735 isTauTy (NoteTy _ ty)           = isTauTy ty
 736 isTauTy other                   = False
 737 \end{code}
 738
 739 \begin{code}
 740 mkRhoTy :: [PredType] -> Type -> Type
 741 mkRhoTy theta ty = foldr (\p r -> FunTy (mkPredTy p) r) ty theta
 742
 743 splitRhoTy :: Type -> ([PredType], Type)
 744 splitRhoTy ty = split ty ty []
 745  where
 746   split orig_ty (FunTy arg res) ts = case splitPredTy_maybe arg of
 747                                         Just p -> split res res (p:ts)
 748                                         Nothing   -> (reverse ts, orig_ty)
 749   split orig_ty (NoteTy (IPNote _) ty)  ts = (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)
 752 \end{code}
 753
 754
 755
 756 \begin{code}
 757 mkSigmaTy tyvars theta tau = mkForAllTys tyvars (mkRhoTy theta tau)
 758
 759 isSigmaTy :: Type -> Bool
 760 isSigmaTy (FunTy a b)           = isPredTy a
 761     where isPredTy (NoteTy (IPNote _) _) = True
 762           -- JRL could be a dict ty, but that would be polymorphic,
 763           -- and thus there would have been an outer ForAllTy
 764           isPredTy _                     = False
 765 isSigmaTy (NoteTy (IPNote _) _) = False
 766 isSigmaTy (NoteTy _ ty)         = isSigmaTy ty
 767 isSigmaTy (ForAllTy tyvar ty)   = True
 768 isSigmaTy _                     = False
 769
 770 splitSigmaTy :: Type -> ([TyVar], [PredType], Type)
 771 splitSigmaTy ty =
 772   (tyvars, theta, tau)
 773  where
 774   (tyvars,rho) = splitForAllTys ty
 775   (theta,tau)  = splitRhoTy rho
 776 \end{code}
 777
 778
 779 %************************************************************************
 780 %*                                                                      *
 781 \subsection{Kinds and free variables}
 782 %*                                                                      *
 783 %************************************************************************
 784
 785 ---------------------------------------------------------------------
 786                 Finding the kind of a type
 787                 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 788 \begin{code}
 789 typeKind :: Type -> Kind
 790
 791 typeKind (TyVarTy tyvar)        = tyVarKind tyvar
 792 typeKind (TyConApp tycon tys)   = foldr (\_ k -> funResultTy k) (tyConKind tycon) tys
 793 typeKind (NoteTy _ ty)          = typeKind ty
 794 typeKind (AppTy fun arg)        = funResultTy (typeKind fun)
 795
 796 typeKind (FunTy arg res)        = boxedTypeKind -- A function is boxed regardless of its result type
 797                                                 -- No functions at the type level, hence we don't need
 798                                                 -- to say (typeKind res).
 799
 800 typeKind (ForAllTy tv ty)       = typeKind ty
 801 \end{code}
 802
 803
 804 ---------------------------------------------------------------------
 805                 Free variables of a type
 806                 ~~~~~~~~~~~~~~~~~~~~~~~~
 807 \begin{code}
 808 tyVarsOfType :: Type -> TyVarSet
 809
 810 tyVarsOfType (TyVarTy tv)               = unitVarSet tv
 811 tyVarsOfType (TyConApp tycon tys)       = tyVarsOfTypes tys
 812 tyVarsOfType (NoteTy (FTVNote tvs) ty2) = tvs
 813 tyVarsOfType (NoteTy (SynNote ty1) ty2) = tyVarsOfType ty1
 814 tyVarsOfType (NoteTy (UsgNote _) ty)    = tyVarsOfType ty
 815 tyVarsOfType (NoteTy (UsgForAll _) ty)  = tyVarsOfType ty
 816 tyVarsOfType (NoteTy (IPNote _) ty)     = tyVarsOfType ty
 817 tyVarsOfType (FunTy arg res)            = tyVarsOfType arg `unionVarSet` tyVarsOfType res
 818 tyVarsOfType (AppTy fun arg)            = tyVarsOfType fun `unionVarSet` tyVarsOfType arg
 819 tyVarsOfType (ForAllTy tyvar ty)        = tyVarsOfType ty `minusVarSet` unitVarSet tyvar
 820
 821 tyVarsOfTypes :: [Type] -> TyVarSet
 822 tyVarsOfTypes tys = foldr (unionVarSet.tyVarsOfType) emptyVarSet tys
 823
 824 tyVarsOfPred :: PredType -> TyVarSet
 825 tyVarsOfPred (Class clas tys) = tyVarsOfTypes tys
 826 tyVarsOfPred (IParam n ty)    = tyVarsOfType ty
 827
 828 tyVarsOfTheta :: ThetaType -> TyVarSet
 829 tyVarsOfTheta = foldr (unionVarSet . tyVarsOfPred) emptyVarSet
 830
 831 -- Add a Note with the free tyvars to the top of the type
 832 -- (but under a usage if there is one)
 833 addFreeTyVars :: Type -> Type
 834 addFreeTyVars (NoteTy note@(UsgNote   _) ty) = NoteTy note (addFreeTyVars ty)
 835 addFreeTyVars (NoteTy note@(UsgForAll _) ty) = NoteTy note (addFreeTyVars ty)
 836 addFreeTyVars ty@(NoteTy (FTVNote _) _)      = ty
 837 addFreeTyVars ty                             = NoteTy (FTVNote (tyVarsOfType ty)) ty
 838
 839 -- Find the free names of a type, including the type constructors and classes it mentions
 840 namesOfType :: Type -> NameSet
 841 namesOfType (TyVarTy tv)                = unitNameSet (getName tv)
 842 namesOfType (TyConApp tycon tys)        = unitNameSet (getName tycon) `unionNameSets`
 843                                           namesOfTypes tys
 844 namesOfType (NoteTy (SynNote ty1) ty2)  = namesOfType ty1
 845 namesOfType (NoteTy other_note    ty2)  = namesOfType ty2
 846 namesOfType (FunTy arg res)             = namesOfType arg `unionNameSets` namesOfType res
 847 namesOfType (AppTy fun arg)             = namesOfType fun `unionNameSets` namesOfType arg
 848 namesOfType (ForAllTy tyvar ty)         = namesOfType ty `minusNameSet` unitNameSet (getName tyvar)
 849
 850 namesOfTypes tys = foldr (unionNameSets . namesOfType) emptyNameSet tys
 851 \end{code}
 852
 853
 854 %************************************************************************
 855 %*                                                                      *
 856 \subsection{TidyType}
 857 %*                                                                      *
 858 %************************************************************************
 859
 860 tidyTy tidies up a type for printing in an error message, or in
 861 an interface file.
 862
 863 It doesn't change the uniques at all, just the print names.
 864
 865 \begin{code}
 866 tidyTyVar :: TidyEnv -> TyVar -> (TidyEnv, TyVar)
 867 tidyTyVar env@(tidy_env, subst) tyvar
 868   = case lookupVarEnv subst tyvar of
 869
 870         Just tyvar' ->  -- Already substituted
 871                 (env, tyvar')
 872
 873         Nothing ->      -- Make a new nice name for it
 874
 875                 case tidyOccName tidy_env (getOccName name) of
 876                     (tidy', occ') ->    -- New occname reqd
 877                                 ((tidy', subst'), tyvar')
 878                               where
 879                                 subst' = extendVarEnv subst tyvar tyvar'
 880                                 tyvar' = setTyVarName tyvar name'
 881                                 name'  = mkLocalName (getUnique name) occ' noSrcLoc
 882                                         -- Note: make a *user* tyvar, so it printes nicely
 883                                         -- Could extract src loc, but no need.
 884   where
 885     name = tyVarName tyvar
 886
 887 tidyTyVars env tyvars = mapAccumL tidyTyVar env tyvars
 888
 889 tidyType :: TidyEnv -> Type -> Type
 890 tidyType env@(tidy_env, subst) ty
 891   = go ty
 892   where
 893     go (TyVarTy tv)         = case lookupVarEnv subst tv of
 894                                 Nothing  -> TyVarTy tv
 895                                 Just tv' -> TyVarTy tv'
 896     go (TyConApp tycon tys) = let args = map go tys
 897                               in args `seqList` TyConApp tycon args
 898     go (NoteTy note ty)     = (NoteTy SAPPLY (go_note note)) SAPPLY (go ty)
 899     go (AppTy fun arg)      = (AppTy SAPPLY (go fun)) SAPPLY (go arg)
 900     go (FunTy fun arg)      = (FunTy SAPPLY (go fun)) SAPPLY (go arg)
 901     go (ForAllTy tv ty)     = ForAllTy tvp SAPPLY (tidyType envp ty)
 902                               where
 903                                 (envp, tvp) = tidyTyVar env tv
 904
 905     go_note (SynNote ty)        = SynNote SAPPLY (go ty)
 906     go_note note@(FTVNote ftvs) = note  -- No need to tidy the free tyvars
 907     go_note note@(UsgNote _)    = note  -- Usage annotation is already tidy
 908     go_note note@(UsgForAll _)  = note  -- Uvar binder is already tidy
 909     go_note (IPNote n)          = IPNote (tidyIPName n)
 910
 911 tidyTypes  env tys    = map (tidyType env) tys
 912 \end{code}
 913
 914
 915 @tidyOpenType@ grabs the free type variables, tidies them
 916 and then uses @tidyType@ to work over the type itself
 917
 918 \begin{code}
 919 tidyOpenType :: TidyEnv -> Type -> (TidyEnv, Type)
 920 tidyOpenType env ty
 921   = (env', tidyType env' ty)
 922   where
 923     env'         = foldl go env (varSetElems (tyVarsOfType ty))
 924     go env tyvar = fst (tidyTyVar env tyvar)
 925
 926 tidyOpenTypes :: TidyEnv -> [Type] -> (TidyEnv, [Type])
 927 tidyOpenTypes env tys = mapAccumL tidyOpenType env tys
 928
 929 tidyTopType :: Type -> Type
 930 tidyTopType ty = tidyType emptyTidyEnv ty
 931 \end{code}
 932
 933 \begin{code}
 934 tidyIPName :: Name -> Name
 935 tidyIPName name
 936   = mkLocalName (getUnique name) (getOccName name) noSrcLoc
 937 \end{code}
 938
 939
 940 %************************************************************************
 941 %*                                                                      *
 942 \subsection{Boxedness and liftedness}
 943 %*                                                                      *
 944 %************************************************************************
 945
 946 \begin{code}
 947 isUnboxedType :: Type -> Bool
 948 isUnboxedType ty = not (isFollowableRep (typePrimRep ty))
 949
 950 isUnLiftedType :: Type -> Bool
 951         -- isUnLiftedType returns True for forall'd unlifted types:
 952         --      x :: forall a. Int#
 953         -- I found bindings like these were getting floated to the top level.
 954         -- They are pretty bogus types, mind you.  It would be better never to
 955         -- construct them
 956
 957 isUnLiftedType (ForAllTy tv ty) = isUnLiftedType ty
 958 isUnLiftedType (NoteTy _ ty)    = isUnLiftedType ty
 959 isUnLiftedType (TyConApp tc _)  = isUnLiftedTyCon tc
 960 isUnLiftedType other            = False
 961
 962 isUnboxedTupleType :: Type -> Bool
 963 isUnboxedTupleType ty = case splitTyConApp_maybe ty of
 964                            Just (tc, ty_args) -> isUnboxedTupleTyCon tc
 965                            other              -> False
 966
 967 -- Should only be applied to *types*; hence the assert
 968 isAlgType :: Type -> Bool
 969 isAlgType ty = case splitTyConApp_maybe ty of
 970                         Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
 971                                               isAlgTyCon tc
 972                         other              -> False
 973
 974 -- Should only be applied to *types*; hence the assert
 975 isDataType :: Type -> Bool
 976 isDataType ty = case splitTyConApp_maybe ty of
 977                         Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
 978                                               isDataTyCon tc
 979                         other              -> False
 980
 981 isNewType :: Type -> Bool
 982 isNewType ty = case splitTyConApp_maybe ty of
 983                         Just (tc, ty_args) -> ASSERT( length ty_args == tyConArity tc )
 984                                               isNewTyCon tc
 985                         other              -> False
 986 \end{code}
 987
 988
 989 %************************************************************************
 990 %*                                                                      *
 991 \subsection{Sequencing on types
 992 %*                                                                      *
 993 %************************************************************************
 994
 995 \begin{code}
 996 seqType :: Type -> ()
 997 seqType (TyVarTy tv)      = tv `seq` ()
 998 seqType (AppTy t1 t2)     = seqType t1 `seq` seqType t2
 999 seqType (FunTy t1 t2)     = seqType t1 `seq` seqType t2
1000 seqType (NoteTy note t2)  = seqNote note `seq` seqType t2
1001 seqType (TyConApp tc tys) = tc `seq` seqTypes tys
1002 seqType (ForAllTy tv ty)  = tv `seq` seqType ty
1003
1004 seqTypes :: [Type] -> ()
1005 seqTypes []       = ()
1006 seqTypes (ty:tys) = seqType ty `seq` seqTypes tys
1007
1008 seqNote :: TyNote -> ()
1009 seqNote (SynNote ty)  = seqType ty
1010 seqNote (FTVNote set) = sizeUniqSet set `seq` ()
1011 seqNote (UsgNote usg) = usg `seq` ()
1012 seqNote (IPNote nm)   = nm `seq` ()
1013 \end{code}