DsUtils.hs 33.7 KB
Newer Older
Austin Seipp's avatar
Austin Seipp committed
1 2 3 4
{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998

Simon Marlow's avatar
Simon Marlow committed
5 6

Utilities for desugaring
7 8

This module exports some utility functions of no great interest.
Austin Seipp's avatar
Austin Seipp committed
9
-}
10

11
{-# LANGUAGE CPP #-}
Ian Lynagh's avatar
Ian Lynagh committed
12

13
-- | Utility functions for constructing Core syntax, principally for desugaring
14
module DsUtils (
15 16
        EquationInfo(..),
        firstPat, shiftEqns,
17

18 19 20 21 22 23 24 25
        MatchResult(..), CanItFail(..), CaseAlt(..),
        cantFailMatchResult, alwaysFailMatchResult,
        extractMatchResult, combineMatchResults,
        adjustMatchResult,  adjustMatchResultDs,
        mkCoLetMatchResult, mkViewMatchResult, mkGuardedMatchResult,
        matchCanFail, mkEvalMatchResult,
        mkCoPrimCaseMatchResult, mkCoAlgCaseMatchResult, mkCoSynCaseMatchResult,
        wrapBind, wrapBinds,
26

27
        mkErrorAppDs, mkCoreAppDs, mkCoreAppsDs, mkCastDs,
28 29 30 31

        seqVar,

        -- LHs tuples
32
        mkLHsVarPatTup, mkLHsPatTup, mkVanillaTuplePat,
Simon Marlow's avatar
Simon Marlow committed
33
        mkBigLHsVarTupId, mkBigLHsTupId, mkBigLHsVarPatTupId, mkBigLHsPatTupId,
34 35 36

        mkSelectorBinds,

37
        selectSimpleMatchVarL, selectMatchVars, selectMatchVar,
38
        mkOptTickBox, mkBinaryTickBox, getUnBangedLPat
39 40
    ) where

41 42
#include "HsVersions.h"

43
import {-# SOURCE #-}   Match ( matchSimply )
44

45
import HsSyn
Simon Marlow's avatar
Simon Marlow committed
46
import TcHsSyn
47
import Coercion( Coercion, isReflCo )
48
import TcType( tcSplitTyConApp )
49 50
import CoreSyn
import DsMonad
cactus's avatar
cactus committed
51
import {-# SOURCE #-} DsExpr ( dsLExpr )
52

Simon Marlow's avatar
Simon Marlow committed
53
import CoreUtils
54
import MkCore
Simon Marlow's avatar
Simon Marlow committed
55 56 57 58
import MkId
import Id
import Literal
import TyCon
cactus's avatar
cactus committed
59
import ConLike
Simon Marlow's avatar
Simon Marlow committed
60
import DataCon
cactus's avatar
cactus committed
61
import PatSyn
Simon Marlow's avatar
Simon Marlow committed
62 63 64 65 66 67
import Type
import TysPrim
import TysWiredIn
import BasicTypes
import UniqSet
import UniqSupply
68
import Module
Simon Marlow's avatar
Simon Marlow committed
69
import PrelNames
sof's avatar
sof committed
70
import Outputable
Simon Marlow's avatar
Simon Marlow committed
71 72
import SrcLoc
import Util
Ian Lynagh's avatar
Ian Lynagh committed
73
import DynFlags
74
import FastString
75

cactus's avatar
cactus committed
76 77
import TcEvidence

78
import Control.Monad    ( zipWithM )
sof's avatar
sof committed
79

Austin Seipp's avatar
Austin Seipp committed
80 81 82
{-
************************************************************************
*                                                                      *
83
\subsection{ Selecting match variables}
Austin Seipp's avatar
Austin Seipp committed
84 85
*                                                                      *
************************************************************************
sof's avatar
sof committed
86 87 88 89 90

We're about to match against some patterns.  We want to make some
@Ids@ to use as match variables.  If a pattern has an @Id@ readily at
hand, which should indeed be bound to the pattern as a whole, then use it;
otherwise, make one up.
Austin Seipp's avatar
Austin Seipp committed
91
-}
sof's avatar
sof committed
92

93
selectSimpleMatchVarL :: LPat Id -> DsM Id
94
selectSimpleMatchVarL pat = selectMatchVar (unLoc pat)
95 96 97 98

-- (selectMatchVars ps tys) chooses variables of type tys
-- to use for matching ps against.  If the pattern is a variable,
-- we try to use that, to save inventing lots of fresh variables.
99 100 101
--
-- OLD, but interesting note:
--    But even if it is a variable, its type might not match.  Consider
102 103 104
--      data T a where
--        T1 :: Int -> T Int
--        T2 :: a   -> T a
105
--
106 107 108
--      f :: T a -> a -> Int
--      f (T1 i) (x::Int) = x
--      f (T2 i) (y::a)   = 0
109 110 111 112 113 114
--    Then we must not choose (x::Int) as the matching variable!
-- And nowadays we won't, because the (x::Int) will be wrapped in a CoPat

selectMatchVars :: [Pat Id] -> DsM [Id]
selectMatchVars ps = mapM selectMatchVar ps

115
selectMatchVar :: Pat Id -> DsM Id
116 117 118
selectMatchVar (BangPat pat) = selectMatchVar (unLoc pat)
selectMatchVar (LazyPat pat) = selectMatchVar (unLoc pat)
selectMatchVar (ParPat pat)  = selectMatchVar (unLoc pat)
119
selectMatchVar (VarPat var)  = return (localiseId var)  -- Note [Localise pattern binders]
120
selectMatchVar (AsPat var _) = return (unLoc var)
121
selectMatchVar other_pat     = newSysLocalDs (hsPatType other_pat)
122
                                  -- OK, better make up one...
sof's avatar
sof committed
123

Austin Seipp's avatar
Austin Seipp committed
124
{-
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
Note [Localise pattern binders]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider     module M where
               [Just a] = e
After renaming it looks like
             module M where
               [Just M.a] = e

We don't generalise, since it's a pattern binding, monomorphic, etc,
so after desugaring we may get something like
             M.a = case e of (v:_) ->
                   case v of Just M.a -> M.a
Notice the "M.a" in the pattern; after all, it was in the original
pattern.  However, after optimisation those pattern binders can become
let-binders, and then end up floated to top level.  They have a
different *unique* by then (the simplifier is good about maintaining
proper scoping), but it's BAD to have two top-level bindings with the
External Name M.a, because that turns into two linker symbols for M.a.
It's quite rare for this to actually *happen* -- the only case I know
144
of is tc003 compiled with the 'hpc' way -- but that only makes it
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
all the more annoying.

To avoid this, we craftily call 'localiseId' in the desugarer, which
simply turns the External Name for the Id into an Internal one, but
doesn't change the unique.  So the desugarer produces this:
             M.a{r8} = case e of (v:_) ->
                       case v of Just a{r8} -> M.a{r8}
The unique is still 'r8', but the binding site in the pattern
is now an Internal Name.  Now the simplifier's usual mechanisms
will propagate that Name to all the occurrence sites, as well as
un-shadowing it, so we'll get
             M.a{r8} = case e of (v:_) ->
                       case v of Just a{s77} -> a{s77}
In fact, even CoreSubst.simplOptExpr will do this, and simpleOptExpr
runs on the output of the desugarer, so all is well by the end of
the desugaring pass.

sof's avatar
sof committed
162

Austin Seipp's avatar
Austin Seipp committed
163 164 165 166 167
************************************************************************
*                                                                      *
* type synonym EquationInfo and access functions for its pieces        *
*                                                                      *
************************************************************************
168 169 170 171
\subsection[EquationInfo-synonym]{@EquationInfo@: a useful synonym}

The ``equation info'' used by @match@ is relatively complicated and
worthy of a type synonym and a few handy functions.
Austin Seipp's avatar
Austin Seipp committed
172
-}
173

174
firstPat :: EquationInfo -> Pat Id
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
175
firstPat eqn = ASSERT( notNull (eqn_pats eqn) ) head (eqn_pats eqn)
176

177
shiftEqns :: [EquationInfo] -> [EquationInfo]
178 179
-- Drop the first pattern in each equation
shiftEqns eqns = [ eqn { eqn_pats = tail (eqn_pats eqn) } | eqn <- eqns ]
180

Austin Seipp's avatar
Austin Seipp committed
181
-- Functions on MatchResults
182

183 184 185 186
matchCanFail :: MatchResult -> Bool
matchCanFail (MatchResult CanFail _)  = True
matchCanFail (MatchResult CantFail _) = False

187
alwaysFailMatchResult :: MatchResult
188
alwaysFailMatchResult = MatchResult CanFail (\fail -> return fail)
189

190
cantFailMatchResult :: CoreExpr -> MatchResult
191
cantFailMatchResult expr = MatchResult CantFail (\_ -> return expr)
192

193
extractMatchResult :: MatchResult -> CoreExpr -> DsM CoreExpr
194
extractMatchResult (MatchResult CantFail match_fn) _
195
  = match_fn (error "It can't fail!")
196

197 198 199
extractMatchResult (MatchResult CanFail match_fn) fail_expr = do
    (fail_bind, if_it_fails) <- mkFailurePair fail_expr
    body <- match_fn if_it_fails
200
    return (mkCoreLet fail_bind body)
201

202 203 204

combineMatchResults :: MatchResult -> MatchResult -> MatchResult
combineMatchResults (MatchResult CanFail      body_fn1)
205
                    (MatchResult can_it_fail2 body_fn2)
206 207
  = MatchResult can_it_fail2 body_fn
  where
208 209 210 211
    body_fn fail = do body2 <- body_fn2 fail
                      (fail_bind, duplicatable_expr) <- mkFailurePair body2
                      body1 <- body_fn1 duplicatable_expr
                      return (Let fail_bind body1)
212

213
combineMatchResults match_result1@(MatchResult CantFail _) _
214 215
  = match_result1

216
adjustMatchResult :: DsWrapper -> MatchResult -> MatchResult
217
adjustMatchResult encl_fn (MatchResult can_it_fail body_fn)
218
  = MatchResult can_it_fail (\fail -> encl_fn <$> body_fn fail)
219 220 221

adjustMatchResultDs :: (CoreExpr -> DsM CoreExpr) -> MatchResult -> MatchResult
adjustMatchResultDs encl_fn (MatchResult can_it_fail body_fn)
222
  = MatchResult can_it_fail (\fail -> encl_fn =<< body_fn fail)
223

224 225 226
wrapBinds :: [(Var,Var)] -> CoreExpr -> CoreExpr
wrapBinds [] e = e
wrapBinds ((new,old):prs) e = wrapBind new old (wrapBinds prs e)
227

228
wrapBind :: Var -> Var -> CoreExpr -> CoreExpr
229 230
wrapBind new old body   -- NB: this function must deal with term
  | new==old    = body  -- variables, type variables or coercion variables
231
  | otherwise   = Let (NonRec new (varToCoreExpr old)) body
232

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
233 234
seqVar :: Var -> CoreExpr -> CoreExpr
seqVar var body = Case (Var var) var (exprType body)
235
                        [(DEFAULT, [], body)]
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
236

237
mkCoLetMatchResult :: CoreBind -> MatchResult -> MatchResult
238
mkCoLetMatchResult bind = adjustMatchResult (mkCoreLet bind)
239

240 241 242
-- (mkViewMatchResult var' viewExpr var mr) makes the expression
-- let var' = viewExpr var in mr
mkViewMatchResult :: Id -> CoreExpr -> Id -> MatchResult -> MatchResult
243
mkViewMatchResult var' viewExpr var =
244
    adjustMatchResult (mkCoreLet (NonRec var' (mkCoreAppDs (text "mkView" <+> ppr var') viewExpr (Var var))))
245

246 247
mkEvalMatchResult :: Id -> Type -> MatchResult -> MatchResult
mkEvalMatchResult var ty
248
  = adjustMatchResult (\e -> Case (Var var) var ty [(DEFAULT, [], e)])
249 250

mkGuardedMatchResult :: CoreExpr -> MatchResult -> MatchResult
251
mkGuardedMatchResult pred_expr (MatchResult _ body_fn)
252 253
  = MatchResult CanFail (\fail -> do body <- body_fn fail
                                     return (mkIfThenElse pred_expr body fail))
254

255
mkCoPrimCaseMatchResult :: Id                           -- Scrutinee
256
                    -> Type                             -- Type of the case
257 258
                    -> [(Literal, MatchResult)]         -- Alternatives
                    -> MatchResult                      -- Literals are all unlifted
259
mkCoPrimCaseMatchResult var ty match_alts
260
  = MatchResult CanFail mk_case
261
  where
262 263 264
    mk_case fail = do
        alts <- mapM (mk_alt fail) sorted_alts
        return (Case (Var var) var ty ((DEFAULT, [], fail) : alts))
265

266
    sorted_alts = sortWith fst match_alts       -- Right order for a Case
267 268 269 270
    mk_alt fail (lit, MatchResult _ body_fn)
       = ASSERT( not (litIsLifted lit) )
         do body <- body_fn fail
            return (LitAlt lit, [], body)
271

cactus's avatar
cactus committed
272 273 274 275
data CaseAlt a = MkCaseAlt{ alt_pat :: a,
                            alt_bndrs :: [CoreBndr],
                            alt_wrapper :: HsWrapper,
                            alt_result :: MatchResult }
276

277
mkCoAlgCaseMatchResult
278
  :: DynFlags
cactus's avatar
cactus committed
279 280 281
  -> Id                 -- Scrutinee
  -> Type               -- Type of exp
  -> [CaseAlt DataCon]  -- Alternatives (bndrs *include* tyvars, dicts)
282
  -> MatchResult
283
mkCoAlgCaseMatchResult dflags var ty match_alts
cactus's avatar
cactus committed
284
  | isNewtype  -- Newtype case; use a let
285
  = ASSERT( null (tail match_alts) && null (tail arg_ids1) )
286
    mkCoLetMatchResult (NonRec arg_id1 newtype_rhs) match_result1
287

cactus's avatar
cactus committed
288 289 290 291
  | isPArrFakeAlts match_alts
  = MatchResult CanFail $ mkPArrCase dflags var ty (sort_alts match_alts)
  | otherwise
  = mkDataConCase var ty match_alts
292
  where
cactus's avatar
cactus committed
293 294
    isNewtype = isNewTyCon (dataConTyCon (alt_pat alt1))

295 296
        -- [Interesting: because of GADTs, we can't rely on the type of
        --  the scrutinised Id to be sufficiently refined to have a TyCon in it]
297

cactus's avatar
cactus committed
298 299 300 301 302
    alt1@MkCaseAlt{ alt_bndrs = arg_ids1, alt_result = match_result1 }
      = ASSERT( notNull match_alts ) head match_alts
    -- Stuff for newtype
    arg_id1       = ASSERT( notNull arg_ids1 ) head arg_ids1
    var_ty        = idType var
303 304
    (tc, ty_args) = tcSplitTyConApp var_ty      -- Don't look through newtypes
                                                -- (not that splitTyConApp does, these days)
chak@cse.unsw.edu.au.'s avatar
chak@cse.unsw.edu.au. committed
305
    newtype_rhs = unwrapNewTypeBody tc ty_args (Var var)
chak's avatar
chak committed
306

cactus's avatar
cactus committed
307 308
        --- Stuff for parallel arrays
        --
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
        -- Concerning `isPArrFakeAlts':
        --
        --  * it is *not* sufficient to just check the type of the type
        --   constructor, as we have to be careful not to confuse the real
        --   representation of parallel arrays with the fake constructors;
        --   moreover, a list of alternatives must not mix fake and real
        --   constructors (this is checked earlier on)
        --
        -- FIXME: We actually go through the whole list and make sure that
        --        either all or none of the constructors are fake parallel
        --        array constructors.  This is to spot equations that mix fake
        --        constructors with the real representation defined in
        --        `PrelPArr'.  It would be nicer to spot this situation
        --        earlier and raise a proper error message, but it can really
        --        only happen in `PrelPArr' anyway.
        --
cactus's avatar
cactus committed
325 326 327 328 329

    isPArrFakeAlts :: [CaseAlt DataCon] -> Bool
    isPArrFakeAlts [alt] = isPArrFakeCon (alt_pat alt)
    isPArrFakeAlts (alt:alts) =
      case (isPArrFakeCon (alt_pat alt), isPArrFakeAlts alts) of
chak's avatar
chak committed
330 331
        (True , True ) -> True
        (False, False) -> False
332 333
        _              -> panic "DsUtils: you may not mix `[:...:]' with `PArr' patterns"
    isPArrFakeAlts [] = panic "DsUtils: unexpectedly found an empty list of PArr fake alternatives"
cactus's avatar
cactus committed
334 335 336 337 338 339 340 341 342 343 344 345

mkCoSynCaseMatchResult :: Id -> Type -> CaseAlt PatSyn -> MatchResult
mkCoSynCaseMatchResult var ty alt = MatchResult CanFail $ mkPatSynCase var ty alt

sort_alts :: [CaseAlt DataCon] -> [CaseAlt DataCon]
sort_alts = sortWith (dataConTag . alt_pat)

mkPatSynCase :: Id -> Type -> CaseAlt PatSyn -> CoreExpr -> DsM CoreExpr
mkPatSynCase var ty alt fail = do
    matcher <- dsLExpr $ mkLHsWrap wrapper $ nlHsTyApp matcher [ty]
    let MatchResult _ mkCont = match_result
    cont <- mkCoreLams bndrs <$> mkCont fail
346
    return $ mkCoreAppsDs (text "patsyn" <+> ppr var) matcher [Var var, ensure_unstrict cont, Lam voidArgId fail]
cactus's avatar
cactus committed
347 348 349 350 351
  where
    MkCaseAlt{ alt_pat = psyn,
               alt_bndrs = bndrs,
               alt_wrapper = wrapper,
               alt_result = match_result} = alt
352
    (matcher, needs_void_lam) = patSynMatcher psyn
cactus's avatar
cactus committed
353

354
    -- See Note [Matchers and builders for pattern synonyms] in PatSyns
355
    -- on these extra Void# arguments
356 357
    ensure_unstrict cont | needs_void_lam = Lam voidArgId cont
                         | otherwise      = cont
358

cactus's avatar
cactus committed
359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
mkDataConCase :: Id -> Type -> [CaseAlt DataCon] -> MatchResult
mkDataConCase _   _  []            = panic "mkDataConCase: no alternatives"
mkDataConCase var ty alts@(alt1:_) = MatchResult fail_flag mk_case
  where
    con1          = alt_pat alt1
    tycon         = dataConTyCon con1
    data_cons     = tyConDataCons tycon
    match_results = map alt_result alts

    sorted_alts :: [CaseAlt DataCon]
    sorted_alts  = sort_alts alts

    var_ty       = idType var
    (_, ty_args) = tcSplitTyConApp var_ty -- Don't look through newtypes
                                          -- (not that splitTyConApp does, these days)

    mk_case :: CoreExpr -> DsM CoreExpr
    mk_case fail = do
        alts <- mapM (mk_alt fail) sorted_alts
        return $ mkWildCase (Var var) (idType var) ty (mk_default fail ++ alts)

    mk_alt :: CoreExpr -> CaseAlt DataCon -> DsM CoreAlt
    mk_alt fail MkCaseAlt{ alt_pat = con,
                           alt_bndrs = args,
                           alt_result = MatchResult _ body_fn }
      = do { body <- body_fn fail
           ; case dataConBoxer con of {
                Nothing -> return (DataAlt con, args, body) ;
                Just (DCB boxer) ->
        do { us <- newUniqueSupply
           ; let (rep_ids, binds) = initUs_ us (boxer ty_args args)
           ; return (DataAlt con, rep_ids, mkLets binds body) } } }

    mk_default :: CoreExpr -> [CoreAlt]
    mk_default fail | exhaustive_case = []
                    | otherwise       = [(DEFAULT, [], fail)]

    fail_flag :: CanItFail
    fail_flag | exhaustive_case
              = foldr orFail CantFail [can_it_fail | MatchResult can_it_fail _ <- match_results]
              | otherwise
              = CanFail

    mentioned_constructors = mkUniqSet $ map alt_pat alts
    un_mentioned_constructors
        = mkUniqSet data_cons `minusUniqSet` mentioned_constructors
    exhaustive_case = isEmptyUniqSet un_mentioned_constructors

--- Stuff for parallel arrays
--
--  * the following is to desugar cases over fake constructors for
--   parallel arrays, which are introduced by `tidy1' in the `PArrPat'
--   case
--
mkPArrCase :: DynFlags -> Id -> Type -> [CaseAlt DataCon] -> CoreExpr -> DsM CoreExpr
mkPArrCase dflags var ty sorted_alts fail = do
    lengthP <- dsDPHBuiltin lengthPVar
    alt <- unboxAlt
    return (mkWildCase (len lengthP) intTy ty [alt])
  where
    elemTy      = case splitTyConApp (idType var) of
        (_, [elemTy]) -> elemTy
        _             -> panic panicMsg
    panicMsg    = "DsUtils.mkCoAlgCaseMatchResult: not a parallel array?"
    len lengthP = mkApps (Var lengthP) [Type elemTy, Var var]
chak's avatar
chak committed
424
    --
cactus's avatar
cactus committed
425 426 427 428 429
    unboxAlt = do
        l      <- newSysLocalDs intPrimTy
        indexP <- dsDPHBuiltin indexPVar
        alts   <- mapM (mkAlt indexP) sorted_alts
        return (DataAlt intDataCon, [l], mkWildCase (Var l) intPrimTy ty (dft : alts))
chak's avatar
chak committed
430
      where
cactus's avatar
cactus committed
431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447
        dft  = (DEFAULT, [], fail)

    --
    -- each alternative matches one array length (corresponding to one
    -- fake array constructor), so the match is on a literal; each
    -- alternative's body is extended by a local binding for each
    -- constructor argument, which are bound to array elements starting
    -- with the first
    --
    mkAlt indexP alt@MkCaseAlt{alt_result = MatchResult _ bodyFun} = do
        body <- bodyFun fail
        return (LitAlt lit, [], mkCoreLets binds body)
      where
        lit   = MachInt $ toInteger (dataConSourceArity (alt_pat alt))
        binds = [NonRec arg (indexExpr i) | (i, arg) <- zip [1..] (alt_bndrs alt)]
        --
        indexExpr i = mkApps (Var indexP) [Type elemTy, Var var, mkIntExpr dflags i]
448

Austin Seipp's avatar
Austin Seipp committed
449 450 451
{-
************************************************************************
*                                                                      *
452
\subsection{Desugarer's versions of some Core functions}
Austin Seipp's avatar
Austin Seipp committed
453 454 455
*                                                                      *
************************************************************************
-}
456

457 458 459 460
mkErrorAppDs :: Id              -- The error function
             -> Type            -- Type to which it should be applied
             -> SDoc            -- The error message string to pass
             -> DsM CoreExpr
461

462 463
mkErrorAppDs err_id ty msg = do
    src_loc <- getSrcSpanDs
Ian Lynagh's avatar
Ian Lynagh committed
464
    dflags <- getDynFlags
465
    let
466
        full_msg = showSDoc dflags (hcat [ppr src_loc, vbar, msg])
467 468
        core_msg = Lit (mkMachString full_msg)
        -- mkMachString returns a result of type String#
469
    return (mkApps (Var err_id) [Type ty, core_msg])
470

Austin Seipp's avatar
Austin Seipp committed
471
{-
472 473 474 475 476 477
'mkCoreAppDs' and 'mkCoreAppsDs' hand the special-case desugaring of 'seq'.

Note [Desugaring seq (1)]  cf Trac #1031
~~~~~~~~~~~~~~~~~~~~~~~~~
   f x y = x `seq` (y `seq` (# x,y #))

478
The [CoreSyn let/app invariant] means that, other things being equal, because
479 480 481 482
the argument to the outer 'seq' has an unlifted type, we'll use call-by-value thus:

   f x y = case (y `seq` (# x,y #)) of v -> x `seq` v

483 484
But that is bad for two reasons:
  (a) we now evaluate y before x, and
485 486 487 488 489
  (b) we can't bind v to an unboxed pair

Seq is very, very special!  So we recognise it right here, and desugar to
        case x of _ -> case y of _ -> (# x,y #)

simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
490
Note [Desugaring seq (2)]  cf Trac #2273
491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517
~~~~~~~~~~~~~~~~~~~~~~~~~
Consider
   let chp = case b of { True -> fst x; False -> 0 }
   in chp `seq` ...chp...
Here the seq is designed to plug the space leak of retaining (snd x)
for too long.

If we rely on the ordinary inlining of seq, we'll get
   let chp = case b of { True -> fst x; False -> 0 }
   case chp of _ { I# -> ...chp... }

But since chp is cheap, and the case is an alluring contet, we'll
inline chp into the case scrutinee.  Now there is only one use of chp,
so we'll inline a second copy.  Alas, we've now ruined the purpose of
the seq, by re-introducing the space leak:
    case (case b of {True -> fst x; False -> 0}) of
      I# _ -> ...case b of {True -> fst x; False -> 0}...

We can try to avoid doing this by ensuring that the binder-swap in the
case happens, so we get his at an early stage:
   case chp of chp2 { I# -> ...chp2... }
But this is fragile.  The real culprit is the source program.  Perhaps we
should have said explicitly
   let !chp2 = chp in ...chp2...

But that's painful.  So the code here does a little hack to make seq
more robust: a saturated application of 'seq' is turned *directly* into
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
518 519 520 521 522
the case expression, thus:
   x  `seq` e2 ==> case x of x -> e2    -- Note shadowing!
   e1 `seq` e2 ==> case x of _ -> e2

So we desugar our example to:
523 524
   let chp = case b of { True -> fst x; False -> 0 }
   case chp of chp { I# -> ...chp... }
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
525
And now all is well.
526 527

The reason it's a hack is because if you define mySeq=seq, the hack
528
won't work on mySeq.
529 530 531

Note [Desugaring seq (3)] cf Trac #2409
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
532
The isLocalId ensures that we don't turn
533 534 535
        True `seq` e
into
        case True of True { ... }
536
which stupidly tries to bind the datacon 'True'.
Austin Seipp's avatar
Austin Seipp committed
537
-}
538

539 540
mkCoreAppDs  :: SDoc -> CoreExpr -> CoreExpr -> CoreExpr
mkCoreAppDs _ (Var f `App` Type ty1 `App` Type ty2 `App` arg1) arg2
541 542 543 544 545
  | f `hasKey` seqIdKey            -- Note [Desugaring seq (1), (2)]
  = Case arg1 case_bndr ty2 [(DEFAULT,[],arg2)]
  where
    case_bndr = case arg1 of
                   Var v1 | isLocalId v1 -> v1        -- Note [Desugaring seq (2) and (3)]
546
                   _                     -> mkWildValBinder ty1
547

548
mkCoreAppDs s fun arg = mkCoreApp s fun arg  -- The rest is done in MkCore
549

550 551
mkCoreAppsDs :: SDoc -> CoreExpr -> [CoreExpr] -> CoreExpr
mkCoreAppsDs s fun args = foldl (mkCoreAppDs s) fun args
552

553 554 555 556 557 558 559 560 561 562 563 564
mkCastDs :: CoreExpr -> Coercion -> CoreExpr
-- We define a desugarer-specific verison of CoreUtils.mkCast,
-- because in the immediate output of the desugarer, we can have
-- apparently-mis-matched coercions:  E.g.
--     let a = b
--     in (x :: a) |> (co :: b ~ Int)
-- Lint know about type-bindings for let and does not complain
-- So here we do not make the assertion checks that we make in
-- CoreUtils.mkCast; and we do less peephole optimisation too
mkCastDs e co | isReflCo co = e
              | otherwise   = Cast e co

Austin Seipp's avatar
Austin Seipp committed
565 566 567
{-
************************************************************************
*                                                                      *
568
               Tuples and selector bindings
Austin Seipp's avatar
Austin Seipp committed
569 570
*                                                                      *
************************************************************************
571 572 573

This is used in various places to do with lazy patterns.
For each binder $b$ in the pattern, we create a binding:
574
\begin{verbatim}
575
    b = case v of pat' -> b'
576 577
\end{verbatim}
where @pat'@ is @pat@ with each binder @b@ cloned into @b'@.
578 579 580 581 582 583 584 585 586 587

ToDo: making these bindings should really depend on whether there's
much work to be done per binding.  If the pattern is complex, it
should be de-mangled once, into a tuple (and then selected from).
Otherwise the demangling can be in-line in the bindings (as here).

Boring!  Boring!  One error message per binder.  The above ToDo is
even more helpful.  Something very similar happens for pattern-bound
expressions.

588 589 590 591 592 593 594
Note [mkSelectorBinds]
~~~~~~~~~~~~~~~~~~~~~~
Given   p = e, where p binds x,y
we are going to make EITHER

EITHER (A)   v = e   (where v is fresh)
             x = case v of p -> x
Ian Lynagh's avatar
Ian Lynagh committed
595
             y = case v of p -> y
596 597 598 599 600

OR (B)       t = case e of p -> (x,y)
             x = case t of (x,_) -> x
             y = case t of (_,y) -> y

601
We do (A) when
602
 * Matching the pattern is cheap so we don't mind
603
   doing it twice.
604 605
 * Or if the pattern binds only one variable (so we'll only
   match once)
606
 * AND the pattern can't fail (else we tiresomely get two inexhaustive
607 608 609 610 611 612
   pattern warning messages)

Otherwise we do (B).  Really (A) is just an optimisation for very common
cases like
     Just x = e
     (p,q) = e
Austin Seipp's avatar
Austin Seipp committed
613
-}
614

615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632
mkSelectorBinds :: Bool           -- ^ is strict
                -> [[Tickish Id]] -- ^ ticks to add, possibly
                -> LPat Id        -- ^ The pattern
                -> CoreExpr       -- ^ Expression to which the pattern is bound
                -> DsM (Maybe Id,[(Id,CoreExpr)])
                -- ^ Id the rhs is bound to, for desugaring strict
                -- binds (see Note [Desugar Strict binds] in DsBinds)
                -- and all the desugared binds

mkSelectorBinds _ ticks (L _ (VarPat v)) val_expr
  = return (Just v
           ,[(v, case ticks of
                    [t] -> mkOptTickBox t val_expr
                    _   -> val_expr)])

mkSelectorBinds is_strict ticks pat val_expr
  | null binders, not is_strict
  = return (Nothing, [])
633 634 635 636
  | isSingleton binders || is_simple_lpat pat
    -- See Note [mkSelectorBinds]
  = do { val_var <- newSysLocalDs (hsLPatType pat)
        -- Make up 'v' in Note [mkSelectorBinds]
637
        -- NB: give it the type of *pattern* p, not the type of the *rhs* e.
638
        -- This does not matter after desugaring, but there's a subtle
639 640 641 642 643 644 645 646 647 648 649
        -- issue with implicit parameters. Consider
        --      (x,y) = ?i
        -- Then, ?i is given type {?i :: Int}, a PredType, which is opaque
        -- to the desugarer.  (Why opaque?  Because newtypes have to be.  Why
        -- does it get that type?  So that when we abstract over it we get the
        -- right top-level type  (?i::Int) => ...)
        --
        -- So to get the type of 'v', use the pattern not the rhs.  Often more
        -- efficient too.

        -- For the error message we make one error-app, to avoid duplication.
650 651 652 653 654
        -- But we need it at different types, so we make it polymorphic:
        --     err_var = /\a. iRREFUT_PAT_ERR a "blah blah blah"
       ; err_app <- mkErrorAppDs iRREFUT_PAT_ERROR_ID alphaTy (ppr pat)
       ; err_var <- newSysLocalDs (mkForAllTy alphaTyVar alphaTy)
       ; binds   <- zipWithM (mk_bind val_var err_var) ticks' binders
655 656 657 658
       ; return (Just val_var
                ,(val_var, val_expr) :
                 (err_var, Lam alphaTyVar err_app) :
                 binds) }
659 660

  | otherwise
661 662 663 664
  = do { val_var <- newSysLocalDs (hsLPatType pat)
       ; error_expr <- mkErrorAppDs iRREFUT_PAT_ERROR_ID tuple_ty (ppr pat)
       ; tuple_expr
           <- matchSimply (Var val_var) PatBindRhs pat local_tuple error_expr
665
       ; tuple_var <- newSysLocalDs tuple_ty
666 667 668 669
       ; let mk_tup_bind tick binder
              = (binder, mkOptTickBox tick $
                            mkTupleSelector local_binders binder
                                            tuple_var (Var tuple_var))
670 671 672 673 674 675 676 677 678 679
         -- if strict and no binders we want to force the case
         -- expression to force an error if the pattern match
         -- failed. See Note [Desugar Strict binds] in DsBinds.
       ; let force_var = if null binders && is_strict
                         then tuple_var
                         else val_var
       ; return (Just force_var
                ,(val_var,val_expr) :
                 (tuple_var, tuple_expr) :
                 zipWith mk_tup_bind ticks' binders) }
680
  where
681
    binders       = collectPatBinders pat
682
    ticks'        = ticks ++ repeat []
683 684

    local_binders = map localiseId binders      -- See Note [Localise pattern binders]
685 686
    local_tuple   = mkBigCoreVarTup binders
    tuple_ty      = exprType local_tuple
687

688
    mk_bind scrut_var err_var tick bndr_var = do
689
    -- (mk_bind sv err_var) generates
690
    --          bv = case sv of { pat -> bv; other -> err_var @ type-of-bv }
691
    -- Remember, pat binds bv
692 693
        rhs_expr <- matchSimply (Var scrut_var) PatBindRhs pat
                                (Var bndr_var) error_expr
694
        return (bndr_var, mkOptTickBox tick rhs_expr)
695
      where
696
        error_expr = Var err_var `App` Type (idType bndr_var)
697

698 699
    is_simple_lpat p = is_simple_pat (unLoc p)

700
    is_simple_pat (TuplePat ps Boxed _) = all is_triv_lpat ps
cactus's avatar
cactus committed
701 702 703 704
    is_simple_pat pat@(ConPatOut{})     = case unLoc (pat_con pat) of
        RealDataCon con -> isProductTyCon (dataConTyCon con)
                           && all is_triv_lpat (hsConPatArgs (pat_args pat))
        PatSynCon _     -> False
705 706 707
    is_simple_pat (VarPat _)                   = True
    is_simple_pat (ParPat p)                   = is_simple_lpat p
    is_simple_pat _                                    = False
708

709 710
    is_triv_lpat p = is_triv_pat (unLoc p)

711
    is_triv_pat (VarPat _)  = True
712
    is_triv_pat (WildPat _) = True
713
    is_triv_pat (ParPat p)  = is_triv_lpat p
714 715
    is_triv_pat _           = False

Austin Seipp's avatar
Austin Seipp committed
716
{-
717 718 719
Creating big tuples and their types for full Haskell expressions.
They work over *Ids*, and create tuples replete with their types,
which is whey they are not in HsUtils.
Austin Seipp's avatar
Austin Seipp committed
720
-}
721 722

mkLHsPatTup :: [LPat Id] -> LPat Id
723
mkLHsPatTup []     = noLoc $ mkVanillaTuplePat [] Boxed
724
mkLHsPatTup [lpat] = lpat
725 726
mkLHsPatTup lpats  = L (getLoc (head lpats)) $
                     mkVanillaTuplePat lpats Boxed
727

728 729 730 731 732
mkLHsVarPatTup :: [Id] -> LPat Id
mkLHsVarPatTup bs  = mkLHsPatTup (map nlVarPat bs)

mkVanillaTuplePat :: [OutPat Id] -> Boxity -> Pat Id
-- A vanilla tuple pattern simply gets its type from its sub-patterns
733
mkVanillaTuplePat pats box = TuplePat pats box (map hsLPatType pats)
734

735
-- The Big equivalents for the source tuple expressions
Simon Marlow's avatar
Simon Marlow committed
736 737
mkBigLHsVarTupId :: [Id] -> LHsExpr Id
mkBigLHsVarTupId ids = mkBigLHsTupId (map nlHsVar ids)
738

Simon Marlow's avatar
Simon Marlow committed
739 740
mkBigLHsTupId :: [LHsExpr Id] -> LHsExpr Id
mkBigLHsTupId = mkChunkified mkLHsTupleExpr
741 742

-- The Big equivalents for the source tuple patterns
Simon Marlow's avatar
Simon Marlow committed
743 744
mkBigLHsVarPatTupId :: [Id] -> LPat Id
mkBigLHsVarPatTupId bs = mkBigLHsPatTupId (map nlVarPat bs)
745

Simon Marlow's avatar
Simon Marlow committed
746 747
mkBigLHsPatTupId :: [LPat Id] -> LPat Id
mkBigLHsPatTupId = mkChunkified mkLHsPatTup
748

Austin Seipp's avatar
Austin Seipp committed
749 750 751
{-
************************************************************************
*                                                                      *
752
        Code for pattern-matching and other failures
Austin Seipp's avatar
Austin Seipp committed
753 754
*                                                                      *
************************************************************************
755 756 757 758

Generally, we handle pattern matching failure like this: let-bind a
fail-variable, and use that variable if the thing fails:
\begin{verbatim}
759 760 761 762 763 764 765
        let fail.33 = error "Help"
        in
        case x of
                p1 -> ...
                p2 -> fail.33
                p3 -> fail.33
                p4 -> ...
766 767 768 769
\end{verbatim}
Then
\begin{itemize}
\item
770
If the case can't fail, then there'll be no mention of @fail.33@, and the
771 772 773 774 775 776 777 778 779 780
simplifier will later discard it.

\item
If it can fail in only one way, then the simplifier will inline it.

\item
Only if it is used more than once will the let-binding remain.
\end{itemize}

There's a problem when the result of the case expression is of
781
unboxed type.  Then the type of @fail.33@ is unboxed too, and
782 783
there is every chance that someone will change the let into a case:
\begin{verbatim}
784 785
        case error "Help" of
          fail.33 -> case ....
786 787 788
\end{verbatim}

which is of course utterly wrong.  Rather than drop the condition that
789
only boxed types can be let-bound, we just turn the fail into a function
790 791
for the primitive case:
\begin{verbatim}
792 793 794 795 796 797 798 799
        let fail.33 :: Void -> Int#
            fail.33 = \_ -> error "Help"
        in
        case x of
                p1 -> ...
                p2 -> fail.33 void
                p3 -> fail.33 void
                p4 -> ...
800 801
\end{verbatim}

802
Now @fail.33@ is a function, so it can be let-bound.
Austin Seipp's avatar
Austin Seipp committed
803
-}
804

805 806 807 808
mkFailurePair :: CoreExpr       -- Result type of the whole case expression
              -> DsM (CoreBind, -- Binds the newly-created fail variable
                                -- to \ _ -> expression
                      CoreExpr) -- Fail variable applied to realWorld#
809
-- See Note [Failure thunks and CPR]
810
mkFailurePair expr
811 812 813 814 815
  = do { fail_fun_var <- newFailLocalDs (voidPrimTy `mkFunTy` ty)
       ; fail_fun_arg <- newSysLocalDs voidPrimTy
       ; let real_arg = setOneShotLambda fail_fun_arg
       ; return (NonRec fail_fun_var (Lam real_arg expr),
                 App (Var fail_fun_var) (Var voidPrimId)) }
816
  where
817
    ty = exprType expr
818

Austin Seipp's avatar
Austin Seipp committed
819
{-
820 821 822 823 824 825
Note [Failure thunks and CPR]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When we make a failure point we ensure that it
does not look like a thunk. Example:

   let fail = \rw -> error "urk"
826
   in case x of
827 828
        [] -> fail realWorld#
        (y:ys) -> case ys of
829
                    [] -> fail realWorld#
830 831 832 833 834 835 836
                    (z:zs) -> (y,z)

Reason: we know that a failure point is always a "join point" and is
entered at most once.  Adding a dummy 'realWorld' token argument makes
it clear that sharing is not an issue.  And that in turn makes it more
CPR-friendly.  This matters a lot: if you don't get it right, you lose
the tail call property.  For example, see Trac #3403.
837 838 839 840 841 842 843


************************************************************************
*                                                                      *
              Ticks
*                                                                      *
********************************************************************* -}
844

845 846
mkOptTickBox :: [Tickish Id] -> CoreExpr -> CoreExpr
mkOptTickBox = flip (foldr Tick)
andy@galois.com's avatar
andy@galois.com committed
847 848 849

mkBinaryTickBox :: Int -> Int -> CoreExpr -> DsM CoreExpr
mkBinaryTickBox ixT ixF e = do
850
       uq <- newUnique
851
       this_mod <- getModule
852 853 854 855 856
       let bndr1 = mkSysLocal (fsLit "t1") uq boolTy
       let
           falseBox = Tick (HpcTick this_mod ixF) (Var falseDataConId)
           trueBox  = Tick (HpcTick this_mod ixT) (Var trueDataConId)
       --
857 858 859 860
       return $ Case e bndr1 boolTy
                       [ (DataAlt falseDataCon, [], falseBox)
                       , (DataAlt trueDataCon,  [], trueBox)
                       ]
861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888



-- *******************************************************************


-- | Remove any bang from a pattern and say if it is a strict bind,
-- also make irrefutable patterns ordinary patterns if -XStrict.
--
-- Example:
-- ~pat    => False, pat -- when -XStrict
-- ~pat    => False, ~pat -- without -XStrict
-- ~(~pat) => False, ~pat -- when -XStrict
-- pat     => True, pat -- when -XStrict
-- !pat    => True, pat -- always
getUnBangedLPat :: DynFlags
                -> LPat id  -- ^ Original pattern
                -> (Bool, LPat id) -- is bind strict?, pattern without bangs
getUnBangedLPat dflags (L l (ParPat p))
  = let (is_strict, p') = getUnBangedLPat dflags p
    in (is_strict, L l (ParPat p'))
getUnBangedLPat _ (L _ (BangPat p))
  = (True,p)
getUnBangedLPat dflags (L _ (LazyPat p))
  | xopt Opt_Strict dflags
  = (False,p)
getUnBangedLPat dflags p
  = (xopt Opt_Strict dflags,p)