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