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