    {-
    (c) The University of Glasgow 2006
    (c) The GRASP/AQUA Project, Glasgow University, 1992-1998

    Utility functions on @Core@ syntax
    -}

    module GHC.Core.Subst (
            -- * Main data types
            Subst(..), -- Implementation exported for supercompiler's Renaming.hs only
            TvSubstEnv, IdSubstEnv, InScopeSet,

            -- ** Substituting into expressions and related types
            deShadowBinds, substRuleInfo, substRulesForImportedIds,
            substTyUnchecked, substCo, substExpr, substExprSC, substBind, substBindSC,
            substUnfolding, substUnfoldingSC,
            lookupIdSubst, lookupIdSubst_maybe, substIdType, substIdOcc,
            substTickish, substDVarSet, substIdInfo,

            -- ** Operations on substitutions
            emptySubst, mkEmptySubst, mkTCvSubst, mkOpenSubst, isEmptySubst,
            extendIdSubst, extendIdSubstList, extendTCvSubst, extendTvSubstList,
            extendIdSubstWithClone,
            extendSubst, extendSubstList, extendSubstWithVar,
            extendSubstInScope, extendSubstInScopeList, extendSubstInScopeSet,
            isInScope, setInScope, getSubstInScope,
            extendTvSubst, extendCvSubst,
            delBndr, delBndrs, zapSubst,

            -- ** Substituting and cloning binders
            substBndr, substBndrs, substRecBndrs, substTyVarBndr, substCoVarBndr,
            cloneBndr, cloneBndrs, cloneIdBndr, cloneIdBndrs, cloneRecIdBndrs,

        ) where

    import GHC.Prelude

    import GHC.Core
    import GHC.Core.FVs
    import GHC.Core.Seq
    import GHC.Core.Utils

            -- We are defining local versions
    import GHC.Core.Type hiding ( substTy )
    import GHC.Core.Coercion
        ( tyCoFVsOfCo, mkCoVarCo, substCoVarBndr )

    import GHC.Types.Var.Set
    import GHC.Types.Var.Env as InScopeSet
    import GHC.Types.Id
    import GHC.Types.Name     ( Name )
    import GHC.Types.Var
    import GHC.Types.Tickish
    import GHC.Types.Id.Info
    import GHC.Types.Unique.Supply

    import GHC.Builtin.Names
    import GHC.Data.Maybe

    import GHC.Utils.Misc
    import GHC.Utils.Outputable
    import GHC.Utils.Panic

    import Data.Functor.Identity (Identity (..))
    import Data.List (mapAccumL)

    {-
    ************************************************************************
    *                                                                      *
    \subsection{Substitutions}
    *                                                                      *
    ************************************************************************
    -}

    {-
    Note [Extending the IdSubstEnv]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~
    We make a different choice for Ids than we do for TyVars.

    For TyVars, see Note [Extending the TvSubstEnv and CvSubstEnv] in GHC.Core.TyCo.Subst.

    For Ids, we have a different invariant
            The IdSubstEnv is extended *only* when the Unique on an Id changes
            Otherwise, we just extend the InScopeSet

    In consequence:

    * If all subst envs are empty, substExpr would be a
      no-op, so substExprSC ("short cut") does nothing.

      However, substExpr still goes ahead and substitutes.  Reason: we may
      want to replace existing Ids with new ones from the in-scope set, to
      avoid space leaks.

    * In substIdBndr, we extend the IdSubstEnv only when the unique changes

    * If the CvSubstEnv, TvSubstEnv and IdSubstEnv are all empty,
      substExpr does nothing (Note that the above rule for substIdBndr
      maintains this property.  If the incoming envts are both empty, then
      substituting the type and IdInfo can't change anything.)

    * In lookupIdSubst, we *must* look up the Id in the in-scope set, because
      it may contain non-trivial changes.  Example:
            (/\a. \x:a. ...x...) Int
      We extend the TvSubstEnv with [a |-> Int]; but x's unique does not change
      so we only extend the in-scope set.  Then we must look up in the in-scope
      set when we find the occurrence of x.

    * The requirement to look up the Id in the in-scope set means that we
      must NOT take no-op short cut when the IdSubst is empty.
      We must still look up every Id in the in-scope set.

    * (However, we don't need to do so for expressions found in the IdSubst
      itself, whose range is assumed to be correct wrt the in-scope set.)

    Why do we make a different choice for the IdSubstEnv than the
    TvSubstEnv and CvSubstEnv?

    * For Ids, we change the IdInfo all the time (e.g. deleting the
      unfolding), and adding it back later, so using the TyVar convention
      would entail extending the substitution almost all the time

    * The simplifier wants to look up in the in-scope set anyway, in case it
      can see a better unfolding from an enclosing case expression

    * For TyVars, only coercion variables can possibly change, and they are
      easy to spot
    -}

    ----------------------------

    -- We keep GHC.Core.Subst separate from GHC.Core.TyCo.Subst to avoid creating
    -- circular dependencies. Functions in this file that don't depend on
    -- the definition of CoreExpr can be moved to GHC.Core.TyCo.Subst, as long
    -- as it does not require importing too many additional hs-boot files and
    -- cause a significant drop in performance.

    -- | Add a substitution for an 'Id' to the 'Subst': you must ensure that the in-scope set is
    -- such that TyCoSubst Note [The substitution invariant]
    -- holds after extending the substitution like this
    extendIdSubst :: Subst -> Id -> CoreExpr -> Subst
    -- ToDo: add an ASSERT that fvs(subst-result) is already in the in-scope set
    extendIdSubst :: Subst -> Id -> CoreExpr -> Subst
    extendIdSubst (Subst InScopeSet
    in_scope IdSubstEnv
    ids TvSubstEnv
    tvs CvSubstEnv
    cvs) Id
    v CoreExpr
    r
      = Bool -> SDoc -> Subst -> Subst
    forall a. HasCallStack => Bool -> SDoc -> a -> a
    assertPpr (Id -> Bool
    isNonCoVarId Id
    v) (Id -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Id
    v SDoc -> SDoc -> SDoc
    forall doc. IsDoc doc => doc -> doc -> doc
    $$ CoreExpr -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr CoreExpr
    r) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $
        InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    in_scope (IdSubstEnv -> Id -> CoreExpr -> IdSubstEnv
    forall a. VarEnv a -> Id -> a -> VarEnv a
    extendVarEnv IdSubstEnv
    ids Id
    v CoreExpr
    r) TvSubstEnv
    tvs CvSubstEnv
    cvs

    extendIdSubstWithClone :: Subst -> Id -> Id -> Subst
    extendIdSubstWithClone :: Subst -> Id -> Id -> Subst
    extendIdSubstWithClone (Subst InScopeSet
    in_scope IdSubstEnv
    ids TvSubstEnv
    tvs CvSubstEnv
    cvs) Id
    v Id
    v'
      = Bool -> SDoc -> Subst -> Subst
    forall a. HasCallStack => Bool -> SDoc -> a -> a
    assertPpr (Id -> Bool
    isNonCoVarId Id
    v) (Id -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Id
    v SDoc -> SDoc -> SDoc
    forall doc. IsDoc doc => doc -> doc -> doc
    $$ Id -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Id
    v') (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $
        InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst (InScopeSet -> VarSet -> InScopeSet
    extendInScopeSetSet InScopeSet
    in_scope VarSet
    new_in_scope)
              (IdSubstEnv -> Id -> CoreExpr -> IdSubstEnv
    forall a. VarEnv a -> Id -> a -> VarEnv a
    extendVarEnv IdSubstEnv
    ids Id
    v (Id -> CoreExpr
    forall b. Id -> Expr b
    varToCoreExpr Id
    v')) TvSubstEnv
    tvs CvSubstEnv
    cvs
        where
          new_in_scope :: VarSet
    new_in_scope = Type -> VarSet
    tyCoVarsOfType (Id -> Type
    varType Id
    v') VarSet -> Id -> VarSet
    `extendVarSet` Id
    v'

    -- | Adds multiple 'Id' substitutions to the 'Subst': see also 'extendIdSubst'
    extendIdSubstList :: Subst -> [(Id, CoreExpr)] -> Subst
    extendIdSubstList :: Subst -> [(Id, CoreExpr)] -> Subst
    extendIdSubstList (Subst InScopeSet
    in_scope IdSubstEnv
    ids TvSubstEnv
    tvs CvSubstEnv
    cvs) [(Id, CoreExpr)]
    prs
      = Bool -> Subst -> Subst
    forall a. HasCallStack => Bool -> a -> a
    assert (((Id, CoreExpr) -> Bool) -> [(Id, CoreExpr)] -> Bool
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
    all (Id -> Bool
    isNonCoVarId (Id -> Bool) -> ((Id, CoreExpr) -> Id) -> (Id, CoreExpr) -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Id, CoreExpr) -> Id
    forall a b. (a, b) -> a
    fst) [(Id, CoreExpr)]
    prs) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $
        InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    in_scope (IdSubstEnv -> [(Id, CoreExpr)] -> IdSubstEnv
    forall a. VarEnv a -> [(Id, a)] -> VarEnv a
    extendVarEnvList IdSubstEnv
    ids [(Id, CoreExpr)]
    prs) TvSubstEnv
    tvs CvSubstEnv
    cvs

    -- | Add a substitution appropriate to the thing being substituted
    --   (whether an expression, type, or coercion). See also
    --   'extendIdSubst', 'extendTvSubst', 'extendCvSubst'
    extendSubst :: Subst -> Var -> CoreArg -> Subst
    extendSubst :: Subst -> Id -> CoreExpr -> Subst
    extendSubst Subst
    subst Id
    var CoreExpr
    arg
      = case CoreExpr
    arg of
          Type Type
    ty     -> Bool -> Subst -> Subst
    forall a. HasCallStack => Bool -> a -> a
    assert (Id -> Bool
    isTyVar Id
    var) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $ Subst -> Id -> Type -> Subst
    extendTvSubst Subst
    subst Id
    var Type
    ty
          Coercion Coercion
    co -> Bool -> Subst -> Subst
    forall a. HasCallStack => Bool -> a -> a
    assert (Id -> Bool
    isCoVar Id
    var) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $ Subst -> Id -> Coercion -> Subst
    extendCvSubst Subst
    subst Id
    var Coercion
    co
          CoreExpr
    _           -> Bool -> Subst -> Subst
    forall a. HasCallStack => Bool -> a -> a
    assert (Id -> Bool
    isId    Id
    var) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $ Subst -> Id -> CoreExpr -> Subst
    extendIdSubst Subst
    subst Id
    var CoreExpr
    arg

    extendSubstWithVar :: Subst -> Var -> Var -> Subst
    extendSubstWithVar :: Subst -> Id -> Id -> Subst
    extendSubstWithVar Subst
    subst Id
    v1 Id
    v2
      | Id -> Bool
    isTyVar Id
    v1 = Bool -> Subst -> Subst
    forall a. HasCallStack => Bool -> a -> a
    assert (Id -> Bool
    isTyVar Id
    v2) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $ Subst -> Id -> Type -> Subst
    extendTvSubst Subst
    subst Id
    v1 (Id -> Type
    mkTyVarTy Id
    v2)
      | Id -> Bool
    isCoVar Id
    v1 = Bool -> Subst -> Subst
    forall a. HasCallStack => Bool -> a -> a
    assert (Id -> Bool
    isCoVar Id
    v2) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $ Subst -> Id -> Coercion -> Subst
    extendCvSubst Subst
    subst Id
    v1 (Id -> Coercion
    mkCoVarCo Id
    v2)
      | Bool
    otherwise  = Bool -> Subst -> Subst
    forall a. HasCallStack => Bool -> a -> a
    assert (Id -> Bool
    isId    Id
    v2) (Subst -> Subst) -> Subst -> Subst
    forall a b. (a -> b) -> a -> b
    $ Subst -> Id -> CoreExpr -> Subst
    extendIdSubst Subst
    subst Id
    v1 (Id -> CoreExpr
    forall b. Id -> Expr b
    Var Id
    v2)

    -- | Add a substitution as appropriate to each of the terms being
    --   substituted (whether expressions, types, or coercions). See also
    --   'extendSubst'.
    extendSubstList :: Subst -> [(Var,CoreArg)] -> Subst
    extendSubstList :: Subst -> [(Id, CoreExpr)] -> Subst
    extendSubstList Subst
    subst []              = Subst
    subst
    extendSubstList Subst
    subst ((Id
    var,CoreExpr
    rhs):[(Id, CoreExpr)]
    prs) = Subst -> [(Id, CoreExpr)] -> Subst
    extendSubstList (Subst -> Id -> CoreExpr -> Subst
    extendSubst Subst
    subst Id
    var CoreExpr
    rhs) [(Id, CoreExpr)]
    prs

    -- | Find the substitution for an 'Id' in the 'Subst'
    -- The Id should not be a CoVar
    lookupIdSubst :: HasDebugCallStack => Subst -> Id -> CoreExpr
    lookupIdSubst :: HasDebugCallStack => Subst -> Id -> CoreExpr
    lookupIdSubst (Subst InScopeSet
    in_scope IdSubstEnv
    ids TvSubstEnv
    _ CvSubstEnv
    _) Id
    v
      | Bool -> SDoc -> (Bool -> Bool) -> Bool -> Bool
    forall a. HasCallStack => Bool -> SDoc -> a -> a
    assertPpr (Id -> Bool
    isId Id
    v Bool -> Bool -> Bool
    && Bool -> Bool
    not (Id -> Bool
    isCoVar Id
    v)) (Id -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Id
    v)
        Bool -> Bool
    not (Id -> Bool
    isLocalId Id
    v)                   = Id -> CoreExpr
    forall b. Id -> Expr b
    Var Id
    v
      | Just CoreExpr
    e  <- IdSubstEnv -> Id -> Maybe CoreExpr
    forall a. VarEnv a -> Id -> Maybe a
    lookupVarEnv IdSubstEnv
    ids       Id
    v = CoreExpr
    e
      | Just Id
    v' <- InScopeSet -> Id -> Maybe Id
    lookupInScope InScopeSet
    in_scope Id
    v = Id -> CoreExpr
    forall b. Id -> Expr b
    Var Id
    v'
            -- Vital! See Note [Extending the IdSubstEnv]
            -- If v isn't in the InScopeSet, we panic, because
            -- it's a bad bug and we really want to know
      | Bool
    otherwise = String -> SDoc -> CoreExpr
    forall a. HasCallStack => String -> SDoc -> a
    pprPanic String
    "lookupIdSubst" (Id -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Id
    v SDoc -> SDoc -> SDoc
    forall doc. IsDoc doc => doc -> doc -> doc
    $$ InScopeSet -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr InScopeSet
    in_scope)

    lookupIdSubst_maybe :: HasDebugCallStack => Subst -> Id -> Maybe CoreExpr
    -- Just look up in the substitution; do not check the in-scope set
    lookupIdSubst_maybe :: HasDebugCallStack => Subst -> Id -> Maybe CoreExpr
    lookupIdSubst_maybe (Subst InScopeSet
    _ IdSubstEnv
    ids TvSubstEnv
    _ CvSubstEnv
    _) Id
    v
      = Bool -> SDoc -> Maybe CoreExpr -> Maybe CoreExpr
    forall a. HasCallStack => Bool -> SDoc -> a -> a
    assertPpr (Id -> Bool
    isId Id
    v Bool -> Bool -> Bool
    && Bool -> Bool
    not (Id -> Bool
    isCoVar Id
    v)) (Id -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Id
    v) (Maybe CoreExpr -> Maybe CoreExpr)
    -> Maybe CoreExpr -> Maybe CoreExpr
    forall a b. (a -> b) -> a -> b
    $
        IdSubstEnv -> Id -> Maybe CoreExpr
    forall a. VarEnv a -> Id -> Maybe a
    lookupVarEnv IdSubstEnv
    ids Id
    v

    delBndr :: Subst -> Var -> Subst
    delBndr :: Subst -> Id -> Subst
    delBndr (Subst InScopeSet
    in_scope IdSubstEnv
    ids TvSubstEnv
    tvs CvSubstEnv
    cvs) Id
    v
      | Id -> Bool
    isCoVar Id
    v = InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    in_scope IdSubstEnv
    ids TvSubstEnv
    tvs (CvSubstEnv -> Id -> CvSubstEnv
    forall a. VarEnv a -> Id -> VarEnv a
    delVarEnv CvSubstEnv
    cvs Id
    v)
      | Id -> Bool
    isTyVar Id
    v = InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    in_scope IdSubstEnv
    ids (TvSubstEnv -> Id -> TvSubstEnv
    forall a. VarEnv a -> Id -> VarEnv a
    delVarEnv TvSubstEnv
    tvs Id
    v) CvSubstEnv
    cvs
      | Bool
    otherwise = InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    in_scope (IdSubstEnv -> Id -> IdSubstEnv
    forall a. VarEnv a -> Id -> VarEnv a
    delVarEnv IdSubstEnv
    ids Id
    v) TvSubstEnv
    tvs CvSubstEnv
    cvs

    delBndrs :: Subst -> [Var] -> Subst
    delBndrs :: Subst -> [Id] -> Subst
    delBndrs (Subst InScopeSet
    in_scope IdSubstEnv
    ids TvSubstEnv
    tvs CvSubstEnv
    cvs) [Id]
    vs
      = InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    in_scope (IdSubstEnv -> [Id] -> IdSubstEnv
    forall a. VarEnv a -> [Id] -> VarEnv a
    delVarEnvList IdSubstEnv
    ids [Id]
    vs) (TvSubstEnv -> [Id] -> TvSubstEnv
    forall a. VarEnv a -> [Id] -> VarEnv a
    delVarEnvList TvSubstEnv
    tvs [Id]
    vs) (CvSubstEnv -> [Id] -> CvSubstEnv
    forall a. VarEnv a -> [Id] -> VarEnv a
    delVarEnvList CvSubstEnv
    cvs [Id]
    vs)
          -- Easiest thing is just delete all from all!

    -- | Simultaneously substitute for a bunch of variables
    --   No left-right shadowing
    --   ie the substitution for   (\x \y. e) a1 a2
    --      so neither x nor y scope over a1 a2
    mkOpenSubst :: InScopeSet -> [(Var,CoreArg)] -> Subst
    mkOpenSubst :: InScopeSet -> [(Id, CoreExpr)] -> Subst
    mkOpenSubst InScopeSet
    in_scope [(Id, CoreExpr)]
    pairs = InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    in_scope
                                       ([(Id, CoreExpr)] -> IdSubstEnv
    forall a. [(Id, a)] -> VarEnv a
    mkVarEnv [(Id
    id,CoreExpr
    e)  | (Id
    id, CoreExpr
    e) <- [(Id, CoreExpr)]
    pairs, Id -> Bool
    isId Id
    id])
                                       ([(Id, Type)] -> TvSubstEnv
    forall a. [(Id, a)] -> VarEnv a
    mkVarEnv [(Id
    tv,Type
    ty) | (Id
    tv, Type Type
    ty) <- [(Id, CoreExpr)]
    pairs])
                                       ([(Id, Coercion)] -> CvSubstEnv
    forall a. [(Id, a)] -> VarEnv a
    mkVarEnv [(Id
    v,Coercion
    co)  | (Id
    v, Coercion Coercion
    co) <- [(Id, CoreExpr)]
    pairs])

    ------------------------------

    {-
    ************************************************************************
    *                                                                      *
            Substituting expressions
    *                                                                      *
    ************************************************************************
    -}

    substExprSC :: HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    -- Just like substExpr, but a no-op if the substitution is empty
    -- Note that this does /not/ replace occurrences of free vars with
    -- their canonical representatives in the in-scope set
    substExprSC :: HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    substExprSC Subst
    subst CoreExpr
    orig_expr
      | Subst -> Bool
    isEmptySubst Subst
    subst = CoreExpr
    orig_expr
      | Bool
    otherwise          = -- pprTrace "enter subst-expr" (doc $$ ppr orig_expr) $
                             HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst CoreExpr
    orig_expr

    -- | substExpr applies a substitution to an entire 'CoreExpr'. Remember,
    -- you may only apply the substitution /once/:
    -- See Note [Substitutions apply only once] in "GHC.Core.TyCo.Subst"
    --
    -- Do *not* attempt to short-cut in the case of an empty substitution!
    -- See Note [Extending the IdSubstEnv]
    substExpr :: HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
       -- HasDebugCallStack so we can track failures in lookupIdSubst
    substExpr :: HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst CoreExpr
    expr
      = CoreExpr -> CoreExpr
    go CoreExpr
    expr
      where
        go :: CoreExpr -> CoreExpr
    go (Var Id
    v)         = HasDebugCallStack => Subst -> Id -> CoreExpr
    Subst -> Id -> CoreExpr
    lookupIdSubst Subst
    subst Id
    v
        go (Type Type
    ty)       = Type -> CoreExpr
    forall b. Type -> Expr b
    Type (Subst -> Type -> Type
    substTyUnchecked Subst
    subst Type
    ty)
        go (Coercion Coercion
    co)   = Coercion -> CoreExpr
    forall b. Coercion -> Expr b
    Coercion (HasDebugCallStack => Subst -> Coercion -> Coercion
    Subst -> Coercion -> Coercion
    substCo Subst
    subst Coercion
    co)
        go (Lit Literal
    lit)       = Literal -> CoreExpr
    forall b. Literal -> Expr b
    Lit Literal
    lit
        go (App CoreExpr
    fun CoreExpr
    arg)   = CoreExpr -> CoreExpr -> CoreExpr
    forall b. Expr b -> Expr b -> Expr b
    App (CoreExpr -> CoreExpr
    go CoreExpr
    fun) (CoreExpr -> CoreExpr
    go CoreExpr
    arg)
        go (Tick CoreTickish
    tickish CoreExpr
    e) = CoreTickish -> CoreExpr -> CoreExpr
    mkTick (Subst -> CoreTickish -> CoreTickish
    substTickish Subst
    subst CoreTickish
    tickish) (CoreExpr -> CoreExpr
    go CoreExpr
    e)
        go (Cast CoreExpr
    e Coercion
    co)     = CoreExpr -> Coercion -> CoreExpr
    forall b. Expr b -> Coercion -> Expr b
    Cast (CoreExpr -> CoreExpr
    go CoreExpr
    e) (HasDebugCallStack => Subst -> Coercion -> Coercion
    Subst -> Coercion -> Coercion
    substCo Subst
    subst Coercion
    co)
           -- Do not optimise even identity coercions
           -- Reason: substitution applies to the LHS of RULES, and
           --         if you "optimise" an identity coercion, you may
           --         lose a binder. We optimise the LHS of rules at
           --         construction time

        go (Lam Id
    bndr CoreExpr
    body) = Id -> CoreExpr -> CoreExpr
    forall b. b -> Expr b -> Expr b
    Lam Id
    bndr' (HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst' CoreExpr
    body)
                           where
                             (Subst
    subst', Id
    bndr') = Subst -> Id -> (Subst, Id)
    substBndr Subst
    subst Id
    bndr

        go (Let Bind Id
    bind CoreExpr
    body) = Bind Id -> CoreExpr -> CoreExpr
    forall b. Bind b -> Expr b -> Expr b
    Let Bind Id
    bind' (HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst' CoreExpr
    body)
                           where
                             (Subst
    subst', Bind Id
    bind') = HasDebugCallStack => Subst -> Bind Id -> (Subst, Bind Id)
    Subst -> Bind Id -> (Subst, Bind Id)
    substBind Subst
    subst Bind Id
    bind

        go (Case CoreExpr
    scrut Id
    bndr Type
    ty [Alt Id]
    alts) = CoreExpr -> Id -> Type -> [Alt Id] -> CoreExpr
    forall b. Expr b -> b -> Type -> [Alt b] -> Expr b
    Case (CoreExpr -> CoreExpr
    go CoreExpr
    scrut) Id
    bndr' (Subst -> Type -> Type
    substTyUnchecked Subst
    subst Type
    ty) ((Alt Id -> Alt Id) -> [Alt Id] -> [Alt Id]
    forall a b. (a -> b) -> [a] -> [b]
    map (Subst -> Alt Id -> Alt Id
    go_alt Subst
    subst') [Alt Id]
    alts)
                                     where
                                     (Subst
    subst', Id
    bndr') = Subst -> Id -> (Subst, Id)
    substBndr Subst
    subst Id
    bndr

        go_alt :: Subst -> Alt Id -> Alt Id
    go_alt Subst
    subst (Alt AltCon
    con [Id]
    bndrs CoreExpr
    rhs) = AltCon -> [Id] -> CoreExpr -> Alt Id
    forall b. AltCon -> [b] -> Expr b -> Alt b
    Alt AltCon
    con [Id]
    bndrs' (HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst' CoreExpr
    rhs)
                                     where
                                       (Subst
    subst', [Id]
    bndrs') = Subst -> [Id] -> (Subst, [Id])
    forall (f :: * -> *).
    Traversable f =>
    Subst -> f Id -> (Subst, f Id)
    substBndrs Subst
    subst [Id]
    bndrs

    -- | Apply a substitution to an entire 'CoreBind', additionally returning an updated 'Subst'
    -- that should be used by subsequent substitutions.
    substBind, substBindSC :: HasDebugCallStack => Subst -> CoreBind -> (Subst, CoreBind)

    substBindSC :: HasDebugCallStack => Subst -> Bind Id -> (Subst, Bind Id)
    substBindSC Subst
    subst Bind Id
    bind    -- Short-cut if the substitution is empty
      | Bool -> Bool
    not (Subst -> Bool
    isEmptySubst Subst
    subst)
      = HasDebugCallStack => Subst -> Bind Id -> (Subst, Bind Id)
    Subst -> Bind Id -> (Subst, Bind Id)
    substBind Subst
    subst Bind Id
    bind
      | Bool
    otherwise
      = case Bind Id
    bind of
           NonRec Id
    bndr CoreExpr
    rhs -> (Subst
    subst', Id -> CoreExpr -> Bind Id
    forall b. b -> Expr b -> Bind b
    NonRec Id
    bndr' CoreExpr
    rhs)
              where
                (Subst
    subst', Id
    bndr') = Subst -> Id -> (Subst, Id)
    substBndr Subst
    subst Id
    bndr
           Rec [(Id, CoreExpr)]
    pairs -> (Subst
    subst', [(Id, CoreExpr)] -> Bind Id
    forall b. [(b, Expr b)] -> Bind b
    Rec ([Id]
    bndrs' [Id] -> [CoreExpr] -> [(Id, CoreExpr)]
    forall a b. [a] -> [b] -> [(a, b)]
    `zip` [CoreExpr]
    rhss'))
              where
                ([Id]
    bndrs, [CoreExpr]
    rhss)    = [(Id, CoreExpr)] -> ([Id], [CoreExpr])
    forall a b. [(a, b)] -> ([a], [b])
    unzip [(Id, CoreExpr)]
    pairs
                (Subst
    subst', [Id]
    bndrs') = Subst -> [Id] -> (Subst, [Id])
    forall (f :: * -> *).
    Traversable f =>
    Subst -> f Id -> (Subst, f Id)
    substRecBndrs Subst
    subst [Id]
    bndrs
                rhss' :: [CoreExpr]
    rhss' | Subst -> Bool
    isEmptySubst Subst
    subst'
                      = [CoreExpr]
    rhss
                      | Bool
    otherwise
                      = (CoreExpr -> CoreExpr) -> [CoreExpr] -> [CoreExpr]
    forall a b. (a -> b) -> [a] -> [b]
    map (HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst') [CoreExpr]
    rhss

    substBind :: HasDebugCallStack => Subst -> Bind Id -> (Subst, Bind Id)
    substBind Subst
    subst (NonRec Id
    bndr CoreExpr
    rhs)
      = (Subst
    subst', Id -> CoreExpr -> Bind Id
    forall b. b -> Expr b -> Bind b
    NonRec Id
    bndr' (HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst CoreExpr
    rhs))
      where
        (Subst
    subst', Id
    bndr') = Subst -> Id -> (Subst, Id)
    substBndr Subst
    subst Id
    bndr

    substBind Subst
    subst (Rec [(Id, CoreExpr)]
    pairs)
       = (Subst
    subst', [(Id, CoreExpr)] -> Bind Id
    forall b. [(b, Expr b)] -> Bind b
    Rec ([Id]
    bndrs' [Id] -> [CoreExpr] -> [(Id, CoreExpr)]
    forall a b. [a] -> [b] -> [(a, b)]
    `zip` [CoreExpr]
    rhss'))
       where
           ([Id]
    bndrs, [CoreExpr]
    rhss)    = [(Id, CoreExpr)] -> ([Id], [CoreExpr])
    forall a b. [(a, b)] -> ([a], [b])
    unzip [(Id, CoreExpr)]
    pairs
           (Subst
    subst', [Id]
    bndrs') = Subst -> [Id] -> (Subst, [Id])
    forall (f :: * -> *).
    Traversable f =>
    Subst -> f Id -> (Subst, f Id)
    substRecBndrs Subst
    subst [Id]
    bndrs
           rhss' :: [CoreExpr]
    rhss' = (CoreExpr -> CoreExpr) -> [CoreExpr] -> [CoreExpr]
    forall a b. (a -> b) -> [a] -> [b]
    map (HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst') [CoreExpr]
    rhss

    -- | De-shadowing the program is sometimes a useful pre-pass. It can be done simply
    -- by running over the bindings with an empty substitution, because substitution
    -- returns a result that has no-shadowing guaranteed.
    --
    -- (Actually, within a single /type/ there might still be shadowing, because
    -- 'substTy' is a no-op for the empty substitution, but that's probably OK.)
    --
    -- [Aug 09] This function is not used in GHC at the moment, but seems so
    --          short and simple that I'm going to leave it here
    deShadowBinds :: CoreProgram -> CoreProgram
    deShadowBinds :: CoreProgram -> CoreProgram
    deShadowBinds CoreProgram
    binds = (Subst, CoreProgram) -> CoreProgram
    forall a b. (a, b) -> b
    snd ((Subst -> Bind Id -> (Subst, Bind Id))
    -> Subst -> CoreProgram -> (Subst, CoreProgram)
    forall (t :: * -> *) s a b.
    Traversable t =>
    (s -> a -> (s, b)) -> s -> t a -> (s, t b)
    mapAccumL HasDebugCallStack => Subst -> Bind Id -> (Subst, Bind Id)
    Subst -> Bind Id -> (Subst, Bind Id)
    substBind Subst
    emptySubst CoreProgram
    binds)

    {-
    ************************************************************************
    *                                                                      *
            Substituting binders
    *                                                                      *
    ************************************************************************

    Remember that substBndr and friends are used when doing expression
    substitution only.  Their only business is substitution, so they
    preserve all IdInfo (suitably substituted).  For example, we *want* to
    preserve occ info in rules.
    -}

    -- | Substitutes a 'Var' for another one according to the 'Subst' given, returning
    -- the result and an updated 'Subst' that should be used by subsequent substitutions.
    -- 'IdInfo' is preserved by this process, although it is substituted into appropriately.
    substBndr :: Subst -> Var -> (Subst, Var)
    substBndr :: Subst -> Id -> (Subst, Id)
    substBndr Subst
    subst Id
    bndr
      | Id -> Bool
    isTyVar Id
    bndr  = HasDebugCallStack => Subst -> Id -> (Subst, Id)
    Subst -> Id -> (Subst, Id)
    substTyVarBndr Subst
    subst Id
    bndr
      | Id -> Bool
    isCoVar Id
    bndr  = HasDebugCallStack => Subst -> Id -> (Subst, Id)
    Subst -> Id -> (Subst, Id)
    substCoVarBndr Subst
    subst Id
    bndr
      | Bool
    otherwise     = SDoc -> Subst -> Subst -> Id -> (Subst, Id)
    substIdBndr (String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "var-bndr") Subst
    subst Subst
    subst Id
    bndr

    -- | Applies 'substBndr' to a number of 'Var's, accumulating a new 'Subst' left-to-right
    substBndrs :: Traversable f => Subst -> f Var -> (Subst, f Var)
    substBndrs :: forall (f :: * -> *).
    Traversable f =>
    Subst -> f Id -> (Subst, f Id)
    substBndrs = (Subst -> Id -> (Subst, Id)) -> Subst -> f Id -> (Subst, f Id)
    forall (t :: * -> *) s a b.
    Traversable t =>
    (s -> a -> (s, b)) -> s -> t a -> (s, t b)
    mapAccumL Subst -> Id -> (Subst, Id)
    substBndr
    {-# INLINE substBndrs #-}

    -- | Substitute in a mutually recursive group of 'Id's
    substRecBndrs :: Traversable f => Subst -> f Id -> (Subst, f Id)
    substRecBndrs :: forall (f :: * -> *).
    Traversable f =>
    Subst -> f Id -> (Subst, f Id)
    substRecBndrs Subst
    subst f Id
    bndrs
      = (Subst
    new_subst, f Id
    new_bndrs)
      where         -- Here's the reason we need to pass rec_subst to subst_id
        (Subst
    new_subst, f Id
    new_bndrs) = (Subst -> Id -> (Subst, Id)) -> Subst -> f Id -> (Subst, f Id)
    forall (t :: * -> *) s a b.
    Traversable t =>
    (s -> a -> (s, b)) -> s -> t a -> (s, t b)
    mapAccumL (SDoc -> Subst -> Subst -> Id -> (Subst, Id)
    substIdBndr (String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "rec-bndr") Subst
    new_subst) Subst
    subst f Id
    bndrs
    {-# SPECIALIZE substRecBndrs :: Subst -> [Id] -> (Subst, [Id]) #-}
    {-# SPECIALIZE substRecBndrs :: Subst -> Identity Id -> (Subst, Identity Id) #-}

    substIdBndr :: SDoc
                -> Subst            -- ^ Substitution to use for the IdInfo
                -> Subst -> Id      -- ^ Substitution and Id to transform
                -> (Subst, Id)      -- ^ Transformed pair
                                    -- NB: unfolding may be zapped

    substIdBndr :: SDoc -> Subst -> Subst -> Id -> (Subst, Id)
    substIdBndr SDoc
    _doc Subst
    rec_subst subst :: Subst
    subst@(Subst InScopeSet
    in_scope IdSubstEnv
    env TvSubstEnv
    tvs CvSubstEnv
    cvs) Id
    old_id
      = -- pprTrace "substIdBndr" (doc $$ ppr old_id $$ ppr in_scope) $
        (InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    new_in_scope IdSubstEnv
    new_env TvSubstEnv
    tvs CvSubstEnv
    cvs, Id
    new_id)
      where
        id1 :: Id
    id1 = InScopeSet -> Id -> Id
    uniqAway InScopeSet
    in_scope Id
    old_id      -- id1 is cloned if necessary
        id2 :: Id
    id2 | Bool
    no_type_change = Id
    id1
            | Bool
    otherwise      = (Type -> Type) -> Id -> Id
    updateIdTypeAndMult (Subst -> Type -> Type
    substTyUnchecked Subst
    subst) Id
    id1

        old_ty :: Type
    old_ty = Id -> Type
    idType Id
    old_id
        old_w :: Type
    old_w = Id -> Type
    idMult Id
    old_id
        no_type_change :: Bool
    no_type_change = (TvSubstEnv -> Bool
    forall a. VarEnv a -> Bool
    isEmptyVarEnv TvSubstEnv
    tvs Bool -> Bool -> Bool
    && CvSubstEnv -> Bool
    forall a. VarEnv a -> Bool
    isEmptyVarEnv CvSubstEnv
    cvs) Bool -> Bool -> Bool
    ||
                         (Type -> Bool
    noFreeVarsOfType Type
    old_ty Bool -> Bool -> Bool
    && Type -> Bool
    noFreeVarsOfType Type
    old_w)

            -- new_id has the right IdInfo
            -- The lazy-set is because we're in a loop here, with
            -- rec_subst, when dealing with a mutually-recursive group
        !new_id :: Id
    new_id = Maybe IdInfo -> Id -> Id
    maybeModifyIdInfo Maybe IdInfo
    mb_new_info Id
    id2
        mb_new_info :: Maybe IdInfo
    mb_new_info = Subst -> Id -> IdInfo -> Maybe IdInfo
    substIdInfo Subst
    rec_subst Id
    id2 (HasDebugCallStack => Id -> IdInfo
    Id -> IdInfo
    idInfo Id
    id2)
            -- NB: unfolding info may be zapped

            -- Extend the substitution if the unique has changed
            -- See the notes with substTyVarBndr for the delVarEnv
        !new_in_scope :: InScopeSet
    new_in_scope = InScopeSet
    in_scope InScopeSet -> Id -> InScopeSet
    `InScopeSet.extendInScopeSet` Id
    new_id
            -- Forcing new_in_scope improves T9675 by 1.7%
        !new_env :: IdSubstEnv
    new_env | Bool
    no_change = IdSubstEnv -> Id -> IdSubstEnv
    forall a. VarEnv a -> Id -> VarEnv a
    delVarEnv IdSubstEnv
    env Id
    old_id
                 | Bool
    otherwise = IdSubstEnv -> Id -> CoreExpr -> IdSubstEnv
    forall a. VarEnv a -> Id -> a -> VarEnv a
    extendVarEnv IdSubstEnv
    env Id
    old_id (Id -> CoreExpr
    forall b. Id -> Expr b
    Var Id
    new_id)

        no_change :: Bool
    no_change = Id
    id1 Id -> Id -> Bool
    forall a. Eq a => a -> a -> Bool
    == Id
    old_id
            -- See Note [Extending the IdSubstEnv]
            -- it's /not/ necessary to check mb_new_info and no_type_change

    {-
    Now a variant that unconditionally allocates a new unique.
    It also unconditionally zaps the OccInfo.
    -}

    -- | Very similar to 'substBndr', but it always allocates a new 'Unique' for
    -- each variable in its output.  It substitutes the IdInfo though.
    -- Discards non-Stable unfoldings
    cloneIdBndr :: Subst -> UniqSupply -> Id -> (Subst, Id)
    cloneIdBndr :: Subst -> UniqSupply -> Id -> (Subst, Id)
    cloneIdBndr Subst
    subst UniqSupply
    us Id
    old_id
      = Subst -> Subst -> (Id, Unique) -> (Subst, Id)
    clone_id Subst
    subst Subst
    subst (Id
    old_id, UniqSupply -> Unique
    uniqFromSupply UniqSupply
    us)

    -- | Applies 'cloneIdBndr' to a number of 'Id's, accumulating a final
    -- substitution from left to right
    -- Discards non-Stable unfoldings
    cloneIdBndrs :: Subst -> UniqSupply -> [Id] -> (Subst, [Id])
    cloneIdBndrs :: Subst -> UniqSupply -> [Id] -> (Subst, [Id])
    cloneIdBndrs Subst
    subst UniqSupply
    us [Id]
    ids
      = (Subst -> (Id, Unique) -> (Subst, Id))
    -> Subst -> [(Id, Unique)] -> (Subst, [Id])
    forall (t :: * -> *) s a b.
    Traversable t =>
    (s -> a -> (s, b)) -> s -> t a -> (s, t b)
    mapAccumL (Subst -> Subst -> (Id, Unique) -> (Subst, Id)
    clone_id Subst
    subst) Subst
    subst ([Id]
    ids [Id] -> [Unique] -> [(Id, Unique)]
    forall a b. [a] -> [b] -> [(a, b)]
    `zip` UniqSupply -> [Unique]
    uniqsFromSupply UniqSupply
    us)

    cloneBndrs :: MonadUnique m => Subst -> [Var] -> m (Subst, [Var])
    -- Works for all kinds of variables (typically case binders)
    -- not just Ids
    cloneBndrs :: forall (m :: * -> *).
    MonadUnique m =>
    Subst -> [Id] -> m (Subst, [Id])
    cloneBndrs Subst
    subst [Id]
    vs
      = do us <- m [Unique]
    forall (m :: * -> *). MonadUnique m => m [Unique]
    getUniquesM
           pure $ mapAccumL (\Subst
    subst (Id
    v, Unique
    u) -> Subst -> Unique -> Id -> (Subst, Id)
    cloneBndr Subst
    subst Unique
    u Id
    v) subst (vs `zip` us)

    cloneBndr :: Subst -> Unique -> Var -> (Subst, Var)
    cloneBndr :: Subst -> Unique -> Id -> (Subst, Id)
    cloneBndr Subst
    subst Unique
    uniq Id
    v
      | Id -> Bool
    isTyVar Id
    v = Subst -> Id -> Unique -> (Subst, Id)
    cloneTyVarBndr Subst
    subst Id
    v Unique
    uniq
      | Bool
    otherwise = Subst -> Subst -> (Id, Unique) -> (Subst, Id)
    clone_id Subst
    subst Subst
    subst (Id
    v,Unique
    uniq)  -- Works for coercion variables too

    -- | Clone a mutually recursive group of 'Id's
    cloneRecIdBndrs :: MonadUnique m => Subst -> [Id] -> m (Subst, [Id])
    cloneRecIdBndrs :: forall (m :: * -> *).
    MonadUnique m =>
    Subst -> [Id] -> m (Subst, [Id])
    cloneRecIdBndrs Subst
    subst [Id]
    ids
      = do us <- m [Unique]
    forall (m :: * -> *). MonadUnique m => m [Unique]
    getUniquesM
           let (subst', ids') = mapAccumL (clone_id subst') subst (ids `zip` us)
           pure (subst', ids')

    -- Just like substIdBndr, except that it always makes a new unique
    -- It is given the unique to use
    -- Discards non-Stable unfoldings
    clone_id    :: Subst                    -- Substitution for the IdInfo
                -> Subst -> (Id, Unique)    -- Substitution and Id to transform
                -> (Subst, Id)              -- Transformed pair

    clone_id :: Subst -> Subst -> (Id, Unique) -> (Subst, Id)
    clone_id Subst
    rec_subst subst :: Subst
    subst@(Subst InScopeSet
    in_scope IdSubstEnv
    idvs TvSubstEnv
    tvs CvSubstEnv
    cvs) (Id
    old_id, Unique
    uniq)
      = (InScopeSet -> IdSubstEnv -> TvSubstEnv -> CvSubstEnv -> Subst
    Subst InScopeSet
    new_in_scope IdSubstEnv
    new_idvs TvSubstEnv
    tvs CvSubstEnv
    new_cvs, Id
    new_id)
      where
        id1 :: Id
    id1     = Id -> Unique -> Id
    setVarUnique Id
    old_id Unique
    uniq
        id2 :: Id
    id2     = Subst -> Id -> Id
    substIdType Subst
    subst Id
    id1
        !new_id :: Id
    new_id = Maybe IdInfo -> Id -> Id
    maybeModifyIdInfo (Subst -> Id -> IdInfo -> Maybe IdInfo
    substIdInfo Subst
    rec_subst Id
    id2 (HasDebugCallStack => Id -> IdInfo
    Id -> IdInfo
    idInfo Id
    old_id)) Id
    id2
        !new_in_scope :: InScopeSet
    new_in_scope = InScopeSet
    in_scope InScopeSet -> Id -> InScopeSet
    `InScopeSet.extendInScopeSet` Id
    new_id
            -- Forcing new_in_scope improves T9675 by 1.7%
        (!IdSubstEnv
    new_idvs, !CvSubstEnv
    new_cvs) | Id -> Bool
    isCoVar Id
    old_id = (IdSubstEnv
    idvs, CvSubstEnv -> Id -> Coercion -> CvSubstEnv
    forall a. VarEnv a -> Id -> a -> VarEnv a
    extendVarEnv CvSubstEnv
    cvs Id
    old_id (Id -> Coercion
    mkCoVarCo Id
    new_id))
                              | Bool
    otherwise      = (IdSubstEnv -> Id -> CoreExpr -> IdSubstEnv
    forall a. VarEnv a -> Id -> a -> VarEnv a
    extendVarEnv IdSubstEnv
    idvs Id
    old_id (Id -> CoreExpr
    forall b. Id -> Expr b
    Var Id
    new_id), CvSubstEnv
    cvs)

    {-
    ************************************************************************
    *                                                                      *
                    Types and Coercions
    *                                                                      *
    ************************************************************************
    -}

    {-
    ************************************************************************
    *                                                                      *
    \section{IdInfo substitution}
    *                                                                      *
    ************************************************************************
    -}

    substIdType :: Subst -> Id -> Id
    substIdType :: Subst -> Id -> Id
    substIdType subst :: Subst
    subst@(Subst InScopeSet
    _ IdSubstEnv
    _ TvSubstEnv
    tv_env CvSubstEnv
    cv_env) Id
    id
      | (TvSubstEnv -> Bool
    forall a. VarEnv a -> Bool
    isEmptyVarEnv TvSubstEnv
    tv_env Bool -> Bool -> Bool
    && CvSubstEnv -> Bool
    forall a. VarEnv a -> Bool
    isEmptyVarEnv CvSubstEnv
    cv_env)
        Bool -> Bool -> Bool
    || (Type -> Bool
    noFreeVarsOfType Type
    old_ty Bool -> Bool -> Bool
    && Type -> Bool
    noFreeVarsOfType Type
    old_w) = Id
    id
      | Bool
    otherwise   =
          (Type -> Type) -> Id -> Id
    updateIdTypeAndMult (Subst -> Type -> Type
    substTyUnchecked Subst
    subst) Id
    id
            -- The tyCoVarsOfType is cheaper than it looks
            -- because we cache the free tyvars of the type
            -- in a Note in the id's type itself
      where
        old_ty :: Type
    old_ty = Id -> Type
    idType Id
    id
        old_w :: Type
    old_w  = Id -> Type
    varMult Id
    id

    ------------------
    -- | Substitute into some 'IdInfo' with regard to the supplied new 'Id'.
    -- Discards unfoldings, unless they are Stable
    substIdInfo :: Subst -> Id -> IdInfo -> Maybe IdInfo
    substIdInfo :: Subst -> Id -> IdInfo -> Maybe IdInfo
    substIdInfo Subst
    subst Id
    new_id IdInfo
    info
      | Bool
    nothing_to_do = Maybe IdInfo
    forall a. Maybe a
    Nothing
      | Bool
    otherwise     = IdInfo -> Maybe IdInfo
    forall a. a -> Maybe a
    Just (IdInfo
    info IdInfo -> RuleInfo -> IdInfo
    `setRuleInfo`      Subst -> Id -> RuleInfo -> RuleInfo
    substRuleInfo Subst
    subst Id
    new_id RuleInfo
    old_rules
                                   IdInfo -> Unfolding -> IdInfo
    `setUnfoldingInfo` Subst -> Unfolding -> Unfolding
    substUnfolding Subst
    subst Unfolding
    old_unf)
      where
        old_rules :: RuleInfo
    old_rules     = IdInfo -> RuleInfo
    ruleInfo IdInfo
    info
        old_unf :: Unfolding
    old_unf       = IdInfo -> Unfolding
    realUnfoldingInfo IdInfo
    info
        nothing_to_do :: Bool
    nothing_to_do = RuleInfo -> Bool
    isEmptyRuleInfo RuleInfo
    old_rules Bool -> Bool -> Bool
    && Bool -> Bool
    not (Unfolding -> Bool
    hasCoreUnfolding Unfolding
    old_unf)

    ------------------
    -- | Substitutes for the 'Id's within an unfolding
    -- NB: substUnfolding /discards/ any unfolding without
    --     without a Stable source.  This is usually what we want,
    --     but it may be a bit unexpected
    substUnfolding, substUnfoldingSC :: Subst -> Unfolding -> Unfolding
            -- Seq'ing on the returned Unfolding is enough to cause
            -- all the substitutions to happen completely

    substUnfoldingSC :: Subst -> Unfolding -> Unfolding
    substUnfoldingSC Subst
    subst Unfolding
    unf       -- Short-cut version
      | Subst -> Bool
    isEmptySubst Subst
    subst = Unfolding
    unf
      | Bool
    otherwise          = Subst -> Unfolding -> Unfolding
    substUnfolding Subst
    subst Unfolding
    unf

    substUnfolding :: Subst -> Unfolding -> Unfolding
    substUnfolding Subst
    subst df :: Unfolding
    df@(DFunUnfolding { df_bndrs :: Unfolding -> [Id]
    df_bndrs = [Id]
    bndrs, df_args :: Unfolding -> [CoreExpr]
    df_args = [CoreExpr]
    args })
      = Unfolding
    df { df_bndrs = bndrs', df_args = args' }
      where
        (Subst
    subst',[Id]
    bndrs') = Subst -> [Id] -> (Subst, [Id])
    forall (f :: * -> *).
    Traversable f =>
    Subst -> f Id -> (Subst, f Id)
    substBndrs Subst
    subst [Id]
    bndrs
        args' :: [CoreExpr]
    args'           = (CoreExpr -> CoreExpr) -> [CoreExpr] -> [CoreExpr]
    forall a b. (a -> b) -> [a] -> [b]
    map (HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst') [CoreExpr]
    args

    substUnfolding Subst
    subst unf :: Unfolding
    unf@(CoreUnfolding { uf_tmpl :: Unfolding -> CoreExpr
    uf_tmpl = CoreExpr
    tmpl, uf_src :: Unfolding -> UnfoldingSource
    uf_src = UnfoldingSource
    src })
      -- Retain stable unfoldings
      | Bool -> Bool
    not (UnfoldingSource -> Bool
    isStableSource UnfoldingSource
    src)  -- Zap an unstable unfolding, to save substitution work
      = Unfolding
    NoUnfolding
      | Bool
    otherwise                 -- But keep a stable one!
      = CoreExpr -> ()
    seqExpr CoreExpr
    new_tmpl () -> Unfolding -> Unfolding
    forall a b. a -> b -> b
    `seq`
        Unfolding
    unf { uf_tmpl = new_tmpl }
      where
        new_tmpl :: CoreExpr
    new_tmpl = HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    subst CoreExpr
    tmpl

    substUnfolding Subst
    _ Unfolding
    unf = Unfolding
    unf      -- NoUnfolding, OtherCon

    ------------------
    substIdOcc :: Subst -> Id -> Id
    -- These Ids should not be substituted to non-Ids
    substIdOcc :: Subst -> Id -> Id
    substIdOcc Subst
    subst Id
    v = case HasDebugCallStack => Subst -> Id -> CoreExpr
    Subst -> Id -> CoreExpr
    lookupIdSubst Subst
    subst Id
    v of
                            Var Id
    v' -> Id
    v'
                            CoreExpr
    other  -> String -> SDoc -> Id
    forall a. HasCallStack => String -> SDoc -> a
    pprPanic String
    "substIdOcc" ([SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat [Id -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Id
    v SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> CoreExpr -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr CoreExpr
    other, Subst -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Subst
    subst])

    ------------------
    -- | Substitutes for the 'Id's within the 'RuleInfo' given the new function 'Id'
    substRuleInfo :: Subst -> Id -> RuleInfo -> RuleInfo
    substRuleInfo :: Subst -> Id -> RuleInfo -> RuleInfo
    substRuleInfo Subst
    subst Id
    new_id (RuleInfo [CoreRule]
    rules DVarSet
    rhs_fvs)
      = [CoreRule] -> DVarSet -> RuleInfo
    RuleInfo ((CoreRule -> CoreRule) -> [CoreRule] -> [CoreRule]
    forall a b. (a -> b) -> [a] -> [b]
    map (Subst -> (Name -> Name) -> CoreRule -> CoreRule
    substRule Subst
    subst Name -> Name
    subst_ru_fn) [CoreRule]
    rules)
                      (HasDebugCallStack => Subst -> DVarSet -> DVarSet
    Subst -> DVarSet -> DVarSet
    substDVarSet Subst
    subst DVarSet
    rhs_fvs)
      where
        subst_ru_fn :: Name -> Name
    subst_ru_fn = Name -> Name -> Name
    forall a b. a -> b -> a
    const (Id -> Name
    idName Id
    new_id)

    ------------------
    substRulesForImportedIds :: Subst -> [CoreRule] -> [CoreRule]
    substRulesForImportedIds :: Subst -> [CoreRule] -> [CoreRule]
    substRulesForImportedIds Subst
    subst [CoreRule]
    rules
      = (CoreRule -> CoreRule) -> [CoreRule] -> [CoreRule]
    forall a b. (a -> b) -> [a] -> [b]
    map (Subst -> (Name -> Name) -> CoreRule -> CoreRule
    substRule Subst
    subst Name -> Name
    forall {a} {a}. Outputable a => a -> a
    not_needed) [CoreRule]
    rules
      where
        not_needed :: a -> a
    not_needed a
    name = String -> SDoc -> a
    forall a. HasCallStack => String -> SDoc -> a
    pprPanic String
    "substRulesForImportedIds" (a -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr a
    name)

    ------------------
    substRule :: Subst -> (Name -> Name) -> CoreRule -> CoreRule

    -- The subst_ru_fn argument is applied to substitute the ru_fn field
    -- of the rule:
    --    - Rules for *imported* Ids never change ru_fn
    --    - Rules for *local* Ids are in the IdInfo for that Id,
    --      and the ru_fn field is simply replaced by the new name
    --      of the Id
    substRule :: Subst -> (Name -> Name) -> CoreRule -> CoreRule
    substRule Subst
    _ Name -> Name
    _ rule :: CoreRule
    rule@(BuiltinRule {}) = CoreRule
    rule
    substRule Subst
    subst Name -> Name
    subst_ru_fn rule :: CoreRule
    rule@(Rule { ru_bndrs :: CoreRule -> [Id]
    ru_bndrs = [Id]
    bndrs, ru_args :: CoreRule -> [CoreExpr]
    ru_args = [CoreExpr]
    args
                                           , ru_fn :: CoreRule -> Name
    ru_fn = Name
    fn_name, ru_rhs :: CoreRule -> CoreExpr
    ru_rhs = CoreExpr
    rhs
                                           , ru_local :: CoreRule -> Bool
    ru_local = Bool
    is_local })
      = CoreRule
    rule { ru_bndrs = bndrs'
             , ru_fn    = if is_local
                            then subst_ru_fn fn_name
                            else fn_name
             , ru_args  = map (substExpr subst') args
             , ru_rhs   = substExpr subst' rhs }
               -- Do NOT optimise the RHS (previously we did simplOptExpr here)
               -- See Note [Substitute lazily]
      where
        (Subst
    subst', [Id]
    bndrs') = Subst -> [Id] -> (Subst, [Id])
    forall (f :: * -> *).
    Traversable f =>
    Subst -> f Id -> (Subst, f Id)
    substBndrs Subst
    subst [Id]
    bndrs

    ------------------
    substDVarSet :: HasDebugCallStack => Subst -> DVarSet -> DVarSet
    substDVarSet :: HasDebugCallStack => Subst -> DVarSet -> DVarSet
    substDVarSet subst :: Subst
    subst@(Subst InScopeSet
    _ IdSubstEnv
    _ TvSubstEnv
    tv_env CvSubstEnv
    cv_env) DVarSet
    fvs
      = [Id] -> DVarSet
    mkDVarSet ([Id] -> DVarSet) -> [Id] -> DVarSet
    forall a b. (a -> b) -> a -> b
    $ ([Id], VarSet) -> [Id]
    forall a b. (a, b) -> a
    fst (([Id], VarSet) -> [Id]) -> ([Id], VarSet) -> [Id]
    forall a b. (a -> b) -> a -> b
    $ (Id -> ([Id], VarSet) -> ([Id], VarSet))
    -> ([Id], VarSet) -> [Id] -> ([Id], VarSet)
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr Id -> ([Id], VarSet) -> ([Id], VarSet)
    subst_fv ([], VarSet
    emptyVarSet) ([Id] -> ([Id], VarSet)) -> [Id] -> ([Id], VarSet)
    forall a b. (a -> b) -> a -> b
    $ DVarSet -> [Id]
    dVarSetElems DVarSet
    fvs
      where
      subst_fv :: Var -> ([Var], VarSet) -> ([Var], VarSet)
      subst_fv :: Id -> ([Id], VarSet) -> ([Id], VarSet)
    subst_fv Id
    fv ([Id], VarSet)
    acc
         | Id -> Bool
    isTyVar Id
    fv
         , let fv_ty :: Type
    fv_ty = TvSubstEnv -> Id -> Maybe Type
    forall a. VarEnv a -> Id -> Maybe a
    lookupVarEnv TvSubstEnv
    tv_env Id
    fv Maybe Type -> Type -> Type
    forall a. Maybe a -> a -> a
    `orElse` Id -> Type
    mkTyVarTy Id
    fv
         = Type -> FV
    tyCoFVsOfType Type
    fv_ty (Bool -> Id -> Bool
    forall a b. a -> b -> a
    const Bool
    True) VarSet
    emptyVarSet (([Id], VarSet) -> ([Id], VarSet))
    -> ([Id], VarSet) -> ([Id], VarSet)
    forall a b. (a -> b) -> a -> b
    $! ([Id], VarSet)
    acc
         | Id -> Bool
    isCoVar Id
    fv
         , let fv_co :: Coercion
    fv_co = CvSubstEnv -> Id -> Maybe Coercion
    forall a. VarEnv a -> Id -> Maybe a
    lookupVarEnv CvSubstEnv
    cv_env Id
    fv Maybe Coercion -> Coercion -> Coercion
    forall a. Maybe a -> a -> a
    `orElse` Id -> Coercion
    mkCoVarCo Id
    fv
         = Coercion -> FV
    tyCoFVsOfCo Coercion
    fv_co (Bool -> Id -> Bool
    forall a b. a -> b -> a
    const Bool
    True) VarSet
    emptyVarSet (([Id], VarSet) -> ([Id], VarSet))
    -> ([Id], VarSet) -> ([Id], VarSet)
    forall a b. (a -> b) -> a -> b
    $! ([Id], VarSet)
    acc
         | Bool
    otherwise
         , let fv_expr :: CoreExpr
    fv_expr = HasDebugCallStack => Subst -> Id -> CoreExpr
    Subst -> Id -> CoreExpr
    lookupIdSubst Subst
    subst Id
    fv
         = CoreExpr -> FV
    exprFVs CoreExpr
    fv_expr (Bool -> Id -> Bool
    forall a b. a -> b -> a
    const Bool
    True) VarSet
    emptyVarSet (([Id], VarSet) -> ([Id], VarSet))
    -> ([Id], VarSet) -> ([Id], VarSet)
    forall a b. (a -> b) -> a -> b
    $! ([Id], VarSet)
    acc

    ------------------
    -- | Drop free vars from the breakpoint if they have a non-variable substitution.
    substTickish :: Subst -> CoreTickish -> CoreTickish
    substTickish :: Subst -> CoreTickish -> CoreTickish
    substTickish Subst
    subst (Breakpoint XBreakpoint 'TickishPassCore
    ext Int
    n [XTickishId 'TickishPassCore]
    ids Module
    modl)
       = XBreakpoint 'TickishPassCore
    -> Int -> [XTickishId 'TickishPassCore] -> Module -> CoreTickish
    forall (pass :: TickishPass).
    XBreakpoint pass
    -> Int -> [XTickishId pass] -> Module -> GenTickish pass
    Breakpoint XBreakpoint 'TickishPassCore
    ext Int
    n ((Id -> Maybe Id) -> [Id] -> [Id]
    forall a b. (a -> Maybe b) -> [a] -> [b]
    mapMaybe Id -> Maybe Id
    do_one [Id]
    [XTickishId 'TickishPassCore]
    ids) Module
    modl
     where
        do_one :: Id -> Maybe Id
    do_one = CoreExpr -> Maybe Id
    getIdFromTrivialExpr_maybe (CoreExpr -> Maybe Id) -> (Id -> CoreExpr) -> Id -> Maybe Id
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . HasDebugCallStack => Subst -> Id -> CoreExpr
    Subst -> Id -> CoreExpr
    lookupIdSubst Subst
    subst

    substTickish Subst
    _subst CoreTickish
    other = CoreTickish
    other

    {- Note [Substitute lazily]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~
    The functions that substitute over IdInfo must be pretty lazy, because
    they are knot-tied by substRecBndrs.

    One case in point was #10627 in which a rule for a function 'f'
    referred to 'f' (at a different type) on the RHS.  But instead of just
    substituting in the rhs of the rule, we were calling simpleOptExpr, which
    looked at the idInfo for 'f'; result <<loop>>.

    In any case we don't need to optimise the RHS of rules, or unfoldings,
    because the simplifier will do that.

    Another place this went wrong was in `substRuleInfo`, which would immediately force
    the lazy call to substExpr, which led to an infinite loop (as reported by #20112).

    This time the call stack looked something like:

    * `substRecBndrs`
    * `substIdBndr`
    * `substIdInfo`
    * `substRuleInfo`
    * `substRule`
    * `substExpr`
    * `mkTick`
    * `isSaturatedConApp`
    * Look at `IdInfo` for thing we are currently substituting because the rule is attached to `transpose` and mentions it in the `RHS` of the rule.

    and the rule was

    {-# RULES
    "transpose/overlays1" forall xs. transpose (overlays1 xs) = overlays1 (fmap transpose xs) #-}

    This rule was attached to `transpose`, but also mentions itself in the RHS so we have
    to be careful to not force the `IdInfo` for transpose when dealing with the RHS of the rule.

    Note [substTickish]
    ~~~~~~~~~~~~~~~~~~~~~~
    A Breakpoint contains a list of Ids.  What happens if we ever want to
    substitute an expression for one of these Ids?

    First, we ensure that we only ever substitute trivial expressions for
    these Ids, by marking them as NoOccInfo in the occurrence analyser.
    Then, when substituting for the Id, we unwrap any type applications
    and abstractions to get back to an Id, with getIdFromTrivialExpr.

    Second, we have to ensure that we never try to substitute a literal
    for an Id in a breakpoint.  We ensure this by never storing an Id with
    an unlifted type in a Breakpoint - see GHC.HsToCore.Ticks.mkTickish.
    Breakpoints can't handle free variables with unlifted types anyway.

    These measures are only reliable with unoptimized code.
    Since we can now enable optimizations for GHCi with
    @-fno-unoptimized-core-for-interpreter -O@, nontrivial expressions can be
    substituted, e.g. by specializations.
    Therefore we resort to discarding free variables from breakpoints when this
    situation occurs.
    -}

    {-
    Note [Worker inlining]
    ~~~~~~~~~~~~~~~~~~~~~~
    A worker can get substituted away entirely.
            - it might be trivial
            - it might simply be very small
    We do not treat an InlWrapper as an 'occurrence' in the occurrence
    analyser, so it's possible that the worker is not even in scope any more.

    In all these cases we simply drop the special case, returning to
    InlVanilla.  The WARN is just so I can see if it happens a lot.
    -}