Comments only
[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, DataConRep(..), HsBang(..), StrictnessMark(..),
18         ConTag,
19         
20         -- ** Type construction
21         mkDataCon, fIRST_TAG,
22         buildAlgTyCon, 
23         
24         -- ** Type deconstruction
25         dataConRepType, dataConSig, dataConFullSig,
26         dataConName, dataConIdentity, dataConTag, dataConTyCon, 
27         dataConOrigTyCon, dataConUserType,
28         dataConUnivTyVars, dataConExTyVars, dataConAllTyVars, 
29         dataConEqSpec, eqSpecPreds, dataConTheta,
30         dataConStupidTheta,  
31         dataConInstArgTys, dataConOrigArgTys, dataConOrigResTy,
32         dataConInstOrigArgTys, dataConRepArgTys, 
33         dataConFieldLabels, dataConFieldType,
34         dataConStrictMarks, 
35         dataConSourceArity, dataConRepArity, dataConRepRepArity,
36         dataConIsInfix,
37         dataConWorkId, dataConWrapId, dataConWrapId_maybe, dataConImplicitIds,
38         dataConRepStrictness, dataConRepBangs, dataConBoxer,
39         
40         -- ** Predicates on DataCons
41         isNullarySrcDataCon, isNullaryRepDataCon, isTupleDataCon, isUnboxedTupleCon,
42         isVanillaDataCon, classDataCon, dataConCannotMatch,
43         isBanged, isMarkedStrict, eqHsBang,
44
45         -- ** Promotion related functions
46         promoteKind, promoteDataCon, promoteDataCon_maybe
47     ) where
48
49 #include "HsVersions.h"
50
51 import {-# SOURCE #-} MkId( DataConBoxer )
52 import Type
53 import TypeRep( Type(..) )  -- Used in promoteType
54 import PrelNames( liftedTypeKindTyConKey )
55 import ForeignCall( CType )
56 import Coercion
57 import Kind
58 import Unify
59 import TyCon
60 import Class
61 import Name
62 import Var
63 import Outputable
64 import Unique
65 import ListSetOps
66 import Util
67 import BasicTypes
68 import FastString
69 import Module
70 import VarEnv
71
72 import qualified Data.Data as Data
73 import qualified Data.Typeable
74 import Data.Maybe
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  = [x,y]
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         -- See Note [Bangs on data constructor arguments]
346         dcArgBangs :: [HsBang],
347                 -- Strictness annotations as decided by the compiler.  
348                 -- Matches 1-1 with dcOrigArgTys
349                 -- Hence length = dataConSourceArity dataCon
350
351         dcFields  :: [FieldLabel],
352                 -- Field labels for this constructor, in the
353                 -- same order as the dcOrigArgTys; 
354                 -- length = 0 (if not a record) or dataConSourceArity.
355
356         -- The curried worker function that corresponds to the constructor:
357         -- It doesn't have an unfolding; the code generator saturates these Ids
358         -- and allocates a real constructor when it finds one.
359         dcWorkId :: Id,
360
361         -- Constructor representation
362         dcRep      :: DataConRep,
363
364         -- Cached
365         dcRepArity    :: Arity,  -- == length dataConRepArgTys
366         dcSourceArity :: Arity,  -- == length dcOrigArgTys
367
368         -- Result type of constructor is T t1..tn
369         dcRepTyCon  :: TyCon,           -- Result tycon, T
370
371         dcRepType   :: Type,    -- Type of the constructor
372                                 --      forall a x y. (a~(x,y), x~y, Ord x) =>
373                                 --        x -> y -> T a
374                                 -- (this is *not* of the constructor wrapper Id:
375                                 --  see Note [Data con representation] below)
376         -- Notice that the existential type parameters come *second*.  
377         -- Reason: in a case expression we may find:
378         --      case (e :: T t) of
379         --        MkT x y co1 co2 (d:Ord x) (v:r) (w:F s) -> ...
380         -- It's convenient to apply the rep-type of MkT to 't', to get
381         --      forall x y. (t~(x,y), x~y, Ord x) => x -> y -> T t
382         -- and use that to check the pattern.  Mind you, this is really only
383         -- used in CoreLint.
384
385
386         dcInfix :: Bool,        -- True <=> declared infix
387                                 -- Used for Template Haskell and 'deriving' only
388                                 -- The actual fixity is stored elsewhere
389
390         dcPromoted :: Maybe TyCon    -- The promoted TyCon if this DataCon is promotable
391                                      -- See Note [Promoted data constructors] in TyCon
392   }
393   deriving Data.Typeable.Typeable
394
395 data DataConRep 
396   = NoDataConRep              -- No wrapper
397
398   | DCR { dcr_wrap_id :: Id   -- Takes src args, unboxes/flattens, 
399                               -- and constructs the representation
400
401         , dcr_boxer   :: DataConBoxer
402
403         , dcr_arg_tys :: [Type]  -- Final, representation argument types, 
404                                  -- after unboxing and flattening,
405                                  -- and *including* all evidence args
406
407         , dcr_stricts :: [StrictnessMark]  -- 1-1 with dcr_arg_tys
408                 -- See also Note [Data-con worker strictness] in MkId.lhs
409
410         , dcr_bangs :: [HsBang]  -- The actual decisions made (including failures)
411                                  -- 1-1 with orig_arg_tys
412                                  -- See Note [Bangs on data constructor arguments]
413
414     }
415 -- Algebraic data types always have a worker, and
416 -- may or may not have a wrapper, depending on whether
417 -- the wrapper does anything.  
418 --
419 -- Data types have a worker with no unfolding
420 -- Newtypes just have a worker, which has a compulsory unfolding (just a cast)
421
422 -- _Neither_ the worker _nor_ the wrapper take the dcStupidTheta dicts as arguments
423
424 -- The wrapper (if it exists) takes dcOrigArgTys as its arguments
425 -- The worker takes dataConRepArgTys as its arguments
426 -- If the worker is absent, dataConRepArgTys is the same as dcOrigArgTys
427
428 -- The 'NoDataConRep' case is important
429 -- Not only is this efficient,
430 -- but it also ensures that the wrapper is replaced
431 -- by the worker (because it *is* the worker)
432 -- even when there are no args. E.g. in
433 --              f (:) x
434 -- the (:) *is* the worker.
435 -- This is really important in rule matching,
436 -- (We could match on the wrappers,
437 -- but that makes it less likely that rules will match
438 -- when we bring bits of unfoldings together.)
439
440 -------------------------
441 -- HsBang describes what the *programmer* wrote
442 -- This info is retained in the DataCon.dcStrictMarks field
443 data HsBang 
444   = HsUserBang   -- The user's source-code request
445        (Maybe Bool)       -- Just True    {-# UNPACK #-}
446                           -- Just False   {-# NOUNPACK #-}
447                           -- Nothing      no pragma
448        Bool               -- True <=> '!' specified
449
450   | HsNoBang              -- Lazy field
451                           -- HsUserBang Nothing False means the same as HsNoBang
452
453   | HsUnpack              -- Definite commitment: this field is strict and unboxed
454        (Maybe Coercion)   --    co :: arg-ty ~ product-ty
455
456   | HsStrict              -- Definite commitment: this field is strict but not unboxed
457   deriving (Data.Data, Data.Typeable)
458
459 -------------------------
460 -- StrictnessMark is internal only, used to indicate strictness 
461 -- of the DataCon *worker* fields
462 data StrictnessMark = MarkedStrict | NotMarkedStrict    
463 \end{code}
464
465 Note [Data con representation]
466 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
467 The dcRepType field contains the type of the representation of a contructor
468 This may differ from the type of the contructor *Id* (built
469 by MkId.mkDataConId) for two reasons:
470         a) the constructor Id may be overloaded, but the dictionary isn't stored
471            e.g.    data Eq a => T a = MkT a a
472
473         b) the constructor may store an unboxed version of a strict field.
474
475 Here's an example illustrating both:
476         data Ord a => T a = MkT Int! a
477 Here
478         T :: Ord a => Int -> a -> T a
479 but the rep type is
480         Trep :: Int# -> a -> T a
481 Actually, the unboxed part isn't implemented yet!
482
483 Note [Bangs on data constructor arguments]
484 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
485 Consider
486   data T = MkT !Int {-# UNPACK #-} !Int Bool
487 Its dcArgBangs field records the *users* specifications, in this case
488     [ HsUserBang Nothing True
489     , HsUserBang (Just True) True
490     , HsNoBang]
491 See the declaration of HsBang in BasicTypes
492
493 The dcr_bangs field of the dcRep field records the *actual, decided*
494 representation of the data constructor.  Without -O this might be
495     [HsStrict, HsStrict, HsNoBang]
496 With -O it might be
497     [HsStrict, HsUnpack, HsNoBang]
498 With -funbox-small-strict-fields it might be
499     [HsUnpack, HsUnpack, HsNoBang]
500
501 For imported data types, the dcArgBangs field is just the same as the
502 dcr_bangs field; we don't know what the user originally said.
503
504
505 %************************************************************************
506 %*                                                                      *
507 \subsection{Instances}
508 %*                                                                      *
509 %************************************************************************
510
511 \begin{code}
512 instance Eq DataCon where
513     a == b = getUnique a == getUnique b
514     a /= b = getUnique a /= getUnique b
515
516 instance Ord DataCon where
517     a <= b = getUnique a <= getUnique b
518     a <  b = getUnique a <  getUnique b
519     a >= b = getUnique a >= getUnique b
520     a >  b = getUnique a > getUnique b
521     compare a b = getUnique a `compare` getUnique b
522
523 instance Uniquable DataCon where
524     getUnique = dcUnique
525
526 instance NamedThing DataCon where
527     getName = dcName
528
529 instance Outputable DataCon where
530     ppr con = ppr (dataConName con)
531
532 instance OutputableBndr DataCon where
533     pprInfixOcc con = pprInfixName (dataConName con)
534     pprPrefixOcc con = pprPrefixName (dataConName con)
535
536 instance Data.Data DataCon where
537     -- don't traverse?
538     toConstr _   = abstractConstr "DataCon"
539     gunfold _ _  = error "gunfold"
540     dataTypeOf _ = mkNoRepType "DataCon"
541
542 instance Outputable HsBang where
543     ppr HsNoBang               = empty
544     ppr (HsUserBang prag bang) = pp_unpk prag <+> ppWhen bang (char '!')
545     ppr (HsUnpack Nothing)     = ptext (sLit "Unpk")
546     ppr (HsUnpack (Just co))   = ptext (sLit "Unpk") <> parens (ppr co)
547     ppr HsStrict               = ptext (sLit "SrictNotUnpacked")
548
549 pp_unpk :: Maybe Bool -> SDoc
550 pp_unpk Nothing      = empty
551 pp_unpk (Just True)  = ptext (sLit "{-# UNPACK #-}")
552 pp_unpk (Just False) = ptext (sLit "{-# NOUNPACK #-}")
553
554 instance Outputable StrictnessMark where
555   ppr MarkedStrict     = ptext (sLit "!")
556   ppr NotMarkedStrict  = empty
557
558
559 eqHsBang :: HsBang -> HsBang -> Bool
560 eqHsBang HsNoBang             HsNoBang             = True
561 eqHsBang HsStrict             HsStrict             = True
562 eqHsBang (HsUserBang u1 b1)   (HsUserBang u2 b2)   = u1==u2 && b1==b2
563 eqHsBang (HsUnpack Nothing)   (HsUnpack Nothing)   = True
564 eqHsBang (HsUnpack (Just c1)) (HsUnpack (Just c2)) = eqType (coercionType c1) (coercionType c2)
565 eqHsBang _ _ = False
566
567 isBanged :: HsBang -> Bool
568 isBanged HsNoBang                  = False
569 isBanged (HsUserBang Nothing bang) = bang
570 isBanged _                         = True
571
572 isMarkedStrict :: StrictnessMark -> Bool
573 isMarkedStrict NotMarkedStrict = False
574 isMarkedStrict _               = True   -- All others are strict
575 \end{code}
576
577
578 %************************************************************************
579 %*                                                                      *
580 \subsection{Construction}
581 %*                                                                      *
582 %************************************************************************
583
584 \begin{code}
585 -- | Build a new data constructor
586 mkDataCon :: Name 
587           -> Bool               -- ^ Is the constructor declared infix?
588           -> [HsBang]           -- ^ Strictness annotations written in the source file
589           -> [FieldLabel]       -- ^ Field labels for the constructor, if it is a record, 
590                                 --   otherwise empty
591           -> [TyVar]            -- ^ Universally quantified type variables
592           -> [TyVar]            -- ^ Existentially quantified type variables
593           -> [(TyVar,Type)]     -- ^ GADT equalities
594           -> ThetaType          -- ^ Theta-type occuring before the arguments proper
595           -> [Type]             -- ^ Original argument types
596           -> Type               -- ^ Original result type
597           -> TyCon              -- ^ Representation type constructor
598           -> ThetaType          -- ^ The "stupid theta", context of the data declaration 
599                                 --   e.g. @data Eq a => T a ...@
600           -> Id                 -- ^ Worker Id
601           -> DataConRep         -- ^ Representation
602           -> DataCon
603   -- Can get the tag from the TyCon
604
605 mkDataCon name declared_infix
606           arg_stricts   -- Must match orig_arg_tys 1-1
607           fields
608           univ_tvs ex_tvs 
609           eq_spec theta
610           orig_arg_tys orig_res_ty rep_tycon
611           stupid_theta work_id rep
612 -- Warning: mkDataCon is not a good place to check invariants. 
613 -- If the programmer writes the wrong result type in the decl, thus:
614 --      data T a where { MkT :: S }
615 -- then it's possible that the univ_tvs may hit an assertion failure
616 -- if you pull on univ_tvs.  This case is checked by checkValidDataCon,
617 -- so the error is detected properly... it's just that asaertions here
618 -- are a little dodgy.
619
620   = con
621   where
622     is_vanilla = null ex_tvs && null eq_spec && null theta
623     con = MkData {dcName = name, dcUnique = nameUnique name, 
624                   dcVanilla = is_vanilla, dcInfix = declared_infix,
625                   dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs, 
626                   dcEqSpec = eq_spec, 
627                   dcOtherTheta = theta,
628                   dcStupidTheta = stupid_theta, 
629                   dcOrigArgTys = orig_arg_tys, dcOrigResTy = orig_res_ty,
630                   dcRepTyCon = rep_tycon, 
631                   dcArgBangs = arg_stricts, 
632                   dcFields = fields, dcTag = tag, dcRepType = rep_ty,
633                   dcWorkId = work_id,
634                   dcRep = rep, 
635                   dcSourceArity = length orig_arg_tys,
636                   dcRepArity = length rep_arg_tys,
637                   dcPromoted = mb_promoted }
638
639         -- The 'arg_stricts' passed to mkDataCon are simply those for the
640         -- source-language arguments.  We add extra ones for the
641         -- dictionary arguments right here.
642
643     tag = assoc "mkDataCon" (tyConDataCons rep_tycon `zip` [fIRST_TAG..]) con
644     rep_arg_tys = dataConRepArgTys con
645     rep_ty = mkForAllTys univ_tvs $ mkForAllTys ex_tvs $ 
646              mkFunTys rep_arg_tys $
647              mkTyConApp rep_tycon (mkTyVarTys univ_tvs)
648
649     mb_promoted   -- See Note [Promoted data constructors] in TyCon
650       | isJust (promotableTyCon_maybe rep_tycon)
651           -- The TyCon is promotable only if all its datacons
652           -- are, so the promoteType for prom_kind should succeed
653       = Just (mkPromotedDataCon con name (getUnique name) prom_kind roles)
654       | otherwise 
655       = Nothing          
656     prom_kind = promoteType (dataConUserType con)
657     roles = map (const Nominal)          (univ_tvs ++ ex_tvs) ++
658             map (const Representational) orig_arg_tys
659
660 eqSpecPreds :: [(TyVar,Type)] -> ThetaType
661 eqSpecPreds spec = [ mkEqPred (mkTyVarTy tv) ty | (tv,ty) <- spec ]
662 \end{code}
663
664 Note [Unpack equality predicates]
665 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
666 If we have a GADT with a contructor C :: (a~[b]) => b -> T a
667 we definitely want that equality predicate *unboxed* so that it
668 takes no space at all.  This is easily done: just give it
669 an UNPACK pragma. The rest of the unpack/repack code does the
670 heavy lifting.  This one line makes every GADT take a word less
671 space for each equality predicate, so it's pretty important!
672
673 \begin{code}
674 -- | The 'Name' of the 'DataCon', giving it a unique, rooted identification
675 dataConName :: DataCon -> Name
676 dataConName = dcName
677
678 -- | The tag used for ordering 'DataCon's
679 dataConTag :: DataCon -> ConTag
680 dataConTag  = dcTag
681
682 -- | The type constructor that we are building via this data constructor
683 dataConTyCon :: DataCon -> TyCon
684 dataConTyCon = dcRepTyCon
685
686 -- | The original type constructor used in the definition of this data
687 -- constructor.  In case of a data family instance, that will be the family
688 -- type constructor.
689 dataConOrigTyCon :: DataCon -> TyCon
690 dataConOrigTyCon dc 
691   | Just (tc, _) <- tyConFamInst_maybe (dcRepTyCon dc) = tc
692   | otherwise                                          = dcRepTyCon dc
693
694 -- | The representation type of the data constructor, i.e. the sort
695 -- type that will represent values of this type at runtime
696 dataConRepType :: DataCon -> Type
697 dataConRepType = dcRepType
698
699 -- | Should the 'DataCon' be presented infix?
700 dataConIsInfix :: DataCon -> Bool
701 dataConIsInfix = dcInfix
702
703 -- | The universally-quantified type variables of the constructor
704 dataConUnivTyVars :: DataCon -> [TyVar]
705 dataConUnivTyVars = dcUnivTyVars
706
707 -- | The existentially-quantified type variables of the constructor
708 dataConExTyVars :: DataCon -> [TyVar]
709 dataConExTyVars = dcExTyVars
710
711 -- | Both the universal and existentiatial type variables of the constructor
712 dataConAllTyVars :: DataCon -> [TyVar]
713 dataConAllTyVars (MkData { dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs })
714   = univ_tvs ++ ex_tvs
715
716 -- | Equalities derived from the result type of the data constructor, as written
717 -- by the programmer in any GADT declaration
718 dataConEqSpec :: DataCon -> [(TyVar,Type)]
719 dataConEqSpec = dcEqSpec
720
721 -- | The *full* constraints on the constructor type
722 dataConTheta :: DataCon -> ThetaType
723 dataConTheta (MkData { dcEqSpec = eq_spec, dcOtherTheta = theta }) 
724   = eqSpecPreds eq_spec ++ theta
725
726 -- | Get the Id of the 'DataCon' worker: a function that is the "actual"
727 -- constructor and has no top level binding in the program. The type may
728 -- be different from the obvious one written in the source program. Panics
729 -- if there is no such 'Id' for this 'DataCon'
730 dataConWorkId :: DataCon -> Id
731 dataConWorkId dc = dcWorkId dc
732
733 -- | Get the Id of the 'DataCon' wrapper: a function that wraps the "actual"
734 -- constructor so it has the type visible in the source program: c.f. 'dataConWorkId'.
735 -- Returns Nothing if there is no wrapper, which occurs for an algebraic data constructor 
736 -- and also for a newtype (whose constructor is inlined compulsorily)
737 dataConWrapId_maybe :: DataCon -> Maybe Id
738 dataConWrapId_maybe dc = case dcRep dc of
739                            NoDataConRep -> Nothing
740                            DCR { dcr_wrap_id = wrap_id } -> Just wrap_id
741
742 -- | Returns an Id which looks like the Haskell-source constructor by using
743 -- the wrapper if it exists (see 'dataConWrapId_maybe') and failing over to
744 -- the worker (see 'dataConWorkId')
745 dataConWrapId :: DataCon -> Id
746 dataConWrapId dc = case dcRep dc of
747                      NoDataConRep-> dcWorkId dc    -- worker=wrapper
748                      DCR { dcr_wrap_id = wrap_id } -> wrap_id
749
750 -- | Find all the 'Id's implicitly brought into scope by the data constructor. Currently,
751 -- the union of the 'dataConWorkId' and the 'dataConWrapId'
752 dataConImplicitIds :: DataCon -> [Id]
753 dataConImplicitIds (MkData { dcWorkId = work, dcRep = rep})
754   = case rep of
755        NoDataConRep               -> [work]
756        DCR { dcr_wrap_id = wrap } -> [wrap,work]
757
758 -- | The labels for the fields of this particular 'DataCon'
759 dataConFieldLabels :: DataCon -> [FieldLabel]
760 dataConFieldLabels = dcFields
761
762 -- | Extract the type for any given labelled field of the 'DataCon'
763 dataConFieldType :: DataCon -> FieldLabel -> Type
764 dataConFieldType con label
765   = case lookup label (dcFields con `zip` dcOrigArgTys con) of
766       Just ty -> ty
767       Nothing -> pprPanic "dataConFieldType" (ppr con <+> ppr label)
768
769 -- | The strictness markings decided on by the compiler.  Does not include those for
770 -- existential dictionaries.  The list is in one-to-one correspondence with the arity of the 'DataCon'
771 dataConStrictMarks :: DataCon -> [HsBang]
772 dataConStrictMarks = dcArgBangs
773
774 -- | Source-level arity of the data constructor
775 dataConSourceArity :: DataCon -> Arity
776 dataConSourceArity (MkData { dcSourceArity = arity }) = arity
777
778 -- | Gives the number of actual fields in the /representation/ of the 
779 -- data constructor. This may be more than appear in the source code;
780 -- the extra ones are the existentially quantified dictionaries
781 dataConRepArity :: DataCon -> Arity
782 dataConRepArity (MkData { dcRepArity = arity }) = arity
783
784
785 -- | The number of fields in the /representation/ of the constructor
786 -- AFTER taking into account the unpacking of any unboxed tuple fields
787 dataConRepRepArity :: DataCon -> RepArity
788 dataConRepRepArity dc = typeRepArity (dataConRepArity dc) (dataConRepType dc)
789
790 -- | Return whether there are any argument types for this 'DataCon's original source type
791 isNullarySrcDataCon :: DataCon -> Bool
792 isNullarySrcDataCon dc = null (dcOrigArgTys dc)
793
794 -- | Return whether there are any argument types for this 'DataCon's runtime representation type
795 isNullaryRepDataCon :: DataCon -> Bool
796 isNullaryRepDataCon dc = dataConRepArity dc == 0
797
798 dataConRepStrictness :: DataCon -> [StrictnessMark]
799 -- ^ Give the demands on the arguments of a
800 -- Core constructor application (Con dc args)
801 dataConRepStrictness dc = case dcRep dc of
802                             NoDataConRep -> [NotMarkedStrict | _ <- dataConRepArgTys dc]
803                             DCR { dcr_stricts = strs } -> strs
804
805 dataConRepBangs :: DataCon -> [HsBang]
806 dataConRepBangs dc = case dcRep dc of
807                        NoDataConRep -> dcArgBangs dc
808                        DCR { dcr_bangs = bangs } -> bangs
809
810 dataConBoxer :: DataCon -> Maybe DataConBoxer
811 dataConBoxer (MkData { dcRep = DCR { dcr_boxer = boxer } }) = Just boxer
812 dataConBoxer _ = Nothing 
813
814 -- | The \"signature\" of the 'DataCon' returns, in order:
815 --
816 -- 1) The result of 'dataConAllTyVars',
817 --
818 -- 2) All the 'ThetaType's relating to the 'DataCon' (coercion, dictionary, implicit
819 --    parameter - whatever)
820 --
821 -- 3) The type arguments to the constructor
822 --
823 -- 4) The /original/ result type of the 'DataCon'
824 dataConSig :: DataCon -> ([TyVar], ThetaType, [Type], Type)
825 dataConSig (MkData {dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs, 
826                     dcEqSpec = eq_spec, dcOtherTheta  = theta, 
827                     dcOrigArgTys = arg_tys, dcOrigResTy = res_ty})
828   = (univ_tvs ++ ex_tvs, eqSpecPreds eq_spec ++ theta, arg_tys, res_ty)
829
830 -- | The \"full signature\" of the 'DataCon' returns, in order:
831 --
832 -- 1) The result of 'dataConUnivTyVars'
833 --
834 -- 2) The result of 'dataConExTyVars'
835 --
836 -- 3) The result of 'dataConEqSpec'
837 --
838 -- 4) The result of 'dataConDictTheta'
839 --
840 -- 5) The original argument types to the 'DataCon' (i.e. before 
841 --    any change of the representation of the type)
842 --
843 -- 6) The original result type of the 'DataCon'
844 dataConFullSig :: DataCon 
845                -> ([TyVar], [TyVar], [(TyVar,Type)], ThetaType, [Type], Type)
846 dataConFullSig (MkData {dcUnivTyVars = univ_tvs, dcExTyVars = ex_tvs, 
847                         dcEqSpec = eq_spec, dcOtherTheta = theta,
848                         dcOrigArgTys = arg_tys, dcOrigResTy = res_ty})
849   = (univ_tvs, ex_tvs, eq_spec, theta, arg_tys, res_ty)
850
851 dataConOrigResTy :: DataCon -> Type
852 dataConOrigResTy dc = dcOrigResTy dc
853
854 -- | The \"stupid theta\" of the 'DataCon', such as @data Eq a@ in:
855 --
856 -- > data Eq a => T a = ...
857 dataConStupidTheta :: DataCon -> ThetaType
858 dataConStupidTheta dc = dcStupidTheta dc
859
860 dataConUserType :: DataCon -> Type
861 -- ^ The user-declared type of the data constructor
862 -- in the nice-to-read form:
863 --
864 -- > T :: forall a b. a -> b -> T [a]
865 --
866 -- rather than:
867 --
868 -- > T :: forall a c. forall b. (c~[a]) => a -> b -> T c
869 --
870 -- NB: If the constructor is part of a data instance, the result type
871 -- mentions the family tycon, not the internal one.
872 dataConUserType  (MkData { dcUnivTyVars = univ_tvs, 
873                            dcExTyVars = ex_tvs, dcEqSpec = eq_spec,
874                            dcOtherTheta = theta, dcOrigArgTys = arg_tys,
875                            dcOrigResTy = res_ty })
876   = mkForAllTys ((univ_tvs `minusList` map fst eq_spec) ++ ex_tvs) $
877     mkFunTys theta $
878     mkFunTys arg_tys $
879     res_ty
880
881 -- | Finds the instantiated types of the arguments required to construct a 'DataCon' representation
882 -- NB: these INCLUDE any dictionary args
883 --     but EXCLUDE the data-declaration context, which is discarded
884 -- It's all post-flattening etc; this is a representation type
885 dataConInstArgTys :: DataCon    -- ^ A datacon with no existentials or equality constraints
886                                 -- However, it can have a dcTheta (notably it can be a 
887                                 -- class dictionary, with superclasses)
888                   -> [Type]     -- ^ Instantiated at these types
889                   -> [Type]
890 dataConInstArgTys dc@(MkData {dcUnivTyVars = univ_tvs, dcEqSpec = eq_spec,
891                               dcExTyVars = ex_tvs}) inst_tys
892  = ASSERT2( length univ_tvs == length inst_tys
893           , ptext (sLit "dataConInstArgTys") <+> ppr dc $$ ppr univ_tvs $$ ppr inst_tys)
894    ASSERT2( null ex_tvs && null eq_spec, ppr dc )
895    map (substTyWith univ_tvs inst_tys) (dataConRepArgTys dc)
896
897 -- | Returns just the instantiated /value/ argument types of a 'DataCon',
898 -- (excluding dictionary args)
899 dataConInstOrigArgTys 
900         :: DataCon      -- Works for any DataCon
901         -> [Type]       -- Includes existential tyvar args, but NOT
902                         -- equality constraints or dicts
903         -> [Type]
904 -- For vanilla datacons, it's all quite straightforward
905 -- But for the call in MatchCon, we really do want just the value args
906 dataConInstOrigArgTys dc@(MkData {dcOrigArgTys = arg_tys,
907                                   dcUnivTyVars = univ_tvs, 
908                                   dcExTyVars = ex_tvs}) inst_tys
909   = ASSERT2( length tyvars == length inst_tys
910           , ptext (sLit "dataConInstOrigArgTys") <+> ppr dc $$ ppr tyvars $$ ppr inst_tys )
911     map (substTyWith tyvars inst_tys) arg_tys
912   where
913     tyvars = univ_tvs ++ ex_tvs
914 \end{code}
915
916 \begin{code}
917 -- | Returns the argument types of the wrapper, excluding all dictionary arguments
918 -- and without substituting for any type variables
919 dataConOrigArgTys :: DataCon -> [Type]
920 dataConOrigArgTys dc = dcOrigArgTys dc
921
922 -- | Returns the arg types of the worker, including *all* evidence, after any 
923 -- flattening has been done and without substituting for any type variables
924 dataConRepArgTys :: DataCon -> [Type]
925 dataConRepArgTys (MkData { dcRep = rep 
926                          , dcEqSpec = eq_spec
927                          , dcOtherTheta = theta
928                          , dcOrigArgTys = orig_arg_tys })
929   = case rep of
930       NoDataConRep -> ASSERT( null eq_spec ) theta ++ orig_arg_tys
931       DCR { dcr_arg_tys = arg_tys } -> arg_tys
932 \end{code}
933
934 \begin{code}
935 -- | The string @package:module.name@ identifying a constructor, which is attached
936 -- to its info table and used by the GHCi debugger and the heap profiler
937 dataConIdentity :: DataCon -> [Word8]
938 -- We want this string to be UTF-8, so we get the bytes directly from the FastStrings.
939 dataConIdentity dc = bytesFS (packageIdFS (modulePackageId mod)) ++ 
940                   fromIntegral (ord ':') : bytesFS (moduleNameFS (moduleName mod)) ++
941                   fromIntegral (ord '.') : bytesFS (occNameFS (nameOccName name))
942   where name = dataConName dc
943         mod  = ASSERT( isExternalName name ) nameModule name
944 \end{code}
945
946 \begin{code}
947 isTupleDataCon :: DataCon -> Bool
948 isTupleDataCon (MkData {dcRepTyCon = tc}) = isTupleTyCon tc
949         
950 isUnboxedTupleCon :: DataCon -> Bool
951 isUnboxedTupleCon (MkData {dcRepTyCon = tc}) = isUnboxedTupleTyCon tc
952
953 -- | Vanilla 'DataCon's are those that are nice boring Haskell 98 constructors
954 isVanillaDataCon :: DataCon -> Bool
955 isVanillaDataCon dc = dcVanilla dc
956 \end{code}
957
958 \begin{code}
959 classDataCon :: Class -> DataCon
960 classDataCon clas = case tyConDataCons (classTyCon clas) of
961                       (dict_constr:no_more) -> ASSERT( null no_more ) dict_constr 
962                       [] -> panic "classDataCon"
963 \end{code}
964
965 \begin{code}
966 dataConCannotMatch :: [Type] -> DataCon -> Bool
967 -- Returns True iff the data con *definitely cannot* match a 
968 --                  scrutinee of type (T tys)
969 --                  where T is the dcRepTyCon for the data con
970 -- NB: look at *all* equality constraints, not only those
971 --     in dataConEqSpec; see Trac #5168
972 dataConCannotMatch tys con
973   | null theta        = False   -- Common
974   | all isTyVarTy tys = False   -- Also common
975   | otherwise
976   = typesCantMatch [(Type.substTy subst ty1, Type.substTy subst ty2)
977                    | (ty1, ty2) <- concatMap predEqs theta ]
978   where
979     dc_tvs  = dataConUnivTyVars con
980     theta   = dataConTheta con
981     subst   = ASSERT2( length dc_tvs == length tys, ppr con $$ ppr dc_tvs $$ ppr tys ) 
982               zipTopTvSubst dc_tvs tys
983
984     -- TODO: could gather equalities from superclasses too
985     predEqs pred = case classifyPredType pred of
986                      EqPred ty1 ty2 -> [(ty1, ty2)]
987                      TuplePred ts   -> concatMap predEqs ts
988                      _              -> []
989 \end{code}
990
991 %************************************************************************
992 %*                                                                      *
993               Building an algebraic data type
994 %*                                                                      *
995 %************************************************************************
996
997 \begin{code}
998 buildAlgTyCon :: Name 
999               -> [TyVar]               -- ^ Kind variables and type variables
1000               -> [Role]
1001               -> Maybe CType
1002               -> ThetaType             -- ^ Stupid theta
1003               -> AlgTyConRhs
1004               -> RecFlag
1005               -> Bool                  -- ^ True <=> this TyCon is promotable
1006               -> Bool                  -- ^ True <=> was declared in GADT syntax
1007               -> TyConParent
1008               -> TyCon
1009
1010 buildAlgTyCon tc_name ktvs roles cType stupid_theta rhs 
1011               is_rec is_promotable gadt_syn parent
1012   = tc
1013   where 
1014     kind = mkPiKinds ktvs liftedTypeKind
1015
1016     -- tc and mb_promoted_tc are mutually recursive
1017     tc = mkAlgTyCon tc_name kind ktvs roles cType stupid_theta 
1018                     rhs parent is_rec gadt_syn 
1019                     mb_promoted_tc
1020
1021     mb_promoted_tc
1022       | is_promotable = Just (mkPromotedTyCon tc (promoteKind kind))
1023       | otherwise     = Nothing
1024 \end{code}
1025
1026
1027 %************************************************************************
1028 %*                                                                      *
1029         Promoting of data types to the kind level
1030 %*                                                                      *
1031 %************************************************************************
1032
1033 These two 'promoted..' functions are here because
1034  * They belong together
1035  * 'prmoteDataCon' depends on DataCon stuff
1036
1037 \begin{code}
1038 promoteDataCon :: DataCon -> TyCon
1039 promoteDataCon (MkData { dcPromoted = Just tc }) = tc
1040 promoteDataCon dc = pprPanic "promoteDataCon" (ppr dc)
1041
1042 promoteDataCon_maybe :: DataCon -> Maybe TyCon
1043 promoteDataCon_maybe (MkData { dcPromoted = mb_tc }) = mb_tc
1044 \end{code}
1045
1046 Note [Promoting a Type to a Kind]
1047 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1048 Suppsoe we have a data constructor D
1049      D :: forall (a:*). Maybe a -> T a
1050 We promote this to be a type constructor 'D:
1051      'D :: forall (k:BOX). 'Maybe k -> 'T k
1052
1053 The transformation from type to kind is done by promoteType
1054
1055   * Convert forall (a:*) to forall (k:BOX), and substitute
1056
1057   * Ensure all foralls are at the top (no higher rank stuff)
1058
1059   * Ensure that all type constructors mentioned (Maybe and T
1060     in the example) are promotable; that is, they have kind 
1061           * -> ... -> * -> *
1062
1063 \begin{code}
1064 -- | Promotes a type to a kind. 
1065 -- Assumes the argument satisfies 'isPromotableType'
1066 promoteType :: Type -> Kind
1067 promoteType ty
1068   = mkForAllTys kvs (go rho)
1069   where
1070     (tvs, rho) = splitForAllTys ty
1071     kvs = [ mkKindVar (tyVarName tv) superKind | tv <- tvs ]
1072     env = zipVarEnv tvs kvs
1073
1074     go (TyConApp tc tys) | Just prom_tc <- promotableTyCon_maybe tc
1075                          = mkTyConApp prom_tc (map go tys)
1076     go (FunTy arg res)   = mkArrowKind (go arg) (go res)
1077     go (TyVarTy tv)      | Just kv <- lookupVarEnv env tv 
1078                          = TyVarTy kv
1079     go _ = panic "promoteType"  -- Argument did not satisfy isPromotableType
1080
1081 promoteKind :: Kind -> SuperKind
1082 -- Promote the kind of a type constructor
1083 -- from (* -> * -> *) to (BOX -> BOX -> BOX) 
1084 promoteKind (TyConApp tc []) 
1085   | tc `hasKey` liftedTypeKindTyConKey = superKind
1086 promoteKind (FunTy arg res) = FunTy (promoteKind arg) (promoteKind res)
1087 promoteKind k = pprPanic "promoteKind" (ppr k)
1088 \end{code}