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