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