3f747f94f3cdc58fa92356a8a399cc1b0f355eda
[ghc.git] / compiler / basicTypes / DataCon.lhs
1 %
2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 %
5 \section[DataCon]{@DataCon@: Data Constructors}
6
7 \begin{code}
8 {-# OPTIONS -fno-warn-tabs #-}
9 -- The above warning supression flag is a temporary kludge.
10 -- While working on this module you are encouraged to remove it and
11 -- detab the module (please do the detabbing in a separate patch). See
12 --     http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#TabsvsSpaces
13 -- for details
14
15 module DataCon (
16         -- * Main data types
17         DataCon, DataConIds(..),
18         ConTag,
19         
20         -- ** Type construction
21         mkDataCon, fIRST_TAG,
22         
23         -- ** Type deconstruction
24         dataConRepType, dataConSig, dataConFullSig,
25         dataConName, dataConIdentity, dataConTag, dataConTyCon, 
26         dataConOrigTyCon, dataConUserType,
27         dataConUnivTyVars, dataConExTyVars, dataConAllTyVars, 
28         dataConEqSpec, eqSpecPreds, dataConTheta,
29         dataConStupidTheta,  
30         dataConInstArgTys, dataConOrigArgTys, dataConOrigResTy,
31         dataConInstOrigArgTys, dataConRepArgTys, 
32         dataConFieldLabels, dataConFieldType,
33         dataConStrictMarks, dataConExStricts,
34         dataConSourceArity, dataConRepArity,
35         dataConIsInfix,
36         dataConWorkId, dataConWrapId, dataConWrapId_maybe, dataConImplicitIds,
37         dataConRepStrictness,
38         
39         -- ** Predicates on DataCons
40         isNullarySrcDataCon, isNullaryRepDataCon, isTupleCon, isUnboxedTupleCon,
41         isVanillaDataCon, classDataCon, dataConCannotMatch,
42
43         -- * Splitting product types
44         splitProductType_maybe, splitProductType, deepSplitProductType,
45         deepSplitProductType_maybe,
46
47         -- ** Promotion related functions
48         promoteType, isPromotableType, isPromotableTyCon,
49         buildPromotedTyCon, buildPromotedDataCon,
50     ) where
51
52 #include "HsVersions.h"
53
54 import Type
55 import TypeRep( Type(..) )  -- Used in promoteType
56 import PrelNames( liftedTypeKindTyConKey )
57 import Kind
58 import Unify
59 import Coercion
60 import TyCon
61 import Class
62 import Name
63 import Var
64 import Outputable
65 import Unique
66 import ListSetOps
67 import Util
68 import BasicTypes
69 import FastString
70 import Module
71 import VarEnv
72
73 import qualified Data.Data as Data
74 import qualified Data.Typeable
75 import Data.Char
76 import Data.Word
77 \end{code}
78
79
80 Data constructor representation
81 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
82 Consider the following Haskell data type declaration
83
84         data T = T !Int ![Int]
85
86 Using the strictness annotations, GHC will represent this as
87
88         data T = T Int# [Int]
89
90 That is, the Int has been unboxed.  Furthermore, the Haskell source construction
91
92         T e1 e2
93
94 is translated to
95
96         case e1 of { I# x -> 
97         case e2 of { r ->
98         T x r }}
99
100 That is, the first argument is unboxed, and the second is evaluated.  Finally,
101 pattern matching is translated too:
102
103         case e of { T a b -> ... }
104
105 becomes
106
107         case e of { T a' b -> let a = I# a' in ... }
108
109 To keep ourselves sane, we name the different versions of the data constructor
110 differently, as follows.
111
112
113 Note [Data Constructor Naming]
114 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
115 Each data constructor C has two, and possibly up to four, Names associated with it:
116
117                    OccName   Name space   Name of   Notes
118  ---------------------------------------------------------------------------
119  The "data con itself"   C     DataName   DataCon   In dom( GlobalRdrEnv )
120  The "worker data con"   C     VarName    Id        The worker
121  The "wrapper data con"  $WC   VarName    Id        The wrapper
122  The "newtype coercion"  :CoT  TcClsName  TyCon
123  
124 EVERY data constructor (incl for newtypes) has the former two (the
125 data con itself, and its worker.  But only some data constructors have a
126 wrapper (see Note [The need for a wrapper]).
127
128 Each of these three has a distinct Unique.  The "data con itself" name
129 appears in the output of the renamer, and names the Haskell-source
130 data constructor.  The type checker translates it into either the wrapper Id
131 (if it exists) or worker Id (otherwise).
132
133 The data con has one or two Ids associated with it:
134
135 The "worker Id", is the actual data constructor.
136 * Every data constructor (newtype or data type) has a worker
137
138 * The worker is very like a primop, in that it has no binding.
139
140 * For a *data* type, the worker *is* the data constructor;
141   it has no unfolding
142
143 * For a *newtype*, the worker has a compulsory unfolding which 
144   does a cast, e.g.
145         newtype T = MkT Int
146         The worker for MkT has unfolding
147                 \\(x:Int). x `cast` sym CoT
148   Here CoT is the type constructor, witnessing the FC axiom
149         axiom CoT : T = Int
150
151 The "wrapper Id", \$WC, goes as follows
152
153 * Its type is exactly what it looks like in the source program. 
154
155 * It is an ordinary function, and it gets a top-level binding 
156   like any other function.
157
158 * The wrapper Id isn't generated for a data type if there is
159   nothing for the wrapper to do.  That is, if its defn would be
160         \$wC = C
161
162 Note [The need for a wrapper]
163 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
164 Why might the wrapper have anything to do?  Two reasons:
165
166 * Unboxing strict fields (with -funbox-strict-fields)
167         data T = MkT !(Int,Int)
168         \$wMkT :: (Int,Int) -> T
169         \$wMkT (x,y) = MkT x y
170   Notice that the worker has two fields where the wapper has 
171   just one.  That is, the worker has type
172                 MkT :: Int -> Int -> T
173
174 * Equality constraints for GADTs
175         data T a where { MkT :: a -> T [a] }
176
177   The worker gets a type with explicit equality
178   constraints, thus:
179         MkT :: forall a b. (a=[b]) => b -> T a
180
181   The wrapper has the programmer-specified type:
182         \$wMkT :: a -> T [a]
183         \$wMkT a x = MkT [a] a [a] x
184   The third argument is a coerion
185         [a] :: [a]~[a]
186
187 INVARIANT: the dictionary constructor for a class
188            never has a wrapper.
189
190
191 A note about the stupid context
192 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
193 Data types can have a context:
194         
195         data (Eq a, Ord b) => T a b = T1 a b | T2 a
196
197 and that makes the constructors have a context too
198 (notice that T2's context is "thinned"):
199
200         T1 :: (Eq a, Ord b) => a -> b -> T a b
201         T2 :: (Eq a) => a -> T a b
202
203 Furthermore, this context pops up when pattern matching
204 (though GHC hasn't implemented this, but it is in H98, and
205 I've fixed GHC so that it now does):
206
207         f (T2 x) = x
208 gets inferred type
209         f :: Eq a => T a b -> a
210
211 I say the context is "stupid" because the dictionaries passed
212 are immediately discarded -- they do nothing and have no benefit.
213 It's a flaw in the language.
214
215         Up to now [March 2002] I have put this stupid context into the
216         type of the "wrapper" constructors functions, T1 and T2, but
217         that turned out to be jolly inconvenient for generics, and
218         record update, and other functions that build values of type T
219         (because they don't have suitable dictionaries available).
220
221         So now I've taken the stupid context out.  I simply deal with
222         it separately in the type checker on occurrences of a
223         constructor, either in an expression or in a pattern.
224
225         [May 2003: actually I think this decision could evasily be
226         reversed now, and probably should be.  Generics could be
227         disabled for types with a stupid context; record updates now
228         (H98) needs the context too; etc.  It's an unforced change, so
229         I'm leaving it for now --- but it does seem odd that the
230         wrapper doesn't include the stupid context.]
231
232 [July 04] With the advent of generalised data types, it's less obvious
233 what the "stupid context" is.  Consider
234         C :: forall a. Ord a => a -> a -> T (Foo a)
235 Does the C constructor in Core contain the Ord dictionary?  Yes, it must:
236
237         f :: T b -> Ordering
238         f = /\b. \x:T b. 
239             case x of
240                 C a (d:Ord a) (p:a) (q:a) -> compare d p q
241
242 Note that (Foo a) might not be an instance of Ord.
243
244 %************************************************************************
245 %*                                                                      *
246 \subsection{Data constructors}
247 %*                                                                      *
248 %************************************************************************
249
250 \begin{code}
251 -- | A data constructor
252 data DataCon
253   = MkData {
254         dcName    :: Name,      -- This is the name of the *source data con*
255                                 -- (see "Note [Data Constructor Naming]" above)
256         dcUnique :: Unique,     -- Cached from Name
257         dcTag    :: ConTag,     -- ^ Tag, used for ordering 'DataCon's
258
259         -- Running example:
260         --
261         --      *** As declared by the user
262         --  data T a where
263         --    MkT :: forall x y. (x~y,Ord x) => x -> y -> T (x,y)
264
265         --      *** As represented internally
266         --  data T a where
267         --    MkT :: forall a. forall x y. (a~(x,y),x~y,Ord x) => x -> y -> T a
268         -- 
269         -- The next six fields express the type of the constructor, in pieces
270         -- e.g.
271         --
272         --      dcUnivTyVars  = [a]
273         --      dcExTyVars    = [x,y]
274         --      dcEqSpec      = [a~(x,y)]
275         --      dcOtherTheta  = [x~y, Ord x]    
276         --      dcOrigArgTys  = [a,List b]
277         --      dcRepTyCon       = T
278
279         dcVanilla :: Bool,      -- True <=> This is a vanilla Haskell 98 data constructor
280                                 --          Its type is of form
281                                 --              forall a1..an . t1 -> ... tm -> T a1..an
282                                 --          No existentials, no coercions, nothing.
283                                 -- That is: dcExTyVars = dcEqSpec = dcOtherTheta = []
284                 -- NB 1: newtypes always have a vanilla data con
285                 -- NB 2: a vanilla constructor can still be declared in GADT-style 
286                 --       syntax, provided its type looks like the above.
287                 --       The declaration format is held in the TyCon (algTcGadtSyntax)
288
289         dcUnivTyVars :: [TyVar],        -- Universally-quantified type vars [a,b,c]
290                                         -- INVARIANT: length matches arity of the dcRepTyCon
291                                         ---           result type of (rep) data con is exactly (T a b c)
292
293         dcExTyVars   :: [TyVar],        -- Existentially-quantified type vars 
294                 -- In general, the dcUnivTyVars are NOT NECESSARILY THE SAME AS THE TYVARS
295                 -- FOR THE PARENT TyCon. With GADTs the data con might not even have 
296                 -- the same number of type variables.
297                 -- [This is a change (Oct05): previously, vanilla datacons guaranteed to
298                 --  have the same type variables as their parent TyCon, but that seems ugly.]
299
300         -- INVARIANT: the UnivTyVars and ExTyVars all have distinct OccNames
301         -- Reason: less confusing, and easier to generate IfaceSyn
302
303         dcEqSpec :: [(TyVar,Type)],     -- Equalities derived from the result type, 
304                                         -- _as written by the programmer_
305                 -- This field allows us to move conveniently between the two ways
306                 -- of representing a GADT constructor's type:
307                 --      MkT :: forall a b. (a ~ [b]) => b -> T a
308                 --      MkT :: forall b. b -> T [b]
309                 -- Each equality is of the form (a ~ ty), where 'a' is one of 
310                 -- the universally quantified type variables
311                                         
312                 -- The next two fields give the type context of the data constructor
313                 --      (aside from the GADT constraints, 
314                 --       which are given by the dcExpSpec)
315                 -- In GADT form, this is *exactly* what the programmer writes, even if
316                 -- the context constrains only universally quantified variables
317                 --      MkT :: forall a b. (a ~ b, Ord b) => a -> T a b
318         dcOtherTheta :: ThetaType,  -- The other constraints in the data con's type
319                                     -- other than those in the dcEqSpec
320
321         dcStupidTheta :: ThetaType,     -- The context of the data type declaration 
322                                         --      data Eq a => T a = ...
323                                         -- or, rather, a "thinned" version thereof
324                 -- "Thinned", because the Report says
325                 -- to eliminate any constraints that don't mention
326                 -- tyvars free in the arg types for this constructor
327                 --
328                 -- INVARIANT: the free tyvars of dcStupidTheta are a subset of dcUnivTyVars
329                 -- Reason: dcStupidTeta is gotten by thinning the stupid theta from the tycon
330                 -- 
331                 -- "Stupid", because the dictionaries aren't used for anything.  
332                 -- Indeed, [as of March 02] they are no longer in the type of 
333                 -- the wrapper Id, because that makes it harder to use the wrap-id 
334                 -- to rebuild values after record selection or in generics.
335
336         dcOrigArgTys :: [Type],         -- Original argument types
337                                         -- (before unboxing and flattening of strict fields)
338         dcOrigResTy :: Type,            -- Original result type, as seen by the user
339                 -- NB: for a data instance, the original user result type may 
340                 -- differ from the DataCon's representation TyCon.  Example
341                 --      data instance T [a] where MkT :: a -> T [a]
342                 -- The OrigResTy is T [a], but the dcRepTyCon might be :T123
343
344         -- Now the strictness annotations and field labels of the constructor
345         dcStrictMarks :: [HsBang],
346                 -- Strictness annotations as decided by the compiler.  
347                 -- Does *not* include the existential dictionaries
348                 -- length = dataConSourceArity dataCon
349
350         dcFields  :: [FieldLabel],
351                 -- Field labels for this constructor, in the
352                 -- same order as the dcOrigArgTys; 
353                 -- length = 0 (if not a record) or dataConSourceArity.
354
355         -- Constructor representation
356         dcRepArgTys :: [Type],  -- Final, representation argument types, 
357                                 -- after unboxing and flattening,
358                                 -- and *including* all existential evidence args
359
360         dcRepStrictness :: [StrictnessMark],
361                 -- One for each *representation* *value* argument
362                 -- See also Note [Data-con worker strictness] in MkId.lhs
363
364         -- Result type of constructor is T t1..tn
365         dcRepTyCon  :: TyCon,           -- Result tycon, T
366
367         dcRepType   :: Type,    -- Type of the constructor
368                                 --      forall a x y. (a~(x,y), x~y, Ord x) =>
369                                 --        x -> y -> T a
370                                 -- (this is *not* of the constructor wrapper Id:
371                                 --  see Note [Data con representation] below)
372         -- Notice that the existential type parameters come *second*.  
373         -- Reason: in a case expression we may find:
374         --      case (e :: T t) of
375         --        MkT x y co1 co2 (d:Ord x) (v:r) (w:F s) -> ...
376         -- It's convenient to apply the rep-type of MkT to 't', to get
377         --      forall x y. (t~(x,y), x~y, Ord x) => x -> y -> T t
378         -- and use that to check the pattern.  Mind you, this is really only
379         -- used in CoreLint.
380
381
382         -- The curried worker function that corresponds to the constructor:
383         -- It doesn't have an unfolding; the code generator saturates these Ids
384         -- and allocates a real constructor when it finds one.
385         --
386         -- An entirely separate wrapper function is built in TcTyDecls
387         dcIds :: DataConIds,
388
389         dcInfix :: Bool         -- True <=> declared infix
390                                 -- Used for Template Haskell and 'deriving' only
391                                 -- The actual fixity is stored elsewhere
392   }
393   deriving Data.Typeable.Typeable
394
395 -- | Contains the Ids of the data constructor functions
396 data DataConIds
397   = DCIds (Maybe Id) Id         -- Algebraic data types always have a worker, and
398                                 -- may or may not have a wrapper, depending on whether
399                                 -- the wrapper does anything.  Newtypes just have a worker
400
401         -- _Neither_ the worker _nor_ the wrapper take the dcStupidTheta dicts as arguments
402
403         -- The wrapper takes dcOrigArgTys as its arguments
404         -- The worker takes dcRepArgTys as its arguments
405         -- If the worker is absent, dcRepArgTys is the same as dcOrigArgTys
406
407         -- The 'Nothing' case of DCIds is important
408         -- Not only is this efficient,
409         -- but it also ensures that the wrapper is replaced
410         -- by the worker (because it *is* the worker)
411         -- even when there are no args. E.g. in
412         --              f (:) x
413         -- the (:) *is* the worker.
414         -- This is really important in rule matching,
415         -- (We could match on the wrappers,
416         -- but that makes it less likely that rules will match
417         -- when we bring bits of unfoldings together.)
418
419 -- | Type of the tags associated with each constructor possibility
420 type ConTag = Int
421
422 fIRST_TAG :: ConTag
423 -- ^ Tags are allocated from here for real constructors
424 fIRST_TAG =  1
425 \end{code}
426
427 Note [Data con representation]
428 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
429 The dcRepType field contains the type of the representation of a contructor
430 This may differ from the type of the contructor *Id* (built
431 by MkId.mkDataConId) for two reasons:
432         a) the constructor Id may be overloaded, but the dictionary isn't stored
433            e.g.    data Eq a => T a = MkT a a
434
435         b) the constructor may store an unboxed version of a strict field.
436
437 Here's an example illustrating both:
438         data Ord a => T a = MkT Int! a
439 Here
440         T :: Ord a => Int -> a -> T a
441 but the rep type is
442         Trep :: Int# -> a -> T a
443 Actually, the unboxed part isn't implemented yet!
444
445
446 %************************************************************************
447 %*                                                                      *
448 \subsection{Instances}
449 %*                                                                      *
450 %************************************************************************
451
452 \begin{code}
453 instance Eq DataCon where
454     a == b = getUnique a == getUnique b
455     a /= b = getUnique a /= getUnique b
456
457 instance Ord DataCon where
458     a <= b = getUnique a <= getUnique b
459     a <  b = getUnique a <  getUnique b
460     a >= b = getUnique a >= getUnique b
461     a >  b = getUnique a > getUnique b
462     compare a b = getUnique a `compare` getUnique b
463
464 instance Uniquable DataCon where
465     getUnique = dcUnique
466
467 instance NamedThing DataCon where
468     getName = dcName
469
470 instance Outputable DataCon where
471     ppr con = ppr (dataConName con)
472
473 instance Show DataCon where
474     showsPrec p con = showsPrecSDoc p (ppr con)
475
476 instance Data.Data DataCon where
477     -- don't traverse?
478     toConstr _   = abstractConstr "DataCon"
479     gunfold _ _  = error "gunfold"
480     dataTypeOf _ = mkNoRepType "DataCon"
481 \end{code}
482
483
484 %************************************************************************
485 %*                                                                      *
486 \subsection{Construction}
487 %*                                                                      *
488 %************************************************************************
489
490 \begin{code}
491 -- | Build a new data constructor
492 mkDataCon :: Name 
493           -> Bool               -- ^ Is the constructor declared infix?
494           -> [HsBang]           -- ^ Strictness annotations written in the source file
495           -> [FieldLabel]       -- ^ Field labels for the constructor, if it is a record, 
496                                 --   otherwise empty
497           -> [TyVar]            -- ^ Universally quantified type variables
498           -> [TyVar]            -- ^ Existentially quantified type variables
499           -> [(TyVar,Type)]     -- ^ GADT equalities
500           -> ThetaType          -- ^ Theta-type occuring before the arguments proper
501           -> [Type]             -- ^ Original argument types
502           -> Type               -- ^ Original result type
503           -> TyCon              -- ^ Representation type constructor
504           -> ThetaType          -- ^ The "stupid theta", context of the data declaration 
505                                 --   e.g. @data Eq a => T a ...@
506           -> DataConIds         -- ^ The Ids of the actual builder functions
507           -> DataCon
508   -- Can get the tag from the TyCon
509
510 mkDataCon name declared_infix
511           arg_stricts   -- Must match orig_arg_tys 1-1
512           fields
513           univ_tvs ex_tvs 
514           eq_spec theta
515           orig_arg_tys orig_res_ty rep_tycon
516           stupid_theta ids
517 -- Warning: mkDataCon is not a good place to check invariants. 
518 -- If the programmer writes the wrong result type in the decl, thus:
519 --      data T a where { MkT :: S }
520 -- then it's possible that the univ_tvs may hit an assertion failure
521 -- if you pull on univ_tvs.  This case is checked by checkValidDataCon,
522 -- so the error is detected properly... it's just that asaertions here
523 -- are a little dodgy.
524
525   = -- ASSERT( not (any isEqPred theta) )
526         -- We don't currently allow any equality predicates on
527         -- a data constructor (apart from the GADT ones in eq_spec)
528     con
529   where
530     is_vanilla = null ex_tvs && null eq_spec && null theta
531     con = MkData {dcName = name, dcUnique = nameUnique name, 
532                   dcVanilla = is_vanilla, dcInfix = declared_infix,
533                   dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs, 
534                   dcEqSpec = eq_spec, 
535                   dcOtherTheta = theta,
536                   dcStupidTheta = stupid_theta, 
537                   dcOrigArgTys = orig_arg_tys, dcOrigResTy = orig_res_ty,
538                   dcRepTyCon = rep_tycon, 
539                   dcRepArgTys = rep_arg_tys,
540                   dcStrictMarks = arg_stricts, 
541                   dcRepStrictness = rep_arg_stricts,
542                   dcFields = fields, dcTag = tag, dcRepType = ty,
543                   dcIds = ids }
544
545         -- Strictness marks for source-args
546         --      *after unboxing choices*, 
547         -- but  *including existential dictionaries*
548         -- 
549         -- The 'arg_stricts' passed to mkDataCon are simply those for the
550         -- source-language arguments.  We add extra ones for the
551         -- dictionary arguments right here.
552     full_theta   = eqSpecPreds eq_spec ++ theta
553     real_arg_tys = full_theta                         ++ orig_arg_tys
554     real_stricts = map mk_pred_strict_mark full_theta ++ arg_stricts
555
556         -- Representation arguments and demands
557         -- To do: eliminate duplication with MkId
558     (rep_arg_stricts, rep_arg_tys) = computeRep real_stricts real_arg_tys
559
560     tag = assoc "mkDataCon" (tyConDataCons rep_tycon `zip` [fIRST_TAG..]) con
561     ty  = mkForAllTys univ_tvs $ mkForAllTys ex_tvs $ 
562           mkFunTys rep_arg_tys $
563           mkTyConApp rep_tycon (mkTyVarTys univ_tvs)
564
565 eqSpecPreds :: [(TyVar,Type)] -> ThetaType
566 eqSpecPreds spec = [ mkEqPred (mkTyVarTy tv, ty) | (tv,ty) <- spec ]
567
568 mk_pred_strict_mark :: PredType -> HsBang
569 mk_pred_strict_mark pred 
570   | isEqPred pred = HsUnpack    -- Note [Unpack equality predicates]
571   | otherwise     = HsNoBang
572 \end{code}
573
574 Note [Unpack equality predicates]
575 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
576 If we have a GADT with a contructor C :: (a~[b]) => b -> T a
577 we definitely want that equality predicate *unboxed* so that it
578 takes no space at all.  This is easily done: just give it
579 an UNPACK pragma. The rest of the unpack/repack code does the
580 heavy lifting.  This one line makes every GADT take a word less
581 space for each equality predicate, so it's pretty important!
582
583 \begin{code}
584 -- | The 'Name' of the 'DataCon', giving it a unique, rooted identification
585 dataConName :: DataCon -> Name
586 dataConName = dcName
587
588 -- | The tag used for ordering 'DataCon's
589 dataConTag :: DataCon -> ConTag
590 dataConTag  = dcTag
591
592 -- | The type constructor that we are building via this data constructor
593 dataConTyCon :: DataCon -> TyCon
594 dataConTyCon = dcRepTyCon
595
596 -- | The original type constructor used in the definition of this data
597 -- constructor.  In case of a data family instance, that will be the family
598 -- type constructor.
599 dataConOrigTyCon :: DataCon -> TyCon
600 dataConOrigTyCon dc 
601   | Just (tc, _) <- tyConFamInst_maybe (dcRepTyCon dc) = tc
602   | otherwise                                          = dcRepTyCon dc
603
604 -- | The representation type of the data constructor, i.e. the sort
605 -- type that will represent values of this type at runtime
606 dataConRepType :: DataCon -> Type
607 dataConRepType = dcRepType
608
609 -- | Should the 'DataCon' be presented infix?
610 dataConIsInfix :: DataCon -> Bool
611 dataConIsInfix = dcInfix
612
613 -- | The universally-quantified type variables of the constructor
614 dataConUnivTyVars :: DataCon -> [TyVar]
615 dataConUnivTyVars = dcUnivTyVars
616
617 -- | The existentially-quantified type variables of the constructor
618 dataConExTyVars :: DataCon -> [TyVar]
619 dataConExTyVars = dcExTyVars
620
621 -- | Both the universal and existentiatial type variables of the constructor
622 dataConAllTyVars :: DataCon -> [TyVar]
623 dataConAllTyVars (MkData { dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs })
624   = univ_tvs ++ ex_tvs
625
626 -- | Equalities derived from the result type of the data constructor, as written
627 -- by the programmer in any GADT declaration
628 dataConEqSpec :: DataCon -> [(TyVar,Type)]
629 dataConEqSpec = dcEqSpec
630
631 -- | The *full* constraints on the constructor type
632 dataConTheta :: DataCon -> ThetaType
633 dataConTheta (MkData { dcEqSpec = eq_spec, dcOtherTheta = theta }) 
634   = eqSpecPreds eq_spec ++ theta
635
636 -- | Get the Id of the 'DataCon' worker: a function that is the "actual"
637 -- constructor and has no top level binding in the program. The type may
638 -- be different from the obvious one written in the source program. Panics
639 -- if there is no such 'Id' for this 'DataCon'
640 dataConWorkId :: DataCon -> Id
641 dataConWorkId dc = case dcIds dc of
642                         DCIds _ wrk_id -> wrk_id
643
644 -- | Get the Id of the 'DataCon' wrapper: a function that wraps the "actual"
645 -- constructor so it has the type visible in the source program: c.f. 'dataConWorkId'.
646 -- Returns Nothing if there is no wrapper, which occurs for an algebraic data constructor 
647 -- and also for a newtype (whose constructor is inlined compulsorily)
648 dataConWrapId_maybe :: DataCon -> Maybe Id
649 dataConWrapId_maybe dc = case dcIds dc of
650                                 DCIds mb_wrap _ -> mb_wrap
651
652 -- | Returns an Id which looks like the Haskell-source constructor by using
653 -- the wrapper if it exists (see 'dataConWrapId_maybe') and failing over to
654 -- the worker (see 'dataConWorkId')
655 dataConWrapId :: DataCon -> Id
656 dataConWrapId dc = case dcIds dc of
657                         DCIds (Just wrap) _   -> wrap
658                         DCIds Nothing     wrk -> wrk        -- worker=wrapper
659
660 -- | Find all the 'Id's implicitly brought into scope by the data constructor. Currently,
661 -- the union of the 'dataConWorkId' and the 'dataConWrapId'
662 dataConImplicitIds :: DataCon -> [Id]
663 dataConImplicitIds dc = case dcIds dc of
664                           DCIds (Just wrap) work -> [wrap,work]
665                           DCIds Nothing     work -> [work]
666
667 -- | The labels for the fields of this particular 'DataCon'
668 dataConFieldLabels :: DataCon -> [FieldLabel]
669 dataConFieldLabels = dcFields
670
671 -- | Extract the type for any given labelled field of the 'DataCon'
672 dataConFieldType :: DataCon -> FieldLabel -> Type
673 dataConFieldType con label
674   = case lookup label (dcFields con `zip` dcOrigArgTys con) of
675       Just ty -> ty
676       Nothing -> pprPanic "dataConFieldType" (ppr con <+> ppr label)
677
678 -- | The strictness markings decided on by the compiler.  Does not include those for
679 -- existential dictionaries.  The list is in one-to-one correspondence with the arity of the 'DataCon'
680 dataConStrictMarks :: DataCon -> [HsBang]
681 dataConStrictMarks = dcStrictMarks
682
683 -- | Strictness of evidence arguments to the wrapper function
684 dataConExStricts :: DataCon -> [HsBang]
685 -- Usually empty, so we don't bother to cache this
686 dataConExStricts dc = map mk_pred_strict_mark (dataConTheta dc)
687
688 -- | Source-level arity of the data constructor
689 dataConSourceArity :: DataCon -> Arity
690 dataConSourceArity dc = length (dcOrigArgTys dc)
691
692 -- | Gives the number of actual fields in the /representation/ of the 
693 -- data constructor. This may be more than appear in the source code;
694 -- the extra ones are the existentially quantified dictionaries
695 dataConRepArity :: DataCon -> Int
696 dataConRepArity (MkData {dcRepArgTys = arg_tys}) = length arg_tys
697
698 -- | Return whether there are any argument types for this 'DataCon's original source type
699 isNullarySrcDataCon :: DataCon -> Bool
700 isNullarySrcDataCon dc = null (dcOrigArgTys dc)
701
702 -- | Return whether there are any argument types for this 'DataCon's runtime representation type
703 isNullaryRepDataCon :: DataCon -> Bool
704 isNullaryRepDataCon dc = null (dcRepArgTys dc)
705
706 dataConRepStrictness :: DataCon -> [StrictnessMark]
707 -- ^ Give the demands on the arguments of a
708 -- Core constructor application (Con dc args)
709 dataConRepStrictness dc = dcRepStrictness dc
710
711 -- | The \"signature\" of the 'DataCon' returns, in order:
712 --
713 -- 1) The result of 'dataConAllTyVars',
714 --
715 -- 2) All the 'ThetaType's relating to the 'DataCon' (coercion, dictionary, implicit
716 --    parameter - whatever)
717 --
718 -- 3) The type arguments to the constructor
719 --
720 -- 4) The /original/ result type of the 'DataCon'
721 dataConSig :: DataCon -> ([TyVar], ThetaType, [Type], Type)
722 dataConSig (MkData {dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs, 
723                     dcEqSpec = eq_spec, dcOtherTheta  = theta, 
724                     dcOrigArgTys = arg_tys, dcOrigResTy = res_ty})
725   = (univ_tvs ++ ex_tvs, eqSpecPreds eq_spec ++ theta, arg_tys, res_ty)
726
727 -- | The \"full signature\" of the 'DataCon' returns, in order:
728 --
729 -- 1) The result of 'dataConUnivTyVars'
730 --
731 -- 2) The result of 'dataConExTyVars'
732 --
733 -- 3) The result of 'dataConEqSpec'
734 --
735 -- 4) The result of 'dataConDictTheta'
736 --
737 -- 5) The original argument types to the 'DataCon' (i.e. before 
738 --    any change of the representation of the type)
739 --
740 -- 6) The original result type of the 'DataCon'
741 dataConFullSig :: DataCon 
742                -> ([TyVar], [TyVar], [(TyVar,Type)], ThetaType, [Type], Type)
743 dataConFullSig (MkData {dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs, 
744                         dcEqSpec = eq_spec, dcOtherTheta = theta,
745                         dcOrigArgTys = arg_tys, dcOrigResTy = res_ty})
746   = (univ_tvs, ex_tvs, eq_spec, theta, arg_tys, res_ty)
747
748 dataConOrigResTy :: DataCon -> Type
749 dataConOrigResTy dc = dcOrigResTy dc
750
751 -- | The \"stupid theta\" of the 'DataCon', such as @data Eq a@ in:
752 --
753 -- > data Eq a => T a = ...
754 dataConStupidTheta :: DataCon -> ThetaType
755 dataConStupidTheta dc = dcStupidTheta dc
756
757 dataConUserType :: DataCon -> Type
758 -- ^ The user-declared type of the data constructor
759 -- in the nice-to-read form:
760 --
761 -- > T :: forall a b. a -> b -> T [a]
762 --
763 -- rather than:
764 --
765 -- > T :: forall a c. forall b. (c~[a]) => a -> b -> T c
766 --
767 -- NB: If the constructor is part of a data instance, the result type
768 -- mentions the family tycon, not the internal one.
769 dataConUserType  (MkData { dcUnivTyVars = univ_tvs, 
770                            dcExTyVars = ex_tvs, dcEqSpec = eq_spec,
771                            dcOtherTheta = theta, dcOrigArgTys = arg_tys,
772                            dcOrigResTy = res_ty })
773   = mkForAllTys ((univ_tvs `minusList` map fst eq_spec) ++ ex_tvs) $
774     mkFunTys theta $
775     mkFunTys arg_tys $
776     res_ty
777
778 -- | Finds the instantiated types of the arguments required to construct a 'DataCon' representation
779 -- NB: these INCLUDE any dictionary args
780 --     but EXCLUDE the data-declaration context, which is discarded
781 -- It's all post-flattening etc; this is a representation type
782 dataConInstArgTys :: DataCon    -- ^ A datacon with no existentials or equality constraints
783                                 -- However, it can have a dcTheta (notably it can be a 
784                                 -- class dictionary, with superclasses)
785                   -> [Type]     -- ^ Instantiated at these types
786                   -> [Type]
787 dataConInstArgTys dc@(MkData {dcRepArgTys = rep_arg_tys, 
788                               dcUnivTyVars = univ_tvs, dcEqSpec = eq_spec,
789                               dcExTyVars = ex_tvs}) inst_tys
790  = ASSERT2 ( length univ_tvs == length inst_tys 
791            , ptext (sLit "dataConInstArgTys") <+> ppr dc $$ ppr univ_tvs $$ ppr inst_tys)
792    ASSERT2 ( null ex_tvs && null eq_spec, ppr dc )        
793    map (substTyWith univ_tvs inst_tys) rep_arg_tys
794
795 -- | Returns just the instantiated /value/ argument types of a 'DataCon',
796 -- (excluding dictionary args)
797 dataConInstOrigArgTys 
798         :: DataCon      -- Works for any DataCon
799         -> [Type]       -- Includes existential tyvar args, but NOT
800                         -- equality constraints or dicts
801         -> [Type]
802 -- For vanilla datacons, it's all quite straightforward
803 -- But for the call in MatchCon, we really do want just the value args
804 dataConInstOrigArgTys dc@(MkData {dcOrigArgTys = arg_tys,
805                                   dcUnivTyVars = univ_tvs, 
806                                   dcExTyVars = ex_tvs}) inst_tys
807   = ASSERT2( length tyvars == length inst_tys
808           , ptext (sLit "dataConInstOrigArgTys") <+> ppr dc $$ ppr tyvars $$ ppr inst_tys )
809     map (substTyWith tyvars inst_tys) arg_tys
810   where
811     tyvars = univ_tvs ++ ex_tvs
812 \end{code}
813
814 \begin{code}
815 -- | Returns the argument types of the wrapper, excluding all dictionary arguments
816 -- and without substituting for any type variables
817 dataConOrigArgTys :: DataCon -> [Type]
818 dataConOrigArgTys dc = dcOrigArgTys dc
819
820 -- | Returns the arg types of the worker, including all dictionaries, after any 
821 -- flattening has been done and without substituting for any type variables
822 dataConRepArgTys :: DataCon -> [Type]
823 dataConRepArgTys dc = dcRepArgTys dc
824 \end{code}
825
826 \begin{code}
827 -- | The string @package:module.name@ identifying a constructor, which is attached
828 -- to its info table and used by the GHCi debugger and the heap profiler
829 dataConIdentity :: DataCon -> [Word8]
830 -- We want this string to be UTF-8, so we get the bytes directly from the FastStrings.
831 dataConIdentity dc = bytesFS (packageIdFS (modulePackageId mod)) ++ 
832                   fromIntegral (ord ':') : bytesFS (moduleNameFS (moduleName mod)) ++
833                   fromIntegral (ord '.') : bytesFS (occNameFS (nameOccName name))
834   where name = dataConName dc
835         mod  = ASSERT( isExternalName name ) nameModule name
836 \end{code}
837
838 \begin{code}
839 isTupleCon :: DataCon -> Bool
840 isTupleCon (MkData {dcRepTyCon = tc}) = isTupleTyCon tc
841         
842 isUnboxedTupleCon :: DataCon -> Bool
843 isUnboxedTupleCon (MkData {dcRepTyCon = tc}) = isUnboxedTupleTyCon tc
844
845 -- | Vanilla 'DataCon's are those that are nice boring Haskell 98 constructors
846 isVanillaDataCon :: DataCon -> Bool
847 isVanillaDataCon dc = dcVanilla dc
848 \end{code}
849
850 \begin{code}
851 classDataCon :: Class -> DataCon
852 classDataCon clas = case tyConDataCons (classTyCon clas) of
853                       (dict_constr:no_more) -> ASSERT( null no_more ) dict_constr 
854                       [] -> panic "classDataCon"
855 \end{code}
856
857 \begin{code}
858 dataConCannotMatch :: [Type] -> DataCon -> Bool
859 -- Returns True iff the data con *definitely cannot* match a 
860 --                  scrutinee of type (T tys)
861 --                  where T is the type constructor for the data con
862 -- NB: look at *all* equality constraints, not only those
863 --     in dataConEqSpec; see Trac #5168
864 dataConCannotMatch tys con
865   | null theta        = False   -- Common
866   | all isTyVarTy tys = False   -- Also common
867   | otherwise
868   = typesCantMatch [(Type.substTy subst ty1, Type.substTy subst ty2)
869                    | (ty1, ty2) <- concatMap predEqs theta ]
870   where
871     dc_tvs  = dataConUnivTyVars con
872     theta   = dataConTheta con
873     subst   = zipTopTvSubst dc_tvs tys
874
875     -- TODO: could gather equalities from superclasses too
876     predEqs pred = case classifyPredType pred of
877                      EqPred ty1 ty2 -> [(ty1, ty2)]
878                      TuplePred ts   -> concatMap predEqs ts
879                      _              -> []
880 \end{code}
881
882 %************************************************************************
883 %*                                                                      *
884 \subsection{Splitting products}
885 %*                                                                      *
886 %************************************************************************
887
888 \begin{code}
889 -- | Extract the type constructor, type argument, data constructor and it's
890 -- /representation/ argument types from a type if it is a product type.
891 --
892 -- Precisely, we return @Just@ for any type that is all of:
893 --
894 --  * Concrete (i.e. constructors visible)
895 --
896 --  * Single-constructor
897 --
898 --  * Not existentially quantified
899 --
900 -- Whether the type is a @data@ type or a @newtype@
901 splitProductType_maybe
902         :: Type                         -- ^ A product type, perhaps
903         -> Maybe (TyCon,                -- The type constructor
904                   [Type],               -- Type args of the tycon
905                   DataCon,              -- The data constructor
906                   [Type])               -- Its /representation/ arg types
907
908         -- Rejecing existentials is conservative.  Maybe some things
909         -- could be made to work with them, but I'm not going to sweat
910         -- it through till someone finds it's important.
911
912 splitProductType_maybe ty
913   = case splitTyConApp_maybe ty of
914         Just (tycon,ty_args)
915            | isProductTyCon tycon       -- Includes check for non-existential,
916                                         -- and for constructors visible
917            -> Just (tycon, ty_args, data_con, dataConInstArgTys data_con ty_args)
918            where
919               data_con = ASSERT( not (null (tyConDataCons tycon)) ) 
920                          head (tyConDataCons tycon)
921         _other -> Nothing
922
923 -- | As 'splitProductType_maybe', but panics if the 'Type' is not a product type
924 splitProductType :: String -> Type -> (TyCon, [Type], DataCon, [Type])
925 splitProductType str ty
926   = case splitProductType_maybe ty of
927         Just stuff -> stuff
928         Nothing    -> pprPanic (str ++ ": not a product") (pprType ty)
929
930
931 -- | As 'splitProductType_maybe', but in turn instantiates the 'TyCon' returned
932 -- and hence recursively tries to unpack it as far as it able to
933 deepSplitProductType_maybe :: Type -> Maybe (TyCon, [Type], DataCon, [Type])
934 deepSplitProductType_maybe ty
935   = do { (res@(tycon, tycon_args, _, _)) <- splitProductType_maybe ty
936        ; let {result 
937              | Just (ty', _co) <- instNewTyCon_maybe tycon tycon_args
938              , not (isRecursiveTyCon tycon)
939              = deepSplitProductType_maybe ty'   -- Ignore the coercion?
940              | isNewTyCon tycon = Nothing  -- cannot unbox through recursive
941                                            -- newtypes nor through families
942              | otherwise = Just res}
943        ; result
944        }
945
946 -- | As 'deepSplitProductType_maybe', but panics if the 'Type' is not a product type
947 deepSplitProductType :: String -> Type -> (TyCon, [Type], DataCon, [Type])
948 deepSplitProductType str ty 
949   = case deepSplitProductType_maybe ty of
950       Just stuff -> stuff
951       Nothing -> pprPanic (str ++ ": not a product") (pprType ty)
952
953 -- | Compute the representation type strictness and type suitable for a 'DataCon'
954 computeRep :: [HsBang]                  -- ^ Original argument strictness
955            -> [Type]                    -- ^ Original argument types
956            -> ([StrictnessMark],        -- Representation arg strictness
957                [Type])                  -- And type
958
959 computeRep stricts tys
960   = unzip $ concat $ zipWithEqual "computeRep" unbox stricts tys
961   where
962     unbox HsNoBang       ty = [(NotMarkedStrict, ty)]
963     unbox HsStrict       ty = [(MarkedStrict,    ty)]
964     unbox HsNoUnpack     ty = [(MarkedStrict,    ty)]
965     unbox HsUnpackFailed ty = [(MarkedStrict,    ty)]
966     unbox HsUnpack ty = zipEqual "computeRep" (dataConRepStrictness arg_dc) arg_tys
967                       where
968                         (_tycon, _tycon_args, arg_dc, arg_tys) 
969                            = deepSplitProductType "unbox_strict_arg_ty" ty
970 \end{code}
971
972
973 %************************************************************************
974 %*                                                                      *
975         Promoting of data types to the kind level
976 %*                                                                      *
977 %************************************************************************
978
979 These two 'buildPromoted..' functions are here because
980  * They belong together
981  * 'buildPromotedTyCon' is used by promoteType
982  * 'buildPromotedTyCon' depends on DataCon stuff
983
984 \begin{code}
985 buildPromotedTyCon :: TyCon -> TyCon
986 buildPromotedTyCon tc
987   = mkPromotedTyCon tc (promoteKind (tyConKind tc))
988
989 buildPromotedDataCon :: DataCon -> TyCon
990 buildPromotedDataCon dc 
991   = ASSERT ( isPromotableType ty )
992     mkPromotedDataTyCon dc (getName dc) (getUnique dc) kind arity
993   where 
994     ty    = dataConUserType dc
995     kind  = promoteType ty
996     arity = dataConSourceArity dc
997 \end{code}
998
999 Note [Promoting a Type to a Kind]
1000 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1001 Suppsoe we have a data constructor D
1002      D :: forall (a:*). Maybe a -> T a
1003 We promote this to be a type constructor 'D:
1004      'D :: forall (k:BOX). 'Maybe k -> 'T k
1005
1006 The transformation from type to kind is done by promoteType
1007
1008   * Convert forall (a:*) to forall (k:BOX), and substitute
1009
1010   * Ensure all foralls are at the top (no higher rank stuff)
1011
1012   * Ensure that all type constructors mentioned (Maybe and T
1013     in the example) are promotable; that is, they have kind 
1014           * -> ... -> * -> *
1015
1016 \begin{code}
1017 isPromotableType :: Type -> Bool
1018 isPromotableType ty
1019   = all (isLiftedTypeKind . tyVarKind) tvs
1020     && go rho
1021   where
1022     (tvs, rho) = splitForAllTys ty
1023     go (TyConApp tc tys) | Just n <- isPromotableTyCon tc
1024                          = tys `lengthIs` n && all go tys
1025     go (FunTy arg res)   = go arg && go res
1026     go (TyVarTy tvar)    = tvar `elem` tvs
1027     go _                 = False
1028
1029 -- If tc's kind is [ *^n -> * ] returns [ Just n ], else returns [ Nothing ]
1030 isPromotableTyCon :: TyCon -> Maybe Int
1031 isPromotableTyCon tc
1032   | all isLiftedTypeKind (res:args) = Just $ length args
1033   | otherwise                       = Nothing
1034   where
1035     (args, res) = splitKindFunTys (tyConKind tc)
1036
1037 -- | Promotes a type to a kind. 
1038 -- Assumes the argument satisfies 'isPromotableType'
1039 promoteType :: Type -> Kind
1040 promoteType ty
1041   = mkForAllTys kvs (go rho)
1042   where
1043     (tvs, rho) = splitForAllTys ty
1044     kvs = [ mkKindVar (tyVarName tv) superKind | tv <- tvs ]
1045     env = zipVarEnv tvs kvs
1046
1047     go (TyConApp tc tys) = mkTyConApp (buildPromotedTyCon tc) (map go tys)
1048     go (FunTy arg res)   = mkArrowKind (go arg) (go res)
1049     go (TyVarTy tv)      | Just kv <- lookupVarEnv env tv 
1050                          = TyVarTy kv
1051     go _ = panic "promoteType"  -- Argument did not satisfy isPromotableType
1052
1053 promoteKind :: Kind -> SuperKind
1054 -- Promote the kind of a type constructor
1055 -- from (* -> * -> *) to (BOX -> BOX -> BOX) 
1056 promoteKind (TyConApp tc []) 
1057   | tc `hasKey` liftedTypeKindTyConKey = superKind
1058 promoteKind (FunTy arg res) = FunTy (promoteKind arg) (promoteKind res)
1059 promoteKind k = pprPanic "promoteKind" (ppr k)
1060 \end{code}