ghc/compiler/coreSyn/Subst.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   3 %
   4 \section[CoreUtils]{Utility functions on @Core@ syntax}
   5
   6 \begin{code}
   7 module Subst (
   8         -- In-scope set
   9         InScopeSet, emptyInScopeSet,
  10         lookupInScope, setInScope, extendInScope, extendInScopes, isInScope, modifyInScope,
  11
  12         -- Substitution stuff
  13         Subst, TyVarSubst, IdSubst,
  14         emptySubst, mkSubst, substEnv, substInScope,
  15         lookupSubst, lookupIdSubst, isEmptySubst, extendSubst, extendSubstList,
  16         zapSubstEnv, setSubstEnv,
  17
  18         bindSubst, unBindSubst, bindSubstList, unBindSubstList,
  19
  20         -- Binders
  21         substBndr, substBndrs, substTyVar, substId, substIds,
  22         substAndCloneId, substAndCloneIds,
  23
  24         -- Type stuff
  25         mkTyVarSubst, mkTopTyVarSubst,
  26         substTy, substClasses, substTheta,
  27
  28         -- Expression stuff
  29         substExpr, substIdInfo
  30     ) where
  31
  32 #include "HsVersions.h"
  33
  34 import CoreSyn          ( Expr(..), Bind(..), Note(..), CoreExpr, CoreBndr,
  35                           CoreRules(..), CoreRule(..),
  36                           emptyCoreRules, isEmptyCoreRules, seqRules
  37                         )
  38 import CoreFVs          ( exprFreeVars, mustHaveLocalBinding )
  39 import TypeRep          ( Type(..), TyNote(..),
  40                         )  -- friend
  41 import Type             ( ThetaType, PredType(..), ClassContext,
  42                           tyVarsOfType, tyVarsOfTypes, mkAppTy
  43                         )
  44 import VarSet
  45 import VarEnv
  46 import Var              ( setVarUnique, isId )
  47 import Id               ( idType, setIdType, idOccInfo, zapFragileIdInfo )
  48 import IdInfo           ( IdInfo, isFragileOccInfo,
  49                           specInfo, setSpecInfo,
  50                           WorkerInfo(..), workerExists, workerInfo, setWorkerInfo, WorkerInfo
  51                         )
  52 import BasicTypes       ( OccInfo(..) )
  53 import UniqSupply       ( UniqSupply, uniqFromSupply, splitUniqSupply )
  54 import Var              ( Var, Id, TyVar, isTyVar )
  55 import Outputable
  56 import PprCore          ()      -- Instances
  57 import Util             ( mapAccumL, foldl2, seqList, ($!) )
  58 \end{code}
  59
  60 %************************************************************************
  61 %*                                                                      *
  62 \subsection{Substitutions}
  63 %*                                                                      *
  64 %************************************************************************
  65
  66 \begin{code}
  67 type InScopeSet = VarEnv Var
  68
  69 data Subst = Subst InScopeSet           -- In scope
  70                    SubstEnv             -- Substitution itself
  71         -- INVARIANT 1: The (domain of the) in-scope set is a superset
  72         --              of the free vars of the range of the substitution
  73         --              that might possibly clash with locally-bound variables
  74         --              in the thing being substituted in.
  75         -- This is what lets us deal with name capture properly
  76         -- It's a hard invariant to check...
  77         -- There are various ways of causing it to happen:
  78         --      - arrange that the in-scope set really is all the things in scope
  79         --      - arrange that it's the free vars of the range of the substitution
  80         --      - make it empty because all the free vars of the subst are fresh,
  81         --              and hence can't possibly clash.a
  82         --
  83         -- INVARIANT 2: No variable is both in scope and in the domain of the substitution
  84         --              Equivalently, the substitution is idempotent
  85         --
  86
  87 type IdSubst    = Subst
  88 \end{code}
  89
  90 The general plan about the substitution and in-scope set for Ids is as follows
  91
  92 * substId always adds new_id to the in-scope set.
  93   new_id has a correctly-substituted type, but all its fragile IdInfo has been zapped.
  94   That is added back in later.  So new_id is the minimal thing it's
  95   correct to substitute.
  96
  97 * substId adds a binding (DoneVar new_id occ) to the substitution if
  98         EITHER the Id's unique has changed
  99         OR     the Id has interesting occurrence information
 100   So in effect you can only get to interesting occurrence information
 101   by looking up the *old* Id; it's not really attached to the new id
 102   at all.
 103
 104   Note, though that the substitution isn't necessarily extended
 105   if the type changes.  Why not?  Because of the next point:
 106
 107 * We *always, always* finish by looking up in the in-scope set
 108   any variable that doesn't get a DoneEx or DoneVar hit in the substitution.
 109   Reason: so that we never finish up with a "old" Id in the result.
 110   An old Id might point to an old unfolding and so on... which gives a space leak.
 111
 112   [The DoneEx and DoneVar hits map to "new" stuff.]
 113
 114 * It follows that substExpr must not do a no-op if the substitution is empty.
 115   substType is free to do so, however.
 116
 117 * When we come to a let-binding (say) we generate new IdInfo, including an
 118   unfolding, attach it to the binder, and add this newly adorned binder to
 119   the in-scope set.  So all subsequent occurrences of the binder will get mapped
 120   to the full-adorned binder, which is also the one put in the binding site.
 121
 122 * The in-scope "set" usually maps x->x; we use it simply for its domain.
 123   But sometimes we have two in-scope Ids that are synomyms, and should
 124   map to the same target:  x->x, y->x.  Notably:
 125         case y of x { ... }
 126   That's why the "set" is actually a VarEnv Var
 127
 128 \begin{code}
 129 emptyInScopeSet :: InScopeSet
 130 emptyInScopeSet = emptyVarSet
 131
 132 add_in_scope :: InScopeSet -> Var -> InScopeSet
 133 add_in_scope in_scope v = extendVarEnv in_scope v v
 134 \end{code}
 135
 136
 137
 138 \begin{code}
 139 isEmptySubst :: Subst -> Bool
 140 isEmptySubst (Subst _ env) = isEmptySubstEnv env
 141
 142 emptySubst :: Subst
 143 emptySubst = Subst emptyInScopeSet emptySubstEnv
 144
 145 mkSubst :: InScopeSet -> SubstEnv -> Subst
 146 mkSubst in_scope env = Subst in_scope env
 147
 148 substEnv :: Subst -> SubstEnv
 149 substEnv (Subst _ env) = env
 150
 151 substInScope :: Subst -> InScopeSet
 152 substInScope (Subst in_scope _) = in_scope
 153
 154 zapSubstEnv :: Subst -> Subst
 155 zapSubstEnv (Subst in_scope env) = Subst in_scope emptySubstEnv
 156
 157 extendSubst :: Subst -> Var -> SubstResult -> Subst
 158 extendSubst (Subst in_scope env) v r = Subst in_scope (extendSubstEnv env v r)
 159
 160 extendSubstList :: Subst -> [Var] -> [SubstResult] -> Subst
 161 extendSubstList (Subst in_scope env) v r = Subst in_scope (extendSubstEnvList env v r)
 162
 163 lookupSubst :: Subst -> Var -> Maybe SubstResult
 164 lookupSubst (Subst _ env) v = lookupSubstEnv env v
 165
 166 lookupIdSubst :: Subst -> Id -> SubstResult
 167 -- Does the lookup in the in-scope set too
 168 lookupIdSubst (Subst in_scope env) v
 169   = case lookupSubstEnv env v of
 170         Just (DoneId v' occ) -> DoneId (lookupInScope in_scope v') occ
 171         Just res             -> res
 172         Nothing              -> DoneId v' (idOccInfo v')
 173                                 -- We don't use DoneId for LoopBreakers, so the idOccInfo is
 174                                 -- very important!  If isFragileOccInfo returned True for
 175                                 -- loop breakers we could avoid this call, but at the expense
 176                                 -- of adding more to the substitution, and building new Ids
 177                                 -- in substId a bit more often than really necessary
 178                              where
 179                                     v' = lookupInScope in_scope v
 180
 181 lookupInScope :: InScopeSet -> Var -> Var
 182 -- It's important to look for a fixed point
 183 -- When we see (case x of y { I# v -> ... })
 184 -- we add  [x -> y] to the in-scope set (Simplify.simplCaseBinder).
 185 -- When we lookup up an occurrence of x, we map to y, but then
 186 -- we want to look up y in case it has acquired more evaluation information by now.
 187 lookupInScope in_scope v
 188   = case lookupVarEnv in_scope v of
 189         Just v' | v == v'   -> v'       -- Reached a fixed point
 190                 | otherwise -> lookupInScope in_scope v'
 191         Nothing             -> WARN( mustHaveLocalBinding v, ppr v )
 192                                v
 193
 194 isInScope :: Var -> Subst -> Bool
 195 isInScope v (Subst in_scope _) = v `elemVarEnv` in_scope
 196
 197 extendInScope :: Subst -> Var -> Subst
 198 extendInScope (Subst in_scope env) v = Subst (in_scope `add_in_scope` v) env
 199
 200 modifyInScope :: Subst -> Var -> Var -> Subst
 201 modifyInScope (Subst in_scope env) old_v new_v = Subst (extendVarEnv in_scope old_v new_v) env
 202         -- make old_v map to new_v
 203
 204 extendInScopes :: Subst -> [Var] -> Subst
 205 extendInScopes (Subst in_scope env) vs = Subst (foldl add_in_scope in_scope vs) env
 206
 207 -------------------------------
 208 bindSubst :: Subst -> Var -> Var -> Subst
 209 -- Extend with a substitution, v1 -> Var v2
 210 -- and extend the in-scopes with v2
 211 bindSubst (Subst in_scope env) old_bndr new_bndr
 212   = Subst (in_scope `add_in_scope` new_bndr)
 213           (extendSubstEnv env old_bndr subst_result)
 214   where
 215     subst_result | isId old_bndr = DoneEx (Var new_bndr)
 216                  | otherwise     = DoneTy (TyVarTy new_bndr)
 217
 218 unBindSubst :: Subst -> Var -> Var -> Subst
 219 -- Reverse the effect of bindSubst
 220 -- If old_bndr was already in the substitution, this doesn't quite work
 221 unBindSubst (Subst in_scope env) old_bndr new_bndr
 222   = Subst (in_scope `delVarEnv` new_bndr) (delSubstEnv env old_bndr)
 223
 224 -- And the "List" forms
 225 bindSubstList :: Subst -> [Var] -> [Var] -> Subst
 226 bindSubstList subst old_bndrs new_bndrs
 227   = foldl2 bindSubst subst old_bndrs new_bndrs
 228
 229 unBindSubstList :: Subst -> [Var] -> [Var] -> Subst
 230 unBindSubstList subst old_bndrs new_bndrs
 231   = foldl2 unBindSubst subst old_bndrs new_bndrs
 232
 233
 234 -------------------------------
 235 setInScope :: Subst     -- Take env part from here
 236            -> InScopeSet
 237            -> Subst
 238 setInScope (Subst in_scope1 env1) in_scope2
 239   = Subst in_scope2 env1
 240
 241 setSubstEnv :: Subst            -- Take in-scope part from here
 242             -> SubstEnv         -- ... and env part from here
 243             -> Subst
 244 setSubstEnv (Subst in_scope1 _) env2 = Subst in_scope1 env2
 245 \end{code}
 246
 247
 248 %************************************************************************
 249 %*                                                                      *
 250 \subsection{Type substitution}
 251 %*                                                                      *
 252 %************************************************************************
 253
 254 \begin{code}
 255 type TyVarSubst    = Subst      -- TyVarSubst are expected to have range elements
 256         -- (We could have a variant of Subst, but it doesn't seem worth it.)
 257
 258 -- mkTyVarSubst generates the in-scope set from
 259 -- the types given; but it's just a thunk so with a bit of luck
 260 -- it'll never be evaluated
 261 mkTyVarSubst :: [TyVar] -> [Type] -> Subst
 262 mkTyVarSubst tyvars tys = Subst (tyVarsOfTypes tys) (zip_ty_env tyvars tys emptySubstEnv)
 263
 264 -- mkTopTyVarSubst is called when doing top-level substitutions.
 265 -- Here we expect that the free vars of the range of the
 266 -- substitution will be empty.
 267 mkTopTyVarSubst :: [TyVar] -> [Type] -> Subst
 268 mkTopTyVarSubst tyvars tys = Subst emptyInScopeSet (zip_ty_env tyvars tys emptySubstEnv)
 269
 270 zip_ty_env []       []       env = env
 271 zip_ty_env (tv:tvs) (ty:tys) env = zip_ty_env tvs tys (extendSubstEnv env tv (DoneTy ty))
 272 \end{code}
 273
 274 substTy works with general Substs, so that it can be called from substExpr too.
 275
 276 \begin{code}
 277 substTy :: Subst -> Type  -> Type
 278 substTy subst ty | isEmptySubst subst = ty
 279                  | otherwise          = subst_ty subst ty
 280
 281 substClasses :: TyVarSubst -> ClassContext -> ClassContext
 282 substClasses subst theta
 283   | isEmptySubst subst = theta
 284   | otherwise          = [(clas, map (subst_ty subst) tys) | (clas, tys) <- theta]
 285
 286 substTheta :: TyVarSubst -> ThetaType -> ThetaType
 287 substTheta subst theta
 288   | isEmptySubst subst = theta
 289   | otherwise          = map (substPred subst) theta
 290
 291 substPred :: TyVarSubst -> PredType -> PredType
 292 substPred subst (Class clas tys) = Class clas (map (subst_ty subst) tys)
 293 substPred subst (IParam n ty)    = IParam n (subst_ty subst ty)
 294
 295 subst_ty subst ty
 296    = go ty
 297   where
 298     go (TyConApp tc tys)           = let args = map go tys
 299                                      in  args `seqList` TyConApp tc args
 300     go (NoteTy (SynNote ty1) ty2)  = NoteTy (SynNote $! (go ty1)) $! (go ty2)
 301     go (NoteTy (FTVNote _) ty2)    = go ty2             -- Discard the free tyvar note
 302     go (NoteTy (UsgNote usg)  ty2) = (NoteTy $! UsgNote usg) $! go ty2          -- Keep usage annot
 303     go (NoteTy (UsgForAll uv) ty2) = (NoteTy $! UsgForAll uv) $! go ty2         -- Keep uvar bdr
 304     go (NoteTy (IPNote nm) ty2)    = (NoteTy $! IPNote nm) $! go ty2            -- Keep ip note
 305
 306     go (FunTy arg res)             = (FunTy $! (go arg)) $! (go res)
 307     go (AppTy fun arg)             = mkAppTy (go fun) $! (go arg)
 308     go ty@(TyVarTy tv)             = case (lookupSubst subst tv) of
 309                                         Nothing            -> ty
 310                                         Just (DoneTy ty')  -> ty'
 311
 312     go (ForAllTy tv ty)            = case substTyVar subst tv of
 313                                         (subst', tv') -> ForAllTy tv' $! (subst_ty subst' ty)
 314 \end{code}
 315
 316 Here is where we invent a new binder if necessary.
 317
 318 \begin{code}
 319 substTyVar :: Subst -> TyVar -> (Subst, TyVar)
 320 substTyVar subst@(Subst in_scope env) old_var
 321   | old_var == new_var  -- No need to clone
 322                         -- But we *must* zap any current substitution for the variable.
 323                         --  For example:
 324                         --      (\x.e) with id_subst = [x |-> e']
 325                         -- Here we must simply zap the substitution for x
 326                         --
 327                         -- The new_id isn't cloned, but it may have a different type
 328                         -- etc, so we must return it, not the old id
 329   = (Subst (in_scope `add_in_scope` new_var)
 330            (delSubstEnv env old_var),
 331      new_var)
 332
 333   | otherwise   -- The new binder is in scope so
 334                 -- we'd better rename it away from the in-scope variables
 335                 -- Extending the substitution to do this renaming also
 336                 -- has the (correct) effect of discarding any existing
 337                 -- substitution for that variable
 338   = (Subst (in_scope `add_in_scope` new_var)
 339            (extendSubstEnv env old_var (DoneTy (TyVarTy new_var))),
 340      new_var)
 341   where
 342     new_var = uniqAway in_scope old_var
 343         -- The uniqAway part makes sure the new variable is not already in scope
 344 \end{code}
 345
 346
 347 %************************************************************************
 348 %*                                                                      *
 349 \section{Expression substitution}
 350 %*                                                                      *
 351 %************************************************************************
 352
 353 This expression substituter deals correctly with name capture.
 354
 355 BUT NOTE that substExpr silently discards the
 356         unfolding, and
 357         spec env
 358 IdInfo attached to any binders in the expression.  It's quite
 359 tricky to do them 'right' in the case of mutually recursive bindings,
 360 and so far has proved unnecessary.
 361
 362 \begin{code}
 363 substExpr :: Subst -> CoreExpr -> CoreExpr
 364 substExpr subst expr
 365         -- NB: we do not do a no-op when the substitution is empty,
 366         -- because we always want to substitute the variables in the
 367         -- in-scope set for their occurrences.  Why?
 368         --      (a) because they may contain more information
 369         --      (b) because leaving an un-substituted Id might cause
 370         --          a space leak (its unfolding might point to an old version
 371         --          of its right hand side).
 372
 373   = go expr
 374   where
 375     go (Var v) = -- See the notes at the top, with the Subst data type declaration
 376                  case lookupIdSubst subst v of
 377
 378                     ContEx env' e' -> substExpr (setSubstEnv subst env') e'
 379                     DoneId v _     -> Var v
 380                     DoneEx e'      -> e'
 381
 382     go (Type ty)      = Type (go_ty ty)
 383     go (Lit lit)      = Lit lit
 384     go (App fun arg)  = App (go fun) (go arg)
 385     go (Note note e)  = Note (go_note note) (go e)
 386
 387     go (Lam bndr body) = Lam bndr' (substExpr subst' body)
 388                        where
 389                          (subst', bndr') = substBndr subst bndr
 390
 391     go (Let (NonRec bndr rhs) body) = Let (NonRec bndr' (go rhs)) (substExpr subst' body)
 392                                     where
 393                                       (subst', bndr') = substBndr subst bndr
 394
 395     go (Let (Rec pairs) body) = Let (Rec pairs') (substExpr subst' body)
 396                               where
 397                                 (subst', bndrs') = substBndrs subst (map fst pairs)
 398                                 pairs'  = bndrs' `zip` rhss'
 399                                 rhss'   = map (substExpr subst' . snd) pairs
 400
 401     go (Case scrut bndr alts) = Case (go scrut) bndr' (map (go_alt subst') alts)
 402                               where
 403                                 (subst', bndr') = substBndr subst bndr
 404
 405     go_alt subst (con, bndrs, rhs) = (con, bndrs', substExpr subst' rhs)
 406                                  where
 407                                    (subst', bndrs') = substBndrs subst bndrs
 408
 409     go_note (Coerce ty1 ty2) = Coerce (go_ty ty1) (go_ty ty2)
 410     go_note note             = note
 411
 412     go_ty ty = substTy subst ty
 413
 414 \end{code}
 415
 416 Substituting in binders is a rather tricky part of the whole compiler.
 417
 418 When we hit a binder we may need to
 419   (a) apply the the type envt (if non-empty) to its type
 420   (c) give it a new unique to avoid name clashes
 421
 422 \begin{code}
 423 substBndr :: Subst -> Var -> (Subst, Var)
 424 substBndr subst bndr
 425   | isTyVar bndr  = substTyVar subst bndr
 426   | otherwise     = substId    subst bndr
 427
 428 substBndrs :: Subst -> [Var] -> (Subst, [Var])
 429 substBndrs subst bndrs = mapAccumL substBndr subst bndrs
 430
 431
 432 substIds :: Subst -> [Id] -> (Subst, [Id])
 433 substIds subst bndrs = mapAccumL substId subst bndrs
 434
 435 substId :: Subst -> Id -> (Subst, Id)
 436         -- Returns an Id with empty IdInfo
 437         -- See the notes with the Subst data type decl at the
 438         -- top of this module
 439
 440 substId subst@(Subst in_scope env) old_id
 441   = (Subst (in_scope `add_in_scope` new_id) new_env, new_id)
 442   where
 443     id_ty    = idType old_id
 444     occ_info = idOccInfo old_id
 445
 446        -- id1 has its type zapped
 447     id1 |  noTypeSubst env
 448         || isEmptyVarSet (tyVarsOfType id_ty) = old_id
 449                         -- The tyVarsOfType is cheaper than it looks
 450                         -- because we cache the free tyvars of the type
 451                         -- in a Note in the id's type itself
 452         | otherwise  = setIdType old_id (substTy subst id_ty)
 453
 454         -- id2 has its IdInfo zapped
 455     id2 = zapFragileIdInfo id1
 456
 457         -- new_id is cloned if necessary
 458     new_id = uniqAway in_scope id2
 459
 460         -- Extend the substitution if the unique has changed,
 461         -- or there's some useful occurrence information
 462         -- See the notes with substTyVar for the delSubstEnv
 463     new_env | new_id /= old_id || isFragileOccInfo occ_info
 464             = extendSubstEnv env old_id (DoneId new_id occ_info)
 465             | otherwise
 466             = delSubstEnv env old_id
 467 \end{code}
 468
 469 Now a variant that unconditionally allocates a new unique.
 470
 471 \begin{code}
 472 substAndCloneIds :: Subst -> UniqSupply -> [Id] -> (Subst, UniqSupply, [Id])
 473 substAndCloneIds subst us [] = (subst, us, [])
 474 substAndCloneIds subst us (b:bs) = case substAndCloneId  subst  us  b  of { (subst1, us1, b') ->
 475                                    case substAndCloneIds subst1 us1 bs of { (subst2, us2, bs') ->
 476                                    (subst2, us2, (b':bs')) }}
 477
 478 substAndCloneId :: Subst -> UniqSupply -> Id -> (Subst, UniqSupply, Id)
 479 substAndCloneId subst@(Subst in_scope env) us old_id
 480   = (Subst (in_scope `add_in_scope` new_id)
 481            (extendSubstEnv env old_id (DoneEx (Var new_id))),
 482      new_us,
 483      new_id)
 484   where
 485     id_ty    = idType old_id
 486     id1 | noTypeSubst env || isEmptyVarSet (tyVarsOfType id_ty) = old_id
 487         | otherwise                                             = setIdType old_id (substTy subst id_ty)
 488
 489     id2          = zapFragileIdInfo id1
 490     new_id       = setVarUnique id2 (uniqFromSupply us1)
 491     (us1,new_us) = splitUniqSupply us
 492 \end{code}
 493
 494
 495 %************************************************************************
 496 %*                                                                      *
 497 \section{IdInfo substitution}
 498 %*                                                                      *
 499 %************************************************************************
 500
 501 \begin{code}
 502 substIdInfo :: Subst
 503             -> IdInfo           -- Get un-substituted ones from here
 504             -> IdInfo           -- Substitute it and add it to here
 505             -> IdInfo           -- To give this
 506         -- Seq'ing on the returned IdInfo is enough to cause all the
 507         -- substitutions to happen completely
 508
 509 substIdInfo subst old_info new_info
 510   = info2
 511   where
 512     info1 | isEmptyCoreRules old_rules = new_info
 513           | otherwise                  = new_info `setSpecInfo` new_rules
 514                         -- setSpecInfo does a seq
 515           where
 516             new_rules = substRules subst old_rules
 517
 518     info2 | not (workerExists old_wrkr) = info1
 519           | otherwise                   = info1 `setWorkerInfo` new_wrkr
 520                         -- setWorkerInfo does a seq
 521           where
 522             new_wrkr = substWorker subst old_wrkr
 523
 524     old_rules = specInfo   old_info
 525     old_wrkr  = workerInfo old_info
 526
 527 substWorker :: Subst -> WorkerInfo -> WorkerInfo
 528         -- Seq'ing on the returned WorkerInfo is enough to cause all the
 529         -- substitutions to happen completely
 530
 531 substWorker subst NoWorker
 532   = NoWorker
 533 substWorker subst (HasWorker w a)
 534   = case lookupIdSubst subst w of
 535         (DoneId w1 _)     -> HasWorker w1 a
 536         (DoneEx (Var w1)) -> HasWorker w1 a
 537         (DoneEx other)    -> WARN( True, text "substWorker: DoneEx" <+> ppr w )
 538                                   NoWorker      -- Worker has got substituted away altogether
 539         (ContEx se1 e)    -> WARN( True, text "substWorker: ContEx" <+> ppr w <+> ppr e)
 540                                   NoWorker      -- Ditto
 541
 542 substRules :: Subst -> CoreRules -> CoreRules
 543         -- Seq'ing on the returned CoreRules is enough to cause all the
 544         -- substitutions to happen completely
 545
 546 substRules subst rules
 547  | isEmptySubst subst = rules
 548
 549 substRules subst (Rules rules rhs_fvs)
 550   = seqRules new_rules `seq` new_rules
 551   where
 552     new_rules = Rules (map do_subst rules) (substVarSet subst rhs_fvs)
 553
 554     do_subst rule@(BuiltinRule _) = rule
 555     do_subst (Rule name tpl_vars lhs_args rhs)
 556         = Rule name tpl_vars'
 557                (map (substExpr subst') lhs_args)
 558                (substExpr subst' rhs)
 559         where
 560           (subst', tpl_vars') = substBndrs subst tpl_vars
 561
 562 substVarSet subst fvs
 563   = foldVarSet (unionVarSet . subst_fv subst) emptyVarSet fvs
 564   where
 565     subst_fv subst fv = case lookupIdSubst subst fv of
 566                             DoneId fv' _    -> unitVarSet fv'
 567                             DoneEx expr     -> exprFreeVars expr
 568                             DoneTy ty       -> tyVarsOfType ty
 569                             ContEx se' expr -> substVarSet (setSubstEnv subst se') (exprFreeVars expr)
 570 \end{code}