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