88a620978e341f39e54fa67fb15436b825dbeca4
[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         TyCon, FieldLabel,
11
12         PrimRep(..),
13         tyConPrimRep,
14         sizeofPrimRep,
15
16         AlgTyConRhs(..), visibleDataCons, 
17         TyConParent(..), 
18         SynTyConRhs(..),
19
20         isFunTyCon, isUnLiftedTyCon, isProductTyCon, 
21         isAlgTyCon, isDataTyCon, 
22         isNewTyCon, unwrapNewTyCon_maybe, 
23         isSynTyCon, isClosedSynTyCon, isOpenSynTyCon,
24         isPrimTyCon, 
25
26         isEnumerationTyCon, isGadtSyntaxTyCon, isOpenTyCon,
27         assocTyConArgPoss_maybe, isTyConAssoc, setTyConArgPoss,
28         isTupleTyCon, isUnboxedTupleTyCon, isBoxedTupleTyCon, tupleTyConBoxity,
29         isRecursiveTyCon, newTyConRhs, newTyConEtadRhs, newTyConCo_maybe,
30         isHiBootTyCon, isSuperKindTyCon,
31         isCoercionTyCon_maybe, isCoercionTyCon,
32         isImplicitTyCon,
33
34         tcExpandTyCon_maybe, coreExpandTyCon_maybe,
35
36         makeTyConAbstract, isAbstractTyCon,
37
38         mkForeignTyCon, isForeignTyCon,
39
40         mkAlgTyCon,
41         mkClassTyCon,
42         mkFunTyCon,
43         mkPrimTyCon,
44         mkVoidPrimTyCon,
45         mkLiftedPrimTyCon,
46         mkTupleTyCon,
47         mkSynTyCon,
48         mkSuperKindTyCon,
49         mkCoercionTyCon,
50
51         tyConName,
52         tyConKind,
53         tyConUnique,
54         tyConTyVars,
55         algTyConRhs, tyConDataCons, tyConDataCons_maybe, tyConFamilySize,
56         tyConSelIds,
57         tyConStupidTheta,
58         tyConArity,
59         isClassTyCon, tyConClass_maybe,
60         isFamInstTyCon, tyConFamInst_maybe, tyConFamilyCoercion_maybe,
61         synTyConDefn, synTyConRhs, synTyConType, synTyConResKind,
62         tyConExtName,           -- External name for foreign types
63
64         maybeTyConSingleCon,
65
66         -- Generics
67         tyConHasGenerics
68 ) where
69
70 #include "HsVersions.h"
71
72 import {-# SOURCE #-} TypeRep ( Kind, Type, PredType )
73 import {-# SOURCE #-} DataCon ( DataCon, isVanillaDataCon )
74
75 import Var
76 import Class
77 import BasicTypes
78 import Name
79 import PrelNames
80 import Maybes
81 import Outputable
82 import FastString
83 import Constants
84 \end{code}
85
86 %************************************************************************
87 %*                                                                      *
88 \subsection{The data type}
89 %*                                                                      *
90 %************************************************************************
91
92 \begin{code}
93 data TyCon
94   = FunTyCon {
95         tyConUnique :: Unique,
96         tyConName   :: Name,
97         tyConKind   :: Kind,
98         tyConArity  :: Arity
99     }
100
101
102   | AlgTyCon {          -- Data type, and newtype decls.
103                         -- All lifted, all boxed
104         tyConUnique :: Unique,
105         tyConName   :: Name,
106         tyConKind   :: Kind,
107         tyConArity  :: Arity,
108
109         tyConTyVars :: [TyVar],         -- Scopes over (a) the algTcStupidTheta
110                                         --             (b) the cached types in
111                                         --                 algTyConRhs.NewTyCon
112                                         --             (c) the family instance
113                                         --                 types if present
114                                         -- But not over the data constructors
115
116         algTcSelIds :: [Id],            -- Its record selectors (empty if none)
117
118         algTcGadtSyntax  :: Bool,       -- True <=> the data type was declared using GADT syntax
119                                         -- That doesn't mean it's a true GADT; only that the "where"
120                                         --      form was used. This field is used only to guide
121                                         --      pretty-printinng
122         algTcStupidTheta :: [PredType], -- The "stupid theta" for the data type
123                                         -- (always empty for GADTs)
124
125         algTcRhs :: AlgTyConRhs,        -- Data constructors in here
126
127         algTcRec :: RecFlag,            -- Tells whether the data type is part
128                                         -- of a mutually-recursive group or not
129
130         hasGenerics :: Bool,            -- True <=> generic to/from functions are available
131                                         -- (in the exports of the data type's source module)
132
133         algTcParent :: TyConParent      -- Gives the class or family tycon for
134                                         -- derived tycons representing classes
135                                         -- or family instances, respectively.
136     }
137
138   | TupleTyCon {
139         tyConUnique :: Unique,
140         tyConName   :: Name,
141         tyConKind   :: Kind,
142         tyConArity  :: Arity,
143         tyConBoxed  :: Boxity,
144         tyConTyVars :: [TyVar],
145         dataCon     :: DataCon,
146         hasGenerics :: Bool
147     }
148
149   | SynTyCon {
150         tyConUnique  :: Unique,
151         tyConName    :: Name,
152         tyConKind    :: Kind,
153         tyConArity   :: Arity,
154
155         tyConTyVars  :: [TyVar],        -- Bound tyvars
156
157         synTcRhs     :: SynTyConRhs,    -- Expanded type in here
158
159         synTcParent  :: TyConParent     -- Gives the family tycon of
160                                         -- representation tycons of family
161                                         -- instances
162
163     }
164
165   | PrimTyCon {                 -- Primitive types; cannot be defined in Haskell
166                                 -- Now includes foreign-imported types
167                                 -- Also includes Kinds
168         tyConUnique   :: Unique,
169         tyConName     :: Name,
170         tyConKind     :: Kind,
171         tyConArity    :: Arity,         -- SLPJ Oct06: I'm not sure what the significance
172                                         --             of the arity of a primtycon is!
173
174         primTyConRep  :: PrimRep,
175                         -- Many primitive tycons are unboxed, but some are
176                         -- boxed (represented by pointers). The CgRep tells.
177
178         isUnLifted   :: Bool,           -- Most primitive tycons are unlifted, 
179                                         -- but foreign-imported ones may not be
180         tyConExtName :: Maybe FastString        -- Just xx for foreign-imported types
181     }
182
183   | CoercionTyCon {     -- E.g. (:=:), sym, trans, left, right
184                         -- INVARIANT: coercions are always fully applied
185         tyConUnique :: Unique,
186         tyConName   :: Name,
187         tyConArity  :: Arity,
188         coKindFun   :: [Type] -> (Type,Type)
189     }           -- INVARAINT: coKindFun is always applied to exactly 'arity' args
190                 -- E.g. for trans (c1 :: ta=tb) (c2 :: tb=tc), the coKindFun returns 
191                 --      the kind as a pair of types: (ta,tc)
192         
193   | SuperKindTyCon {    -- Super Kinds, TY (box) and CO (diamond).
194                         -- They have no kind; and arity zero
195         tyConUnique :: Unique,
196         tyConName   :: Name
197     }
198
199 type FieldLabel = Name
200
201 -- Right hand sides of type constructors for algebraic types
202 --
203 data AlgTyConRhs
204
205   -- We know nothing about this data type, except that it's represented by a
206   -- pointer.  Used when we export a data type abstractly into an hi file.
207   --
208   = AbstractTyCon
209
210   -- The constructor represents an open family without a fixed right hand
211   -- side.  Additional instances can appear at any time.
212   -- 
213   -- These are introduced by either a top level decl:
214   --    data T a :: *
215   -- or an assoicated data type decl, in a class decl:
216   --    class C a b where
217   --      data T b :: *
218
219   | OpenTyCon {
220
221       otArgPoss   :: Maybe [Int]
222         -- Nothing <=> top-level indexed type family
223         -- Just ns <=> associated (not toplevel) family
224         --   In the latter case, for each tyvar in the AT decl, 'ns' gives the
225         --   position of that tyvar in the class argument list (starting from 0).
226         --   NB: Length is less than tyConArity iff higher kind signature.
227         
228     }
229
230   | DataTyCon {
231         data_cons :: [DataCon],
232                         -- The constructors; can be empty if the user declares
233                         --   the type to have no constructors
234                         -- INVARIANT: Kept in order of increasing tag
235                         --        (see the tag assignment in DataCon.mkDataCon)
236         is_enum :: Bool         -- Cached: True <=> an enumeration type
237     }                   --         Includes data types with no constructors.
238
239   | NewTyCon {
240         data_con :: DataCon,    -- The unique constructor; it has no existentials
241
242         nt_rhs :: Type,         -- Cached: the argument type of the constructor
243                                 --  = the representation type of the tycon
244                                 -- The free tyvars of this type are the tyConTyVars
245       
246         nt_co :: Maybe TyCon,   -- A CoercionTyCon used to create the newtype
247                                 -- from the representation
248                                 -- Optional for non-recursive newtypes
249                                 -- See Note [Newtype coercions]
250                                 -- Invariant: arity = #tvs in nt_etad_rhs;
251                                 --      See Note [Newtype eta]
252                                 -- Watch out!  If any newtypes become transparent
253                                 -- again check Trac #1072.
254
255         nt_etad_rhs :: ([TyVar], Type)
256                         -- The same again, but this time eta-reduced
257                         -- hence the [TyVar] which may be shorter than the declared 
258                         -- arity of the TyCon.  See Note [Newtype eta]
259     }
260
261 visibleDataCons :: AlgTyConRhs -> [DataCon]
262 visibleDataCons AbstractTyCon                 = []
263 visibleDataCons OpenTyCon {}                  = []
264 visibleDataCons (DataTyCon{ data_cons = cs }) = cs
265 visibleDataCons (NewTyCon{ data_con = c })    = [c]
266
267 -- Both type classes as well as family instances imply implicit
268 -- type constructors.  These implicit type constructors refer to their parent
269 -- structure (ie, the class or family from which they derive) using a type of
270 -- the following form.  We use `TyConParent' for both algebraic and synonym 
271 -- types, but the variant `ClassTyCon' will only be used by algebraic tycons.
272
273 data TyConParent 
274   = NoParentTyCon       -- An ordinary type constructor has no parent.
275
276   | ClassTyCon          -- Type constructors representing a class dictionary.
277         Class           -- INVARIANT: the classTyCon of this Class is the current tycon
278
279   | FamilyTyCon         -- Type constructors representing an instance of a type
280         TyCon           --   The type family
281         [Type]          --   Instance types; free variables are the tyConTyVars
282                         --      of the current TyCon (not the family one)
283                         --      INVARIANT: the number of types matches the arity 
284                         --                 of the family tycon
285         TyCon           --   A CoercionTyCon identifying the representation 
286                         --     type with the type instance family.  
287                         --      c.f. Note [Newtype coercions]
288
289         --
290         -- E.g.  data intance T [a] = ...
291         -- gives a representation tycon:
292         --      data :R7T a = ...
293         --      axiom co a :: T [a] ~ :R7T a
294         -- with :R7T's algTcParent = FamilyTyCon T [a] co
295
296 okParent :: Name -> TyConParent -> Bool -- Checks invariants
297 okParent _       NoParentTyCon                   = True
298 okParent tc_name (ClassTyCon cls)                = tyConName (classTyCon cls) == tc_name
299 okParent _       (FamilyTyCon fam_tc tys _co_tc) = tyConArity fam_tc == length tys
300
301 --------------------
302 data SynTyConRhs
303   = OpenSynTyCon Kind           -- Type family: *result* kind given
304                  (Maybe [Int])  -- for associated families: for each tyvars in
305                                 -- the AT decl, gives the position of that
306                                 -- tyvar in the class argument list (starting
307                                 -- from 0). 
308                                 -- NB: Length is less than tyConArity
309                                 --     if higher kind signature.
310
311   | SynonymTyCon Type   -- Mentioning head type vars.  Acts as a template for
312                         --  the expansion when the tycon is applied to some
313                         --  types.
314 \end{code}
315
316 Note [Newtype coercions]
317 ~~~~~~~~~~~~~~~~~~~~~~~~
318 The NewTyCon field nt_co is a a TyCon (a coercion constructor in fact)
319 which is used for coercing from the representation type of the
320 newtype, to the newtype itself. For example,
321
322    newtype T a = MkT (a -> a)
323
324 the NewTyCon for T will contain nt_co = CoT where CoT t : T t :=: t ->
325 t.  This TyCon is a CoercionTyCon, so it does not have a kind on its
326 own; it basically has its own typing rule for the fully-applied
327 version.  If the newtype T has k type variables then CoT has arity at
328 most k.  In the case that the right hand side is a type application
329 ending with the same type variables as the left hand side, we
330 "eta-contract" the coercion.  So if we had
331
332    newtype S a = MkT [a]
333
334 then we would generate the arity 0 coercion CoS : S :=: [].  The
335 primary reason we do this is to make newtype deriving cleaner.
336
337 In the paper we'd write
338         axiom CoT : (forall t. T t) :=: (forall t. [t])
339 and then when we used CoT at a particular type, s, we'd say
340         CoT @ s
341 which encodes as (TyConApp instCoercionTyCon [TyConApp CoT [], s])
342
343 But in GHC we instead make CoT into a new piece of type syntax, CoercionTyCon,
344 (like instCoercionTyCon, symCoercionTyCon etc), which must always
345 be saturated, but which encodes as
346         TyConApp CoT [s]
347 In the vocabulary of the paper it's as if we had axiom declarations
348 like
349         axiom CoT t :  T t :=: [t]
350
351 Note [Newtype eta]
352 ~~~~~~~~~~~~~~~~~~
353 Consider
354         newtype Parser m a = MkParser (Foogle m a)
355 Are these two types equal (to Core)?
356         Monad (Parser m) 
357         Monad (Foogle m)
358 Well, yes.  But to see that easily we eta-reduce the RHS type of
359 Parser, in this case to ([], Froogle), so that even unsaturated applications
360 of Parser will work right.  This eta reduction is done when the type 
361 constructor is built, and cached in NewTyCon.  The cached field is
362 only used in coreExpandTyCon_maybe.
363  
364 Here's an example that I think showed up in practice
365 Source code:
366         newtype T a = MkT [a]
367         newtype Foo m = MkFoo (forall a. m a -> Int)
368
369         w1 :: Foo []
370         w1 = ...
371         
372         w2 :: Foo T
373         w2 = MkFoo (\(MkT x) -> case w1 of MkFoo f -> f x)
374
375 After desugaring, and discading the data constructors for the newtypes,
376 we get:
377         w2 :: Foo T
378         w2 = w1
379 And now Lint complains unless Foo T == Foo [], and that requires T==[]
380
381 This point carries over to the newtype coercion, because we need to
382 say 
383         w2 = w1 `cast` Foo CoT
384
385 so the coercion tycon CoT must have 
386         kind:    T ~ []
387  and    arity:   0
388
389
390 Note [Indexed data types] (aka data type families)
391 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
392    See also Note [Wrappers for data instance tycons] in MkId.lhs
393
394 Consider
395         data family T a
396
397         data instance T (b,c) where
398           T1 :: b -> c -> T (b,c)
399
400 Then
401   * T is the "family TyCon"
402
403   * We make "representation TyCon" :R1T, thus:
404         data :R1T b c where
405           T1 :: forall b c. b -> c -> :R1T b c
406
407   * It has a top-level coercion connecting it to the family TyCon
408
409         axiom :Co:R1T b c : T (b,c) ~ :R1T b c
410
411   * The data contructor T1 has a wrapper (which is what the source-level
412     "T1" invokes):
413
414         $WT1 :: forall b c. b -> c -> T (b,c)
415         $WT1 b c (x::b) (y::c) = T1 b c x y `cast` sym (:Co:R1T b c)
416
417   * The representation TyCon :R1T has an AlgTyConParent of
418
419         FamilyTyCon T [(b,c)] :Co:R1T
420
421
422
423 %************************************************************************
424 %*                                                                      *
425 \subsection{PrimRep}
426 %*                                                                      *
427 %************************************************************************
428
429 A PrimRep is an abstraction of a type.  It contains information that
430 the code generator needs in order to pass arguments, return results,
431 and store values of this type.
432
433 A PrimRep is somewhat similar to a CgRep (see codeGen/SMRep) and a
434 MachRep (see cmm/MachOp), although each of these types has a distinct
435 and clearly defined purpose:
436
437   - A PrimRep is a CgRep + information about signedness + information
438     about primitive pointers (AddrRep).  Signedness and primitive
439     pointers are required when passing a primitive type to a foreign
440     function, but aren't needed for call/return conventions of Haskell
441     functions.
442
443   - A MachRep is a basic machine type (non-void, doesn't contain
444     information on pointerhood or signedness, but contains some
445     reps that don't have corresponding Haskell types).
446
447 \begin{code}
448 data PrimRep
449   = VoidRep
450   | PtrRep
451   | IntRep              -- signed, word-sized
452   | WordRep             -- unsinged, word-sized
453   | Int64Rep            -- signed, 64 bit (32-bit words only)
454   | Word64Rep           -- unsigned, 64 bit (32-bit words only)
455   | AddrRep             -- a pointer, but not to a Haskell value
456   | FloatRep
457   | DoubleRep
458   deriving( Eq )
459
460 -- Size of a PrimRep, in bytes
461 sizeofPrimRep :: PrimRep -> Int
462 sizeofPrimRep IntRep   = wORD_SIZE
463 sizeofPrimRep WordRep  = wORD_SIZE
464 sizeofPrimRep Int64Rep = wORD64_SIZE
465 sizeofPrimRep Word64Rep= wORD64_SIZE
466 sizeofPrimRep FloatRep = 4
467 sizeofPrimRep DoubleRep= 8
468 sizeofPrimRep AddrRep  = wORD_SIZE
469 sizeofPrimRep PtrRep   = wORD_SIZE
470 sizeofPrimRep VoidRep  = 0
471 \end{code}
472
473 %************************************************************************
474 %*                                                                      *
475 \subsection{TyCon Construction}
476 %*                                                                      *
477 %************************************************************************
478
479 Note: the TyCon constructors all take a Kind as one argument, even though
480 they could, in principle, work out their Kind from their other arguments.
481 But to do so they need functions from Types, and that makes a nasty
482 module mutual-recursion.  And they aren't called from many places.
483 So we compromise, and move their Kind calculation to the call site.
484
485 \begin{code}
486 mkFunTyCon :: Name -> Kind -> TyCon
487 mkFunTyCon name kind 
488   = FunTyCon { 
489         tyConUnique = nameUnique name,
490         tyConName   = name,
491         tyConKind   = kind,
492         tyConArity  = 2
493     }
494
495 -- This is the making of a TyCon. Just the same as the old mkAlgTyCon,
496 -- but now you also have to pass in the generic information about the type
497 -- constructor - you can get hold of it easily (see Generics module)
498 mkAlgTyCon :: Name
499            -> Kind
500            -> [TyVar]
501            -> [PredType]
502            -> AlgTyConRhs
503            -> [Id]
504            -> TyConParent
505            -> RecFlag
506            -> Bool
507            -> Bool
508            -> TyCon
509 mkAlgTyCon name kind tyvars stupid rhs sel_ids parent is_rec gen_info gadt_syn
510   = AlgTyCon {  
511         tyConName        = name,
512         tyConUnique      = nameUnique name,
513         tyConKind        = kind,
514         tyConArity       = length tyvars,
515         tyConTyVars      = tyvars,
516         algTcStupidTheta = stupid,
517         algTcRhs         = rhs,
518         algTcSelIds      = sel_ids,
519         algTcParent      = ASSERT( okParent name parent ) parent,
520         algTcRec         = is_rec,
521         algTcGadtSyntax  = gadt_syn,
522         hasGenerics = gen_info
523     }
524
525 mkClassTyCon :: Name -> Kind -> [TyVar] -> AlgTyConRhs -> Class -> RecFlag -> TyCon
526 mkClassTyCon name kind tyvars rhs clas is_rec =
527   mkAlgTyCon name kind tyvars [] rhs [] (ClassTyCon clas) is_rec False False
528
529 mkTupleTyCon :: Name -> Kind -> Arity -> [TyVar] -> DataCon -> Boxity -> Bool -> TyCon
530 mkTupleTyCon name kind arity tyvars con boxed gen_info
531   = TupleTyCon {
532         tyConUnique = nameUnique name,
533         tyConName = name,
534         tyConKind = kind,
535         tyConArity = arity,
536         tyConBoxed = boxed,
537         tyConTyVars = tyvars,
538         dataCon = con,
539         hasGenerics = gen_info
540     }
541
542 -- Foreign-imported (.NET) type constructors are represented
543 -- as primitive, but *lifted*, TyCons for now. They are lifted
544 -- because the Haskell type T representing the (foreign) .NET
545 -- type T is actually implemented (in ILX) as a thunk<T>
546 mkForeignTyCon :: Name -> Maybe FastString -> Kind -> Arity -> TyCon
547 mkForeignTyCon name ext_name kind arity
548   = PrimTyCon {
549         tyConName    = name,
550         tyConUnique  = nameUnique name,
551         tyConKind    = kind,
552         tyConArity   = arity,
553         primTyConRep = PtrRep, -- they all do
554         isUnLifted   = False,
555         tyConExtName = ext_name
556     }
557
558
559 -- most Prim tycons are lifted
560 mkPrimTyCon :: Name  -> Kind -> Arity -> PrimRep -> TyCon
561 mkPrimTyCon name kind arity rep
562   = mkPrimTyCon' name kind arity rep True  
563
564 mkVoidPrimTyCon :: Name -> Kind -> Arity -> TyCon
565 mkVoidPrimTyCon name kind arity 
566   = mkPrimTyCon' name kind arity VoidRep True  
567
568 -- but RealWorld is lifted
569 mkLiftedPrimTyCon :: Name  -> Kind -> Arity -> PrimRep -> TyCon
570 mkLiftedPrimTyCon name kind arity rep
571   = mkPrimTyCon' name kind arity rep False
572
573 mkPrimTyCon' :: Name  -> Kind -> Arity -> PrimRep -> Bool -> TyCon
574 mkPrimTyCon' name kind arity rep is_unlifted
575   = PrimTyCon {
576         tyConName    = name,
577         tyConUnique  = nameUnique name,
578         tyConKind    = kind,
579         tyConArity   = arity,
580         primTyConRep = rep,
581         isUnLifted   = is_unlifted,
582         tyConExtName = Nothing
583     }
584
585 mkSynTyCon :: Name -> Kind -> [TyVar] -> SynTyConRhs -> TyConParent -> TyCon
586 mkSynTyCon name kind tyvars rhs parent
587   = SynTyCon {  
588         tyConName = name,
589         tyConUnique = nameUnique name,
590         tyConKind = kind,
591         tyConArity = length tyvars,
592         tyConTyVars = tyvars,
593         synTcRhs = rhs,
594         synTcParent = parent
595     }
596
597 mkCoercionTyCon :: Name -> Arity -> ([Type] -> (Type,Type)) -> TyCon
598 mkCoercionTyCon name arity kindRule
599   = CoercionTyCon {
600         tyConName = name,
601         tyConUnique = nameUnique name,
602         tyConArity = arity,
603         coKindFun = kindRule
604     }
605
606 -- Super kinds always have arity zero
607 mkSuperKindTyCon :: Name -> TyCon
608 mkSuperKindTyCon name
609   = SuperKindTyCon {
610         tyConName = name,
611         tyConUnique = nameUnique name
612   }
613 \end{code}
614
615 \begin{code}
616 isFunTyCon :: TyCon -> Bool
617 isFunTyCon (FunTyCon {}) = True
618 isFunTyCon _             = False
619
620 isAbstractTyCon :: TyCon -> Bool
621 isAbstractTyCon (AlgTyCon { algTcRhs = AbstractTyCon }) = True
622 isAbstractTyCon _ = False
623
624 makeTyConAbstract :: TyCon -> TyCon
625 makeTyConAbstract tc@(AlgTyCon {}) = tc { algTcRhs = AbstractTyCon }
626 makeTyConAbstract tc = pprPanic "makeTyConAbstract" (ppr tc)
627
628 isPrimTyCon :: TyCon -> Bool
629 isPrimTyCon (PrimTyCon {}) = True
630 isPrimTyCon _              = False
631
632 isUnLiftedTyCon :: TyCon -> Bool
633 isUnLiftedTyCon (PrimTyCon  {isUnLifted = is_unlifted}) = is_unlifted
634 isUnLiftedTyCon (TupleTyCon {tyConBoxed = boxity})      = not (isBoxed boxity)
635 isUnLiftedTyCon _                                       = False
636
637 -- isAlgTyCon returns True for both @data@ and @newtype@
638 isAlgTyCon :: TyCon -> Bool
639 isAlgTyCon (AlgTyCon {})   = True
640 isAlgTyCon (TupleTyCon {}) = True
641 isAlgTyCon _               = False
642
643 isDataTyCon :: TyCon -> Bool
644 -- isDataTyCon returns True for data types that are definitely
645 -- represented by heap-allocated constructors.
646 -- These are srcutinised by Core-level @case@ expressions, and they
647 -- get info tables allocated for them.
648 --      True for all @data@ types
649 --      False for newtypes
650 --                unboxed tuples
651 --                type families
652 -- 
653 -- NB: for a data type family, T, only the *instance* tycons are
654 --     get an info table etc.  The family tycon does not.
655 --     Hence False for OpenTyCon
656 isDataTyCon (AlgTyCon {algTcRhs = rhs})
657   = case rhs of
658         OpenTyCon {}  -> False
659         DataTyCon {}  -> True
660         NewTyCon {}   -> False
661         AbstractTyCon -> False   -- We don't know, so return False
662 isDataTyCon (TupleTyCon {tyConBoxed = boxity}) = isBoxed boxity
663 isDataTyCon _ = False
664
665 isNewTyCon :: TyCon -> Bool
666 isNewTyCon (AlgTyCon {algTcRhs = NewTyCon {}}) = True
667 isNewTyCon _                                   = False
668
669 unwrapNewTyCon_maybe :: TyCon -> Maybe ([TyVar], Type, Maybe TyCon)
670 unwrapNewTyCon_maybe (AlgTyCon { tyConTyVars = tvs, 
671                                  algTcRhs = NewTyCon { nt_co = mb_co, 
672                                                        nt_rhs = rhs }})
673                            = Just (tvs, rhs, mb_co)
674 unwrapNewTyCon_maybe _     = Nothing
675
676 isProductTyCon :: TyCon -> Bool
677 -- A "product" tycon
678 --      has *one* constructor, 
679 --      is *not* existential
680 -- but
681 --      may be  DataType, NewType
682 --      may be  unboxed or not, 
683 --      may be  recursive or not
684 -- 
685 isProductTyCon tc@(AlgTyCon {}) = case algTcRhs tc of
686                                     DataTyCon{ data_cons = [data_con] } 
687                                                 -> isVanillaDataCon data_con
688                                     NewTyCon {} -> True
689                                     _           -> False
690 isProductTyCon (TupleTyCon {})  = True   
691 isProductTyCon _                = False
692
693 isSynTyCon :: TyCon -> Bool
694 isSynTyCon (SynTyCon {}) = True
695 isSynTyCon _             = False
696
697 -- As for newtypes, it is in some contexts important to distinguish between
698 -- closed synonyms and synonym families, as synonym families have no unique
699 -- right hand side to which a synonym family application can expand.
700 --
701 isClosedSynTyCon :: TyCon -> Bool
702 isClosedSynTyCon tycon = isSynTyCon tycon && not (isOpenTyCon tycon)
703
704 isOpenSynTyCon :: TyCon -> Bool
705 isOpenSynTyCon tycon = isSynTyCon tycon && isOpenTyCon tycon
706
707 isGadtSyntaxTyCon :: TyCon -> Bool
708 isGadtSyntaxTyCon (AlgTyCon { algTcGadtSyntax = res }) = res
709 isGadtSyntaxTyCon _                                    = False
710
711 isEnumerationTyCon :: TyCon -> Bool
712 isEnumerationTyCon (AlgTyCon {algTcRhs = DataTyCon { is_enum = res }}) = res
713 isEnumerationTyCon _                                                   = False
714
715 isOpenTyCon :: TyCon -> Bool
716 isOpenTyCon (SynTyCon {synTcRhs = OpenSynTyCon _ _}) = True
717 isOpenTyCon (AlgTyCon {algTcRhs = OpenTyCon {}    }) = True
718 isOpenTyCon _                                        = False
719
720 assocTyConArgPoss_maybe :: TyCon -> Maybe [Int]
721 assocTyConArgPoss_maybe (AlgTyCon { 
722                            algTcRhs = OpenTyCon {otArgPoss = poss}})  = poss
723 assocTyConArgPoss_maybe (SynTyCon { synTcRhs = OpenSynTyCon _ poss }) = poss
724 assocTyConArgPoss_maybe _ = Nothing
725
726 isTyConAssoc :: TyCon -> Bool
727 isTyConAssoc = isJust . assocTyConArgPoss_maybe
728
729 setTyConArgPoss :: TyCon -> [Int] -> TyCon
730 setTyConArgPoss tc@(AlgTyCon { algTcRhs = rhs })               poss = 
731   tc { algTcRhs = rhs {otArgPoss = Just poss} }
732 setTyConArgPoss tc@(SynTyCon { synTcRhs = OpenSynTyCon ki _ }) poss = 
733   tc { synTcRhs = OpenSynTyCon ki (Just poss) }
734 setTyConArgPoss tc _ = pprPanic "setTyConArgPoss" (ppr tc)
735
736 isTupleTyCon :: TyCon -> Bool
737 -- The unit tycon didn't used to be classed as a tuple tycon
738 -- but I thought that was silly so I've undone it
739 -- If it can't be for some reason, it should be a AlgTyCon
740 --
741 -- NB: when compiling Data.Tuple, the tycons won't reply True to
742 -- isTupleTyCon, becuase they are built as AlgTyCons.  However they
743 -- get spat into the interface file as tuple tycons, so I don't think
744 -- it matters.
745 isTupleTyCon (TupleTyCon {}) = True
746 isTupleTyCon _               = False
747
748 isUnboxedTupleTyCon :: TyCon -> Bool
749 isUnboxedTupleTyCon (TupleTyCon {tyConBoxed = boxity}) = not (isBoxed boxity)
750 isUnboxedTupleTyCon _                                  = False
751
752 isBoxedTupleTyCon :: TyCon -> Bool
753 isBoxedTupleTyCon (TupleTyCon {tyConBoxed = boxity}) = isBoxed boxity
754 isBoxedTupleTyCon _                                  = False
755
756 tupleTyConBoxity :: TyCon -> Boxity
757 tupleTyConBoxity tc = tyConBoxed tc
758
759 isRecursiveTyCon :: TyCon -> Bool
760 isRecursiveTyCon (AlgTyCon {algTcRec = Recursive}) = True
761 isRecursiveTyCon _                                 = False
762
763 isHiBootTyCon :: TyCon -> Bool
764 -- Used for knot-tying in hi-boot files
765 isHiBootTyCon (AlgTyCon {algTcRhs = AbstractTyCon}) = True
766 isHiBootTyCon _                                     = False
767
768 isForeignTyCon :: TyCon -> Bool
769 -- isForeignTyCon identifies foreign-imported type constructors
770 isForeignTyCon (PrimTyCon {tyConExtName = Just _}) = True
771 isForeignTyCon _                                   = False
772
773 isSuperKindTyCon :: TyCon -> Bool
774 isSuperKindTyCon (SuperKindTyCon {}) = True
775 isSuperKindTyCon _                   = False
776
777 isCoercionTyCon_maybe :: TyCon -> Maybe (Arity, [Type] -> (Type,Type))
778 isCoercionTyCon_maybe (CoercionTyCon {tyConArity = ar, coKindFun = rule}) 
779   = Just (ar, rule)
780 isCoercionTyCon_maybe _ = Nothing
781
782 isCoercionTyCon :: TyCon -> Bool
783 isCoercionTyCon (CoercionTyCon {}) = True
784 isCoercionTyCon _                  = False
785
786 -- Identifies implicit tycons that, in particular, do not go into interface
787 -- files (because they are implicitly reconstructed when the interface is
788 -- read).
789 --
790 -- Note that 
791 --
792 -- * associated families are implicit, as they are re-constructed from
793 --   the class declaration in which they reside, and 
794 -- * family instances are *not* implicit as they represent the instance body
795 --   (similar to a dfun does that for a class instance).
796 --
797 isImplicitTyCon :: TyCon -> Bool
798 isImplicitTyCon tycon | isTyConAssoc tycon           = True
799                       | isSynTyCon tycon             = False
800                       | isAlgTyCon tycon             = isClassTyCon tycon ||
801                                                        isTupleTyCon tycon
802 isImplicitTyCon _other                               = True
803         -- catches: FunTyCon, PrimTyCon, 
804         -- CoercionTyCon, SuperKindTyCon
805 \end{code}
806
807
808 -----------------------------------------------
809 --      Expand type-constructor applications
810 -----------------------------------------------
811
812 \begin{code}
813 tcExpandTyCon_maybe, coreExpandTyCon_maybe 
814         :: TyCon 
815         -> [Type]                       -- Args to tycon
816         -> Maybe ([(TyVar,Type)],       -- Substitution
817                   Type,                 -- Body type (not yet substituted)
818                   [Type])               -- Leftover args
819
820 -- For the *typechecker* view, we expand (closed) synonyms only
821 tcExpandTyCon_maybe (SynTyCon {tyConTyVars = tvs, 
822                                synTcRhs = SynonymTyCon rhs }) tys
823    = expand tvs rhs tys
824 tcExpandTyCon_maybe _ _ = Nothing
825
826 ---------------
827 -- For the *Core* view, we expand synonyms only as well
828
829 coreExpandTyCon_maybe (AlgTyCon {algTcRec = NonRecursive,       -- Not recursive
830          algTcRhs = NewTyCon { nt_etad_rhs = etad_rhs, nt_co = Nothing }}) tys
831    = case etad_rhs of   -- Don't do this in the pattern match, lest we accidentally
832                         -- match the etad_rhs of a *recursive* newtype
833         (tvs,rhs) -> expand tvs rhs tys
834
835 coreExpandTyCon_maybe tycon tys = tcExpandTyCon_maybe tycon tys
836
837
838 ----------------
839 expand  :: [TyVar] -> Type                      -- Template
840         -> [Type]                               -- Args
841         -> Maybe ([(TyVar,Type)], Type, [Type]) -- Expansion
842 expand tvs rhs tys
843   = case n_tvs `compare` length tys of
844         LT -> Just (tvs `zip` tys, rhs, drop n_tvs tys)
845         EQ -> Just (tvs `zip` tys, rhs, [])
846         GT -> Nothing
847    where
848      n_tvs = length tvs
849 \end{code}
850
851 \begin{code}
852 tyConHasGenerics :: TyCon -> Bool
853 tyConHasGenerics (AlgTyCon {hasGenerics = hg})   = hg
854 tyConHasGenerics (TupleTyCon {hasGenerics = hg}) = hg
855 tyConHasGenerics _                               = False        -- Synonyms
856
857 tyConDataCons :: TyCon -> [DataCon]
858 -- It's convenient for tyConDataCons to return the
859 -- empty list for type synonyms etc
860 tyConDataCons tycon = tyConDataCons_maybe tycon `orElse` []
861
862 tyConDataCons_maybe :: TyCon -> Maybe [DataCon]
863 tyConDataCons_maybe (AlgTyCon {algTcRhs = DataTyCon { data_cons = cons }}) = Just cons
864 tyConDataCons_maybe (AlgTyCon {algTcRhs = NewTyCon { data_con = con }})    = Just [con]
865 tyConDataCons_maybe (TupleTyCon {dataCon = con})                           = Just [con]
866 tyConDataCons_maybe _                                                      = Nothing
867
868 tyConFamilySize  :: TyCon -> Int
869 tyConFamilySize (AlgTyCon   {algTcRhs = DataTyCon {data_cons = cons}}) = 
870   length cons
871 tyConFamilySize (AlgTyCon   {algTcRhs = NewTyCon {}})                  = 1
872 tyConFamilySize (AlgTyCon   {algTcRhs = OpenTyCon {}})                 = 0
873 tyConFamilySize (TupleTyCon {})                                        = 1
874 tyConFamilySize other = pprPanic "tyConFamilySize:" (ppr other)
875
876 tyConSelIds :: TyCon -> [Id]
877 tyConSelIds (AlgTyCon {algTcSelIds = fs}) = fs
878 tyConSelIds _                             = []
879
880 algTyConRhs :: TyCon -> AlgTyConRhs
881 algTyConRhs (AlgTyCon {algTcRhs = rhs})  = rhs
882 algTyConRhs (TupleTyCon {dataCon = con}) = DataTyCon { data_cons = [con], is_enum = False }
883 algTyConRhs other = pprPanic "algTyConRhs" (ppr other)
884 \end{code}
885
886 \begin{code}
887 newTyConRhs :: TyCon -> ([TyVar], Type)
888 newTyConRhs (AlgTyCon {tyConTyVars = tvs, algTcRhs = NewTyCon { nt_rhs = rhs }}) = (tvs, rhs)
889 newTyConRhs tycon = pprPanic "newTyConRhs" (ppr tycon)
890
891 newTyConEtadRhs :: TyCon -> ([TyVar], Type)
892 newTyConEtadRhs (AlgTyCon {algTcRhs = NewTyCon { nt_etad_rhs = tvs_rhs }}) = tvs_rhs
893 newTyConEtadRhs tycon = pprPanic "newTyConEtadRhs" (ppr tycon)
894
895 newTyConCo_maybe :: TyCon -> Maybe TyCon
896 newTyConCo_maybe (AlgTyCon {algTcRhs = NewTyCon { nt_co = co }}) = co
897 newTyConCo_maybe _                                               = Nothing
898
899 tyConPrimRep :: TyCon -> PrimRep
900 tyConPrimRep (PrimTyCon {primTyConRep = rep}) = rep
901 tyConPrimRep tc = ASSERT(not (isUnboxedTupleTyCon tc)) PtrRep
902 \end{code}
903
904 \begin{code}
905 tyConStupidTheta :: TyCon -> [PredType]
906 tyConStupidTheta (AlgTyCon {algTcStupidTheta = stupid}) = stupid
907 tyConStupidTheta (TupleTyCon {})                        = []
908 tyConStupidTheta tycon = pprPanic "tyConStupidTheta" (ppr tycon)
909 \end{code}
910
911 \begin{code}
912 synTyConDefn :: TyCon -> ([TyVar], Type)
913 synTyConDefn (SynTyCon {tyConTyVars = tyvars, synTcRhs = SynonymTyCon ty}) 
914   = (tyvars, ty)
915 synTyConDefn tycon = pprPanic "getSynTyConDefn" (ppr tycon)
916
917 synTyConRhs :: TyCon -> SynTyConRhs
918 synTyConRhs (SynTyCon {synTcRhs = rhs}) = rhs
919 synTyConRhs tc                          = pprPanic "synTyConRhs" (ppr tc)
920
921 synTyConType :: TyCon -> Type
922 synTyConType tc = case synTcRhs tc of
923                     SynonymTyCon t -> t
924                     _              -> pprPanic "synTyConType" (ppr tc)
925
926 synTyConResKind :: TyCon -> Kind
927 synTyConResKind (SynTyCon {synTcRhs = OpenSynTyCon kind _}) = kind
928 synTyConResKind tycon  = pprPanic "synTyConResKind" (ppr tycon)
929 \end{code}
930
931 \begin{code}
932 maybeTyConSingleCon :: TyCon -> Maybe DataCon
933 maybeTyConSingleCon (AlgTyCon {algTcRhs = DataTyCon {data_cons = [c] }}) = Just c
934 maybeTyConSingleCon (AlgTyCon {algTcRhs = NewTyCon { data_con = c }})    = Just c
935 maybeTyConSingleCon (AlgTyCon {})                = Nothing
936 maybeTyConSingleCon (TupleTyCon {dataCon = con}) = Just con
937 maybeTyConSingleCon (PrimTyCon {})               = Nothing
938 maybeTyConSingleCon (FunTyCon {})                = Nothing  -- case at funty
939 maybeTyConSingleCon tc = pprPanic "maybeTyConSingleCon: unexpected tycon " $ ppr tc
940 \end{code}
941
942 \begin{code}
943 isClassTyCon :: TyCon -> Bool
944 isClassTyCon (AlgTyCon {algTcParent = ClassTyCon _}) = True
945 isClassTyCon _                                       = False
946
947 tyConClass_maybe :: TyCon -> Maybe Class
948 tyConClass_maybe (AlgTyCon {algTcParent = ClassTyCon clas}) = Just clas
949 tyConClass_maybe _                                          = Nothing
950
951 isFamInstTyCon :: TyCon -> Bool
952 isFamInstTyCon (AlgTyCon {algTcParent = FamilyTyCon _ _ _ }) = True
953 isFamInstTyCon (SynTyCon {synTcParent = FamilyTyCon _ _ _ }) = True
954 isFamInstTyCon _                                             = False
955
956 tyConFamInst_maybe :: TyCon -> Maybe (TyCon, [Type])
957 tyConFamInst_maybe (AlgTyCon {algTcParent = FamilyTyCon fam instTys _}) = 
958   Just (fam, instTys)
959 tyConFamInst_maybe (SynTyCon {synTcParent = FamilyTyCon fam instTys _}) = 
960   Just (fam, instTys)
961 tyConFamInst_maybe _                                                    = 
962   Nothing
963
964 tyConFamilyCoercion_maybe :: TyCon -> Maybe TyCon
965 tyConFamilyCoercion_maybe (AlgTyCon {algTcParent = FamilyTyCon _ _ coe}) = 
966   Just coe
967 tyConFamilyCoercion_maybe (SynTyCon {synTcParent = FamilyTyCon _ _ coe}) = 
968   Just coe
969 tyConFamilyCoercion_maybe _                                              =
970   Nothing
971 \end{code}
972
973
974 %************************************************************************
975 %*                                                                      *
976 \subsection[TyCon-instances]{Instance declarations for @TyCon@}
977 %*                                                                      *
978 %************************************************************************
979
980 @TyCon@s are compared by comparing their @Unique@s.
981
982 The strictness analyser needs @Ord@. It is a lexicographic order with
983 the property @(a<=b) || (b<=a)@.
984
985 \begin{code}
986 instance Eq TyCon where
987     a == b = case (a `compare` b) of { EQ -> True;   _ -> False }
988     a /= b = case (a `compare` b) of { EQ -> False;  _ -> True  }
989
990 instance Ord TyCon where
991     a <= b = case (a `compare` b) of { LT -> True;  EQ -> True;  GT -> False }
992     a <  b = case (a `compare` b) of { LT -> True;  EQ -> False; GT -> False }
993     a >= b = case (a `compare` b) of { LT -> False; EQ -> True;  GT -> True  }
994     a >  b = case (a `compare` b) of { LT -> False; EQ -> False; GT -> True  }
995     compare a b = getUnique a `compare` getUnique b
996
997 instance Uniquable TyCon where
998     getUnique tc = tyConUnique tc
999
1000 instance Outputable TyCon where
1001     ppr tc  = ppr (getName tc) 
1002
1003 instance NamedThing TyCon where
1004     getName = tyConName
1005 \end{code}