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