[project @ 2004-10-04 15:51:00 by simonpj]
[ghc-hetmet.git] / ghc / compiler / basicTypes / DataCon.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
3 %
4 \section[DataCon]{@DataCon@: Data Constructors}
5
6 \begin{code}
7 module DataCon (
8         DataCon, DataConIds(..),
9         ConTag, fIRST_TAG,
10         mkDataCon,
11         dataConRepType, dataConSig, dataConName, dataConTag, dataConTyCon,
12         dataConTyVars, dataConStupidTheta, 
13         dataConArgTys, dataConOrigArgTys, dataConResTy,
14         dataConInstOrigArgTys, dataConRepArgTys, 
15         dataConFieldLabels, dataConStrictMarks, dataConExStricts,
16         dataConSourceArity, dataConRepArity,
17         dataConIsInfix,
18         dataConWorkId, dataConWrapId, dataConWrapId_maybe, dataConImplicitIds,
19         dataConRepStrictness,
20         isNullarySrcDataCon, isNullaryRepDataCon, isTupleCon, isUnboxedTupleCon,
21         isVanillaDataCon, classDataCon, 
22
23         splitProductType_maybe, splitProductType,
24     ) where
25
26 #include "HsVersions.h"
27
28 import Type             ( Type, ThetaType, substTyWith, substTy, zipTopTvSubst,
29                           mkForAllTys, mkFunTys, mkTyConApp,
30                           splitTyConApp_maybe, 
31                           mkPredTys, isStrictPred, pprType
32                         )
33 import TyCon            ( TyCon, FieldLabel, tyConDataCons, tyConDataCons, 
34                           isProductTyCon, isTupleTyCon, isUnboxedTupleTyCon )
35 import Class            ( Class, classTyCon )
36 import Name             ( Name, NamedThing(..), nameUnique )
37 import Var              ( TyVar, Id )
38 import BasicTypes       ( Arity, StrictnessMark(..) )
39 import Outputable
40 import Unique           ( Unique, Uniquable(..) )
41 import ListSetOps       ( assoc )
42 import Util             ( zipEqual, zipWithEqual )
43 \end{code}
44
45
46 Data constructor representation
47 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
48 Consider the following Haskell data type declaration
49
50         data T = T !Int ![Int]
51
52 Using the strictness annotations, GHC will represent this as
53
54         data T = T Int# [Int]
55
56 That is, the Int has been unboxed.  Furthermore, the Haskell source construction
57
58         T e1 e2
59
60 is translated to
61
62         case e1 of { I# x -> 
63         case e2 of { r ->
64         T x r }}
65
66 That is, the first argument is unboxed, and the second is evaluated.  Finally,
67 pattern matching is translated too:
68
69         case e of { T a b -> ... }
70
71 becomes
72
73         case e of { T a' b -> let a = I# a' in ... }
74
75 To keep ourselves sane, we name the different versions of the data constructor
76 differently, as follows.
77
78
79 Note [Data Constructor Naming]
80 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
81 Each data constructor C has two, and possibly three, Names associated with it:
82
83                              OccName    Name space      Used for
84   ---------------------------------------------------------------------------
85   * The "source data con"       C       DataName        The DataCon itself
86   * The "real data con"         C       VarName         Its worker Id
87   * The "wrapper data con"      $WC     VarName         Wrapper Id (optional)
88
89 Each of these three has a distinct Unique.  The "source data con" name
90 appears in the output of the renamer, and names the Haskell-source
91 data constructor.  The type checker translates it into either the wrapper Id
92 (if it exists) or worker Id (otherwise).
93
94 The data con has one or two Ids associated with it:
95
96   The "worker Id", is the actual data constructor.
97         Its type may be different to the Haskell source constructor
98         because:
99                 - useless dict args are dropped
100                 - strict args may be flattened
101         The worker is very like a primop, in that it has no binding.
102
103         Newtypes currently do get a worker-Id, but it is never used.
104
105
106   The "wrapper Id", $wC, whose type is exactly what it looks like
107         in the source program. It is an ordinary function,
108         and it gets a top-level binding like any other function.
109
110         The wrapper Id isn't generated for a data type if the worker
111         and wrapper are identical.  It's always generated for a newtype.
112
113
114
115 A note about the stupid context
116 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
117 Data types can have a context:
118         
119         data (Eq a, Ord b) => T a b = T1 a b | T2 a
120
121 and that makes the constructors have a context too
122 (notice that T2's context is "thinned"):
123
124         T1 :: (Eq a, Ord b) => a -> b -> T a b
125         T2 :: (Eq a) => a -> T a b
126
127 Furthermore, this context pops up when pattern matching
128 (though GHC hasn't implemented this, but it is in H98, and
129 I've fixed GHC so that it now does):
130
131         f (T2 x) = x
132 gets inferred type
133         f :: Eq a => T a b -> a
134
135 I say the context is "stupid" because the dictionaries passed
136 are immediately discarded -- they do nothing and have no benefit.
137 It's a flaw in the language.
138
139         Up to now [March 2002] I have put this stupid context into the
140         type of the "wrapper" constructors functions, T1 and T2, but
141         that turned out to be jolly inconvenient for generics, and
142         record update, and other functions that build values of type T
143         (because they don't have suitable dictionaries available).
144
145         So now I've taken the stupid context out.  I simply deal with
146         it separately in the type checker on occurrences of a
147         constructor, either in an expression or in a pattern.
148
149         [May 2003: actually I think this decision could evasily be
150         reversed now, and probably should be.  Generics could be
151         disabled for types with a stupid context; record updates now
152         (H98) needs the context too; etc.  It's an unforced change, so
153         I'm leaving it for now --- but it does seem odd that the
154         wrapper doesn't include the stupid context.]
155
156 [July 04] With the advent of generalised data types, it's less obvious
157 what the "stupid context" is.  Consider
158         C :: forall a. Ord a => a -> a -> T (Foo a)
159 Does the C constructor in Core contain the Ord dictionary?  Yes, it must:
160
161         f :: T b -> Ordering
162         f = /\b. \x:T b. 
163             case x of
164                 C a (d:Ord a) (p:a) (q:a) -> compare d p q
165
166 Note that (Foo a) might not be an instance of Ord.
167
168 %************************************************************************
169 %*                                                                      *
170 \subsection{Data constructors}
171 %*                                                                      *
172 %************************************************************************
173
174 \begin{code}
175 data DataCon
176   = MkData {
177         dcName    :: Name,      -- This is the name of the *source data con*
178                                 -- (see "Note [Data Constructor Naming]" above)
179         dcUnique :: Unique,     -- Cached from Name
180         dcTag    :: ConTag,
181
182         -- Running example:
183         --
184         --      data Eq a => T a = forall b. Ord b => MkT a [b]
185
186         -- The next six fields express the type of the constructor, in pieces
187         -- e.g.
188         --
189         --      dcTyVars      = [a,b]
190         --      dcStupidTheta = [Eq a]
191         --      dcTheta       = [Ord b]
192         --      dcOrigArgTys  = [a,List b]
193         --      dcTyCon       = T
194         --      dcTyArgs      = [a,b]
195
196         dcVanilla :: Bool,      -- True <=> This is a vanilla Haskell 98 data constructor
197                                 --          Its type is of form
198                                 --              forall a1..an . t1 -> ... tm -> T a1..an
199                                 --          No existentials, no GADTs, nothing.
200
201         dcTyVars :: [TyVar],    -- Universally-quantified type vars 
202                                 -- for the data constructor.
203                 -- dcVanilla = True  <=> The [TyVar] are identical to those of the parent tycon
204                 --             False <=> The [TyVar] are NOT NECESSARILY THE SAME AS THE TYVARS
205                 --                                   FOR THE PARENT TyCon. (With GADTs the data
206                 --                                   con might not even have the same number of
207                 --                                   type variables.)
208
209         dcStupidTheta  ::  ThetaType,   -- This is a "thinned" version of 
210                                         -- the context of the data decl.  
211                 -- "Thinned", because the Report says
212                 -- to eliminate any constraints that don't mention
213                 -- tyvars free in the arg types for this constructor
214                 --
215                 -- "Stupid", because the dictionaries aren't used for anything.  
216                 -- 
217                 -- Indeed, [as of March 02] they are no 
218                 -- longer in the type of the wrapper Id, because
219                 -- that makes it harder to use the wrap-id to rebuild
220                 -- values after record selection or in generics.
221
222         dcTheta  :: ThetaType,          -- The existentially quantified stuff
223                                         
224         dcOrigArgTys :: [Type],         -- Original argument types
225                                         -- (before unboxing and flattening of
226                                         --  strict fields)
227
228         -- Result type of constructor is T t1..tn
229         dcTyCon  :: TyCon,              -- Result tycon, T
230         dcResTys :: [Type],             -- Result type args, t1..tn
231
232         -- Now the strictness annotations and field labels of the constructor
233         dcStrictMarks :: [StrictnessMark],
234                 -- Strictness annotations as decided by the compiler.  
235                 -- Does *not* include the existential dictionaries
236                 -- length = dataConSourceArity dataCon
237
238         dcFields  :: [FieldLabel],
239                 -- Field labels for this constructor, in the
240                 -- same order as the argument types; 
241                 -- length = 0 (if not a record) or dataConSourceArity.
242
243         -- Constructor representation
244         dcRepArgTys :: [Type],          -- Final, representation argument types, 
245                                         -- after unboxing and flattening,
246                                         -- and *including* existential dictionaries
247
248         dcRepStrictness :: [StrictnessMark],    -- One for each *representation* argument       
249
250         dcRepType   :: Type,    -- Type of the constructor
251                                 --      forall a b . Ord b => a -> [b] -> MkT a
252                                 -- (this is *not* of the constructor wrapper Id:
253                                 --  see notes after this data type declaration)
254                                 --
255         -- Notice that the existential type parameters come *second*.  
256         -- Reason: in a case expression we may find:
257         --      case (e :: T t) of { MkT b (d:Ord b) (x:t) (xs:[b]) -> ... }
258         -- It's convenient to apply the rep-type of MkT to 't', to get
259         --      forall b. Ord b => ...
260         -- and use that to check the pattern.  Mind you, this is really only
261         -- use in CoreLint.
262
263
264         -- Finally, the curried worker function that corresponds to the constructor
265         -- It doesn't have an unfolding; the code generator saturates these Ids
266         -- and allocates a real constructor when it finds one.
267         --
268         -- An entirely separate wrapper function is built in TcTyDecls
269         dcIds :: DataConIds,
270
271         dcInfix :: Bool         -- True <=> declared infix
272                                 -- Used for Template Haskell and 'deriving' only
273                                 -- The actual fixity is stored elsewhere
274   }
275
276 data DataConIds
277   = NewDC Id                    -- Newtypes have only a wrapper, but no worker
278   | AlgDC (Maybe Id) Id         -- Algebraic data types always have a worker, and
279                                 -- may or may not have a wrapper, depending on whether
280                                 -- the wrapper does anything.
281
282         -- *Neither* the worker *nor* the wrapper take the dcStupidTheta dicts as arguments
283
284         -- The wrapper takes dcOrigArgTys as its arguments
285         -- The worker takes dcRepArgTys as its arguments
286         -- If the worker is absent, dcRepArgTys is the same as dcOrigArgTys
287
288         -- The 'Nothing' case of AlgDC is important
289         -- Not only is this efficient,
290         -- but it also ensures that the wrapper is replaced
291         -- by the worker (becuase it *is* the wroker)
292         -- even when there are no args. E.g. in
293         --              f (:) x
294         -- the (:) *is* the worker.
295         -- This is really important in rule matching,
296         -- (We could match on the wrappers,
297         -- but that makes it less likely that rules will match
298         -- when we bring bits of unfoldings together.)
299
300 type ConTag = Int
301
302 fIRST_TAG :: ConTag
303 fIRST_TAG =  1  -- Tags allocated from here for real constructors
304 \end{code}
305
306 The dcRepType field contains the type of the representation of a contructor
307 This may differ from the type of the contructor *Id* (built
308 by MkId.mkDataConId) for two reasons:
309         a) the constructor Id may be overloaded, but the dictionary isn't stored
310            e.g.    data Eq a => T a = MkT a a
311
312         b) the constructor may store an unboxed version of a strict field.
313
314 Here's an example illustrating both:
315         data Ord a => T a = MkT Int! a
316 Here
317         T :: Ord a => Int -> a -> T a
318 but the rep type is
319         Trep :: Int# -> a -> T a
320 Actually, the unboxed part isn't implemented yet!
321
322
323 %************************************************************************
324 %*                                                                      *
325 \subsection{Instances}
326 %*                                                                      *
327 %************************************************************************
328
329 \begin{code}
330 instance Eq DataCon where
331     a == b = getUnique a == getUnique b
332     a /= b = getUnique a /= getUnique b
333
334 instance Ord DataCon where
335     a <= b = getUnique a <= getUnique b
336     a <  b = getUnique a <  getUnique b
337     a >= b = getUnique a >= getUnique b
338     a >  b = getUnique a > getUnique b
339     compare a b = getUnique a `compare` getUnique b
340
341 instance Uniquable DataCon where
342     getUnique = dcUnique
343
344 instance NamedThing DataCon where
345     getName = dcName
346
347 instance Outputable DataCon where
348     ppr con = ppr (dataConName con)
349
350 instance Show DataCon where
351     showsPrec p con = showsPrecSDoc p (ppr con)
352 \end{code}
353
354
355 %************************************************************************
356 %*                                                                      *
357 \subsection{Construction}
358 %*                                                                      *
359 %************************************************************************
360
361 \begin{code}
362 mkDataCon :: Name 
363           -> Bool       -- Declared infix
364           -> Bool       -- Vanilla (see notes with dcVanilla)
365           -> [StrictnessMark] -> [FieldLabel]
366           -> [TyVar] -> ThetaType -> ThetaType
367           -> [Type] -> TyCon -> [Type]
368           -> DataConIds
369           -> DataCon
370   -- Can get the tag from the TyCon
371
372 mkDataCon name declared_infix vanilla
373           arg_stricts   -- Must match orig_arg_tys 1-1
374           fields
375           tyvars stupid_theta theta orig_arg_tys tycon res_tys
376           ids
377   = con
378   where
379     con = MkData {dcName = name, 
380                   dcUnique = nameUnique name, dcVanilla = vanilla,
381                   dcTyVars = tyvars, dcStupidTheta = stupid_theta, dcTheta = theta,
382                   dcOrigArgTys = orig_arg_tys, dcTyCon = tycon, dcResTys = res_tys,
383                   dcRepArgTys = rep_arg_tys,
384                   dcStrictMarks = arg_stricts, dcRepStrictness = rep_arg_stricts,
385                   dcFields = fields, dcTag = tag, dcRepType = ty,
386                   dcIds = ids, dcInfix = declared_infix}
387
388         -- Strictness marks for source-args
389         --      *after unboxing choices*, 
390         -- but  *including existential dictionaries*
391         -- 
392         -- The 'arg_stricts' passed to mkDataCon are simply those for the
393         -- source-language arguments.  We add extra ones for the
394         -- dictionary arguments right here.
395     dict_tys     = mkPredTys theta
396     real_arg_tys = dict_tys                      ++ orig_arg_tys
397     real_stricts = map mk_dict_strict_mark theta ++ arg_stricts
398
399         -- Representation arguments and demands
400     (rep_arg_stricts, rep_arg_tys) = computeRep real_stricts real_arg_tys
401
402     tag = assoc "mkDataCon" (tyConDataCons tycon `zip` [fIRST_TAG..]) con
403     ty  = mkForAllTys tyvars (mkFunTys rep_arg_tys result_ty)
404                 -- NB: the existential dict args are already in rep_arg_tys
405
406     result_ty = mkTyConApp tycon res_tys
407
408 mk_dict_strict_mark pred | isStrictPred pred = MarkedStrict
409                          | otherwise         = NotMarkedStrict
410 \end{code}
411
412 \begin{code}
413 dataConName :: DataCon -> Name
414 dataConName = dcName
415
416 dataConTag :: DataCon -> ConTag
417 dataConTag  = dcTag
418
419 dataConTyCon :: DataCon -> TyCon
420 dataConTyCon = dcTyCon
421
422 dataConRepType :: DataCon -> Type
423 dataConRepType = dcRepType
424
425 dataConIsInfix :: DataCon -> Bool
426 dataConIsInfix = dcInfix
427
428 dataConTyVars :: DataCon -> [TyVar]
429 dataConTyVars = dcTyVars
430
431 dataConWorkId :: DataCon -> Id
432 dataConWorkId dc = case dcIds dc of
433                         AlgDC _ wrk_id -> wrk_id
434                         NewDC _ -> pprPanic "dataConWorkId" (ppr dc)
435
436 dataConWrapId_maybe :: DataCon -> Maybe Id
437 dataConWrapId_maybe dc = case dcIds dc of
438                                 AlgDC mb_wrap _ -> mb_wrap
439                                 NewDC wrap      -> Just wrap
440
441 dataConWrapId :: DataCon -> Id
442 -- Returns an Id which looks like the Haskell-source constructor
443 dataConWrapId dc = case dcIds dc of
444                         AlgDC (Just wrap) _   -> wrap
445                         AlgDC Nothing     wrk -> wrk        -- worker=wrapper
446                         NewDC wrap            -> wrap
447
448 dataConImplicitIds :: DataCon -> [Id]
449 dataConImplicitIds dc = case dcIds dc of
450                           AlgDC (Just wrap) work -> [wrap,work]
451                           AlgDC Nothing     work -> [work]
452                           NewDC wrap             -> [wrap]
453
454 dataConFieldLabels :: DataCon -> [FieldLabel]
455 dataConFieldLabels = dcFields
456
457 dataConStrictMarks :: DataCon -> [StrictnessMark]
458 dataConStrictMarks = dcStrictMarks
459
460 dataConExStricts :: DataCon -> [StrictnessMark]
461 -- Strictness of *existential* arguments only
462 -- Usually empty, so we don't bother to cache this
463 dataConExStricts dc = map mk_dict_strict_mark (dcTheta dc)
464
465 dataConSourceArity :: DataCon -> Arity
466         -- Source-level arity of the data constructor
467 dataConSourceArity dc = length (dcOrigArgTys dc)
468
469 -- dataConRepArity gives the number of actual fields in the
470 -- {\em representation} of the data constructor.  This may be more than appear
471 -- in the source code; the extra ones are the existentially quantified
472 -- dictionaries
473 dataConRepArity (MkData {dcRepArgTys = arg_tys}) = length arg_tys
474
475 isNullarySrcDataCon, isNullaryRepDataCon :: DataCon -> Bool
476 isNullarySrcDataCon dc = null (dcOrigArgTys dc)
477 isNullaryRepDataCon dc = null (dcRepArgTys dc)
478
479 dataConRepStrictness :: DataCon -> [StrictnessMark]
480         -- Give the demands on the arguments of a
481         -- Core constructor application (Con dc args)
482 dataConRepStrictness dc = dcRepStrictness dc
483
484 dataConSig :: DataCon -> ([TyVar], ThetaType,
485                           [Type], TyCon, [Type])
486
487 dataConSig (MkData {dcTyVars = tyvars, dcTheta  = theta,
488                     dcOrigArgTys = arg_tys, dcTyCon = tycon, dcResTys = res_tys})
489   = (tyvars, theta, arg_tys, tycon, res_tys)
490
491 dataConArgTys :: DataCon
492               -> [Type]         -- Instantiated at these types
493                                 -- NB: these INCLUDE the existentially quantified arg types
494               -> [Type]         -- Needs arguments of these types
495                                 -- NB: these INCLUDE the existentially quantified dict args
496                                 --     but EXCLUDE the data-decl context which is discarded
497                                 -- It's all post-flattening etc; this is a representation type
498 dataConArgTys (MkData {dcRepArgTys = arg_tys, dcTyVars = tyvars}) inst_tys
499  = map (substTyWith tyvars inst_tys) arg_tys
500
501 dataConResTy :: DataCon -> [Type] -> Type
502 dataConResTy (MkData {dcTyVars = tyvars, dcTyCon = tc, dcResTys = res_tys}) inst_tys
503  = substTy (zipTopTvSubst tyvars inst_tys) (mkTyConApp tc res_tys)
504         -- zipTopTvSubst because the res_tys can't contain any foralls
505
506 -- And the same deal for the original arg tys
507 -- This one only works for vanilla DataCons
508 dataConInstOrigArgTys :: DataCon -> [Type] -> [Type]
509 dataConInstOrigArgTys (MkData {dcOrigArgTys = arg_tys, dcTyVars = tyvars, dcVanilla = is_vanilla}) inst_tys
510  = ASSERT( is_vanilla ) 
511    map (substTyWith tyvars inst_tys) arg_tys
512
513 dataConStupidTheta :: DataCon -> ThetaType
514 dataConStupidTheta dc = dcStupidTheta dc
515 \end{code}
516
517 These two functions get the real argument types of the constructor,
518 without substituting for any type variables.
519
520 dataConOrigArgTys returns the arg types of the wrapper, excluding all dictionary args.
521
522 dataConRepArgTys retuns the arg types of the worker, including all dictionaries, and
523 after any flattening has been done.
524
525 \begin{code}
526 dataConOrigArgTys :: DataCon -> [Type]
527 dataConOrigArgTys dc = dcOrigArgTys dc
528
529 dataConRepArgTys :: DataCon -> [Type]
530 dataConRepArgTys dc = dcRepArgTys dc
531 \end{code}
532
533
534 \begin{code}
535 isTupleCon :: DataCon -> Bool
536 isTupleCon (MkData {dcTyCon = tc}) = isTupleTyCon tc
537         
538 isUnboxedTupleCon :: DataCon -> Bool
539 isUnboxedTupleCon (MkData {dcTyCon = tc}) = isUnboxedTupleTyCon tc
540
541 isVanillaDataCon :: DataCon -> Bool
542 isVanillaDataCon dc = dcVanilla dc
543 \end{code}
544
545
546 \begin{code}
547 classDataCon :: Class -> DataCon
548 classDataCon clas = case tyConDataCons (classTyCon clas) of
549                       (dict_constr:no_more) -> ASSERT( null no_more ) dict_constr 
550 \end{code}
551
552 %************************************************************************
553 %*                                                                      *
554 \subsection{Splitting products}
555 %*                                                                      *
556 %************************************************************************
557
558 \begin{code}
559 splitProductType_maybe
560         :: Type                         -- A product type, perhaps
561         -> Maybe (TyCon,                -- The type constructor
562                   [Type],               -- Type args of the tycon
563                   DataCon,              -- The data constructor
564                   [Type])               -- Its *representation* arg types
565
566         -- Returns (Just ...) for any
567         --      concrete (i.e. constructors visible)
568         --      single-constructor
569         --      not existentially quantified
570         -- type whether a data type or a new type
571         --
572         -- Rejecing existentials is conservative.  Maybe some things
573         -- could be made to work with them, but I'm not going to sweat
574         -- it through till someone finds it's important.
575
576 splitProductType_maybe ty
577   = case splitTyConApp_maybe ty of
578         Just (tycon,ty_args)
579            | isProductTyCon tycon       -- Includes check for non-existential,
580                                         -- and for constructors visible
581            -> Just (tycon, ty_args, data_con, dataConArgTys data_con ty_args)
582            where
583               data_con = head (tyConDataCons tycon)
584         other -> Nothing
585
586 splitProductType str ty
587   = case splitProductType_maybe ty of
588         Just stuff -> stuff
589         Nothing    -> pprPanic (str ++ ": not a product") (pprType ty)
590
591
592 computeRep :: [StrictnessMark]          -- Original arg strictness
593            -> [Type]                    -- and types
594            -> ([StrictnessMark],        -- Representation arg strictness
595                [Type])                  -- And type
596
597 computeRep stricts tys
598   = unzip $ concat $ zipWithEqual "computeRep" unbox stricts tys
599   where
600     unbox NotMarkedStrict ty = [(NotMarkedStrict, ty)]
601     unbox MarkedStrict    ty = [(MarkedStrict,    ty)]
602     unbox MarkedUnboxed   ty = zipEqual "computeRep" (dataConRepStrictness arg_dc) arg_tys
603                              where
604                                (_, _, arg_dc, arg_tys) = splitProductType "unbox_strict_arg_ty" ty
605 \end{code}