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