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

\section[CoreRules]{Transformation rules}
-}

{-# LANGUAGE CPP #-}

-- | Functions for collecting together and applying rewrite rules to a module.
-- The 'CoreRule' datatype itself is declared elsewhere.
module Rules (
        -- ** Constructing
        emptyRuleBase, mkRuleBase, extendRuleBaseList,
        unionRuleBase, pprRuleBase,

        -- ** Checking rule applications
        ruleCheckProgram,

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

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

        lookupRule, mkRule, roughTopNames
    ) where

#include "HsVersions.h"

import GhcPrelude

import CoreSyn          -- All of it
import Module           ( Module, ModuleSet, elemModuleSet )
import CoreSubst
import CoreOpt          ( exprIsLambda_maybe )
import CoreFVs          ( exprFreeVars, exprsFreeVars, bindFreeVars
                        , rulesFreeVarsDSet, exprsOrphNames, exprFreeVarsList )
import CoreUtils        ( exprType, eqExpr, mkTick, mkTicks,
                          stripTicksTopT, stripTicksTopE,
                          isJoinBind )
import PprCore          ( pprRules )
import Type             ( Type, Kind, substTy, mkTCvSubst )
import TcType           ( tcSplitTyConApp_maybe )
import TysWiredIn       ( anyTypeOfKind )
import Coercion
import CoreTidy         ( tidyRules )
import Id
import IdInfo           ( RuleInfo( RuleInfo ) )
import Var
import VarEnv
import VarSet
import Name             ( Name, NamedThing(..), nameIsLocalOrFrom )
import NameSet
import NameEnv
import UniqFM
import Unify            ( ruleMatchTyKiX )
import BasicTypes
import DynFlags         ( DynFlags )
import Outputable
import FastString
import Maybes
import Bag
import Util
import Data.List
import Data.Ord
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
     DsBinds

* TidyPgm 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 CoreMonad.
  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 combing 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, we combine (b-d) into a single
  RuleBase, reading
     (b) from the ModGuts,
     (c) from the CoreMonad, and
     (d) from its mutable variable
  [Of coures this means that we won't see new EPS rules that come in
  during a single simplifier iteration, but that probably does not
  matter.]


************************************************************************
*                                                                      *
\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@ contains the mapping:
\begin{verbatim}
        forall a b d. [Type (List a), Type b, Var d]  ===>  f' a b
\end{verbatim}
then when we find an application of f to matching types, we simply replace
it by the matching RHS:
\begin{verbatim}
        f (List Int) Bool dict ===>  f' Int Bool
\end{verbatim}
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.

There is one more exciting case, which is dealt with in exactly the same
way.  If the specialised value is unboxed then it is lifted at its
definition site and unlifted at its uses.  For example:

        pi :: forall a. Num a => a

might have a specialisation

        [Int#] ===>  (case pi' of Lift pi# -> pi#)

where pi' :: Lift Int# is the specialised version of pi.
-}

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 'CoreSyn.CoreRule'
mkRule :: Module
-> Bool
-> Bool
-> RuleName
-> Activation
-> Name
-> [CoreBndr]
-> [CoreExpr]
-> CoreExpr
-> CoreRule
mkRule this_mod :: Module
this_mod is_auto :: Bool
is_auto is_local :: Bool
is_local name :: RuleName
name act :: Activation
act fn :: Name
fn bndrs :: [CoreBndr]
bndrs args :: [CoreExpr]
args rhs :: CoreExpr
rhs
  = $WRule :: RuleName
-> Activation
-> Name
-> [Maybe Name]
-> [CoreBndr]
-> [CoreExpr]
-> CoreExpr
-> Bool
-> Module
-> IsOrphan
-> Bool
-> CoreRule
Rule { ru_name :: RuleName
ru_name = RuleName
name, ru_fn :: Name
ru_fn = Name
fn, ru_act :: Activation
ru_act = Activation
act,
           ru_bndrs :: [CoreBndr]
ru_bndrs = [CoreBndr]
bndrs, ru_args :: [CoreExpr]
ru_args = [CoreExpr]
args,
           ru_rhs :: CoreExpr
ru_rhs = CoreExpr
rhs,
           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 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
exprsOrphNames [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

--------------
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 "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 args :: [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 ty :: Type
ty) = case HasCallStack => Type -> Maybe (TyCon, [Type])
Type -> Maybe (TyCon, [Type])
tcSplitTyConApp_maybe Type
ty of
                               Just (tc :: TyCon
tc,_) -> Name -> Maybe Name
forall a. a -> Maybe a
Just (TyCon -> Name
forall a. NamedThing a => a -> Name
getName TyCon
tc)
                               Nothing     -> Maybe Name
forall a. Maybe a
Nothing
roughTopName (Coercion _) = Maybe Name
forall a. Maybe a
Nothing
roughTopName (App f :: CoreExpr
f _) = CoreExpr -> Maybe Name
roughTopName CoreExpr
f
roughTopName (Var f :: CoreBndr
f)   | CoreBndr -> Bool
isGlobalId CoreBndr
f   -- Note [Care with roughTopName]
                       , CoreBndr -> Bool
isDataConWorkId CoreBndr
f Bool -> Bool -> Bool
|| CoreBndr -> Arity
idArity CoreBndr
f Arity -> Arity -> Bool
forall a. Ord a => a -> a -> Bool
> 0
                       = Name -> Maybe Name
forall a. a -> Maybe a
Just (CoreBndr -> Name
idName CoreBndr
f)
roughTopName (Tick t :: Tickish CoreBndr
t e :: CoreExpr
e) | Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable Tickish CoreBndr
t
                        = CoreExpr -> Maybe Name
roughTopName CoreExpr
e
roughTopName _ = 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 n1 :: Name
n1 : ts :: [Maybe Name]
ts) (Just n2 :: Name
n2 : as :: [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 (_       : ts :: [Maybe Name]
ts) (_       : as :: [Maybe Name]
as) = [Maybe Name] -> [Maybe Name] -> Bool
ruleCantMatch [Maybe Name]
ts [Maybe Name]
as
ruleCantMatch _              _              = 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 :: DynFlags -> [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 PprCore because it calls tidyRules
pprRulesForUser :: DynFlags -> [CoreRule] -> SDoc
pprRulesForUser dflags :: DynFlags
dflags rules :: [CoreRule]
rules
  = PprStyle -> SDoc -> SDoc
withPprStyle (DynFlags -> PprStyle
defaultUserStyle DynFlags
dflags) (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 ((CoreRule -> RuleName) -> CoreRule -> CoreRule -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing 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
*                                                                      *
************************************************************************
-}

-- | Make a 'RuleInfo' containing a number of 'CoreRule's, suitable
-- for putting into an 'IdInfo'
mkRuleInfo :: [CoreRule] -> RuleInfo
mkRuleInfo :: [CoreRule] -> RuleInfo
mkRuleInfo rules :: [CoreRule]
rules = [CoreRule] -> DVarSet -> RuleInfo
RuleInfo [CoreRule]
rules ([CoreRule] -> DVarSet
rulesFreeVarsDSet [CoreRule]
rules)

extendRuleInfo :: RuleInfo -> [CoreRule] -> RuleInfo
extendRuleInfo :: RuleInfo -> [CoreRule] -> RuleInfo
extendRuleInfo (RuleInfo rs1 :: [CoreRule]
rs1 fvs1 :: DVarSet
fvs1) rs2 :: [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 rs1 :: [CoreRule]
rs1 fvs1 :: DVarSet
fvs1) (RuleInfo rs2 :: [CoreRule]
rs2 fvs2 :: 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 :: CoreBndr -> [CoreRule] -> CoreBndr
addIdSpecialisations id :: CoreBndr
id rules :: [CoreRule]
rules
  | [CoreRule] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [CoreRule]
rules
  = CoreBndr
id
  | Bool
otherwise
  = CoreBndr -> RuleInfo -> CoreBndr
setIdSpecialisation CoreBndr
id (RuleInfo -> CoreBndr) -> RuleInfo -> CoreBndr
forall a b. (a -> b) -> a -> b
$
    RuleInfo -> [CoreRule] -> RuleInfo
extendRuleInfo (CoreBndr -> RuleInfo
idSpecialisation CoreBndr
id) [CoreRule]
rules

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

getRules :: RuleEnv -> Id -> [CoreRule]
-- See Note [Where rules are found]
getRules :: RuleEnv -> CoreBndr -> [CoreRule]
getRules (RuleEnv { re_base :: RuleEnv -> RuleBase
re_base = RuleBase
rule_base, re_visible_orphs :: RuleEnv -> ModuleSet
re_visible_orphs = ModuleSet
orphs }) fn :: CoreBndr
fn
  = CoreBndr -> [CoreRule]
idCoreRules CoreBndr
fn [CoreRule] -> [CoreRule] -> [CoreRule]
forall a. [a] -> [a] -> [a]
++ (CoreRule -> Bool) -> [CoreRule] -> [CoreRule]
forall a. (a -> Bool) -> [a] -> [a]
filter (ModuleSet -> CoreRule -> Bool
ruleIsVisible ModuleSet
orphs) [CoreRule]
imp_rules
  where
    imp_rules :: [CoreRule]
imp_rules = RuleBase -> Name -> Maybe [CoreRule]
forall a. NameEnv a -> Name -> Maybe a
lookupNameEnv RuleBase
rule_base (CoreBndr -> Name
idName CoreBndr
fn) Maybe [CoreRule] -> [CoreRule] -> [CoreRule]
forall a. Maybe a -> a -> a
`orElse` []

ruleIsVisible :: ModuleSet -> CoreRule -> Bool
ruleIsVisible :: ModuleSet -> CoreRule -> Bool
ruleIsVisible _ BuiltinRule{} = Bool
True
ruleIsVisible vis_orphs :: 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 iself (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 PrelRules.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


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

-- RuleBase itself is defined in CoreSyn, along with CoreRule

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

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

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

unionRuleBase :: RuleBase -> RuleBase -> RuleBase
unionRuleBase :: RuleBase -> RuleBase -> RuleBase
unionRuleBase rb1 :: RuleBase
rb1 rb2 :: RuleBase
rb2 = ([CoreRule] -> [CoreRule] -> [CoreRule])
-> RuleBase -> RuleBase -> RuleBase
forall a. (a -> a -> a) -> NameEnv a -> NameEnv a -> NameEnv a
plusNameEnv_C [CoreRule] -> [CoreRule] -> [CoreRule]
forall a. [a] -> [a] -> [a]
(++) RuleBase
rb1 RuleBase
rb2

extendRuleBase :: RuleBase -> CoreRule -> RuleBase
extendRuleBase :: RuleBase -> CoreRule -> RuleBase
extendRuleBase rule_base :: RuleBase
rule_base rule :: 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]
singleton RuleBase
rule_base (CoreRule -> Name
ruleIdName CoreRule
rule) CoreRule
rule

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

{-
************************************************************************
*                                                                      *
                        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 :: DynFlags -> InScopeEnv
           -> (Activation -> Bool)      -- When rule is active
           -> Id -> [CoreExpr]
           -> [CoreRule] -> Maybe (CoreRule, CoreExpr)

-- See Note [Extra args in rule matching]
-- See comments on matchRule
lookupRule :: DynFlags
-> InScopeEnv
-> (Activation -> Bool)
-> CoreBndr
-> [CoreExpr]
-> [CoreRule]
-> Maybe (CoreRule, CoreExpr)
lookupRule dflags :: DynFlags
dflags in_scope :: InScopeEnv
in_scope is_active :: Activation -> Bool
is_active fn :: CoreBndr
fn args :: [CoreExpr]
args rules :: [CoreRule]
rules
  = -- pprTrace "matchRules" (ppr fn <+> ppr args $$ ppr rules ) $
    case [(CoreRule, CoreExpr)] -> [CoreRule] -> [(CoreRule, CoreExpr)]
go [] [CoreRule]
rules of
        []     -> Maybe (CoreRule, CoreExpr)
forall a. Maybe a
Nothing
        (m :: (CoreRule, CoreExpr)
m:ms :: [(CoreRule, CoreExpr)]
ms) -> (CoreRule, CoreExpr) -> Maybe (CoreRule, CoreExpr)
forall a. a -> Maybe a
Just ((CoreBndr, [CoreExpr])
-> (CoreRule, CoreExpr)
-> [(CoreRule, CoreExpr)]
-> (CoreRule, CoreExpr)
findBest (CoreBndr
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 ((Tickish CoreBndr -> Bool) -> CoreExpr -> CoreExpr
forall b. (Tickish CoreBndr -> Bool) -> Expr b -> Expr b
stripTicksTopE Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable) [CoreExpr]
args
    ticks :: [Tickish CoreBndr]
ticks = (CoreExpr -> [Tickish CoreBndr])
-> [CoreExpr] -> [Tickish CoreBndr]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap ((Tickish CoreBndr -> Bool) -> CoreExpr -> [Tickish CoreBndr]
forall b.
(Tickish CoreBndr -> Bool) -> Expr b -> [Tickish CoreBndr]
stripTicksTopT Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable) [CoreExpr]
args

    go :: [(CoreRule,CoreExpr)] -> [CoreRule] -> [(CoreRule,CoreExpr)]
    go :: [(CoreRule, CoreExpr)] -> [CoreRule] -> [(CoreRule, CoreExpr)]
go ms :: [(CoreRule, CoreExpr)]
ms [] = [(CoreRule, CoreExpr)]
ms
    go ms :: [(CoreRule, CoreExpr)]
ms (r :: CoreRule
r:rs :: [CoreRule]
rs)
      | Just e :: CoreExpr
e <- DynFlags
-> InScopeEnv
-> (Activation -> Bool)
-> CoreBndr
-> [CoreExpr]
-> [Maybe Name]
-> CoreRule
-> Maybe CoreExpr
matchRule DynFlags
dflags InScopeEnv
in_scope Activation -> Bool
is_active CoreBndr
fn [CoreExpr]
args' [Maybe Name]
rough_args CoreRule
r
      = [(CoreRule, CoreExpr)] -> [CoreRule] -> [(CoreRule, CoreExpr)]
go ((CoreRule
r,[Tickish CoreBndr] -> CoreExpr -> CoreExpr
mkTicks [Tickish CoreBndr]
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 :: (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 :: (CoreBndr, [CoreExpr])
-> (CoreRule, CoreExpr)
-> [(CoreRule, CoreExpr)]
-> (CoreRule, CoreExpr)
findBest _      (rule :: CoreRule
rule,ans :: CoreExpr
ans)   [] = (CoreRule
rule,CoreExpr
ans)
findBest target :: (CoreBndr, [CoreExpr])
target (rule1 :: CoreRule
rule1,ans1 :: CoreExpr
ans1) ((rule2 :: CoreRule
rule2,ans2 :: CoreExpr
ans2):prs :: [(CoreRule, CoreExpr)]
prs)
  | CoreRule
rule1 CoreRule -> CoreRule -> Bool
`isMoreSpecific` CoreRule
rule2 = (CoreBndr, [CoreExpr])
-> (CoreRule, CoreExpr)
-> [(CoreRule, CoreExpr)]
-> (CoreRule, CoreExpr)
findBest (CoreBndr, [CoreExpr])
target (CoreRule
rule1,CoreExpr
ans1) [(CoreRule, CoreExpr)]
prs
  | CoreRule
rule2 CoreRule -> CoreRule -> Bool
`isMoreSpecific` CoreRule
rule1 = (CoreBndr, [CoreExpr])
-> (CoreRule, CoreExpr)
-> [(CoreRule, CoreExpr)]
-> (CoreRule, CoreExpr)
findBest (CoreBndr, [CoreExpr])
target (CoreRule
rule2,CoreExpr
ans2) [(CoreRule, CoreExpr)]
prs
  | Bool
debugIsOn = let pp_rule :: CoreRule -> SDoc
pp_rule rule :: CoreRule
rule
                      = SDoc -> SDoc -> SDoc
ifPprDebug (CoreRule -> SDoc
forall a. Outputable a => a -> SDoc
ppr CoreRule
rule)
                                   (SDoc -> SDoc
doubleQuotes (RuleName -> SDoc
ftext (CoreRule -> RuleName
ruleName CoreRule
rule)))
                in String -> SDoc -> (CoreRule, CoreExpr) -> (CoreRule, CoreExpr)
forall a. String -> SDoc -> a -> a
pprTrace "Rules.findBest: rule overlap (Rule 1 wins)"
                         ([SDoc] -> SDoc
vcat [ SDoc -> SDoc
whenPprDebug (SDoc -> SDoc) -> SDoc -> SDoc
forall a b. (a -> b) -> a -> b
$
                                 String -> SDoc
text "Expression to match:" SDoc -> SDoc -> SDoc
<+> CoreBndr -> SDoc
forall a. Outputable a => a -> SDoc
ppr CoreBndr
fn
                                 SDoc -> SDoc -> SDoc
<+> [SDoc] -> SDoc
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
text "Rule 1:" SDoc -> SDoc -> SDoc
<+> CoreRule -> SDoc
pp_rule CoreRule
rule1
                               , String -> SDoc
text "Rule 2:" SDoc -> SDoc -> SDoc
<+> CoreRule -> SDoc
pp_rule CoreRule
rule2]) ((CoreRule, CoreExpr) -> (CoreRule, CoreExpr))
-> (CoreRule, CoreExpr) -> (CoreRule, CoreExpr)
forall a b. (a -> b) -> a -> b
$
                (CoreBndr, [CoreExpr])
-> (CoreRule, CoreExpr)
-> [(CoreRule, CoreExpr)]
-> (CoreRule, CoreExpr)
findBest (CoreBndr, [CoreExpr])
target (CoreRule
rule1,CoreExpr
ans1) [(CoreRule, CoreExpr)]
prs
  | Bool
otherwise = (CoreBndr, [CoreExpr])
-> (CoreRule, CoreExpr)
-> [(CoreRule, CoreExpr)]
-> (CoreRule, CoreExpr)
findBest (CoreBndr, [CoreExpr])
target (CoreRule
rule1,CoreExpr
ans1) [(CoreRule, CoreExpr)]
prs
  where
    (fn :: CoreBndr
fn,args :: [CoreExpr]
args) = (CoreBndr, [CoreExpr])
target

isMoreSpecific :: CoreRule -> CoreRule -> Bool
-- This tests if one rule is more specific than another
-- We take the view that a BuiltinRule is less specific than
-- anything else, because we want user-define rules to "win"
-- In particular, class ops have a built-in rule, but we
-- any user-specific rules to win
--   eg (Trac #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
isMoreSpecific :: CoreRule -> CoreRule -> Bool
isMoreSpecific (BuiltinRule {}) _                = Bool
False
isMoreSpecific (Rule {})        (BuiltinRule {}) = Bool
True
isMoreSpecific (Rule { ru_bndrs :: CoreRule -> [CoreBndr]
ru_bndrs = [CoreBndr]
bndrs1, ru_args :: CoreRule -> [CoreExpr]
ru_args = [CoreExpr]
args1 })
               (Rule { ru_bndrs :: CoreRule -> [CoreBndr]
ru_bndrs = [CoreBndr]
bndrs2, ru_args :: CoreRule -> [CoreExpr]
ru_args = [CoreExpr]
args2, ru_name :: CoreRule -> RuleName
ru_name = RuleName
rule_name2 })
  = Maybe (CoreExpr -> CoreExpr, [CoreExpr]) -> Bool
forall a. Maybe a -> Bool
isJust (InScopeEnv
-> RuleName
-> [CoreBndr]
-> [CoreExpr]
-> [CoreExpr]
-> Maybe (CoreExpr -> CoreExpr, [CoreExpr])
matchN (InScopeSet
in_scope, CoreBndr -> Unfolding
forall p. p -> Unfolding
id_unfolding_fun) RuleName
rule_name2 [CoreBndr]
bndrs2 [CoreExpr]
args2 [CoreExpr]
args1)
  where
   id_unfolding_fun :: p -> Unfolding
id_unfolding_fun _ = Unfolding
NoUnfolding     -- Don't expand in templates
   in_scope :: InScopeSet
in_scope = VarSet -> InScopeSet
mkInScopeSet ([CoreBndr] -> VarSet
mkVarSet [CoreBndr]
bndrs1)
        -- Actually we should probably include the free vars
        -- of rule1's args, but I can't be bothered

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

{-
Note [Extra args in rule matching]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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.  It's up to the caller to keep track
of any left-over args.  E.g. if you call
        lookupRule ... f [e1, e2, e3]
and it returns Just (r, rhs), where r has ruleArity 2
then 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
-}

------------------------------------
matchRule :: DynFlags -> 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 call: matchRule the_rule [e1,map e2 e3]
--        = Just ("map/map", (\f,g,x -> rhs) e1 e2 e3)
--
-- Any 'surplus' arguments in the input are simply put on the end
-- of the output.

matchRule :: DynFlags
-> InScopeEnv
-> (Activation -> Bool)
-> CoreBndr
-> [CoreExpr]
-> [Maybe Name]
-> CoreRule
-> Maybe CoreExpr
matchRule dflags :: DynFlags
dflags rule_env :: InScopeEnv
rule_env _is_active :: Activation -> Bool
_is_active fn :: CoreBndr
fn args :: [CoreExpr]
args _rough_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 DynFlags
dflags InScopeEnv
rule_env CoreBndr
fn [CoreExpr]
args of
        Nothing   -> Maybe CoreExpr
forall a. Maybe a
Nothing
        Just expr :: CoreExpr
expr -> CoreExpr -> Maybe CoreExpr
forall a. a -> Maybe a
Just CoreExpr
expr

matchRule _ in_scope :: InScopeEnv
in_scope is_active :: Activation -> Bool
is_active _ args :: [CoreExpr]
args rough_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 -> [CoreBndr]
ru_bndrs = [CoreBndr]
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
  = case InScopeEnv
-> RuleName
-> [CoreBndr]
-> [CoreExpr]
-> [CoreExpr]
-> Maybe (CoreExpr -> CoreExpr, [CoreExpr])
matchN InScopeEnv
in_scope RuleName
rule_name [CoreBndr]
tpl_vars [CoreExpr]
tpl_args [CoreExpr]
args of
        Nothing                       -> Maybe CoreExpr
forall a. Maybe a
Nothing
        Just (bind_wrapper :: CoreExpr -> CoreExpr
bind_wrapper, tpl_vals :: [CoreExpr]
tpl_vals) -> CoreExpr -> Maybe CoreExpr
forall a. a -> Maybe a
Just (CoreExpr -> CoreExpr
bind_wrapper (CoreExpr -> CoreExpr) -> CoreExpr -> CoreExpr
forall a b. (a -> b) -> a -> b
$
                                               CoreExpr
rule_fn CoreExpr -> [CoreExpr] -> CoreExpr
forall b. Expr b -> [Expr b] -> Expr b
`mkApps` [CoreExpr]
tpl_vals)
  where
    rule_fn :: CoreExpr
rule_fn = [CoreBndr] -> CoreExpr -> CoreExpr
forall b. [b] -> Expr b -> Expr b
mkLams [CoreBndr]
tpl_vars CoreExpr
rhs

---------------------------------------
matchN  :: InScopeEnv
        -> RuleName -> [Var] -> [CoreExpr]
        -> [CoreExpr]           -- ^ Target; can have more elements than the template
        -> Maybe (BindWrapper,  -- Floated bindings; see Note [Matching lets]
                  [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 two few actual arguments from the target to match the template

matchN :: InScopeEnv
-> RuleName
-> [CoreBndr]
-> [CoreExpr]
-> [CoreExpr]
-> Maybe (CoreExpr -> CoreExpr, [CoreExpr])
matchN (in_scope :: InScopeSet
in_scope, id_unf :: CoreBndr -> Unfolding
id_unf) rule_name :: RuleName
rule_name tmpl_vars :: [CoreBndr]
tmpl_vars tmpl_es :: [CoreExpr]
tmpl_es target_es :: [CoreExpr]
target_es
  = do  { RuleSubst
subst <- RuleMatchEnv
-> RuleSubst -> [CoreExpr] -> [CoreExpr] -> Maybe RuleSubst
go RuleMatchEnv
init_menv RuleSubst
emptyRuleSubst [CoreExpr]
tmpl_es [CoreExpr]
target_es
        ; let (_, matched_es :: [CoreExpr]
matched_es) = (RuleSubst -> (CoreBndr, CoreBndr) -> (RuleSubst, CoreExpr))
-> RuleSubst -> [(CoreBndr, CoreBndr)] -> (RuleSubst, [CoreExpr])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL RuleSubst -> (CoreBndr, CoreBndr) -> (RuleSubst, CoreExpr)
lookup_tmpl RuleSubst
subst ([(CoreBndr, CoreBndr)] -> (RuleSubst, [CoreExpr]))
-> [(CoreBndr, CoreBndr)] -> (RuleSubst, [CoreExpr])
forall a b. (a -> b) -> a -> b
$
                                [CoreBndr]
tmpl_vars [CoreBndr] -> [CoreBndr] -> [(CoreBndr, CoreBndr)]
forall a b. [a] -> [b] -> [(a, b)]
`zip` [CoreBndr]
tmpl_vars1
        ; (CoreExpr -> CoreExpr, [CoreExpr])
-> Maybe (CoreExpr -> CoreExpr, [CoreExpr])
forall (m :: * -> *) a. Monad m => a -> m a
return (RuleSubst -> CoreExpr -> CoreExpr
rs_binds RuleSubst
subst, [CoreExpr]
matched_es) }
  where
    (init_rn_env :: RnEnv2
init_rn_env, tmpl_vars1 :: [CoreBndr]
tmpl_vars1) = (RnEnv2 -> CoreBndr -> (RnEnv2, CoreBndr))
-> RnEnv2 -> [CoreBndr] -> (RnEnv2, [CoreBndr])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL RnEnv2 -> CoreBndr -> (RnEnv2, CoreBndr)
rnBndrL (InScopeSet -> RnEnv2
mkRnEnv2 InScopeSet
in_scope) [CoreBndr]
tmpl_vars
                  -- See Note [Cloning the template binders]

    init_menv :: RuleMatchEnv
init_menv = RV :: RnEnv2
-> VarSet -> Subst -> (CoreBndr -> Unfolding) -> RuleMatchEnv
RV { rv_tmpls :: VarSet
rv_tmpls = [CoreBndr] -> VarSet
mkVarSet [CoreBndr]
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 :: CoreBndr -> Unfolding
rv_unf   = CoreBndr -> Unfolding
id_unf }

    go :: RuleMatchEnv
-> RuleSubst -> [CoreExpr] -> [CoreExpr] -> Maybe RuleSubst
go _    subst :: RuleSubst
subst []     _      = RuleSubst -> Maybe RuleSubst
forall a. a -> Maybe a
Just RuleSubst
subst
    go _    _     _      []     = Maybe RuleSubst
forall a. Maybe a
Nothing       -- Fail if too few actual args
    go menv :: RuleMatchEnv
menv subst :: RuleSubst
subst (t :: CoreExpr
t:ts :: [CoreExpr]
ts) (e :: CoreExpr
e:es :: [CoreExpr]
es) = do { RuleSubst
subst1 <- RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match RuleMatchEnv
menv RuleSubst
subst CoreExpr
t CoreExpr
e
                                     ; RuleMatchEnv
-> RuleSubst -> [CoreExpr] -> [CoreExpr] -> Maybe RuleSubst
go RuleMatchEnv
menv RuleSubst
subst1 [CoreExpr]
ts [CoreExpr]
es }

    lookup_tmpl :: RuleSubst -> (InVar,OutVar) -> (RuleSubst, CoreExpr)
                   -- Need to return a RuleSubst solely for the benefit of mk_fake_ty
    lookup_tmpl :: RuleSubst -> (CoreBndr, CoreBndr) -> (RuleSubst, CoreExpr)
lookup_tmpl rs :: RuleSubst
rs@(RS { rs_tv_subst :: RuleSubst -> TvSubstEnv
rs_tv_subst = TvSubstEnv
tv_subst, rs_id_subst :: RuleSubst -> IdSubstEnv
rs_id_subst = IdSubstEnv
id_subst })
                (tmpl_var :: CoreBndr
tmpl_var, tmpl_var1 :: CoreBndr
tmpl_var1)
        | CoreBndr -> Bool
isId CoreBndr
tmpl_var1
        = case IdSubstEnv -> CoreBndr -> Maybe CoreExpr
forall a. VarEnv a -> CoreBndr -> Maybe a
lookupVarEnv IdSubstEnv
id_subst CoreBndr
tmpl_var1 of
             Just e :: CoreExpr
e -> (RuleSubst
rs, CoreExpr
e)
             Nothing | Just refl_co :: Coercion
refl_co <- CoreBndr -> Maybe Coercion
isReflCoVar_maybe CoreBndr
tmpl_var1
                     , let co_expr :: Expr b
co_expr   = Coercion -> Expr b
forall b. Coercion -> Expr b
Coercion Coercion
refl_co
                           id_subst' :: IdSubstEnv
id_subst' = IdSubstEnv -> CoreBndr -> CoreExpr -> IdSubstEnv
forall a. VarEnv a -> CoreBndr -> a -> VarEnv a
extendVarEnv IdSubstEnv
id_subst CoreBndr
tmpl_var1 CoreExpr
forall b. Expr b
co_expr
                           rs' :: RuleSubst
rs'       = RuleSubst
rs { rs_id_subst :: IdSubstEnv
rs_id_subst = IdSubstEnv
id_subst' }
                     -> (RuleSubst
rs', CoreExpr
forall b. Expr b
co_expr) -- See Note [Unbound RULE binders]
                     | Bool
otherwise
                     -> CoreBndr -> (RuleSubst, CoreExpr)
forall a. CoreBndr -> a
unbound CoreBndr
tmpl_var
        | Bool
otherwise
        = case TvSubstEnv -> CoreBndr -> Maybe Type
forall a. VarEnv a -> CoreBndr -> Maybe a
lookupVarEnv TvSubstEnv
tv_subst CoreBndr
tmpl_var1 of
             Just ty :: Type
ty -> (RuleSubst
rs, Type -> CoreExpr
forall b. Type -> Expr b
Type Type
ty)
             Nothing -> (RuleSubst
rs', Type -> CoreExpr
forall b. Type -> Expr b
Type Type
fake_ty) -- See Note [Unbound RULE binders]
        where
          rs' :: RuleSubst
rs'     = RuleSubst
rs { rs_tv_subst :: TvSubstEnv
rs_tv_subst = TvSubstEnv -> CoreBndr -> Type -> TvSubstEnv
forall a. VarEnv a -> CoreBndr -> a -> VarEnv a
extendVarEnv TvSubstEnv
tv_subst CoreBndr
tmpl_var1 Type
fake_ty }
          fake_ty :: Type
fake_ty = InScopeSet -> RuleSubst -> CoreBndr -> Type
mk_fake_ty InScopeSet
in_scope RuleSubst
rs CoreBndr
tmpl_var1
                    -- This call is the sole reason we accumulate
                    -- RuleSubst in lookup_tmpl

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


mk_fake_ty :: InScopeSet -> RuleSubst -> TyVar -> Kind
-- Roughly:
--    mk_fake_ty subst tv = Any @(subst (tyVarKind tv))
-- That is: apply the substitution to the kind of the given tyvar,
-- and make an 'any' type of that kind.
-- Tiresomely, the RuleSubst is not well adapted to substTy, leading to
-- horrible impedence matching.
--
-- Happily, this function is seldom called
mk_fake_ty :: InScopeSet -> RuleSubst -> CoreBndr -> Type
mk_fake_ty in_scope :: InScopeSet
in_scope (RS { rs_tv_subst :: RuleSubst -> TvSubstEnv
rs_tv_subst = TvSubstEnv
tv_subst, rs_id_subst :: RuleSubst -> IdSubstEnv
rs_id_subst = IdSubstEnv
id_subst }) tmpl_var1 :: CoreBndr
tmpl_var1
  = Type -> Type
anyTypeOfKind Type
kind
  where
    kind :: Type
kind = HasCallStack => TCvSubst -> Type -> Type
TCvSubst -> Type -> Type
Type.substTy (InScopeSet -> (TvSubstEnv, CvSubstEnv) -> TCvSubst
mkTCvSubst InScopeSet
in_scope (TvSubstEnv
tv_subst, CvSubstEnv
cv_subst))
                        (CoreBndr -> Type
tyVarKind CoreBndr
tmpl_var1)

    cv_subst :: CvSubstEnv
cv_subst = IdSubstEnv -> CvSubstEnv
to_co_env IdSubstEnv
id_subst

    to_co_env :: IdSubstEnv -> CvSubstEnv
    to_co_env :: IdSubstEnv -> CvSubstEnv
to_co_env env :: IdSubstEnv
env = (Unique -> CoreExpr -> CvSubstEnv -> CvSubstEnv)
-> CvSubstEnv -> IdSubstEnv -> CvSubstEnv
forall elt a. (Unique -> elt -> a -> a) -> a -> UniqFM elt -> a
nonDetFoldUFM_Directly Unique -> CoreExpr -> CvSubstEnv -> CvSubstEnv
to_co CvSubstEnv
forall a. NameEnv a
emptyVarEnv IdSubstEnv
env
      -- It's OK to use nonDetFoldUFM_Directly because we forget the
      -- order immediately by creating a new env

    to_co :: Unique -> CoreExpr -> CvSubstEnv -> CvSubstEnv
to_co uniq :: Unique
uniq expr :: CoreExpr
expr env :: CvSubstEnv
env
      = case CoreExpr -> Maybe Coercion
exprToCoercion_maybe CoreExpr
expr of
          Just co :: Coercion
co -> CvSubstEnv -> Unique -> Coercion -> CvSubstEnv
forall a. VarEnv a -> Unique -> a -> VarEnv a
extendVarEnv_Directly CvSubstEnv
env Unique
uniq Coercion
co
          Nothing -> CvSubstEnv
env

{- 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 (Trac #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 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 Trac #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 Trac #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 Trac #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
*                                                                      *
********************************************************************* -}

-- * 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 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]
       , RuleMatchEnv -> CoreBndr -> Unfolding
rv_unf :: IdUnfoldingFun
       }

rvInScopeEnv :: RuleMatchEnv -> InScopeEnv
rvInScopeEnv :: RuleMatchEnv -> InScopeEnv
rvInScopeEnv renv :: RuleMatchEnv
renv = (RnEnv2 -> InScopeSet
rnInScopeSet (RuleMatchEnv -> RnEnv2
rv_lcl RuleMatchEnv
renv), RuleMatchEnv -> CoreBndr -> Unfolding
rv_unf RuleMatchEnv
renv)

data RuleSubst = RS { RuleSubst -> TvSubstEnv
rs_tv_subst :: TvSubstEnv   -- Range is the
                    , RuleSubst -> IdSubstEnv
rs_id_subst :: IdSubstEnv   --   template variables
                    , RuleSubst -> CoreExpr -> CoreExpr
rs_binds    :: BindWrapper  -- Floated bindings
                    , RuleSubst -> VarSet
rs_bndrs    :: VarSet       -- 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 :: TvSubstEnv
-> IdSubstEnv -> (CoreExpr -> CoreExpr) -> VarSet -> RuleSubst
RS { rs_tv_subst :: TvSubstEnv
rs_tv_subst = TvSubstEnv
forall a. NameEnv a
emptyVarEnv, rs_id_subst :: IdSubstEnv
rs_id_subst = IdSubstEnv
forall a. NameEnv a
emptyVarEnv
                    , rs_binds :: CoreExpr -> CoreExpr
rs_binds = \e :: CoreExpr
e -> CoreExpr
e, rs_bndrs :: VarSet
rs_bndrs = VarSet
emptyVarSet }

--      At one stage I tried to match even if there are more
--      template args than real args.

--      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

match :: RuleMatchEnv
      -> RuleSubst
      -> CoreExpr               -- Template
      -> CoreExpr               -- Target
      -> Maybe RuleSubst

-- We look through certain ticks. See note [Tick annotations in RULE matching]
match :: RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst e1 :: CoreExpr
e1 (Tick t :: Tickish CoreBndr
t e2 :: CoreExpr
e2)
  | Tickish CoreBndr -> Bool
forall id. Tickish id -> Bool
tickishFloatable Tickish CoreBndr
t
  = RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match RuleMatchEnv
renv RuleSubst
subst' CoreExpr
e1 CoreExpr
e2
  where subst' :: RuleSubst
subst' = RuleSubst
subst { rs_binds :: CoreExpr -> CoreExpr
rs_binds = RuleSubst -> CoreExpr -> CoreExpr
rs_binds RuleSubst
subst (CoreExpr -> CoreExpr)
-> (CoreExpr -> CoreExpr) -> CoreExpr -> CoreExpr
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Tickish CoreBndr -> CoreExpr -> CoreExpr
mkTick Tickish CoreBndr
t }
match _ _ e :: CoreExpr
e@Tick{} _
  = String -> SDoc -> Maybe RuleSubst
forall a. HasCallStack => String -> SDoc -> a
pprPanic "Tick in rule" (CoreExpr -> SDoc
forall a. Outputable a => a -> SDoc
ppr CoreExpr
e)

-- See the notes with Unify.match, which matches types
-- Everything is very similar for terms

-- Interesting examples:
-- Consider matching
--      \x->f      against    \f->f
-- When we meet the lambdas we must remember to rename f to f' in the
-- second expression.  The RnEnv2 does that.
--
-- Consider matching
--      forall a. \b->b    against   \a->3
-- We must rename the \a.  Otherwise when we meet the lambdas we
-- might substitute [a/b] in the template, and then erroneously
-- succeed in matching what looks like the template variable 'a' against 3.

-- The Var case follows closely what happens in Unify.match
match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst (Var v1 :: CoreBndr
v1) e2 :: CoreExpr
e2
  = RuleMatchEnv
-> RuleSubst -> CoreBndr -> CoreExpr -> Maybe RuleSubst
match_var RuleMatchEnv
renv RuleSubst
subst CoreBndr
v1 CoreExpr
e2

match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst e1 :: CoreExpr
e1 (Var v2 :: CoreBndr
v2)      -- Note [Expanding variables]
  | Bool -> Bool
not (RnEnv2 -> CoreBndr -> Bool
inRnEnvR RnEnv2
rn_env CoreBndr
v2) -- Note [Do not expand locally-bound variables]
  , Just e2' :: CoreExpr
e2' <- Unfolding -> Maybe CoreExpr
expandUnfolding_maybe (RuleMatchEnv -> CoreBndr -> Unfolding
rv_unf RuleMatchEnv
renv CoreBndr
v2')
  = RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match (RuleMatchEnv
renv { rv_lcl :: RnEnv2
rv_lcl = RnEnv2 -> RnEnv2
nukeRnEnvR RnEnv2
rn_env }) RuleSubst
subst CoreExpr
e1 CoreExpr
e2'
  where
    v2' :: CoreBndr
v2'    = RnEnv2 -> CoreBndr -> CoreBndr
lookupRnInScope RnEnv2
rn_env CoreBndr
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

match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst e1 :: CoreExpr
e1 (Let bind :: CoreBind
bind e2 :: CoreExpr
e2)
  | -- 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 -> Maybe RuleSubst
match (RuleMatchEnv
renv { rv_fltR :: Subst
rv_fltR = Subst
flt_subst' })
          (RuleSubst
subst { rs_binds :: CoreExpr -> CoreExpr
rs_binds = RuleSubst -> CoreExpr -> CoreExpr
rs_binds RuleSubst
subst (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
bind'
                 , rs_bndrs :: VarSet
rs_bndrs = VarSet -> [CoreBndr] -> VarSet
extendVarSetList (RuleSubst -> VarSet
rs_bndrs RuleSubst
subst) [CoreBndr]
new_bndrs })
          CoreExpr
e1 CoreExpr
e2
  where
    flt_subst :: Subst
flt_subst = Subst -> VarSet -> Subst
addInScopeSet (RuleMatchEnv -> Subst
rv_fltR RuleMatchEnv
renv) (RuleSubst -> VarSet
rs_bndrs RuleSubst
subst)
    (flt_subst' :: Subst
flt_subst', bind' :: CoreBind
bind') = Subst -> CoreBind -> (Subst, CoreBind)
substBind Subst
flt_subst CoreBind
bind
    new_bndrs :: [CoreBndr]
new_bndrs = CoreBind -> [CoreBndr]
forall b. Bind b -> [b]
bindersOf CoreBind
bind'

{- 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 _ subst :: RuleSubst
subst (Lit lit1 :: Literal
lit1) (Lit lit2 :: Literal
lit2)
  | Literal
lit1 Literal -> Literal -> Bool
forall a. Eq a => a -> a -> Bool
== Literal
lit2
  = RuleSubst -> Maybe RuleSubst
forall a. a -> Maybe a
Just RuleSubst
subst

match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst (App f1 :: CoreExpr
f1 a1 :: CoreExpr
a1) (App f2 :: CoreExpr
f2 a2 :: CoreExpr
a2)
  = do  { RuleSubst
subst' <- RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match RuleMatchEnv
renv RuleSubst
subst CoreExpr
f1 CoreExpr
f2
        ; RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match RuleMatchEnv
renv RuleSubst
subst' CoreExpr
a1 CoreExpr
a2 }

match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst (Lam x1 :: CoreBndr
x1 e1 :: CoreExpr
e1) e2 :: CoreExpr
e2
  | Just (x2 :: CoreBndr
x2, e2 :: CoreExpr
e2, ts :: [Tickish CoreBndr]
ts) <- InScopeEnv
-> CoreExpr -> Maybe (CoreBndr, CoreExpr, [Tickish CoreBndr])
exprIsLambda_maybe (RuleMatchEnv -> InScopeEnv
rvInScopeEnv RuleMatchEnv
renv) CoreExpr
e2
  = let renv' :: RuleMatchEnv
renv' = RuleMatchEnv
renv { rv_lcl :: RnEnv2
rv_lcl = RnEnv2 -> CoreBndr -> CoreBndr -> RnEnv2
rnBndr2 (RuleMatchEnv -> RnEnv2
rv_lcl RuleMatchEnv
renv) CoreBndr
x1 CoreBndr
x2
                     , rv_fltR :: Subst
rv_fltR = Subst -> CoreBndr -> Subst
delBndr (RuleMatchEnv -> Subst
rv_fltR RuleMatchEnv
renv) CoreBndr
x2 }
        subst' :: RuleSubst
subst' = RuleSubst
subst { rs_binds :: CoreExpr -> CoreExpr
rs_binds = RuleSubst -> CoreExpr -> CoreExpr
rs_binds RuleSubst
subst (CoreExpr -> CoreExpr)
-> (CoreExpr -> CoreExpr) -> CoreExpr -> CoreExpr
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (CoreExpr -> [Tickish CoreBndr] -> CoreExpr)
-> [Tickish CoreBndr] -> CoreExpr -> CoreExpr
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((Tickish CoreBndr -> CoreExpr -> CoreExpr)
-> CoreExpr -> [Tickish CoreBndr] -> CoreExpr
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Tickish CoreBndr -> CoreExpr -> CoreExpr
mkTick) [Tickish CoreBndr]
ts }
    in  RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match RuleMatchEnv
renv' RuleSubst
subst' CoreExpr
e1 CoreExpr
e2

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

match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst (Type ty1 :: Type
ty1) (Type ty2 :: Type
ty2)
  = RuleMatchEnv -> RuleSubst -> Type -> Type -> Maybe RuleSubst
match_ty RuleMatchEnv
renv RuleSubst
subst Type
ty1 Type
ty2
match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst (Coercion co1 :: Coercion
co1) (Coercion co2 :: Coercion
co2)
  = RuleMatchEnv
-> RuleSubst -> Coercion -> Coercion -> Maybe RuleSubst
match_co RuleMatchEnv
renv RuleSubst
subst Coercion
co1 Coercion
co2

match renv :: RuleMatchEnv
renv subst :: RuleSubst
subst (Cast e1 :: CoreExpr
e1 co1 :: Coercion
co1) (Cast e2 :: CoreExpr
e2 co2 :: Coercion
co2)
  = do  { RuleSubst
subst1 <- RuleMatchEnv
-> RuleSubst -> Coercion -> Coercion -> Maybe RuleSubst
match_co RuleMatchEnv
renv RuleSubst
subst Coercion
co1 Coercion
co2
        ; RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match RuleMatchEnv
renv RuleSubst
subst1 CoreExpr
e1 CoreExpr
e2 }

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

-------------
match_co :: RuleMatchEnv
         -> RuleSubst
         -> Coercion
         -> Coercion
         -> Maybe RuleSubst
match_co :: RuleMatchEnv
-> RuleSubst -> Coercion -> Coercion -> Maybe RuleSubst
match_co renv :: RuleMatchEnv
renv subst :: RuleSubst
subst co1 :: Coercion
co1 co2 :: Coercion
co2
  | Just cv :: CoreBndr
cv <- Coercion -> Maybe CoreBndr
getCoVar_maybe Coercion
co1
  = RuleMatchEnv
-> RuleSubst -> CoreBndr -> CoreExpr -> Maybe RuleSubst
match_var RuleMatchEnv
renv RuleSubst
subst CoreBndr
cv (Coercion -> CoreExpr
forall b. Coercion -> Expr b
Coercion Coercion
co2)
  | Just (ty1 :: Type
ty1, r1 :: Role
r1) <- Coercion -> Maybe (Type, Role)
isReflCo_maybe Coercion
co1
  = do { (ty2 :: Type
ty2, r2 :: Role
r2) <- Coercion -> Maybe (Type, Role)
isReflCo_maybe Coercion
co2
       ; Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Role
r1 Role -> Role -> Bool
forall a. Eq a => a -> a -> Bool
== Role
r2)
       ; RuleMatchEnv -> RuleSubst -> Type -> Type -> Maybe RuleSubst
match_ty RuleMatchEnv
renv RuleSubst
subst Type
ty1 Type
ty2 }
match_co renv :: RuleMatchEnv
renv subst :: RuleSubst
subst co1 :: Coercion
co1 co2 :: Coercion
co2
  | Just (tc1 :: TyCon
tc1, cos1 :: [Coercion]
cos1) <- Coercion -> Maybe (TyCon, [Coercion])
splitTyConAppCo_maybe Coercion
co1
  = case Coercion -> Maybe (TyCon, [Coercion])
splitTyConAppCo_maybe Coercion
co2 of
      Just (tc2 :: TyCon
tc2, cos2 :: [Coercion]
cos2)
        |  TyCon
tc1 TyCon -> TyCon -> Bool
forall a. Eq a => a -> a -> Bool
== TyCon
tc2
        -> RuleMatchEnv
-> RuleSubst -> [Coercion] -> [Coercion] -> Maybe RuleSubst
match_cos RuleMatchEnv
renv RuleSubst
subst [Coercion]
cos1 [Coercion]
cos2
      _ -> Maybe RuleSubst
forall a. Maybe a
Nothing
match_co renv :: RuleMatchEnv
renv subst :: RuleSubst
subst co1 :: Coercion
co1 co2 :: Coercion
co2
  | Just (arg1 :: Coercion
arg1, res1 :: Coercion
res1) <- Coercion -> Maybe (Coercion, Coercion)
splitFunCo_maybe Coercion
co1
  = case Coercion -> Maybe (Coercion, Coercion)
splitFunCo_maybe Coercion
co2 of
      Just (arg2 :: Coercion
arg2, res2 :: Coercion
res2)
        -> RuleMatchEnv
-> RuleSubst -> [Coercion] -> [Coercion] -> Maybe RuleSubst
match_cos RuleMatchEnv
renv RuleSubst
subst [Coercion
arg1, Coercion
res1] [Coercion
arg2, Coercion
res2]
      _ -> Maybe RuleSubst
forall a. Maybe a
Nothing
match_co _ _ _co1 :: Coercion
_co1 _co2 :: Coercion
_co2
    -- Currently just deals with CoVarCo, TyConAppCo and Refl
#if defined(DEBUG)
  = pprTrace "match_co: needs more cases" (ppr _co1 $$ ppr _co2) Nothing
#else
  = Maybe RuleSubst
forall a. Maybe a
Nothing
#endif

match_cos :: RuleMatchEnv
         -> RuleSubst
         -> [Coercion]
         -> [Coercion]
         -> Maybe RuleSubst
match_cos :: RuleMatchEnv
-> RuleSubst -> [Coercion] -> [Coercion] -> Maybe RuleSubst
match_cos renv :: RuleMatchEnv
renv subst :: RuleSubst
subst (co1 :: Coercion
co1:cos1 :: [Coercion]
cos1) (co2 :: Coercion
co2:cos2 :: [Coercion]
cos2) =
  do { RuleSubst
subst' <- RuleMatchEnv
-> RuleSubst -> Coercion -> Coercion -> Maybe RuleSubst
match_co RuleMatchEnv
renv RuleSubst
subst Coercion
co1 Coercion
co2
     ; RuleMatchEnv
-> RuleSubst -> [Coercion] -> [Coercion] -> Maybe RuleSubst
match_cos RuleMatchEnv
renv RuleSubst
subst' [Coercion]
cos1 [Coercion]
cos2 }
match_cos _ subst :: RuleSubst
subst [] [] = RuleSubst -> Maybe RuleSubst
forall a. a -> Maybe a
Just RuleSubst
subst
match_cos _ _ cos1 :: [Coercion]
cos1 cos2 :: [Coercion]
cos2 = String -> SDoc -> Maybe RuleSubst -> Maybe RuleSubst
forall a. String -> SDoc -> a -> a
pprTrace "match_cos: not same length" ([Coercion] -> SDoc
forall a. Outputable a => a -> SDoc
ppr [Coercion]
cos1 SDoc -> SDoc -> SDoc
$$ [Coercion] -> SDoc
forall a. Outputable a => a -> SDoc
ppr [Coercion]
cos2) Maybe RuleSubst
forall a. Maybe a
Nothing

-------------
rnMatchBndr2 :: RuleMatchEnv -> RuleSubst -> Var -> Var -> RuleMatchEnv
rnMatchBndr2 :: RuleMatchEnv -> RuleSubst -> CoreBndr -> CoreBndr -> RuleMatchEnv
rnMatchBndr2 renv :: RuleMatchEnv
renv subst :: RuleSubst
subst x1 :: CoreBndr
x1 x2 :: CoreBndr
x2
  = RuleMatchEnv
renv { rv_lcl :: RnEnv2
rv_lcl  = RnEnv2 -> CoreBndr -> CoreBndr -> RnEnv2
rnBndr2 RnEnv2
rn_env CoreBndr
x1 CoreBndr
x2
         , rv_fltR :: Subst
rv_fltR = Subst -> CoreBndr -> Subst
delBndr (RuleMatchEnv -> Subst
rv_fltR RuleMatchEnv
renv) CoreBndr
x2 }
  where
    rn_env :: RnEnv2
rn_env = RnEnv2 -> VarSet -> RnEnv2
addRnInScopeSet (RuleMatchEnv -> RnEnv2
rv_lcl RuleMatchEnv
renv) (RuleSubst -> VarSet
rs_bndrs RuleSubst
subst)
    -- Typically this is a no-op, but it may matter if
    -- there are some floated let-bindings

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

match_alts _ _ _ _
  = Maybe RuleSubst
forall a. Maybe a
Nothing

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

------------------------------------------
match_var :: RuleMatchEnv
          -> RuleSubst
          -> Var                -- Template
          -> CoreExpr        -- Target
          -> Maybe RuleSubst
match_var :: RuleMatchEnv
-> RuleSubst -> CoreBndr -> 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 })
          subst :: RuleSubst
subst v1 :: CoreBndr
v1 e2 :: CoreExpr
e2
  | CoreBndr
v1' CoreBndr -> VarSet -> Bool
`elemVarSet` VarSet
tmpls
  = RuleMatchEnv
-> RuleSubst -> CoreBndr -> CoreExpr -> Maybe RuleSubst
match_tmpl_var RuleMatchEnv
renv RuleSubst
subst CoreBndr
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 v2 :: CoreBndr
v2 | CoreBndr
v1' CoreBndr -> CoreBndr -> Bool
forall a. Eq a => a -> a -> Bool
== RnEnv2 -> CoreBndr -> CoreBndr
rnOccR RnEnv2
rn_env CoreBndr
v2
              -> RuleSubst -> Maybe RuleSubst
forall a. a -> Maybe a
Just RuleSubst
subst

              | Var v2' :: CoreBndr
v2' <- SDoc -> Subst -> CoreBndr -> CoreExpr
lookupIdSubst (String -> SDoc
text "match_var") Subst
flt_env CoreBndr
v2
              , CoreBndr
v1' CoreBndr -> CoreBndr -> Bool
forall a. Eq a => a -> a -> Bool
== CoreBndr
v2'
              -> RuleSubst -> Maybe RuleSubst
forall a. a -> Maybe a
Just RuleSubst
subst

       _ -> Maybe RuleSubst
forall a. Maybe a
Nothing

  where
    v1' :: CoreBndr
v1' = RnEnv2 -> CoreBndr -> CoreBndr
rnOccL RnEnv2
rn_env CoreBndr
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 -> CoreBndr -> 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 -> VarSet
rs_bndrs = VarSet
let_bndrs })
               v1' :: CoreBndr
v1' e2 :: CoreExpr
e2
  | (CoreBndr -> Bool) -> [CoreBndr] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (RnEnv2 -> CoreBndr -> Bool
inRnEnvR RnEnv2
rn_env) (CoreExpr -> [CoreBndr]
exprFreeVarsList CoreExpr
e2)
  = Maybe RuleSubst
forall a. Maybe a
Nothing     -- Occurs check failure
                -- e.g. match forall a. (\x-> a x) against (\y. y y)

  | Just e1' :: CoreExpr
e1' <- IdSubstEnv -> CoreBndr -> Maybe CoreExpr
forall a. VarEnv a -> CoreBndr -> Maybe a
lookupVarEnv IdSubstEnv
id_subst CoreBndr
v1'
  = if InScopeSet -> CoreExpr -> CoreExpr -> Bool
eqExpr (RnEnv2 -> InScopeSet
rnInScopeSet RnEnv2
rn_env) 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
  =             -- Note [Matching variable types]
                -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                -- However, we must match the *types*; e.g.
                --   forall (c::Char->Int) (x::Char).
                --      f (c x) = "RULE FIRED"
                -- We must only match on args that have the right type
                -- 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
    do { RuleSubst
subst' <- RuleMatchEnv -> RuleSubst -> Type -> Type -> Maybe RuleSubst
match_ty RuleMatchEnv
renv RuleSubst
subst (CoreBndr -> Type
idType CoreBndr
v1') (CoreExpr -> Type
exprType CoreExpr
e2)
       ; RuleSubst -> Maybe RuleSubst
forall (m :: * -> *) a. Monad m => a -> m a
return (RuleSubst
subst' { rs_id_subst :: IdSubstEnv
rs_id_subst = IdSubstEnv
id_subst' }) }
  where
    -- e2' is the result of applying flt_env to e2
    e2' :: CoreExpr
e2' | VarSet -> Bool
isEmptyVarSet VarSet
let_bndrs = CoreExpr
e2
        | Bool
otherwise = SDoc -> Subst -> CoreExpr -> CoreExpr
substExpr (String -> SDoc
text "match_tmpl_var") Subst
flt_env CoreExpr
e2

    id_subst' :: IdSubstEnv
id_subst' = IdSubstEnv -> CoreBndr -> CoreExpr -> IdSubstEnv
forall a. VarEnv a -> CoreBndr -> a -> VarEnv a
extendVarEnv (RuleSubst -> IdSubstEnv
rs_id_subst RuleSubst
subst) CoreBndr
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 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 -> Type -> Type -> Maybe RuleSubst
match_ty renv :: RuleMatchEnv
renv subst :: RuleSubst
subst ty1 :: Type
ty1 ty2 :: Type
ty2
  = do  { TvSubstEnv
tv_subst'
            <- VarSet -> RnEnv2 -> TvSubstEnv -> Type -> Type -> Maybe TvSubstEnv
Unify.ruleMatchTyKiX (RuleMatchEnv -> VarSet
rv_tmpls RuleMatchEnv
renv) (RuleMatchEnv -> RnEnv2
rv_lcl RuleMatchEnv
renv) TvSubstEnv
tv_subst Type
ty1 Type
ty2
        ; RuleSubst -> Maybe RuleSubst
forall (m :: * -> *) a. Monad m => a -> m a
return (RuleSubst
subst { rs_tv_subst :: TvSubstEnv
rs_tv_subst = TvSubstEnv
tv_subst' }) }
  where
    tv_subst :: TvSubstEnv
tv_subst = RuleSubst -> TvSubstEnv
rs_tv_subst RuleSubst
subst

{-
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 Notes 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.

cf Note [Notes in call patterns] in 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?
        f (let v = x+1 in v) v
      --> NOT!
        let v = x+1 in f (x+1) v

  (b) 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 "RuleFloatLet".

Our cunning plan is this:
  * 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.

  * The RnEnv2 in the MatchEnv binds only the local binders
    in the term (lambdas, case)

  * When we encounter a let in the term to be matched, we
    check that does not mention any locally bound (lambda, case)
    variables.  If so we fail

  * We use CoreSubst.substBind to freshen the binding, using an
    in-scope set that is the original in-scope variables plus the
    rs_bndrs (currently floated let-bindings).  So in (a) above
    we'll freshen the 'v' binding; in (b) above we'll freshen
    the *second* 'v' binding.

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


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 :: CompilerPhase               -- ^ Rule activation test
                 -> String                      -- ^ Rule pattern
                 -> (Id -> [CoreRule])          -- ^ Rules for an Id
                 -> CoreProgram                 -- ^ Bindings to check in
                 -> SDoc                        -- ^ Resulting check message
ruleCheckProgram :: CompilerPhase
-> String -> (CoreBndr -> [CoreRule]) -> [CoreBind] -> SDoc
ruleCheckProgram phase :: CompilerPhase
phase rule_pat :: String
rule_pat rules :: CoreBndr -> [CoreRule]
rules binds :: [CoreBind]
binds
  | Bag SDoc -> Bool
forall a. Bag a -> Bool
isEmptyBag Bag SDoc
results
  = String -> SDoc
text "Rule check results: no rule application sites"
  | Bool
otherwise
  = [SDoc] -> SDoc
vcat [String -> SDoc
text "Rule check results:",
          SDoc
line,
          [SDoc] -> SDoc
vcat [ SDoc
p SDoc -> SDoc -> SDoc
$$ SDoc
line | SDoc
p <- Bag SDoc -> [SDoc]
forall a. Bag a -> [a]
bagToList Bag SDoc
results ]
         ]
  where
    env :: RuleCheckEnv
env = RuleCheckEnv :: (Activation -> Bool)
-> (CoreBndr -> Unfolding)
-> String
-> (CoreBndr -> [CoreRule])
-> RuleCheckEnv
RuleCheckEnv { rc_is_active :: Activation -> Bool
rc_is_active = CompilerPhase -> Activation -> Bool
isActive CompilerPhase
phase
                       , rc_id_unf :: CoreBndr -> Unfolding
rc_id_unf    = CoreBndr -> Unfolding
idUnfolding     -- Not quite right
                                                        -- Should use activeUnfolding
                       , rc_pattern :: String
rc_pattern   = String
rule_pat
                       , rc_rules :: CoreBndr -> [CoreRule]
rc_rules = CoreBndr -> [CoreRule]
rules }
    results :: Bag SDoc
results = [Bag SDoc] -> Bag SDoc
forall a. [Bag a] -> Bag a
unionManyBags ((CoreBind -> Bag SDoc) -> [CoreBind] -> [Bag SDoc]
forall a b. (a -> b) -> [a] -> [b]
map (RuleCheckEnv -> CoreBind -> Bag SDoc
ruleCheckBind RuleCheckEnv
env) [CoreBind]
binds)
    line :: SDoc
line = String -> SDoc
text (Arity -> Char -> String
forall a. Arity -> a -> [a]
replicate 20 '-')

data RuleCheckEnv = RuleCheckEnv {
    RuleCheckEnv -> Activation -> Bool
rc_is_active :: Activation -> Bool,
    RuleCheckEnv -> CoreBndr -> Unfolding
rc_id_unf  :: IdUnfoldingFun,
    RuleCheckEnv -> String
rc_pattern :: String,
    RuleCheckEnv -> CoreBndr -> [CoreRule]
rc_rules :: Id -> [CoreRule]
}

ruleCheckBind :: RuleCheckEnv -> CoreBind -> Bag SDoc
   -- The Bag returned has one SDoc for each call site found
ruleCheckBind :: RuleCheckEnv -> CoreBind -> Bag SDoc
ruleCheckBind env :: RuleCheckEnv
env (NonRec _ r :: CoreExpr
r) = RuleCheckEnv -> CoreExpr -> Bag SDoc
ruleCheck RuleCheckEnv
env CoreExpr
r
ruleCheckBind env :: RuleCheckEnv
env (Rec prs :: [(CoreBndr, CoreExpr)]
prs)    = [Bag SDoc] -> Bag SDoc
forall a. [Bag a] -> Bag a
unionManyBags [RuleCheckEnv -> CoreExpr -> Bag SDoc
ruleCheck RuleCheckEnv
env CoreExpr
r | (_,r :: CoreExpr
r) <- [(CoreBndr, CoreExpr)]
prs]

ruleCheck :: RuleCheckEnv -> CoreExpr -> Bag SDoc
ruleCheck :: RuleCheckEnv -> CoreExpr -> Bag SDoc
ruleCheck _   (Var _)       = Bag SDoc
forall a. Bag a
emptyBag
ruleCheck _   (Lit _)       = Bag SDoc
forall a. Bag a
emptyBag
ruleCheck _   (Type _)      = Bag SDoc
forall a. Bag a
emptyBag
ruleCheck _   (Coercion _)  = Bag SDoc
forall a. Bag a
emptyBag
ruleCheck env :: RuleCheckEnv
env (App f :: CoreExpr
f a :: 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 env :: RuleCheckEnv
env (Tick _ e :: CoreExpr
e)  = RuleCheckEnv -> CoreExpr -> Bag SDoc
ruleCheck RuleCheckEnv
env CoreExpr
e
ruleCheck env :: RuleCheckEnv
env (Cast e :: CoreExpr
e _)    = RuleCheckEnv -> CoreExpr -> Bag SDoc
ruleCheck RuleCheckEnv
env CoreExpr
e
ruleCheck env :: RuleCheckEnv
env (Let bd :: CoreBind
bd e :: CoreExpr
e)    = RuleCheckEnv -> CoreBind -> Bag SDoc
ruleCheckBind RuleCheckEnv
env CoreBind
bd 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 env :: RuleCheckEnv
env (Lam _ e :: CoreExpr
e)     = RuleCheckEnv -> CoreExpr -> Bag SDoc
ruleCheck RuleCheckEnv
env CoreExpr
e
ruleCheck env :: RuleCheckEnv
env (Case e :: CoreExpr
e _ _ as :: [Alt CoreBndr]
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 CoreExpr
r | (_,_,r :: CoreExpr
r) <- [Alt CoreBndr]
as]

ruleCheckApp :: RuleCheckEnv -> Expr CoreBndr -> [Arg CoreBndr] -> Bag SDoc
ruleCheckApp :: RuleCheckEnv -> CoreExpr -> [CoreExpr] -> Bag SDoc
ruleCheckApp env :: RuleCheckEnv
env (App f :: CoreExpr
f a :: CoreExpr
a) as :: [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 env :: RuleCheckEnv
env (Var f :: CoreBndr
f) as :: [CoreExpr]
as   = RuleCheckEnv -> CoreBndr -> [CoreExpr] -> Bag SDoc
ruleCheckFun RuleCheckEnv
env CoreBndr
f [CoreExpr]
as
ruleCheckApp env :: RuleCheckEnv
env other :: CoreExpr
other _      = 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 -> CoreBndr -> [CoreExpr] -> Bag SDoc
ruleCheckFun env :: RuleCheckEnv
env fn :: CoreBndr
fn args :: [CoreExpr]
args
  | [CoreRule] -> 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 -> CoreBndr -> [CoreExpr] -> [CoreRule] -> SDoc
ruleAppCheck_help RuleCheckEnv
env CoreBndr
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 -> CoreBndr -> [CoreRule]
rc_rules RuleCheckEnv
env CoreBndr
fn)
    match :: CoreRule -> Bool
match rule :: 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 -> CoreBndr -> [CoreExpr] -> [CoreRule] -> SDoc
ruleAppCheck_help env :: RuleCheckEnv
env fn :: CoreBndr
fn args :: [CoreExpr]
args rules :: [CoreRule]
rules
  =     -- The rules match the pattern, so we want to print something
    [SDoc] -> SDoc
vcat [String -> SDoc
text "Expression:" SDoc -> SDoc -> SDoc
<+> CoreExpr -> SDoc
forall a. Outputable a => a -> SDoc
ppr (CoreExpr -> [CoreExpr] -> CoreExpr
forall b. Expr b -> [Expr b] -> Expr b
mkApps (CoreBndr -> CoreExpr
forall b. CoreBndr -> Expr b
Var CoreBndr
fn) [CoreExpr]
args),
          [SDoc] -> SDoc
vcat ((CoreRule -> SDoc) -> [CoreRule] -> [SDoc]
forall a b. (a -> b) -> [a] -> [b]
map CoreRule -> SDoc
check_rule [CoreRule]
rules)]
  where
    n_args :: Arity
n_args = [CoreExpr] -> 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` [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 rule :: CoreRule
rule = (DynFlags -> SDoc) -> SDoc
sdocWithDynFlags ((DynFlags -> SDoc) -> SDoc) -> (DynFlags -> SDoc) -> SDoc
forall a b. (a -> b) -> a -> b
$ \dflags :: DynFlags
dflags ->
                      CoreRule -> SDoc
rule_herald CoreRule
rule SDoc -> SDoc -> SDoc
<> SDoc
colon SDoc -> SDoc -> SDoc
<+> DynFlags -> CoreRule -> SDoc
rule_info DynFlags
dflags CoreRule
rule

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

    rule_info :: DynFlags -> CoreRule -> SDoc
rule_info dflags :: DynFlags
dflags rule :: CoreRule
rule
        | Just _ <- DynFlags
-> InScopeEnv
-> (Activation -> Bool)
-> CoreBndr
-> [CoreExpr]
-> [Maybe Name]
-> CoreRule
-> Maybe CoreExpr
matchRule DynFlags
dflags (InScopeSet
emptyInScopeSet, RuleCheckEnv -> CoreBndr -> Unfolding
rc_id_unf RuleCheckEnv
env)
                              Activation -> Bool
noBlackList CoreBndr
fn [CoreExpr]
args [Maybe Name]
rough_args CoreRule
rule
        = String -> SDoc
text "matches (which is very peculiar!)"

    rule_info _ (BuiltinRule {}) = String -> SDoc
text "does not match"

    rule_info _ (Rule { ru_act :: CoreRule -> Activation
ru_act = Activation
act,
                        ru_bndrs :: CoreRule -> [CoreBndr]
ru_bndrs = [CoreBndr]
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
text "active only in later phase"
        | Arity
n_args Arity -> Arity -> Bool
forall a. Ord a => a -> a -> Bool
< Arity
n_rule_args        = String -> SDoc
text "too few arguments"
        | Arity
n_mismatches Arity -> Arity -> Bool
forall a. Eq a => a -> a -> Bool
== Arity
n_rule_args = String -> SDoc
text "no arguments match"
        | Arity
n_mismatches Arity -> Arity -> Bool
forall a. Eq a => a -> a -> Bool
== 0           = String -> SDoc
text "all arguments match (considered individually), but rule as a whole does not"
        | Bool
otherwise                   = String -> SDoc
text "arguments" SDoc -> SDoc -> SDoc
<+> [Arity] -> SDoc
forall a. Outputable a => a -> SDoc
ppr [Arity]
mismatches SDoc -> SDoc -> SDoc
<+> String -> SDoc
text "do not match (1-indexing)"
        where
          n_rule_args :: Arity
n_rule_args  = [CoreExpr] -> Arity
forall (t :: * -> *) a. Foldable t => t a -> Arity
length [CoreExpr]
rule_args
          n_mismatches :: Arity
n_mismatches = [Arity] -> Arity
forall (t :: * -> *) a. Foldable t => t a -> Arity
length [Arity]
mismatches
          mismatches :: [Arity]
mismatches   = [Arity
i | (rule_arg :: CoreExpr
rule_arg, (arg :: CoreExpr
arg,i :: 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))]

          lhs_fvs :: VarSet
lhs_fvs = [CoreExpr] -> VarSet
exprsFreeVars [CoreExpr]
rule_args     -- Includes template tyvars
          match_fn :: CoreExpr -> CoreExpr -> Maybe RuleSubst
match_fn rule_arg :: CoreExpr
rule_arg arg :: CoreExpr
arg = RuleMatchEnv
-> RuleSubst -> CoreExpr -> CoreExpr -> Maybe RuleSubst
match RuleMatchEnv
renv RuleSubst
emptyRuleSubst CoreExpr
rule_arg CoreExpr
arg
                where
                  in_scope :: InScopeSet
in_scope = VarSet -> InScopeSet
mkInScopeSet (VarSet
lhs_fvs VarSet -> VarSet -> VarSet
`unionVarSet` CoreExpr -> VarSet
exprFreeVars CoreExpr
arg)
                  renv :: RuleMatchEnv
renv = RV :: RnEnv2
-> VarSet -> Subst -> (CoreBndr -> Unfolding) -> RuleMatchEnv
RV { rv_lcl :: RnEnv2
rv_lcl   = InScopeSet -> RnEnv2
mkRnEnv2 InScopeSet
in_scope
                            , rv_tmpls :: VarSet
rv_tmpls = [CoreBndr] -> VarSet
mkVarSet [CoreBndr]
rule_bndrs
                            , rv_fltR :: Subst
rv_fltR  = InScopeSet -> Subst
mkEmptySubst InScopeSet
in_scope
                            , rv_unf :: CoreBndr -> Unfolding
rv_unf   = RuleCheckEnv -> CoreBndr -> Unfolding
rc_id_unf RuleCheckEnv
env }