Re-add FunTy (big patch)
[ghc.git] / compiler / types / TyCon.hs
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
9 {-# LANGUAGE CPP #-}
10
11 module TyCon(
12 -- * Main TyCon data types
13 TyCon,
14
15 AlgTyConRhs(..), visibleDataCons,
16 AlgTyConFlav(..), isNoParent,
17 FamTyConFlav(..), Role(..), Injectivity(..),
18 RuntimeRepInfo(..),
19
20 -- ** Field labels
21 tyConFieldLabels, tyConFieldLabelEnv,
22
23 -- ** Constructing TyCons
24 mkAlgTyCon,
25 mkClassTyCon,
26 mkFunTyCon,
27 mkPrimTyCon,
28 mkKindTyCon,
29 mkLiftedPrimTyCon,
30 mkTupleTyCon,
31 mkSynonymTyCon,
32 mkFamilyTyCon,
33 mkPromotedDataCon,
34 mkTcTyCon,
35
36 -- ** Predicates on TyCons
37 isAlgTyCon, isVanillaAlgTyCon,
38 isClassTyCon, isFamInstTyCon,
39 isFunTyCon,
40 isPrimTyCon,
41 isTupleTyCon, isUnboxedTupleTyCon, isBoxedTupleTyCon,
42 isTypeSynonymTyCon,
43 mightBeUnsaturatedTyCon,
44 isPromotedDataCon, isPromotedDataCon_maybe,
45 isKindTyCon, isLiftedTypeKindTyConName,
46
47 isDataTyCon, isProductTyCon, isDataProductTyCon_maybe,
48 isEnumerationTyCon,
49 isNewTyCon, isAbstractTyCon,
50 isFamilyTyCon, isOpenFamilyTyCon,
51 isTypeFamilyTyCon, isDataFamilyTyCon,
52 isOpenTypeFamilyTyCon, isClosedSynFamilyTyConWithAxiom_maybe,
53 familyTyConInjectivityInfo,
54 isBuiltInSynFamTyCon_maybe,
55 isUnliftedTyCon,
56 isGadtSyntaxTyCon, isInjectiveTyCon, isGenerativeTyCon, isGenInjAlgRhs,
57 isTyConAssoc, tyConAssoc_maybe,
58 isRecursiveTyCon,
59 isImplicitTyCon,
60 isTyConWithSrcDataCons,
61 isTcTyCon,
62
63 -- ** Extracting information out of TyCons
64 tyConName,
65 tyConKind,
66 tyConUnique,
67 tyConTyVars,
68 tyConCType, tyConCType_maybe,
69 tyConDataCons, tyConDataCons_maybe,
70 tyConSingleDataCon_maybe, tyConSingleDataCon,
71 tyConSingleAlgDataCon_maybe,
72 tyConFamilySize,
73 tyConStupidTheta,
74 tyConArity,
75 tyConRoles,
76 tyConFlavour,
77 tyConTuple_maybe, tyConClass_maybe, tyConATs,
78 tyConFamInst_maybe, tyConFamInstSig_maybe, tyConFamilyCoercion_maybe,
79 tyConFamilyResVar_maybe,
80 synTyConDefn_maybe, synTyConRhs_maybe,
81 famTyConFlav_maybe, famTcResVar,
82 algTyConRhs,
83 newTyConRhs, newTyConEtadArity, newTyConEtadRhs,
84 unwrapNewTyCon_maybe, unwrapNewTyConEtad_maybe,
85 algTcFields,
86 tyConRuntimeRepInfo,
87 tyConBinders, tyConResKind,
88 tcTyConScopedTyVars,
89
90 -- ** Manipulating TyCons
91 expandSynTyCon_maybe,
92 makeTyConAbstract,
93 newTyConCo, newTyConCo_maybe,
94 pprPromotionQuote,
95
96 -- * Runtime type representation
97 TyConRepName, tyConRepName_maybe,
98 mkPrelTyConRepName,
99 tyConRepModOcc,
100
101 -- * Primitive representations of Types
102 PrimRep(..), PrimElemRep(..),
103 isVoidRep, isGcPtrRep,
104 primRepSizeW, primElemRepSizeB,
105 primRepIsFloat,
106
107 -- * Recursion breaking
108 RecTcChecker, initRecTc, checkRecTc
109
110 ) where
111
112 #include "HsVersions.h"
113
114 import {-# SOURCE #-} TyCoRep ( Kind, Type, PredType, TyBinder, pprType, mkPiTys )
115 import {-# SOURCE #-} TysWiredIn ( runtimeRepTyCon, constraintKind
116 , vecCountTyCon, vecElemTyCon, liftedTypeKind )
117 import {-# SOURCE #-} DataCon ( DataCon, dataConExTyVars, dataConFieldLabels )
118
119 import Binary
120 import Var
121 import Class
122 import BasicTypes
123 import DynFlags
124 import ForeignCall
125 import Name
126 import NameEnv
127 import CoAxiom
128 import PrelNames
129 import Maybes
130 import Outputable
131 import FastStringEnv
132 import FieldLabel
133 import Constants
134 import Util
135 import Unique( tyConRepNameUnique, dataConRepNameUnique )
136 import UniqSet
137 import Module
138
139 import qualified Data.Data as Data
140
141 {-
142 -----------------------------------------------
143 Notes about type families
144 -----------------------------------------------
145
146 Note [Type synonym families]
147 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
148 * Type synonym families, also known as "type functions", map directly
149 onto the type functions in FC:
150
151 type family F a :: *
152 type instance F Int = Bool
153 ..etc...
154
155 * Reply "yes" to isTypeFamilyTyCon, and isFamilyTyCon
156
157 * From the user's point of view (F Int) and Bool are simply
158 equivalent types.
159
160 * A Haskell 98 type synonym is a degenerate form of a type synonym
161 family.
162
163 * Type functions can't appear in the LHS of a type function:
164 type instance F (F Int) = ... -- BAD!
165
166 * Translation of type family decl:
167 type family F a :: *
168 translates to
169 a FamilyTyCon 'F', whose FamTyConFlav is OpenSynFamilyTyCon
170
171 type family G a :: * where
172 G Int = Bool
173 G Bool = Char
174 G a = ()
175 translates to
176 a FamilyTyCon 'G', whose FamTyConFlav is ClosedSynFamilyTyCon, with the
177 appropriate CoAxiom representing the equations
178
179 We also support injective type families -- see Note [Injective type families]
180
181 Note [Data type families]
182 ~~~~~~~~~~~~~~~~~~~~~~~~~
183 See also Note [Wrappers for data instance tycons] in MkId.hs
184
185 * Data type families are declared thus
186 data family T a :: *
187 data instance T Int = T1 | T2 Bool
188
189 Here T is the "family TyCon".
190
191 * Reply "yes" to isDataFamilyTyCon, and isFamilyTyCon
192
193 * The user does not see any "equivalent types" as he did with type
194 synonym families. He just sees constructors with types
195 T1 :: T Int
196 T2 :: Bool -> T Int
197
198 * Here's the FC version of the above declarations:
199
200 data T a
201 data R:TInt = T1 | T2 Bool
202 axiom ax_ti : T Int ~R R:TInt
203
204 Note that this is a *representational* coercion
205 The R:TInt is the "representation TyCons".
206 It has an AlgTyConFlav of
207 DataFamInstTyCon T [Int] ax_ti
208
209 * The axiom ax_ti may be eta-reduced; see
210 Note [Eta reduction for data family axioms] in TcInstDcls
211
212 * The data contructor T2 has a wrapper (which is what the
213 source-level "T2" invokes):
214
215 $WT2 :: Bool -> T Int
216 $WT2 b = T2 b `cast` sym ax_ti
217
218 * A data instance can declare a fully-fledged GADT:
219
220 data instance T (a,b) where
221 X1 :: T (Int,Bool)
222 X2 :: a -> b -> T (a,b)
223
224 Here's the FC version of the above declaration:
225
226 data R:TPair a where
227 X1 :: R:TPair Int Bool
228 X2 :: a -> b -> R:TPair a b
229 axiom ax_pr :: T (a,b) ~R R:TPair a b
230
231 $WX1 :: forall a b. a -> b -> T (a,b)
232 $WX1 a b (x::a) (y::b) = X2 a b x y `cast` sym (ax_pr a b)
233
234 The R:TPair are the "representation TyCons".
235 We have a bit of work to do, to unpick the result types of the
236 data instance declaration for T (a,b), to get the result type in the
237 representation; e.g. T (a,b) --> R:TPair a b
238
239 The representation TyCon R:TList, has an AlgTyConFlav of
240
241 DataFamInstTyCon T [(a,b)] ax_pr
242
243 * Notice that T is NOT translated to a FC type function; it just
244 becomes a "data type" with no constructors, which can be coerced inot
245 into R:TInt, R:TPair by the axioms. These axioms
246 axioms come into play when (and *only* when) you
247 - use a data constructor
248 - do pattern matching
249 Rather like newtype, in fact
250
251 As a result
252
253 - T behaves just like a data type so far as decomposition is concerned
254
255 - (T Int) is not implicitly converted to R:TInt during type inference.
256 Indeed the latter type is unknown to the programmer.
257
258 - There *is* an instance for (T Int) in the type-family instance
259 environment, but it is only used for overlap checking
260
261 - It's fine to have T in the LHS of a type function:
262 type instance F (T a) = [a]
263
264 It was this last point that confused me! The big thing is that you
265 should not think of a data family T as a *type function* at all, not
266 even an injective one! We can't allow even injective type functions
267 on the LHS of a type function:
268 type family injective G a :: *
269 type instance F (G Int) = Bool
270 is no good, even if G is injective, because consider
271 type instance G Int = Bool
272 type instance F Bool = Char
273
274 So a data type family is not an injective type function. It's just a
275 data type with some axioms that connect it to other data types.
276
277 * The tyConTyVars of the representation tycon are the tyvars that the
278 user wrote in the patterns. This is important in TcDeriv, where we
279 bring these tyvars into scope before type-checking the deriving
280 clause. This fact is arranged for in TcInstDecls.tcDataFamInstDecl.
281
282 Note [Associated families and their parent class]
283 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
284 *Associated* families are just like *non-associated* families, except
285 that they have a famTcParent field of (Just cls), which identifies the
286 parent class.
287
288 However there is an important sharing relationship between
289 * the tyConTyVars of the parent Class
290 * the tyConTyvars of the associated TyCon
291
292 class C a b where
293 data T p a
294 type F a q b
295
296 Here the 'a' and 'b' are shared with the 'Class'; that is, they have
297 the same Unique.
298
299 This is important. In an instance declaration we expect
300 * all the shared variables to be instantiated the same way
301 * the non-shared variables of the associated type should not
302 be instantiated at all
303
304 instance C [x] (Tree y) where
305 data T p [x] = T1 x | T2 p
306 type F [x] q (Tree y) = (x,y,q)
307
308 Note [TyCon Role signatures]
309 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
310 Every tycon has a role signature, assigning a role to each of the tyConTyVars
311 (or of equal length to the tyConArity, if there are no tyConTyVars). An
312 example demonstrates these best: say we have a tycon T, with parameters a at
313 nominal, b at representational, and c at phantom. Then, to prove
314 representational equality between T a1 b1 c1 and T a2 b2 c2, we need to have
315 nominal equality between a1 and a2, representational equality between b1 and
316 b2, and nothing in particular (i.e., phantom equality) between c1 and c2. This
317 might happen, say, with the following declaration:
318
319 data T a b c where
320 MkT :: b -> T Int b c
321
322 Data and class tycons have their roles inferred (see inferRoles in TcTyDecls),
323 as do vanilla synonym tycons. Family tycons have all parameters at role N,
324 though it is conceivable that we could relax this restriction. (->)'s and
325 tuples' parameters are at role R. Each primitive tycon declares its roles;
326 it's worth noting that (~#)'s parameters are at role N. Promoted data
327 constructors' type arguments are at role R. All kind arguments are at role
328 N.
329
330 Note [Unboxed tuple RuntimeRep vars]
331 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
332 The contents of an unboxed tuple may have any representation. Accordingly,
333 the kind of the unboxed tuple constructor is runtime-representation
334 polymorphic. For example,
335
336 (#,#) :: forall (q :: RuntimeRep) (r :: RuntimeRep). TYPE q -> TYPE r -> #
337
338 These extra tyvars (v and w) cause some delicate processing around tuples,
339 where we used to be able to assume that the tycon arity and the
340 datacon arity were the same.
341
342 Note [Injective type families]
343 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
344 We allow injectivity annotations for type families (both open and closed):
345
346 type family F (a :: k) (b :: k) = r | r -> a
347 type family G a b = res | res -> a b where ...
348
349 Injectivity information is stored in the `famTcInj` field of `FamilyTyCon`.
350 `famTcInj` maybe stores a list of Bools, where each entry corresponds to a
351 single element of `tyConTyVars` (both lists should have identical length). If no
352 injectivity annotation was provided `famTcInj` is Nothing. From this follows an
353 invariant that if `famTcInj` is a Just then at least one element in the list
354 must be True.
355
356 See also:
357 * [Injectivity annotation] in HsDecls
358 * [Renaming injectivity annotation] in RnSource
359 * [Verifying injectivity annotation] in FamInstEnv
360 * [Type inference for type families with injectivity] in TcInteract
361
362
363 ************************************************************************
364 * *
365 \subsection{The data type}
366 * *
367 ************************************************************************
368 -}
369
370 {- Note [TyCon binders]
371 ~~~~~~~~~~~~~~~~~~~~~~~
372
373 data TyConBinder = TCB TyVar TcConBinderVis
374
375 data TyConBinderVis = NamedTCB VisiblityFlag
376 | AnonTCB
377 -}
378
379 -- | TyCons represent type constructors. Type constructors are introduced by
380 -- things such as:
381 --
382 -- 1) Data declarations: @data Foo = ...@ creates the @Foo@ type constructor of
383 -- kind @*@
384 --
385 -- 2) Type synonyms: @type Foo = ...@ creates the @Foo@ type constructor
386 --
387 -- 3) Newtypes: @newtype Foo a = MkFoo ...@ creates the @Foo@ type constructor
388 -- of kind @* -> *@
389 --
390 -- 4) Class declarations: @class Foo where@ creates the @Foo@ type constructor
391 -- of kind @*@
392 --
393 -- This data type also encodes a number of primitive, built in type constructors
394 -- such as those for function and tuple types.
395
396 -- If you edit this type, you may need to update the GHC formalism
397 -- See Note [GHC Formalism] in coreSyn/CoreLint.hs
398 data TyCon
399 = -- | The function type constructor, @(->)@
400 FunTyCon {
401 tyConUnique :: Unique, -- ^ A Unique of this TyCon. Invariant:
402 -- identical to Unique of Name stored in
403 -- tyConName field.
404
405 tyConName :: Name, -- ^ Name of the constructor
406
407 -- See Note [The binders/kind/arity fields of a TyCon]
408 tyConBinders :: [TyBinder], -- ^ The TyBinders for this TyCon's kind.
409 tyConResKind :: Kind, -- ^ Result kind
410 tyConKind :: Kind, -- ^ Kind of this TyCon
411 tyConArity :: Arity, -- ^ Arity
412
413 tcRepName :: TyConRepName
414 }
415
416 -- | Algebraic data types, from
417 -- - @data@ declararations
418 -- - @newtype@ declarations
419 -- - data instance declarations
420 -- - type instance declarations
421 -- - the TyCon generated by a class declaration
422 -- - boxed tuples
423 -- - unboxed tuples
424 -- - constraint tuples
425 -- All these constructors are lifted and boxed except unboxed tuples
426 -- which should have an 'UnboxedAlgTyCon' parent.
427 -- Data/newtype/type /families/ are handled by 'FamilyTyCon'.
428 -- See 'AlgTyConRhs' for more information.
429 | AlgTyCon {
430 tyConUnique :: Unique, -- ^ A Unique of this TyCon. Invariant:
431 -- identical to Unique of Name stored in
432 -- tyConName field.
433
434 tyConName :: Name, -- ^ Name of the constructor
435
436 -- See Note [The binders/kind/arity fields of a TyCon]
437 tyConBinders :: [TyBinder], -- ^ The TyBinders for this TyCon's kind.
438 tyConResKind :: Kind, -- ^ Result kind
439 tyConKind :: Kind, -- ^ Kind of this TyCon
440 tyConArity :: Arity, -- ^ Arity
441
442 -- See Note [tyConTyVars and tyConBinders]
443 tyConTyVars :: [TyVar], -- ^ The kind and type variables used in the
444 -- type constructor.
445 -- Invariant: length tyConTyVars = tyConArity
446 -- Precisely, this list scopes over:
447 --
448 -- 1. The 'algTcStupidTheta'
449 -- 2. The cached types in algTyConRhs.NewTyCon
450 -- 3. The family instance types if present
451 --
452 -- Note that it does /not/ scope over the data
453 -- constructors.
454
455 tcRoles :: [Role], -- ^ The role for each type variable
456 -- This list has length = tyConArity
457 -- See also Note [TyCon Role signatures]
458
459 tyConCType :: Maybe CType,-- ^ The C type that should be used
460 -- for this type when using the FFI
461 -- and CAPI
462
463 algTcGadtSyntax :: Bool, -- ^ Was the data type declared with GADT
464 -- syntax? If so, that doesn't mean it's a
465 -- true GADT; only that the "where" form
466 -- was used. This field is used only to
467 -- guide pretty-printing
468
469 algTcStupidTheta :: [PredType], -- ^ The \"stupid theta\" for the data
470 -- type (always empty for GADTs). A
471 -- \"stupid theta\" is the context to
472 -- the left of an algebraic type
473 -- declaration, e.g. @Eq a@ in the
474 -- declaration @data Eq a => T a ...@.
475
476 algTcRhs :: AlgTyConRhs, -- ^ Contains information about the
477 -- data constructors of the algebraic type
478
479 algTcFields :: FieldLabelEnv, -- ^ Maps a label to information
480 -- about the field
481
482 algTcRec :: RecFlag, -- ^ Tells us whether the data type is part
483 -- of a mutually-recursive group or not
484
485 algTcParent :: AlgTyConFlav -- ^ Gives the class or family declaration
486 -- 'TyCon' for derived 'TyCon's representing
487 -- class or family instances, respectively.
488
489 }
490
491 -- | Represents type synonyms
492 | SynonymTyCon {
493 tyConUnique :: Unique, -- ^ A Unique of this TyCon. Invariant:
494 -- identical to Unique of Name stored in
495 -- tyConName field.
496
497 tyConName :: Name, -- ^ Name of the constructor
498
499 -- See Note [The binders/kind/arity fields of a TyCon]
500 tyConBinders :: [TyBinder], -- ^ The TyBinders for this TyCon's kind.
501 tyConResKind :: Kind, -- ^ Result kind
502 tyConKind :: Kind, -- ^ Kind of this TyCon
503 tyConArity :: Arity, -- ^ Arity
504
505 -- See Note [tyConTyVars and tyConBinders]
506 tyConTyVars :: [TyVar], -- ^ List of type and kind variables in this
507 -- TyCon. Includes implicit kind variables.
508 -- Scopes over: synTcRhs
509
510 tcRoles :: [Role], -- ^ The role for each type variable
511 -- This list has length = tyConArity
512 -- See also Note [TyCon Role signatures]
513
514 synTcRhs :: Type -- ^ Contains information about the expansion
515 -- of the synonym
516 }
517
518 -- | Represents families (both type and data)
519 -- Argument roles are all Nominal
520 | FamilyTyCon {
521 tyConUnique :: Unique, -- ^ A Unique of this TyCon. Invariant:
522 -- identical to Unique of Name stored in
523 -- tyConName field.
524
525 tyConName :: Name, -- ^ Name of the constructor
526
527 -- See Note [The binders/kind/arity fields of a TyCon]
528 tyConBinders :: [TyBinder], -- ^ The TyBinders for this TyCon's kind.
529 tyConResKind :: Kind, -- ^ Result kind
530 tyConKind :: Kind, -- ^ Kind of this TyCon
531 tyConArity :: Arity, -- ^ Arity
532
533 -- See Note [tyConTyVars and tyConBinders]
534 tyConTyVars :: [TyVar], -- ^ The kind and type variables used in the
535 -- type constructor.
536 -- Invariant: length tyvars = arity
537 -- Needed to connect an associated family TyCon
538 -- with its parent class; see TcValidity.checkConsistentFamInst
539
540 famTcResVar :: Maybe Name, -- ^ Name of result type variable, used
541 -- for pretty-printing with --show-iface
542 -- and for reifying TyCon in Template
543 -- Haskell
544
545 famTcFlav :: FamTyConFlav, -- ^ Type family flavour: open, closed,
546 -- abstract, built-in. See comments for
547 -- FamTyConFlav
548
549 famTcParent :: Maybe Class, -- ^ For *associated* type/data families
550 -- The class in whose declaration the family is declared
551 -- See Note [Associated families and their parent class]
552
553 famTcInj :: Injectivity -- ^ is this a type family injective in
554 -- its type variables? Nothing if no
555 -- injectivity annotation was given
556 }
557
558 -- | Primitive types; cannot be defined in Haskell. This includes
559 -- the usual suspects (such as @Int#@) as well as foreign-imported
560 -- types and kinds (@*@, @#@, and @?@)
561 | PrimTyCon {
562 tyConUnique :: Unique, -- ^ A Unique of this TyCon. Invariant:
563 -- identical to Unique of Name stored in
564 -- tyConName field.
565
566 tyConName :: Name, -- ^ Name of the constructor
567
568 -- See Note [The binders/kind/arity fields of a TyCon]
569 tyConBinders :: [TyBinder], -- ^ The TyBinders for this TyCon's kind.
570 tyConResKind :: Kind, -- ^ Result kind
571 tyConKind :: Kind, -- ^ Kind of this TyCon
572 tyConArity :: Arity, -- ^ Arity
573
574 tcRoles :: [Role], -- ^ The role for each type variable
575 -- This list has length = tyConArity
576 -- See also Note [TyCon Role signatures]
577
578 isUnlifted :: Bool, -- ^ Most primitive tycons are unlifted (may
579 -- not contain bottom) but other are lifted,
580 -- e.g. @RealWorld@
581 -- Only relevant if tyConKind = *
582
583 primRepName :: Maybe TyConRepName -- Only relevant for kind TyCons
584 -- i.e, *, #, ?
585 }
586
587 -- | Represents promoted data constructor.
588 | PromotedDataCon { -- See Note [Promoted data constructors]
589 tyConUnique :: Unique, -- ^ Same Unique as the data constructor
590 tyConName :: Name, -- ^ Same Name as the data constructor
591
592 -- See Note [The binders/kind/arity fields of a TyCon]
593 tyConBinders :: [TyBinder], -- ^ The TyBinders for this TyCon's kind.
594 tyConResKind :: Kind, -- ^ Result kind
595 tyConKind :: Kind, -- ^ Kind of this TyCon
596 tyConArity :: Arity, -- ^ Arity
597
598 tcRoles :: [Role], -- ^ Roles: N for kind vars, R for type vars
599 dataCon :: DataCon, -- ^ Corresponding data constructor
600 tcRepName :: TyConRepName,
601 promDcRepInfo :: RuntimeRepInfo -- ^ See comments with 'RuntimeRepInfo'
602 }
603
604 -- | These exist only during a recursive type/class type-checking knot.
605 | TcTyCon {
606 tyConUnique :: Unique,
607 tyConName :: Name,
608 tyConUnsat :: Bool, -- ^ can this tycon be unsaturated?
609
610 -- See Note [The binders/kind/arity fields of a TyCon]
611 tyConTyVars :: [TyVar], -- ^ The TyCon's parameterised tyvars
612 tyConBinders :: [TyBinder], -- ^ The TyBinders for this TyCon's kind.
613 tyConResKind :: Kind, -- ^ Result kind
614 tyConKind :: Kind, -- ^ Kind of this TyCon
615 tyConArity :: Arity, -- ^ Arity
616
617 tcTyConScopedTyVars :: [TyVar] -- ^ Scoped tyvars over the
618 -- tycon's body. See Note [TcTyCon]
619 }
620
621
622 -- | Represents right-hand-sides of 'TyCon's for algebraic types
623 data AlgTyConRhs
624
625 -- | Says that we know nothing about this data type, except that
626 -- it's represented by a pointer. Used when we export a data type
627 -- abstractly into an .hi file.
628 = AbstractTyCon
629 Bool -- True <=> It's definitely a distinct data type,
630 -- equal only to itself; ie not a newtype
631 -- False <=> Not sure
632
633 -- | Information about those 'TyCon's derived from a @data@
634 -- declaration. This includes data types with no constructors at
635 -- all.
636 | DataTyCon {
637 data_cons :: [DataCon],
638 -- ^ The data type constructors; can be empty if the
639 -- user declares the type to have no constructors
640 --
641 -- INVARIANT: Kept in order of increasing 'DataCon'
642 -- tag (see the tag assignment in DataCon.mkDataCon)
643
644 is_enum :: Bool -- ^ Cached value: is this an enumeration type?
645 -- See Note [Enumeration types]
646 }
647
648 | TupleTyCon { -- A boxed, unboxed, or constraint tuple
649 data_con :: DataCon, -- NB: it can be an *unboxed* tuple
650 tup_sort :: TupleSort -- ^ Is this a boxed, unboxed or constraint
651 -- tuple?
652 }
653
654 -- | Information about those 'TyCon's derived from a @newtype@ declaration
655 | NewTyCon {
656 data_con :: DataCon, -- ^ The unique constructor for the @newtype@.
657 -- It has no existentials
658
659 nt_rhs :: Type, -- ^ Cached value: the argument type of the
660 -- constructor, which is just the representation
661 -- type of the 'TyCon' (remember that @newtype@s
662 -- do not exist at runtime so need a different
663 -- representation type).
664 --
665 -- The free 'TyVar's of this type are the
666 -- 'tyConTyVars' from the corresponding 'TyCon'
667
668 nt_etad_rhs :: ([TyVar], Type),
669 -- ^ Same as the 'nt_rhs', but this time eta-reduced.
670 -- Hence the list of 'TyVar's in this field may be
671 -- shorter than the declared arity of the 'TyCon'.
672
673 -- See Note [Newtype eta]
674 nt_co :: CoAxiom Unbranched
675 -- The axiom coercion that creates the @newtype@
676 -- from the representation 'Type'.
677
678 -- See Note [Newtype coercions]
679 -- Invariant: arity = #tvs in nt_etad_rhs;
680 -- See Note [Newtype eta]
681 -- Watch out! If any newtypes become transparent
682 -- again check Trac #1072.
683 }
684
685 -- | Some promoted datacons signify extra info relevant to GHC. For example,
686 -- the @IntRep@ constructor of @RuntimeRep@ corresponds to the 'IntRep'
687 -- constructor of 'PrimRep'. This data structure allows us to store this
688 -- information right in the 'TyCon'. The other approach would be to look
689 -- up things like @RuntimeRep@'s @PrimRep@ by known-key every time.
690 data RuntimeRepInfo
691 = NoRRI -- ^ an ordinary promoted data con
692 | RuntimeRep ([Type] -> PrimRep)
693 -- ^ A constructor of @RuntimeRep@. The argument to the function should
694 -- be the list of arguments to the promoted datacon.
695 | VecCount Int -- ^ A constructor of @VecCount@
696 | VecElem PrimElemRep -- ^ A constructor of @VecElem@
697
698 -- | Extract those 'DataCon's that we are able to learn about. Note
699 -- that visibility in this sense does not correspond to visibility in
700 -- the context of any particular user program!
701 visibleDataCons :: AlgTyConRhs -> [DataCon]
702 visibleDataCons (AbstractTyCon {}) = []
703 visibleDataCons (DataTyCon{ data_cons = cs }) = cs
704 visibleDataCons (NewTyCon{ data_con = c }) = [c]
705 visibleDataCons (TupleTyCon{ data_con = c }) = [c]
706
707 -- ^ Both type classes as well as family instances imply implicit
708 -- type constructors. These implicit type constructors refer to their parent
709 -- structure (ie, the class or family from which they derive) using a type of
710 -- the following form.
711 data AlgTyConFlav
712 = -- | An ordinary type constructor has no parent.
713 VanillaAlgTyCon
714 TyConRepName
715
716 -- | An unboxed type constructor. Note that this carries no TyConRepName
717 -- as it is not representable.
718 | UnboxedAlgTyCon
719
720 -- | Type constructors representing a class dictionary.
721 -- See Note [ATyCon for classes] in TyCoRep
722 | ClassTyCon
723 Class -- INVARIANT: the classTyCon of this Class is the
724 -- current tycon
725 TyConRepName
726
727 -- | Type constructors representing an *instance* of a *data* family.
728 -- Parameters:
729 --
730 -- 1) The type family in question
731 --
732 -- 2) Instance types; free variables are the 'tyConTyVars'
733 -- of the current 'TyCon' (not the family one). INVARIANT:
734 -- the number of types matches the arity of the family 'TyCon'
735 --
736 -- 3) A 'CoTyCon' identifying the representation
737 -- type with the type instance family
738 | DataFamInstTyCon -- See Note [Data type families]
739 (CoAxiom Unbranched) -- The coercion axiom.
740 -- A *Representational* coercion,
741 -- of kind T ty1 ty2 ~R R:T a b c
742 -- where T is the family TyCon,
743 -- and R:T is the representation TyCon (ie this one)
744 -- and a,b,c are the tyConTyVars of this TyCon
745 --
746 -- BUT may be eta-reduced; see TcInstDcls
747 -- Note [Eta reduction for data family axioms]
748
749 -- Cached fields of the CoAxiom, but adjusted to
750 -- use the tyConTyVars of this TyCon
751 TyCon -- The family TyCon
752 [Type] -- Argument types (mentions the tyConTyVars of this TyCon)
753 -- Match in length the tyConTyVars of the family TyCon
754
755 -- E.g. data intance T [a] = ...
756 -- gives a representation tycon:
757 -- data R:TList a = ...
758 -- axiom co a :: T [a] ~ R:TList a
759 -- with R:TList's algTcParent = DataFamInstTyCon T [a] co
760
761 instance Outputable AlgTyConFlav where
762 ppr (VanillaAlgTyCon {}) = text "Vanilla ADT"
763 ppr (UnboxedAlgTyCon {}) = text "Unboxed ADT"
764 ppr (ClassTyCon cls _) = text "Class parent" <+> ppr cls
765 ppr (DataFamInstTyCon _ tc tys) = text "Family parent (family instance)"
766 <+> ppr tc <+> sep (map pprType tys)
767
768 -- | Checks the invariants of a 'AlgTyConFlav' given the appropriate type class
769 -- name, if any
770 okParent :: Name -> AlgTyConFlav -> Bool
771 okParent _ (VanillaAlgTyCon {}) = True
772 okParent _ (UnboxedAlgTyCon) = True
773 okParent tc_name (ClassTyCon cls _) = tc_name == tyConName (classTyCon cls)
774 okParent _ (DataFamInstTyCon _ fam_tc tys) = tyConArity fam_tc == length tys
775
776 isNoParent :: AlgTyConFlav -> Bool
777 isNoParent (VanillaAlgTyCon {}) = True
778 isNoParent _ = False
779
780 --------------------
781
782 data Injectivity
783 = NotInjective
784 | Injective [Bool] -- 1-1 with tyConTyVars (incl kind vars)
785 deriving( Eq )
786
787 -- | Information pertaining to the expansion of a type synonym (@type@)
788 data FamTyConFlav
789 = -- | Represents an open type family without a fixed right hand
790 -- side. Additional instances can appear at any time.
791 --
792 -- These are introduced by either a top level declaration:
793 --
794 -- > data family T a :: *
795 --
796 -- Or an associated data type declaration, within a class declaration:
797 --
798 -- > class C a b where
799 -- > data T b :: *
800 DataFamilyTyCon
801 TyConRepName
802
803 -- | An open type synonym family e.g. @type family F x y :: * -> *@
804 | OpenSynFamilyTyCon
805
806 -- | A closed type synonym family e.g.
807 -- @type family F x where { F Int = Bool }@
808 | ClosedSynFamilyTyCon (Maybe (CoAxiom Branched))
809 -- See Note [Closed type families]
810
811 -- | A closed type synonym family declared in an hs-boot file with
812 -- type family F a where ..
813 | AbstractClosedSynFamilyTyCon
814
815 -- | Built-in type family used by the TypeNats solver
816 | BuiltInSynFamTyCon BuiltInSynFamily
817
818 {- Note [The binders/kind/arity fields of a TyCon]
819 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
820 All TyCons have this group of fields
821 tyConBinders :: [TyBinder]
822 tyConResKind :: Kind
823 tyConKind :: Kind -- Cached = mkPiTys tyConBinders tyConResKind
824 tyConArity :: Arity -- Cached = length tyConBinders
825
826 They fit together like so:
827
828 * tyConBinders gives the telescope of Named (forall'd)
829 Anon (ordinary ->) binders
830
831 * Note that tyConBinders /includes/ Anon arguments. For example:
832 type App a (b :: k) = a b
833 -- App :: forall {k}; (k->*) -> k -> *
834 we get
835 tyConTyBinders = [ Named (k :: *) Invisible, Anon (k->*), Anon k ]
836
837 * tyConKind is the full kind of the TyCon,
838 not just the result kind
839
840 * tyConArity is the arguments this TyCon must be applied to, to be
841 considered saturated. Here we mean "applied to in the actual Type",
842 not surface syntax; i.e. including implicit kind variables.
843
844 Note [tyConTyVars and tyConBinders]
845 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
846 Consider
847 type App a (b :: k) = a b
848 -- App :: forall {k}; (k->*) -> k -> *
849
850 For App we get:
851 tyConTyVars = [ k:*, a:k->*, b:k]
852 tyConTyBinders = [ Named (k :: *) Invisible, Anon (k->*), Anon k ]
853
854 The tyConBinder field is used to construct the kind of App, namely
855 App :: forall {k}; (k->*) -> k -> *
856 The tyConTyVars field always corresponds 1-1 with tyConBinders, and
857 records the names of the binders. That is important for type synonyms,
858 etc, where those names scope over some other field in the TyCon. In
859 this case, 'a' and 'b' are mentioned in the RHS.
860
861 Note [Closed type families]
862 ~~~~~~~~~~~~~~~~~~~~~~~~~
863 * In an open type family you can add new instances later. This is the
864 usual case.
865
866 * In a closed type family you can only put equations where the family
867 is defined.
868
869 A non-empty closed type family has a single axiom with multiple
870 branches, stored in the 'ClosedSynFamilyTyCon' constructor. A closed
871 type family with no equations does not have an axiom, because there is
872 nothing for the axiom to prove!
873
874
875 Note [Promoted data constructors]
876 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
877 All data constructors can be promoted to become a type constructor,
878 via the PromotedDataCon alternative in TyCon.
879
880 * The TyCon promoted from a DataCon has the *same* Name and Unique as
881 the DataCon. Eg. If the data constructor Data.Maybe.Just(unique 78,
882 say) is promoted to a TyCon whose name is Data.Maybe.Just(unique 78)
883
884 * Small note: We promote the *user* type of the DataCon. Eg
885 data T = MkT {-# UNPACK #-} !(Bool, Bool)
886 The promoted kind is
887 MkT :: (Bool,Bool) -> T
888 *not*
889 MkT :: Bool -> Bool -> T
890
891 Note [Enumeration types]
892 ~~~~~~~~~~~~~~~~~~~~~~~~
893 We define datatypes with no constructors to *not* be
894 enumerations; this fixes trac #2578, Otherwise we
895 end up generating an empty table for
896 <mod>_<type>_closure_tbl
897 which is used by tagToEnum# to map Int# to constructors
898 in an enumeration. The empty table apparently upset
899 the linker.
900
901 Moreover, all the data constructor must be enumerations, meaning
902 they have type (forall abc. T a b c). GADTs are not enumerations.
903 For example consider
904 data T a where
905 T1 :: T Int
906 T2 :: T Bool
907 T3 :: T a
908 What would [T1 ..] be? [T1,T3] :: T Int? Easiest thing is to exclude them.
909 See Trac #4528.
910
911 Note [Newtype coercions]
912 ~~~~~~~~~~~~~~~~~~~~~~~~
913 The NewTyCon field nt_co is a CoAxiom which is used for coercing from
914 the representation type of the newtype, to the newtype itself. For
915 example,
916
917 newtype T a = MkT (a -> a)
918
919 the NewTyCon for T will contain nt_co = CoT where CoT t : T t ~ t -> t.
920
921 In the case that the right hand side is a type application
922 ending with the same type variables as the left hand side, we
923 "eta-contract" the coercion. So if we had
924
925 newtype S a = MkT [a]
926
927 then we would generate the arity 0 axiom CoS : S ~ []. The
928 primary reason we do this is to make newtype deriving cleaner.
929
930 In the paper we'd write
931 axiom CoT : (forall t. T t) ~ (forall t. [t])
932 and then when we used CoT at a particular type, s, we'd say
933 CoT @ s
934 which encodes as (TyConApp instCoercionTyCon [TyConApp CoT [], s])
935
936 Note [Newtype eta]
937 ~~~~~~~~~~~~~~~~~~
938 Consider
939 newtype Parser a = MkParser (IO a) deriving Monad
940 Are these two types equal (to Core)?
941 Monad Parser
942 Monad IO
943 which we need to make the derived instance for Monad Parser.
944
945 Well, yes. But to see that easily we eta-reduce the RHS type of
946 Parser, in this case to ([], Froogle), so that even unsaturated applications
947 of Parser will work right. This eta reduction is done when the type
948 constructor is built, and cached in NewTyCon.
949
950 Here's an example that I think showed up in practice
951 Source code:
952 newtype T a = MkT [a]
953 newtype Foo m = MkFoo (forall a. m a -> Int)
954
955 w1 :: Foo []
956 w1 = ...
957
958 w2 :: Foo T
959 w2 = MkFoo (\(MkT x) -> case w1 of MkFoo f -> f x)
960
961 After desugaring, and discarding the data constructors for the newtypes,
962 we get:
963 w2 = w1 `cast` Foo CoT
964 so the coercion tycon CoT must have
965 kind: T ~ []
966 and arity: 0
967
968 Note [TcTyCon]
969 ~~~~~~~~~~~~~~
970 When checking a type/class declaration (in module TcTyClsDecls), we come
971 upon knowledge of the eventual tycon in bits and pieces. First, we use
972 getInitialKinds to look over the user-provided kind signature of a tycon
973 (including, for example, the number of parameters written to the tycon)
974 to get an initial shape of the tycon's kind. Then, using these initial
975 kinds, we kind-check the body of the tycon (class methods, data constructors,
976 etc.), filling in the metavariables in the tycon's initial kind.
977 We then generalize to get the tycon's final, fixed kind. Finally, once
978 this has happened for all tycons in a mutually recursive group, we
979 can desugar the lot.
980
981 For convenience, we store partially-known tycons in TcTyCons, which
982 might store meta-variables. These TcTyCons are stored in the local
983 environment in TcTyClsDecls, until the real full TyCons can be created
984 during desugaring. A desugared program should never have a TcTyCon.
985
986 A challenging piece in all of this is that we end up taking three separate
987 passes over every declaration: one in getInitialKind (this pass look only
988 at the head, not the body), one in kcTyClDecls (to kind-check the body),
989 and a final one in tcTyClDecls (to desugar). In the latter two passes,
990 we need to connect the user-written type variables in an LHsQTyVars
991 with the variables in the tycon's inferred kind. Because the tycon might
992 not have a CUSK, this matching up is, in general, quite hard to do.
993 (Look through the git history between Dec 2015 and Apr 2016 for
994 TcHsType.splitTelescopeTvs!) Instead of trying, we just store the list
995 of type variables to bring into scope in the later passes when we create
996 a TcTyCon in getInitialKinds. Much easier this way! These tyvars are
997 brought into scope in kcTyClTyVars and tcTyClTyVars, both in TcHsType.
998
999 It is important that the scoped type variables not be zonked, as some
1000 scoped type variables come into existence as SigTvs. If we zonk, the
1001 Unique will change and the user-written occurrences won't match up with
1002 what we expect.
1003
1004 In a TcTyCon, everything is zonked (except the scoped vars) after
1005 the kind-checking pass.
1006
1007 ************************************************************************
1008 * *
1009 TyConRepName
1010 * *
1011 ********************************************************************* -}
1012
1013 type TyConRepName = Name -- The Name of the top-level declaration
1014 -- $tcMaybe :: Data.Typeable.Internal.TyCon
1015 -- $tcMaybe = TyCon { tyConName = "Maybe", ... }
1016
1017 tyConRepName_maybe :: TyCon -> Maybe TyConRepName
1018 tyConRepName_maybe (FunTyCon { tcRepName = rep_nm })
1019 = Just rep_nm
1020 tyConRepName_maybe (PrimTyCon { primRepName = mb_rep_nm })
1021 = mb_rep_nm
1022 tyConRepName_maybe (AlgTyCon { algTcParent = parent })
1023 | VanillaAlgTyCon rep_nm <- parent = Just rep_nm
1024 | ClassTyCon _ rep_nm <- parent = Just rep_nm
1025 tyConRepName_maybe (FamilyTyCon { famTcFlav = DataFamilyTyCon rep_nm })
1026 = Just rep_nm
1027 tyConRepName_maybe (PromotedDataCon { tcRepName = rep_nm })
1028 = Just rep_nm
1029 tyConRepName_maybe _ = Nothing
1030
1031 -- | Make a 'Name' for the 'Typeable' representation of the given wired-in type
1032 mkPrelTyConRepName :: Name -> TyConRepName
1033 -- See Note [Grand plan for Typeable] in 'TcTypeable' in TcTypeable.
1034 mkPrelTyConRepName tc_name -- Prelude tc_name is always External,
1035 -- so nameModule will work
1036 = mkExternalName rep_uniq rep_mod rep_occ (nameSrcSpan tc_name)
1037 where
1038 name_occ = nameOccName tc_name
1039 name_mod = nameModule tc_name
1040 name_uniq = nameUnique tc_name
1041 rep_uniq | isTcOcc name_occ = tyConRepNameUnique name_uniq
1042 | otherwise = dataConRepNameUnique name_uniq
1043 (rep_mod, rep_occ) = tyConRepModOcc name_mod name_occ
1044
1045 -- | The name (and defining module) for the Typeable representation (TyCon) of a
1046 -- type constructor.
1047 --
1048 -- See Note [Grand plan for Typeable] in 'TcTypeable' in TcTypeable.
1049 tyConRepModOcc :: Module -> OccName -> (Module, OccName)
1050 tyConRepModOcc tc_module tc_occ = (rep_module, mkTyConRepOcc tc_occ)
1051 where
1052 rep_module
1053 | tc_module == gHC_PRIM = gHC_TYPES
1054 | otherwise = tc_module
1055
1056
1057 {- *********************************************************************
1058 * *
1059 PrimRep
1060 * *
1061 ************************************************************************
1062
1063 Note [rep swamp]
1064
1065 GHC has a rich selection of types that represent "primitive types" of
1066 one kind or another. Each of them makes a different set of
1067 distinctions, and mostly the differences are for good reasons,
1068 although it's probably true that we could merge some of these.
1069
1070 Roughly in order of "includes more information":
1071
1072 - A Width (cmm/CmmType) is simply a binary value with the specified
1073 number of bits. It may represent a signed or unsigned integer, a
1074 floating-point value, or an address.
1075
1076 data Width = W8 | W16 | W32 | W64 | W80 | W128
1077
1078 - Size, which is used in the native code generator, is Width +
1079 floating point information.
1080
1081 data Size = II8 | II16 | II32 | II64 | FF32 | FF64 | FF80
1082
1083 it is necessary because e.g. the instruction to move a 64-bit float
1084 on x86 (movsd) is different from the instruction to move a 64-bit
1085 integer (movq), so the mov instruction is parameterised by Size.
1086
1087 - CmmType wraps Width with more information: GC ptr, float, or
1088 other value.
1089
1090 data CmmType = CmmType CmmCat Width
1091
1092 data CmmCat -- "Category" (not exported)
1093 = GcPtrCat -- GC pointer
1094 | BitsCat -- Non-pointer
1095 | FloatCat -- Float
1096
1097 It is important to have GcPtr information in Cmm, since we generate
1098 info tables containing pointerhood for the GC from this. As for
1099 why we have float (and not signed/unsigned) here, see Note [Signed
1100 vs unsigned].
1101
1102 - ArgRep makes only the distinctions necessary for the call and
1103 return conventions of the STG machine. It is essentially CmmType
1104 + void.
1105
1106 - PrimRep makes a few more distinctions than ArgRep: it divides
1107 non-GC-pointers into signed/unsigned and addresses, information
1108 that is necessary for passing these values to foreign functions.
1109
1110 There's another tension here: whether the type encodes its size in
1111 bytes, or whether its size depends on the machine word size. Width
1112 and CmmType have the size built-in, whereas ArgRep and PrimRep do not.
1113
1114 This means to turn an ArgRep/PrimRep into a CmmType requires DynFlags.
1115
1116 On the other hand, CmmType includes some "nonsense" values, such as
1117 CmmType GcPtrCat W32 on a 64-bit machine.
1118 -}
1119
1120 -- | A 'PrimRep' is an abstraction of a type. It contains information that
1121 -- the code generator needs in order to pass arguments, return results,
1122 -- and store values of this type.
1123 data PrimRep
1124 = VoidRep
1125 | PtrRep
1126 | IntRep -- ^ Signed, word-sized value
1127 | WordRep -- ^ Unsigned, word-sized value
1128 | Int64Rep -- ^ Signed, 64 bit value (with 32-bit words only)
1129 | Word64Rep -- ^ Unsigned, 64 bit value (with 32-bit words only)
1130 | AddrRep -- ^ A pointer, but /not/ to a Haskell value (use 'PtrRep')
1131 | FloatRep
1132 | DoubleRep
1133 | VecRep Int PrimElemRep -- ^ A vector
1134 deriving( Eq, Show )
1135
1136 data PrimElemRep
1137 = Int8ElemRep
1138 | Int16ElemRep
1139 | Int32ElemRep
1140 | Int64ElemRep
1141 | Word8ElemRep
1142 | Word16ElemRep
1143 | Word32ElemRep
1144 | Word64ElemRep
1145 | FloatElemRep
1146 | DoubleElemRep
1147 deriving( Eq, Show )
1148
1149 instance Outputable PrimRep where
1150 ppr r = text (show r)
1151
1152 instance Outputable PrimElemRep where
1153 ppr r = text (show r)
1154
1155 isVoidRep :: PrimRep -> Bool
1156 isVoidRep VoidRep = True
1157 isVoidRep _other = False
1158
1159 isGcPtrRep :: PrimRep -> Bool
1160 isGcPtrRep PtrRep = True
1161 isGcPtrRep _ = False
1162
1163 -- | Find the size of a 'PrimRep', in words
1164 primRepSizeW :: DynFlags -> PrimRep -> Int
1165 primRepSizeW _ IntRep = 1
1166 primRepSizeW _ WordRep = 1
1167 primRepSizeW dflags Int64Rep = wORD64_SIZE `quot` wORD_SIZE dflags
1168 primRepSizeW dflags Word64Rep = wORD64_SIZE `quot` wORD_SIZE dflags
1169 primRepSizeW _ FloatRep = 1 -- NB. might not take a full word
1170 primRepSizeW dflags DoubleRep = dOUBLE_SIZE dflags `quot` wORD_SIZE dflags
1171 primRepSizeW _ AddrRep = 1
1172 primRepSizeW _ PtrRep = 1
1173 primRepSizeW _ VoidRep = 0
1174 primRepSizeW dflags (VecRep len rep) = len * primElemRepSizeB rep `quot` wORD_SIZE dflags
1175
1176 primElemRepSizeB :: PrimElemRep -> Int
1177 primElemRepSizeB Int8ElemRep = 1
1178 primElemRepSizeB Int16ElemRep = 2
1179 primElemRepSizeB Int32ElemRep = 4
1180 primElemRepSizeB Int64ElemRep = 8
1181 primElemRepSizeB Word8ElemRep = 1
1182 primElemRepSizeB Word16ElemRep = 2
1183 primElemRepSizeB Word32ElemRep = 4
1184 primElemRepSizeB Word64ElemRep = 8
1185 primElemRepSizeB FloatElemRep = 4
1186 primElemRepSizeB DoubleElemRep = 8
1187
1188 -- | Return if Rep stands for floating type,
1189 -- returns Nothing for vector types.
1190 primRepIsFloat :: PrimRep -> Maybe Bool
1191 primRepIsFloat FloatRep = Just True
1192 primRepIsFloat DoubleRep = Just True
1193 primRepIsFloat (VecRep _ _) = Nothing
1194 primRepIsFloat _ = Just False
1195
1196
1197 {-
1198 ************************************************************************
1199 * *
1200 Field labels
1201 * *
1202 ************************************************************************
1203 -}
1204
1205 -- | The labels for the fields of this particular 'TyCon'
1206 tyConFieldLabels :: TyCon -> [FieldLabel]
1207 tyConFieldLabels tc = dFsEnvElts $ tyConFieldLabelEnv tc
1208
1209 -- | The labels for the fields of this particular 'TyCon'
1210 tyConFieldLabelEnv :: TyCon -> FieldLabelEnv
1211 tyConFieldLabelEnv tc
1212 | isAlgTyCon tc = algTcFields tc
1213 | otherwise = emptyDFsEnv
1214
1215
1216 -- | Make a map from strings to FieldLabels from all the data
1217 -- constructors of this algebraic tycon
1218 fieldsOfAlgTcRhs :: AlgTyConRhs -> FieldLabelEnv
1219 fieldsOfAlgTcRhs rhs = mkDFsEnv [ (flLabel fl, fl)
1220 | fl <- dataConsFields (visibleDataCons rhs) ]
1221 where
1222 -- Duplicates in this list will be removed by 'mkFsEnv'
1223 dataConsFields dcs = concatMap dataConFieldLabels dcs
1224
1225
1226 {-
1227 ************************************************************************
1228 * *
1229 \subsection{TyCon Construction}
1230 * *
1231 ************************************************************************
1232
1233 Note: the TyCon constructors all take a Kind as one argument, even though
1234 they could, in principle, work out their Kind from their other arguments.
1235 But to do so they need functions from Types, and that makes a nasty
1236 module mutual-recursion. And they aren't called from many places.
1237 So we compromise, and move their Kind calculation to the call site.
1238 -}
1239
1240 -- | Given the name of the function type constructor and it's kind, create the
1241 -- corresponding 'TyCon'. It is reccomended to use 'TyCoRep.funTyCon' if you want
1242 -- this functionality
1243 mkFunTyCon :: Name -> [TyBinder] -> Name -> TyCon
1244 mkFunTyCon name binders rep_nm
1245 = FunTyCon {
1246 tyConUnique = nameUnique name,
1247 tyConName = name,
1248 tyConBinders = binders,
1249 tyConResKind = liftedTypeKind,
1250 tyConKind = mkPiTys binders liftedTypeKind,
1251 tyConArity = 2,
1252 tcRepName = rep_nm
1253 }
1254
1255 -- | This is the making of an algebraic 'TyCon'. Notably, you have to
1256 -- pass in the generic (in the -XGenerics sense) information about the
1257 -- type constructor - you can get hold of it easily (see Generics
1258 -- module)
1259 mkAlgTyCon :: Name
1260 -> [TyBinder] -- ^ Binders of the resulting 'TyCon'
1261 -> Kind -- ^ Result kind
1262 -> [TyVar] -- ^ 'TyVar's scoped over: see 'tyConTyVars'.
1263 -- Arity is inferred from the length of this
1264 -- list
1265 -> [Role] -- ^ The roles for each TyVar
1266 -> Maybe CType -- ^ The C type this type corresponds to
1267 -- when using the CAPI FFI
1268 -> [PredType] -- ^ Stupid theta: see 'algTcStupidTheta'
1269 -> AlgTyConRhs -- ^ Information about data constructors
1270 -> AlgTyConFlav -- ^ What flavour is it?
1271 -- (e.g. vanilla, type family)
1272 -> RecFlag -- ^ Is the 'TyCon' recursive?
1273 -> Bool -- ^ Was the 'TyCon' declared with GADT syntax?
1274 -> TyCon
1275 mkAlgTyCon name binders res_kind tyvars roles cType stupid rhs parent is_rec gadt_syn
1276 = AlgTyCon {
1277 tyConName = name,
1278 tyConUnique = nameUnique name,
1279 tyConBinders = binders,
1280 tyConResKind = res_kind,
1281 tyConKind = mkPiTys binders res_kind,
1282 tyConArity = length tyvars,
1283 tyConTyVars = tyvars,
1284 tcRoles = roles,
1285 tyConCType = cType,
1286 algTcStupidTheta = stupid,
1287 algTcRhs = rhs,
1288 algTcFields = fieldsOfAlgTcRhs rhs,
1289 algTcParent = ASSERT2( okParent name parent, ppr name $$ ppr parent ) parent,
1290 algTcRec = is_rec,
1291 algTcGadtSyntax = gadt_syn
1292 }
1293
1294 -- | Simpler specialization of 'mkAlgTyCon' for classes
1295 mkClassTyCon :: Name -> [TyBinder]
1296 -> [TyVar] -> [Role] -> AlgTyConRhs -> Class
1297 -> RecFlag -> Name -> TyCon
1298 mkClassTyCon name binders tyvars roles rhs clas is_rec tc_rep_name
1299 = mkAlgTyCon name binders constraintKind tyvars roles Nothing [] rhs
1300 (ClassTyCon clas tc_rep_name)
1301 is_rec False
1302
1303 mkTupleTyCon :: Name
1304 -> [TyBinder]
1305 -> Kind -- ^ Result kind of the 'TyCon'
1306 -> Arity -- ^ Arity of the tuple
1307 -> [TyVar] -- ^ 'TyVar's scoped over: see 'tyConTyVars'
1308 -> DataCon
1309 -> TupleSort -- ^ Whether the tuple is boxed or unboxed
1310 -> AlgTyConFlav
1311 -> TyCon
1312 mkTupleTyCon name binders res_kind arity tyvars con sort parent
1313 = AlgTyCon {
1314 tyConName = name,
1315 tyConUnique = nameUnique name,
1316 tyConBinders = binders,
1317 tyConResKind = res_kind,
1318 tyConKind = mkPiTys binders res_kind,
1319 tyConArity = arity,
1320 tyConTyVars = tyvars,
1321 tcRoles = replicate arity Representational,
1322 tyConCType = Nothing,
1323 algTcStupidTheta = [],
1324 algTcRhs = TupleTyCon { data_con = con,
1325 tup_sort = sort },
1326 algTcFields = emptyDFsEnv,
1327 algTcParent = parent,
1328 algTcRec = NonRecursive,
1329 algTcGadtSyntax = False
1330 }
1331
1332 -- | Makes a tycon suitable for use during type-checking.
1333 -- The only real need for this is for printing error messages during
1334 -- a recursive type/class type-checking knot. It has a kind because
1335 -- TcErrors sometimes calls typeKind.
1336 -- See also Note [Kind checking recursive type and class declarations]
1337 -- in TcTyClsDecls.
1338 mkTcTyCon :: Name -> [TyVar]
1339 -> [TyBinder] -> Kind -- ^ /result/ kind only
1340 -> Bool -- ^ Can this be unsaturated?
1341 -> [TyVar] -- ^ Scoped type variables, see Note [TcTyCon]
1342 -> TyCon
1343 mkTcTyCon name tvs binders res_kind unsat scoped_tvs
1344 = TcTyCon { tyConUnique = getUnique name
1345 , tyConName = name
1346 , tyConTyVars = tvs
1347 , tyConBinders = binders
1348 , tyConResKind = res_kind
1349 , tyConKind = mkPiTys binders res_kind
1350 , tyConUnsat = unsat
1351 , tyConArity = length binders
1352 , tcTyConScopedTyVars = scoped_tvs }
1353
1354 -- | Create an unlifted primitive 'TyCon', such as @Int#@
1355 mkPrimTyCon :: Name -> [TyBinder]
1356 -> Kind -- ^ /result/ kind
1357 -> [Role] -> TyCon
1358 mkPrimTyCon name binders res_kind roles
1359 = mkPrimTyCon' name binders res_kind roles True (Just $ mkPrelTyConRepName name)
1360
1361 -- | Kind constructors
1362 mkKindTyCon :: Name -> [TyBinder]
1363 -> Kind -- ^ /result/ kind
1364 -> [Role] -> Name -> TyCon
1365 mkKindTyCon name binders res_kind roles rep_nm
1366 = tc
1367 where
1368 tc = mkPrimTyCon' name binders res_kind roles False (Just rep_nm)
1369
1370 -- | Create a lifted primitive 'TyCon' such as @RealWorld@
1371 mkLiftedPrimTyCon :: Name -> [TyBinder]
1372 -> Kind -- ^ /result/ kind
1373 -> [Role] -> TyCon
1374 mkLiftedPrimTyCon name binders res_kind roles
1375 = mkPrimTyCon' name binders res_kind roles False (Just rep_nm)
1376 where rep_nm = mkPrelTyConRepName name
1377
1378 mkPrimTyCon' :: Name -> [TyBinder]
1379 -> Kind -- ^ /result/ kind
1380 -> [Role]
1381 -> Bool -> Maybe TyConRepName -> TyCon
1382 mkPrimTyCon' name binders res_kind roles is_unlifted rep_nm
1383 = PrimTyCon {
1384 tyConName = name,
1385 tyConUnique = nameUnique name,
1386 tyConBinders = binders,
1387 tyConResKind = res_kind,
1388 tyConKind = mkPiTys binders res_kind,
1389 tyConArity = length roles,
1390 tcRoles = roles,
1391 isUnlifted = is_unlifted,
1392 primRepName = rep_nm
1393 }
1394
1395 -- | Create a type synonym 'TyCon'
1396 mkSynonymTyCon :: Name -> [TyBinder] -> Kind -- ^ /result/ kind
1397 -> [TyVar] -> [Role] -> Type -> TyCon
1398 mkSynonymTyCon name binders res_kind tyvars roles rhs
1399 = SynonymTyCon {
1400 tyConName = name,
1401 tyConUnique = nameUnique name,
1402 tyConBinders = binders,
1403 tyConResKind = res_kind,
1404 tyConKind = mkPiTys binders res_kind,
1405 tyConArity = length tyvars,
1406 tyConTyVars = tyvars,
1407 tcRoles = roles,
1408 synTcRhs = rhs
1409 }
1410
1411 -- | Create a type family 'TyCon'
1412 mkFamilyTyCon :: Name -> [TyBinder] -> Kind -- ^ /result/ kind
1413 -> [TyVar] -> Maybe Name -> FamTyConFlav
1414 -> Maybe Class -> Injectivity -> TyCon
1415 mkFamilyTyCon name binders res_kind tyvars resVar flav parent inj
1416 = FamilyTyCon
1417 { tyConUnique = nameUnique name
1418 , tyConName = name
1419 , tyConBinders = binders
1420 , tyConResKind = res_kind
1421 , tyConKind = mkPiTys binders res_kind
1422 , tyConArity = length tyvars
1423 , tyConTyVars = tyvars
1424 , famTcResVar = resVar
1425 , famTcFlav = flav
1426 , famTcParent = parent
1427 , famTcInj = inj
1428 }
1429
1430
1431 -- | Create a promoted data constructor 'TyCon'
1432 -- Somewhat dodgily, we give it the same Name
1433 -- as the data constructor itself; when we pretty-print
1434 -- the TyCon we add a quote; see the Outputable TyCon instance
1435 mkPromotedDataCon :: DataCon -> Name -> TyConRepName -> [TyBinder] -> Kind -> [Role]
1436 -> RuntimeRepInfo -> TyCon
1437 mkPromotedDataCon con name rep_name binders res_kind roles rep_info
1438 = PromotedDataCon {
1439 tyConUnique = nameUnique name,
1440 tyConName = name,
1441 tyConArity = arity,
1442 tcRoles = roles,
1443 tyConBinders = binders,
1444 tyConResKind = res_kind,
1445 tyConKind = mkPiTys binders res_kind,
1446 dataCon = con,
1447 tcRepName = rep_name,
1448 promDcRepInfo = rep_info
1449 }
1450 where
1451 arity = length roles
1452
1453 isFunTyCon :: TyCon -> Bool
1454 isFunTyCon (FunTyCon {}) = True
1455 isFunTyCon _ = False
1456
1457 -- | Test if the 'TyCon' is algebraic but abstract (invisible data constructors)
1458 isAbstractTyCon :: TyCon -> Bool
1459 isAbstractTyCon (AlgTyCon { algTcRhs = AbstractTyCon {} }) = True
1460 isAbstractTyCon _ = False
1461
1462 -- | Make an fake, abstract 'TyCon' from an existing one.
1463 -- Used when recovering from errors
1464 makeTyConAbstract :: TyCon -> TyCon
1465 makeTyConAbstract tc
1466 = mkTcTyCon (tyConName tc) (tyConTyVars tc)
1467 (tyConBinders tc) (tyConResKind tc)
1468 (mightBeUnsaturatedTyCon tc) [{- no scoped vars -}]
1469
1470 -- | Does this 'TyCon' represent something that cannot be defined in Haskell?
1471 isPrimTyCon :: TyCon -> Bool
1472 isPrimTyCon (PrimTyCon {}) = True
1473 isPrimTyCon _ = False
1474
1475 -- | Is this 'TyCon' unlifted (i.e. cannot contain bottom)? Note that this can
1476 -- only be true for primitive and unboxed-tuple 'TyCon's
1477 isUnliftedTyCon :: TyCon -> Bool
1478 isUnliftedTyCon (PrimTyCon {isUnlifted = is_unlifted})
1479 = is_unlifted
1480 isUnliftedTyCon (AlgTyCon { algTcRhs = rhs } )
1481 | TupleTyCon { tup_sort = sort } <- rhs
1482 = not (isBoxed (tupleSortBoxity sort))
1483 isUnliftedTyCon _ = False
1484
1485 -- | Returns @True@ if the supplied 'TyCon' resulted from either a
1486 -- @data@ or @newtype@ declaration
1487 isAlgTyCon :: TyCon -> Bool
1488 isAlgTyCon (AlgTyCon {}) = True
1489 isAlgTyCon _ = False
1490
1491 -- | Returns @True@ for vanilla AlgTyCons -- that is, those created
1492 -- with a @data@ or @newtype@ declaration.
1493 isVanillaAlgTyCon :: TyCon -> Bool
1494 isVanillaAlgTyCon (AlgTyCon { algTcParent = VanillaAlgTyCon _ }) = True
1495 isVanillaAlgTyCon _ = False
1496
1497 isDataTyCon :: TyCon -> Bool
1498 -- ^ Returns @True@ for data types that are /definitely/ represented by
1499 -- heap-allocated constructors. These are scrutinised by Core-level
1500 -- @case@ expressions, and they get info tables allocated for them.
1501 --
1502 -- Generally, the function will be true for all @data@ types and false
1503 -- for @newtype@s, unboxed tuples and type family 'TyCon's. But it is
1504 -- not guaranteed to return @True@ in all cases that it could.
1505 --
1506 -- NB: for a data type family, only the /instance/ 'TyCon's
1507 -- get an info table. The family declaration 'TyCon' does not
1508 isDataTyCon (AlgTyCon {algTcRhs = rhs})
1509 = case rhs of
1510 TupleTyCon { tup_sort = sort }
1511 -> isBoxed (tupleSortBoxity sort)
1512 DataTyCon {} -> True
1513 NewTyCon {} -> False
1514 AbstractTyCon {} -> False -- We don't know, so return False
1515 isDataTyCon _ = False
1516
1517 -- | 'isInjectiveTyCon' is true of 'TyCon's for which this property holds
1518 -- (where X is the role passed in):
1519 -- If (T a1 b1 c1) ~X (T a2 b2 c2), then (a1 ~X1 a2), (b1 ~X2 b2), and (c1 ~X3 c2)
1520 -- (where X1, X2, and X3, are the roles given by tyConRolesX tc X)
1521 -- See also Note [Decomposing equality] in TcCanonical
1522 isInjectiveTyCon :: TyCon -> Role -> Bool
1523 isInjectiveTyCon _ Phantom = False
1524 isInjectiveTyCon (FunTyCon {}) _ = True
1525 isInjectiveTyCon (AlgTyCon {}) Nominal = True
1526 isInjectiveTyCon (AlgTyCon {algTcRhs = rhs}) Representational
1527 = isGenInjAlgRhs rhs
1528 isInjectiveTyCon (SynonymTyCon {}) _ = False
1529 isInjectiveTyCon (FamilyTyCon { famTcFlav = DataFamilyTyCon _ })
1530 Nominal = True
1531 isInjectiveTyCon (FamilyTyCon { famTcInj = Injective inj }) _ = and inj
1532 isInjectiveTyCon (FamilyTyCon {}) _ = False
1533 isInjectiveTyCon (PrimTyCon {}) _ = True
1534 isInjectiveTyCon (PromotedDataCon {}) _ = True
1535 isInjectiveTyCon tc@(TcTyCon {}) _
1536 = pprPanic "isInjectiveTyCon sees a TcTyCon" (ppr tc)
1537
1538 -- | 'isGenerativeTyCon' is true of 'TyCon's for which this property holds
1539 -- (where X is the role passed in):
1540 -- If (T tys ~X t), then (t's head ~X T).
1541 -- See also Note [Decomposing equality] in TcCanonical
1542 isGenerativeTyCon :: TyCon -> Role -> Bool
1543 isGenerativeTyCon (FamilyTyCon { famTcFlav = DataFamilyTyCon _ }) Nominal = True
1544 isGenerativeTyCon (FamilyTyCon {}) _ = False
1545 -- in all other cases, injectivity implies generativitiy
1546 isGenerativeTyCon tc r = isInjectiveTyCon tc r
1547
1548 -- | Is this an 'AlgTyConRhs' of a 'TyCon' that is generative and injective
1549 -- with respect to representational equality?
1550 isGenInjAlgRhs :: AlgTyConRhs -> Bool
1551 isGenInjAlgRhs (TupleTyCon {}) = True
1552 isGenInjAlgRhs (DataTyCon {}) = True
1553 isGenInjAlgRhs (AbstractTyCon distinct) = distinct
1554 isGenInjAlgRhs (NewTyCon {}) = False
1555
1556 -- | Is this 'TyCon' that for a @newtype@
1557 isNewTyCon :: TyCon -> Bool
1558 isNewTyCon (AlgTyCon {algTcRhs = NewTyCon {}}) = True
1559 isNewTyCon _ = False
1560
1561 -- | Take a 'TyCon' apart into the 'TyVar's it scopes over, the 'Type' it expands
1562 -- into, and (possibly) a coercion from the representation type to the @newtype@.
1563 -- Returns @Nothing@ if this is not possible.
1564 unwrapNewTyCon_maybe :: TyCon -> Maybe ([TyVar], Type, CoAxiom Unbranched)
1565 unwrapNewTyCon_maybe (AlgTyCon { tyConTyVars = tvs,
1566 algTcRhs = NewTyCon { nt_co = co,
1567 nt_rhs = rhs }})
1568 = Just (tvs, rhs, co)
1569 unwrapNewTyCon_maybe _ = Nothing
1570
1571 unwrapNewTyConEtad_maybe :: TyCon -> Maybe ([TyVar], Type, CoAxiom Unbranched)
1572 unwrapNewTyConEtad_maybe (AlgTyCon { algTcRhs = NewTyCon { nt_co = co,
1573 nt_etad_rhs = (tvs,rhs) }})
1574 = Just (tvs, rhs, co)
1575 unwrapNewTyConEtad_maybe _ = Nothing
1576
1577 isProductTyCon :: TyCon -> Bool
1578 -- True of datatypes or newtypes that have
1579 -- one, non-existential, data constructor
1580 -- See Note [Product types]
1581 isProductTyCon tc@(AlgTyCon {})
1582 = case algTcRhs tc of
1583 TupleTyCon {} -> True
1584 DataTyCon{ data_cons = [data_con] }
1585 -> null (dataConExTyVars data_con)
1586 NewTyCon {} -> True
1587 _ -> False
1588 isProductTyCon _ = False
1589
1590 isDataProductTyCon_maybe :: TyCon -> Maybe DataCon
1591 -- True of datatypes (not newtypes) with
1592 -- one, vanilla, data constructor
1593 -- See Note [Product types]
1594 isDataProductTyCon_maybe (AlgTyCon { algTcRhs = rhs })
1595 = case rhs of
1596 DataTyCon { data_cons = [con] }
1597 | null (dataConExTyVars con) -- non-existential
1598 -> Just con
1599 TupleTyCon { data_con = con }
1600 -> Just con
1601 _ -> Nothing
1602 isDataProductTyCon_maybe _ = Nothing
1603
1604 {- Note [Product types]
1605 ~~~~~~~~~~~~~~~~~~~~~~~
1606 A product type is
1607 * A data type (not a newtype)
1608 * With one, boxed data constructor
1609 * That binds no existential type variables
1610
1611 The main point is that product types are amenable to unboxing for
1612 * Strict function calls; we can transform
1613 f (D a b) = e
1614 to
1615 fw a b = e
1616 via the worker/wrapper transformation. (Question: couldn't this
1617 work for existentials too?)
1618
1619 * CPR for function results; we can transform
1620 f x y = let ... in D a b
1621 to
1622 fw x y = let ... in (# a, b #)
1623
1624 Note that the data constructor /can/ have evidence arguments: equality
1625 constraints, type classes etc. So it can be GADT. These evidence
1626 arguments are simply value arguments, and should not get in the way.
1627 -}
1628
1629
1630 -- | Is this a 'TyCon' representing a regular H98 type synonym (@type@)?
1631 isTypeSynonymTyCon :: TyCon -> Bool
1632 isTypeSynonymTyCon (SynonymTyCon {}) = True
1633 isTypeSynonymTyCon _ = False
1634
1635
1636 -- As for newtypes, it is in some contexts important to distinguish between
1637 -- closed synonyms and synonym families, as synonym families have no unique
1638 -- right hand side to which a synonym family application can expand.
1639 --
1640
1641 -- | True iff we can decompose (T a b c) into ((T a b) c)
1642 -- I.e. is it injective and generative w.r.t nominal equality?
1643 -- That is, if (T a b) ~N d e f, is it always the case that
1644 -- (T ~N d), (a ~N e) and (b ~N f)?
1645 -- Specifically NOT true of synonyms (open and otherwise)
1646 --
1647 -- It'd be unusual to call mightBeUnsaturatedTyCon on a regular H98
1648 -- type synonym, because you should probably have expanded it first
1649 -- But regardless, it's not decomposable
1650 mightBeUnsaturatedTyCon :: TyCon -> Bool
1651 mightBeUnsaturatedTyCon (SynonymTyCon {}) = False
1652 mightBeUnsaturatedTyCon (FamilyTyCon { famTcFlav = flav}) = isDataFamFlav flav
1653 mightBeUnsaturatedTyCon (TcTyCon { tyConUnsat = unsat }) = unsat
1654 mightBeUnsaturatedTyCon _other = True
1655
1656 -- | Is this an algebraic 'TyCon' declared with the GADT syntax?
1657 isGadtSyntaxTyCon :: TyCon -> Bool
1658 isGadtSyntaxTyCon (AlgTyCon { algTcGadtSyntax = res }) = res
1659 isGadtSyntaxTyCon _ = False
1660
1661 -- | Is this an algebraic 'TyCon' which is just an enumeration of values?
1662 isEnumerationTyCon :: TyCon -> Bool
1663 -- See Note [Enumeration types] in TyCon
1664 isEnumerationTyCon (AlgTyCon { tyConArity = arity, algTcRhs = rhs })
1665 = case rhs of
1666 DataTyCon { is_enum = res } -> res
1667 TupleTyCon {} -> arity == 0
1668 _ -> False
1669 isEnumerationTyCon _ = False
1670
1671 -- | Is this a 'TyCon', synonym or otherwise, that defines a family?
1672 isFamilyTyCon :: TyCon -> Bool
1673 isFamilyTyCon (FamilyTyCon {}) = True
1674 isFamilyTyCon _ = False
1675
1676 -- | Is this a 'TyCon', synonym or otherwise, that defines a family with
1677 -- instances?
1678 isOpenFamilyTyCon :: TyCon -> Bool
1679 isOpenFamilyTyCon (FamilyTyCon {famTcFlav = flav })
1680 | OpenSynFamilyTyCon <- flav = True
1681 | DataFamilyTyCon {} <- flav = True
1682 isOpenFamilyTyCon _ = False
1683
1684 -- | Is this a synonym 'TyCon' that can have may have further instances appear?
1685 isTypeFamilyTyCon :: TyCon -> Bool
1686 isTypeFamilyTyCon (FamilyTyCon { famTcFlav = flav }) = not (isDataFamFlav flav)
1687 isTypeFamilyTyCon _ = False
1688
1689 -- | Is this a synonym 'TyCon' that can have may have further instances appear?
1690 isDataFamilyTyCon :: TyCon -> Bool
1691 isDataFamilyTyCon (FamilyTyCon { famTcFlav = flav }) = isDataFamFlav flav
1692 isDataFamilyTyCon _ = False
1693
1694 -- | Is this an open type family TyCon?
1695 isOpenTypeFamilyTyCon :: TyCon -> Bool
1696 isOpenTypeFamilyTyCon (FamilyTyCon {famTcFlav = OpenSynFamilyTyCon }) = True
1697 isOpenTypeFamilyTyCon _ = False
1698
1699 -- | Is this a non-empty closed type family? Returns 'Nothing' for
1700 -- abstract or empty closed families.
1701 isClosedSynFamilyTyConWithAxiom_maybe :: TyCon -> Maybe (CoAxiom Branched)
1702 isClosedSynFamilyTyConWithAxiom_maybe
1703 (FamilyTyCon {famTcFlav = ClosedSynFamilyTyCon mb}) = mb
1704 isClosedSynFamilyTyConWithAxiom_maybe _ = Nothing
1705
1706 -- | Try to read the injectivity information from a FamilyTyCon.
1707 -- For every other TyCon this function panics.
1708 familyTyConInjectivityInfo :: TyCon -> Injectivity
1709 familyTyConInjectivityInfo (FamilyTyCon { famTcInj = inj }) = inj
1710 familyTyConInjectivityInfo _ = panic "familyTyConInjectivityInfo"
1711
1712 isBuiltInSynFamTyCon_maybe :: TyCon -> Maybe BuiltInSynFamily
1713 isBuiltInSynFamTyCon_maybe
1714 (FamilyTyCon {famTcFlav = BuiltInSynFamTyCon ops }) = Just ops
1715 isBuiltInSynFamTyCon_maybe _ = Nothing
1716
1717 isDataFamFlav :: FamTyConFlav -> Bool
1718 isDataFamFlav (DataFamilyTyCon {}) = True -- Data family
1719 isDataFamFlav _ = False -- Type synonym family
1720
1721 -- | Are we able to extract information 'TyVar' to class argument list
1722 -- mapping from a given 'TyCon'?
1723 isTyConAssoc :: TyCon -> Bool
1724 isTyConAssoc tc = isJust (tyConAssoc_maybe tc)
1725
1726 tyConAssoc_maybe :: TyCon -> Maybe Class
1727 tyConAssoc_maybe (FamilyTyCon { famTcParent = mb_cls }) = mb_cls
1728 tyConAssoc_maybe _ = Nothing
1729
1730 -- The unit tycon didn't used to be classed as a tuple tycon
1731 -- but I thought that was silly so I've undone it
1732 -- If it can't be for some reason, it should be a AlgTyCon
1733 isTupleTyCon :: TyCon -> Bool
1734 -- ^ Does this 'TyCon' represent a tuple?
1735 --
1736 -- NB: when compiling @Data.Tuple@, the tycons won't reply @True@ to
1737 -- 'isTupleTyCon', because they are built as 'AlgTyCons'. However they
1738 -- get spat into the interface file as tuple tycons, so I don't think
1739 -- it matters.
1740 isTupleTyCon (AlgTyCon { algTcRhs = TupleTyCon {} }) = True
1741 isTupleTyCon _ = False
1742
1743 tyConTuple_maybe :: TyCon -> Maybe TupleSort
1744 tyConTuple_maybe (AlgTyCon { algTcRhs = rhs })
1745 | TupleTyCon { tup_sort = sort} <- rhs = Just sort
1746 tyConTuple_maybe _ = Nothing
1747
1748 -- | Is this the 'TyCon' for an unboxed tuple?
1749 isUnboxedTupleTyCon :: TyCon -> Bool
1750 isUnboxedTupleTyCon (AlgTyCon { algTcRhs = rhs })
1751 | TupleTyCon { tup_sort = sort } <- rhs
1752 = not (isBoxed (tupleSortBoxity sort))
1753 isUnboxedTupleTyCon _ = False
1754
1755 -- | Is this the 'TyCon' for a boxed tuple?
1756 isBoxedTupleTyCon :: TyCon -> Bool
1757 isBoxedTupleTyCon (AlgTyCon { algTcRhs = rhs })
1758 | TupleTyCon { tup_sort = sort } <- rhs
1759 = isBoxed (tupleSortBoxity sort)
1760 isBoxedTupleTyCon _ = False
1761
1762 -- | Is this a recursive 'TyCon'?
1763 isRecursiveTyCon :: TyCon -> Bool
1764 isRecursiveTyCon (AlgTyCon {algTcRec = Recursive}) = True
1765 isRecursiveTyCon _ = False
1766
1767 -- | Is this a PromotedDataCon?
1768 isPromotedDataCon :: TyCon -> Bool
1769 isPromotedDataCon (PromotedDataCon {}) = True
1770 isPromotedDataCon _ = False
1771
1772 -- | Retrieves the promoted DataCon if this is a PromotedDataCon;
1773 isPromotedDataCon_maybe :: TyCon -> Maybe DataCon
1774 isPromotedDataCon_maybe (PromotedDataCon { dataCon = dc }) = Just dc
1775 isPromotedDataCon_maybe _ = Nothing
1776
1777 -- | Is this tycon really meant for use at the kind level? That is,
1778 -- should it be permitted without -XDataKinds?
1779 isKindTyCon :: TyCon -> Bool
1780 isKindTyCon tc = getUnique tc `elementOfUniqSet` kindTyConKeys
1781
1782 -- | These TyCons should be allowed at the kind level, even without
1783 -- -XDataKinds.
1784 kindTyConKeys :: UniqSet Unique
1785 kindTyConKeys = unionManyUniqSets
1786 ( mkUniqSet [ liftedTypeKindTyConKey, starKindTyConKey, unicodeStarKindTyConKey
1787 , constraintKindTyConKey, tYPETyConKey ]
1788 : map (mkUniqSet . tycon_with_datacons) [ runtimeRepTyCon
1789 , vecCountTyCon, vecElemTyCon ] )
1790 where
1791 tycon_with_datacons tc = getUnique tc : map getUnique (tyConDataCons tc)
1792
1793 isLiftedTypeKindTyConName :: Name -> Bool
1794 isLiftedTypeKindTyConName
1795 = (`hasKey` liftedTypeKindTyConKey) <||>
1796 (`hasKey` starKindTyConKey) <||>
1797 (`hasKey` unicodeStarKindTyConKey)
1798
1799 -- | Identifies implicit tycons that, in particular, do not go into interface
1800 -- files (because they are implicitly reconstructed when the interface is
1801 -- read).
1802 --
1803 -- Note that:
1804 --
1805 -- * Associated families are implicit, as they are re-constructed from
1806 -- the class declaration in which they reside, and
1807 --
1808 -- * Family instances are /not/ implicit as they represent the instance body
1809 -- (similar to a @dfun@ does that for a class instance).
1810 --
1811 -- * Tuples are implicit iff they have a wired-in name
1812 -- (namely: boxed and unboxed tupeles are wired-in and implicit,
1813 -- but constraint tuples are not)
1814 isImplicitTyCon :: TyCon -> Bool
1815 isImplicitTyCon (FunTyCon {}) = True
1816 isImplicitTyCon (PrimTyCon {}) = True
1817 isImplicitTyCon (PromotedDataCon {}) = True
1818 isImplicitTyCon (AlgTyCon { algTcRhs = rhs, tyConName = name })
1819 | TupleTyCon {} <- rhs = isWiredInName name
1820 | otherwise = False
1821 isImplicitTyCon (FamilyTyCon { famTcParent = parent }) = isJust parent
1822 isImplicitTyCon (SynonymTyCon {}) = False
1823 isImplicitTyCon tc@(TcTyCon {})
1824 = pprPanic "isImplicitTyCon sees a TcTyCon" (ppr tc)
1825
1826 tyConCType_maybe :: TyCon -> Maybe CType
1827 tyConCType_maybe tc@(AlgTyCon {}) = tyConCType tc
1828 tyConCType_maybe _ = Nothing
1829
1830 -- | Is this a TcTyCon? (That is, one only used during type-checking?)
1831 isTcTyCon :: TyCon -> Bool
1832 isTcTyCon (TcTyCon {}) = True
1833 isTcTyCon _ = False
1834
1835 {-
1836 -----------------------------------------------
1837 -- Expand type-constructor applications
1838 -----------------------------------------------
1839 -}
1840
1841 expandSynTyCon_maybe
1842 :: TyCon
1843 -> [tyco] -- ^ Arguments to 'TyCon'
1844 -> Maybe ([(TyVar,tyco)],
1845 Type,
1846 [tyco]) -- ^ Returns a 'TyVar' substitution, the body
1847 -- type of the synonym (not yet substituted)
1848 -- and any arguments remaining from the
1849 -- application
1850
1851 -- ^ Expand a type synonym application, if any
1852 expandSynTyCon_maybe tc tys
1853 | SynonymTyCon { tyConTyVars = tvs, synTcRhs = rhs, tyConArity = arity } <- tc
1854 = case arity `compare` length tys of
1855 LT -> Just (tvs `zip` tys, rhs, drop arity tys)
1856 EQ -> Just (tvs `zip` tys, rhs, [])
1857 GT -> Nothing
1858 | otherwise
1859 = Nothing
1860
1861 ----------------
1862
1863 -- | Check if the tycon actually refers to a proper `data` or `newtype`
1864 -- with user defined constructors rather than one from a class or other
1865 -- construction.
1866 isTyConWithSrcDataCons :: TyCon -> Bool
1867 isTyConWithSrcDataCons (AlgTyCon { algTcRhs = rhs, algTcParent = parent }) =
1868 case rhs of
1869 DataTyCon {} -> isSrcParent
1870 NewTyCon {} -> isSrcParent
1871 TupleTyCon {} -> isSrcParent
1872 _ -> False
1873 where
1874 isSrcParent = isNoParent parent
1875 isTyConWithSrcDataCons _ = False
1876
1877
1878 -- | As 'tyConDataCons_maybe', but returns the empty list of constructors if no
1879 -- constructors could be found
1880 tyConDataCons :: TyCon -> [DataCon]
1881 -- It's convenient for tyConDataCons to return the
1882 -- empty list for type synonyms etc
1883 tyConDataCons tycon = tyConDataCons_maybe tycon `orElse` []
1884
1885 -- | Determine the 'DataCon's originating from the given 'TyCon', if the 'TyCon'
1886 -- is the sort that can have any constructors (note: this does not include
1887 -- abstract algebraic types)
1888 tyConDataCons_maybe :: TyCon -> Maybe [DataCon]
1889 tyConDataCons_maybe (AlgTyCon {algTcRhs = rhs})
1890 = case rhs of
1891 DataTyCon { data_cons = cons } -> Just cons
1892 NewTyCon { data_con = con } -> Just [con]
1893 TupleTyCon { data_con = con } -> Just [con]
1894 _ -> Nothing
1895 tyConDataCons_maybe _ = Nothing
1896
1897 -- | If the given 'TyCon' has a /single/ data constructor, i.e. it is a @data@
1898 -- type with one alternative, a tuple type or a @newtype@ then that constructor
1899 -- is returned. If the 'TyCon' has more than one constructor, or represents a
1900 -- primitive or function type constructor then @Nothing@ is returned. In any
1901 -- other case, the function panics
1902 tyConSingleDataCon_maybe :: TyCon -> Maybe DataCon
1903 tyConSingleDataCon_maybe (AlgTyCon { algTcRhs = rhs })
1904 = case rhs of
1905 DataTyCon { data_cons = [c] } -> Just c
1906 TupleTyCon { data_con = c } -> Just c
1907 NewTyCon { data_con = c } -> Just c
1908 _ -> Nothing
1909 tyConSingleDataCon_maybe _ = Nothing
1910
1911 tyConSingleDataCon :: TyCon -> DataCon
1912 tyConSingleDataCon tc
1913 = case tyConSingleDataCon_maybe tc of
1914 Just c -> c
1915 Nothing -> pprPanic "tyConDataCon" (ppr tc)
1916
1917 tyConSingleAlgDataCon_maybe :: TyCon -> Maybe DataCon
1918 -- Returns (Just con) for single-constructor
1919 -- *algebraic* data types *not* newtypes
1920 tyConSingleAlgDataCon_maybe (AlgTyCon { algTcRhs = rhs })
1921 = case rhs of
1922 DataTyCon { data_cons = [c] } -> Just c
1923 TupleTyCon { data_con = c } -> Just c
1924 _ -> Nothing
1925 tyConSingleAlgDataCon_maybe _ = Nothing
1926
1927 -- | Determine the number of value constructors a 'TyCon' has. Panics if the
1928 -- 'TyCon' is not algebraic or a tuple
1929 tyConFamilySize :: TyCon -> Int
1930 tyConFamilySize tc@(AlgTyCon { algTcRhs = rhs })
1931 = case rhs of
1932 DataTyCon { data_cons = cons } -> length cons
1933 NewTyCon {} -> 1
1934 TupleTyCon {} -> 1
1935 _ -> pprPanic "tyConFamilySize 1" (ppr tc)
1936 tyConFamilySize tc = pprPanic "tyConFamilySize 2" (ppr tc)
1937
1938 -- | Extract an 'AlgTyConRhs' with information about data constructors from an
1939 -- algebraic or tuple 'TyCon'. Panics for any other sort of 'TyCon'
1940 algTyConRhs :: TyCon -> AlgTyConRhs
1941 algTyConRhs (AlgTyCon {algTcRhs = rhs}) = rhs
1942 algTyConRhs other = pprPanic "algTyConRhs" (ppr other)
1943
1944 -- | Extract type variable naming the result of injective type family
1945 tyConFamilyResVar_maybe :: TyCon -> Maybe Name
1946 tyConFamilyResVar_maybe (FamilyTyCon {famTcResVar = res}) = res
1947 tyConFamilyResVar_maybe _ = Nothing
1948
1949 -- | Get the list of roles for the type parameters of a TyCon
1950 tyConRoles :: TyCon -> [Role]
1951 -- See also Note [TyCon Role signatures]
1952 tyConRoles tc
1953 = case tc of
1954 { FunTyCon {} -> const_role Representational
1955 ; AlgTyCon { tcRoles = roles } -> roles
1956 ; SynonymTyCon { tcRoles = roles } -> roles
1957 ; FamilyTyCon {} -> const_role Nominal
1958 ; PrimTyCon { tcRoles = roles } -> roles
1959 ; PromotedDataCon { tcRoles = roles } -> roles
1960 ; TcTyCon {} -> pprPanic "tyConRoles sees a TcTyCon" (ppr tc)
1961 }
1962 where
1963 const_role r = replicate (tyConArity tc) r
1964
1965 -- | Extract the bound type variables and type expansion of a type synonym
1966 -- 'TyCon'. Panics if the 'TyCon' is not a synonym
1967 newTyConRhs :: TyCon -> ([TyVar], Type)
1968 newTyConRhs (AlgTyCon {tyConTyVars = tvs, algTcRhs = NewTyCon { nt_rhs = rhs }})
1969 = (tvs, rhs)
1970 newTyConRhs tycon = pprPanic "newTyConRhs" (ppr tycon)
1971
1972 -- | The number of type parameters that need to be passed to a newtype to
1973 -- resolve it. May be less than in the definition if it can be eta-contracted.
1974 newTyConEtadArity :: TyCon -> Int
1975 newTyConEtadArity (AlgTyCon {algTcRhs = NewTyCon { nt_etad_rhs = tvs_rhs }})
1976 = length (fst tvs_rhs)
1977 newTyConEtadArity tycon = pprPanic "newTyConEtadArity" (ppr tycon)
1978
1979 -- | Extract the bound type variables and type expansion of an eta-contracted
1980 -- type synonym 'TyCon'. Panics if the 'TyCon' is not a synonym
1981 newTyConEtadRhs :: TyCon -> ([TyVar], Type)
1982 newTyConEtadRhs (AlgTyCon {algTcRhs = NewTyCon { nt_etad_rhs = tvs_rhs }}) = tvs_rhs
1983 newTyConEtadRhs tycon = pprPanic "newTyConEtadRhs" (ppr tycon)
1984
1985 -- | Extracts the @newtype@ coercion from such a 'TyCon', which can be used to
1986 -- construct something with the @newtype@s type from its representation type
1987 -- (right hand side). If the supplied 'TyCon' is not a @newtype@, returns
1988 -- @Nothing@
1989 newTyConCo_maybe :: TyCon -> Maybe (CoAxiom Unbranched)
1990 newTyConCo_maybe (AlgTyCon {algTcRhs = NewTyCon { nt_co = co }}) = Just co
1991 newTyConCo_maybe _ = Nothing
1992
1993 newTyConCo :: TyCon -> CoAxiom Unbranched
1994 newTyConCo tc = case newTyConCo_maybe tc of
1995 Just co -> co
1996 Nothing -> pprPanic "newTyConCo" (ppr tc)
1997
1998 -- | Find the \"stupid theta\" of the 'TyCon'. A \"stupid theta\" is the context
1999 -- to the left of an algebraic type declaration, e.g. @Eq a@ in the declaration
2000 -- @data Eq a => T a ...@
2001 tyConStupidTheta :: TyCon -> [PredType]
2002 tyConStupidTheta (AlgTyCon {algTcStupidTheta = stupid}) = stupid
2003 tyConStupidTheta tycon = pprPanic "tyConStupidTheta" (ppr tycon)
2004
2005 -- | Extract the 'TyVar's bound by a vanilla type synonym
2006 -- and the corresponding (unsubstituted) right hand side.
2007 synTyConDefn_maybe :: TyCon -> Maybe ([TyVar], Type)
2008 synTyConDefn_maybe (SynonymTyCon {tyConTyVars = tyvars, synTcRhs = ty})
2009 = Just (tyvars, ty)
2010 synTyConDefn_maybe _ = Nothing
2011
2012 -- | Extract the information pertaining to the right hand side of a type synonym
2013 -- (@type@) declaration.
2014 synTyConRhs_maybe :: TyCon -> Maybe Type
2015 synTyConRhs_maybe (SynonymTyCon {synTcRhs = rhs}) = Just rhs
2016 synTyConRhs_maybe _ = Nothing
2017
2018 -- | Extract the flavour of a type family (with all the extra information that
2019 -- it carries)
2020 famTyConFlav_maybe :: TyCon -> Maybe FamTyConFlav
2021 famTyConFlav_maybe (FamilyTyCon {famTcFlav = flav}) = Just flav
2022 famTyConFlav_maybe _ = Nothing
2023
2024 -- | Is this 'TyCon' that for a class instance?
2025 isClassTyCon :: TyCon -> Bool
2026 isClassTyCon (AlgTyCon {algTcParent = ClassTyCon {}}) = True
2027 isClassTyCon _ = False
2028
2029 -- | If this 'TyCon' is that for a class instance, return the class it is for.
2030 -- Otherwise returns @Nothing@
2031 tyConClass_maybe :: TyCon -> Maybe Class
2032 tyConClass_maybe (AlgTyCon {algTcParent = ClassTyCon clas _}) = Just clas
2033 tyConClass_maybe _ = Nothing
2034
2035 -- | Return the associated types of the 'TyCon', if any
2036 tyConATs :: TyCon -> [TyCon]
2037 tyConATs (AlgTyCon {algTcParent = ClassTyCon clas _}) = classATs clas
2038 tyConATs _ = []
2039
2040 ----------------------------------------------------------------------------
2041 -- | Is this 'TyCon' that for a data family instance?
2042 isFamInstTyCon :: TyCon -> Bool
2043 isFamInstTyCon (AlgTyCon {algTcParent = DataFamInstTyCon {} })
2044 = True
2045 isFamInstTyCon _ = False
2046
2047 tyConFamInstSig_maybe :: TyCon -> Maybe (TyCon, [Type], CoAxiom Unbranched)
2048 tyConFamInstSig_maybe (AlgTyCon {algTcParent = DataFamInstTyCon ax f ts })
2049 = Just (f, ts, ax)
2050 tyConFamInstSig_maybe _ = Nothing
2051
2052 -- | If this 'TyCon' is that of a data family instance, return the family in question
2053 -- and the instance types. Otherwise, return @Nothing@
2054 tyConFamInst_maybe :: TyCon -> Maybe (TyCon, [Type])
2055 tyConFamInst_maybe (AlgTyCon {algTcParent = DataFamInstTyCon _ f ts })
2056 = Just (f, ts)
2057 tyConFamInst_maybe _ = Nothing
2058
2059 -- | If this 'TyCon' is that of a data family instance, return a 'TyCon' which
2060 -- represents a coercion identifying the representation type with the type
2061 -- instance family. Otherwise, return @Nothing@
2062 tyConFamilyCoercion_maybe :: TyCon -> Maybe (CoAxiom Unbranched)
2063 tyConFamilyCoercion_maybe (AlgTyCon {algTcParent = DataFamInstTyCon ax _ _ })
2064 = Just ax
2065 tyConFamilyCoercion_maybe _ = Nothing
2066
2067 -- | Extract any 'RuntimeRepInfo' from this TyCon
2068 tyConRuntimeRepInfo :: TyCon -> RuntimeRepInfo
2069 tyConRuntimeRepInfo (PromotedDataCon { promDcRepInfo = rri }) = rri
2070 tyConRuntimeRepInfo _ = NoRRI
2071 -- could panic in that second case. But Douglas Adams told me not to.
2072
2073 {-
2074 ************************************************************************
2075 * *
2076 \subsection[TyCon-instances]{Instance declarations for @TyCon@}
2077 * *
2078 ************************************************************************
2079
2080 @TyCon@s are compared by comparing their @Unique@s.
2081 -}
2082
2083 instance Eq TyCon where
2084 a == b = getUnique a == getUnique b
2085 a /= b = getUnique a /= getUnique b
2086
2087 instance Ord TyCon where
2088 a <= b = case (a `compare` b) of { LT -> True; EQ -> True; GT -> False }
2089 a < b = case (a `compare` b) of { LT -> True; EQ -> False; GT -> False }
2090 a >= b = case (a `compare` b) of { LT -> False; EQ -> True; GT -> True }
2091 a > b = case (a `compare` b) of { LT -> False; EQ -> False; GT -> True }
2092 compare a b = getUnique a `compare` getUnique b
2093
2094 instance Uniquable TyCon where
2095 getUnique tc = tyConUnique tc
2096
2097 instance Outputable TyCon where
2098 -- At the moment a promoted TyCon has the same Name as its
2099 -- corresponding TyCon, so we add the quote to distinguish it here
2100 ppr tc = pprPromotionQuote tc <> ppr (tyConName tc)
2101
2102 tyConFlavour :: TyCon -> String
2103 tyConFlavour (AlgTyCon { algTcParent = parent, algTcRhs = rhs })
2104 | ClassTyCon _ _ <- parent = "class"
2105 | otherwise = case rhs of
2106 TupleTyCon { tup_sort = sort }
2107 | isBoxed (tupleSortBoxity sort) -> "tuple"
2108 | otherwise -> "unboxed tuple"
2109 DataTyCon {} -> "data type"
2110 NewTyCon {} -> "newtype"
2111 AbstractTyCon {} -> "abstract type"
2112 tyConFlavour (FamilyTyCon { famTcFlav = flav })
2113 | isDataFamFlav flav = "data family"
2114 | otherwise = "type family"
2115 tyConFlavour (SynonymTyCon {}) = "type synonym"
2116 tyConFlavour (FunTyCon {}) = "built-in type"
2117 tyConFlavour (PrimTyCon {}) = "built-in type"
2118 tyConFlavour (PromotedDataCon {}) = "promoted data constructor"
2119 tyConFlavour tc@(TcTyCon {})
2120 = pprPanic "tyConFlavour sees a TcTyCon" (ppr tc)
2121
2122 pprPromotionQuote :: TyCon -> SDoc
2123 -- Promoted data constructors already have a tick in their OccName
2124 pprPromotionQuote tc
2125 = case tc of
2126 PromotedDataCon {} -> char '\'' -- Always quote promoted DataCons in types
2127 _ -> empty
2128
2129 instance NamedThing TyCon where
2130 getName = tyConName
2131
2132 instance Data.Data TyCon where
2133 -- don't traverse?
2134 toConstr _ = abstractConstr "TyCon"
2135 gunfold _ _ = error "gunfold"
2136 dataTypeOf _ = mkNoRepType "TyCon"
2137
2138 instance Binary Injectivity where
2139 put_ bh NotInjective = putByte bh 0
2140 put_ bh (Injective xs) = putByte bh 1 >> put_ bh xs
2141
2142 get bh = do { h <- getByte bh
2143 ; case h of
2144 0 -> return NotInjective
2145 _ -> do { xs <- get bh
2146 ; return (Injective xs) } }
2147
2148 {-
2149 ************************************************************************
2150 * *
2151 Walking over recursive TyCons
2152 * *
2153 ************************************************************************
2154
2155 Note [Expanding newtypes and products]
2156 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2157 When expanding a type to expose a data-type constructor, we need to be
2158 careful about newtypes, lest we fall into an infinite loop. Here are
2159 the key examples:
2160
2161 newtype Id x = MkId x
2162 newtype Fix f = MkFix (f (Fix f))
2163 newtype T = MkT (T -> T)
2164
2165 Type Expansion
2166 --------------------------
2167 T T -> T
2168 Fix Maybe Maybe (Fix Maybe)
2169 Id (Id Int) Int
2170 Fix Id NO NO NO
2171
2172 Notice that
2173 * We can expand T, even though it's recursive.
2174 * We can expand Id (Id Int), even though the Id shows up
2175 twice at the outer level, because Id is non-recursive
2176
2177 So, when expanding, we keep track of when we've seen a recursive
2178 newtype at outermost level; and bale out if we see it again.
2179
2180 We sometimes want to do the same for product types, so that the
2181 strictness analyser doesn't unbox infinitely deeply.
2182
2183 More precisely, we keep a *count* of how many times we've seen it.
2184 This is to account for
2185 data instance T (a,b) = MkT (T a) (T b)
2186 Then (Trac #10482) if we have a type like
2187 T (Int,(Int,(Int,(Int,Int))))
2188 we can still unbox deeply enough during strictness analysis.
2189 We have to treat T as potentially recursive, but it's still
2190 good to be able to unwrap multiple layers.
2191
2192 The function that manages all this is checkRecTc.
2193 -}
2194
2195 data RecTcChecker = RC !Int (NameEnv Int)
2196 -- The upper bound, and the number of times
2197 -- we have encountered each TyCon
2198
2199 initRecTc :: RecTcChecker
2200 -- Intialise with a fixed max bound of 100
2201 -- We should probably have a flag for this
2202 initRecTc = RC 100 emptyNameEnv
2203
2204 checkRecTc :: RecTcChecker -> TyCon -> Maybe RecTcChecker
2205 -- Nothing => Recursion detected
2206 -- Just rec_tcs => Keep going
2207 checkRecTc rc@(RC bound rec_nts) tc
2208 | not (isRecursiveTyCon tc)
2209 = Just rc -- Tuples are a common example here
2210 | otherwise
2211 = case lookupNameEnv rec_nts tc_name of
2212 Just n | n >= bound -> Nothing
2213 | otherwise -> Just (RC bound (extendNameEnv rec_nts tc_name (n+1)))
2214 Nothing -> Just (RC bound (extendNameEnv rec_nts tc_name 1))
2215 where
2216 tc_name = tyConName tc