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