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