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

    module GHC.Types.Var.Env (
            -- * Var, Id and TyVar environments (maps)
            VarEnv, IdEnv, TyVarEnv, CoVarEnv, TyCoVarEnv,

            -- ** Manipulating these environments
            emptyVarEnv, unitVarEnv, mkVarEnv, mkVarEnv_Directly,
            elemVarEnv, disjointVarEnv, anyVarEnv,
            extendVarEnv, extendVarEnv_C, extendVarEnv_Acc,
            extendVarEnvList,
            plusVarEnv, plusVarEnv_C, plusVarEnv_CD, plusMaybeVarEnv_C,
            plusVarEnvList, alterVarEnv,
            delVarEnvList, delVarEnv,
            minusVarEnv,
            lookupVarEnv, lookupVarEnv_NF, lookupWithDefaultVarEnv,
            lookupVarEnv_Directly,
            mapVarEnv, zipVarEnv,
            modifyVarEnv, modifyVarEnv_Directly,
            isEmptyVarEnv,
            elemVarEnvByKey,
            filterVarEnv, restrictVarEnv,
            partitionVarEnv, varEnvDomain,
            nonDetStrictFoldVarEnv_Directly,

            -- * Deterministic Var environments (maps)
            DVarEnv, DIdEnv, DTyVarEnv,

            -- ** Manipulating these environments
            emptyDVarEnv, mkDVarEnv,
            dVarEnvElts,
            extendDVarEnv, extendDVarEnv_C,
            extendDVarEnvList,
            lookupDVarEnv, elemDVarEnv,
            isEmptyDVarEnv, foldDVarEnv, nonDetStrictFoldDVarEnv,
            mapDVarEnv, filterDVarEnv,
            modifyDVarEnv,
            alterDVarEnv,
            plusDVarEnv, plusDVarEnv_C,
            unitDVarEnv,
            delDVarEnv,
            delDVarEnvList,
            minusDVarEnv,
            partitionDVarEnv,
            anyDVarEnv,

            -- * The InScopeSet type
            InScopeSet(..),

            -- ** Operations on InScopeSets
            emptyInScopeSet, mkInScopeSet, mkInScopeSetList, delInScopeSet,
            extendInScopeSet, extendInScopeSetList, extendInScopeSetSet,
            getInScopeVars, lookupInScope, lookupInScope_Directly,
            unionInScope, elemInScopeSet, uniqAway,
            varSetInScope,
            unsafeGetFreshLocalUnique,

            -- * The RnEnv2 type
            RnEnv2,

            -- ** Operations on RnEnv2s
            mkRnEnv2, rnBndr2, rnBndrs2, rnBndr2_var,
            rnOccL, rnOccR, inRnEnvL, inRnEnvR,  anyInRnEnvR,
            rnOccL_maybe, rnOccR_maybe,
            rnBndrL, rnBndrR, nukeRnEnvL, nukeRnEnvR, rnSwap,
            delBndrL, delBndrR, delBndrsL, delBndrsR,
            extendRnInScopeSetList,
            rnEtaL, rnEtaR,
            rnInScope, rnInScopeSet, lookupRnInScope,
            rnEnvL, rnEnvR,

            -- * TidyEnv and its operation
            TidyEnv,
            emptyTidyEnv, mkEmptyTidyEnv, delTidyEnvList
        ) where

    import GHC.Prelude
    import qualified GHC.Data.Word64Map.Strict as Word64Map -- TODO: Move this to UniqFM

    import GHC.Types.Name.Occurrence
    import GHC.Types.Name
    import GHC.Types.Var as Var
    import GHC.Types.Var.Set
    import GHC.Data.Graph.UnVar   -- UnVarSet
    import GHC.Types.Unique.Set
    import GHC.Types.Unique.FM
    import GHC.Types.Unique.DFM
    import GHC.Types.Unique
    import GHC.Utils.Misc
    import GHC.Utils.Panic
    import GHC.Data.Maybe
    import GHC.Utils.Outputable

    {-
    ************************************************************************
    *                                                                      *
                    In-scope sets
    *                                                                      *
    ************************************************************************
    -}

    -- | A set of variables that are in scope at some point.
    --
    -- Note that this is a /superset/ of the variables that are currently in scope.
    -- See Note [The InScopeSet invariant].
    --
    -- "Secrets of the Glasgow Haskell Compiler inliner" Section 3.2 provides
    -- the motivation for this abstraction.
    newtype InScopeSet = InScope VarSet
            -- Note [Lookups in in-scope set]
            -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            -- We store a VarSet here, but we use this for lookups rather than just
            -- membership tests. Typically the InScopeSet contains the canonical
            -- version of the variable (e.g. with an informative unfolding), so this
            -- lookup is useful (see, for instance, Note [In-scope set as a
            -- substitution]).

            -- Note [The InScopeSet invariant]
            -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            -- The InScopeSet must include every in-scope variable, but it may also
            -- include other variables.

            -- Its principal purpose is to provide a set of variables to be avoided
            -- when creating a fresh identifier (fresh in the sense that it does not
            -- "shadow" any in-scope binding). To do this we simply have to find one that
            -- does not appear in the InScopeSet. This is done by the key function
            -- GHC.Types.Var.Env.uniqAway.

            -- See "Secrets of the Glasgow Haskell Compiler inliner" Section 3.2
            -- for more detailed motivation. #20419 has further discussion.

    instance Outputable InScopeSet where
      ppr :: InScopeSet -> SDoc
    ppr (InScope VarSet
    s) =
        String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "InScope" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+>
        SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc
    braces ([SDoc] -> SDoc
    forall doc. IsLine doc => [doc] -> doc
    fsep ((Var -> SDoc) -> [Var] -> [SDoc]
    forall a b. (a -> b) -> [a] -> [b]
    map (Name -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr (Name -> SDoc) -> (Var -> Name) -> Var -> SDoc
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Var -> Name
    Var.varName) (VarSet -> [Var]
    forall elt. UniqSet elt -> [elt]
    nonDetEltsUniqSet VarSet
    s)))
                          -- It's OK to use nonDetEltsUniqSet here because it's
                          -- only for pretty printing
                          -- In-scope sets get big, and with -dppr-debug
                          -- the output is overwhelming

    emptyInScopeSet :: InScopeSet
    emptyInScopeSet :: InScopeSet
    emptyInScopeSet = VarSet -> InScopeSet
    InScope VarSet
    emptyVarSet

    getInScopeVars ::  InScopeSet -> VarSet
    getInScopeVars :: InScopeSet -> VarSet
    getInScopeVars (InScope VarSet
    vs) = VarSet
    vs

    mkInScopeSet :: VarSet -> InScopeSet
    mkInScopeSet :: VarSet -> InScopeSet
    mkInScopeSet VarSet
    in_scope = VarSet -> InScopeSet
    InScope VarSet
    in_scope

    mkInScopeSetList :: [Var] -> InScopeSet
    mkInScopeSetList :: [Var] -> InScopeSet
    mkInScopeSetList [Var]
    vs = VarSet -> InScopeSet
    InScope ([Var] -> VarSet
    mkVarSet [Var]
    vs)

    extendInScopeSet :: InScopeSet -> Var -> InScopeSet
    extendInScopeSet :: InScopeSet -> Var -> InScopeSet
    extendInScopeSet (InScope VarSet
    in_scope) Var
    v
       = VarSet -> InScopeSet
    InScope (VarSet -> Var -> VarSet
    extendVarSet VarSet
    in_scope Var
    v)

    extendInScopeSetList :: InScopeSet -> [Var] -> InScopeSet
    extendInScopeSetList :: InScopeSet -> [Var] -> InScopeSet
    extendInScopeSetList (InScope VarSet
    in_scope) [Var]
    vs
       = VarSet -> InScopeSet
    InScope (VarSet -> InScopeSet) -> VarSet -> InScopeSet
    forall a b. (a -> b) -> a -> b
    $ (VarSet -> Var -> VarSet) -> VarSet -> [Var] -> VarSet
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' VarSet -> Var -> VarSet
    extendVarSet VarSet
    in_scope [Var]
    vs

    extendInScopeSetSet :: InScopeSet -> VarSet -> InScopeSet
    extendInScopeSetSet :: InScopeSet -> VarSet -> InScopeSet
    extendInScopeSetSet (InScope VarSet
    in_scope) VarSet
    vs
       = VarSet -> InScopeSet
    InScope (VarSet
    in_scope VarSet -> VarSet -> VarSet
    `unionVarSet` VarSet
    vs)

    delInScopeSet :: InScopeSet -> Var -> InScopeSet
    delInScopeSet :: InScopeSet -> Var -> InScopeSet
    delInScopeSet (InScope VarSet
    in_scope) Var
    v = VarSet -> InScopeSet
    InScope (VarSet
    in_scope VarSet -> Var -> VarSet
    `delVarSet` Var
    v)

    elemInScopeSet :: Var -> InScopeSet -> Bool
    elemInScopeSet :: Var -> InScopeSet -> Bool
    elemInScopeSet Var
    v (InScope VarSet
    in_scope) = Var
    v Var -> VarSet -> Bool
    `elemVarSet` VarSet
    in_scope

    -- | Look up a variable the 'InScopeSet'.  This lets you map from
    -- the variable's identity (unique) to its full value.
    lookupInScope :: InScopeSet -> Var -> Maybe Var
    lookupInScope :: InScopeSet -> Var -> Maybe Var
    lookupInScope (InScope VarSet
    in_scope) Var
    v  = VarSet -> Var -> Maybe Var
    lookupVarSet VarSet
    in_scope Var
    v

    lookupInScope_Directly :: InScopeSet -> Unique -> Maybe Var
    lookupInScope_Directly :: InScopeSet -> Unique -> Maybe Var
    lookupInScope_Directly (InScope VarSet
    in_scope) Unique
    uniq
      = VarSet -> Unique -> Maybe Var
    lookupVarSet_Directly VarSet
    in_scope Unique
    uniq

    unionInScope :: InScopeSet -> InScopeSet -> InScopeSet
    unionInScope :: InScopeSet -> InScopeSet -> InScopeSet
    unionInScope (InScope VarSet
    s1) (InScope VarSet
    s2)
      = VarSet -> InScopeSet
    InScope (VarSet
    s1 VarSet -> VarSet -> VarSet
    `unionVarSet` VarSet
    s2)

    varSetInScope :: VarSet -> InScopeSet -> Bool
    varSetInScope :: VarSet -> InScopeSet -> Bool
    varSetInScope VarSet
    vars (InScope VarSet
    s1) = VarSet
    vars VarSet -> VarSet -> Bool
    `subVarSet` VarSet
    s1

    {-
    Note [Local uniques]
    ~~~~~~~~~~~~~~~~~~~~
    Sometimes one must create conjure up a unique which is unique in a particular
    context (but not necessarily globally unique). For instance, one might need to
    create a fresh local identifier which does not shadow any of the locally
    in-scope variables.  For this we purpose we provide 'uniqAway'.

    'uniqAway' is implemented in terms of the 'unsafeGetFreshLocalUnique'
    operation, which generates an unclaimed 'Unique' from an 'InScopeSet'. To
    ensure that we do not conflict with uniques allocated by future allocations
    from 'UniqSupply's, Uniques generated by 'unsafeGetFreshLocalUnique' are
    allocated into a dedicated region of the unique space (namely the X tag).

    Note that one must be quite carefully when using uniques generated in this way
    since they are only locally unique. In particular, two successive calls to
    'uniqAway' on the same 'InScopeSet' will produce the same unique.
     -}

    -- | @uniqAway in_scope v@ finds a unique that is not used in the
    -- in-scope set, and gives that to v. See Note [Local uniques] and
    -- Note [The InScopeSet invariant].
    uniqAway :: InScopeSet -> Var -> Var
    -- It starts with v's current unique, of course, in the hope that it won't
    -- have to change, and thereafter uses the successor to the last derived unique
    -- found in the in-scope set.
    uniqAway :: InScopeSet -> Var -> Var
    uniqAway InScopeSet
    in_scope Var
    var
      | Var
    var Var -> InScopeSet -> Bool
    `elemInScopeSet` InScopeSet
    in_scope = InScopeSet -> Var -> Var
    uniqAway' InScopeSet
    in_scope Var
    var      -- Make a new one
      | Bool
    otherwise                     = Var
    var                         -- Nothing to do

    uniqAway' :: InScopeSet -> Var -> Var
    -- This one *always* makes up a new variable
    uniqAway' :: InScopeSet -> Var -> Var
    uniqAway' InScopeSet
    in_scope Var
    var
      = Var -> Unique -> Var
    setVarUnique Var
    var (InScopeSet -> Unique
    unsafeGetFreshLocalUnique InScopeSet
    in_scope)

    -- | @unsafeGetFreshUnique in_scope@ finds a unique that is not in-scope in the
    -- given 'InScopeSet'. This must be used very carefully since one can very easily
    -- introduce non-unique 'Unique's this way. See Note [Local uniques].
    unsafeGetFreshLocalUnique :: InScopeSet -> Unique
    unsafeGetFreshLocalUnique :: InScopeSet -> Unique
    unsafeGetFreshLocalUnique (InScope VarSet
    set)
      | Just (Key
    uniq,Var
    _) <- Key -> Word64Map Var -> Maybe (Key, Var)
    forall a. Key -> Word64Map a -> Maybe (Key, a)
    Word64Map.lookupLT (Unique -> Key
    getKey Unique
    maxLocalUnique) (UniqFM Var Var -> Word64Map Var
    forall {k} (key :: k) elt. UniqFM key elt -> Word64Map elt
    ufmToIntMap (UniqFM Var Var -> Word64Map Var)
    -> UniqFM Var Var -> Word64Map Var
    forall a b. (a -> b) -> a -> b
    $ VarSet -> UniqFM Var Var
    forall a. UniqSet a -> UniqFM a a
    getUniqSet VarSet
    set)
      , let uniq' :: Unique
    uniq' = Key -> Unique
    mkLocalUnique Key
    uniq
      , Bool -> Bool
    not (Bool -> Bool) -> Bool -> Bool
    forall a b. (a -> b) -> a -> b
    $ Unique
    uniq' Unique -> Unique -> Bool
    `ltUnique` Unique
    minLocalUnique
      = Unique -> Unique
    incrUnique Unique
    uniq'

      | Bool
    otherwise
      = Unique
    minLocalUnique

    {-
    ************************************************************************
    *                                                                      *
                    Dual renaming
    *                                                                      *
    ************************************************************************
    -}

    -- | Rename Environment 2
    --
    -- When we are comparing (or matching) types or terms, we are faced with
    -- \"going under\" corresponding binders.  E.g. when comparing:
    --
    -- > \x. e1     ~   \y. e2
    --
    -- Basically we want to rename [@x@ -> @y@] or [@y@ -> @x@], but there are lots of
    -- things we must be careful of.  In particular, @x@ might be free in @e2@, or
    -- y in @e1@.  So the idea is that we come up with a fresh binder that is free
    -- in neither, and rename @x@ and @y@ respectively.  That means we must maintain:
    --
    -- 1. A renaming for the left-hand expression
    --
    -- 2. A renaming for the right-hand expressions
    --
    -- 3. An in-scope set
    --
    -- Furthermore, when matching, we want to be able to have an 'occurs check',
    -- to prevent:
    --
    -- > \x. f   ~   \y. y
    --
    -- matching with [@f@ -> @y@].  So for each expression we want to know that set of
    -- locally-bound variables. That is precisely the domain of the mappings 1.
    -- and 2., but we must ensure that we always extend the mappings as we go in.
    --
    -- All of this information is bundled up in the 'RnEnv2'
    data RnEnv2
      = RV2 { RnEnv2 -> UniqFM Var Var
    envL     :: VarEnv Var        -- Renaming for Left term
            , RnEnv2 -> UniqFM Var Var
    envR     :: VarEnv Var        -- Renaming for Right term
            , RnEnv2 -> InScopeSet
    in_scope :: InScopeSet }      -- In scope in left or right terms

    -- The renamings envL and envR are *guaranteed* to contain a binding
    -- for every variable bound as we go into the term, even if it is not
    -- renamed.  That way we can ask what variables are locally bound
    -- (inRnEnvL, inRnEnvR)

    mkRnEnv2 :: InScopeSet -> RnEnv2
    mkRnEnv2 :: InScopeSet -> RnEnv2
    mkRnEnv2 InScopeSet
    vars = RV2     { envL :: UniqFM Var Var
    envL     = UniqFM Var Var
    forall a. VarEnv a
    emptyVarEnv
                            , envR :: UniqFM Var Var
    envR     = UniqFM Var Var
    forall a. VarEnv a
    emptyVarEnv
                            , in_scope :: InScopeSet
    in_scope = InScopeSet
    vars }

    extendRnInScopeSetList :: RnEnv2 -> [Var] -> RnEnv2
    extendRnInScopeSetList :: RnEnv2 -> [Var] -> RnEnv2
    extendRnInScopeSetList RnEnv2
    env [Var]
    vs
      | [Var] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [Var]
    vs   = RnEnv2
    env
      | Bool
    otherwise = RnEnv2
    env { in_scope = extendInScopeSetList (in_scope env) vs }

    rnInScope :: Var -> RnEnv2 -> Bool
    rnInScope :: Var -> RnEnv2 -> Bool
    rnInScope Var
    x RnEnv2
    env = Var
    x Var -> InScopeSet -> Bool
    `elemInScopeSet` RnEnv2 -> InScopeSet
    in_scope RnEnv2
    env

    rnInScopeSet :: RnEnv2 -> InScopeSet
    rnInScopeSet :: RnEnv2 -> InScopeSet
    rnInScopeSet = RnEnv2 -> InScopeSet
    in_scope

    -- | Retrieve the left mapping
    rnEnvL :: RnEnv2 -> VarEnv Var
    rnEnvL :: RnEnv2 -> UniqFM Var Var
    rnEnvL = RnEnv2 -> UniqFM Var Var
    envL

    -- | Retrieve the right mapping
    rnEnvR :: RnEnv2 -> VarEnv Var
    rnEnvR :: RnEnv2 -> UniqFM Var Var
    rnEnvR = RnEnv2 -> UniqFM Var Var
    envR

    rnBndrs2 :: RnEnv2 -> [Var] -> [Var] -> RnEnv2
    -- ^ Applies 'rnBndr2' to several variables: the two variable lists must be of equal length
    rnBndrs2 :: RnEnv2 -> [Var] -> [Var] -> RnEnv2
    rnBndrs2 RnEnv2
    env [Var]
    bsL [Var]
    bsR = (RnEnv2 -> Var -> Var -> RnEnv2)
    -> RnEnv2 -> [Var] -> [Var] -> RnEnv2
    forall acc a b. (acc -> a -> b -> acc) -> acc -> [a] -> [b] -> acc
    foldl2 RnEnv2 -> Var -> Var -> RnEnv2
    rnBndr2 RnEnv2
    env [Var]
    bsL [Var]
    bsR

    rnBndr2 :: RnEnv2 -> Var -> Var -> RnEnv2
    -- ^ @rnBndr2 env bL bR@ goes under a binder @bL@ in the Left term,
    --                       and binder @bR@ in the Right term.
    -- It finds a new binder, @new_b@,
    -- and returns an environment mapping @bL -> new_b@ and @bR -> new_b@
    rnBndr2 :: RnEnv2 -> Var -> Var -> RnEnv2
    rnBndr2 RnEnv2
    env Var
    bL Var
    bR = (RnEnv2, Var) -> RnEnv2
    forall a b. (a, b) -> a
    fst ((RnEnv2, Var) -> RnEnv2) -> (RnEnv2, Var) -> RnEnv2
    forall a b. (a -> b) -> a -> b
    $ RnEnv2 -> Var -> Var -> (RnEnv2, Var)
    rnBndr2_var RnEnv2
    env Var
    bL Var
    bR

    rnBndr2_var :: RnEnv2 -> Var -> Var -> (RnEnv2, Var)
    -- ^ Similar to 'rnBndr2' but returns the new variable as well as the
    -- new environment.
    -- Postcondition: the type of the returned Var is that of bR
    rnBndr2_var :: RnEnv2 -> Var -> Var -> (RnEnv2, Var)
    rnBndr2_var (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    envL, envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    envR, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) Var
    bL Var
    bR
      = (RV2 { envL :: UniqFM Var Var
    envL     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envL Var
    bL Var
    new_b   -- See Note
             , envR :: UniqFM Var Var
    envR     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envR Var
    bR Var
    new_b   -- [Rebinding]
             , in_scope :: InScopeSet
    in_scope = InScopeSet -> Var -> InScopeSet
    extendInScopeSet InScopeSet
    in_scope Var
    new_b }, Var
    new_b)
      where
            -- Find a new binder not in scope in either term
            -- To avoid calling `uniqAway`, we try bL's Unique
            -- But we always return a Var whose type is that of bR
        new_b :: Var
    new_b | Bool -> Bool
    not (Var
    bR Var -> InScopeSet -> Bool
    `elemInScopeSet` InScopeSet
    in_scope) = Var
    bR
              | Bool -> Bool
    not (Var
    bL Var -> InScopeSet -> Bool
    `elemInScopeSet` InScopeSet
    in_scope) = Var
    bR Var -> Unique -> Var
    `setVarUnique` Var -> Unique
    varUnique Var
    bL
              | Bool
    otherwise                          = InScopeSet -> Var -> Var
    uniqAway' InScopeSet
    in_scope Var
    bR

            -- Note [Rebinding]
            -- ~~~~~~~~~~~~~~~~
            -- If the new var is the same as the old one, note that
            -- the extendVarEnv *replaces* any current renaming
            -- E.g.   (\x. \x. ...)  ~  (\y. \z. ...)
            --
            --                        envL    envR          in_scope
            --   Inside \x  \y      { [x->y], [y->y],       {y} }
            --          \x  \z      { [x->z], [y->y, z->z], {y,z} }
            --          The envL binding [x->y] is replaced by [x->z]

    rnBndrL :: RnEnv2 -> Var -> (RnEnv2, Var)
    -- ^ Similar to 'rnBndr2' but used when there's a binder on the left
    -- side only.
    rnBndrL :: RnEnv2 -> Var -> (RnEnv2, Var)
    rnBndrL (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    envL, envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    envR, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) Var
    bL
      = (RV2 { envL :: UniqFM Var Var
    envL     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envL Var
    bL Var
    new_b
             , envR :: UniqFM Var Var
    envR     = UniqFM Var Var
    envR
             , in_scope :: InScopeSet
    in_scope = InScopeSet -> Var -> InScopeSet
    extendInScopeSet InScopeSet
    in_scope Var
    new_b }, Var
    new_b)
      where
        new_b :: Var
    new_b = InScopeSet -> Var -> Var
    uniqAway InScopeSet
    in_scope Var
    bL

    rnBndrR :: RnEnv2 -> Var -> (RnEnv2, Var)
    -- ^ Similar to 'rnBndr2' but used when there's a binder on the right
    -- side only.
    rnBndrR :: RnEnv2 -> Var -> (RnEnv2, Var)
    rnBndrR (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    envL, envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    envR, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) Var
    bR
      = (RV2 { envR :: UniqFM Var Var
    envR     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envR Var
    bR Var
    new_b
             , envL :: UniqFM Var Var
    envL     = UniqFM Var Var
    envL
             , in_scope :: InScopeSet
    in_scope = InScopeSet -> Var -> InScopeSet
    extendInScopeSet InScopeSet
    in_scope Var
    new_b }, Var
    new_b)
      where
        new_b :: Var
    new_b = InScopeSet -> Var -> Var
    uniqAway InScopeSet
    in_scope Var
    bR

    rnEtaL :: RnEnv2 -> Var -> (RnEnv2, Var)
    -- ^ Similar to 'rnBndrL' but used for eta expansion
    -- See Note [Eta expansion]
    rnEtaL :: RnEnv2 -> Var -> (RnEnv2, Var)
    rnEtaL (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    envL, envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    envR, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) Var
    bL
      = (RV2 { envL :: UniqFM Var Var
    envL     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envL Var
    bL Var
    new_b
             , envR :: UniqFM Var Var
    envR     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envR Var
    new_b Var
    new_b     -- Note [Eta expansion]
             , in_scope :: InScopeSet
    in_scope = InScopeSet -> Var -> InScopeSet
    extendInScopeSet InScopeSet
    in_scope Var
    new_b }, Var
    new_b)
      where
        new_b :: Var
    new_b = InScopeSet -> Var -> Var
    uniqAway InScopeSet
    in_scope Var
    bL

    rnEtaR :: RnEnv2 -> Var -> (RnEnv2, Var)
    -- ^ Similar to 'rnBndr2' but used for eta expansion
    -- See Note [Eta expansion]
    rnEtaR :: RnEnv2 -> Var -> (RnEnv2, Var)
    rnEtaR (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    envL, envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    envR, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) Var
    bR
      = (RV2 { envL :: UniqFM Var Var
    envL     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envL Var
    new_b Var
    new_b     -- Note [Eta expansion]
             , envR :: UniqFM Var Var
    envR     = UniqFM Var Var -> Var -> Var -> UniqFM Var Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv UniqFM Var Var
    envR Var
    bR Var
    new_b
             , in_scope :: InScopeSet
    in_scope = InScopeSet -> Var -> InScopeSet
    extendInScopeSet InScopeSet
    in_scope Var
    new_b }, Var
    new_b)
      where
        new_b :: Var
    new_b = InScopeSet -> Var -> Var
    uniqAway InScopeSet
    in_scope Var
    bR

    delBndrL, delBndrR :: RnEnv2 -> Var -> RnEnv2
    delBndrL :: RnEnv2 -> Var -> RnEnv2
    delBndrL rn :: RnEnv2
    rn@(RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    env, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) Var
    v
      = RnEnv2
    rn { envL = env `delVarEnv` v, in_scope = in_scope `extendInScopeSet` v }
    delBndrR :: RnEnv2 -> Var -> RnEnv2
    delBndrR rn :: RnEnv2
    rn@(RV2 { envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    env, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) Var
    v
      = RnEnv2
    rn { envR = env `delVarEnv` v, in_scope = in_scope `extendInScopeSet` v }

    delBndrsL, delBndrsR :: RnEnv2 -> [Var] -> RnEnv2
    delBndrsL :: RnEnv2 -> [Var] -> RnEnv2
    delBndrsL rn :: RnEnv2
    rn@(RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    env, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) [Var]
    v
      = RnEnv2
    rn { envL = env `delVarEnvList` v, in_scope = in_scope `extendInScopeSetList` v }
    delBndrsR :: RnEnv2 -> [Var] -> RnEnv2
    delBndrsR rn :: RnEnv2
    rn@(RV2 { envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    env, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope }) [Var]
    v
      = RnEnv2
    rn { envR = env `delVarEnvList` v, in_scope = in_scope `extendInScopeSetList` v }

    rnOccL, rnOccR :: RnEnv2 -> Var -> Var
    -- ^ Look up the renaming of an occurrence in the left or right term
    rnOccL :: RnEnv2 -> Var -> Var
    rnOccL (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    env }) Var
    v = UniqFM Var Var -> Var -> Maybe Var
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv UniqFM Var Var
    env Var
    v Maybe Var -> Var -> Var
    forall a. Maybe a -> a -> a
    `orElse` Var
    v
    rnOccR :: RnEnv2 -> Var -> Var
    rnOccR (RV2 { envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    env }) Var
    v = UniqFM Var Var -> Var -> Maybe Var
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv UniqFM Var Var
    env Var
    v Maybe Var -> Var -> Var
    forall a. Maybe a -> a -> a
    `orElse` Var
    v

    rnOccL_maybe, rnOccR_maybe :: RnEnv2 -> Var -> Maybe Var
    -- ^ Look up the renaming of an occurrence in the left or right term
    rnOccL_maybe :: RnEnv2 -> Var -> Maybe Var
    rnOccL_maybe (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    env }) Var
    v = UniqFM Var Var -> Var -> Maybe Var
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv UniqFM Var Var
    env Var
    v
    rnOccR_maybe :: RnEnv2 -> Var -> Maybe Var
    rnOccR_maybe (RV2 { envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    env }) Var
    v = UniqFM Var Var -> Var -> Maybe Var
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv UniqFM Var Var
    env Var
    v

    inRnEnvL, inRnEnvR :: RnEnv2 -> Var -> Bool
    -- ^ Tells whether a variable is locally bound
    inRnEnvL :: RnEnv2 -> Var -> Bool
    inRnEnvL (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    env }) Var
    v = Var
    v Var -> UniqFM Var Var -> Bool
    forall a. Var -> VarEnv a -> Bool
    `elemVarEnv` UniqFM Var Var
    env
    inRnEnvR :: RnEnv2 -> Var -> Bool
    inRnEnvR (RV2 { envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    env }) Var
    v = Var
    v Var -> UniqFM Var Var -> Bool
    forall a. Var -> VarEnv a -> Bool
    `elemVarEnv` UniqFM Var Var
    env

    -- | `anyInRnEnvR env set` == `any (inRnEnvR rn_env) (toList set)`
    -- but lazy in the second argument if the right side of the env is empty.
    anyInRnEnvR :: RnEnv2 -> VarSet -> Bool
    anyInRnEnvR :: RnEnv2 -> VarSet -> Bool
    anyInRnEnvR (RV2 { envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    env }) VarSet
    vs
      -- Avoid allocating the predicate if we deal with an empty env.
      | UniqFM Var Var -> Bool
    forall a. VarEnv a -> Bool
    isEmptyVarEnv UniqFM Var Var
    env = Bool
    False
      | Bool
    otherwise         = (Var -> Bool) -> VarSet -> Bool
    anyVarSet (Var -> UniqFM Var Var -> Bool
    forall a. Var -> VarEnv a -> Bool
    `elemVarEnv` UniqFM Var Var
    env) VarSet
    vs

    lookupRnInScope :: RnEnv2 -> Var -> Var
    lookupRnInScope :: RnEnv2 -> Var -> Var
    lookupRnInScope RnEnv2
    env Var
    v = InScopeSet -> Var -> Maybe Var
    lookupInScope (RnEnv2 -> InScopeSet
    in_scope RnEnv2
    env) Var
    v Maybe Var -> Var -> Var
    forall a. Maybe a -> a -> a
    `orElse` Var
    v

    nukeRnEnvL, nukeRnEnvR :: RnEnv2 -> RnEnv2
    -- ^ Wipe the left or right side renaming
    nukeRnEnvL :: RnEnv2 -> RnEnv2
    nukeRnEnvL RnEnv2
    env = RnEnv2
    env { envL = emptyVarEnv }
    nukeRnEnvR :: RnEnv2 -> RnEnv2
    nukeRnEnvR RnEnv2
    env = RnEnv2
    env { envR = emptyVarEnv }

    rnSwap :: RnEnv2 -> RnEnv2
    -- ^ swap the meaning of left and right
    rnSwap :: RnEnv2 -> RnEnv2
    rnSwap (RV2 { envL :: RnEnv2 -> UniqFM Var Var
    envL = UniqFM Var Var
    envL, envR :: RnEnv2 -> UniqFM Var Var
    envR = UniqFM Var Var
    envR, in_scope :: RnEnv2 -> InScopeSet
    in_scope = InScopeSet
    in_scope })
      = RV2 { envL :: UniqFM Var Var
    envL = UniqFM Var Var
    envR, envR :: UniqFM Var Var
    envR = UniqFM Var Var
    envL, in_scope :: InScopeSet
    in_scope = InScopeSet
    in_scope }

    {-
    Note [Eta expansion]
    ~~~~~~~~~~~~~~~~~~~~
    When matching
         (\x.M) ~ N
    we rename x to x' with, where x' is not in scope in
    either term.  Then we want to behave as if we'd seen
         (\x'.M) ~ (\x'.N x')
    Since x' isn't in scope in N, the form (\x'. N x') doesn't
    capture any variables in N.  But we must nevertheless extend
    the envR with a binding [x' -> x'], to support the occurs check.
    For example, if we don't do this, we can get silly matches like
            forall a.  (\y.a)  ~   v
    succeeding with [a -> v y], which is bogus of course.

    ************************************************************************
    *                                                                      *
                    Tidying
    *                                                                      *
    ************************************************************************
    -}

    -- | Tidy Environment
    --
    -- When tidying up print names, we keep a mapping of in-scope occ-names
    -- (the 'TidyOccEnv') and a Var-to-Var of the current renamings
    type TidyEnv = (TidyOccEnv, VarEnv Var)

    emptyTidyEnv :: TidyEnv
    emptyTidyEnv :: TidyEnv
    emptyTidyEnv = (TidyOccEnv
    emptyTidyOccEnv, UniqFM Var Var
    forall a. VarEnv a
    emptyVarEnv)

    mkEmptyTidyEnv :: TidyOccEnv -> TidyEnv
    mkEmptyTidyEnv :: TidyOccEnv -> TidyEnv
    mkEmptyTidyEnv TidyOccEnv
    occ_env = (TidyOccEnv
    occ_env, UniqFM Var Var
    forall a. VarEnv a
    emptyVarEnv)

    delTidyEnvList :: TidyEnv -> [Var] -> TidyEnv
    delTidyEnvList :: TidyEnv -> [Var] -> TidyEnv
    delTidyEnvList (TidyOccEnv
    occ_env, UniqFM Var Var
    var_env) [Var]
    vs = (TidyOccEnv
    occ_env', UniqFM Var Var
    var_env')
      where
        occ_env' :: TidyOccEnv
    occ_env' = TidyOccEnv
    occ_env TidyOccEnv -> [OccName] -> TidyOccEnv
    `delTidyOccEnvList` (Var -> OccName) -> [Var] -> [OccName]
    forall a b. (a -> b) -> [a] -> [b]
    map Var -> OccName
    forall a. NamedThing a => a -> OccName
    getOccName [Var]
    vs
        var_env' :: UniqFM Var Var
    var_env' = UniqFM Var Var
    var_env UniqFM Var Var -> [Var] -> UniqFM Var Var
    forall a. VarEnv a -> [Var] -> VarEnv a
    `delVarEnvList` [Var]
    vs

    {-
    ************************************************************************
    *                                                                      *
       VarEnv
    *                                                                      *
    ************************************************************************
    -}

    -- We would like this to be `UniqFM Var elt`
    -- but the code uses various key types.
    -- So for now make it explicitly untyped

    -- | Variable Environment
    type VarEnv elt     = UniqFM Var elt

    -- | Identifier Environment
    type IdEnv elt      = UniqFM Id elt

    -- | Type Variable Environment
    type TyVarEnv elt   = UniqFM Var elt

    -- | Type or Coercion Variable Environment
    type TyCoVarEnv elt = UniqFM TyCoVar elt

    -- | Coercion Variable Environment
    type CoVarEnv elt   = UniqFM CoVar elt

    emptyVarEnv       :: VarEnv a
    mkVarEnv          :: [(Var, a)] -> VarEnv a
    mkVarEnv_Directly :: [(Unique, a)] -> VarEnv a
    zipVarEnv         :: [Var] -> [a] -> VarEnv a
    unitVarEnv        :: Var -> a -> VarEnv a
    alterVarEnv       :: (Maybe a -> Maybe a) -> VarEnv a -> Var -> VarEnv a
    extendVarEnv      :: VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv_C    :: (a->a->a) -> VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv_Acc  :: (a->b->b) -> (a->b) -> VarEnv b -> Var -> a -> VarEnv b
    plusVarEnv        :: VarEnv a -> VarEnv a -> VarEnv a
    plusVarEnvList    :: [VarEnv a] -> VarEnv a
    extendVarEnvList  :: VarEnv a -> [(Var, a)] -> VarEnv a
    varEnvDomain      :: VarEnv elt -> UnVarSet

    partitionVarEnv   :: (a -> Bool) -> VarEnv a -> (VarEnv a, VarEnv a)
    -- | Only keep variables contained in the VarSet
    restrictVarEnv    :: VarEnv a -> VarSet -> VarEnv a
    delVarEnvList     :: VarEnv a -> [Var] -> VarEnv a
    delVarEnv         :: VarEnv a -> Var -> VarEnv a
    minusVarEnv       :: VarEnv a -> VarEnv b -> VarEnv a
    plusVarEnv_C      :: (a -> a -> a) -> VarEnv a -> VarEnv a -> VarEnv a
    plusVarEnv_CD     :: (a -> a -> a) -> VarEnv a -> a -> VarEnv a -> a -> VarEnv a
    plusMaybeVarEnv_C :: (a -> a -> Maybe a) -> VarEnv a -> VarEnv a -> VarEnv a
    mapVarEnv         :: (a -> b) -> VarEnv a -> VarEnv b
    modifyVarEnv      :: (a -> a) -> VarEnv a -> Var -> VarEnv a

    isEmptyVarEnv     :: VarEnv a -> Bool
    lookupVarEnv      :: VarEnv a -> Var -> Maybe a
    lookupVarEnv_Directly :: VarEnv a -> Unique -> Maybe a
    filterVarEnv      :: (a -> Bool) -> VarEnv a -> VarEnv a
    anyVarEnv         :: (elt -> Bool) -> UniqFM key elt -> Bool
    lookupVarEnv_NF   :: VarEnv a -> Var -> a
    lookupWithDefaultVarEnv :: VarEnv a -> a -> Var -> a
    elemVarEnv        :: Var -> VarEnv a -> Bool
    elemVarEnvByKey   :: Unique -> VarEnv a -> Bool
    disjointVarEnv    :: VarEnv a -> VarEnv a -> Bool
    nonDetStrictFoldVarEnv_Directly :: (Unique -> a -> r -> r) -> r -> VarEnv a -> r

    elemVarEnv :: forall a. Var -> VarEnv a -> Bool
    elemVarEnv       = Var -> UniqFM Var a -> Bool
    forall key elt. Uniquable key => key -> UniqFM key elt -> Bool
    elemUFM
    elemVarEnvByKey :: forall a. Unique -> VarEnv a -> Bool
    elemVarEnvByKey  = Unique -> UniqFM Var a -> Bool
    forall {k} (key :: k) elt. Unique -> UniqFM key elt -> Bool
    elemUFM_Directly
    disjointVarEnv :: forall a. VarEnv a -> VarEnv a -> Bool
    disjointVarEnv   = UniqFM Var a -> UniqFM Var a -> Bool
    forall {k} (key :: k) elt1 elt2.
    UniqFM key elt1 -> UniqFM key elt2 -> Bool
    disjointUFM
    alterVarEnv :: forall a. (Maybe a -> Maybe a) -> VarEnv a -> Var -> VarEnv a
    alterVarEnv      = (Maybe a -> Maybe a) -> UniqFM Var a -> Var -> UniqFM Var a
    forall key elt.
    Uniquable key =>
    (Maybe elt -> Maybe elt) -> UniqFM key elt -> key -> UniqFM key elt
    alterUFM
    extendVarEnv :: forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv     = UniqFM Var a -> Var -> a -> UniqFM Var a
    forall key elt.
    Uniquable key =>
    UniqFM key elt -> key -> elt -> UniqFM key elt
    addToUFM
    extendVarEnv_C :: forall a. (a -> a -> a) -> VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv_C   = (a -> a -> a) -> UniqFM Var a -> Var -> a -> UniqFM Var a
    forall key elt.
    Uniquable key =>
    (elt -> elt -> elt)
    -> UniqFM key elt -> key -> elt -> UniqFM key elt
    addToUFM_C
    extendVarEnv_Acc :: forall a b.
    (a -> b -> b) -> (a -> b) -> VarEnv b -> Var -> a -> VarEnv b
    extendVarEnv_Acc = (a -> b -> b)
    -> (a -> b) -> UniqFM Var b -> Var -> a -> UniqFM Var b
    forall key elt elts.
    Uniquable key =>
    (elt -> elts -> elts)
    -> (elt -> elts)
    -> UniqFM key elts
    -> key
    -> elt
    -> UniqFM key elts
    addToUFM_Acc
    extendVarEnvList :: forall a. VarEnv a -> [(Var, a)] -> VarEnv a
    extendVarEnvList = UniqFM Var a -> [(Var, a)] -> UniqFM Var a
    forall key elt.
    Uniquable key =>
    UniqFM key elt -> [(key, elt)] -> UniqFM key elt
    addListToUFM
    plusVarEnv_C :: forall a. (a -> a -> a) -> VarEnv a -> VarEnv a -> VarEnv a
    plusVarEnv_C     = (a -> a -> a) -> UniqFM Var a -> UniqFM Var a -> UniqFM Var a
    forall {k} elt (key :: k).
    (elt -> elt -> elt)
    -> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
    plusUFM_C
    plusVarEnv_CD :: forall a.
    (a -> a -> a) -> VarEnv a -> a -> VarEnv a -> a -> VarEnv a
    plusVarEnv_CD    = (a -> a -> a)
    -> UniqFM Var a -> a -> UniqFM Var a -> a -> UniqFM Var a
    forall {k} elta eltb eltc (key :: k).
    (elta -> eltb -> eltc)
    -> UniqFM key elta
    -> elta
    -> UniqFM key eltb
    -> eltb
    -> UniqFM key eltc
    plusUFM_CD
    plusMaybeVarEnv_C :: forall a. (a -> a -> Maybe a) -> VarEnv a -> VarEnv a -> VarEnv a
    plusMaybeVarEnv_C = (a -> a -> Maybe a) -> UniqFM Var a -> UniqFM Var a -> UniqFM Var a
    forall {k} elt (key :: k).
    (elt -> elt -> Maybe elt)
    -> UniqFM key elt -> UniqFM key elt -> UniqFM key elt
    plusMaybeUFM_C
    delVarEnvList :: forall a. VarEnv a -> [Var] -> VarEnv a
    delVarEnvList    = UniqFM Var a -> [Var] -> UniqFM Var a
    forall key elt.
    Uniquable key =>
    UniqFM key elt -> [key] -> UniqFM key elt
    delListFromUFM
    delVarEnv :: forall a. VarEnv a -> Var -> VarEnv a
    delVarEnv        = UniqFM Var a -> Var -> UniqFM Var a
    forall key elt.
    Uniquable key =>
    UniqFM key elt -> key -> UniqFM key elt
    delFromUFM
    minusVarEnv :: forall a b. VarEnv a -> VarEnv b -> VarEnv a
    minusVarEnv      = UniqFM Var a -> UniqFM Var b -> UniqFM Var a
    forall {k} (key :: k) elt1 elt2.
    UniqFM key elt1 -> UniqFM key elt2 -> UniqFM key elt1
    minusUFM
    plusVarEnv :: forall a. VarEnv a -> VarEnv a -> VarEnv a
    plusVarEnv       = UniqFM Var a -> UniqFM Var a -> UniqFM Var a
    forall {k} (key :: k) elt.
    UniqFM key elt -> UniqFM key elt -> UniqFM key elt
    plusUFM
    plusVarEnvList :: forall a. [VarEnv a] -> VarEnv a
    plusVarEnvList   = [UniqFM Var a] -> UniqFM Var a
    forall {k} (key :: k) elt. [UniqFM key elt] -> UniqFM key elt
    plusUFMList
    -- lookupVarEnv is very hot (in part due to being called by substTyVar),
    -- if it's not inlined than the mere allocation of the Just constructor causes
    -- perf benchmarks to regress by 2% in some cases. See #21159, !7638 and containers#821
    -- for some more explanation about what exactly went wrong.
    {-# INLINE lookupVarEnv #-}
    lookupVarEnv :: forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv     = UniqFM Var a -> Var -> Maybe a
    forall key elt. Uniquable key => UniqFM key elt -> key -> Maybe elt
    lookupUFM
    lookupVarEnv_Directly :: forall a. VarEnv a -> Unique -> Maybe a
    lookupVarEnv_Directly = UniqFM Var a -> Unique -> Maybe a
    forall {k} (key :: k) elt. UniqFM key elt -> Unique -> Maybe elt
    lookupUFM_Directly
    filterVarEnv :: forall a. (a -> Bool) -> VarEnv a -> VarEnv a
    filterVarEnv     = (a -> Bool) -> UniqFM Var a -> UniqFM Var a
    forall {k} elt (key :: k).
    (elt -> Bool) -> UniqFM key elt -> UniqFM key elt
    filterUFM
    anyVarEnv :: forall {k} elt (key :: k). (elt -> Bool) -> UniqFM key elt -> Bool
    anyVarEnv        = (elt -> Bool) -> UniqFM key elt -> Bool
    forall {k} elt (key :: k). (elt -> Bool) -> UniqFM key elt -> Bool
    anyUFM
    lookupWithDefaultVarEnv :: forall a. VarEnv a -> a -> Var -> a
    lookupWithDefaultVarEnv = UniqFM Var a -> a -> Var -> a
    forall key elt.
    Uniquable key =>
    UniqFM key elt -> elt -> key -> elt
    lookupWithDefaultUFM
    mapVarEnv :: forall a b. (a -> b) -> VarEnv a -> VarEnv b
    mapVarEnv        = (a -> b) -> UniqFM Var a -> UniqFM Var b
    forall {k} elt1 elt2 (key :: k).
    (elt1 -> elt2) -> UniqFM key elt1 -> UniqFM key elt2
    mapUFM
    mkVarEnv :: forall a. [(Var, a)] -> VarEnv a
    mkVarEnv         = [(Var, a)] -> UniqFM Var a
    forall key elt. Uniquable key => [(key, elt)] -> UniqFM key elt
    listToUFM
    mkVarEnv_Directly :: forall a. [(Unique, a)] -> VarEnv a
    mkVarEnv_Directly= [(Unique, a)] -> UniqFM Var a
    forall {k} elt (key :: k). [(Unique, elt)] -> UniqFM key elt
    listToUFM_Directly
    emptyVarEnv :: forall a. VarEnv a
    emptyVarEnv      = UniqFM Var a
    forall {k} (key :: k) elt. UniqFM key elt
    emptyUFM
    unitVarEnv :: forall a. Var -> a -> VarEnv a
    unitVarEnv       = Var -> a -> UniqFM Var a
    forall key elt. Uniquable key => key -> elt -> UniqFM key elt
    unitUFM
    isEmptyVarEnv :: forall a. VarEnv a -> Bool
    isEmptyVarEnv    = UniqFM Var a -> Bool
    forall {k} (key :: k) elt. UniqFM key elt -> Bool
    isNullUFM
    partitionVarEnv :: forall a. (a -> Bool) -> VarEnv a -> (VarEnv a, VarEnv a)
    partitionVarEnv  = (a -> Bool) -> UniqFM Var a -> (UniqFM Var a, UniqFM Var a)
    forall {k} elt (key :: k).
    (elt -> Bool) -> UniqFM key elt -> (UniqFM key elt, UniqFM key elt)
    partitionUFM
    varEnvDomain :: forall elt. VarEnv elt -> UnVarSet
    varEnvDomain     = UniqFM Var elt -> UnVarSet
    forall {k} (key :: k) elt. UniqFM key elt -> UnVarSet
    domUFMUnVarSet
    nonDetStrictFoldVarEnv_Directly :: forall a r. (Unique -> a -> r -> r) -> r -> VarEnv a -> r
    nonDetStrictFoldVarEnv_Directly = (Unique -> a -> r -> r) -> r -> UniqFM Var a -> r
    forall {k} elt a (key :: k).
    (Unique -> elt -> a -> a) -> a -> UniqFM key elt -> a
    nonDetStrictFoldUFM_Directly

    restrictVarEnv :: forall a. VarEnv a -> VarSet -> VarEnv a
    restrictVarEnv VarEnv a
    env VarSet
    vs = (Unique -> a -> Bool) -> VarEnv a -> VarEnv a
    forall {k} elt (key :: k).
    (Unique -> elt -> Bool) -> UniqFM key elt -> UniqFM key elt
    filterUFM_Directly Unique -> a -> Bool
    keep VarEnv a
    env
      where
        keep :: Unique -> a -> Bool
    keep Unique
    u a
    _ = Unique
    u Unique -> VarSet -> Bool
    `elemVarSetByKey` VarSet
    vs

    zipVarEnv :: forall a. [Var] -> [a] -> VarEnv a
    zipVarEnv [Var]
    tyvars [a]
    tys   = [(Var, a)] -> VarEnv a
    forall a. [(Var, a)] -> VarEnv a
    mkVarEnv (String -> [Var] -> [a] -> [(Var, a)]
    forall a b. HasDebugCallStack => String -> [a] -> [b] -> [(a, b)]
    zipEqual String
    "zipVarEnv" [Var]
    tyvars [a]
    tys)
    lookupVarEnv_NF :: forall a. VarEnv a -> Var -> a
    lookupVarEnv_NF VarEnv a
    env Var
    id = case VarEnv a -> Var -> Maybe a
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv VarEnv a
    env Var
    id of
                             Just a
    xx -> a
    xx
                             Maybe a
    Nothing -> String -> a
    forall a. HasCallStack => String -> a
    panic String
    "lookupVarEnv_NF: Nothing"

    {-
    @modifyVarEnv@: Look up a thing in the VarEnv,
    then mash it with the modify function, and put it back.
    -}

    modifyVarEnv :: forall a. (a -> a) -> VarEnv a -> Var -> VarEnv a
    modifyVarEnv a -> a
    mangle_fn VarEnv a
    env Var
    key
      = case (VarEnv a -> Var -> Maybe a
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv VarEnv a
    env Var
    key) of
          Maybe a
    Nothing -> VarEnv a
    env
          Just a
    xx -> VarEnv a -> Var -> a -> VarEnv a
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv VarEnv a
    env Var
    key (a -> a
    mangle_fn a
    xx)

    modifyVarEnv_Directly :: (a -> a) -> UniqFM key a -> Unique -> UniqFM key a
    modifyVarEnv_Directly :: forall {k} a (key :: k).
    (a -> a) -> UniqFM key a -> Unique -> UniqFM key a
    modifyVarEnv_Directly a -> a
    mangle_fn UniqFM key a
    env Unique
    key
      = case (UniqFM key a -> Unique -> Maybe a
    forall {k} (key :: k) elt. UniqFM key elt -> Unique -> Maybe elt
    lookupUFM_Directly UniqFM key a
    env Unique
    key) of
          Maybe a
    Nothing -> UniqFM key a
    env
          Just a
    xx -> UniqFM key a -> Unique -> a -> UniqFM key a
    forall {k} (key :: k) elt.
    UniqFM key elt -> Unique -> elt -> UniqFM key elt
    addToUFM_Directly UniqFM key a
    env Unique
    key (a -> a
    mangle_fn a
    xx)

    {-
    ************************************************************************
    *                                                                      *
       Deterministic VarEnv (DVarEnv)
    *                                                                      *
    ************************************************************************
    -}
    -- See Note [Deterministic UniqFM] in GHC.Types.Unique.DFM for explanation why we need
    -- DVarEnv.

    -- | Deterministic Variable Environment
    type DVarEnv elt = UniqDFM Var elt

    -- | Deterministic Identifier Environment
    -- Sadly not always indexed by Id, but it is in the common case.
    type DIdEnv elt = UniqDFM Var elt

    -- | Deterministic Type Variable Environment
    type DTyVarEnv elt = UniqDFM TyVar elt

    emptyDVarEnv :: DVarEnv a
    emptyDVarEnv :: forall a. DVarEnv a
    emptyDVarEnv = UniqDFM Var a
    forall {k} (key :: k) elt. UniqDFM key elt
    emptyUDFM

    dVarEnvElts :: DVarEnv a -> [a]
    dVarEnvElts :: forall a. DVarEnv a -> [a]
    dVarEnvElts = UniqDFM Var a -> [a]
    forall {k} (key :: k) elt. UniqDFM key elt -> [elt]
    eltsUDFM

    mkDVarEnv :: [(Var, a)] -> DVarEnv a
    mkDVarEnv :: forall a. [(Var, a)] -> DVarEnv a
    mkDVarEnv = [(Var, a)] -> UniqDFM Var a
    forall key elt. Uniquable key => [(key, elt)] -> UniqDFM key elt
    listToUDFM

    extendDVarEnv :: DVarEnv a -> Var -> a -> DVarEnv a
    extendDVarEnv :: forall a. DVarEnv a -> Var -> a -> DVarEnv a
    extendDVarEnv = UniqDFM Var a -> Var -> a -> UniqDFM Var a
    forall key elt.
    Uniquable key =>
    UniqDFM key elt -> key -> elt -> UniqDFM key elt
    addToUDFM

    minusDVarEnv :: DVarEnv a -> DVarEnv a' -> DVarEnv a
    minusDVarEnv :: forall a a'. DVarEnv a -> DVarEnv a' -> DVarEnv a
    minusDVarEnv = UniqDFM Var a -> UniqDFM Var a' -> UniqDFM Var a
    forall {k} (key :: k) elt1 elt2.
    UniqDFM key elt1 -> UniqDFM key elt2 -> UniqDFM key elt1
    minusUDFM

    lookupDVarEnv :: DVarEnv a -> Var -> Maybe a
    lookupDVarEnv :: forall a. DVarEnv a -> Var -> Maybe a
    lookupDVarEnv = UniqDFM Var a -> Var -> Maybe a
    forall key elt.
    Uniquable key =>
    UniqDFM key elt -> key -> Maybe elt
    lookupUDFM

    foldDVarEnv :: (a -> b -> b) -> b -> DVarEnv a -> b
    foldDVarEnv :: forall a b. (a -> b -> b) -> b -> DVarEnv a -> b
    foldDVarEnv = (a -> b -> b) -> b -> UniqDFM Var a -> b
    forall {k} elt a (key :: k).
    (elt -> a -> a) -> a -> UniqDFM key elt -> a
    foldUDFM

    -- See Note [Deterministic UniqFM] to learn about nondeterminism.
    -- If you use this please provide a justification why it doesn't introduce
    -- nondeterminism.
    nonDetStrictFoldDVarEnv :: (a -> b -> b) -> b -> DVarEnv a -> b
    nonDetStrictFoldDVarEnv :: forall a b. (a -> b -> b) -> b -> DVarEnv a -> b
    nonDetStrictFoldDVarEnv = (a -> b -> b) -> b -> UniqDFM Var a -> b
    forall {k} elt a (key :: k).
    (elt -> a -> a) -> a -> UniqDFM key elt -> a
    nonDetStrictFoldUDFM

    mapDVarEnv :: (a -> b) -> DVarEnv a -> DVarEnv b
    mapDVarEnv :: forall a b. (a -> b) -> DVarEnv a -> DVarEnv b
    mapDVarEnv = (a -> b) -> UniqDFM Var a -> UniqDFM Var b
    forall {k} elt1 elt2 (key :: k).
    (elt1 -> elt2) -> UniqDFM key elt1 -> UniqDFM key elt2
    mapUDFM

    filterDVarEnv      :: (a -> Bool) -> DVarEnv a -> DVarEnv a
    filterDVarEnv :: forall a. (a -> Bool) -> DVarEnv a -> DVarEnv a
    filterDVarEnv = (a -> Bool) -> UniqDFM Var a -> UniqDFM Var a
    forall {k} elt (key :: k).
    (elt -> Bool) -> UniqDFM key elt -> UniqDFM key elt
    filterUDFM

    alterDVarEnv :: (Maybe a -> Maybe a) -> DVarEnv a -> Var -> DVarEnv a
    alterDVarEnv :: forall a. (Maybe a -> Maybe a) -> DVarEnv a -> Var -> DVarEnv a
    alterDVarEnv = (Maybe a -> Maybe a) -> UniqDFM Var a -> Var -> UniqDFM Var a
    forall key elt.
    Uniquable key =>
    (Maybe elt -> Maybe elt)
    -> UniqDFM key elt -> key -> UniqDFM key elt
    alterUDFM

    plusDVarEnv :: DVarEnv a -> DVarEnv a -> DVarEnv a
    plusDVarEnv :: forall a. DVarEnv a -> DVarEnv a -> DVarEnv a
    plusDVarEnv = UniqDFM Var a -> UniqDFM Var a -> UniqDFM Var a
    forall {k} (key :: k) elt.
    UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
    plusUDFM

    plusDVarEnv_C :: (a -> a -> a) -> DVarEnv a -> DVarEnv a -> DVarEnv a
    plusDVarEnv_C :: forall a. (a -> a -> a) -> DVarEnv a -> DVarEnv a -> DVarEnv a
    plusDVarEnv_C = (a -> a -> a) -> UniqDFM Var a -> UniqDFM Var a -> UniqDFM Var a
    forall {k} elt (key :: k).
    (elt -> elt -> elt)
    -> UniqDFM key elt -> UniqDFM key elt -> UniqDFM key elt
    plusUDFM_C

    unitDVarEnv :: Var -> a -> DVarEnv a
    unitDVarEnv :: forall a. Var -> a -> DVarEnv a
    unitDVarEnv = Var -> a -> UniqDFM Var a
    forall key elt. Uniquable key => key -> elt -> UniqDFM key elt
    unitUDFM

    delDVarEnv :: DVarEnv a -> Var -> DVarEnv a
    delDVarEnv :: forall a. DVarEnv a -> Var -> DVarEnv a
    delDVarEnv = UniqDFM Var a -> Var -> UniqDFM Var a
    forall key elt.
    Uniquable key =>
    UniqDFM key elt -> key -> UniqDFM key elt
    delFromUDFM

    delDVarEnvList :: DVarEnv a -> [Var] -> DVarEnv a
    delDVarEnvList :: forall a. DVarEnv a -> [Var] -> DVarEnv a
    delDVarEnvList = UniqDFM Var a -> [Var] -> UniqDFM Var a
    forall key elt.
    Uniquable key =>
    UniqDFM key elt -> [key] -> UniqDFM key elt
    delListFromUDFM

    isEmptyDVarEnv :: DVarEnv a -> Bool
    isEmptyDVarEnv :: forall a. DVarEnv a -> Bool
    isEmptyDVarEnv = UniqDFM Var a -> Bool
    forall {k} (key :: k) elt. UniqDFM key elt -> Bool
    isNullUDFM

    elemDVarEnv :: Var -> DVarEnv a -> Bool
    elemDVarEnv :: forall a. Var -> DVarEnv a -> Bool
    elemDVarEnv = Var -> UniqDFM Var a -> Bool
    forall key elt. Uniquable key => key -> UniqDFM key elt -> Bool
    elemUDFM

    extendDVarEnv_C :: (a -> a -> a) -> DVarEnv a -> Var -> a -> DVarEnv a
    extendDVarEnv_C :: forall a. (a -> a -> a) -> DVarEnv a -> Var -> a -> DVarEnv a
    extendDVarEnv_C = (a -> a -> a) -> UniqDFM Var a -> Var -> a -> UniqDFM Var a
    forall key elt.
    Uniquable key =>
    (elt -> elt -> elt)
    -> UniqDFM key elt -> key -> elt -> UniqDFM key elt
    addToUDFM_C

    modifyDVarEnv :: (a -> a) -> DVarEnv a -> Var -> DVarEnv a
    modifyDVarEnv :: forall a. (a -> a) -> DVarEnv a -> Var -> DVarEnv a
    modifyDVarEnv a -> a
    mangle_fn DVarEnv a
    env Var
    key
      = case (DVarEnv a -> Var -> Maybe a
    forall a. DVarEnv a -> Var -> Maybe a
    lookupDVarEnv DVarEnv a
    env Var
    key) of
          Maybe a
    Nothing -> DVarEnv a
    env
          Just a
    xx -> DVarEnv a -> Var -> a -> DVarEnv a
    forall a. DVarEnv a -> Var -> a -> DVarEnv a
    extendDVarEnv DVarEnv a
    env Var
    key (a -> a
    mangle_fn a
    xx)

    partitionDVarEnv :: (a -> Bool) -> DVarEnv a -> (DVarEnv a, DVarEnv a)
    partitionDVarEnv :: forall a. (a -> Bool) -> DVarEnv a -> (DVarEnv a, DVarEnv a)
    partitionDVarEnv = (a -> Bool) -> UniqDFM Var a -> (UniqDFM Var a, UniqDFM Var a)
    forall {k} elt (key :: k).
    (elt -> Bool)
    -> UniqDFM key elt -> (UniqDFM key elt, UniqDFM key elt)
    partitionUDFM

    extendDVarEnvList :: DVarEnv a -> [(Var, a)] -> DVarEnv a
    extendDVarEnvList :: forall a. DVarEnv a -> [(Var, a)] -> DVarEnv a
    extendDVarEnvList = UniqDFM Var a -> [(Var, a)] -> UniqDFM Var a
    forall key elt.
    Uniquable key =>
    UniqDFM key elt -> [(key, elt)] -> UniqDFM key elt
    addListToUDFM

    anyDVarEnv :: (a -> Bool) -> DVarEnv a -> Bool
    anyDVarEnv :: forall a. (a -> Bool) -> DVarEnv a -> Bool
    anyDVarEnv = (a -> Bool) -> UniqDFM Var a -> Bool
    forall {k} elt (key :: k). (elt -> Bool) -> UniqDFM key elt -> Bool
    anyUDFM