compiler/types/TyCon.lhs

   1 %
   2 % (c) The University of Glasgow 2006
   3 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   4 %
   5
   6 The @TyCon@ datatype
   7
   8 \begin{code}
   9 module TyCon(
  10         -- * Main TyCon data types
  11         TyCon, FieldLabel,
  12
  13         AlgTyConRhs(..), visibleDataCons,
  14         TyConParent(..), isNoParent,
  15         SynTyConRhs(..),
  16
  17         -- ** Coercion axiom constructors
  18         CoAxiom(..), coAxiomName, coAxiomArity,
  19
  20         -- ** Constructing TyCons
  21         mkAlgTyCon,
  22         mkClassTyCon,
  23         mkFunTyCon,
  24         mkPrimTyCon,
  25         mkKindTyCon,
  26         mkLiftedPrimTyCon,
  27         mkTupleTyCon,
  28         mkSynTyCon,
  29         mkSuperKindTyCon,
  30         mkForeignTyCon,
  31         mkAnyTyCon,
  32
  33         -- ** Predicates on TyCons
  34         isAlgTyCon,
  35         isClassTyCon, isFamInstTyCon,
  36         isFunTyCon,
  37         isPrimTyCon,
  38         isTupleTyCon, isUnboxedTupleTyCon, isBoxedTupleTyCon,
  39         isSynTyCon, isClosedSynTyCon,
  40         isSuperKindTyCon, isDecomposableTyCon,
  41         isForeignTyCon, isAnyTyCon, tyConHasKind,
  42
  43         isInjectiveTyCon,
  44         isDataTyCon, isProductTyCon, isEnumerationTyCon,
  45         isNewTyCon, isAbstractTyCon,
  46         isFamilyTyCon, isSynFamilyTyCon, isDataFamilyTyCon,
  47         isUnLiftedTyCon,
  48         isGadtSyntaxTyCon,
  49         isTyConAssoc,
  50         isRecursiveTyCon,
  51         isHiBootTyCon,
  52         isImplicitTyCon, tyConHasGenerics,
  53
  54         -- ** Extracting information out of TyCons
  55         tyConName,
  56         tyConKind,
  57         tyConUnique,
  58         tyConTyVars,
  59         tyConDataCons, tyConDataCons_maybe, tyConSingleDataCon_maybe,
  60         tyConFamilySize,
  61         tyConStupidTheta,
  62         tyConArity,
  63         tyConParent,
  64         tyConClass_maybe,
  65         tyConFamInst_maybe, tyConFamilyCoercion_maybe,tyConFamInstSig_maybe,
  66         synTyConDefn, synTyConRhs, synTyConType,
  67         tyConExtName,           -- External name for foreign types
  68         algTyConRhs,
  69         newTyConRhs, newTyConEtadRhs, unwrapNewTyCon_maybe,
  70         tupleTyConBoxity,
  71
  72         -- ** Manipulating TyCons
  73         tcExpandTyCon_maybe, coreExpandTyCon_maybe,
  74         makeTyConAbstract,
  75         newTyConCo, newTyConCo_maybe,
  76
  77         -- * Primitive representations of Types
  78         PrimRep(..),
  79         tyConPrimRep,
  80         primRepSizeW
  81 ) where
  82
  83 #include "HsVersions.h"
  84
  85 import {-# SOURCE #-} TypeRep ( Kind, Type, PredType )
  86 import {-# SOURCE #-} DataCon ( DataCon, isVanillaDataCon )
  87
  88 import Var
  89 import Class
  90 import BasicTypes
  91 import Name
  92 import PrelNames
  93 import Maybes
  94 import Outputable
  95 import FastString
  96 import Constants
  97 import Util
  98 import qualified Data.Data as Data
  99 \end{code}
 100
 101 -----------------------------------------------
 102         Notes about type families
 103 -----------------------------------------------
 104
 105 Note [Type synonym families]
 106 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 107 * Type synonym families, also known as "type functions", map directly
 108   onto the type functions in FC:
 109
 110         type family F a :: *
 111         type instance F Int = Bool
 112         ..etc...
 113
 114 * Reply "yes" to isSynFamilyTyCon, and isFamilyTyCon
 115
 116 * From the user's point of view (F Int) and Bool are simply
 117   equivalent types.
 118
 119 * A Haskell 98 type synonym is a degenerate form of a type synonym
 120   family.
 121
 122 * Type functions can't appear in the LHS of a type function:
 123         type instance F (F Int) = ...   -- BAD!
 124
 125 * Translation of type family decl:
 126         type family F a :: *
 127   translates to
 128     a SynTyCon 'F', whose SynTyConRhs is SynFamilyTyCon
 129
 130 * Translation of type instance decl:
 131         type instance F [a] = Maybe a
 132   translates to a "representation TyCon", 'R:FList', where
 133      R:FList is a SynTyCon, whose
 134        SynTyConRhs is (SynonymTyCon (Maybe a))
 135        TyConParent is (FamInstTyCon F [a] co)
 136          where co :: F [a] ~ R:FList a
 137
 138   It's very much as if the user had written
 139        type instance F [a] = R:FList a
 140        type R:FList a = Maybe a
 141   Indeed, in GHC's internal representation, the RHS of every
 142   'type instance' is simply an application of the representation
 143   TyCon to the quantified varaibles.
 144
 145   The intermediate representation TyCon is a bit gratuitous, but
 146   it means that:
 147
 148         each 'type instance' decls is in 1-1 correspondance
 149         with its representation TyCon
 150
 151   So the result of typechecking a 'type instance' decl is just a
 152   TyCon.  In turn this means that type and data families can be
 153   treated uniformly.
 154
 155 * Translation of type family decl:
 156         type family F a :: *
 157   translates to
 158     a SynTyCon 'F', whose SynTyConRhs is SynFamilyTyCon
 159
 160 * Translation of type instance decl:
 161         type instance F [a] = Maybe a
 162   translates to
 163     A SynTyCon 'R:FList a', whose
 164        SynTyConRhs is (SynonymTyCon (Maybe a))
 165        TyConParent is (FamInstTyCon F [a] co)
 166          where co :: F [a] ~ R:FList a
 167     Notice that we introduce a gratuitous vanilla type synonym
 168        type R:FList a = Maybe a
 169     solely so that type and data families can be treated more
 170     uniformly, via a single FamInstTyCon descriptor
 171
 172 * In the future we might want to support
 173     * closed type families (esp when we have proper kinds)
 174     * injective type families (allow decomposition)
 175   but we don't at the moment [2010]
 176
 177 Note [Data type families]
 178 ~~~~~~~~~~~~~~~~~~~~~~~~~
 179 See also Note [Wrappers for data instance tycons] in MkId.lhs
 180
 181 * Data type families are declared thus
 182         data family T a :: *
 183         data instance T Int = T1 | T2 Bool
 184
 185   Here T is the "family TyCon".
 186
 187 * Reply "yes" to isDataFamilyTyCon, and isFamilyTyCon
 188
 189 * Reply "yes" to isDataFamilyTyCon, and isFamilyTyCon
 190
 191 * The user does not see any "equivalent types" as he did with type
 192   synonym families.  He just sees constructors with types
 193         T1 :: T Int
 194         T2 :: Bool -> T Int
 195
 196 * Here's the FC version of the above declarations:
 197
 198         data T a
 199         data R:TInt = T1 | T2 Bool
 200         axiom ax_ti : T Int ~ R:TInt
 201
 202   The R:TInt is the "representation TyCons".
 203   It has an AlgTyConParent of
 204         FamInstTyCon T [Int] ax_ti
 205
 206 * The data contructor T2 has a wrapper (which is what the
 207   source-level "T2" invokes):
 208
 209         $WT2 :: Bool -> T Int
 210         $WT2 b = T2 b `cast` sym ax_ti
 211
 212 * A data instance can declare a fully-fledged GADT:
 213
 214         data instance T (a,b) where
 215           X1 :: T (Int,Bool)
 216           X2 :: a -> b -> T (a,b)
 217
 218   Here's the FC version of the above declaration:
 219
 220         data R:TPair a where
 221           X1 :: R:TPair Int Bool
 222           X2 :: a -> b -> R:TPair a b
 223         axiom ax_pr :: T (a,b) ~ R:TPair a b
 224
 225         $WX1 :: forall a b. a -> b -> T (a,b)
 226         $WX1 a b (x::a) (y::b) = X2 a b x y `cast` sym (ax_pr a b)
 227
 228   The R:TPair are the "representation TyCons".
 229   We have a bit of work to do, to unpick the result types of the
 230   data instance declaration for T (a,b), to get the result type in the
 231   representation; e.g.  T (a,b) --> R:TPair a b
 232
 233   The representation TyCon R:TList, has an AlgTyConParent of
 234
 235         FamInstTyCon T [(a,b)] ax_pr
 236
 237 * Notice that T is NOT translated to a FC type function; it just
 238   becomes a "data type" with no constructors, which can be coerced inot
 239   into R:TInt, R:TPair by the axioms.  These axioms
 240   axioms come into play when (and *only* when) you
 241         - use a data constructor
 242         - do pattern matching
 243   Rather like newtype, in fact
 244
 245   As a result
 246
 247   - T behaves just like a data type so far as decomposition is concerned
 248
 249   - (T Int) is not implicitly converted to R:TInt during type inference.
 250     Indeed the latter type is unknown to the programmer.
 251
 252   - There *is* an instance for (T Int) in the type-family instance
 253     environment, but it is only used for overlap checking
 254
 255   - It's fine to have T in the LHS of a type function:
 256     type instance F (T a) = [a]
 257
 258   It was this last point that confused me!  The big thing is that you
 259   should not think of a data family T as a *type function* at all, not
 260   even an injective one!  We can't allow even injective type functions
 261   on the LHS of a type function:
 262         type family injective G a :: *
 263         type instance F (G Int) = Bool
 264   is no good, even if G is injective, because consider
 265         type instance G Int = Bool
 266         type instance F Bool = Char
 267
 268   So a data type family is not an injective type function. It's just a
 269   data type with some axioms that connect it to other data types.
 270
 271 %************************************************************************
 272 %*                                                                      *
 273 \subsection{The data type}
 274 %*                                                                      *
 275 %************************************************************************
 276
 277 \begin{code}
 278 -- | TyCons represent type constructors. Type constructors are introduced by things such as:
 279 --
 280 -- 1) Data declarations: @data Foo = ...@ creates the @Foo@ type constructor of kind @*@
 281 --
 282 -- 2) Type synonyms: @type Foo = ...@ creates the @Foo@ type constructor
 283 --
 284 -- 3) Newtypes: @newtype Foo a = MkFoo ...@ creates the @Foo@ type constructor of kind @* -> *@
 285 --
 286 -- 4) Class declarations: @class Foo where@ creates the @Foo@ type constructor of kind @*@
 287 --
 288 -- This data type also encodes a number of primitive, built in type constructors such as those
 289 -- for function and tuple types.
 290 data TyCon
 291   = -- | The function type constructor, @(->)@
 292     FunTyCon {
 293         tyConUnique :: Unique,
 294         tyConName   :: Name,
 295         tc_kind   :: Kind,
 296         tyConArity  :: Arity
 297     }
 298
 299   -- | Algebraic type constructors, which are defined to be those
 300   -- arising @data@ type and @newtype@ declarations.  All these
 301   -- constructors are lifted and boxed. See 'AlgTyConRhs' for more
 302   -- information.
 303   | AlgTyCon {
 304         tyConUnique :: Unique,
 305         tyConName   :: Name,
 306         tc_kind   :: Kind,
 307         tyConArity  :: Arity,
 308
 309         tyConTyVars :: [TyVar],   -- ^ The type variables used in the type constructor.
 310                                   -- Invariant: length tyvars = arity
 311                                   -- Precisely, this list scopes over:
 312                                   --
 313                                   -- 1. The 'algTcStupidTheta'
 314                                   -- 2. The cached types in 'algTyConRhs.NewTyCon'
 315                                   -- 3. The family instance types if present
 316                                   --
 317                                   -- Note that it does /not/ scope over the data constructors.
 318
 319         algTcGadtSyntax  :: Bool,       -- ^ Was the data type declared with GADT syntax?
 320                                         -- If so, that doesn't mean it's a true GADT;
 321                                         -- only that the "where" form was used.
 322                                         -- This field is used only to guide pretty-printing
 323
 324         algTcStupidTheta :: [PredType], -- ^ The \"stupid theta\" for the data type
 325                                         -- (always empty for GADTs).
 326                                         -- A \"stupid theta\" is the context to the left
 327                                         -- of an algebraic type declaration,
 328                                         -- e.g. @Eq a@ in the declaration
 329                                         --    @data Eq a => T a ...@.
 330
 331         algTcRhs :: AlgTyConRhs,  -- ^ Contains information about the
 332                                   -- data constructors of the algebraic type
 333
 334         algTcRec :: RecFlag,      -- ^ Tells us whether the data type is part
 335                                   -- of a mutually-recursive group or not
 336
 337         hasGenerics :: Bool,      -- ^ Whether generic (in the -XGenerics sense)
 338                                   -- to\/from functions are available in the exports
 339                                   -- of the data type's source module.
 340
 341         algTcParent :: TyConParent      -- ^ Gives the class or family declaration 'TyCon'
 342                                         -- for derived 'TyCon's representing class
 343                                         -- or family instances, respectively.
 344                                         -- See also 'synTcParent'
 345     }
 346
 347   -- | Represents the infinite family of tuple type constructors,
 348   --   @()@, @(a,b)@, @(# a, b #)@ etc.
 349   | TupleTyCon {
 350         tyConUnique :: Unique,
 351         tyConName   :: Name,
 352         tc_kind   :: Kind,
 353         tyConArity  :: Arity,
 354         tyConBoxed  :: Boxity,
 355         tyConTyVars :: [TyVar],
 356         dataCon     :: DataCon, -- ^ Corresponding tuple data constructor
 357         hasGenerics :: Bool
 358     }
 359
 360   -- | Represents type synonyms
 361   | SynTyCon {
 362         tyConUnique  :: Unique,
 363         tyConName    :: Name,
 364         tc_kind    :: Kind,
 365         tyConArity   :: Arity,
 366
 367         tyConTyVars  :: [TyVar],        -- Bound tyvars
 368
 369         synTcRhs     :: SynTyConRhs,    -- ^ Contains information about the
 370                                         -- expansion of the synonym
 371
 372         synTcParent  :: TyConParent     -- ^ Gives the family declaration 'TyCon'
 373                                         -- of 'TyCon's representing family instances
 374
 375     }
 376
 377   -- | Primitive types; cannot be defined in Haskell. This includes
 378   -- the usual suspects (such as @Int#@) as well as foreign-imported
 379   -- types and kinds
 380   | PrimTyCon {
 381         tyConUnique   :: Unique,
 382         tyConName     :: Name,
 383         tc_kind       :: Kind,
 384         tyConArity    :: Arity,         -- SLPJ Oct06: I'm not sure what the significance
 385                                         --             of the arity of a primtycon is!
 386
 387         primTyConRep  :: PrimRep,       -- ^ Many primitive tycons are unboxed, but some are
 388                                         --   boxed (represented by pointers). This 'PrimRep'
 389                                         --   holds that information.
 390                                         -- Only relevant if tc_kind = *
 391
 392         isUnLifted   :: Bool,           -- ^ Most primitive tycons are unlifted
 393                                         --   (may not contain bottom)
 394                                         --   but foreign-imported ones may be lifted
 395
 396         tyConExtName :: Maybe FastString   -- ^ @Just e@ for foreign-imported types,
 397                                            --   holds the name of the imported thing
 398     }
 399
 400   -- | Any types.  Like tuples, this is a potentially-infinite family of TyCons
 401   --   one for each distinct Kind. They have no values at all.
 402   --   Because there are infinitely many of them (like tuples) they are
 403   --   defined in GHC.Prim and have names like "Any(*->*)".
 404   --   Their Unique is derived from the OccName.
 405   -- See Note [Any types] in TysPrim
 406   | AnyTyCon {
 407         tyConUnique  :: Unique,
 408         tyConName    :: Name,
 409         tc_kind      :: Kind    -- Never = *; that is done via PrimTyCon
 410                                 -- See Note [Any types] in TysPrim
 411     }
 412
 413   -- | Super-kinds. These are "kinds-of-kinds" and are never seen in
 414   -- Haskell source programs.  There are only two super-kinds: TY (aka
 415   -- "box"), which is the super-kind of kinds that construct types
 416   -- eventually, and CO (aka "diamond"), which is the super-kind of
 417   -- kinds that just represent coercions.
 418   --
 419   -- Super-kinds have no kind themselves, and have arity zero
 420   | SuperKindTyCon {
 421         tyConUnique :: Unique,
 422         tyConName   :: Name
 423     }
 424
 425 -- | Names of the fields in an algebraic record type
 426 type FieldLabel = Name
 427
 428 -- | Represents right-hand-sides of 'TyCon's for algebraic types
 429 data AlgTyConRhs
 430
 431     -- | Says that we know nothing about this data type, except that
 432     -- it's represented by a pointer.  Used when we export a data type
 433     -- abstractly into an .hi file.
 434   = AbstractTyCon
 435
 436     -- | Represents an open type family without a fixed right hand
 437     -- side.  Additional instances can appear at any time.
 438     --
 439     -- These are introduced by either a top level declaration:
 440     --
 441     -- > data T a :: *
 442     --
 443     -- Or an associated data type declaration, within a class declaration:
 444     --
 445     -- > class C a b where
 446     -- >   data T b :: *
 447   | DataFamilyTyCon
 448
 449     -- | Information about those 'TyCon's derived from a @data@
 450     -- declaration. This includes data types with no constructors at
 451     -- all.
 452   | DataTyCon {
 453         data_cons :: [DataCon],
 454                           -- ^ The data type constructors; can be empty if the user
 455                           --   declares the type to have no constructors
 456                           --
 457                           -- INVARIANT: Kept in order of increasing 'DataCon' tag
 458                           --      (see the tag assignment in DataCon.mkDataCon)
 459
 460         is_enum :: Bool   -- ^ Cached value: is this an enumeration type?
 461                           --   See Note [Enumeration types]
 462     }
 463
 464   -- | Information about those 'TyCon's derived from a @newtype@ declaration
 465   | NewTyCon {
 466         data_con :: DataCon,    -- ^ The unique constructor for the @newtype@.
 467                                 --   It has no existentials
 468
 469         nt_rhs :: Type,         -- ^ Cached value: the argument type of the constructor,
 470                                 -- which is just the representation type of the 'TyCon'
 471                                 -- (remember that @newtype@s do not exist at runtime
 472                                 -- so need a different representation type).
 473                                 --
 474                                 -- The free 'TyVar's of this type are the 'tyConTyVars'
 475                                 -- from the corresponding 'TyCon'
 476
 477         nt_etad_rhs :: ([TyVar], Type),
 478                         -- ^ Same as the 'nt_rhs', but this time eta-reduced.
 479                         -- Hence the list of 'TyVar's in this field may be
 480                         -- shorter than the declared arity of the 'TyCon'.
 481
 482                         -- See Note [Newtype eta]
 483         nt_co :: CoAxiom     -- The axiom coercion that creates the @newtype@ from
 484                              -- the representation 'Type'.
 485
 486                              -- See Note [Newtype coercions]
 487                              -- Invariant: arity = #tvs in nt_etad_rhs;
 488                              -- See Note [Newtype eta]
 489                              -- Watch out!  If any newtypes become transparent
 490                              -- again check Trac #1072.
 491     }
 492
 493 -- | Extract those 'DataCon's that we are able to learn about.  Note
 494 -- that visibility in this sense does not correspond to visibility in
 495 -- the context of any particular user program!
 496 visibleDataCons :: AlgTyConRhs -> [DataCon]
 497 visibleDataCons AbstractTyCon                 = []
 498 visibleDataCons DataFamilyTyCon {}                    = []
 499 visibleDataCons (DataTyCon{ data_cons = cs }) = cs
 500 visibleDataCons (NewTyCon{ data_con = c })    = [c]
 501
 502 -- ^ Both type classes as well as family instances imply implicit
 503 -- type constructors.  These implicit type constructors refer to their parent
 504 -- structure (ie, the class or family from which they derive) using a type of
 505 -- the following form.  We use 'TyConParent' for both algebraic and synonym
 506 -- types, but the variant 'ClassTyCon' will only be used by algebraic 'TyCon's.
 507 data TyConParent
 508   = -- | An ordinary type constructor has no parent.
 509     NoParentTyCon
 510
 511   -- | Type constructors representing a class dictionary.
 512   | ClassTyCon
 513         Class           -- INVARIANT: the classTyCon of this Class is the current tycon
 514
 515   -- | An *associated* type of a class.
 516   | AssocFamilyTyCon
 517         Class           -- The class in whose declaration the family is declared
 518                         -- The 'tyConTyVars' of this 'TyCon' may mention some
 519                         -- of the same type variables as the classTyVars of the
 520                         -- parent 'Class'.  E.g.
 521                         --
 522                         -- @
 523                         --    class C a b where
 524                         --      data T c a
 525                         -- @
 526                         --
 527                         -- Here the 'a' is shared with the 'Class', and that is
 528                         -- important. In an instance declaration we expect the
 529                         -- two to be instantiated the same way.  Eg.
 530                         --
 531                         -- @
 532                         --    instanc C [x] (Tree y) where
 533                         --      data T c [x] = T1 x | T2 c
 534                         -- @
 535
 536   -- | Type constructors representing an instance of a type family. Parameters:
 537   --
 538   --  1) The type family in question
 539   --
 540   --  2) Instance types; free variables are the 'tyConTyVars'
 541   --  of the current 'TyCon' (not the family one). INVARIANT:
 542   --  the number of types matches the arity of the family 'TyCon'
 543   --
 544   --  3) A 'CoTyCon' identifying the representation
 545   --  type with the type instance family
 546   | FamInstTyCon          -- See Note [Data type families]
 547                           -- and Note [Type synonym families]
 548         TyCon   -- The family TyCon
 549         [Type]  -- Argument types (mentions the tyConTyVars of this TyCon)
 550         CoAxiom   -- The coercion constructor
 551
 552         -- E.g.  data intance T [a] = ...
 553         -- gives a representation tycon:
 554         --      data R:TList a = ...
 555         --      axiom co a :: T [a] ~ R:TList a
 556         -- with R:TList's algTcParent = FamInstTyCon T [a] co
 557
 558 -- | Checks the invariants of a 'TyConParent' given the appropriate type class name, if any
 559 okParent :: Name -> TyConParent -> Bool
 560 okParent _       NoParentTyCon                    = True
 561 okParent tc_name (AssocFamilyTyCon cls)           = tc_name `elem` map tyConName (classATs cls)
 562 okParent tc_name (ClassTyCon cls)                 = tc_name == tyConName (classTyCon cls)
 563 okParent _       (FamInstTyCon fam_tc tys _co_tc) = tyConArity fam_tc == length tys
 564
 565 isNoParent :: TyConParent -> Bool
 566 isNoParent NoParentTyCon = True
 567 isNoParent _             = False
 568
 569 --------------------
 570
 571 -- | Information pertaining to the expansion of a type synonym (@type@)
 572 data SynTyConRhs
 573   = -- | An ordinary type synonyn.
 574     SynonymTyCon
 575        Type           -- This 'Type' is the rhs, and may mention from 'tyConTyVars'.
 576                       -- It acts as a template for the expansion when the 'TyCon'
 577                       -- is applied to some types.
 578
 579    -- | A type synonym family  e.g. @type family F x y :: * -> *@
 580    | SynFamilyTyCon
 581 \end{code}
 582
 583 Note [Enumeration types]
 584 ~~~~~~~~~~~~~~~~~~~~~~~~
 585 We define datatypes with no constructors to *not* be
 586 enumerations; this fixes trac #2578,  Otherwise we
 587 end up generating an empty table for
 588   <mod>_<type>_closure_tbl
 589 which is used by tagToEnum# to map Int# to constructors
 590 in an enumeration. The empty table apparently upset
 591 the linker.
 592
 593 Moreover, all the data constructor must be enumerations, meaning
 594 they have type  (forall abc. T a b c).  GADTs are not enumerations.
 595 For example consider
 596     data T a where
 597       T1 :: T Int
 598       T2 :: T Bool
 599       T3 :: T a
 600 What would [T1 ..] be?  [T1,T3] :: T Int? Easiest thing is to exclude them.
 601 See Trac #4528.
 602
 603 Note [Newtype coercions]
 604 ~~~~~~~~~~~~~~~~~~~~~~~~
 605 The NewTyCon field nt_co is a a TyCon (a coercion constructor in fact)
 606 which is used for coercing from the representation type of the
 607 newtype, to the newtype itself. For example,
 608
 609    newtype T a = MkT (a -> a)
 610
 611 the NewTyCon for T will contain nt_co = CoT where CoT t : T t ~ t ->
 612 t.  This TyCon is a CoTyCon, so it does not have a kind on its
 613 own; it basically has its own typing rule for the fully-applied
 614 version.  If the newtype T has k type variables then CoT has arity at
 615 most k.  In the case that the right hand side is a type application
 616 ending with the same type variables as the left hand side, we
 617 "eta-contract" the coercion.  So if we had
 618
 619    newtype S a = MkT [a]
 620
 621 then we would generate the arity 0 coercion CoS : S ~ [].  The
 622 primary reason we do this is to make newtype deriving cleaner.
 623
 624 In the paper we'd write
 625         axiom CoT : (forall t. T t) ~ (forall t. [t])
 626 and then when we used CoT at a particular type, s, we'd say
 627         CoT @ s
 628 which encodes as (TyConApp instCoercionTyCon [TyConApp CoT [], s])
 629
 630 But in GHC we instead make CoT into a new piece of type syntax, CoTyCon,
 631 (like instCoercionTyCon, symCoercionTyCon etc), which must always
 632 be saturated, but which encodes as
 633         TyConApp CoT [s]
 634 In the vocabulary of the paper it's as if we had axiom declarations
 635 like
 636         axiom CoT t :  T t ~ [t]
 637
 638 Note [Newtype eta]
 639 ~~~~~~~~~~~~~~~~~~
 640 Consider
 641         newtype Parser m a = MkParser (Foogle m a)
 642 Are these two types equal (to Core)?
 643         Monad (Parser m)
 644         Monad (Foogle m)
 645 Well, yes.  But to see that easily we eta-reduce the RHS type of
 646 Parser, in this case to ([], Froogle), so that even unsaturated applications
 647 of Parser will work right.  This eta reduction is done when the type
 648 constructor is built, and cached in NewTyCon.  The cached field is
 649 only used in coreExpandTyCon_maybe.
 650
 651 Here's an example that I think showed up in practice
 652 Source code:
 653         newtype T a = MkT [a]
 654         newtype Foo m = MkFoo (forall a. m a -> Int)
 655
 656         w1 :: Foo []
 657         w1 = ...
 658
 659         w2 :: Foo T
 660         w2 = MkFoo (\(MkT x) -> case w1 of MkFoo f -> f x)
 661
 662 After desugaring, and discarding the data constructors for the newtypes,
 663 we get:
 664         w2 :: Foo T
 665         w2 = w1
 666 And now Lint complains unless Foo T == Foo [], and that requires T==[]
 667
 668 This point carries over to the newtype coercion, because we need to
 669 say
 670         w2 = w1 `cast` Foo CoT
 671
 672 so the coercion tycon CoT must have
 673         kind:    T ~ []
 674  and    arity:   0
 675
 676
 677 %************************************************************************
 678 %*                                                                      *
 679                     Coercion axioms
 680 %*                                                                      *
 681 %************************************************************************
 682
 683 \begin{code}
 684 -- | A 'CoAxiom' is a \"coercion constructor\", i.e. a named equality axiom.
 685 data CoAxiom
 686   = CoAxiom                   -- type equality axiom.
 687     { co_ax_unique :: Unique   -- unique identifier
 688     , co_ax_name   :: Name     -- name for pretty-printing
 689     , co_ax_tvs    :: [TyVar]  -- bound type variables
 690     , co_ax_lhs    :: Type     -- left-hand side of the equality
 691     , co_ax_rhs    :: Type     -- right-hand side of the equality
 692     }
 693
 694 coAxiomArity :: CoAxiom -> Arity
 695 coAxiomArity ax = length (co_ax_tvs ax)
 696
 697 coAxiomName :: CoAxiom -> Name
 698 coAxiomName = co_ax_name
 699 \end{code}
 700
 701
 702 %************************************************************************
 703 %*                                                                      *
 704 \subsection{PrimRep}
 705 %*                                                                      *
 706 %************************************************************************
 707
 708 A PrimRep is somewhat similar to a CgRep (see codeGen/SMRep) and a
 709 MachRep (see cmm/CmmExpr), although each of these types has a distinct
 710 and clearly defined purpose:
 711
 712   - A PrimRep is a CgRep + information about signedness + information
 713     about primitive pointers (AddrRep).  Signedness and primitive
 714     pointers are required when passing a primitive type to a foreign
 715     function, but aren't needed for call/return conventions of Haskell
 716     functions.
 717
 718   - A MachRep is a basic machine type (non-void, doesn't contain
 719     information on pointerhood or signedness, but contains some
 720     reps that don't have corresponding Haskell types).
 721
 722 \begin{code}
 723 -- | A 'PrimRep' is an abstraction of a type.  It contains information that
 724 -- the code generator needs in order to pass arguments, return results,
 725 -- and store values of this type.
 726 data PrimRep
 727   = VoidRep
 728   | PtrRep
 729   | IntRep              -- ^ Signed, word-sized value
 730   | WordRep             -- ^ Unsigned, word-sized value
 731   | Int64Rep            -- ^ Signed, 64 bit value (with 32-bit words only)
 732   | Word64Rep           -- ^ Unsigned, 64 bit value (with 32-bit words only)
 733   | AddrRep             -- ^ A pointer, but /not/ to a Haskell value (use 'PtrRep')
 734   | FloatRep
 735   | DoubleRep
 736   deriving( Eq, Show )
 737
 738 instance Outputable PrimRep where
 739   ppr r = text (show r)
 740
 741 -- | Find the size of a 'PrimRep', in words
 742 primRepSizeW :: PrimRep -> Int
 743 primRepSizeW IntRep   = 1
 744 primRepSizeW WordRep  = 1
 745 primRepSizeW Int64Rep = wORD64_SIZE `quot` wORD_SIZE
 746 primRepSizeW Word64Rep= wORD64_SIZE `quot` wORD_SIZE
 747 primRepSizeW FloatRep = 1    -- NB. might not take a full word
 748 primRepSizeW DoubleRep= dOUBLE_SIZE `quot` wORD_SIZE
 749 primRepSizeW AddrRep  = 1
 750 primRepSizeW PtrRep   = 1
 751 primRepSizeW VoidRep  = 0
 752 \end{code}
 753
 754 %************************************************************************
 755 %*                                                                      *
 756 \subsection{TyCon Construction}
 757 %*                                                                      *
 758 %************************************************************************
 759
 760 Note: the TyCon constructors all take a Kind as one argument, even though
 761 they could, in principle, work out their Kind from their other arguments.
 762 But to do so they need functions from Types, and that makes a nasty
 763 module mutual-recursion.  And they aren't called from many places.
 764 So we compromise, and move their Kind calculation to the call site.
 765
 766 \begin{code}
 767 -- | Given the name of the function type constructor and it's kind, create the
 768 -- corresponding 'TyCon'. It is reccomended to use 'TypeRep.funTyCon' if you want
 769 -- this functionality
 770 mkFunTyCon :: Name -> Kind -> TyCon
 771 mkFunTyCon name kind
 772   = FunTyCon {
 773         tyConUnique = nameUnique name,
 774         tyConName   = name,
 775         tc_kind   = kind,
 776         tyConArity  = 2
 777     }
 778
 779 -- | This is the making of an algebraic 'TyCon'. Notably, you have to
 780 -- pass in the generic (in the -XGenerics sense) information about the
 781 -- type constructor - you can get hold of it easily (see Generics
 782 -- module)
 783 mkAlgTyCon :: Name
 784            -> Kind              -- ^ Kind of the resulting 'TyCon'
 785            -> [TyVar]           -- ^ 'TyVar's scoped over: see 'tyConTyVars'.
 786                                 --   Arity is inferred from the length of this list
 787            -> [PredType]        -- ^ Stupid theta: see 'algTcStupidTheta'
 788            -> AlgTyConRhs       -- ^ Information about dat aconstructors
 789            -> TyConParent
 790            -> RecFlag           -- ^ Is the 'TyCon' recursive?
 791            -> Bool              -- ^ Does it have generic functions? See 'hasGenerics'
 792            -> Bool              -- ^ Was the 'TyCon' declared with GADT syntax?
 793            -> TyCon
 794 mkAlgTyCon name kind tyvars stupid rhs parent is_rec gen_info gadt_syn
 795   = AlgTyCon {
 796         tyConName        = name,
 797         tyConUnique      = nameUnique name,
 798         tc_kind          = kind,
 799         tyConArity       = length tyvars,
 800         tyConTyVars      = tyvars,
 801         algTcStupidTheta = stupid,
 802         algTcRhs         = rhs,
 803         algTcParent      = ASSERT( okParent name parent ) parent,
 804         algTcRec         = is_rec,
 805         algTcGadtSyntax  = gadt_syn,
 806         hasGenerics      = gen_info
 807     }
 808
 809 -- | Simpler specialization of 'mkAlgTyCon' for classes
 810 mkClassTyCon :: Name -> Kind -> [TyVar] -> AlgTyConRhs -> Class -> RecFlag -> TyCon
 811 mkClassTyCon name kind tyvars rhs clas is_rec =
 812   mkAlgTyCon name kind tyvars [] rhs (ClassTyCon clas) is_rec False False
 813
 814 mkTupleTyCon :: Name
 815              -> Kind    -- ^ Kind of the resulting 'TyCon'
 816              -> Arity   -- ^ Arity of the tuple
 817              -> [TyVar] -- ^ 'TyVar's scoped over: see 'tyConTyVars'
 818              -> DataCon
 819              -> Boxity  -- ^ Whether the tuple is boxed or unboxed
 820              -> Bool    -- ^ Does it have generic functions? See 'hasGenerics'
 821              -> TyCon
 822 mkTupleTyCon name kind arity tyvars con boxed gen_info
 823   = TupleTyCon {
 824         tyConUnique = nameUnique name,
 825         tyConName = name,
 826         tc_kind = kind,
 827         tyConArity = arity,
 828         tyConBoxed = boxed,
 829         tyConTyVars = tyvars,
 830         dataCon = con,
 831         hasGenerics = gen_info
 832     }
 833
 834 -- ^ Foreign-imported (.NET) type constructors are represented
 835 -- as primitive, but /lifted/, 'TyCons' for now. They are lifted
 836 -- because the Haskell type @T@ representing the (foreign) .NET
 837 -- type @T@ is actually implemented (in ILX) as a @thunk<T>@
 838 mkForeignTyCon :: Name
 839                -> Maybe FastString -- ^ Name of the foreign imported thing, maybe
 840                -> Kind
 841                -> Arity
 842                -> TyCon
 843 mkForeignTyCon name ext_name kind arity
 844   = PrimTyCon {
 845         tyConName    = name,
 846         tyConUnique  = nameUnique name,
 847         tc_kind    = kind,
 848         tyConArity   = arity,
 849         primTyConRep = PtrRep, -- they all do
 850         isUnLifted   = False,
 851         tyConExtName = ext_name
 852     }
 853
 854
 855 -- | Create an unlifted primitive 'TyCon', such as @Int#@
 856 mkPrimTyCon :: Name  -> Kind -> Arity -> PrimRep -> TyCon
 857 mkPrimTyCon name kind arity rep
 858   = mkPrimTyCon' name kind arity rep True
 859
 860 -- | Kind constructors
 861 mkKindTyCon :: Name -> Kind -> TyCon
 862 mkKindTyCon name kind
 863   = mkPrimTyCon' name kind 0 VoidRep True
 864
 865 -- | Create a lifted primitive 'TyCon' such as @RealWorld@
 866 mkLiftedPrimTyCon :: Name  -> Kind -> Arity -> PrimRep -> TyCon
 867 mkLiftedPrimTyCon name kind arity rep
 868   = mkPrimTyCon' name kind arity rep False
 869
 870 mkPrimTyCon' :: Name  -> Kind -> Arity -> PrimRep -> Bool -> TyCon
 871 mkPrimTyCon' name kind arity rep is_unlifted
 872   = PrimTyCon {
 873         tyConName    = name,
 874         tyConUnique  = nameUnique name,
 875         tc_kind    = kind,
 876         tyConArity   = arity,
 877         primTyConRep = rep,
 878         isUnLifted   = is_unlifted,
 879         tyConExtName = Nothing
 880     }
 881
 882 -- | Create a type synonym 'TyCon'
 883 mkSynTyCon :: Name -> Kind -> [TyVar] -> SynTyConRhs -> TyConParent -> TyCon
 884 mkSynTyCon name kind tyvars rhs parent
 885   = SynTyCon {
 886         tyConName = name,
 887         tyConUnique = nameUnique name,
 888         tc_kind = kind,
 889         tyConArity = length tyvars,
 890         tyConTyVars = tyvars,
 891         synTcRhs = rhs,
 892         synTcParent = parent
 893     }
 894
 895 mkAnyTyCon :: Name -> Kind -> TyCon
 896 mkAnyTyCon name kind
 897   = AnyTyCon {  tyConName = name,
 898                 tc_kind = kind,
 899                 tyConUnique = nameUnique name }
 900
 901 -- | Create a super-kind 'TyCon'
 902 mkSuperKindTyCon :: Name -> TyCon -- Super kinds always have arity zero
 903 mkSuperKindTyCon name
 904   = SuperKindTyCon {
 905         tyConName = name,
 906         tyConUnique = nameUnique name
 907   }
 908 \end{code}
 909
 910 \begin{code}
 911 isFunTyCon :: TyCon -> Bool
 912 isFunTyCon (FunTyCon {}) = True
 913 isFunTyCon _             = False
 914
 915 -- | Test if the 'TyCon' is algebraic but abstract (invisible data constructors)
 916 isAbstractTyCon :: TyCon -> Bool
 917 isAbstractTyCon (AlgTyCon { algTcRhs = AbstractTyCon }) = True
 918 isAbstractTyCon _ = False
 919
 920 -- | Make an algebraic 'TyCon' abstract. Panics if the supplied 'TyCon' is not algebraic
 921 makeTyConAbstract :: TyCon -> TyCon
 922 makeTyConAbstract tc@(AlgTyCon {}) = tc { algTcRhs = AbstractTyCon }
 923 makeTyConAbstract tc = pprPanic "makeTyConAbstract" (ppr tc)
 924
 925 -- | Does this 'TyCon' represent something that cannot be defined in Haskell?
 926 isPrimTyCon :: TyCon -> Bool
 927 isPrimTyCon (PrimTyCon {}) = True
 928 isPrimTyCon _              = False
 929
 930 -- | Is this 'TyCon' unlifted (i.e. cannot contain bottom)? Note that this can only
 931 -- be true for primitive and unboxed-tuple 'TyCon's
 932 isUnLiftedTyCon :: TyCon -> Bool
 933 isUnLiftedTyCon (PrimTyCon  {isUnLifted = is_unlifted}) = is_unlifted
 934 isUnLiftedTyCon (TupleTyCon {tyConBoxed = boxity})      = not (isBoxed boxity)
 935 isUnLiftedTyCon _                                       = False
 936
 937 -- | Returns @True@ if the supplied 'TyCon' resulted from either a
 938 -- @data@ or @newtype@ declaration
 939 isAlgTyCon :: TyCon -> Bool
 940 isAlgTyCon (AlgTyCon {})   = True
 941 isAlgTyCon (TupleTyCon {}) = True
 942 isAlgTyCon _               = False
 943
 944 isDataTyCon :: TyCon -> Bool
 945 -- ^ Returns @True@ for data types that are /definitely/ represented by
 946 -- heap-allocated constructors.  These are scrutinised by Core-level
 947 -- @case@ expressions, and they get info tables allocated for them.
 948 --
 949 -- Generally, the function will be true for all @data@ types and false
 950 -- for @newtype@s, unboxed tuples and type family 'TyCon's. But it is
 951 -- not guarenteed to return @True@ in all cases that it could.
 952 --
 953 -- NB: for a data type family, only the /instance/ 'TyCon's
 954 --     get an info table.  The family declaration 'TyCon' does not
 955 isDataTyCon (AlgTyCon {algTcRhs = rhs})
 956   = case rhs of
 957         DataFamilyTyCon {}  -> False
 958         DataTyCon {}  -> True
 959         NewTyCon {}   -> False
 960         AbstractTyCon -> False   -- We don't know, so return False
 961 isDataTyCon (TupleTyCon {tyConBoxed = boxity}) = isBoxed boxity
 962 isDataTyCon _ = False
 963
 964 -- | Is this 'TyCon' that for a @newtype@
 965 isNewTyCon :: TyCon -> Bool
 966 isNewTyCon (AlgTyCon {algTcRhs = NewTyCon {}}) = True
 967 isNewTyCon _                                   = False
 968
 969 -- | Take a 'TyCon' apart into the 'TyVar's it scopes over, the 'Type' it expands
 970 -- into, and (possibly) a coercion from the representation type to the @newtype@.
 971 -- Returns @Nothing@ if this is not possible.
 972 unwrapNewTyCon_maybe :: TyCon -> Maybe ([TyVar], Type, CoAxiom)
 973 unwrapNewTyCon_maybe (AlgTyCon { tyConTyVars = tvs,
 974                                  algTcRhs = NewTyCon { nt_co = co,
 975                                                        nt_rhs = rhs }})
 976                            = Just (tvs, rhs, co)
 977 unwrapNewTyCon_maybe _     = Nothing
 978
 979 isProductTyCon :: TyCon -> Bool
 980 -- | A /product/ 'TyCon' must both:
 981 --
 982 -- 1. Have /one/ constructor
 983 --
 984 -- 2. /Not/ be existential
 985 --
 986 -- However other than this there are few restrictions: they may be @data@ or @newtype@
 987 -- 'TyCon's of any boxity and may even be recursive.
 988 isProductTyCon tc@(AlgTyCon {}) = case algTcRhs tc of
 989                                     DataTyCon{ data_cons = [data_con] }
 990                                                 -> isVanillaDataCon data_con
 991                                     NewTyCon {} -> True
 992                                     _           -> False
 993 isProductTyCon (TupleTyCon {})  = True
 994 isProductTyCon _                = False
 995
 996 -- | Is this a 'TyCon' representing a type synonym (@type@)?
 997 isSynTyCon :: TyCon -> Bool
 998 isSynTyCon (SynTyCon {}) = True
 999 isSynTyCon _             = False
1000
1001 -- As for newtypes, it is in some contexts important to distinguish between
1002 -- closed synonyms and synonym families, as synonym families have no unique
1003 -- right hand side to which a synonym family application can expand.
1004 --
1005
1006 isDecomposableTyCon :: TyCon -> Bool
1007 -- True iff we can decompose (T a b c) into ((T a b) c)
1008 -- Specifically NOT true of synonyms (open and otherwise)
1009 isDecomposableTyCon (SynTyCon {}) = False
1010 isDecomposableTyCon _other        = True
1011
1012 -- | Is this an algebraic 'TyCon' declared with the GADT syntax?
1013 isGadtSyntaxTyCon :: TyCon -> Bool
1014 isGadtSyntaxTyCon (AlgTyCon { algTcGadtSyntax = res }) = res
1015 isGadtSyntaxTyCon _                                    = False
1016
1017 -- | Is this an algebraic 'TyCon' which is just an enumeration of values?
1018 isEnumerationTyCon :: TyCon -> Bool
1019 -- See Note [Enumeration types] in TyCon
1020 isEnumerationTyCon (AlgTyCon {algTcRhs = DataTyCon { is_enum = res }}) = res
1021 isEnumerationTyCon (TupleTyCon {tyConArity = arity}) = arity == 0
1022 isEnumerationTyCon _                                                   = False
1023
1024 -- | Is this a 'TyCon', synonym or otherwise, that may have further instances appear?
1025 isFamilyTyCon :: TyCon -> Bool
1026 isFamilyTyCon (SynTyCon {synTcRhs = SynFamilyTyCon {}})  = True
1027 isFamilyTyCon (AlgTyCon {algTcRhs = DataFamilyTyCon {}}) = True
1028 isFamilyTyCon _ = False
1029
1030 -- | Is this a synonym 'TyCon' that can have may have further instances appear?
1031 isSynFamilyTyCon :: TyCon -> Bool
1032 isSynFamilyTyCon (SynTyCon {synTcRhs = SynFamilyTyCon {}}) = True
1033 isSynFamilyTyCon _ = False
1034
1035 -- | Is this a synonym 'TyCon' that can have may have further instances appear?
1036 isDataFamilyTyCon :: TyCon -> Bool
1037 isDataFamilyTyCon (AlgTyCon {algTcRhs = DataFamilyTyCon {}}) = True
1038 isDataFamilyTyCon _ = False
1039
1040 -- | Is this a synonym 'TyCon' that can have no further instances appear?
1041 isClosedSynTyCon :: TyCon -> Bool
1042 isClosedSynTyCon tycon = isSynTyCon tycon && not (isFamilyTyCon tycon)
1043
1044 -- | Injective 'TyCon's can be decomposed, so that
1045 --     T ty1 ~ T ty2  =>  ty1 ~ ty2
1046 isInjectiveTyCon :: TyCon -> Bool
1047 isInjectiveTyCon tc = not (isSynTyCon tc)
1048         -- Ultimately we may have injective associated types
1049         -- in which case this test will become more interesting
1050         --
1051         -- It'd be unusual to call isInjectiveTyCon on a regular H98
1052         -- type synonym, because you should probably have expanded it first
1053         -- But regardless, it's not injective!
1054
1055 -- | Are we able to extract informationa 'TyVar' to class argument list
1056 -- mappping from a given 'TyCon'?
1057 isTyConAssoc :: TyCon -> Bool
1058 isTyConAssoc tc = case tyConParent tc of
1059                      AssocFamilyTyCon {} -> True
1060                      _                   -> False
1061
1062 -- The unit tycon didn't used to be classed as a tuple tycon
1063 -- but I thought that was silly so I've undone it
1064 -- If it can't be for some reason, it should be a AlgTyCon
1065 isTupleTyCon :: TyCon -> Bool
1066 -- ^ Does this 'TyCon' represent a tuple?
1067 --
1068 -- NB: when compiling @Data.Tuple@, the tycons won't reply @True@ to
1069 -- 'isTupleTyCon', becuase they are built as 'AlgTyCons'.  However they
1070 -- get spat into the interface file as tuple tycons, so I don't think
1071 -- it matters.
1072 isTupleTyCon (TupleTyCon {}) = True
1073 isTupleTyCon _               = False
1074
1075 -- | Is this the 'TyCon' for an unboxed tuple?
1076 isUnboxedTupleTyCon :: TyCon -> Bool
1077 isUnboxedTupleTyCon (TupleTyCon {tyConBoxed = boxity}) = not (isBoxed boxity)
1078 isUnboxedTupleTyCon _                                  = False
1079
1080 -- | Is this the 'TyCon' for a boxed tuple?
1081 isBoxedTupleTyCon :: TyCon -> Bool
1082 isBoxedTupleTyCon (TupleTyCon {tyConBoxed = boxity}) = isBoxed boxity
1083 isBoxedTupleTyCon _                                  = False
1084
1085 -- | Extract the boxity of the given 'TyCon', if it is a 'TupleTyCon'.
1086 -- Panics otherwise
1087 tupleTyConBoxity :: TyCon -> Boxity
1088 tupleTyConBoxity tc = tyConBoxed tc
1089
1090 -- | Is this a recursive 'TyCon'?
1091 isRecursiveTyCon :: TyCon -> Bool
1092 isRecursiveTyCon (AlgTyCon {algTcRec = Recursive}) = True
1093 isRecursiveTyCon _                                 = False
1094
1095 -- | Did this 'TyCon' originate from type-checking a .h*-boot file?
1096 isHiBootTyCon :: TyCon -> Bool
1097 -- Used for knot-tying in hi-boot files
1098 isHiBootTyCon (AlgTyCon {algTcRhs = AbstractTyCon}) = True
1099 isHiBootTyCon _                                     = False
1100
1101 -- | Is this the 'TyCon' of a foreign-imported type constructor?
1102 isForeignTyCon :: TyCon -> Bool
1103 isForeignTyCon (PrimTyCon {tyConExtName = Just _}) = True
1104 isForeignTyCon _                                   = False
1105
1106 -- | Is this a super-kind 'TyCon'?
1107 isSuperKindTyCon :: TyCon -> Bool
1108 isSuperKindTyCon (SuperKindTyCon {}) = True
1109 isSuperKindTyCon _                   = False
1110
1111 -- | Is this an AnyTyCon?
1112 isAnyTyCon :: TyCon -> Bool
1113 isAnyTyCon (AnyTyCon {}) = True
1114 isAnyTyCon _              = False
1115
1116 -- | Identifies implicit tycons that, in particular, do not go into interface
1117 -- files (because they are implicitly reconstructed when the interface is
1118 -- read).
1119 --
1120 -- Note that:
1121 --
1122 -- * Associated families are implicit, as they are re-constructed from
1123 --   the class declaration in which they reside, and
1124 --
1125 -- * Family instances are /not/ implicit as they represent the instance body
1126 --   (similar to a @dfun@ does that for a class instance).
1127 isImplicitTyCon :: TyCon -> Bool
1128 isImplicitTyCon tycon | isTyConAssoc tycon           = True
1129                       | isSynTyCon tycon             = False
1130                       | isAlgTyCon tycon             = isClassTyCon tycon ||
1131                                                        isTupleTyCon tycon
1132 isImplicitTyCon _other                               = True
1133         -- catches: FunTyCon, PrimTyCon,
1134         -- CoTyCon, SuperKindTyCon
1135 \end{code}
1136
1137
1138 -----------------------------------------------
1139 --      Expand type-constructor applications
1140 -----------------------------------------------
1141
1142 \begin{code}
1143 tcExpandTyCon_maybe, coreExpandTyCon_maybe
1144         :: TyCon
1145         -> [tyco]                 -- ^ Arguments to 'TyCon'
1146         -> Maybe ([(TyVar,tyco)],
1147                   Type,
1148                   [tyco])         -- ^ Returns a 'TyVar' substitution, the body type
1149                                   -- of the synonym (not yet substituted) and any arguments
1150                                   -- remaining from the application
1151
1152 -- ^ Used to create the view the /typechecker/ has on 'TyCon's.
1153 -- We expand (closed) synonyms only, cf. 'coreExpandTyCon_maybe'
1154 tcExpandTyCon_maybe (SynTyCon {tyConTyVars = tvs,
1155                                synTcRhs = SynonymTyCon rhs }) tys
1156    = expand tvs rhs tys
1157 tcExpandTyCon_maybe _ _ = Nothing
1158
1159 ---------------
1160
1161 -- ^ Used to create the view /Core/ has on 'TyCon's. We expand
1162 -- not only closed synonyms like 'tcExpandTyCon_maybe',
1163 -- but also non-recursive @newtype@s
1164 coreExpandTyCon_maybe tycon tys = tcExpandTyCon_maybe tycon tys
1165
1166
1167 ----------------
1168 expand  :: [TyVar] -> Type                 -- Template
1169         -> [a]                             -- Args
1170         -> Maybe ([(TyVar,a)], Type, [a])  -- Expansion
1171 expand tvs rhs tys
1172   = case n_tvs `compare` length tys of
1173         LT -> Just (tvs `zip` tys, rhs, drop n_tvs tys)
1174         EQ -> Just (tvs `zip` tys, rhs, [])
1175         GT -> Nothing
1176    where
1177      n_tvs = length tvs
1178 \end{code}
1179
1180 \begin{code}
1181 -- | Does this 'TyCon' have any generic to\/from functions available? See also 'hasGenerics'
1182 tyConHasGenerics :: TyCon -> Bool
1183 tyConHasGenerics (AlgTyCon {hasGenerics = hg})   = hg
1184 tyConHasGenerics (TupleTyCon {hasGenerics = hg}) = hg
1185 tyConHasGenerics _                               = False        -- Synonyms
1186
1187 tyConKind :: TyCon -> Kind
1188 tyConKind (FunTyCon   { tc_kind = k }) = k
1189 tyConKind (AlgTyCon   { tc_kind = k }) = k
1190 tyConKind (TupleTyCon { tc_kind = k }) = k
1191 tyConKind (SynTyCon   { tc_kind = k }) = k
1192 tyConKind (PrimTyCon  { tc_kind = k }) = k
1193 tyConKind (AnyTyCon   { tc_kind = k }) = k
1194 tyConKind tc = pprPanic "tyConKind" (ppr tc)    -- SuperKindTyCon and CoTyCon
1195
1196 tyConHasKind :: TyCon -> Bool
1197 tyConHasKind (SuperKindTyCon {}) = False
1198 tyConHasKind _                   = True
1199
1200 -- | As 'tyConDataCons_maybe', but returns the empty list of constructors if no constructors
1201 -- could be found
1202 tyConDataCons :: TyCon -> [DataCon]
1203 -- It's convenient for tyConDataCons to return the
1204 -- empty list for type synonyms etc
1205 tyConDataCons tycon = tyConDataCons_maybe tycon `orElse` []
1206
1207 -- | Determine the 'DataCon's originating from the given 'TyCon', if the 'TyCon' is the
1208 -- sort that can have any constructors (note: this does not include abstract algebraic types)
1209 tyConDataCons_maybe :: TyCon -> Maybe [DataCon]
1210 tyConDataCons_maybe (AlgTyCon {algTcRhs = DataTyCon { data_cons = cons }}) = Just cons
1211 tyConDataCons_maybe (AlgTyCon {algTcRhs = NewTyCon { data_con = con }})    = Just [con]
1212 tyConDataCons_maybe (TupleTyCon {dataCon = con})                           = Just [con]
1213 tyConDataCons_maybe _                                                      = Nothing
1214
1215 -- | Determine the number of value constructors a 'TyCon' has. Panics if the 'TyCon'
1216 -- is not algebraic or a tuple
1217 tyConFamilySize  :: TyCon -> Int
1218 tyConFamilySize (AlgTyCon   {algTcRhs = DataTyCon {data_cons = cons}}) =
1219   length cons
1220 tyConFamilySize (AlgTyCon   {algTcRhs = NewTyCon {}})        = 1
1221 tyConFamilySize (AlgTyCon   {algTcRhs = DataFamilyTyCon {}}) = 0
1222 tyConFamilySize (TupleTyCon {})                              = 1
1223 tyConFamilySize other = pprPanic "tyConFamilySize:" (ppr other)
1224
1225 -- | Extract an 'AlgTyConRhs' with information about data constructors from an algebraic or tuple
1226 -- 'TyCon'. Panics for any other sort of 'TyCon'
1227 algTyConRhs :: TyCon -> AlgTyConRhs
1228 algTyConRhs (AlgTyCon {algTcRhs = rhs}) = rhs
1229 algTyConRhs (TupleTyCon {dataCon = con, tyConArity = arity})
1230     = DataTyCon { data_cons = [con], is_enum = arity == 0 }
1231 algTyConRhs other = pprPanic "algTyConRhs" (ppr other)
1232 \end{code}
1233
1234 \begin{code}
1235 -- | Extract the bound type variables and type expansion of a type synonym 'TyCon'. Panics if the
1236 -- 'TyCon' is not a synonym
1237 newTyConRhs :: TyCon -> ([TyVar], Type)
1238 newTyConRhs (AlgTyCon {tyConTyVars = tvs, algTcRhs = NewTyCon { nt_rhs = rhs }}) = (tvs, rhs)
1239 newTyConRhs tycon = pprPanic "newTyConRhs" (ppr tycon)
1240
1241 -- | Extract the bound type variables and type expansion of an eta-contracted type synonym 'TyCon'.
1242 -- Panics if the 'TyCon' is not a synonym
1243 newTyConEtadRhs :: TyCon -> ([TyVar], Type)
1244 newTyConEtadRhs (AlgTyCon {algTcRhs = NewTyCon { nt_etad_rhs = tvs_rhs }}) = tvs_rhs
1245 newTyConEtadRhs tycon = pprPanic "newTyConEtadRhs" (ppr tycon)
1246
1247 -- | Extracts the @newtype@ coercion from such a 'TyCon', which can be used to construct something
1248 -- with the @newtype@s type from its representation type (right hand side). If the supplied 'TyCon'
1249 -- is not a @newtype@, returns @Nothing@
1250 newTyConCo_maybe :: TyCon -> Maybe CoAxiom
1251 newTyConCo_maybe (AlgTyCon {algTcRhs = NewTyCon { nt_co = co }}) = Just co
1252 newTyConCo_maybe _                                               = Nothing
1253
1254 newTyConCo :: TyCon -> CoAxiom
1255 newTyConCo tc = case newTyConCo_maybe tc of
1256                  Just co -> co
1257                  Nothing -> pprPanic "newTyConCo" (ppr tc)
1258
1259 -- | Find the primitive representation of a 'TyCon'
1260 tyConPrimRep :: TyCon -> PrimRep
1261 tyConPrimRep (PrimTyCon {primTyConRep = rep}) = rep
1262 tyConPrimRep tc = ASSERT(not (isUnboxedTupleTyCon tc)) PtrRep
1263 \end{code}
1264
1265 \begin{code}
1266 -- | Find the \"stupid theta\" of the 'TyCon'. A \"stupid theta\" is the context to the left of
1267 -- an algebraic type declaration, e.g. @Eq a@ in the declaration @data Eq a => T a ...@
1268 tyConStupidTheta :: TyCon -> [PredType]
1269 tyConStupidTheta (AlgTyCon {algTcStupidTheta = stupid}) = stupid
1270 tyConStupidTheta (TupleTyCon {})                        = []
1271 tyConStupidTheta tycon = pprPanic "tyConStupidTheta" (ppr tycon)
1272 \end{code}
1273
1274 \begin{code}
1275 -- | Extract the 'TyVar's bound by a type synonym and the corresponding (unsubstituted) right hand side.
1276 -- If the given 'TyCon' is not a type synonym, panics
1277 synTyConDefn :: TyCon -> ([TyVar], Type)
1278 synTyConDefn (SynTyCon {tyConTyVars = tyvars, synTcRhs = SynonymTyCon ty})
1279   = (tyvars, ty)
1280 synTyConDefn tycon = pprPanic "getSynTyConDefn" (ppr tycon)
1281
1282 -- | Extract the information pertaining to the right hand side of a type synonym (@type@) declaration. Panics
1283 -- if the given 'TyCon' is not a type synonym
1284 synTyConRhs :: TyCon -> SynTyConRhs
1285 synTyConRhs (SynTyCon {synTcRhs = rhs}) = rhs
1286 synTyConRhs tc                          = pprPanic "synTyConRhs" (ppr tc)
1287
1288 -- | Find the expansion of the type synonym represented by the given 'TyCon'. The free variables of this
1289 -- type will typically include those 'TyVar's bound by the 'TyCon'. Panics if the 'TyCon' is not that of
1290 -- a type synonym
1291 synTyConType :: TyCon -> Type
1292 synTyConType tc = case synTcRhs tc of
1293                     SynonymTyCon t -> t
1294                     _              -> pprPanic "synTyConType" (ppr tc)
1295 \end{code}
1296
1297 \begin{code}
1298 -- | If the given 'TyCon' has a /single/ data constructor, i.e. it is a @data@ type with one
1299 -- alternative, a tuple type or a @newtype@ then that constructor is returned. If the 'TyCon'
1300 -- has more than one constructor, or represents a primitive or function type constructor then
1301 -- @Nothing@ is returned. In any other case, the function panics
1302 tyConSingleDataCon_maybe :: TyCon -> Maybe DataCon
1303 tyConSingleDataCon_maybe (TupleTyCon {dataCon = c})                            = Just c
1304 tyConSingleDataCon_maybe (AlgTyCon {algTcRhs = DataTyCon { data_cons = [c] }}) = Just c
1305 tyConSingleDataCon_maybe (AlgTyCon {algTcRhs = NewTyCon { data_con = c }})     = Just c
1306 tyConSingleDataCon_maybe _                                                     = Nothing
1307 \end{code}
1308
1309 \begin{code}
1310 -- | Is this 'TyCon' that for a class instance?
1311 isClassTyCon :: TyCon -> Bool
1312 isClassTyCon (AlgTyCon {algTcParent = ClassTyCon _}) = True
1313 isClassTyCon _                                       = False
1314
1315 -- | If this 'TyCon' is that for a class instance, return the class it is for.
1316 -- Otherwise returns @Nothing@
1317 tyConClass_maybe :: TyCon -> Maybe Class
1318 tyConClass_maybe (AlgTyCon {algTcParent = ClassTyCon clas}) = Just clas
1319 tyConClass_maybe _                                          = Nothing
1320
1321 ----------------------------------------------------------------------------
1322 tyConParent :: TyCon -> TyConParent
1323 tyConParent (AlgTyCon {algTcParent = parent}) = parent
1324 tyConParent (SynTyCon {synTcParent = parent}) = parent
1325 tyConParent _                                 = NoParentTyCon
1326
1327 ----------------------------------------------------------------------------
1328 -- | Is this 'TyCon' that for a family instance, be that for a synonym or an
1329 -- algebraic family instance?
1330 isFamInstTyCon :: TyCon -> Bool
1331 isFamInstTyCon tc = case tyConParent tc of
1332                       FamInstTyCon {} -> True
1333                       _               -> False
1334
1335 tyConFamInstSig_maybe :: TyCon -> Maybe (TyCon, [Type], CoAxiom)
1336 tyConFamInstSig_maybe tc
1337   = case tyConParent tc of
1338       FamInstTyCon f ts co_tc -> Just (f, ts, co_tc)
1339       _                       -> Nothing
1340
1341 -- | If this 'TyCon' is that of a family instance, return the family in question
1342 -- and the instance types. Otherwise, return @Nothing@
1343 tyConFamInst_maybe :: TyCon -> Maybe (TyCon, [Type])
1344 tyConFamInst_maybe tc
1345   = case tyConParent tc of
1346       FamInstTyCon f ts _ -> Just (f, ts)
1347       _                   -> Nothing
1348
1349 -- | If this 'TyCon' is that of a family instance, return a 'TyCon' which represents
1350 -- a coercion identifying the representation type with the type instance family.
1351 -- Otherwise, return @Nothing@
1352 tyConFamilyCoercion_maybe :: TyCon -> Maybe CoAxiom
1353 tyConFamilyCoercion_maybe tc
1354   = case tyConParent tc of
1355       FamInstTyCon _ _ co -> Just co
1356       _                   -> Nothing
1357 \end{code}
1358
1359
1360 %************************************************************************
1361 %*                                                                      *
1362 \subsection[TyCon-instances]{Instance declarations for @TyCon@}
1363 %*                                                                      *
1364 %************************************************************************
1365
1366 @TyCon@s are compared by comparing their @Unique@s.
1367
1368 The strictness analyser needs @Ord@. It is a lexicographic order with
1369 the property @(a<=b) || (b<=a)@.
1370
1371 \begin{code}
1372 instance Eq TyCon where
1373     a == b = case (a `compare` b) of { EQ -> True;   _ -> False }
1374     a /= b = case (a `compare` b) of { EQ -> False;  _ -> True  }
1375
1376 instance Ord TyCon where
1377     a <= b = case (a `compare` b) of { LT -> True;  EQ -> True;  GT -> False }
1378     a <  b = case (a `compare` b) of { LT -> True;  EQ -> False; GT -> False }
1379     a >= b = case (a `compare` b) of { LT -> False; EQ -> True;  GT -> True  }
1380     a >  b = case (a `compare` b) of { LT -> False; EQ -> False; GT -> True  }
1381     compare a b = getUnique a `compare` getUnique b
1382
1383 instance Uniquable TyCon where
1384     getUnique tc = tyConUnique tc
1385
1386 instance Outputable TyCon where
1387     ppr tc  = ppr (getName tc)
1388
1389 instance NamedThing TyCon where
1390     getName = tyConName
1391
1392 instance Data.Typeable TyCon where
1393     typeOf _ = Data.mkTyConApp (Data.mkTyCon "TyCon") []
1394
1395 instance Data.Data TyCon where
1396     -- don't traverse?
1397     toConstr _   = abstractConstr "TyCon"
1398     gunfold _ _  = error "gunfold"
1399     dataTypeOf _ = mkNoRepType "TyCon"
1400
1401 -------------------
1402 instance Eq CoAxiom where
1403     a == b = case (a `compare` b) of { EQ -> True;   _ -> False }
1404     a /= b = case (a `compare` b) of { EQ -> False;  _ -> True  }
1405
1406 instance Ord CoAxiom where
1407     a <= b = case (a `compare` b) of { LT -> True;  EQ -> True;  GT -> False }
1408     a <  b = case (a `compare` b) of { LT -> True;  EQ -> False; GT -> False }
1409     a >= b = case (a `compare` b) of { LT -> False; EQ -> True;  GT -> True  }
1410     a >  b = case (a `compare` b) of { LT -> False; EQ -> False; GT -> True  }
1411     compare a b = getUnique a `compare` getUnique b
1412
1413 instance Uniquable CoAxiom where
1414     getUnique = co_ax_unique
1415
1416 instance Outputable CoAxiom where
1417     ppr = ppr . getName
1418
1419 instance NamedThing CoAxiom where
1420     getName = co_ax_name
1421
1422 instance Data.Typeable CoAxiom where
1423     typeOf _ = Data.mkTyConApp (Data.mkTyCon "CoAxiom") []
1424
1425 instance Data.Data CoAxiom where
1426     -- don't traverse?
1427     toConstr _   = abstractConstr "CoAxiom"
1428     gunfold _ _  = error "gunfold"
1429     dataTypeOf _ = mkNoRepType "CoAxiom"
1430 \end{code}