Kill varSetElems in tidyFreeTyCoVars
[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 Nothing
1369
1370 mkPrimTyCon' :: Name -> [TyBinder]
1371 -> Kind -- ^ /result/ kind
1372 -> [Role]
1373 -> Bool -> Maybe TyConRepName -> TyCon
1374 mkPrimTyCon' name binders res_kind roles is_unlifted rep_nm
1375 = PrimTyCon {
1376 tyConName = name,
1377 tyConUnique = nameUnique name,
1378 tyConBinders = binders,
1379 tyConResKind = res_kind,
1380 tyConKind = mkForAllTys binders res_kind,
1381 tyConArity = length roles,
1382 tcRoles = roles,
1383 isUnlifted = is_unlifted,
1384 primRepName = rep_nm
1385 }
1386
1387 -- | Create a type synonym 'TyCon'
1388 mkSynonymTyCon :: Name -> [TyBinder] -> Kind -- ^ /result/ kind
1389 -> [TyVar] -> [Role] -> Type -> TyCon
1390 mkSynonymTyCon name binders res_kind tyvars roles rhs
1391 = SynonymTyCon {
1392 tyConName = name,
1393 tyConUnique = nameUnique name,
1394 tyConBinders = binders,
1395 tyConResKind = res_kind,
1396 tyConKind = mkForAllTys binders res_kind,
1397 tyConArity = length tyvars,
1398 tyConTyVars = tyvars,
1399 tcRoles = roles,
1400 synTcRhs = rhs
1401 }
1402
1403 -- | Create a type family 'TyCon'
1404 mkFamilyTyCon :: Name -> [TyBinder] -> Kind -- ^ /result/ kind
1405 -> [TyVar] -> Maybe Name -> FamTyConFlav
1406 -> Maybe Class -> Injectivity -> TyCon
1407 mkFamilyTyCon name binders res_kind tyvars resVar flav parent inj
1408 = FamilyTyCon
1409 { tyConUnique = nameUnique name
1410 , tyConName = name
1411 , tyConBinders = binders
1412 , tyConResKind = res_kind
1413 , tyConKind = mkForAllTys binders res_kind
1414 , tyConArity = length tyvars
1415 , tyConTyVars = tyvars
1416 , famTcResVar = resVar
1417 , famTcFlav = flav
1418 , famTcParent = parent
1419 , famTcInj = inj
1420 }
1421
1422
1423 -- | Create a promoted data constructor 'TyCon'
1424 -- Somewhat dodgily, we give it the same Name
1425 -- as the data constructor itself; when we pretty-print
1426 -- the TyCon we add a quote; see the Outputable TyCon instance
1427 mkPromotedDataCon :: DataCon -> Name -> TyConRepName -> [TyBinder] -> Kind -> [Role]
1428 -> RuntimeRepInfo -> TyCon
1429 mkPromotedDataCon con name rep_name binders res_kind roles rep_info
1430 = PromotedDataCon {
1431 tyConUnique = nameUnique name,
1432 tyConName = name,
1433 tyConArity = arity,
1434 tcRoles = roles,
1435 tyConBinders = binders,
1436 tyConResKind = res_kind,
1437 tyConKind = mkForAllTys binders res_kind,
1438 dataCon = con,
1439 tcRepName = rep_name,
1440 promDcRepInfo = rep_info
1441 }
1442 where
1443 arity = length roles
1444
1445 isFunTyCon :: TyCon -> Bool
1446 isFunTyCon (FunTyCon {}) = True
1447 isFunTyCon _ = False
1448
1449 -- | Test if the 'TyCon' is algebraic but abstract (invisible data constructors)
1450 isAbstractTyCon :: TyCon -> Bool
1451 isAbstractTyCon (AlgTyCon { algTcRhs = AbstractTyCon {} }) = True
1452 isAbstractTyCon _ = False
1453
1454 -- | Make an fake, abstract 'TyCon' from an existing one.
1455 -- Used when recovering from errors
1456 makeTyConAbstract :: TyCon -> TyCon
1457 makeTyConAbstract tc
1458 = mkTcTyCon (tyConName tc) (tyConTyVars tc)
1459 (tyConBinders tc) (tyConResKind tc)
1460 (mightBeUnsaturatedTyCon tc) [{- no scoped vars -}]
1461
1462 -- | Does this 'TyCon' represent something that cannot be defined in Haskell?
1463 isPrimTyCon :: TyCon -> Bool
1464 isPrimTyCon (PrimTyCon {}) = True
1465 isPrimTyCon _ = False
1466
1467 -- | Is this 'TyCon' unlifted (i.e. cannot contain bottom)? Note that this can
1468 -- only be true for primitive and unboxed-tuple 'TyCon's
1469 isUnliftedTyCon :: TyCon -> Bool
1470 isUnliftedTyCon (PrimTyCon {isUnlifted = is_unlifted})
1471 = is_unlifted
1472 isUnliftedTyCon (AlgTyCon { algTcRhs = rhs } )
1473 | TupleTyCon { tup_sort = sort } <- rhs
1474 = not (isBoxed (tupleSortBoxity sort))
1475 isUnliftedTyCon _ = False
1476
1477 -- | Returns @True@ if the supplied 'TyCon' resulted from either a
1478 -- @data@ or @newtype@ declaration
1479 isAlgTyCon :: TyCon -> Bool
1480 isAlgTyCon (AlgTyCon {}) = True
1481 isAlgTyCon _ = False
1482
1483 -- | Returns @True@ for vanilla AlgTyCons -- that is, those created
1484 -- with a @data@ or @newtype@ declaration.
1485 isVanillaAlgTyCon :: TyCon -> Bool
1486 isVanillaAlgTyCon (AlgTyCon { algTcParent = VanillaAlgTyCon _ }) = True
1487 isVanillaAlgTyCon _ = False
1488
1489 isDataTyCon :: TyCon -> Bool
1490 -- ^ Returns @True@ for data types that are /definitely/ represented by
1491 -- heap-allocated constructors. These are scrutinised by Core-level
1492 -- @case@ expressions, and they get info tables allocated for them.
1493 --
1494 -- Generally, the function will be true for all @data@ types and false
1495 -- for @newtype@s, unboxed tuples and type family 'TyCon's. But it is
1496 -- not guaranteed to return @True@ in all cases that it could.
1497 --
1498 -- NB: for a data type family, only the /instance/ 'TyCon's
1499 -- get an info table. The family declaration 'TyCon' does not
1500 isDataTyCon (AlgTyCon {algTcRhs = rhs})
1501 = case rhs of
1502 TupleTyCon { tup_sort = sort }
1503 -> isBoxed (tupleSortBoxity sort)
1504 DataTyCon {} -> True
1505 NewTyCon {} -> False
1506 AbstractTyCon {} -> False -- We don't know, so return False
1507 isDataTyCon _ = False
1508
1509 -- | 'isInjectiveTyCon' is true of 'TyCon's for which this property holds
1510 -- (where X is the role passed in):
1511 -- If (T a1 b1 c1) ~X (T a2 b2 c2), then (a1 ~X1 a2), (b1 ~X2 b2), and (c1 ~X3 c2)
1512 -- (where X1, X2, and X3, are the roles given by tyConRolesX tc X)
1513 -- See also Note [Decomposing equality] in TcCanonical
1514 isInjectiveTyCon :: TyCon -> Role -> Bool
1515 isInjectiveTyCon _ Phantom = False
1516 isInjectiveTyCon (FunTyCon {}) _ = True
1517 isInjectiveTyCon (AlgTyCon {}) Nominal = True
1518 isInjectiveTyCon (AlgTyCon {algTcRhs = rhs}) Representational
1519 = isGenInjAlgRhs rhs
1520 isInjectiveTyCon (SynonymTyCon {}) _ = False
1521 isInjectiveTyCon (FamilyTyCon { famTcFlav = DataFamilyTyCon _ })
1522 Nominal = True
1523 isInjectiveTyCon (FamilyTyCon { famTcInj = Injective inj }) _ = and inj
1524 isInjectiveTyCon (FamilyTyCon {}) _ = False
1525 isInjectiveTyCon (PrimTyCon {}) _ = True
1526 isInjectiveTyCon (PromotedDataCon {}) _ = True
1527 isInjectiveTyCon tc@(TcTyCon {}) _
1528 = pprPanic "isInjectiveTyCon sees a TcTyCon" (ppr tc)
1529
1530 -- | 'isGenerativeTyCon' is true of 'TyCon's for which this property holds
1531 -- (where X is the role passed in):
1532 -- If (T tys ~X t), then (t's head ~X T).
1533 -- See also Note [Decomposing equality] in TcCanonical
1534 isGenerativeTyCon :: TyCon -> Role -> Bool
1535 isGenerativeTyCon (FamilyTyCon { famTcFlav = DataFamilyTyCon _ }) Nominal = True
1536 isGenerativeTyCon (FamilyTyCon {}) _ = False
1537 -- in all other cases, injectivity implies generativitiy
1538 isGenerativeTyCon tc r = isInjectiveTyCon tc r
1539
1540 -- | Is this an 'AlgTyConRhs' of a 'TyCon' that is generative and injective
1541 -- with respect to representational equality?
1542 isGenInjAlgRhs :: AlgTyConRhs -> Bool
1543 isGenInjAlgRhs (TupleTyCon {}) = True
1544 isGenInjAlgRhs (DataTyCon {}) = True
1545 isGenInjAlgRhs (AbstractTyCon distinct) = distinct
1546 isGenInjAlgRhs (NewTyCon {}) = False
1547
1548 -- | Is this 'TyCon' that for a @newtype@
1549 isNewTyCon :: TyCon -> Bool
1550 isNewTyCon (AlgTyCon {algTcRhs = NewTyCon {}}) = True
1551 isNewTyCon _ = False
1552
1553 -- | Take a 'TyCon' apart into the 'TyVar's it scopes over, the 'Type' it expands
1554 -- into, and (possibly) a coercion from the representation type to the @newtype@.
1555 -- Returns @Nothing@ if this is not possible.
1556 unwrapNewTyCon_maybe :: TyCon -> Maybe ([TyVar], Type, CoAxiom Unbranched)
1557 unwrapNewTyCon_maybe (AlgTyCon { tyConTyVars = tvs,
1558 algTcRhs = NewTyCon { nt_co = co,
1559 nt_rhs = rhs }})
1560 = Just (tvs, rhs, co)
1561 unwrapNewTyCon_maybe _ = Nothing
1562
1563 unwrapNewTyConEtad_maybe :: TyCon -> Maybe ([TyVar], Type, CoAxiom Unbranched)
1564 unwrapNewTyConEtad_maybe (AlgTyCon { algTcRhs = NewTyCon { nt_co = co,
1565 nt_etad_rhs = (tvs,rhs) }})
1566 = Just (tvs, rhs, co)
1567 unwrapNewTyConEtad_maybe _ = Nothing
1568
1569 isProductTyCon :: TyCon -> Bool
1570 -- True of datatypes or newtypes that have
1571 -- one, non-existential, data constructor
1572 -- See Note [Product types]
1573 isProductTyCon tc@(AlgTyCon {})
1574 = case algTcRhs tc of
1575 TupleTyCon {} -> True
1576 DataTyCon{ data_cons = [data_con] }
1577 -> null (dataConExTyVars data_con)
1578 NewTyCon {} -> True
1579 _ -> False
1580 isProductTyCon _ = False
1581
1582 isDataProductTyCon_maybe :: TyCon -> Maybe DataCon
1583 -- True of datatypes (not newtypes) with
1584 -- one, vanilla, data constructor
1585 -- See Note [Product types]
1586 isDataProductTyCon_maybe (AlgTyCon { algTcRhs = rhs })
1587 = case rhs of
1588 DataTyCon { data_cons = [con] }
1589 | null (dataConExTyVars con) -- non-existential
1590 -> Just con
1591 TupleTyCon { data_con = con }
1592 -> Just con
1593 _ -> Nothing
1594 isDataProductTyCon_maybe _ = Nothing
1595
1596 {- Note [Product types]
1597 ~~~~~~~~~~~~~~~~~~~~~~~
1598 A product type is
1599 * A data type (not a newtype)
1600 * With one, boxed data constructor
1601 * That binds no existential type variables
1602
1603 The main point is that product types are amenable to unboxing for
1604 * Strict function calls; we can transform
1605 f (D a b) = e
1606 to
1607 fw a b = e
1608 via the worker/wrapper transformation. (Question: couldn't this
1609 work for existentials too?)
1610
1611 * CPR for function results; we can transform
1612 f x y = let ... in D a b
1613 to
1614 fw x y = let ... in (# a, b #)
1615
1616 Note that the data constructor /can/ have evidence arguments: equality
1617 constraints, type classes etc. So it can be GADT. These evidence
1618 arguments are simply value arguments, and should not get in the way.
1619 -}
1620
1621
1622 -- | Is this a 'TyCon' representing a regular H98 type synonym (@type@)?
1623 isTypeSynonymTyCon :: TyCon -> Bool
1624 isTypeSynonymTyCon (SynonymTyCon {}) = True
1625 isTypeSynonymTyCon _ = False
1626
1627
1628 -- As for newtypes, it is in some contexts important to distinguish between
1629 -- closed synonyms and synonym families, as synonym families have no unique
1630 -- right hand side to which a synonym family application can expand.
1631 --
1632
1633 -- | True iff we can decompose (T a b c) into ((T a b) c)
1634 -- I.e. is it injective and generative w.r.t nominal equality?
1635 -- That is, if (T a b) ~N d e f, is it always the case that
1636 -- (T ~N d), (a ~N e) and (b ~N f)?
1637 -- Specifically NOT true of synonyms (open and otherwise)
1638 --
1639 -- It'd be unusual to call mightBeUnsaturatedTyCon on a regular H98
1640 -- type synonym, because you should probably have expanded it first
1641 -- But regardless, it's not decomposable
1642 mightBeUnsaturatedTyCon :: TyCon -> Bool
1643 mightBeUnsaturatedTyCon (SynonymTyCon {}) = False
1644 mightBeUnsaturatedTyCon (FamilyTyCon { famTcFlav = flav}) = isDataFamFlav flav
1645 mightBeUnsaturatedTyCon (TcTyCon { tyConUnsat = unsat }) = unsat
1646 mightBeUnsaturatedTyCon _other = True
1647
1648 -- | Is this an algebraic 'TyCon' declared with the GADT syntax?
1649 isGadtSyntaxTyCon :: TyCon -> Bool
1650 isGadtSyntaxTyCon (AlgTyCon { algTcGadtSyntax = res }) = res
1651 isGadtSyntaxTyCon _ = False
1652
1653 -- | Is this an algebraic 'TyCon' which is just an enumeration of values?
1654 isEnumerationTyCon :: TyCon -> Bool
1655 -- See Note [Enumeration types] in TyCon
1656 isEnumerationTyCon (AlgTyCon { tyConArity = arity, algTcRhs = rhs })
1657 = case rhs of
1658 DataTyCon { is_enum = res } -> res
1659 TupleTyCon {} -> arity == 0
1660 _ -> False
1661 isEnumerationTyCon _ = False
1662
1663 -- | Is this a 'TyCon', synonym or otherwise, that defines a family?
1664 isFamilyTyCon :: TyCon -> Bool
1665 isFamilyTyCon (FamilyTyCon {}) = True
1666 isFamilyTyCon _ = False
1667
1668 -- | Is this a 'TyCon', synonym or otherwise, that defines a family with
1669 -- instances?
1670 isOpenFamilyTyCon :: TyCon -> Bool
1671 isOpenFamilyTyCon (FamilyTyCon {famTcFlav = flav })
1672 | OpenSynFamilyTyCon <- flav = True
1673 | DataFamilyTyCon {} <- flav = True
1674 isOpenFamilyTyCon _ = False
1675
1676 -- | Is this a synonym 'TyCon' that can have may have further instances appear?
1677 isTypeFamilyTyCon :: TyCon -> Bool
1678 isTypeFamilyTyCon (FamilyTyCon { famTcFlav = flav }) = not (isDataFamFlav flav)
1679 isTypeFamilyTyCon _ = False
1680
1681 -- | Is this a synonym 'TyCon' that can have may have further instances appear?
1682 isDataFamilyTyCon :: TyCon -> Bool
1683 isDataFamilyTyCon (FamilyTyCon { famTcFlav = flav }) = isDataFamFlav flav
1684 isDataFamilyTyCon _ = False
1685
1686 -- | Is this an open type family TyCon?
1687 isOpenTypeFamilyTyCon :: TyCon -> Bool
1688 isOpenTypeFamilyTyCon (FamilyTyCon {famTcFlav = OpenSynFamilyTyCon }) = True
1689 isOpenTypeFamilyTyCon _ = False
1690
1691 -- | Is this a non-empty closed type family? Returns 'Nothing' for
1692 -- abstract or empty closed families.
1693 isClosedSynFamilyTyConWithAxiom_maybe :: TyCon -> Maybe (CoAxiom Branched)
1694 isClosedSynFamilyTyConWithAxiom_maybe
1695 (FamilyTyCon {famTcFlav = ClosedSynFamilyTyCon mb}) = mb
1696 isClosedSynFamilyTyConWithAxiom_maybe _ = Nothing
1697
1698 -- | Try to read the injectivity information from a FamilyTyCon.
1699 -- For every other TyCon this function panics.
1700 familyTyConInjectivityInfo :: TyCon -> Injectivity
1701 familyTyConInjectivityInfo (FamilyTyCon { famTcInj = inj }) = inj
1702 familyTyConInjectivityInfo _ = panic "familyTyConInjectivityInfo"
1703
1704 isBuiltInSynFamTyCon_maybe :: TyCon -> Maybe BuiltInSynFamily
1705 isBuiltInSynFamTyCon_maybe
1706 (FamilyTyCon {famTcFlav = BuiltInSynFamTyCon ops }) = Just ops
1707 isBuiltInSynFamTyCon_maybe _ = Nothing
1708
1709 isDataFamFlav :: FamTyConFlav -> Bool
1710 isDataFamFlav (DataFamilyTyCon {}) = True -- Data family
1711 isDataFamFlav _ = False -- Type synonym family
1712
1713 -- | Are we able to extract information 'TyVar' to class argument list
1714 -- mapping from a given 'TyCon'?
1715 isTyConAssoc :: TyCon -> Bool
1716 isTyConAssoc tc = isJust (tyConAssoc_maybe tc)
1717
1718 tyConAssoc_maybe :: TyCon -> Maybe Class
1719 tyConAssoc_maybe (FamilyTyCon { famTcParent = mb_cls }) = mb_cls
1720 tyConAssoc_maybe _ = Nothing
1721
1722 -- The unit tycon didn't used to be classed as a tuple tycon
1723 -- but I thought that was silly so I've undone it
1724 -- If it can't be for some reason, it should be a AlgTyCon
1725 isTupleTyCon :: TyCon -> Bool
1726 -- ^ Does this 'TyCon' represent a tuple?
1727 --
1728 -- NB: when compiling @Data.Tuple@, the tycons won't reply @True@ to
1729 -- 'isTupleTyCon', because they are built as 'AlgTyCons'. However they
1730 -- get spat into the interface file as tuple tycons, so I don't think
1731 -- it matters.
1732 isTupleTyCon (AlgTyCon { algTcRhs = TupleTyCon {} }) = True
1733 isTupleTyCon _ = False
1734
1735 tyConTuple_maybe :: TyCon -> Maybe TupleSort
1736 tyConTuple_maybe (AlgTyCon { algTcRhs = rhs })
1737 | TupleTyCon { tup_sort = sort} <- rhs = Just sort
1738 tyConTuple_maybe _ = Nothing
1739
1740 -- | Is this the 'TyCon' for an unboxed tuple?
1741 isUnboxedTupleTyCon :: TyCon -> Bool
1742 isUnboxedTupleTyCon (AlgTyCon { algTcRhs = rhs })
1743 | TupleTyCon { tup_sort = sort } <- rhs
1744 = not (isBoxed (tupleSortBoxity sort))
1745 isUnboxedTupleTyCon _ = False
1746
1747 -- | Is this the 'TyCon' for a boxed tuple?
1748 isBoxedTupleTyCon :: TyCon -> Bool
1749 isBoxedTupleTyCon (AlgTyCon { algTcRhs = rhs })
1750 | TupleTyCon { tup_sort = sort } <- rhs
1751 = isBoxed (tupleSortBoxity sort)
1752 isBoxedTupleTyCon _ = False
1753
1754 -- | Is this a recursive 'TyCon'?
1755 isRecursiveTyCon :: TyCon -> Bool
1756 isRecursiveTyCon (AlgTyCon {algTcRec = Recursive}) = True
1757 isRecursiveTyCon _ = False
1758
1759 -- | Is this a PromotedDataCon?
1760 isPromotedDataCon :: TyCon -> Bool
1761 isPromotedDataCon (PromotedDataCon {}) = True
1762 isPromotedDataCon _ = False
1763
1764 -- | Retrieves the promoted DataCon if this is a PromotedDataCon;
1765 isPromotedDataCon_maybe :: TyCon -> Maybe DataCon
1766 isPromotedDataCon_maybe (PromotedDataCon { dataCon = dc }) = Just dc
1767 isPromotedDataCon_maybe _ = Nothing
1768
1769 -- | Is this tycon really meant for use at the kind level? That is,
1770 -- should it be permitted without -XDataKinds?
1771 isKindTyCon :: TyCon -> Bool
1772 isKindTyCon tc = getUnique tc `elementOfUniqSet` kindTyConKeys
1773
1774 -- | These TyCons should be allowed at the kind level, even without
1775 -- -XDataKinds.
1776 kindTyConKeys :: UniqSet Unique
1777 kindTyConKeys = unionManyUniqSets
1778 ( mkUniqSet [ liftedTypeKindTyConKey, starKindTyConKey, unicodeStarKindTyConKey
1779 , constraintKindTyConKey, tYPETyConKey ]
1780 : map (mkUniqSet . tycon_with_datacons) [ runtimeRepTyCon
1781 , vecCountTyCon, vecElemTyCon ] )
1782 where
1783 tycon_with_datacons tc = getUnique tc : map getUnique (tyConDataCons tc)
1784
1785 isLiftedTypeKindTyConName :: Name -> Bool
1786 isLiftedTypeKindTyConName
1787 = (`hasKey` liftedTypeKindTyConKey) <||>
1788 (`hasKey` starKindTyConKey) <||>
1789 (`hasKey` unicodeStarKindTyConKey)
1790
1791 -- | Identifies implicit tycons that, in particular, do not go into interface
1792 -- files (because they are implicitly reconstructed when the interface is
1793 -- read).
1794 --
1795 -- Note that:
1796 --
1797 -- * Associated families are implicit, as they are re-constructed from
1798 -- the class declaration in which they reside, and
1799 --
1800 -- * Family instances are /not/ implicit as they represent the instance body
1801 -- (similar to a @dfun@ does that for a class instance).
1802 --
1803 -- * Tuples are implicit iff they have a wired-in name
1804 -- (namely: boxed and unboxed tupeles are wired-in and implicit,
1805 -- but constraint tuples are not)
1806 isImplicitTyCon :: TyCon -> Bool
1807 isImplicitTyCon (FunTyCon {}) = True
1808 isImplicitTyCon (PrimTyCon {}) = True
1809 isImplicitTyCon (PromotedDataCon {}) = True
1810 isImplicitTyCon (AlgTyCon { algTcRhs = rhs, tyConName = name })
1811 | TupleTyCon {} <- rhs = isWiredInName name
1812 | otherwise = False
1813 isImplicitTyCon (FamilyTyCon { famTcParent = parent }) = isJust parent
1814 isImplicitTyCon (SynonymTyCon {}) = False
1815 isImplicitTyCon tc@(TcTyCon {})
1816 = pprPanic "isImplicitTyCon sees a TcTyCon" (ppr tc)
1817
1818 tyConCType_maybe :: TyCon -> Maybe CType
1819 tyConCType_maybe tc@(AlgTyCon {}) = tyConCType tc
1820 tyConCType_maybe _ = Nothing
1821
1822 -- | Is this a TcTyCon? (That is, one only used during type-checking?)
1823 isTcTyCon :: TyCon -> Bool
1824 isTcTyCon (TcTyCon {}) = True
1825 isTcTyCon _ = False
1826
1827 {-
1828 -----------------------------------------------
1829 -- Expand type-constructor applications
1830 -----------------------------------------------
1831 -}
1832
1833 expandSynTyCon_maybe
1834 :: TyCon
1835 -> [tyco] -- ^ Arguments to 'TyCon'
1836 -> Maybe ([(TyVar,tyco)],
1837 Type,
1838 [tyco]) -- ^ Returns a 'TyVar' substitution, the body
1839 -- type of the synonym (not yet substituted)
1840 -- and any arguments remaining from the
1841 -- application
1842
1843 -- ^ Expand a type synonym application, if any
1844 expandSynTyCon_maybe tc tys
1845 | SynonymTyCon { tyConTyVars = tvs, synTcRhs = rhs, tyConArity = arity } <- tc
1846 = case arity `compare` length tys of
1847 LT -> Just (tvs `zip` tys, rhs, drop arity tys)
1848 EQ -> Just (tvs `zip` tys, rhs, [])
1849 GT -> Nothing
1850 | otherwise
1851 = Nothing
1852
1853 ----------------
1854
1855 -- | Check if the tycon actually refers to a proper `data` or `newtype`
1856 -- with user defined constructors rather than one from a class or other
1857 -- construction.
1858 isTyConWithSrcDataCons :: TyCon -> Bool
1859 isTyConWithSrcDataCons (AlgTyCon { algTcRhs = rhs, algTcParent = parent }) =
1860 case rhs of
1861 DataTyCon {} -> isSrcParent
1862 NewTyCon {} -> isSrcParent
1863 TupleTyCon {} -> isSrcParent
1864 _ -> False
1865 where
1866 isSrcParent = isNoParent parent
1867 isTyConWithSrcDataCons _ = False
1868
1869
1870 -- | As 'tyConDataCons_maybe', but returns the empty list of constructors if no
1871 -- constructors could be found
1872 tyConDataCons :: TyCon -> [DataCon]
1873 -- It's convenient for tyConDataCons to return the
1874 -- empty list for type synonyms etc
1875 tyConDataCons tycon = tyConDataCons_maybe tycon `orElse` []
1876
1877 -- | Determine the 'DataCon's originating from the given 'TyCon', if the 'TyCon'
1878 -- is the sort that can have any constructors (note: this does not include
1879 -- abstract algebraic types)
1880 tyConDataCons_maybe :: TyCon -> Maybe [DataCon]
1881 tyConDataCons_maybe (AlgTyCon {algTcRhs = rhs})
1882 = case rhs of
1883 DataTyCon { data_cons = cons } -> Just cons
1884 NewTyCon { data_con = con } -> Just [con]
1885 TupleTyCon { data_con = con } -> Just [con]
1886 _ -> Nothing
1887 tyConDataCons_maybe _ = Nothing
1888
1889 -- | If the given 'TyCon' has a /single/ data constructor, i.e. it is a @data@
1890 -- type with one alternative, a tuple type or a @newtype@ then that constructor
1891 -- is returned. If the 'TyCon' has more than one constructor, or represents a
1892 -- primitive or function type constructor then @Nothing@ is returned. In any
1893 -- other case, the function panics
1894 tyConSingleDataCon_maybe :: TyCon -> Maybe DataCon
1895 tyConSingleDataCon_maybe (AlgTyCon { algTcRhs = rhs })
1896 = case rhs of
1897 DataTyCon { data_cons = [c] } -> Just c
1898 TupleTyCon { data_con = c } -> Just c
1899 NewTyCon { data_con = c } -> Just c
1900 _ -> Nothing
1901 tyConSingleDataCon_maybe _ = Nothing
1902
1903 tyConSingleDataCon :: TyCon -> DataCon
1904 tyConSingleDataCon tc
1905 = case tyConSingleDataCon_maybe tc of
1906 Just c -> c
1907 Nothing -> pprPanic "tyConDataCon" (ppr tc)
1908
1909 tyConSingleAlgDataCon_maybe :: TyCon -> Maybe DataCon
1910 -- Returns (Just con) for single-constructor
1911 -- *algebraic* data types *not* newtypes
1912 tyConSingleAlgDataCon_maybe (AlgTyCon { algTcRhs = rhs })
1913 = case rhs of
1914 DataTyCon { data_cons = [c] } -> Just c
1915 TupleTyCon { data_con = c } -> Just c
1916 _ -> Nothing
1917 tyConSingleAlgDataCon_maybe _ = Nothing
1918
1919 -- | Determine the number of value constructors a 'TyCon' has. Panics if the
1920 -- 'TyCon' is not algebraic or a tuple
1921 tyConFamilySize :: TyCon -> Int
1922 tyConFamilySize tc@(AlgTyCon { algTcRhs = rhs })
1923 = case rhs of
1924 DataTyCon { data_cons = cons } -> length cons
1925 NewTyCon {} -> 1
1926 TupleTyCon {} -> 1
1927 _ -> pprPanic "tyConFamilySize 1" (ppr tc)
1928 tyConFamilySize tc = pprPanic "tyConFamilySize 2" (ppr tc)
1929
1930 -- | Extract an 'AlgTyConRhs' with information about data constructors from an
1931 -- algebraic or tuple 'TyCon'. Panics for any other sort of 'TyCon'
1932 algTyConRhs :: TyCon -> AlgTyConRhs
1933 algTyConRhs (AlgTyCon {algTcRhs = rhs}) = rhs
1934 algTyConRhs other = pprPanic "algTyConRhs" (ppr other)
1935
1936 -- | Extract type variable naming the result of injective type family
1937 tyConFamilyResVar_maybe :: TyCon -> Maybe Name
1938 tyConFamilyResVar_maybe (FamilyTyCon {famTcResVar = res}) = res
1939 tyConFamilyResVar_maybe _ = Nothing
1940
1941 -- | Get the list of roles for the type parameters of a TyCon
1942 tyConRoles :: TyCon -> [Role]
1943 -- See also Note [TyCon Role signatures]
1944 tyConRoles tc
1945 = case tc of
1946 { FunTyCon {} -> const_role Representational
1947 ; AlgTyCon { tcRoles = roles } -> roles
1948 ; SynonymTyCon { tcRoles = roles } -> roles
1949 ; FamilyTyCon {} -> const_role Nominal
1950 ; PrimTyCon { tcRoles = roles } -> roles
1951 ; PromotedDataCon { tcRoles = roles } -> roles
1952 ; TcTyCon {} -> pprPanic "tyConRoles sees a TcTyCon" (ppr tc)
1953 }
1954 where
1955 const_role r = replicate (tyConArity tc) r
1956
1957 -- | Extract the bound type variables and type expansion of a type synonym
1958 -- 'TyCon'. Panics if the 'TyCon' is not a synonym
1959 newTyConRhs :: TyCon -> ([TyVar], Type)
1960 newTyConRhs (AlgTyCon {tyConTyVars = tvs, algTcRhs = NewTyCon { nt_rhs = rhs }})
1961 = (tvs, rhs)
1962 newTyConRhs tycon = pprPanic "newTyConRhs" (ppr tycon)
1963
1964 -- | The number of type parameters that need to be passed to a newtype to
1965 -- resolve it. May be less than in the definition if it can be eta-contracted.
1966 newTyConEtadArity :: TyCon -> Int
1967 newTyConEtadArity (AlgTyCon {algTcRhs = NewTyCon { nt_etad_rhs = tvs_rhs }})
1968 = length (fst tvs_rhs)
1969 newTyConEtadArity tycon = pprPanic "newTyConEtadArity" (ppr tycon)
1970
1971 -- | Extract the bound type variables and type expansion of an eta-contracted
1972 -- type synonym 'TyCon'. Panics if the 'TyCon' is not a synonym
1973 newTyConEtadRhs :: TyCon -> ([TyVar], Type)
1974 newTyConEtadRhs (AlgTyCon {algTcRhs = NewTyCon { nt_etad_rhs = tvs_rhs }}) = tvs_rhs
1975 newTyConEtadRhs tycon = pprPanic "newTyConEtadRhs" (ppr tycon)
1976
1977 -- | Extracts the @newtype@ coercion from such a 'TyCon', which can be used to
1978 -- construct something with the @newtype@s type from its representation type
1979 -- (right hand side). If the supplied 'TyCon' is not a @newtype@, returns
1980 -- @Nothing@
1981 newTyConCo_maybe :: TyCon -> Maybe (CoAxiom Unbranched)
1982 newTyConCo_maybe (AlgTyCon {algTcRhs = NewTyCon { nt_co = co }}) = Just co
1983 newTyConCo_maybe _ = Nothing
1984
1985 newTyConCo :: TyCon -> CoAxiom Unbranched
1986 newTyConCo tc = case newTyConCo_maybe tc of
1987 Just co -> co
1988 Nothing -> pprPanic "newTyConCo" (ppr tc)
1989
1990 -- | Find the \"stupid theta\" of the 'TyCon'. A \"stupid theta\" is the context
1991 -- to the left of an algebraic type declaration, e.g. @Eq a@ in the declaration
1992 -- @data Eq a => T a ...@
1993 tyConStupidTheta :: TyCon -> [PredType]
1994 tyConStupidTheta (AlgTyCon {algTcStupidTheta = stupid}) = stupid
1995 tyConStupidTheta tycon = pprPanic "tyConStupidTheta" (ppr tycon)
1996
1997 -- | Extract the 'TyVar's bound by a vanilla type synonym
1998 -- and the corresponding (unsubstituted) right hand side.
1999 synTyConDefn_maybe :: TyCon -> Maybe ([TyVar], Type)
2000 synTyConDefn_maybe (SynonymTyCon {tyConTyVars = tyvars, synTcRhs = ty})
2001 = Just (tyvars, ty)
2002 synTyConDefn_maybe _ = Nothing
2003
2004 -- | Extract the information pertaining to the right hand side of a type synonym
2005 -- (@type@) declaration.
2006 synTyConRhs_maybe :: TyCon -> Maybe Type
2007 synTyConRhs_maybe (SynonymTyCon {synTcRhs = rhs}) = Just rhs
2008 synTyConRhs_maybe _ = Nothing
2009
2010 -- | Extract the flavour of a type family (with all the extra information that
2011 -- it carries)
2012 famTyConFlav_maybe :: TyCon -> Maybe FamTyConFlav
2013 famTyConFlav_maybe (FamilyTyCon {famTcFlav = flav}) = Just flav
2014 famTyConFlav_maybe _ = Nothing
2015
2016 -- | Is this 'TyCon' that for a class instance?
2017 isClassTyCon :: TyCon -> Bool
2018 isClassTyCon (AlgTyCon {algTcParent = ClassTyCon {}}) = True
2019 isClassTyCon _ = False
2020
2021 -- | If this 'TyCon' is that for a class instance, return the class it is for.
2022 -- Otherwise returns @Nothing@
2023 tyConClass_maybe :: TyCon -> Maybe Class
2024 tyConClass_maybe (AlgTyCon {algTcParent = ClassTyCon clas _}) = Just clas
2025 tyConClass_maybe _ = Nothing
2026
2027 -- | Return the associated types of the 'TyCon', if any
2028 tyConATs :: TyCon -> [TyCon]
2029 tyConATs (AlgTyCon {algTcParent = ClassTyCon clas _}) = classATs clas
2030 tyConATs _ = []
2031
2032 ----------------------------------------------------------------------------
2033 -- | Is this 'TyCon' that for a data family instance?
2034 isFamInstTyCon :: TyCon -> Bool
2035 isFamInstTyCon (AlgTyCon {algTcParent = DataFamInstTyCon {} })
2036 = True
2037 isFamInstTyCon _ = False
2038
2039 tyConFamInstSig_maybe :: TyCon -> Maybe (TyCon, [Type], CoAxiom Unbranched)
2040 tyConFamInstSig_maybe (AlgTyCon {algTcParent = DataFamInstTyCon ax f ts })
2041 = Just (f, ts, ax)
2042 tyConFamInstSig_maybe _ = Nothing
2043
2044 -- | If this 'TyCon' is that of a data family instance, return the family in question
2045 -- and the instance types. Otherwise, return @Nothing@
2046 tyConFamInst_maybe :: TyCon -> Maybe (TyCon, [Type])
2047 tyConFamInst_maybe (AlgTyCon {algTcParent = DataFamInstTyCon _ f ts })
2048 = Just (f, ts)
2049 tyConFamInst_maybe _ = Nothing
2050
2051 -- | If this 'TyCon' is that of a data family instance, return a 'TyCon' which
2052 -- represents a coercion identifying the representation type with the type
2053 -- instance family. Otherwise, return @Nothing@
2054 tyConFamilyCoercion_maybe :: TyCon -> Maybe (CoAxiom Unbranched)
2055 tyConFamilyCoercion_maybe (AlgTyCon {algTcParent = DataFamInstTyCon ax _ _ })
2056 = Just ax
2057 tyConFamilyCoercion_maybe _ = Nothing
2058
2059 -- | Extract any 'RuntimeRepInfo' from this TyCon
2060 tyConRuntimeRepInfo :: TyCon -> RuntimeRepInfo
2061 tyConRuntimeRepInfo (PromotedDataCon { promDcRepInfo = rri }) = rri
2062 tyConRuntimeRepInfo _ = NoRRI
2063 -- could panic in that second case. But Douglas Adams told me not to.
2064
2065 {-
2066 ************************************************************************
2067 * *
2068 \subsection[TyCon-instances]{Instance declarations for @TyCon@}
2069 * *
2070 ************************************************************************
2071
2072 @TyCon@s are compared by comparing their @Unique@s.
2073 -}
2074
2075 instance Eq TyCon where
2076 a == b = case (a `compare` b) of { EQ -> True; _ -> False }
2077 a /= b = case (a `compare` b) of { EQ -> False; _ -> True }
2078
2079 instance Ord TyCon where
2080 a <= b = case (a `compare` b) of { LT -> True; EQ -> True; GT -> False }
2081 a < b = case (a `compare` b) of { LT -> True; EQ -> False; GT -> False }
2082 a >= b = case (a `compare` b) of { LT -> False; EQ -> True; GT -> True }
2083 a > b = case (a `compare` b) of { LT -> False; EQ -> False; GT -> True }
2084 compare a b = getUnique a `compare` getUnique b
2085
2086 instance Uniquable TyCon where
2087 getUnique tc = tyConUnique tc
2088
2089 instance Outputable TyCon where
2090 -- At the moment a promoted TyCon has the same Name as its
2091 -- corresponding TyCon, so we add the quote to distinguish it here
2092 ppr tc = pprPromotionQuote tc <> ppr (tyConName tc)
2093
2094 tyConFlavour :: TyCon -> String
2095 tyConFlavour (AlgTyCon { algTcParent = parent, algTcRhs = rhs })
2096 | ClassTyCon _ _ <- parent = "class"
2097 | otherwise = case rhs of
2098 TupleTyCon { tup_sort = sort }
2099 | isBoxed (tupleSortBoxity sort) -> "tuple"
2100 | otherwise -> "unboxed tuple"
2101 DataTyCon {} -> "data type"
2102 NewTyCon {} -> "newtype"
2103 AbstractTyCon {} -> "abstract type"
2104 tyConFlavour (FamilyTyCon { famTcFlav = flav })
2105 | isDataFamFlav flav = "data family"
2106 | otherwise = "type family"
2107 tyConFlavour (SynonymTyCon {}) = "type synonym"
2108 tyConFlavour (FunTyCon {}) = "built-in type"
2109 tyConFlavour (PrimTyCon {}) = "built-in type"
2110 tyConFlavour (PromotedDataCon {}) = "promoted data constructor"
2111 tyConFlavour tc@(TcTyCon {})
2112 = pprPanic "tyConFlavour sees a TcTyCon" (ppr tc)
2113
2114 pprPromotionQuote :: TyCon -> SDoc
2115 -- Promoted data constructors already have a tick in their OccName
2116 pprPromotionQuote tc
2117 = case tc of
2118 PromotedDataCon {} -> char '\'' -- Always quote promoted DataCons in types
2119 _ -> empty
2120
2121 instance NamedThing TyCon where
2122 getName = tyConName
2123
2124 instance Data.Data TyCon where
2125 -- don't traverse?
2126 toConstr _ = abstractConstr "TyCon"
2127 gunfold _ _ = error "gunfold"
2128 dataTypeOf _ = mkNoRepType "TyCon"
2129
2130 instance Binary Injectivity where
2131 put_ bh NotInjective = putByte bh 0
2132 put_ bh (Injective xs) = putByte bh 1 >> put_ bh xs
2133
2134 get bh = do { h <- getByte bh
2135 ; case h of
2136 0 -> return NotInjective
2137 _ -> do { xs <- get bh
2138 ; return (Injective xs) } }
2139
2140 {-
2141 ************************************************************************
2142 * *
2143 Walking over recursive TyCons
2144 * *
2145 ************************************************************************
2146
2147 Note [Expanding newtypes and products]
2148 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2149 When expanding a type to expose a data-type constructor, we need to be
2150 careful about newtypes, lest we fall into an infinite loop. Here are
2151 the key examples:
2152
2153 newtype Id x = MkId x
2154 newtype Fix f = MkFix (f (Fix f))
2155 newtype T = MkT (T -> T)
2156
2157 Type Expansion
2158 --------------------------
2159 T T -> T
2160 Fix Maybe Maybe (Fix Maybe)
2161 Id (Id Int) Int
2162 Fix Id NO NO NO
2163
2164 Notice that
2165 * We can expand T, even though it's recursive.
2166 * We can expand Id (Id Int), even though the Id shows up
2167 twice at the outer level, because Id is non-recursive
2168
2169 So, when expanding, we keep track of when we've seen a recursive
2170 newtype at outermost level; and bale out if we see it again.
2171
2172 We sometimes want to do the same for product types, so that the
2173 strictness analyser doesn't unbox infinitely deeply.
2174
2175 More precisely, we keep a *count* of how many times we've seen it.
2176 This is to account for
2177 data instance T (a,b) = MkT (T a) (T b)
2178 Then (Trac #10482) if we have a type like
2179 T (Int,(Int,(Int,(Int,Int))))
2180 we can still unbox deeply enough during strictness analysis.
2181 We have to treat T as potentially recursive, but it's still
2182 good to be able to unwrap multiple layers.
2183
2184 The function that manages all this is checkRecTc.
2185 -}
2186
2187 data RecTcChecker = RC !Int (NameEnv Int)
2188 -- The upper bound, and the number of times
2189 -- we have encountered each TyCon
2190
2191 initRecTc :: RecTcChecker
2192 -- Intialise with a fixed max bound of 100
2193 -- We should probably have a flag for this
2194 initRecTc = RC 100 emptyNameEnv
2195
2196 checkRecTc :: RecTcChecker -> TyCon -> Maybe RecTcChecker
2197 -- Nothing => Recursion detected
2198 -- Just rec_tcs => Keep going
2199 checkRecTc rc@(RC bound rec_nts) tc
2200 | not (isRecursiveTyCon tc)
2201 = Just rc -- Tuples are a common example here
2202 | otherwise
2203 = case lookupNameEnv rec_nts tc_name of
2204 Just n | n >= bound -> Nothing
2205 | otherwise -> Just (RC bound (extendNameEnv rec_nts tc_name (n+1)))
2206 Nothing -> Just (RC bound (extendNameEnv rec_nts tc_name 1))
2207 where
2208 tc_name = tyConName tc