Major refactoring of CoAxioms
[ghc.git] / 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}