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

    \section[CoreRules]{Rewrite rules}
    -}

    -- | Functions for collecting together and applying rewrite rules to a module.
    -- The 'CoreRule' datatype itself is declared elsewhere.
    module GHC.Core.Rules (
            -- ** Looking up rules
            lookupRule, matchExprs,

            -- ** RuleBase, RuleEnv
            RuleBase, RuleEnv(..), mkRuleEnv, emptyRuleEnv,
            updExternalPackageRules, addLocalRules, updLocalRules,
            emptyRuleBase, mkRuleBase, extendRuleBaseList,
            pprRuleBase,

            -- ** Checking rule applications
            ruleCheckProgram,

            -- ** Manipulating 'RuleInfo' rules
            extendRuleInfo, addRuleInfo,
            addIdSpecialisations, addRulesToId,

            -- ** RuleBase and RuleEnv

            -- * Misc. CoreRule helpers
            rulesOfBinds, getRules, pprRulesForUser,

            -- * Making rules
            mkRule, mkSpecRule, roughTopNames

        ) where

    import GHC.Prelude

    import GHC.Unit.Module   ( Module )
    import GHC.Unit.Module.Env
    import GHC.Unit.Module.ModGuts( ModGuts(..) )
    import GHC.Unit.Module.Deps( Dependencies(..) )

    import GHC.Driver.DynFlags( DynFlags )
    import GHC.Driver.Ppr( showSDoc )

    import GHC.Core         -- All of it
    import GHC.Core.Subst
    import GHC.Core.SimpleOpt ( exprIsLambda_maybe )
    import GHC.Core.FVs       ( exprFreeVars, bindFreeVars
                              , rulesFreeVarsDSet, orphNamesOfExprs )
    import GHC.Core.Utils     ( exprType, mkTick, mkTicks
                              , stripTicksTopT, stripTicksTopE
                              , isJoinBind, mkCastMCo )
    import GHC.Core.Ppr       ( pprRules )
    import GHC.Core.Unify as Unify ( ruleMatchTyKiX )
    import GHC.Core.Type as Type
       ( Type, extendTvSubst, extendCvSubst
       , substTy, getTyVar_maybe )
    import GHC.Core.TyCo.Ppr( pprParendType )
    import GHC.Core.Coercion as Coercion
    import GHC.Core.Tidy     ( tidyRules )
    import GHC.Core.Map.Expr ( eqCoreExpr )
    import GHC.Core.Opt.Arity( etaExpandToJoinPointRule )
    import GHC.Core.Make     ( mkCoreLams )
    import GHC.Core.Opt.OccurAnal( occurAnalyseExpr )

    import GHC.Tc.Utils.TcType  ( tcSplitTyConApp_maybe )
    import GHC.Builtin.Types    ( anyTypeOfKind )

    import GHC.Types.Id
    import GHC.Types.Id.Info ( RuleInfo( RuleInfo ) )
    import GHC.Types.Var
    import GHC.Types.Var.Env
    import GHC.Types.Var.Set
    import GHC.Types.Name    ( Name, NamedThing(..), nameIsLocalOrFrom )
    import GHC.Types.Name.Set
    import GHC.Types.Name.Env
    import GHC.Types.Name.Occurrence( occNameFS )
    import GHC.Types.Unique.FM
    import GHC.Types.Tickish
    import GHC.Types.Basic

    import GHC.Data.FastString
    import GHC.Data.Maybe
    import GHC.Data.Bag
    import GHC.Data.List.SetOps( hasNoDups )

    import GHC.Utils.FV( filterFV, fvVarSet )
    import GHC.Utils.Misc as Utils
    import GHC.Utils.Outputable
    import GHC.Utils.Panic
    import GHC.Utils.Constants (debugIsOn)

    import Data.List (sortBy, mapAccumL, isPrefixOf)
    import Data.Function    ( on )
    import Control.Monad    ( guard )

    {-
    Note [Overall plumbing for rules]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    * After the desugarer:
       - The ModGuts initially contains mg_rules :: [CoreRule] of
         locally-declared rules for imported Ids.
       - Locally-declared rules for locally-declared Ids are attached to
         the IdInfo for that Id.  See Note [Attach rules to local ids] in
         GHC.HsToCore.Binds

    * GHC.Iface.Tidy strips off all the rules from local Ids and adds them to
      mg_rules, so that the ModGuts has *all* the locally-declared rules.

    * The HomePackageTable contains a ModDetails for each home package
      module.  Each contains md_rules :: [CoreRule] of rules declared in
      that module.  The HomePackageTable grows as ghc --make does its
      up-sweep.  In batch mode (ghc -c), the HPT is empty; all imported modules
      are treated by the "external" route, discussed next, regardless of
      which package they come from.

    * The ExternalPackageState has a single eps_rule_base :: RuleBase for
      Ids in other packages.  This RuleBase simply grow monotonically, as
      ghc --make compiles one module after another.

      During simplification, interface files may get demand-loaded,
      as the simplifier explores the unfoldings for Ids it has in
      its hand.  (Via an unsafePerformIO; the EPS is really a cache.)
      That in turn may make the EPS rule-base grow.  In contrast, the
      HPT never grows in this way.

    * The result of all this is that during Core-to-Core optimisation
      there are four sources of rules:

        (a) Rules in the IdInfo of the Id they are a rule for.  These are
            easy: fast to look up, and if you apply a substitution then
            it'll be applied to the IdInfo as a matter of course.

        (b) Rules declared in this module for imported Ids, kept in the
            ModGuts. If you do a substitution, you'd better apply the
            substitution to these.  There are seldom many of these.

        (c) Rules declared in the HomePackageTable.  These never change.

        (d) Rules in the ExternalPackageTable. These can grow in response
            to lazy demand-loading of interfaces.

    * At the moment (c) is carried in a reader-monad way by the GHC.Core.Opt.Monad.
      The HomePackageTable doesn't have a single RuleBase because technically
      we should only be able to "see" rules "below" this module; so we
      generate a RuleBase for (c) by combining rules from all the modules
      "below" us.  That's why we can't just select the home-package RuleBase
      from HscEnv.

      [NB: we are inconsistent here.  We should do the same for external
      packages, but we don't.  Same for type-class instances.]

    * So in the outer simplifier loop (simplifyPgmIO), we combine (b & c) into a single
      RuleBase, reading
         (b) from the ModGuts,
         (c) from the GHC.Core.Opt.Monad, and
      just before doing rule matching we read
         (d) from its mutable variable
      and combine it with the results from (b & c).

      In a single simplifier run new rules can be added into the EPS so it matters
      to keep an up-to-date view of which rules have been loaded. For examples of
      where this went wrong and caused cryptic performance regressions
      see T19790 and !6735.

    ************************************************************************
    *                                                                      *
    \subsection[specialisation-IdInfo]{Specialisation info about an @Id@}
    *                                                                      *
    ************************************************************************

    A CoreRule holds details of one rule for an Id, which
    includes its specialisations.

    For example, if a rule for f is
       RULE "f" forall @a @b d. f @(List a) @b d = f' a b

    then when we find an application of f to matching types, we simply replace
    it by the matching RHS:
            f (List Int) Bool dict ===>  f' Int Bool
    All the stuff about how many dictionaries to discard, and what types
    to apply the specialised function to, are handled by the fact that the
    Rule contains a template for the result of the specialisation.
    -}

    mkRule :: Module -> Bool -> Bool -> RuleName -> Activation
           -> Name -> [CoreBndr] -> [CoreExpr] -> CoreExpr -> CoreRule
    -- ^ Used to make 'CoreRule' for an 'Id' defined in the module being
    -- compiled. See also 'GHC.Core.CoreRule'
    mkRule :: Module
    -> Bool
    -> Bool
    -> RuleName
    -> Activation
    -> Name
    -> [Var]
    -> [CoreExpr]
    -> CoreExpr
    -> CoreRule
    mkRule Module
    this_mod Bool
    is_auto Bool
    is_local RuleName
    name Activation
    act Name
    fn [Var]
    bndrs [CoreExpr]
    args CoreExpr
    rhs
      = Rule { ru_name :: RuleName
    ru_name   = RuleName
    name
             , ru_act :: Activation
    ru_act    = Activation
    act
             , ru_fn :: Name
    ru_fn     = Name
    fn
             , ru_bndrs :: [Var]
    ru_bndrs  = [Var]
    bndrs
             , ru_args :: [CoreExpr]
    ru_args   = [CoreExpr]
    args
             , ru_rhs :: CoreExpr
    ru_rhs    = CoreExpr -> CoreExpr
    occurAnalyseExpr CoreExpr
    rhs
                           -- See Note [OccInfo in unfoldings and rules]
             , ru_rough :: [Maybe Name]
    ru_rough  = [CoreExpr] -> [Maybe Name]
    roughTopNames [CoreExpr]
    args
             , ru_origin :: Module
    ru_origin = Module
    this_mod
             , ru_orphan :: IsOrphan
    ru_orphan = IsOrphan
    orph
             , ru_auto :: Bool
    ru_auto   = Bool
    is_auto
             , ru_local :: Bool
    ru_local  = Bool
    is_local }
      where
            -- Compute orphanhood.  See Note [Orphans] in GHC.Core.InstEnv
            -- A rule is an orphan only if none of the variables
            -- mentioned on its left-hand side are locally defined
        lhs_names :: NameSet
    lhs_names = NameSet -> Name -> NameSet
    extendNameSet ([CoreExpr] -> NameSet
    orphNamesOfExprs [CoreExpr]
    args) Name
    fn

            -- Since rules get eventually attached to one of the free names
            -- from the definition when compiling the ABI hash, we should make
            -- it deterministic. This chooses the one with minimal OccName
            -- as opposed to uniq value.
        local_lhs_names :: NameSet
    local_lhs_names = (Name -> Bool) -> NameSet -> NameSet
    filterNameSet (Module -> Name -> Bool
    nameIsLocalOrFrom Module
    this_mod) NameSet
    lhs_names
        orph :: IsOrphan
    orph = NameSet -> IsOrphan
    chooseOrphanAnchor NameSet
    local_lhs_names

    --------------
    mkSpecRule :: DynFlags -> Module -> Bool -> Activation -> SDoc
               -> Id -> [CoreBndr] -> [CoreExpr] -> CoreExpr -> CoreRule
    -- Make a specialisation rule, for Specialise or SpecConstr
    mkSpecRule :: DynFlags
    -> Module
    -> Bool
    -> Activation
    -> SDoc
    -> Var
    -> [Var]
    -> [CoreExpr]
    -> CoreExpr
    -> CoreRule
    mkSpecRule DynFlags
    dflags Module
    this_mod Bool
    is_auto Activation
    inl_act SDoc
    herald Var
    fn [Var]
    bndrs [CoreExpr]
    args CoreExpr
    rhs
      = case Var -> JoinPointHood
    idJoinPointHood Var
    fn of
          JoinPoint Arity
    join_arity -> Arity -> CoreRule -> CoreRule
    etaExpandToJoinPointRule Arity
    join_arity CoreRule
    rule
          JoinPointHood
    NotJoinPoint         -> CoreRule
    rule
      where
        rule :: CoreRule
    rule = Module
    -> Bool
    -> Bool
    -> RuleName
    -> Activation
    -> Name
    -> [Var]
    -> [CoreExpr]
    -> CoreExpr
    -> CoreRule
    mkRule Module
    this_mod Bool
    is_auto Bool
    is_local
                      RuleName
    rule_name
                      Activation
    inl_act       -- Note [Auto-specialisation and RULES]
                      (Var -> Name
    idName Var
    fn)
                      [Var]
    bndrs [CoreExpr]
    args CoreExpr
    rhs

        is_local :: Bool
    is_local = Var -> Bool
    isLocalId Var
    fn
        rule_name :: RuleName
    rule_name = DynFlags -> SDoc -> Var -> [CoreExpr] -> RuleName
    mkSpecRuleName DynFlags
    dflags SDoc
    herald Var
    fn [CoreExpr]
    args

    mkSpecRuleName :: DynFlags -> SDoc -> Id -> [CoreExpr] -> FastString
    mkSpecRuleName :: DynFlags -> SDoc -> Var -> [CoreExpr] -> RuleName
    mkSpecRuleName DynFlags
    dflags SDoc
    herald Var
    fn [CoreExpr]
    args
      = String -> RuleName
    mkFastString (String -> RuleName) -> String -> RuleName
    forall a b. (a -> b) -> a -> b
    $ DynFlags -> SDoc -> String
    showSDoc DynFlags
    dflags (SDoc -> String) -> SDoc -> String
    forall a b. (a -> b) -> a -> b
    $
        SDoc
    herald SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> RuleName -> SDoc
    forall doc. IsLine doc => RuleName -> doc
    ftext (OccName -> RuleName
    occNameFS (Var -> OccName
    forall a. NamedThing a => a -> OccName
    getOccName Var
    fn))
                         -- This name ends up in interface files, so use occNameFS.
                         -- Otherwise uniques end up there, making builds
                         -- less deterministic (See #4012 comment:61 ff)
               SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> [SDoc] -> SDoc
    forall doc. IsLine doc => [doc] -> doc
    hsep ((CoreExpr -> Maybe SDoc) -> [CoreExpr] -> [SDoc]
    forall a b. (a -> Maybe b) -> [a] -> [b]
    mapMaybe CoreExpr -> Maybe SDoc
    ppr_call_key_ty [CoreExpr]
    args)
      where
        ppr_call_key_ty :: CoreExpr -> Maybe SDoc
        ppr_call_key_ty :: CoreExpr -> Maybe SDoc
    ppr_call_key_ty (Type Kind
    ty) = case Kind -> Maybe Var
    getTyVar_maybe Kind
    ty of
                                      Just {} -> SDoc -> Maybe SDoc
    forall a. a -> Maybe a
    Just (String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "@_")
                                      Maybe Var
    Nothing -> SDoc -> Maybe SDoc
    forall a. a -> Maybe a
    Just (SDoc -> Maybe SDoc) -> SDoc -> Maybe SDoc
    forall a b. (a -> b) -> a -> b
    $ Char -> SDoc
    forall doc. IsLine doc => Char -> doc
    char Char
    '@' SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <> Kind -> SDoc
    pprParendType Kind
    ty
        ppr_call_key_ty CoreExpr
    _ = Maybe SDoc
    forall a. Maybe a
    Nothing

    --------------
    roughTopNames :: [CoreExpr] -> [Maybe Name]
    -- ^ Find the \"top\" free names of several expressions.
    -- Such names are either:
    --
    -- 1. The function finally being applied to in an application chain
    --    (if that name is a GlobalId: see "GHC.Types.Var#globalvslocal"), or
    --
    -- 2. The 'TyCon' if the expression is a 'Type'
    --
    -- This is used for the fast-match-check for rules;
    --      if the top names don't match, the rest can't
    roughTopNames :: [CoreExpr] -> [Maybe Name]
    roughTopNames [CoreExpr]
    args = (CoreExpr -> Maybe Name) -> [CoreExpr] -> [Maybe Name]
    forall a b. (a -> b) -> [a] -> [b]
    map CoreExpr -> Maybe Name
    roughTopName [CoreExpr]
    args

    roughTopName :: CoreExpr -> Maybe Name
    roughTopName :: CoreExpr -> Maybe Name
    roughTopName (Type Kind
    ty) = case HasDebugCallStack => Kind -> Maybe (TyCon, [Kind])
    Kind -> Maybe (TyCon, [Kind])
    tcSplitTyConApp_maybe Kind
    ty of
                                   Just (TyCon
    tc,[Kind]
    _) -> Name -> Maybe Name
    forall a. a -> Maybe a
    Just (TyCon -> Name
    forall a. NamedThing a => a -> Name
    getName TyCon
    tc)
                                   Maybe (TyCon, [Kind])
    Nothing     -> Maybe Name
    forall a. Maybe a
    Nothing
    roughTopName (Coercion Coercion
    _) = Maybe Name
    forall a. Maybe a
    Nothing
    roughTopName (App CoreExpr
    f CoreExpr
    _) = CoreExpr -> Maybe Name
    roughTopName CoreExpr
    f
    roughTopName (Var Var
    f)   | Var -> Bool
    isGlobalId Var
    f   -- Note [Care with roughTopName]
                           , Var -> Bool
    isDataConWorkId Var
    f Bool -> Bool -> Bool
    || Var -> Arity
    idArity Var
    f Arity -> Arity -> Bool
    forall a. Ord a => a -> a -> Bool
    > Arity
    0
                           = Name -> Maybe Name
    forall a. a -> Maybe a
    Just (Var -> Name
    idName Var
    f)
    roughTopName (Tick CoreTickish
    t CoreExpr
    e) | CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable CoreTickish
    t
                            = CoreExpr -> Maybe Name
    roughTopName CoreExpr
    e
    roughTopName CoreExpr
    _ = Maybe Name
    forall a. Maybe a
    Nothing

    ruleCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool
    -- ^ @ruleCantMatch tpl actual@ returns True only if @actual@
    -- definitely can't match @tpl@ by instantiating @tpl@.
    -- It's only a one-way match; unlike instance matching we
    -- don't consider unification.
    --
    -- Notice that [_$_]
    --      @ruleCantMatch [Nothing] [Just n2] = False@
    --      Reason: a template variable can be instantiated by a constant
    -- Also:
    --      @ruleCantMatch [Just n1] [Nothing] = False@
    --      Reason: a local variable @v@ in the actuals might [_$_]

    ruleCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool
    ruleCantMatch (Just Name
    n1 : [Maybe Name]
    ts) (Just Name
    n2 : [Maybe Name]
    as) = Name
    n1 Name -> Name -> Bool
    forall a. Eq a => a -> a -> Bool
    /= Name
    n2 Bool -> Bool -> Bool
    || [Maybe Name] -> [Maybe Name] -> Bool
    ruleCantMatch [Maybe Name]
    ts [Maybe Name]
    as
    ruleCantMatch (Maybe Name
    _       : [Maybe Name]
    ts) (Maybe Name
    _       : [Maybe Name]
    as) = [Maybe Name] -> [Maybe Name] -> Bool
    ruleCantMatch [Maybe Name]
    ts [Maybe Name]
    as
    ruleCantMatch [Maybe Name]
    _              [Maybe Name]
    _              = Bool
    False

    {-
    Note [Care with roughTopName]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Consider this
        module M where { x = a:b }
        module N where { ...f x...
                         RULE f (p:q) = ... }
    You'd expect the rule to match, because the matcher can
    look through the unfolding of 'x'.  So we must avoid roughTopName
    returning 'M.x' for the call (f x), or else it'll say "can't match"
    and we won't even try!!

    However, suppose we have
             RULE g (M.h x) = ...
             foo = ...(g (M.k v))....
    where k is a *function* exported by M.  We never really match
    functions (lambdas) except by name, so in this case it seems like
    a good idea to treat 'M.k' as a roughTopName of the call.
    -}

    pprRulesForUser :: [CoreRule] -> SDoc
    -- (a) tidy the rules
    -- (b) sort them into order based on the rule name
    -- (c) suppress uniques (unless -dppr-debug is on)
    -- This combination makes the output stable so we can use in testing
    -- It's here rather than in GHC.Core.Ppr because it calls tidyRules
    pprRulesForUser :: [CoreRule] -> SDoc
    pprRulesForUser [CoreRule]
    rules
      = PprStyle -> SDoc -> SDoc
    withPprStyle PprStyle
    defaultUserStyle (SDoc -> SDoc) -> SDoc -> SDoc
    forall a b. (a -> b) -> a -> b
    $
        [CoreRule] -> SDoc
    pprRules ([CoreRule] -> SDoc) -> [CoreRule] -> SDoc
    forall a b. (a -> b) -> a -> b
    $
        (CoreRule -> CoreRule -> Ordering) -> [CoreRule] -> [CoreRule]
    forall a. (a -> a -> Ordering) -> [a] -> [a]
    sortBy (RuleName -> RuleName -> Ordering
    lexicalCompareFS (RuleName -> RuleName -> Ordering)
    -> (CoreRule -> RuleName) -> CoreRule -> CoreRule -> Ordering
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` CoreRule -> RuleName
    ruleName) ([CoreRule] -> [CoreRule]) -> [CoreRule] -> [CoreRule]
    forall a b. (a -> b) -> a -> b
    $
        TidyEnv -> [CoreRule] -> [CoreRule]
    tidyRules TidyEnv
    emptyTidyEnv [CoreRule]
    rules

    {-
    ************************************************************************
    *                                                                      *
                    RuleInfo: the rules in an IdInfo
    *                                                                      *
    ************************************************************************
    -}

    extendRuleInfo :: RuleInfo -> [CoreRule] -> RuleInfo
    extendRuleInfo :: RuleInfo -> [CoreRule] -> RuleInfo
    extendRuleInfo (RuleInfo [CoreRule]
    rs1 DVarSet
    fvs1) [CoreRule]
    rs2
      = [CoreRule] -> DVarSet -> RuleInfo
    RuleInfo ([CoreRule]
    rs2 [CoreRule] -> [CoreRule] -> [CoreRule]
    forall a. [a] -> [a] -> [a]
    ++ [CoreRule]
    rs1) ([CoreRule] -> DVarSet
    rulesFreeVarsDSet [CoreRule]
    rs2 DVarSet -> DVarSet -> DVarSet
    `unionDVarSet` DVarSet
    fvs1)

    addRuleInfo :: RuleInfo -> RuleInfo -> RuleInfo
    addRuleInfo :: RuleInfo -> RuleInfo -> RuleInfo
    addRuleInfo (RuleInfo [CoreRule]
    rs1 DVarSet
    fvs1) (RuleInfo [CoreRule]
    rs2 DVarSet
    fvs2)
      = [CoreRule] -> DVarSet -> RuleInfo
    RuleInfo ([CoreRule]
    rs1 [CoreRule] -> [CoreRule] -> [CoreRule]
    forall a. [a] -> [a] -> [a]
    ++ [CoreRule]
    rs2) (DVarSet
    fvs1 DVarSet -> DVarSet -> DVarSet
    `unionDVarSet` DVarSet
    fvs2)

    addIdSpecialisations :: Id -> [CoreRule] -> Id
    addIdSpecialisations :: Var -> [CoreRule] -> Var
    addIdSpecialisations Var
    id [CoreRule]
    rules
      | [CoreRule] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [CoreRule]
    rules
      = Var
    id
      | Bool
    otherwise
      = Var -> RuleInfo -> Var
    setIdSpecialisation Var
    id (RuleInfo -> Var) -> RuleInfo -> Var
    forall a b. (a -> b) -> a -> b
    $
        RuleInfo -> [CoreRule] -> RuleInfo
    extendRuleInfo (Var -> RuleInfo
    idSpecialisation Var
    id) [CoreRule]
    rules

    addRulesToId :: RuleBase -> Id -> Id
    -- Add rules in the RuleBase to the rules in the Id
    addRulesToId :: RuleBase -> Var -> Var
    addRulesToId RuleBase
    rule_base Var
    bndr
      | Just [CoreRule]
    rules <- RuleBase -> Name -> Maybe [CoreRule]
    forall a. NameEnv a -> Name -> Maybe a
    lookupNameEnv RuleBase
    rule_base (Var -> Name
    idName Var
    bndr)
      = Var
    bndr Var -> [CoreRule] -> Var
    `addIdSpecialisations` [CoreRule]
    rules
      | Bool
    otherwise
      = Var
    bndr

    -- | Gather all the rules for locally bound identifiers from the supplied bindings
    rulesOfBinds :: [CoreBind] -> [CoreRule]
    rulesOfBinds :: [CoreBind] -> [CoreRule]
    rulesOfBinds [CoreBind]
    binds = (CoreBind -> [CoreRule]) -> [CoreBind] -> [CoreRule]
    forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
    concatMap ((Var -> [CoreRule]) -> [Var] -> [CoreRule]
    forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
    concatMap Var -> [CoreRule]
    idCoreRules ([Var] -> [CoreRule])
    -> (CoreBind -> [Var]) -> CoreBind -> [CoreRule]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CoreBind -> [Var]
    forall b. Bind b -> [b]
    bindersOf) [CoreBind]
    binds

    {-
    ************************************************************************
    *                                                                      *
                    RuleBase
    *                                                                      *
    ************************************************************************
    -}

    -- | Gathers a collection of 'CoreRule's. Maps (the name of) an 'Id' to its rules
    type RuleBase = NameEnv [CoreRule]
            -- The rules are unordered;
            -- we sort out any overlaps on lookup

    emptyRuleBase :: RuleBase
    emptyRuleBase :: RuleBase
    emptyRuleBase = RuleBase
    forall a. NameEnv a
    emptyNameEnv

    mkRuleBase :: [CoreRule] -> RuleBase
    mkRuleBase :: [CoreRule] -> RuleBase
    mkRuleBase [CoreRule]
    rules = RuleBase -> [CoreRule] -> RuleBase
    extendRuleBaseList RuleBase
    emptyRuleBase [CoreRule]
    rules

    extendRuleBaseList :: RuleBase -> [CoreRule] -> RuleBase
    extendRuleBaseList :: RuleBase -> [CoreRule] -> RuleBase
    extendRuleBaseList RuleBase
    rule_base [CoreRule]
    new_guys
      = (RuleBase -> CoreRule -> RuleBase)
    -> RuleBase -> [CoreRule] -> RuleBase
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' RuleBase -> CoreRule -> RuleBase
    extendRuleBase RuleBase
    rule_base [CoreRule]
    new_guys

    extendRuleBase :: RuleBase -> CoreRule -> RuleBase
    extendRuleBase :: RuleBase -> CoreRule -> RuleBase
    extendRuleBase RuleBase
    rule_base CoreRule
    rule
      = (CoreRule -> [CoreRule] -> [CoreRule])
    -> (CoreRule -> [CoreRule])
    -> RuleBase
    -> Name
    -> CoreRule
    -> RuleBase
    forall a b.
    (a -> b -> b) -> (a -> b) -> NameEnv b -> Name -> a -> NameEnv b
    extendNameEnv_Acc (:) CoreRule -> [CoreRule]
    forall a. a -> [a]
    Utils.singleton RuleBase
    rule_base (CoreRule -> Name
    ruleIdName CoreRule
    rule) CoreRule
    rule

    pprRuleBase :: RuleBase -> SDoc
    pprRuleBase :: RuleBase -> SDoc
    pprRuleBase RuleBase
    rules = RuleBase -> ([[CoreRule]] -> SDoc) -> SDoc
    forall {k} (key :: k) a. UniqFM key a -> ([a] -> SDoc) -> SDoc
    pprUFM RuleBase
    rules (([[CoreRule]] -> SDoc) -> SDoc) -> ([[CoreRule]] -> SDoc) -> SDoc
    forall a b. (a -> b) -> a -> b
    $ \[[CoreRule]]
    rss ->
      [SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat [ [CoreRule] -> SDoc
    pprRules (TidyEnv -> [CoreRule] -> [CoreRule]
    tidyRules TidyEnv
    emptyTidyEnv [CoreRule]
    rs)
           | [CoreRule]
    rs <- [[CoreRule]]
    rss ]

    -- | A full rule environment which we can apply rules from.  Like a 'RuleBase',
    -- but it also includes the set of visible orphans we use to filter out orphan
    -- rules which are not visible (even though we can see them...)
    -- See Note [Orphans] in GHC.Core
    data RuleEnv
        = RuleEnv { RuleEnv -> RuleBase
    re_local_rules   :: !RuleBase -- Rules from this module
                  , RuleEnv -> RuleBase
    re_home_rules    :: !RuleBase -- Rule from the home package
                                                  --   (excl this module)
                  , RuleEnv -> RuleBase
    re_eps_rules     :: !RuleBase -- Rules from other packages
                                                  --   see Note [External package rules]
                  , RuleEnv -> ModuleSet
    re_visible_orphs :: !ModuleSet
                  }

    mkRuleEnv :: ModGuts -> RuleBase -> RuleBase -> RuleEnv
    mkRuleEnv :: ModGuts -> RuleBase -> RuleBase -> RuleEnv
    mkRuleEnv (ModGuts { mg_module :: ModGuts -> Module
    mg_module = Module
    this_mod
                       , mg_deps :: ModGuts -> Dependencies
    mg_deps   = Dependencies
    deps
                       , mg_rules :: ModGuts -> [CoreRule]
    mg_rules  = [CoreRule]
    local_rules })
              RuleBase
    eps_rules RuleBase
    hpt_rules
      = RuleEnv { re_local_rules :: RuleBase
    re_local_rules   = [CoreRule] -> RuleBase
    mkRuleBase [CoreRule]
    local_rules
                , re_home_rules :: RuleBase
    re_home_rules    = RuleBase
    hpt_rules
                , re_eps_rules :: RuleBase
    re_eps_rules     = RuleBase
    eps_rules
                , re_visible_orphs :: ModuleSet
    re_visible_orphs = [Module] -> ModuleSet
    mkModuleSet [Module]
    vis_orphs }
      where
        vis_orphs :: [Module]
    vis_orphs = Module
    this_mod Module -> [Module] -> [Module]
    forall a. a -> [a] -> [a]
    : Dependencies -> [Module]
    dep_orphs Dependencies
    deps

    updExternalPackageRules :: RuleEnv -> RuleBase -> RuleEnv
    -- Completely over-ride the external rules in RuleEnv
    updExternalPackageRules :: RuleEnv -> RuleBase -> RuleEnv
    updExternalPackageRules RuleEnv
    rule_env RuleBase
    eps_rules
      = RuleEnv
    rule_env { re_eps_rules = eps_rules }

    updLocalRules :: RuleEnv -> [CoreRule] -> RuleEnv
    -- Completely over-ride the local rules in RuleEnv
    updLocalRules :: RuleEnv -> [CoreRule] -> RuleEnv
    updLocalRules RuleEnv
    rule_env [CoreRule]
    local_rules
      = RuleEnv
    rule_env { re_local_rules = mkRuleBase local_rules }

    addLocalRules :: RuleEnv -> [CoreRule] -> RuleEnv
    -- Add new local rules
    addLocalRules :: RuleEnv -> [CoreRule] -> RuleEnv
    addLocalRules RuleEnv
    rule_env [CoreRule]
    rules
      = RuleEnv
    rule_env { re_local_rules = extendRuleBaseList (re_local_rules rule_env) rules }

    emptyRuleEnv :: RuleEnv
    emptyRuleEnv :: RuleEnv
    emptyRuleEnv = RuleEnv { re_local_rules :: RuleBase
    re_local_rules   = RuleBase
    forall a. NameEnv a
    emptyNameEnv
                           , re_home_rules :: RuleBase
    re_home_rules    = RuleBase
    forall a. NameEnv a
    emptyNameEnv
                           , re_eps_rules :: RuleBase
    re_eps_rules     = RuleBase
    forall a. NameEnv a
    emptyNameEnv
                           , re_visible_orphs :: ModuleSet
    re_visible_orphs = ModuleSet
    emptyModuleSet }

    getRules :: RuleEnv -> Id -> [CoreRule]
    -- Given a RuleEnv and an Id, find the visible rules for that Id
    -- See Note [Where rules are found]
    --
    -- This function is quite heavily used, so it's worth trying to make it efficient
    getRules :: RuleEnv -> Var -> [CoreRule]
    getRules (RuleEnv { re_local_rules :: RuleEnv -> RuleBase
    re_local_rules   = RuleBase
    local_rule_base
                      , re_home_rules :: RuleEnv -> RuleBase
    re_home_rules    = RuleBase
    home_rule_base
                      , re_eps_rules :: RuleEnv -> RuleBase
    re_eps_rules     = RuleBase
    eps_rule_base
                      , re_visible_orphs :: RuleEnv -> ModuleSet
    re_visible_orphs = ModuleSet
    orphs }) Var
    fn

      | Just {} <- Var -> Maybe DataCon
    isDataConId_maybe Var
    fn   -- Short cut for data constructor workers
      = []                                -- and wrappers, which never have any rules

      | Just ExportFlag
    export_flag <- Var -> Maybe ExportFlag
    isLocalId_maybe Var
    fn
      = -- LocalIds can't have rules in the local_rule_base (used for imported fns)
        -- nor external packages; but there can (just) be rules in another module
        -- in the home package, if it is exported
        case ExportFlag
    export_flag of
          ExportFlag
    NotExported -> Var -> [CoreRule]
    idCoreRules Var
    fn
          ExportFlag
    Exported -> case RuleBase -> [CoreRule]
    get RuleBase
    home_rule_base of
              []           -> Var -> [CoreRule]
    idCoreRules Var
    fn
              [CoreRule]
    home_rules   -> [CoreRule] -> [CoreRule]
    drop_orphs [CoreRule]
    home_rules [CoreRule] -> [CoreRule] -> [CoreRule]
    forall a. [a] -> [a] -> [a]
    ++ Var -> [CoreRule]
    idCoreRules Var
    fn

      | Bool
    otherwise
      = -- This case expression is a fast path, to avoid calling the
        -- recursive (++) in the common case where there are no rules at all
        case (RuleBase -> [CoreRule]
    get RuleBase
    local_rule_base, RuleBase -> [CoreRule]
    get RuleBase
    home_rule_base, RuleBase -> [CoreRule]
    get RuleBase
    eps_rule_base) of
          ([], [], [])                         -> Var -> [CoreRule]
    idCoreRules Var
    fn
          ([CoreRule]
    local_rules, [CoreRule]
    home_rules, [CoreRule]
    eps_rules) -> [CoreRule]
    local_rules           [CoreRule] -> [CoreRule] -> [CoreRule]
    forall a. [a] -> [a] -> [a]
    ++
                                                  [CoreRule] -> [CoreRule]
    drop_orphs [CoreRule]
    home_rules [CoreRule] -> [CoreRule] -> [CoreRule]
    forall a. [a] -> [a] -> [a]
    ++
                                                  [CoreRule] -> [CoreRule]
    drop_orphs [CoreRule]
    eps_rules  [CoreRule] -> [CoreRule] -> [CoreRule]
    forall a. [a] -> [a] -> [a]
    ++
                                                  Var -> [CoreRule]
    idCoreRules Var
    fn
      where
        fn_name :: Name
    fn_name = Var -> Name
    idName Var
    fn
        drop_orphs :: [CoreRule] -> [CoreRule]
    drop_orphs [] = []  -- Fast path; avoid invoking recursive filter
        drop_orphs [CoreRule]
    xs = (CoreRule -> Bool) -> [CoreRule] -> [CoreRule]
    forall a. (a -> Bool) -> [a] -> [a]
    filter (ModuleSet -> CoreRule -> Bool
    ruleIsVisible ModuleSet
    orphs) [CoreRule]
    xs
        get :: RuleBase -> [CoreRule]
    get RuleBase
    rb = RuleBase -> Name -> Maybe [CoreRule]
    forall a. NameEnv a -> Name -> Maybe a
    lookupNameEnv RuleBase
    rb Name
    fn_name Maybe [CoreRule] -> [CoreRule] -> [CoreRule]
    forall a. Maybe a -> a -> a
    `orElse` []

    ruleIsVisible :: ModuleSet -> CoreRule -> Bool
    ruleIsVisible :: ModuleSet -> CoreRule -> Bool
    ruleIsVisible ModuleSet
    _ BuiltinRule{} = Bool
    True
    ruleIsVisible ModuleSet
    vis_orphs Rule { ru_orphan :: CoreRule -> IsOrphan
    ru_orphan = IsOrphan
    orph, ru_origin :: CoreRule -> Module
    ru_origin = Module
    origin }
        = IsOrphan -> Bool
    notOrphan IsOrphan
    orph Bool -> Bool -> Bool
    || Module
    origin Module -> ModuleSet -> Bool
    `elemModuleSet` ModuleSet
    vis_orphs

    {- Note [Where rules are found]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    The rules for an Id come from two places:
      (a) the ones it is born with, stored inside the Id itself (idCoreRules fn),
      (b) rules added in other modules, stored in the global RuleBase (imp_rules)

    It's tempting to think that
         - LocalIds have only (a)
         - non-LocalIds have only (b)

    but that isn't quite right:

         - PrimOps and ClassOps are born with a bunch of rules inside the Id,
           even when they are imported

         - The rules in GHC.Core.Opt.ConstantFold.builtinRules should be active even
           in the module defining the Id (when it's a LocalId), but
           the rules are kept in the global RuleBase

     Note [External package rules]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    In Note [Overall plumbing for rules], it is explained that the final
    RuleBase which we must consider is combined from 4 different sources.

    During simplifier runs, the fourth source of rules is constantly being updated
    as new interfaces are loaded into the EPS. Therefore just before we check to see
    if any rules match we get the EPS RuleBase and combine it with the existing RuleBase
    and then perform exactly 1 lookup into the new map.

    It is more efficient to avoid combining the environments and store the uncombined
    environments as we can instead perform 1 lookup into each environment and then combine
    the results.

    Essentially we use the identity:

    > lookupNameEnv n (plusNameEnv_C (++) rb1 rb2)
    >   = lookupNameEnv n rb1 ++ lookupNameEnv n rb2

    The latter being more efficient as we don't construct an intermediate
    map.
    -}

    {-
    ************************************************************************
    *                                                                      *
                            Matching
    *                                                                      *
    ************************************************************************
    -}

    -- | The main rule matching function. Attempts to apply all (active)
    -- supplied rules to this instance of an application in a given
    -- context, returning the rule applied and the resulting expression if
    -- successful.
    lookupRule :: RuleOpts -> InScopeEnv
               -> (Activation -> Bool)      -- When rule is active
               -> Id -- Function head
               -> [CoreExpr] -- Args
               -> [CoreRule] -- Rules
               -> Maybe (CoreRule, CoreExpr)

    -- See Note [Extra args in the target]
    -- See comments on matchRule
    lookupRule :: RuleOpts
    -> InScopeEnv
    -> (Activation -> Bool)
    -> Var
    -> [CoreExpr]
    -> [CoreRule]
    -> Maybe (CoreRule, CoreExpr)
    lookupRule RuleOpts
    opts rule_env :: InScopeEnv
    rule_env@(ISE InScopeSet
    in_scope IdUnfoldingFun
    _) Activation -> Bool
    is_active Var
    fn [CoreExpr]
    args [CoreRule]
    rules
      = -- pprTrace "lookupRule" (ppr fn <+> ppr args $$ ppr rules $$ ppr in_scope) $
        case [(CoreRule, CoreExpr)] -> [CoreRule] -> [(CoreRule, CoreExpr)]
    go [] [CoreRule]
    rules of
            []     -> Maybe (CoreRule, CoreExpr)
    forall a. Maybe a
    Nothing
            ((CoreRule, CoreExpr)
    m:[(CoreRule, CoreExpr)]
    ms) -> (CoreRule, CoreExpr) -> Maybe (CoreRule, CoreExpr)
    forall a. a -> Maybe a
    Just (InScopeSet
    -> (Var, [CoreExpr])
    -> (CoreRule, CoreExpr)
    -> [(CoreRule, CoreExpr)]
    -> (CoreRule, CoreExpr)
    findBest InScopeSet
    in_scope (Var
    fn,[CoreExpr]
    args') (CoreRule, CoreExpr)
    m [(CoreRule, CoreExpr)]
    ms)
      where
        rough_args :: [Maybe Name]
    rough_args = (CoreExpr -> Maybe Name) -> [CoreExpr] -> [Maybe Name]
    forall a b. (a -> b) -> [a] -> [b]
    map CoreExpr -> Maybe Name
    roughTopName [CoreExpr]
    args

        -- Strip ticks from arguments, see Note [Tick annotations in RULE
        -- matching]. We only collect ticks if a rule actually matches -
        -- this matters for performance tests.
        args' :: [CoreExpr]
    args' = (CoreExpr -> CoreExpr) -> [CoreExpr] -> [CoreExpr]
    forall a b. (a -> b) -> [a] -> [b]
    map ((CoreTickish -> Bool) -> CoreExpr -> CoreExpr
    forall b. (CoreTickish -> Bool) -> Expr b -> Expr b
    stripTicksTopE CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable) [CoreExpr]
    args
        ticks :: [CoreTickish]
    ticks = (CoreExpr -> [CoreTickish]) -> [CoreExpr] -> [CoreTickish]
    forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
    concatMap ((CoreTickish -> Bool) -> CoreExpr -> [CoreTickish]
    forall b. (CoreTickish -> Bool) -> Expr b -> [CoreTickish]
    stripTicksTopT CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable) [CoreExpr]
    args

        go :: [(CoreRule,CoreExpr)] -> [CoreRule] -> [(CoreRule,CoreExpr)]
        go :: [(CoreRule, CoreExpr)] -> [CoreRule] -> [(CoreRule, CoreExpr)]
    go [(CoreRule, CoreExpr)]
    ms [] = [(CoreRule, CoreExpr)]
    ms
        go [(CoreRule, CoreExpr)]
    ms (CoreRule
    r:[CoreRule]
    rs)
          | Just CoreExpr
    e <- RuleOpts
    -> InScopeEnv
    -> (Activation -> Bool)
    -> Var
    -> [CoreExpr]
    -> [Maybe Name]
    -> CoreRule
    -> Maybe CoreExpr
    matchRule RuleOpts
    opts InScopeEnv
    rule_env Activation -> Bool
    is_active Var
    fn [CoreExpr]
    args' [Maybe Name]
    rough_args CoreRule
    r
          = [(CoreRule, CoreExpr)] -> [CoreRule] -> [(CoreRule, CoreExpr)]
    go ((CoreRule
    r,[CoreTickish] -> CoreExpr -> CoreExpr
    mkTicks [CoreTickish]
    ticks CoreExpr
    e)(CoreRule, CoreExpr)
    -> [(CoreRule, CoreExpr)] -> [(CoreRule, CoreExpr)]
    forall a. a -> [a] -> [a]
    :[(CoreRule, CoreExpr)]
    ms) [CoreRule]
    rs
          | Bool
    otherwise
          = -- pprTrace "match failed" (ppr r $$ ppr args $$
            --   ppr [ (arg_id, unfoldingTemplate unf)
            --       | Var arg_id <- args
            --       , let unf = idUnfolding arg_id
            --       , isCheapUnfolding unf] )
            [(CoreRule, CoreExpr)] -> [CoreRule] -> [(CoreRule, CoreExpr)]
    go [(CoreRule, CoreExpr)]
    ms [CoreRule]
    rs

    findBest :: InScopeSet -> (Id, [CoreExpr])
             -> (CoreRule,CoreExpr) -> [(CoreRule,CoreExpr)] -> (CoreRule,CoreExpr)
    -- All these pairs matched the expression
    -- Return the pair the most specific rule
    -- The (fn,args) is just for overlap reporting

    findBest :: InScopeSet
    -> (Var, [CoreExpr])
    -> (CoreRule, CoreExpr)
    -> [(CoreRule, CoreExpr)]
    -> (CoreRule, CoreExpr)
    findBest InScopeSet
    _        (Var, [CoreExpr])
    _      (CoreRule
    rule,CoreExpr
    ans)   [] = (CoreRule
    rule,CoreExpr
    ans)
    findBest InScopeSet
    in_scope (Var, [CoreExpr])
    target (CoreRule
    rule1,CoreExpr
    ans1) ((CoreRule
    rule2,CoreExpr
    ans2):[(CoreRule, CoreExpr)]
    prs)
      | InScopeSet -> CoreRule -> CoreRule -> Bool
    isMoreSpecific InScopeSet
    in_scope CoreRule
    rule1 CoreRule
    rule2 = InScopeSet
    -> (Var, [CoreExpr])
    -> (CoreRule, CoreExpr)
    -> [(CoreRule, CoreExpr)]
    -> (CoreRule, CoreExpr)
    findBest InScopeSet
    in_scope (Var, [CoreExpr])
    target (CoreRule
    rule1,CoreExpr
    ans1) [(CoreRule, CoreExpr)]
    prs
      | InScopeSet -> CoreRule -> CoreRule -> Bool
    isMoreSpecific InScopeSet
    in_scope CoreRule
    rule2 CoreRule
    rule1 = InScopeSet
    -> (Var, [CoreExpr])
    -> (CoreRule, CoreExpr)
    -> [(CoreRule, CoreExpr)]
    -> (CoreRule, CoreExpr)
    findBest InScopeSet
    in_scope (Var, [CoreExpr])
    target (CoreRule
    rule2,CoreExpr
    ans2) [(CoreRule, CoreExpr)]
    prs
      | Bool
    debugIsOn = let pp_rule :: CoreRule -> SDoc
    pp_rule CoreRule
    rule
                          = SDoc -> SDoc -> SDoc
    forall doc. IsOutput doc => doc -> doc -> doc
    ifPprDebug (CoreRule -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr CoreRule
    rule)
                                       (SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc
    doubleQuotes (RuleName -> SDoc
    forall doc. IsLine doc => RuleName -> doc
    ftext (CoreRule -> RuleName
    ruleName CoreRule
    rule)))
                    in String -> SDoc -> (CoreRule, CoreExpr) -> (CoreRule, CoreExpr)
    forall a. String -> SDoc -> a -> a
    pprTrace String
    "Rules.findBest: rule overlap (Rule 1 wins)"
                             ([SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat [ SDoc -> SDoc
    forall doc. IsOutput doc => doc -> doc
    whenPprDebug (SDoc -> SDoc) -> SDoc -> SDoc
    forall a b. (a -> b) -> a -> b
    $
                                     String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Expression to match:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> Var -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Var
    fn
                                     SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> [SDoc] -> SDoc
    forall doc. IsLine doc => [doc] -> doc
    sep ((CoreExpr -> SDoc) -> [CoreExpr] -> [SDoc]
    forall a b. (a -> b) -> [a] -> [b]
    map CoreExpr -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr [CoreExpr]
    args)
                                   , String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Rule 1:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> CoreRule -> SDoc
    pp_rule CoreRule
    rule1
                                   , String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Rule 2:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> CoreRule -> SDoc
    pp_rule CoreRule
    rule2]) ((CoreRule, CoreExpr) -> (CoreRule, CoreExpr))
    -> (CoreRule, CoreExpr) -> (CoreRule, CoreExpr)
    forall a b. (a -> b) -> a -> b
    $
                    InScopeSet
    -> (Var, [CoreExpr])
    -> (CoreRule, CoreExpr)
    -> [(CoreRule, CoreExpr)]
    -> (CoreRule, CoreExpr)
    findBest InScopeSet
    in_scope (Var, [CoreExpr])
    target (CoreRule
    rule1,CoreExpr
    ans1) [(CoreRule, CoreExpr)]
    prs
      | Bool
    otherwise = InScopeSet
    -> (Var, [CoreExpr])
    -> (CoreRule, CoreExpr)
    -> [(CoreRule, CoreExpr)]
    -> (CoreRule, CoreExpr)
    findBest InScopeSet
    in_scope (Var, [CoreExpr])
    target (CoreRule
    rule1,CoreExpr
    ans1) [(CoreRule, CoreExpr)]
    prs
      where
        (Var
    fn,[CoreExpr]
    args) = (Var, [CoreExpr])
    target

    isMoreSpecific :: InScopeSet -> CoreRule -> CoreRule -> Bool
    -- The call (rule1 `isMoreSpecific` rule2)
    -- sees if rule2 can be instantiated to look like rule1
    -- See Note [isMoreSpecific]
    isMoreSpecific :: InScopeSet -> CoreRule -> CoreRule -> Bool
    isMoreSpecific InScopeSet
    _        (BuiltinRule {}) CoreRule
    _                = Bool
    False
    isMoreSpecific InScopeSet
    _        (Rule {})        (BuiltinRule {}) = Bool
    True
    isMoreSpecific InScopeSet
    in_scope (Rule { ru_bndrs :: CoreRule -> [Var]
    ru_bndrs = [Var]
    bndrs1, ru_args :: CoreRule -> [CoreExpr]
    ru_args = [CoreExpr]
    args1 })
                            (Rule { ru_bndrs :: CoreRule -> [Var]
    ru_bndrs = [Var]
    bndrs2, ru_args :: CoreRule -> [CoreExpr]
    ru_args = [CoreExpr]
    args2 })
      = Maybe (CoreExpr -> CoreExpr, [CoreExpr]) -> Bool
    forall a. Maybe a -> Bool
    isJust (InScopeEnv
    -> [Var]
    -> [CoreExpr]
    -> [CoreExpr]
    -> Maybe (CoreExpr -> CoreExpr, [CoreExpr])
    matchExprs InScopeEnv
    in_scope_env [Var]
    bndrs2 [CoreExpr]
    args2 [CoreExpr]
    args1)
      where
       full_in_scope :: InScopeSet
    full_in_scope = InScopeSet
    in_scope InScopeSet -> [Var] -> InScopeSet
    `extendInScopeSetList` [Var]
    bndrs1
       in_scope_env :: InScopeEnv
    in_scope_env  = InScopeSet -> IdUnfoldingFun -> InScopeEnv
    ISE InScopeSet
    full_in_scope IdUnfoldingFun
    noUnfoldingFun
                       -- noUnfoldingFun: don't expand in templates

    noBlackList :: Activation -> Bool
    noBlackList :: Activation -> Bool
    noBlackList Activation
    _ = Bool
    False           -- Nothing is black listed

    {- Note [isMoreSpecific]
    ~~~~~~~~~~~~~~~~~~~~~~~~
    The call (rule1 `isMoreSpecific` rule2)
    sees if rule2 can be instantiated to look like rule1.

    Wrinkle:

    * We take the view that a BuiltinRule is less specific than
      anything else, because we want user-defined rules to "win"
      In particular, class ops have a built-in rule, but we
      prefer any user-specific rules to win:
        eg (#4397)
           truncate :: (RealFrac a, Integral b) => a -> b
           {-# RULES "truncate/Double->Int" truncate = double2Int #-}
           double2Int :: Double -> Int
      We want the specific RULE to beat the built-in class-op rule

    Note [Extra args in the target]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    If we find a matching rule, we return (Just (rule, rhs)),
    /but/ the rule firing has only consumed as many of the input args
    as the ruleArity says.  The unused arguments are handled by the code in
    GHC.Core.Opt.Simplify.tryRules, using the arity of the returned rule.

    E.g. Rule "foo":  forall a b.  f p1 p2 = rhs
         Target:      f e1 e2 e3

    Then lookupRule returns Just (Rule "foo", rhs), where Rule "foo"
    has ruleArity 2.  The real rewrite is
            f e1 e2 e3 ==> rhs e3

    You might think it'd be cleaner for lookupRule to deal with the
    leftover arguments, by applying 'rhs' to them, but the main call
    in the Simplifier works better as it is.  Reason: the 'args' passed
    to lookupRule are the result of a lazy substitution

    Historical note:

    At one stage I tried to match even if there are more args in the
    /template/ than the target.  I now think this is probably a bad idea.
    Should the template (map f xs) match (map g)?  I think not.  For a
    start, in general eta expansion wastes work.  SLPJ July 99
    -}

    ------------------------------------
    matchRule :: RuleOpts -> InScopeEnv -> (Activation -> Bool)
              -> Id -> [CoreExpr] -> [Maybe Name]
              -> CoreRule -> Maybe CoreExpr

    -- If (matchRule rule args) returns Just (name,rhs)
    -- then (f args) matches the rule, and the corresponding
    -- rewritten RHS is rhs
    --
    -- The returned expression is occurrence-analysed
    --
    --      Example
    --
    -- The rule
    --      forall f g x. map f (map g x) ==> map (f . g) x
    -- is stored
    --      CoreRule "map/map"
    --               [f,g,x]                -- tpl_vars
    --               [f,map g x]            -- tpl_args
    --               map (f.g) x)           -- rhs
    --
    -- Then the expression
    --      map e1 (map e2 e3) e4
    -- results in a call to
    --      matchRule the_rule [e1,map e2 e3,e4]
    --        = Just ("map/map", (\f,g,x -> rhs) e1 e2 e3)
    --
    -- NB: The 'surplus' argument e4 in the input is simply dropped.
    -- See Note [Extra args in the target]

    matchRule :: RuleOpts
    -> InScopeEnv
    -> (Activation -> Bool)
    -> Var
    -> [CoreExpr]
    -> [Maybe Name]
    -> CoreRule
    -> Maybe CoreExpr
    matchRule RuleOpts
    opts InScopeEnv
    rule_env Activation -> Bool
    _is_active Var
    fn [CoreExpr]
    args [Maybe Name]
    _rough_args
              (BuiltinRule { ru_try :: CoreRule -> RuleFun
    ru_try = RuleFun
    match_fn })
    -- Built-in rules can't be switched off, it seems
      = case RuleFun
    match_fn RuleOpts
    opts InScopeEnv
    rule_env Var
    fn [CoreExpr]
    args of
            Maybe CoreExpr
    Nothing   -> Maybe CoreExpr
    forall a. Maybe a
    Nothing
            Just CoreExpr
    expr -> CoreExpr -> Maybe CoreExpr
    forall a. a -> Maybe a
    Just CoreExpr
    expr

    matchRule RuleOpts
    _ InScopeEnv
    rule_env Activation -> Bool
    is_active Var
    _ [CoreExpr]
    args [Maybe Name]
    rough_args
              (Rule { ru_name :: CoreRule -> RuleName
    ru_name = RuleName
    rule_name, ru_act :: CoreRule -> Activation
    ru_act = Activation
    act, ru_rough :: CoreRule -> [Maybe Name]
    ru_rough = [Maybe Name]
    tpl_tops
                    , ru_bndrs :: CoreRule -> [Var]
    ru_bndrs = [Var]
    tpl_vars, ru_args :: CoreRule -> [CoreExpr]
    ru_args = [CoreExpr]
    tpl_args, ru_rhs :: CoreRule -> CoreExpr
    ru_rhs = CoreExpr
    rhs })
      | Bool -> Bool
    not (Activation -> Bool
    is_active Activation
    act)               = Maybe CoreExpr
    forall a. Maybe a
    Nothing
      | [Maybe Name] -> [Maybe Name] -> Bool
    ruleCantMatch [Maybe Name]
    tpl_tops [Maybe Name]
    rough_args = Maybe CoreExpr
    forall a. Maybe a
    Nothing
      | Bool
    otherwise = InScopeEnv
    -> RuleName
    -> [Var]
    -> [CoreExpr]
    -> [CoreExpr]
    -> CoreExpr
    -> Maybe CoreExpr
    matchN InScopeEnv
    rule_env RuleName
    rule_name [Var]
    tpl_vars [CoreExpr]
    tpl_args [CoreExpr]
    args CoreExpr
    rhs

    ---------------------------------------
    matchN  :: InScopeEnv
            -> RuleName -> [Var] -> [CoreExpr]
            -> [CoreExpr] -> CoreExpr           -- ^ Target; can have more elements than the template
            -> Maybe CoreExpr
    -- For a given match template and context, find bindings to wrap around
    -- the entire result and what should be substituted for each template variable.
    --
    -- Fail if there are too few actual arguments from the target to match the template
    --
    -- See Note [Extra args in the target]
    -- If there are too /many/ actual arguments, we simply ignore the
    -- trailing ones, returning the result of applying the rule to a prefix
    -- of the actual arguments.

    matchN :: InScopeEnv
    -> RuleName
    -> [Var]
    -> [CoreExpr]
    -> [CoreExpr]
    -> CoreExpr
    -> Maybe CoreExpr
    matchN InScopeEnv
    ise RuleName
    _rule_name [Var]
    tmpl_vars [CoreExpr]
    tmpl_es [CoreExpr]
    target_es CoreExpr
    rhs
      = do { (bind_wrapper, matched_es) <- InScopeEnv
    -> [Var]
    -> [CoreExpr]
    -> [CoreExpr]
    -> Maybe (CoreExpr -> CoreExpr, [CoreExpr])
    matchExprs InScopeEnv
    ise [Var]
    tmpl_vars [CoreExpr]
    tmpl_es [CoreExpr]
    target_es
           ; return (bind_wrapper $
                     mkLams tmpl_vars rhs `mkApps` matched_es) }

    matchExprs :: InScopeEnv -> [Var] -> [CoreExpr] -> [CoreExpr]
               -> Maybe (BindWrapper, [CoreExpr])  -- 1-1 with the [Var]
    matchExprs :: InScopeEnv
    -> [Var]
    -> [CoreExpr]
    -> [CoreExpr]
    -> Maybe (CoreExpr -> CoreExpr, [CoreExpr])
    matchExprs (ISE InScopeSet
    in_scope IdUnfoldingFun
    id_unf) [Var]
    tmpl_vars [CoreExpr]
    tmpl_es [CoreExpr]
    target_es
      = do  { rule_subst <- RuleMatchEnv
    -> RuleSubst -> [CoreExpr] -> [CoreExpr] -> Maybe RuleSubst
    match_exprs RuleMatchEnv
    init_menv RuleSubst
    emptyRuleSubst [CoreExpr]
    tmpl_es [CoreExpr]
    target_es
            ; let (_, matched_es) = mapAccumL (lookup_tmpl rule_subst)
                                              (mkEmptySubst in_scope) $
                                    tmpl_vars `zip` tmpl_vars1

            ; let bind_wrapper = RuleSubst -> CoreExpr -> CoreExpr
    rs_binds RuleSubst
    rule_subst
                                 -- Floated bindings; see Note [Matching lets]

            ; return (bind_wrapper, matched_es) }
      where
        (RnEnv2
    init_rn_env, [Var]
    tmpl_vars1) = (RnEnv2 -> Var -> (RnEnv2, Var))
    -> RnEnv2 -> [Var] -> (RnEnv2, [Var])
    forall (t :: * -> *) s a b.
    Traversable t =>
    (s -> a -> (s, b)) -> s -> t a -> (s, t b)
    mapAccumL RnEnv2 -> Var -> (RnEnv2, Var)
    rnBndrL (InScopeSet -> RnEnv2
    mkRnEnv2 InScopeSet
    in_scope) [Var]
    tmpl_vars
                      -- See Note [Cloning the template binders]

        init_menv :: RuleMatchEnv
    init_menv = RV { rv_tmpls :: VarSet
    rv_tmpls = [Var] -> VarSet
    mkVarSet [Var]
    tmpl_vars1
                       , rv_lcl :: RnEnv2
    rv_lcl   = RnEnv2
    init_rn_env
                       , rv_fltR :: Subst
    rv_fltR  = InScopeSet -> Subst
    mkEmptySubst (RnEnv2 -> InScopeSet
    rnInScopeSet RnEnv2
    init_rn_env)
                       , rv_unf :: IdUnfoldingFun
    rv_unf   = IdUnfoldingFun
    id_unf }

        lookup_tmpl :: RuleSubst -> Subst -> (InVar,OutVar) -> (Subst, CoreExpr)
                       -- Need to return a RuleSubst solely for the benefit of fake_ty
        lookup_tmpl :: RuleSubst -> Subst -> (Var, Var) -> (Subst, CoreExpr)
    lookup_tmpl (RS { rs_tv_subst :: RuleSubst -> TvSubstEnv
    rs_tv_subst = TvSubstEnv
    tv_subst, rs_id_subst :: RuleSubst -> IdSubstEnv
    rs_id_subst = IdSubstEnv
    id_subst })
                    Subst
    tcv_subst (Var
    tmpl_var, Var
    tmpl_var1)
            | Var -> Bool
    isId Var
    tmpl_var1
            = case IdSubstEnv -> Var -> Maybe CoreExpr
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv IdSubstEnv
    id_subst Var
    tmpl_var1 of
                Just CoreExpr
    e | Coercion Coercion
    co <- CoreExpr
    e
                       -> (Subst -> Var -> Coercion -> Subst
    Type.extendCvSubst Subst
    tcv_subst Var
    tmpl_var1 Coercion
    co, Coercion -> CoreExpr
    forall b. Coercion -> Expr b
    Coercion Coercion
    co)
                       | Bool
    otherwise
                       -> (Subst
    tcv_subst, CoreExpr
    e)
                Maybe CoreExpr
    Nothing | Just Coercion
    refl_co <- Var -> Maybe Coercion
    isReflCoVar_maybe Var
    tmpl_var1
                        , let co :: Coercion
    co = HasDebugCallStack => Subst -> Coercion -> Coercion
    Subst -> Coercion -> Coercion
    Coercion.substCo Subst
    tcv_subst Coercion
    refl_co
                        -> -- See Note [Unbound RULE binders]
                           (Subst -> Var -> Coercion -> Subst
    Type.extendCvSubst Subst
    tcv_subst Var
    tmpl_var1 Coercion
    co, Coercion -> CoreExpr
    forall b. Coercion -> Expr b
    Coercion Coercion
    co)
                        | Bool
    otherwise
                        -> Var -> (Subst, CoreExpr)
    unbound Var
    tmpl_var

            | Bool
    otherwise
            = (Subst -> Var -> Kind -> Subst
    Type.extendTvSubst Subst
    tcv_subst Var
    tmpl_var1 Kind
    ty', Kind -> CoreExpr
    forall b. Kind -> Expr b
    Type Kind
    ty')
            where
              ty' :: Kind
    ty' = case TvSubstEnv -> Var -> Maybe Kind
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv TvSubstEnv
    tv_subst Var
    tmpl_var1 of
                      Just Kind
    ty -> Kind
    ty
                      Maybe Kind
    Nothing -> Kind
    fake_ty   -- See Note [Unbound RULE binders]
              fake_ty :: Kind
    fake_ty = Kind -> Kind
    anyTypeOfKind (HasDebugCallStack => Subst -> Kind -> Kind
    Subst -> Kind -> Kind
    Type.substTy Subst
    tcv_subst (Var -> Kind
    tyVarKind Var
    tmpl_var1))
                        -- This substitution is the sole reason we accumulate
                        -- TCvSubst in lookup_tmpl

        unbound :: Var -> (Subst, CoreExpr)
    unbound Var
    tmpl_var
           = String -> SDoc -> (Subst, CoreExpr)
    forall a. HasCallStack => String -> SDoc -> a
    pprPanic String
    "Template variable unbound in rewrite rule" (SDoc -> (Subst, CoreExpr)) -> SDoc -> (Subst, CoreExpr)
    forall a b. (a -> b) -> a -> b
    $
             [SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat [ String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Variable:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> Var -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Var
    tmpl_var SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> SDoc
    dcolon SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> Kind -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr (Var -> Kind
    varType Var
    tmpl_var)
                  , String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Rule bndrs:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> [Var] -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr [Var]
    tmpl_vars
                  , String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "LHS args:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> [CoreExpr] -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr [CoreExpr]
    tmpl_es
                  , String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Actual args:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> [CoreExpr] -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr [CoreExpr]
    target_es ]

    ----------------------
    match_exprs :: RuleMatchEnv -> RuleSubst
                -> [CoreExpr]       -- Templates
                -> [CoreExpr]       -- Targets
                -> Maybe RuleSubst
    -- If the targets are longer than templates, succeed, simply ignoring
    -- the leftover targets. This matters in the call in matchN.
    --
    -- Precondition: corresponding elements of es1 and es2 have the same
    --               type, assuming earlier elements match.
    -- Example:  f :: forall v. v -> blah
    --   match_exprs [Type a, y::a] [Type Int, 3]
    -- Then, after matching Type a against Type Int,
    -- the type of (y::a) matches that of (3::Int)
    match_exprs :: RuleMatchEnv
    -> RuleSubst -> [CoreExpr] -> [CoreExpr] -> Maybe RuleSubst
    match_exprs RuleMatchEnv
    _ RuleSubst
    subst [] [CoreExpr]
    _
      = RuleSubst -> Maybe RuleSubst
    forall a. a -> Maybe a
    Just RuleSubst
    subst
    match_exprs RuleMatchEnv
    renv RuleSubst
    subst (CoreExpr
    e1:[CoreExpr]
    es1) (CoreExpr
    e2:[CoreExpr]
    es2)
      = do { subst' <- RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 CoreExpr
    e2 MCoercion
    MRefl
           ; match_exprs renv subst' es1 es2 }
    match_exprs RuleMatchEnv
    _ RuleSubst
    _ [CoreExpr]
    _ [CoreExpr]
    _ = Maybe RuleSubst
    forall a. Maybe a
    Nothing

    {- Note [Unbound RULE binders]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    It can be the case that the binder in a rule is not actually
    bound on the LHS:

    * Type variables.  Type synonyms with phantom args can give rise to
      unbound template type variables.  Consider this (#10689,
      simplCore/should_compile/T10689):

        type Foo a b = b

        f :: Eq a => a -> Bool
        f x = x==x

        {-# RULES "foo" forall (x :: Foo a Char). f x = True #-}
        finkle = f 'c'

      The rule looks like
        forall (a::*) (d::Eq Char) (x :: Foo a Char).
             f (Foo a Char) d x = True

      Matching the rule won't bind 'a', and legitimately so.  We fudge by
      pretending that 'a' is bound to (Any :: *).

    * Coercion variables.  On the LHS of a RULE for a local binder
      we might have
        RULE forall (c :: a~b). f (x |> c) = e
      Now, if that binding is inlined, so that a=b=Int, we'd get
        RULE forall (c :: Int~Int). f (x |> c) = e
      and now when we simplify the LHS (Simplify.simplRule) we
      optCoercion (look at the CoVarCo case) will turn that 'c' into Refl:
        RULE forall (c :: Int~Int). f (x |> <Int>) = e
      and then perhaps drop it altogether.  Now 'c' is unbound.

      It's tricky to be sure this never happens, so instead I
      say it's OK to have an unbound coercion binder in a RULE
      provided its type is (c :: t~t).  Then, when the RULE
      fires we can substitute <t> for c.

      This actually happened (in a RULE for a local function)
      in #13410, and also in test T10602.

    Note [Cloning the template binders]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Consider the following match (example 1):
            Template:  forall x.  f x
            Target:               f (x+1)
    This should succeed, because the template variable 'x' has nothing to
    do with the 'x' in the target.

    Likewise this one (example 2):
            Template:  forall x. f (\x.x)
            Target:              f (\y.y)

    We achieve this simply by using rnBndrL to clone the template
    binders if they are already in scope.

    ------ Historical note -------
    At one point I tried simply adding the template binders to the
    in-scope set /without/ cloning them, but that failed in a horribly
    obscure way in #14777.  Problem was that during matching we look
    up target-term variables in the in-scope set (see Note [Lookup
    in-scope]).  If a target-term variable happens to name-clash with a
    template variable, that lookup will find the template variable, which
    is /utterly/ bogus.  In #14777, this transformed a term variable
    into a type variable, and then crashed when we wanted its idInfo.
    ------ End of historical note -------

    ************************************************************************
    *                                                                      *
                       The main matcher
    *                                                                      *
    ********************************************************************* -}

    data RuleMatchEnv
      = RV { RuleMatchEnv -> RnEnv2
    rv_lcl   :: RnEnv2          -- Renamings for *local bindings*
                                         --   (lambda/case)
           , RuleMatchEnv -> VarSet
    rv_tmpls :: VarSet          -- Template variables
                                         --   (after applying envL of rv_lcl)
           , RuleMatchEnv -> Subst
    rv_fltR  :: Subst           -- Renamings for floated let-bindings
                                         --   (domain disjoint from envR of rv_lcl)
                                         -- See Note [Matching lets]
                                         -- N.B. The InScopeSet of rv_fltR is always ignored;
                                         -- see (4) in Note [Matching lets].
           , RuleMatchEnv -> IdUnfoldingFun
    rv_unf :: IdUnfoldingFun
           }

    {- Note [rv_lcl in RuleMatchEnv]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Consider matching
      Template: \x->f
      Target:   \f->f

    where 'f' is free in the template. When we meet the lambdas we must
    remember to rename f :-> f' in the target, as well as x :-> f
    in the template.  The rv_lcl::RnEnv2 does that.

    Similarly, consider matching
         Template: {a}  \b->b
         Target:        \a->3
    We must rename the \a.  Otherwise when we meet the lambdas we might
    substitute [b :-> a] in the template, and then erroneously succeed in
    matching what looks like the template variable 'a' against 3.

    So we must add the template vars to the in-scope set before starting;
    see `init_menv` in `matchN`.
    -}

    -- * The domain of the TvSubstEnv and IdSubstEnv are the template
    --   variables passed into the match.
    --
    -- * The BindWrapper in a RuleSubst are the bindings floated out
    --   from nested matches; see the Let case of match, below
    --
    data RuleSubst = RS { -- Substitution; applied only to the template, not the target
                          -- Domain is the template variables
                          -- Range never includes template variables
                          RuleSubst -> TvSubstEnv
    rs_tv_subst :: TvSubstEnv
                        , RuleSubst -> IdSubstEnv
    rs_id_subst :: IdSubstEnv

                          -- Floated bindings
                        , RuleSubst -> CoreExpr -> CoreExpr
    rs_binds    :: BindWrapper  -- Floated bindings
                        , RuleSubst -> [Var]
    rs_bndrs    :: [Var]        -- Variables bound by floated lets
                        }

    type BindWrapper = CoreExpr -> CoreExpr
      -- See Notes [Matching lets] and [Matching cases]
      -- we represent the floated bindings as a core-to-core function

    emptyRuleSubst :: RuleSubst
    emptyRuleSubst :: RuleSubst
    emptyRuleSubst = RS { rs_tv_subst :: TvSubstEnv
    rs_tv_subst = TvSubstEnv
    forall a. VarEnv a
    emptyVarEnv, rs_id_subst :: IdSubstEnv
    rs_id_subst = IdSubstEnv
    forall a. VarEnv a
    emptyVarEnv
                        , rs_binds :: CoreExpr -> CoreExpr
    rs_binds = \CoreExpr
    e -> CoreExpr
    e, rs_bndrs :: [Var]
    rs_bndrs = [] }

    {- Note [Casts in the target]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    As far as possible we don't want casts in the target to get in the way of
    matching.  E.g.
    * (let bind in e)  |> co
    * (case e of alts) |> co
    * (\ a b. f a b)   |> co

    In the first two cases we want to float the cast inwards so we can match on
    the let/case.  This is not important in practice because the Simplifier does
    this anyway.

    But the third case /is/ important: we don't want the cast to get in the way
    of eta-reduction.  See Note [Cancel reflexive casts] for a real life example.

    The most convenient thing is to make 'match' take an MCoercion argument, thus:

    * The main matching function
          match env subst template target mco
      matches   template ~ (target |> mco)

    * Invariant: typeof( subst(template) ) = typeof( target |> mco )

    Note that for applications
         (e1 e2) ~ (d1 d2) |> co
    where 'co' is non-reflexive, we simply fail.  You might wonder about
         (e1 e2) ~ ((d1 |> co1) d2) |> co2
    but the Simplifer pushes the casts in an application to to the
    right, if it can, so this doesn't really arise.

    Note [Casts in the template]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    This Note concerns `matchTemplateCast`.  Consider the definition
      f x = e,
    and SpecConstr on call pattern
      f ((e1,e2) |> co)

    The danger is that We'll make a RULE
       RULE forall a,b,g.  f ((a,b)|> g) = $sf a b g
       $sf a b g = e[ ((a,b)|> g) / x ]

    This requires the rule-matcher to bind the coercion variable `g`.
    That is Very Deeply Suspicious:

    * It would be unreasonable to match on a structured coercion in a pattern,
      such as    RULE   forall g.  f (x |> Sym g) = ...
      because the strucure of a coercion is arbitrary and may change -- it's their
      /type/ that matters.

    * We considered insisting that in a template, in a cast (e |> co), the the cast
      `co` is always a /variable/ cv.  That looks a bit more plausible, but #23209
      (and related tickets) shows that it's very fragile.  For example suppose `e`
      is a variable `f`, and the simplifier has an unconditional substitution
         [f :-> g |> co2]
      Now the rule LHS becomes (f |> (co2 ; cv)); not a coercion variable any more!

    In short, it is Very Deeply Suspicious for a rule to quantify over a coercion
    variable.  And SpecConstr no longer does so: see Note [SpecConstr and casts] in
    SpecConstr.

    It is, however, OK for a cast to appear in a template.  For example
        newtype N a = MkN (a,a)    -- Axiom ax:N a :: (a,a) ~R N a
        f :: N a -> bah
        RULE forall b x:b y:b. f @b ((x,y) |> (axN @b)) = ...

    When matching we can just move these casts to the other side:
        match (tmpl |> co) tgt  -->   match tmpl (tgt |> sym co)
    See matchTemplateCast.

    Wrinkles:

    (CT1) We need to be careful about scoping, and to match left-to-right, so that we
      know the substitution [a :-> b] before we meet (co :: (a,a) ~R N a), and so we
      can apply that substitition

    (CT2) Annoyingly, we still want support one case in which the RULE quantifies
      over a coercion variable: the dreaded map/coerce RULE.
      See Note [Getting the map/coerce RULE to work] in GHC.Core.SimpleOpt.

      Since that can happen, matchTemplateCast laboriously checks whether the
      coercion mentions a template coercion variable; and if so does the Very Deeply
      Suspicious `match_co` instead.  It works fine for map/coerce, where the
      coercion is always a variable and will (robustly) remain so.

    See also
    * Note [Coercion arguments]
    * Note [Matching coercion variables] in GHC.Core.Unify.
    * Note [Cast swizzling on rule LHSs] in GHC.Core.Opt.Simplify.Utils:
      sm_cast_swizzle is switched off in the template of a RULE

    Note [Coercion arguments]
    ~~~~~~~~~~~~~~~~~~~~~~~~~
    What if we have (f (Coercion co)) in the template, where the 'co' is a coercion
    argument to f?  Right now we have nothing in place to ensure that a
    coercion /argument/ in the template is a variable.  We really should,
    perhaps by abstracting over that variable.

    C.f. the treatment of dictionaries in GHC.HsToCore.Binds.decompseRuleLhs.

    For now, though, we simply behave badly, by failing in match_co.
    We really should never rely on matching the structure of a coercion
    (which is just a proof).
    -}

    ----------------------
    match :: RuleMatchEnv
          -> RuleSubst              -- Substitution applies to template only
          -> CoreExpr               -- Template
          -> CoreExpr               -- Target
          -> MCoercion
          -> Maybe RuleSubst

    -- Postcondition (TypeInv): if matching succeeds, then
    --                          typeof( subst(template) ) = typeof( target |> mco )
    --     But this is /not/ a pre-condition! The types of template and target
    --     may differ, see the (App e1 e2) case
    --
    -- Invariant (CoInv):   if mco :: ty ~ ty, then it is MRefl, not MCo co
    --                      See Note [Cancel reflexive casts]
    --
    -- See the notes with Unify.match, which matches types
    -- Everything is very similar for terms

    ------------------------ Ticks ---------------------
    -- We look through certain ticks. See Note [Tick annotations in RULE matching]
    match :: RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 (Tick CoreTickish
    t CoreExpr
    e2) MCoercion
    mco
      | CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable CoreTickish
    t
      = RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    subst' CoreExpr
    e1 CoreExpr
    e2 MCoercion
    mco
      | Bool
    otherwise
      = Maybe RuleSubst
    forall a. Maybe a
    Nothing
      where
        subst' :: RuleSubst
    subst' = RuleSubst
    subst { rs_binds = rs_binds subst . mkTick t }

    match RuleMatchEnv
    renv RuleSubst
    subst e :: CoreExpr
    e@(Tick CoreTickish
    t CoreExpr
    e1) CoreExpr
    e2 MCoercion
    mco
      | CoreTickish -> Bool
    forall (pass :: TickishPass). GenTickish pass -> Bool
    tickishFloatable CoreTickish
    t  -- Ignore floatable ticks in rule template.
      =  RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 CoreExpr
    e2 MCoercion
    mco
      | Bool
    otherwise
      = String -> SDoc -> Maybe RuleSubst
    forall a. HasCallStack => String -> SDoc -> a
    pprPanic String
    "Tick in rule" (CoreExpr -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr CoreExpr
    e)

    ------------------------ Types ---------------------
    match RuleMatchEnv
    renv RuleSubst
    subst (Type Kind
    ty1) (Type Kind
    ty2) MCoercion
    _mco
      = RuleMatchEnv -> RuleSubst -> Kind -> Kind -> Maybe RuleSubst
    match_ty RuleMatchEnv
    renv RuleSubst
    subst Kind
    ty1 Kind
    ty2

    ------------------------ Coercions ---------------------
    -- See Note [Coercion arguments] for why this isn't really right
    match RuleMatchEnv
    renv RuleSubst
    subst (Coercion Coercion
    co1) (Coercion Coercion
    co2) MCoercion
    MRefl
      = RuleMatchEnv
    -> RuleSubst -> Coercion -> Coercion -> Maybe RuleSubst
    match_co RuleMatchEnv
    renv RuleSubst
    subst Coercion
    co1 Coercion
    co2
      -- The MCo case corresponds to matching  co ~ (co2 |> co3)
      -- and I have no idea what to do there -- or even if it can occur
      -- Failing seems the simplest thing to do; it's certainly safe.

    ------------------------ Casts ---------------------
    -- See Note [Casts in the template]
    --     Note [Casts in the target]
    --     Note [Cancel reflexive casts]

    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 (Cast CoreExpr
    e2 Coercion
    co2) MCoercion
    mco
      = RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 CoreExpr
    e2 (MCoercion -> MCoercion
    checkReflexiveMCo (Coercion -> MCoercion -> MCoercion
    mkTransMCoR Coercion
    co2 MCoercion
    mco))
        -- checkReflexiveMCo: cancel casts if possible
        -- This is important: see Note [Cancel reflexive casts]

    match RuleMatchEnv
    renv RuleSubst
    subst (Cast CoreExpr
    e1 Coercion
    co1) CoreExpr
    e2 MCoercion
    mco
      = RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> Coercion
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    matchTemplateCast RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 Coercion
    co1 CoreExpr
    e2 MCoercion
    mco

    ------------------------ Literals ---------------------
    match RuleMatchEnv
    _ RuleSubst
    subst (Lit Literal
    lit1) (Lit Literal
    lit2) MCoercion
    mco
      | Literal
    lit1 Literal -> Literal -> Bool
    forall a. Eq a => a -> a -> Bool
    == Literal
    lit2
      = Bool -> SDoc -> Maybe RuleSubst -> Maybe RuleSubst
    forall a. HasCallStack => Bool -> SDoc -> a -> a
    assertPpr (MCoercion -> Bool
    isReflMCo MCoercion
    mco) (MCoercion -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr MCoercion
    mco) (Maybe RuleSubst -> Maybe RuleSubst)
    -> Maybe RuleSubst -> Maybe RuleSubst
    forall a b. (a -> b) -> a -> b
    $
        RuleSubst -> Maybe RuleSubst
    forall a. a -> Maybe a
    Just RuleSubst
    subst

    ------------------------ Variables ---------------------
    -- The Var case follows closely what happens in GHC.Core.Unify.match
    match RuleMatchEnv
    renv RuleSubst
    subst (Var Var
    v1) CoreExpr
    e2 MCoercion
    mco
      = RuleMatchEnv -> RuleSubst -> Var -> CoreExpr -> Maybe RuleSubst
    match_var RuleMatchEnv
    renv RuleSubst
    subst Var
    v1 (CoreExpr -> MCoercion -> CoreExpr
    mkCastMCo CoreExpr
    e2 MCoercion
    mco)

    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 (Var Var
    v2) MCoercion
    mco  -- Note [Expanding variables]
      | Bool -> Bool
    not (RnEnv2 -> Var -> Bool
    inRnEnvR RnEnv2
    rn_env Var
    v2)      -- Note [Do not expand locally-bound variables]
      , Just CoreExpr
    e2' <- Unfolding -> Maybe CoreExpr
    expandUnfolding_maybe (RuleMatchEnv -> IdUnfoldingFun
    rv_unf RuleMatchEnv
    renv Var
    v2')
      = RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match (RuleMatchEnv
    renv { rv_lcl = nukeRnEnvR rn_env }) RuleSubst
    subst CoreExpr
    e1 CoreExpr
    e2' MCoercion
    mco
      where
        v2' :: Var
    v2'    = RnEnv2 -> Var -> Var
    lookupRnInScope RnEnv2
    rn_env Var
    v2
        rn_env :: RnEnv2
    rn_env = RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv
            -- Notice that we look up v2 in the in-scope set
            -- See Note [Lookup in-scope]
            -- No need to apply any renaming first (hence no rnOccR)
            -- because of the not-inRnEnvR

    ------------------------ Applications ---------------------
    -- See Note [Matching higher order patterns]
    match renv :: RuleMatchEnv
    renv@(RV { rv_tmpls :: RuleMatchEnv -> VarSet
    rv_tmpls = VarSet
    tmpls, rv_lcl :: RuleMatchEnv -> RnEnv2
    rv_lcl = RnEnv2
    rn_env })
          RuleSubst
    subst  e1 :: CoreExpr
    e1@App{} CoreExpr
    e2
          MCoercion
    MRefl               -- Like the App case we insist on Refl here
                              -- See Note [Casts in the target]
      | (Var Var
    f, [CoreExpr]
    args) <- CoreExpr -> (CoreExpr, [CoreExpr])
    forall b. Expr b -> (Expr b, [Expr b])
    collectArgs CoreExpr
    e1
      , let f' :: Var
    f' = RnEnv2 -> Var -> Var
    rnOccL RnEnv2
    rn_env Var
    f   -- See similar rnOccL in match_var
      , Var
    f' Var -> VarSet -> Bool
    `elemVarSet` VarSet
    tmpls                     -- (HOP1)
      , Just [Var]
    vs2 <- (CoreExpr -> Maybe Var) -> [CoreExpr] -> Maybe [Var]
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> [a] -> f [b]
    traverse CoreExpr -> Maybe Var
    arg_as_lcl_var [CoreExpr]
    args  -- (HOP2), (HOP3)
      , [Var] -> Bool
    forall a. Eq a => [a] -> Bool
    hasNoDups [Var]
    vs2                             -- (HOP4)
      , Bool -> Bool
    not Bool
    can_decompose_app_instead
      = RuleMatchEnv -> RuleSubst -> Var -> CoreExpr -> Maybe RuleSubst
    match_tmpl_var RuleMatchEnv
    renv RuleSubst
    subst Var
    f' ([Var] -> CoreExpr -> CoreExpr
    mkCoreLams [Var]
    vs2 CoreExpr
    e2)
        -- match_tmpl_var checks (HOP5) and (HOP6)
      where
        arg_as_lcl_var :: CoreExpr -> Maybe Var
        arg_as_lcl_var :: CoreExpr -> Maybe Var
    arg_as_lcl_var (Var Var
    v)
          | Just Var
    v' <- RnEnv2 -> Var -> Maybe Var
    rnOccL_maybe RnEnv2
    rn_env Var
    v
          , Bool -> Bool
    not (Var
    v' Var -> VarSet -> Bool
    `elemVarSet` VarSet
    tmpls)  -- rnEnvL contains the template variables
          = Var -> Maybe Var
    forall a. a -> Maybe a
    Just (Var -> Var
    to_target Var
    v')          -- to_target: see (W1)
                                         --   in Note [Matching higher order patterns]
        arg_as_lcl_var CoreExpr
    _ = Maybe Var
    forall a. Maybe a
    Nothing

        can_decompose_app_instead :: Bool
    can_decompose_app_instead -- Template (e1 v), target (e2 v), and v # fvs(e2)
          = case (CoreExpr
    e1, CoreExpr
    e2) of      -- See (W2) in Note [Matching higher order patterns]
               (App CoreExpr
    _ (Var Var
    v1), App CoreExpr
    f2 (Var Var
    v2))
                 -> RnEnv2 -> Var -> Var
    rnOccL RnEnv2
    rn_env Var
    v1 Var -> Var -> Bool
    forall a. Eq a => a -> a -> Bool
    == RnEnv2 -> Var -> Var
    rnOccR RnEnv2
    rn_env Var
    v2
                    Bool -> Bool -> Bool
    && Bool -> Bool
    not (Var
    v2 Var -> VarSet -> Bool
    `elemVarSet` CoreExpr -> VarSet
    exprFreeVars CoreExpr
    f2)
               (CoreExpr, CoreExpr)
    _ -> Bool
    False

        ----------------
        -- to_target: see (W1) in Note [Matching higher order patterns]
        to_target :: Var -> Var   -- From canonical variable back to target-expr variable
        to_target :: Var -> Var
    to_target Var
    v = VarEnv Var -> Var -> Maybe Var
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv VarEnv Var
    rev_envR Var
    v Maybe Var -> Var -> Var
    forall a. Maybe a -> a -> a
    `orElse` Var
    v

        rev_envR :: VarEnv Var   -- Inverts rnEnvR: from canonical variable
                                 -- back to target-expr variable
        rev_envR :: VarEnv Var
    rev_envR = (Unique -> Var -> VarEnv Var -> VarEnv Var)
    -> VarEnv Var -> VarEnv Var -> VarEnv Var
    forall a r. (Unique -> a -> r -> r) -> r -> VarEnv a -> r
    nonDetStrictFoldVarEnv_Directly Unique -> Var -> VarEnv Var -> VarEnv Var
    add_one VarEnv Var
    forall a. VarEnv a
    emptyVarEnv (RnEnv2 -> VarEnv Var
    rnEnvR RnEnv2
    rn_env)
        add_one :: Unique -> Var -> VarEnv Var -> VarEnv Var
    add_one Unique
    uniq Var
    var VarEnv Var
    env = VarEnv Var -> Var -> Var -> VarEnv Var
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv VarEnv Var
    env Var
    var (Var
    var Var -> Unique -> Var
    `setVarUnique` Unique
    uniq)

    {- Note [Matching higher order patterns]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Higher order patterns provide a limited form of higher order matching.
    See GHC Proposal #555
      https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0555-template-patterns.rst
    and #22465 for more details and related work.

    Consider the potential match:

       Template: forall f. foo (\x -> f x)
       Target:             foo (\x -> x*2 + x)

    The expression `x*2 + x` in the target is not literally an application of a
    function to the variable `x`, so the simple application rule does not apply.
    However, we can match them modulo beta equivalence with the substitution:

       [f :-> \x -> x*2 + x]

    The general problem of higher order matching is tricky to implement, but
    the subproblem which we call /higher order pattern matching/ is sufficient
    for the given example and much easier to implement.

    Design:

    We start with terminology.

    * /Template variables/. The forall'd variables are called the template
      variables. In the example match above, `f` is a template variable.

    * /Local binders/. The local binders of a rule are the variables bound
      inside the template. In the example match above, `x` is a local binder.
      Note that local binders can be term variables and type variables.

    A /higher order pattern/ (HOP) is a sub-expression of the template,
    of form (f x y z) where:

    * (HOP1) f is a template variable
    * (HOP2) x, y, z are local binders (like y in rule "wombat" above; see definitions).
    * (HOP3) The arguments x, y, z are term variables
    * (HOP4) The arguments x, y, z are distinct (no duplicates)

    Matching of higher order patterns (HOP-matching). A higher order pattern (f x y z)
    (in the template) matches any target expression e provided:

    * (HOP5) The target has the same type as the template
    * (HOP6) No local binder is free in e, other than x, y, z.

    If these two condition hold, the higher order pattern (f x y z) matches
    the target expression e, yielding the substitution [f :-> \x y z. e].
    Notice that this substitution is type preserving, and the RHS
    of the substitution has no free local binders.

    HOP matching is small enough to be done in-line in the `match` function.
    Two wrinkles:

    (W1) Consider the potential match:
            Template:    forall f. foo (\x -> f x)
            Target:                foo (\y -> (y, y))
         During matching we make `x` the canonical variable for the lambdas
         and then we see:
            Template:    f x       rnEnvL = []
            Target:      (y, y)    rnEnvR = [y :-> x]
         We could bind [f :-> \x. (x,x)], by applying rnEnvR substitution to the target
         expression.  But that is tiresome (a) because it involves a traversal, and
         (b) because rnEnvR is a VarEnv Var, and we don't have a substitution function
         for that.

         So instead, we invert rnEnvR, and apply it to the binders, to get
         [f :-> \y. (y,y)].  This is done by `to_target` in the HOP-matching case.
         It takes a little bit of thinking to be sure this will work right in the case
         of shadowing.  E.g.  Template (\x y. f x y)   Target  (\p p. p*p)
         Here rnEnvR will be just [p :-> y], so after inversion we'll get
              [f :-> \x p. p*p]
         but that is fine.

    (W2) This wrinkle concerns the overlap between the new HOP rule and the existing
         decompose-application rule.  See 3.1 of GHC Proposal #555 for a discussion.

         Consider potential match:
            Template: forall f.   foo (\x y. Just (f y x))
            Target:               foo (\p q. Just (h (1+q) p)))
         During matching we will encounter:
            Template:    f x y
            Target:      h (1+q) p    rnEnvR = [p:->x, q:->y]
         The rnEnvR renaming `[p:->x, q:->y]` is done by the matcher (today) on the fly,
         to make the bound variables of the template and target "line up".
         But now we can:
         * Either use the new HOP rule to succeed with
              [f :-> \x y. h (1+x) y]
         * Or use the existing decompose-application rule to match
              (f x) against (h (1+q)) and `y` against `p`.
           This will succeed with
              [f :-> \y. h (1+y)]

         Note that the result of the HOP rule will always be eta-equivalent to
         the result of the decompose-application rule.  But the proposal specifies
         that we should use the decompose-application rule because it involves
         less eta-expansion.

         But take care:
            Template: forall f.   foo (\x y. Just (f y x))
            Target:               foo (\p q. Just (h (p+q) p)))
         Then during matching we will encounter:
            Template:    f x y
            Target:      h (p+q) p      rnEnvR = [p:->x, q:->y]
         Now, we cannot use the decompose-application rule, because p is free in
         (h (p+q)). So, we can only use the new HOP rule.

    (W3) You might wonder if a HOP can have /type/ arguments, thus (in Core)
            RULE forall h.
                 f (\(MkT @b (d::Num b) (x::b)) -> h @b d x) = ...
         where the HOP is (h @b d x). In principle this might be possible, but
         it seems fragile; e.g. we would still need to insist that the (invisible)
         @b was a type variable.  And since `h` gets a polymoprhic type, that
         type would have to be declared by the programmer.

         Maybe one day.  But for now, we insist (in `arg_as_lcl_var`)that a HOP
         has only term-variable arguments.
    -}

    -- Note the match on MRefl!  We fail if there is a cast in the target
    --     (e1 e2) ~ (d1 d2) |> co
    -- See Note [Cancel reflexive casts]: in the Cast equations for 'match'
    -- we aggressively ensure that if MCo is reflective, it really is MRefl.
    match RuleMatchEnv
    renv RuleSubst
    subst (App CoreExpr
    f1 CoreExpr
    a1) (App CoreExpr
    f2 CoreExpr
    a2) MCoercion
    MRefl
      = do  { subst' <- RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    f1 CoreExpr
    f2 MCoercion
    MRefl
            ; match renv subst' a1 a2 MRefl }

    ------------------------ Float lets ---------------------
    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 (Let CoreBind
    bind CoreExpr
    e2) MCoercion
    mco
      | -- pprTrace "match:Let" (vcat [ppr bind, ppr $ okToFloat (rv_lcl renv) (bindFreeVars bind)]) $
        Bool -> Bool
    not (CoreBind -> Bool
    isJoinBind CoreBind
    bind) -- can't float join point out of argument position
      , RnEnv2 -> VarSet -> Bool
    okToFloat (RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv) (CoreBind -> VarSet
    bindFreeVars CoreBind
    bind) -- See Note [Matching lets]
      = RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match (RuleMatchEnv
    renv { rv_fltR = flt_subst'
                    , rv_lcl  = rv_lcl renv `extendRnInScopeSetList` new_bndrs })
                    -- We are floating the let-binding out, as if it had enclosed
                    -- the entire target from Day 1.  So we must add its binders to
                    -- the in-scope set (#20200)
              (RuleSubst
    subst { rs_binds = rs_binds subst . Let bind'
                     , rs_bndrs = new_bndrs ++ rs_bndrs subst })
              CoreExpr
    e1 CoreExpr
    e2 MCoercion
    mco
      | Bool
    otherwise
      = Maybe RuleSubst
    forall a. Maybe a
    Nothing
      where
        in_scope :: InScopeSet
    in_scope  = RnEnv2 -> InScopeSet
    rnInScopeSet (RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv) InScopeSet -> [Var] -> InScopeSet
    `extendInScopeSetList` RuleSubst -> [Var]
    rs_bndrs RuleSubst
    subst
                    -- in_scope: see (4) in Note [Matching lets]
        flt_subst :: Subst
    flt_subst = RuleMatchEnv -> Subst
    rv_fltR RuleMatchEnv
    renv Subst -> InScopeSet -> Subst
    `setInScope` InScopeSet
    in_scope
        (Subst
    flt_subst', CoreBind
    bind') = HasDebugCallStack => Subst -> CoreBind -> (Subst, CoreBind)
    Subst -> CoreBind -> (Subst, CoreBind)
    substBind Subst
    flt_subst CoreBind
    bind
        new_bndrs :: [Var]
    new_bndrs           = CoreBind -> [Var]
    forall b. Bind b -> [b]
    bindersOf CoreBind
    bind'

    ------------------------  Lambdas ---------------------
    match RuleMatchEnv
    renv RuleSubst
    subst (Lam Var
    x1 CoreExpr
    e1) CoreExpr
    e2 MCoercion
    mco
      | let casted_e2 :: CoreExpr
    casted_e2 = CoreExpr -> MCoercion -> CoreExpr
    mkCastMCo CoreExpr
    e2 MCoercion
    mco
            in_scope :: InScopeSet
    in_scope = InScopeSet -> VarSet -> InScopeSet
    extendInScopeSetSet (RnEnv2 -> InScopeSet
    rnInScopeSet (RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv))
                                           (CoreExpr -> VarSet
    exprFreeVars CoreExpr
    casted_e2)
            in_scope_env :: InScopeEnv
    in_scope_env = InScopeSet -> IdUnfoldingFun -> InScopeEnv
    ISE InScopeSet
    in_scope (RuleMatchEnv -> IdUnfoldingFun
    rv_unf RuleMatchEnv
    renv)
            -- extendInScopeSetSet: The InScopeSet of rn_env is not necessarily
            -- a superset of the free vars of e2; it is only guaranteed a superset of
            -- applying the (rnEnvR rn_env) substitution to e2. But exprIsLambda_maybe
            -- wants an in-scope set that includes all the free vars of its argument.
            -- Hence adding adding (exprFreeVars casted_e2) to the in-scope set (#23630)
      , Just (Var
    x2, CoreExpr
    e2', [CoreTickish]
    ts) <- HasDebugCallStack =>
    InScopeEnv -> CoreExpr -> Maybe (Var, CoreExpr, [CoreTickish])
    InScopeEnv -> CoreExpr -> Maybe (Var, CoreExpr, [CoreTickish])
    exprIsLambda_maybe InScopeEnv
    in_scope_env CoreExpr
    casted_e2
        -- See Note [Lambdas in the template]
      = let renv' :: RuleMatchEnv
    renv'  = RuleMatchEnv -> Var -> Var -> RuleMatchEnv
    rnMatchBndr2 RuleMatchEnv
    renv Var
    x1 Var
    x2
            subst' :: RuleSubst
    subst' = RuleSubst
    subst { rs_binds = rs_binds subst . flip (foldr mkTick) ts }
        in  RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv' RuleSubst
    subst' CoreExpr
    e1 CoreExpr
    e2' MCoercion
    MRefl

    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 e2 :: CoreExpr
    e2@(Lam {}) MCoercion
    mco
      | Just (RuleMatchEnv
    renv', CoreExpr
    e2') <- RuleMatchEnv -> CoreExpr -> Maybe (RuleMatchEnv, CoreExpr)
    eta_reduce RuleMatchEnv
    renv CoreExpr
    e2  -- See Note [Eta reduction in the target]
      = RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv' RuleSubst
    subst CoreExpr
    e1 CoreExpr
    e2' MCoercion
    mco

    {- Note [Lambdas in the template]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    If we match
       Template:   (\x. blah_template)
       Target:     (\y. blah_target)
    then we want to match inside the lambdas, using rv_lcl to match up
    x and y.

    But what about this?
       Template   (\x. (blah1 |> cv))
       Target     (\y. blah2) |> co

    This happens quite readily, because the Simplifier generally moves
    casts outside lambdas: see Note [Casts and lambdas] in
    GHC.Core.Opt.Simplify.Utils. So, tiresomely, we want to push `co`
    back inside, which is what `exprIsLambda_maybe` does.  But we've
    stripped off that cast, so now we need to put it back, hence mkCastMCo.

    Unlike the target, where we attempt eta-reduction, we do not attempt
    to eta-reduce the template, and may therefore fail on
      Template:   \x. f True x
      Target      f True

    It's not especially easy to deal with eta reducing the template,
    and never happens, because no one write eta-expanded left-hand-sides.
    -}

    ------------------------ Case expression ---------------------
    {- Disabled: see Note [Matching cases] below
    match renv (tv_subst, id_subst, binds) e1
          (Case scrut case_bndr ty [(con, alt_bndrs, rhs)])
      | exprOkForSpeculation scrut  -- See Note [Matching cases]
      , okToFloat rn_env bndrs (exprFreeVars scrut)
      = match (renv { me_env = rn_env' })
              (tv_subst, id_subst, binds . case_wrap)
              e1 rhs
      where
        rn_env   = me_env renv
        rn_env'  = extendRnInScopeList rn_env bndrs
        bndrs    = case_bndr : alt_bndrs
        case_wrap rhs' = Case scrut case_bndr ty [(con, alt_bndrs, rhs')]
    -}

    match RuleMatchEnv
    renv RuleSubst
    subst (Case CoreExpr
    e1 Var
    x1 Kind
    ty1 [Alt Var]
    alts1) (Case CoreExpr
    e2 Var
    x2 Kind
    ty2 [Alt Var]
    alts2) MCoercion
    mco
      = do  { subst1 <- RuleMatchEnv -> RuleSubst -> Kind -> Kind -> Maybe RuleSubst
    match_ty RuleMatchEnv
    renv RuleSubst
    subst Kind
    ty1 Kind
    ty2
            ; subst2 <- match renv subst1 e1 e2 MRefl
            ; let renv' = RuleMatchEnv -> Var -> Var -> RuleMatchEnv
    rnMatchBndr2 RuleMatchEnv
    renv Var
    x1 Var
    x2
            ; match_alts renv' subst2 alts1 alts2 mco   -- Alts are both sorted
            }

    -- Everything else fails
    match RuleMatchEnv
    _ RuleSubst
    _ CoreExpr
    _e1 CoreExpr
    _e2 MCoercion
    _mco = -- pprTrace "Failing at" ((text "e1:" <+> ppr _e1) $$ (text "e2:" <+> ppr _e2)) $
                             Maybe RuleSubst
    forall a. Maybe a
    Nothing

    -------------
    eta_reduce :: RuleMatchEnv -> CoreExpr -> Maybe (RuleMatchEnv, CoreExpr)
    -- See Note [Eta reduction in the target]
    eta_reduce :: RuleMatchEnv -> CoreExpr -> Maybe (RuleMatchEnv, CoreExpr)
    eta_reduce RuleMatchEnv
    renv e :: CoreExpr
    e@(Lam {})
      = RuleMatchEnv
    -> (CoreExpr -> CoreExpr)
    -> [Var]
    -> CoreExpr
    -> Maybe (RuleMatchEnv, CoreExpr)
    go RuleMatchEnv
    renv CoreExpr -> CoreExpr
    forall a. a -> a
    id [] CoreExpr
    e
      where
        go :: RuleMatchEnv -> BindWrapper -> [Var] -> CoreExpr
           -> Maybe (RuleMatchEnv, CoreExpr)
        go :: RuleMatchEnv
    -> (CoreExpr -> CoreExpr)
    -> [Var]
    -> CoreExpr
    -> Maybe (RuleMatchEnv, CoreExpr)
    go RuleMatchEnv
    renv CoreExpr -> CoreExpr
    bw [Var]
    vs (Let CoreBind
    b CoreExpr
    e) = RuleMatchEnv
    -> (CoreExpr -> CoreExpr)
    -> [Var]
    -> CoreExpr
    -> Maybe (RuleMatchEnv, CoreExpr)
    go RuleMatchEnv
    renv (CoreExpr -> CoreExpr
    bw (CoreExpr -> CoreExpr)
    -> (CoreExpr -> CoreExpr) -> CoreExpr -> CoreExpr
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . CoreBind -> CoreExpr -> CoreExpr
    forall b. Bind b -> Expr b -> Expr b
    Let CoreBind
    b) [Var]
    vs CoreExpr
    e

        go RuleMatchEnv
    renv CoreExpr -> CoreExpr
    bw [Var]
    vs (Lam Var
    v CoreExpr
    e) = RuleMatchEnv
    -> (CoreExpr -> CoreExpr)
    -> [Var]
    -> CoreExpr
    -> Maybe (RuleMatchEnv, CoreExpr)
    go RuleMatchEnv
    renv' CoreExpr -> CoreExpr
    bw (Var
    v'Var -> [Var] -> [Var]
    forall a. a -> [a] -> [a]
    :[Var]
    vs) CoreExpr
    e
          where
             (RnEnv2
    rn_env', Var
    v') = RnEnv2 -> Var -> (RnEnv2, Var)
    rnBndrR (RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv) Var
    v
             renv' :: RuleMatchEnv
    renv' = RuleMatchEnv
    renv { rv_lcl = rn_env' }

        go RuleMatchEnv
    renv CoreExpr -> CoreExpr
    bw (Var
    v:[Var]
    vs) (App CoreExpr
    f CoreExpr
    arg)
          | Var Var
    a <- CoreExpr
    arg, Var
    v Var -> Var -> Bool
    forall a. Eq a => a -> a -> Bool
    == RnEnv2 -> Var -> Var
    rnOccR (RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv) Var
    a
          = RuleMatchEnv
    -> (CoreExpr -> CoreExpr)
    -> [Var]
    -> CoreExpr
    -> Maybe (RuleMatchEnv, CoreExpr)
    go RuleMatchEnv
    renv CoreExpr -> CoreExpr
    bw [Var]
    vs CoreExpr
    f

          | Type Kind
    ty <- CoreExpr
    arg, Just Var
    tv <- Kind -> Maybe Var
    getTyVar_maybe Kind
    ty
          , Var
    v Var -> Var -> Bool
    forall a. Eq a => a -> a -> Bool
    == RnEnv2 -> Var -> Var
    rnOccR (RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv) Var
    tv
          = RuleMatchEnv
    -> (CoreExpr -> CoreExpr)
    -> [Var]
    -> CoreExpr
    -> Maybe (RuleMatchEnv, CoreExpr)
    go RuleMatchEnv
    renv CoreExpr -> CoreExpr
    bw [Var]
    vs CoreExpr
    f

        go RuleMatchEnv
    renv CoreExpr -> CoreExpr
    bw []    CoreExpr
    e = (RuleMatchEnv, CoreExpr) -> Maybe (RuleMatchEnv, CoreExpr)
    forall a. a -> Maybe a
    Just (RuleMatchEnv
    renv, CoreExpr -> CoreExpr
    bw CoreExpr
    e)
        go RuleMatchEnv
    _    CoreExpr -> CoreExpr
    _  (Var
    _:[Var]
    _) CoreExpr
    _ = Maybe (RuleMatchEnv, CoreExpr)
    forall a. Maybe a
    Nothing

    eta_reduce RuleMatchEnv
    _ CoreExpr
    _ = Maybe (RuleMatchEnv, CoreExpr)
    forall a. Maybe a
    Nothing

    {- Note [Eta reduction in the target]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Suppose we are faced with this (#19790)
       Template {x}  f x
       Target        (\a b c. let blah in f x a b c)

    You might wonder why we have an eta-expanded target (see first subtle
    point below), but regardless of how it came about, we'd like
    eta-expansion not to impede matching.

    So eta_reduce does on-the-fly eta-reduction of the target expression.
    Given (\a b c. let blah in e a b c), it returns (let blah in e).

    Subtle points:
    * Consider a target:  \x. f <expensive> x
      In the main eta-reducer we do not eta-reduce this, because doing so
      might reduce the arity of the expression (from 1 to zero, because of
      <expensive>).  But for rule-matching we /do/ want to match template
      (f a) against target (\x. f <expensive> x), with a := <expensive>

      This is a compelling reason for not relying on the Simplifier's
      eta-reducer.

    * The Lam case of eta_reduce renames as it goes. Consider
      (\x. \x. f x x).  We should not eta-reduce this.  As we go we rename
      the first x to x1, and the second to x2; then both argument x's are x2.

    * eta_reduce does /not/ need to check that the bindings 'blah'
      and expression 'e' don't mention a b c; but it /does/ extend the
      rv_lcl RnEnv2 (see rn_bndr in eta_reduce).
      * If 'blah' mentions the binders, the let-float rule won't
        fire; and
      * if 'e' mentions the binders we we'll also fail to match
        e.g. because of the exprFreeVars test in match_tmpl_var.

      Example: Template: {x}  f a         -- Some top-level 'a'
               Target:   (\a b. f a a b)  -- The \a shadows top level 'a'
      Then eta_reduce will /succeed/, with
          (rnEnvR = [a :-> a'], f a)
      The returned RnEnv will map [a :-> a'], where a' is fresh. (There is
      no need to rename 'b' because (in this example) it is not in scope.
      So it's as if we'd returned (f a') from eta_reduce; the renaming applied
      to the target is simply deferred.

    Note [Cancel reflexive casts]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Here is an example (from #19790) which we want to catch
       (f x) ~ (\a b. (f x |> co) a b) |> sym co
    where
       f :: Int -> Stream
       co :: Stream ~ T1 -> T2 -> T3

    when we eta-reduce (\a b. blah a b) to 'blah', we'll get
      (f x) ~ (f x) |> co |> sym co

    and we really want to spot that the co/sym-co cancels out.
    Hence
      * We keep an invariant that the MCoercion is always MRefl
        if the MCoercion is reflexive
      * We maintain this invariant via the call to checkReflexiveMCo
        in the Cast case of 'match'.
    -}

    -------------
    matchTemplateCast
        :: RuleMatchEnv -> RuleSubst
        -> CoreExpr -> Coercion
        -> CoreExpr -> MCoercion
        -> Maybe RuleSubst
    matchTemplateCast :: RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> Coercion
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    matchTemplateCast RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 Coercion
    co1 CoreExpr
    e2 MCoercion
    mco
      | VarSet -> Bool
    isEmptyVarSet (VarSet -> Bool) -> VarSet -> Bool
    forall a b. (a -> b) -> a -> b
    $ FV -> VarSet
    fvVarSet (FV -> VarSet) -> FV -> VarSet
    forall a b. (a -> b) -> a -> b
    $
        (Var -> Bool) -> FV -> FV
    filterFV (Var -> VarSet -> Bool
    `elemVarSet` RuleMatchEnv -> VarSet
    rv_tmpls RuleMatchEnv
    renv) (FV -> FV) -> FV -> FV
    forall a b. (a -> b) -> a -> b
    $    -- Check that the coercion does not
        Coercion -> FV
    tyCoFVsOfCo Coercion
    substed_co                     -- mention any of the template variables
      = -- This is the good path
        -- See Note [Casts in the template]
        RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    subst CoreExpr
    e1 CoreExpr
    e2 (MCoercion -> MCoercion
    checkReflexiveMCo (MCoercion -> Coercion -> MCoercion
    mkTransMCoL MCoercion
    mco (Coercion -> Coercion
    mkSymCo Coercion
    substed_co)))

      | Bool
    otherwise
      = -- This is the Deeply Suspicious Path
        do { let co2 :: Coercion
    co2 = case MCoercion
    mco of
                         MCoercion
    MRefl   -> Kind -> Coercion
    mkRepReflCo (HasDebugCallStack => CoreExpr -> Kind
    CoreExpr -> Kind
    exprType CoreExpr
    e2)
                         MCo Coercion
    co2 -> Coercion
    co2
           ; subst1 <- RuleMatchEnv
    -> RuleSubst -> Coercion -> Coercion -> Maybe RuleSubst
    match_co RuleMatchEnv
    renv RuleSubst
    subst Coercion
    co1 Coercion
    co2
             -- If match_co succeeds, then (exprType e1) = (exprType e2)
             -- Hence the MRefl in the next line
           ; match renv subst1 e1 e2 MRefl }
      where
        substed_co :: Coercion
    substed_co = HasDebugCallStack => Subst -> Coercion -> Coercion
    Subst -> Coercion -> Coercion
    substCo Subst
    current_subst Coercion
    co1

        current_subst :: Subst
        current_subst :: Subst
    current_subst = InScopeSet -> TvSubstEnv -> CvSubstEnv -> Subst
    mkTCvSubst (RnEnv2 -> InScopeSet
    rnInScopeSet (RuleMatchEnv -> RnEnv2
    rv_lcl RuleMatchEnv
    renv))
                                   (RuleSubst -> TvSubstEnv
    rs_tv_subst RuleSubst
    subst)
                                   CvSubstEnv
    emptyCvSubstEnv
           -- emptyCvSubstEnv: ugh!
           -- If there were any CoVar substitutions they would be in
           -- rs_id_subst; but we don't expect there to be any; see
           -- Note [Casts in the template]

    match_co :: RuleMatchEnv
             -> RuleSubst
             -> Coercion
             -> Coercion
             -> Maybe RuleSubst
    -- We only match if the template is a coercion variable or Refl:
    --   see Note [Casts in the template]
    -- Like 'match' it is /not/ guaranteed that
    --     coercionKind template  =  coercionKind target
    -- But if match_co succeeds, it /is/ guaranteed that
    --     coercionKind (subst template) = coercionKind target

    match_co :: RuleMatchEnv
    -> RuleSubst -> Coercion -> Coercion -> Maybe RuleSubst
    match_co RuleMatchEnv
    renv RuleSubst
    subst Coercion
    co1 Coercion
    co2
      | Just Var
    cv <- Coercion -> Maybe Var
    getCoVar_maybe Coercion
    co1
      = RuleMatchEnv -> RuleSubst -> Var -> CoreExpr -> Maybe RuleSubst
    match_var RuleMatchEnv
    renv RuleSubst
    subst Var
    cv (Coercion -> CoreExpr
    forall b. Coercion -> Expr b
    Coercion Coercion
    co2)

      | Just (Kind
    ty1, Role
    r1) <- Coercion -> Maybe (Kind, Role)
    isReflCo_maybe Coercion
    co1
      = do { (ty2, r2) <- Coercion -> Maybe (Kind, Role)
    isReflCo_maybe Coercion
    co2
           ; guard (r1 == r2)
           ; match_ty renv subst ty1 ty2 }

      | Bool
    debugIsOn
      = String -> SDoc -> Maybe RuleSubst -> Maybe RuleSubst
    forall a. String -> SDoc -> a -> a
    pprTrace String
    "match_co: needs more cases" (Coercion -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Coercion
    co1 SDoc -> SDoc -> SDoc
    forall doc. IsDoc doc => doc -> doc -> doc
    $$ Coercion -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr Coercion
    co2) Maybe RuleSubst
    forall a. Maybe a
    Nothing
        -- Currently just deals with CoVarCo and Refl

      | Bool
    otherwise
      = Maybe RuleSubst
    forall a. Maybe a
    Nothing

    -------------
    rnMatchBndr2 :: RuleMatchEnv -> Var -> Var -> RuleMatchEnv
    rnMatchBndr2 :: RuleMatchEnv -> Var -> Var -> RuleMatchEnv
    rnMatchBndr2 RuleMatchEnv
    renv Var
    x1 Var
    x2
      = RuleMatchEnv
    renv { rv_lcl  = rnBndr2 (rv_lcl renv) x1 x2
             , rv_fltR = delBndr (rv_fltR renv) x2 }

    ------------------------------------------
    match_alts :: RuleMatchEnv
               -> RuleSubst
               -> [CoreAlt]                 -- Template
               -> [CoreAlt] -> MCoercion    -- Target
               -> Maybe RuleSubst
    match_alts :: RuleMatchEnv
    -> RuleSubst
    -> [Alt Var]
    -> [Alt Var]
    -> MCoercion
    -> Maybe RuleSubst
    match_alts RuleMatchEnv
    _ RuleSubst
    subst [] [] MCoercion
    _
      = RuleSubst -> Maybe RuleSubst
    forall a. a -> Maybe a
    forall (m :: * -> *) a. Monad m => a -> m a
    return RuleSubst
    subst
    match_alts RuleMatchEnv
    renv RuleSubst
    subst (Alt AltCon
    c1 [Var]
    vs1 CoreExpr
    r1:[Alt Var]
    alts1) (Alt AltCon
    c2 [Var]
    vs2 CoreExpr
    r2:[Alt Var]
    alts2) MCoercion
    mco
      | AltCon
    c1 AltCon -> AltCon -> Bool
    forall a. Eq a => a -> a -> Bool
    == AltCon
    c2
      = do  { subst1 <- RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv' RuleSubst
    subst CoreExpr
    r1 CoreExpr
    r2 MCoercion
    mco
            ; match_alts renv subst1 alts1 alts2 mco }
      where
        renv' :: RuleMatchEnv
    renv' = (RuleMatchEnv -> (Var, Var) -> RuleMatchEnv)
    -> RuleMatchEnv -> [(Var, Var)] -> RuleMatchEnv
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' RuleMatchEnv -> (Var, Var) -> RuleMatchEnv
    mb RuleMatchEnv
    renv ([Var]
    vs1 [Var] -> [Var] -> [(Var, Var)]
    forall a b. [a] -> [b] -> [(a, b)]
    `zip` [Var]
    vs2)
        mb :: RuleMatchEnv -> (Var, Var) -> RuleMatchEnv
    mb RuleMatchEnv
    renv (Var
    v1,Var
    v2) = RuleMatchEnv -> Var -> Var -> RuleMatchEnv
    rnMatchBndr2 RuleMatchEnv
    renv Var
    v1 Var
    v2

    match_alts RuleMatchEnv
    _ RuleSubst
    _ [Alt Var]
    _ [Alt Var]
    _ MCoercion
    _
      = Maybe RuleSubst
    forall a. Maybe a
    Nothing

    ------------------------------------------
    okToFloat :: RnEnv2 -> VarSet -> Bool
    okToFloat :: RnEnv2 -> VarSet -> Bool
    okToFloat RnEnv2
    rn_env VarSet
    bind_fvs
      = (Var -> Bool) -> VarSet -> Bool
    allVarSet Var -> Bool
    not_captured VarSet
    bind_fvs
      where
        not_captured :: Var -> Bool
    not_captured Var
    fv = Bool -> Bool
    not (RnEnv2 -> Var -> Bool
    inRnEnvR RnEnv2
    rn_env Var
    fv)

    ------------------------------------------
    match_var :: RuleMatchEnv
              -> RuleSubst
              -> Var        -- Template
              -> CoreExpr   -- Target
              -> Maybe RuleSubst
    match_var :: RuleMatchEnv -> RuleSubst -> Var -> CoreExpr -> Maybe RuleSubst
    match_var renv :: RuleMatchEnv
    renv@(RV { rv_tmpls :: RuleMatchEnv -> VarSet
    rv_tmpls = VarSet
    tmpls, rv_lcl :: RuleMatchEnv -> RnEnv2
    rv_lcl = RnEnv2
    rn_env, rv_fltR :: RuleMatchEnv -> Subst
    rv_fltR = Subst
    flt_env })
              RuleSubst
    subst Var
    v1 CoreExpr
    e2
      | Var
    v1' Var -> VarSet -> Bool
    `elemVarSet` VarSet
    tmpls
      = RuleMatchEnv -> RuleSubst -> Var -> CoreExpr -> Maybe RuleSubst
    match_tmpl_var RuleMatchEnv
    renv RuleSubst
    subst Var
    v1' CoreExpr
    e2

      | Bool
    otherwise   -- v1' is not a template variable; check for an exact match with e2
      = case CoreExpr
    e2 of  -- Remember, envR of rn_env is disjoint from rv_fltR
           Var Var
    v2 | Just Var
    v2' <- RnEnv2 -> Var -> Maybe Var
    rnOccR_maybe RnEnv2
    rn_env Var
    v2
                  -> -- v2 was bound by a nested lambda or case
                     if Var
    v1' Var -> Var -> Bool
    forall a. Eq a => a -> a -> Bool
    == Var
    v2' then RuleSubst -> Maybe RuleSubst
    forall a. a -> Maybe a
    Just RuleSubst
    subst
                                   else Maybe RuleSubst
    forall a. Maybe a
    Nothing

                  -- v2 is not bound nestedly; it is free
                  -- in the whole expression being matched
                  -- So it will be in the InScopeSet for flt_env (#20200)
                  | Var Var
    v2' <- HasDebugCallStack => Subst -> Var -> CoreExpr
    Subst -> Var -> CoreExpr
    lookupIdSubst Subst
    flt_env Var
    v2
                  , Var
    v1' Var -> Var -> Bool
    forall a. Eq a => a -> a -> Bool
    == Var
    v2'
                  -> RuleSubst -> Maybe RuleSubst
    forall a. a -> Maybe a
    Just RuleSubst
    subst
                  | Bool
    otherwise
                  -> Maybe RuleSubst
    forall a. Maybe a
    Nothing

           CoreExpr
    _ -> Maybe RuleSubst
    forall a. Maybe a
    Nothing

      where
        v1' :: Var
    v1' = RnEnv2 -> Var -> Var
    rnOccL RnEnv2
    rn_env Var
    v1
            -- If the template is
            --      forall x. f x (\x -> x) = ...
            -- Then the x inside the lambda isn't the
            -- template x, so we must rename first!

    ------------------------------------------
    match_tmpl_var :: RuleMatchEnv
                   -> RuleSubst
                   -> Var                -- Template
                   -> CoreExpr           -- Target
                   -> Maybe RuleSubst

    match_tmpl_var :: RuleMatchEnv -> RuleSubst -> Var -> CoreExpr -> Maybe RuleSubst
    match_tmpl_var renv :: RuleMatchEnv
    renv@(RV { rv_lcl :: RuleMatchEnv -> RnEnv2
    rv_lcl = RnEnv2
    rn_env, rv_fltR :: RuleMatchEnv -> Subst
    rv_fltR = Subst
    flt_env })
                   subst :: RuleSubst
    subst@(RS { rs_id_subst :: RuleSubst -> IdSubstEnv
    rs_id_subst = IdSubstEnv
    id_subst, rs_bndrs :: RuleSubst -> [Var]
    rs_bndrs = [Var]
    let_bndrs })
                   Var
    v1' CoreExpr
    e2
      -- anyInRnEnvR is lazy in the 2nd arg which allows us to avoid computing fvs
      -- if the right side of the env is empty.
      | RnEnv2 -> VarSet -> Bool
    anyInRnEnvR RnEnv2
    rn_env (CoreExpr -> VarSet
    exprFreeVars CoreExpr
    e2)
      = Maybe RuleSubst
    forall a. Maybe a
    Nothing     -- Skolem-escape failure
                    -- e.g. match forall a. (\x -> a) against (\y -> y)

      | Just CoreExpr
    e1' <- IdSubstEnv -> Var -> Maybe CoreExpr
    forall a. VarEnv a -> Var -> Maybe a
    lookupVarEnv IdSubstEnv
    id_subst Var
    v1'
      = if CoreExpr -> CoreExpr -> Bool
    eqCoreExpr CoreExpr
    e1' CoreExpr
    e2'
        then RuleSubst -> Maybe RuleSubst
    forall a. a -> Maybe a
    Just RuleSubst
    subst
        else Maybe RuleSubst
    forall a. Maybe a
    Nothing

      | Bool
    otherwise   -- See Note [Matching variable types]
      = do { subst' <- RuleMatchEnv -> RuleSubst -> Kind -> Kind -> Maybe RuleSubst
    match_ty RuleMatchEnv
    renv RuleSubst
    subst (Var -> Kind
    idType Var
    v1') (HasDebugCallStack => CoreExpr -> Kind
    CoreExpr -> Kind
    exprType CoreExpr
    e2)
           ; return (subst' { rs_id_subst = id_subst' }) }
      where
        -- e2' is the result of applying flt_env to e2
        e2' :: CoreExpr
    e2' | [Var] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [Var]
    let_bndrs = CoreExpr
    e2
            | Bool
    otherwise = HasDebugCallStack => Subst -> CoreExpr -> CoreExpr
    Subst -> CoreExpr -> CoreExpr
    substExpr Subst
    flt_env CoreExpr
    e2

        id_subst' :: IdSubstEnv
    id_subst' = IdSubstEnv -> Var -> CoreExpr -> IdSubstEnv
    forall a. VarEnv a -> Var -> a -> VarEnv a
    extendVarEnv (RuleSubst -> IdSubstEnv
    rs_id_subst RuleSubst
    subst) Var
    v1' CoreExpr
    e2'
             -- No further renaming to do on e2',
             -- because no free var of e2' is in the rnEnvR of the envt

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

    match_ty :: RuleMatchEnv
             -> RuleSubst
             -> Type                -- Template
             -> Type                -- Target
             -> Maybe RuleSubst
    -- Matching Core types: use the matcher in GHC.Tc.Utils.TcType.
    -- Notice that we treat newtypes as opaque.  For example, suppose
    -- we have a specialised version of a function at a newtype, say
    --      newtype T = MkT Int
    -- We only want to replace (f T) with f', not (f Int).

    match_ty :: RuleMatchEnv -> RuleSubst -> Kind -> Kind -> Maybe RuleSubst
    match_ty (RV { rv_tmpls :: RuleMatchEnv -> VarSet
    rv_tmpls = VarSet
    tmpls, rv_lcl :: RuleMatchEnv -> RnEnv2
    rv_lcl = RnEnv2
    rn_env })
             subst :: RuleSubst
    subst@(RS { rs_tv_subst :: RuleSubst -> TvSubstEnv
    rs_tv_subst = TvSubstEnv
    tv_subst })
             Kind
    ty1 Kind
    ty2
      = do  { tv_subst' <- VarSet -> RnEnv2 -> TvSubstEnv -> Kind -> Kind -> Maybe TvSubstEnv
    Unify.ruleMatchTyKiX VarSet
    tmpls RnEnv2
    rn_env TvSubstEnv
    tv_subst Kind
    ty1 Kind
    ty2
                   -- NB: ruleMatchTyKiX applis tv_subst to ty1 only
                   --     and of course only binds 'tmpls'
            ; return (subst { rs_tv_subst = tv_subst' }) }

    {- Note [Matching variable types]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    When matching x ~ e, where 'x' is a template variable, we must check that
    x's type matches e's type, to establish (TypeInv).  For example
      forall (c::Char->Int) (x::Char).
         f (c x) = "RULE FIRED"
    We must not match on, say (f (pred (3::Int))).

    It's actually quite difficult to come up with an example that shows
    you need type matching, esp since matching is left-to-right, so type
    args get matched first.  But it's possible (e.g. simplrun008) and this
    is the Right Thing to do.

    An alternative would be to make (TypeInf) into a /pre-condition/.  It
    is threatened only by the App rule.  So when matching an application
    (e1 e2) ~ (d1 d2) would be to collect args of the application chain,
    match the types of the head, then match arg-by-arg.

    However that alternative seems a bit more complicated.  And by
    matching types at variables we do one match_ty for each template
    variable, rather than one for each application chain.  Usually there are
    fewer template variables, although for simple rules it could be the other
    way around.

    Note [Expanding variables]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~
    Here is another Very Important rule: if the term being matched is a
    variable, we expand it so long as its unfolding is "expandable". (Its
    occurrence information is not necessarily up to date, so we don't use
    it.)  By "expandable" we mean a WHNF or a "constructor-like" application.
    This is the key reason for "constructor-like" Ids.  If we have
         {-# NOINLINE [1] CONLIKE g #-}
         {-# RULE f (g x) = h x #-}
    then in the term
       let v = g 3 in ....(f v)....
    we want to make the rule fire, to replace (f v) with (h 3).

    Note [Do not expand locally-bound variables]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Do *not* expand locally-bound variables, else there's a worry that the
    unfolding might mention variables that are themselves renamed.
    Example
              case x of y { (p,q) -> ...y... }
    Don't expand 'y' to (p,q) because p,q might themselves have been
    renamed.  Essentially we only expand unfoldings that are "outside"
    the entire match.

    Hence, (a) the guard (not (isLocallyBoundR v2))
           (b) when we expand we nuke the renaming envt (nukeRnEnvR).

    Note [Tick annotations in RULE matching]
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    We used to unconditionally look through ticks in both template and
    expression being matched. This is actually illegal for counting or
    cost-centre-scoped ticks, because we have no place to put them without
    changing entry counts and/or costs. So now we just fail the match in
    these cases.

    On the other hand, where we are allowed to insert new cost into the
    tick scope, we can float them upwards to the rule application site.

    Moreover, we may encounter ticks in the template of a rule. There are a few
    ways in which these may be introduced (e.g. #18162, #17619). Such ticks are
    ignored by the matcher. See Note [Simplifying rules] in
    GHC.Core.Opt.Simplify.Utils for details.

    cf Note [Tick annotations in call patterns] in GHC.Core.Opt.SpecConstr

    Note [Matching lets]
    ~~~~~~~~~~~~~~~~~~~~
    Matching a let-expression.  Consider
            RULE forall x.  f (g x) = <rhs>
    and target expression
            f (let { w=R } in g E))
    Then we'd like the rule to match, to generate
            let { w=R } in (\x. <rhs>) E
    In effect, we want to float the let-binding outward, to enable
    the match to happen.  This is the WHOLE REASON for accumulating
    bindings in the RuleSubst

    We can only do this if the free variables of R are not bound by the
    part of the target expression outside the let binding; e.g.
            f (\v. let w = v+1 in g E)
    Here we obviously cannot float the let-binding for w.  Hence the
    use of okToFloat.

    There are a couple of tricky points:
      (a) What if floating the binding captures a variable that is
          free in the entire expression?
            f (let v = x+1 in v) v
          --> NOT!
            let v = x+1 in f (x+1) v

      (b) What if the let shadows a local binding?
            f (\v -> (v, let v = x+1 in (v,v))
          --> NOT!
            let v = x+1 in f (\v -> (v, (v,v)))

      (c) What if two non-nested let bindings bind the same variable?
            f (let v = e1 in b1) (let v = e2 in b2)
          --> NOT!
            let v = e1 in let v = e2 in (f b2 b2)
          See testsuite test `T4814`.

    Our cunning plan is this:
      (1) Along with the growing substitution for template variables
          we maintain a growing set of floated let-bindings (rs_binds)
          plus the set of variables thus bound (rs_bndrs).

      (2) The RnEnv2 in the MatchEnv binds only the local binders
          in the term (lambdas, case), not the floated let-bndrs.

      (3) When we encounter a `let` in the term to be matched, in the Let
          case of `match`, we use `okToFloat` to check that it does not mention any
          locally bound (lambda, case) variables.  If so we fail.

      (4) In the Let case of `match`, we use GHC.Core.Subst.substBind to
          freshen the binding (which, remember (3), mentions no locally
          bound variables), in a lexically-scoped way (via rv_fltR in
          MatchEnv).

          The subtle point is that we want an in-scope set for this
          substitution that includes /two/ sets:
          * The in-scope variables at this point, so that we avoid using
            those local names for the floated binding; points (a) and (b) above.
          * All "earlier" floated bindings, so that we avoid using the
            same name for two different floated bindings; point (c) above.

          Because we have to compute the in-scope set here, the in-scope set
          stored in `rv_fltR` is always ignored; we leave it only because it's
          convenient to have `rv_fltR :: Subst` (with an always-ignored `InScopeSet`)
          rather than storing three separate substitutions.

      (5) We apply that freshening substitution, in a lexically-scoped
          way to the term, although lazily; this is the rv_fltR field.

    See #4814, which is an issue resulting from getting this wrong.

    Note [Matching cases]
    ~~~~~~~~~~~~~~~~~~~~~
    {- NOTE: This idea is currently disabled.  It really only works if
             the primops involved are OkForSpeculation, and, since
             they have side effects readIntOfAddr and touch are not.
             Maybe we'll get back to this later .  -}

    Consider
       f (case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
          case touch# fp s# of { _ ->
          I# n# } } )
    This happened in a tight loop generated by stream fusion that
    Roman encountered.  We'd like to treat this just like the let
    case, because the primops concerned are ok-for-speculation.
    That is, we'd like to behave as if it had been
       case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
       case touch# fp s# of { _ ->
       f (I# n# } } )

    Note [Lookup in-scope]
    ~~~~~~~~~~~~~~~~~~~~~~
    Consider this example
            foo :: Int -> Maybe Int -> Int
            foo 0 (Just n) = n
            foo m (Just n) = foo (m-n) (Just n)

    SpecConstr sees this fragment:

            case w_smT of wild_Xf [Just A] {
              Data.Maybe.Nothing -> lvl_smf;
              Data.Maybe.Just n_acT [Just S(L)] ->
                case n_acT of wild1_ams [Just A] { GHC.Base.I# y_amr [Just L] ->
                  $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf
                }};

    and correctly generates the rule

            RULES: "SC:$wfoo1" [0] __forall {y_amr [Just L] :: GHC.Prim.Int#
                                              sc_snn :: GHC.Prim.Int#}
              $wfoo_smW sc_snn (Data.Maybe.Just @ GHC.Base.Int (GHC.Base.I# y_amr))
              = $s$wfoo_sno y_amr sc_snn ;]

    BUT we must ensure that this rule matches in the original function!
    Note that the call to $wfoo is
                $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf

    During matching we expand wild_Xf to (Just n_acT).  But then we must also
    expand n_acT to (I# y_amr).  And we can only do that if we look up n_acT
    in the in-scope set, because in wild_Xf's unfolding it won't have an unfolding
    at all.

    That is why the 'lookupRnInScope' call in the (Var v2) case of 'match'
    is so important.

    ************************************************************************
    *                                                                      *
                       Rule-check the program
    *                                                                      *
    ************************************************************************

       We want to know what sites have rules that could have fired but didn't.
       This pass runs over the tree (without changing it) and reports such.
    -}

    -- | Report partial matches for rules beginning with the specified
    -- string for the purposes of error reporting
    ruleCheckProgram :: RuleOpts                    -- ^ Rule options
                     -> CompilerPhase               -- ^ Rule activation test
                     -> String                      -- ^ Rule pattern
                     -> (Id -> [CoreRule])          -- ^ Rules for an Id
                     -> CoreProgram                 -- ^ Bindings to check in
                     -> SDoc                        -- ^ Resulting check message
    ruleCheckProgram :: RuleOpts
    -> CompilerPhase
    -> String
    -> (Var -> [CoreRule])
    -> [CoreBind]
    -> SDoc
    ruleCheckProgram RuleOpts
    ropts CompilerPhase
    phase String
    rule_pat Var -> [CoreRule]
    rules [CoreBind]
    binds
      | Bag SDoc -> Bool
    forall a. Bag a -> Bool
    isEmptyBag Bag SDoc
    results
      = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Rule check results: no rule application sites"
      | Bool
    otherwise
      = [SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat [String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Rule check results:",
              SDoc
    line,
              [SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat [ SDoc
    p SDoc -> SDoc -> SDoc
    forall doc. IsDoc doc => doc -> doc -> doc
    $$ SDoc
    line | SDoc
    p <- Bag SDoc -> [SDoc]
    forall a. Bag a -> [a]
    bagToList Bag SDoc
    results ]
             ]
      where
        line :: SDoc
    line = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text (Arity -> Char -> String
    forall a. Arity -> a -> [a]
    replicate Arity
    20 Char
    '-')
        env :: RuleCheckEnv
    env = RuleCheckEnv { rc_is_active :: Activation -> Bool
    rc_is_active = CompilerPhase -> Activation -> Bool
    isActive CompilerPhase
    phase
                           , rc_id_unf :: IdUnfoldingFun
    rc_id_unf    = IdUnfoldingFun
    idUnfolding     -- Not quite right
                                                            -- Should use activeUnfolding
                           , rc_pattern :: String
    rc_pattern   = String
    rule_pat
                           , rc_rules :: Var -> [CoreRule]
    rc_rules     = Var -> [CoreRule]
    rules
                           , rc_ropts :: RuleOpts
    rc_ropts     = RuleOpts
    ropts
                           , rc_in_scope :: InScopeSet
    rc_in_scope  = InScopeSet
    emptyInScopeSet }

        results :: Bag SDoc
    results = RuleCheckEnv -> [CoreBind] -> Bag SDoc
    go RuleCheckEnv
    env [CoreBind]
    binds

        go :: RuleCheckEnv -> [CoreBind] -> Bag SDoc
    go RuleCheckEnv
    _   []           = Bag SDoc
    forall a. Bag a
    emptyBag
        go RuleCheckEnv
    env (CoreBind
    bind:[CoreBind]
    binds) = let (RuleCheckEnv
    env', Bag SDoc
    ds) = RuleCheckEnv -> CoreBind -> (RuleCheckEnv, Bag SDoc)
    ruleCheckBind RuleCheckEnv
    env CoreBind
    bind
                              in Bag SDoc
    ds Bag SDoc -> Bag SDoc -> Bag SDoc
    forall a. Bag a -> Bag a -> Bag a
    `unionBags` RuleCheckEnv -> [CoreBind] -> Bag SDoc
    go RuleCheckEnv
    env' [CoreBind]
    binds

    data RuleCheckEnv = RuleCheckEnv
        { RuleCheckEnv -> Activation -> Bool
    rc_is_active :: Activation -> Bool
        , RuleCheckEnv -> IdUnfoldingFun
    rc_id_unf    :: IdUnfoldingFun
        , RuleCheckEnv -> String
    rc_pattern   :: String
        , RuleCheckEnv -> Var -> [CoreRule]
    rc_rules     :: Id -> [CoreRule]
        , RuleCheckEnv -> RuleOpts
    rc_ropts     :: RuleOpts
        , RuleCheckEnv -> InScopeSet
    rc_in_scope  :: InScopeSet }

    extendInScopeRC :: RuleCheckEnv -> Var -> RuleCheckEnv
    extendInScopeRC :: RuleCheckEnv -> Var -> RuleCheckEnv
    extendInScopeRC env :: RuleCheckEnv
    env@(RuleCheckEnv { rc_in_scope :: RuleCheckEnv -> InScopeSet
    rc_in_scope = InScopeSet
    in_scope }) Var
    v
      = RuleCheckEnv
    env { rc_in_scope = in_scope `extendInScopeSet` v }

    extendInScopeListRC :: RuleCheckEnv -> [Var] -> RuleCheckEnv
    extendInScopeListRC :: RuleCheckEnv -> [Var] -> RuleCheckEnv
    extendInScopeListRC env :: RuleCheckEnv
    env@(RuleCheckEnv { rc_in_scope :: RuleCheckEnv -> InScopeSet
    rc_in_scope = InScopeSet
    in_scope }) [Var]
    vs
      = RuleCheckEnv
    env { rc_in_scope = in_scope `extendInScopeSetList` vs }

    ruleCheckBind :: RuleCheckEnv -> CoreBind -> (RuleCheckEnv, Bag SDoc)
       -- The Bag returned has one SDoc for each call site found
    ruleCheckBind :: RuleCheckEnv -> CoreBind -> (RuleCheckEnv, Bag SDoc)
    ruleCheckBind RuleCheckEnv
    env (NonRec Var
    b CoreExpr
    r) = (RuleCheckEnv
    env RuleCheckEnv -> Var -> RuleCheckEnv
    `extendInScopeRC` Var
    b, RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env CoreExpr
    r)
    ruleCheckBind RuleCheckEnv
    env (Rec [(Var, CoreExpr)]
    prs)    = (RuleCheckEnv
    env', [Bag SDoc] -> Bag SDoc
    forall a. [Bag a] -> Bag a
    unionManyBags ((CoreExpr -> Bag SDoc) -> [CoreExpr] -> [Bag SDoc]
    forall a b. (a -> b) -> [a] -> [b]
    map (RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env') [CoreExpr]
    rhss))
                                   where
                                     ([Var]
    bs, [CoreExpr]
    rhss) = [(Var, CoreExpr)] -> ([Var], [CoreExpr])
    forall a b. [(a, b)] -> ([a], [b])
    unzip [(Var, CoreExpr)]
    prs
                                     env' :: RuleCheckEnv
    env' = RuleCheckEnv
    env RuleCheckEnv -> [Var] -> RuleCheckEnv
    `extendInScopeListRC` [Var]
    bs

    ruleCheck :: RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck :: RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    _   (Var Var
    _)         = Bag SDoc
    forall a. Bag a
    emptyBag
    ruleCheck RuleCheckEnv
    _   (Lit Literal
    _)         = Bag SDoc
    forall a. Bag a
    emptyBag
    ruleCheck RuleCheckEnv
    _   (Type Kind
    _)        = Bag SDoc
    forall a. Bag a
    emptyBag
    ruleCheck RuleCheckEnv
    _   (Coercion Coercion
    _)    = Bag SDoc
    forall a. Bag a
    emptyBag
    ruleCheck RuleCheckEnv
    env (App CoreExpr
    f CoreExpr
    a)       = RuleCheckEnv -> CoreExpr -> [CoreExpr] -> Bag SDoc
    ruleCheckApp RuleCheckEnv
    env (CoreExpr -> CoreExpr -> CoreExpr
    forall b. Expr b -> Expr b -> Expr b
    App CoreExpr
    f CoreExpr
    a) []
    ruleCheck RuleCheckEnv
    env (Tick CoreTickish
    _ CoreExpr
    e)      = RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env CoreExpr
    e
    ruleCheck RuleCheckEnv
    env (Cast CoreExpr
    e Coercion
    _)      = RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env CoreExpr
    e
    ruleCheck RuleCheckEnv
    env (Let CoreBind
    bd CoreExpr
    e)      = let (RuleCheckEnv
    env', Bag SDoc
    ds) = RuleCheckEnv -> CoreBind -> (RuleCheckEnv, Bag SDoc)
    ruleCheckBind RuleCheckEnv
    env CoreBind
    bd
                                    in  Bag SDoc
    ds Bag SDoc -> Bag SDoc -> Bag SDoc
    forall a. Bag a -> Bag a -> Bag a
    `unionBags` RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env' CoreExpr
    e
    ruleCheck RuleCheckEnv
    env (Lam Var
    b CoreExpr
    e)       = RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck (RuleCheckEnv
    env RuleCheckEnv -> Var -> RuleCheckEnv
    `extendInScopeRC` Var
    b) CoreExpr
    e
    ruleCheck RuleCheckEnv
    env (Case CoreExpr
    e Var
    b Kind
    _ [Alt Var]
    as) = RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env CoreExpr
    e Bag SDoc -> Bag SDoc -> Bag SDoc
    forall a. Bag a -> Bag a -> Bag a
    `unionBags`
                                    [Bag SDoc] -> Bag SDoc
    forall a. [Bag a] -> Bag a
    unionManyBags [RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck (RuleCheckEnv
    env RuleCheckEnv -> [Var] -> RuleCheckEnv
    `extendInScopeListRC` (Var
    bVar -> [Var] -> [Var]
    forall a. a -> [a] -> [a]
    :[Var]
    bs)) CoreExpr
    r
                                                  | Alt AltCon
    _ [Var]
    bs CoreExpr
    r <- [Alt Var]
    as]

    ruleCheckApp :: RuleCheckEnv -> Expr CoreBndr -> [Arg CoreBndr] -> Bag SDoc
    ruleCheckApp :: RuleCheckEnv -> CoreExpr -> [CoreExpr] -> Bag SDoc
    ruleCheckApp RuleCheckEnv
    env (App CoreExpr
    f CoreExpr
    a) [CoreExpr]
    as = RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env CoreExpr
    a Bag SDoc -> Bag SDoc -> Bag SDoc
    forall a. Bag a -> Bag a -> Bag a
    `unionBags` RuleCheckEnv -> CoreExpr -> [CoreExpr] -> Bag SDoc
    ruleCheckApp RuleCheckEnv
    env CoreExpr
    f (CoreExpr
    aCoreExpr -> [CoreExpr] -> [CoreExpr]
    forall a. a -> [a] -> [a]
    :[CoreExpr]
    as)
    ruleCheckApp RuleCheckEnv
    env (Var Var
    f) [CoreExpr]
    as   = RuleCheckEnv -> Var -> [CoreExpr] -> Bag SDoc
    ruleCheckFun RuleCheckEnv
    env Var
    f [CoreExpr]
    as
    ruleCheckApp RuleCheckEnv
    env CoreExpr
    other [CoreExpr]
    _      = RuleCheckEnv -> CoreExpr -> Bag SDoc
    ruleCheck RuleCheckEnv
    env CoreExpr
    other

    ruleCheckFun :: RuleCheckEnv -> Id -> [CoreExpr] -> Bag SDoc
    -- Produce a report for all rules matching the predicate
    -- saying why it doesn't match the specified application

    ruleCheckFun :: RuleCheckEnv -> Var -> [CoreExpr] -> Bag SDoc
    ruleCheckFun RuleCheckEnv
    env Var
    fn [CoreExpr]
    args
      | [CoreRule] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [CoreRule]
    name_match_rules = Bag SDoc
    forall a. Bag a
    emptyBag
      | Bool
    otherwise             = SDoc -> Bag SDoc
    forall a. a -> Bag a
    unitBag (RuleCheckEnv -> Var -> [CoreExpr] -> [CoreRule] -> SDoc
    ruleAppCheck_help RuleCheckEnv
    env Var
    fn [CoreExpr]
    args [CoreRule]
    name_match_rules)
      where
        name_match_rules :: [CoreRule]
    name_match_rules = (CoreRule -> Bool) -> [CoreRule] -> [CoreRule]
    forall a. (a -> Bool) -> [a] -> [a]
    filter CoreRule -> Bool
    match (RuleCheckEnv -> Var -> [CoreRule]
    rc_rules RuleCheckEnv
    env Var
    fn)
        match :: CoreRule -> Bool
    match CoreRule
    rule = RuleCheckEnv -> String
    rc_pattern RuleCheckEnv
    env String -> String -> Bool
    forall a. Eq a => [a] -> [a] -> Bool
    `isPrefixOf` RuleName -> String
    unpackFS (CoreRule -> RuleName
    ruleName CoreRule
    rule)

    ruleAppCheck_help :: RuleCheckEnv -> Id -> [CoreExpr] -> [CoreRule] -> SDoc
    ruleAppCheck_help :: RuleCheckEnv -> Var -> [CoreExpr] -> [CoreRule] -> SDoc
    ruleAppCheck_help RuleCheckEnv
    env Var
    fn [CoreExpr]
    args [CoreRule]
    rules
      =     -- The rules match the pattern, so we want to print something
        [SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat [String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "Expression:" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> CoreExpr -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr (CoreExpr -> [CoreExpr] -> CoreExpr
    forall b. Expr b -> [Expr b] -> Expr b
    mkApps (Var -> CoreExpr
    forall b. Var -> Expr b
    Var Var
    fn) [CoreExpr]
    args),
              [SDoc] -> SDoc
    forall doc. IsDoc doc => [doc] -> doc
    vcat ((CoreRule -> SDoc) -> [CoreRule] -> [SDoc]
    forall a b. (a -> b) -> [a] -> [b]
    map CoreRule -> SDoc
    check_rule [CoreRule]
    rules)]
      where
        in_scope :: InScopeSet
    in_scope = RuleCheckEnv -> InScopeSet
    rc_in_scope RuleCheckEnv
    env
        n_args :: Arity
    n_args   = [CoreExpr] -> Arity
    forall a. [a] -> Arity
    forall (t :: * -> *) a. Foldable t => t a -> Arity
    length [CoreExpr]
    args
        i_args :: [(CoreExpr, Arity)]
    i_args   = [CoreExpr]
    args [CoreExpr] -> [Arity] -> [(CoreExpr, Arity)]
    forall a b. [a] -> [b] -> [(a, b)]
    `zip` [Arity
    1::Int ..]
        rough_args :: [Maybe Name]
    rough_args = (CoreExpr -> Maybe Name) -> [CoreExpr] -> [Maybe Name]
    forall a b. (a -> b) -> [a] -> [b]
    map CoreExpr -> Maybe Name
    roughTopName [CoreExpr]
    args

        check_rule :: CoreRule -> SDoc
    check_rule CoreRule
    rule = CoreRule -> SDoc
    forall {doc}. IsLine doc => CoreRule -> doc
    rule_herald CoreRule
    rule SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <> SDoc
    forall doc. IsLine doc => doc
    colon SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> RuleOpts -> CoreRule -> SDoc
    rule_info (RuleCheckEnv -> RuleOpts
    rc_ropts RuleCheckEnv
    env) CoreRule
    rule

        rule_herald :: CoreRule -> doc
    rule_herald (BuiltinRule { ru_name :: CoreRule -> RuleName
    ru_name = RuleName
    name })
            = String -> doc
    forall doc. IsLine doc => String -> doc
    text String
    "Builtin rule" doc -> doc -> doc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> doc -> doc
    forall doc. IsLine doc => doc -> doc
    doubleQuotes (RuleName -> doc
    forall doc. IsLine doc => RuleName -> doc
    ftext RuleName
    name)
        rule_herald (Rule { ru_name :: CoreRule -> RuleName
    ru_name = RuleName
    name })
            = String -> doc
    forall doc. IsLine doc => String -> doc
    text String
    "Rule" doc -> doc -> doc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> doc -> doc
    forall doc. IsLine doc => doc -> doc
    doubleQuotes (RuleName -> doc
    forall doc. IsLine doc => RuleName -> doc
    ftext RuleName
    name)

        rule_info :: RuleOpts -> CoreRule -> SDoc
    rule_info RuleOpts
    opts CoreRule
    rule
            | Just CoreExpr
    _ <- RuleOpts
    -> InScopeEnv
    -> (Activation -> Bool)
    -> Var
    -> [CoreExpr]
    -> [Maybe Name]
    -> CoreRule
    -> Maybe CoreExpr
    matchRule RuleOpts
    opts (InScopeSet -> IdUnfoldingFun -> InScopeEnv
    ISE InScopeSet
    emptyInScopeSet (RuleCheckEnv -> IdUnfoldingFun
    rc_id_unf RuleCheckEnv
    env))
                                  Activation -> Bool
    noBlackList Var
    fn [CoreExpr]
    args [Maybe Name]
    rough_args CoreRule
    rule
            = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "matches (which is very peculiar!)"

        rule_info RuleOpts
    _ (BuiltinRule {}) = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "does not match"

        rule_info RuleOpts
    _ (Rule { ru_act :: CoreRule -> Activation
    ru_act = Activation
    act,
                            ru_bndrs :: CoreRule -> [Var]
    ru_bndrs = [Var]
    rule_bndrs, ru_args :: CoreRule -> [CoreExpr]
    ru_args = [CoreExpr]
    rule_args})
            | Bool -> Bool
    not (RuleCheckEnv -> Activation -> Bool
    rc_is_active RuleCheckEnv
    env Activation
    act)  = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "active only in later phase"
            | Arity
    n_args Arity -> Arity -> Bool
    forall a. Ord a => a -> a -> Bool
    < Arity
    n_rule_args        = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "too few arguments"
            | Arity
    n_mismatches Arity -> Arity -> Bool
    forall a. Eq a => a -> a -> Bool
    == Arity
    n_rule_args = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "no arguments match"
            | Arity
    n_mismatches Arity -> Arity -> Bool
    forall a. Eq a => a -> a -> Bool
    == Arity
    0           = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "all arguments match (considered individually), but rule as a whole does not"
            | Bool
    otherwise                   = String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "arguments" SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> [Arity] -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr [Arity]
    mismatches SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> String -> SDoc
    forall doc. IsLine doc => String -> doc
    text String
    "do not match (1-indexing)"
            where
              n_rule_args :: Arity
    n_rule_args  = [CoreExpr] -> Arity
    forall a. [a] -> Arity
    forall (t :: * -> *) a. Foldable t => t a -> Arity
    length [CoreExpr]
    rule_args
              n_mismatches :: Arity
    n_mismatches = [Arity] -> Arity
    forall a. [a] -> Arity
    forall (t :: * -> *) a. Foldable t => t a -> Arity
    length [Arity]
    mismatches
              mismatches :: [Arity]
    mismatches   = [Arity
    i | (CoreExpr
    rule_arg, (CoreExpr
    arg,Arity
    i)) <- [CoreExpr]
    rule_args [CoreExpr]
    -> [(CoreExpr, Arity)] -> [(CoreExpr, (CoreExpr, Arity))]
    forall a b. [a] -> [b] -> [(a, b)]
    `zip` [(CoreExpr, Arity)]
    i_args,
                                  Bool -> Bool
    not (Maybe RuleSubst -> Bool
    forall a. Maybe a -> Bool
    isJust (CoreExpr -> CoreExpr -> Maybe RuleSubst
    match_fn CoreExpr
    rule_arg CoreExpr
    arg))]

              match_fn :: CoreExpr -> CoreExpr -> Maybe RuleSubst
    match_fn CoreExpr
    rule_arg CoreExpr
    arg = RuleMatchEnv
    -> RuleSubst
    -> CoreExpr
    -> CoreExpr
    -> MCoercion
    -> Maybe RuleSubst
    match RuleMatchEnv
    renv RuleSubst
    emptyRuleSubst CoreExpr
    rule_arg CoreExpr
    arg MCoercion
    MRefl
                    where
                      renv :: RuleMatchEnv
    renv = RV { rv_lcl :: RnEnv2
    rv_lcl   = InScopeSet -> RnEnv2
    mkRnEnv2 InScopeSet
    in_scope
                                , rv_tmpls :: VarSet
    rv_tmpls = [Var] -> VarSet
    mkVarSet [Var]
    rule_bndrs
                                , rv_fltR :: Subst
    rv_fltR  = InScopeSet -> Subst
    mkEmptySubst InScopeSet
    in_scope
                                , rv_unf :: IdUnfoldingFun
    rv_unf   = RuleCheckEnv -> IdUnfoldingFun
    rc_id_unf RuleCheckEnv
    env }