never executed always true always false
    1 {-
    2 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
    3 
    4 \section[CoreRules]{Rewrite rules}
    5 -}
    6 
    7 
    8 -- | Functions for collecting together and applying rewrite rules to a module.
    9 -- The 'CoreRule' datatype itself is declared elsewhere.
   10 module GHC.Core.Rules (
   11         -- ** Constructing
   12         emptyRuleBase, mkRuleBase, extendRuleBaseList,
   13         unionRuleBase, pprRuleBase,
   14 
   15         -- ** Checking rule applications
   16         ruleCheckProgram,
   17 
   18         -- ** Manipulating 'RuleInfo' rules
   19         extendRuleInfo, addRuleInfo,
   20         addIdSpecialisations,
   21 
   22         -- * Misc. CoreRule helpers
   23         rulesOfBinds, getRules, pprRulesForUser,
   24 
   25         lookupRule, mkRule, roughTopNames, initRuleOpts
   26     ) where
   27 
   28 import GHC.Prelude
   29 
   30 import GHC.Driver.Session      ( DynFlags, gopt, targetPlatform, homeUnitId_ )
   31 import GHC.Driver.Flags
   32 
   33 import GHC.Unit.Types    ( primUnitId, bignumUnitId )
   34 import GHC.Unit.Module   ( Module )
   35 import GHC.Unit.Module.Env
   36 
   37 import GHC.Core         -- All of it
   38 import GHC.Core.Subst
   39 import GHC.Core.SimpleOpt ( exprIsLambda_maybe )
   40 import GHC.Core.FVs       ( exprFreeVars, exprsFreeVars, bindFreeVars
   41                           , rulesFreeVarsDSet, exprsOrphNames, exprFreeVarsList )
   42 import GHC.Core.Utils     ( exprType, eqExpr, mkTick, mkTicks
   43                           , stripTicksTopT, stripTicksTopE
   44                           , isJoinBind )
   45 import GHC.Core.Ppr       ( pprRules )
   46 import GHC.Core.Unify as Unify ( ruleMatchTyKiX )
   47 import GHC.Core.Type as Type
   48    ( Type, TCvSubst, extendTvSubst, extendCvSubst
   49    , mkEmptyTCvSubst, substTy )
   50 import GHC.Core.Coercion as Coercion
   51 import GHC.Core.Tidy     ( tidyRules )
   52 
   53 import GHC.Tc.Utils.TcType  ( tcSplitTyConApp_maybe )
   54 import GHC.Builtin.Types    ( anyTypeOfKind )
   55 
   56 import GHC.Types.Id
   57 import GHC.Types.Id.Info ( RuleInfo( RuleInfo ) )
   58 import GHC.Types.Var
   59 import GHC.Types.Var.Env
   60 import GHC.Types.Var.Set
   61 import GHC.Types.Name    ( Name, NamedThing(..), nameIsLocalOrFrom )
   62 import GHC.Types.Name.Set
   63 import GHC.Types.Name.Env
   64 import GHC.Types.Unique.FM
   65 import GHC.Types.Tickish
   66 import GHC.Types.Basic
   67 
   68 import GHC.Data.FastString
   69 import GHC.Data.Maybe
   70 import GHC.Data.Bag
   71 
   72 import GHC.Utils.Misc as Utils
   73 import GHC.Utils.Trace
   74 import GHC.Utils.Outputable
   75 import GHC.Utils.Panic
   76 import GHC.Utils.Constants (debugIsOn)
   77 
   78 import Data.List (sortBy, mapAccumL, isPrefixOf)
   79 import Data.Function    ( on )
   80 import Control.Monad    ( guard )
   81 
   82 {-
   83 Note [Overall plumbing for rules]
   84 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   85 * After the desugarer:
   86    - The ModGuts initially contains mg_rules :: [CoreRule] of
   87      locally-declared rules for imported Ids.
   88    - Locally-declared rules for locally-declared Ids are attached to
   89      the IdInfo for that Id.  See Note [Attach rules to local ids] in
   90      GHC.HsToCore.Binds
   91 
   92 * GHC.Iface.Tidy strips off all the rules from local Ids and adds them to
   93   mg_rules, so that the ModGuts has *all* the locally-declared rules.
   94 
   95 * The HomePackageTable contains a ModDetails for each home package
   96   module.  Each contains md_rules :: [CoreRule] of rules declared in
   97   that module.  The HomePackageTable grows as ghc --make does its
   98   up-sweep.  In batch mode (ghc -c), the HPT is empty; all imported modules
   99   are treated by the "external" route, discussed next, regardless of
  100   which package they come from.
  101 
  102 * The ExternalPackageState has a single eps_rule_base :: RuleBase for
  103   Ids in other packages.  This RuleBase simply grow monotonically, as
  104   ghc --make compiles one module after another.
  105 
  106   During simplification, interface files may get demand-loaded,
  107   as the simplifier explores the unfoldings for Ids it has in
  108   its hand.  (Via an unsafePerformIO; the EPS is really a cache.)
  109   That in turn may make the EPS rule-base grow.  In contrast, the
  110   HPT never grows in this way.
  111 
  112 * The result of all this is that during Core-to-Core optimisation
  113   there are four sources of rules:
  114 
  115     (a) Rules in the IdInfo of the Id they are a rule for.  These are
  116         easy: fast to look up, and if you apply a substitution then
  117         it'll be applied to the IdInfo as a matter of course.
  118 
  119     (b) Rules declared in this module for imported Ids, kept in the
  120         ModGuts. If you do a substitution, you'd better apply the
  121         substitution to these.  There are seldom many of these.
  122 
  123     (c) Rules declared in the HomePackageTable.  These never change.
  124 
  125     (d) Rules in the ExternalPackageTable. These can grow in response
  126         to lazy demand-loading of interfaces.
  127 
  128 * At the moment (c) is carried in a reader-monad way by the GHC.Core.Opt.Monad.
  129   The HomePackageTable doesn't have a single RuleBase because technically
  130   we should only be able to "see" rules "below" this module; so we
  131   generate a RuleBase for (c) by combing rules from all the modules
  132   "below" us.  That's why we can't just select the home-package RuleBase
  133   from HscEnv.
  134 
  135   [NB: we are inconsistent here.  We should do the same for external
  136   packages, but we don't.  Same for type-class instances.]
  137 
  138 * So in the outer simplifier loop, we combine (b-d) into a single
  139   RuleBase, reading
  140      (b) from the ModGuts,
  141      (c) from the GHC.Core.Opt.Monad, and
  142      (d) from its mutable variable
  143   [Of course this means that we won't see new EPS rules that come in
  144   during a single simplifier iteration, but that probably does not
  145   matter.]
  146 
  147 
  148 ************************************************************************
  149 *                                                                      *
  150 \subsection[specialisation-IdInfo]{Specialisation info about an @Id@}
  151 *                                                                      *
  152 ************************************************************************
  153 
  154 A @CoreRule@ holds details of one rule for an @Id@, which
  155 includes its specialisations.
  156 
  157 For example, if a rule for @f@ contains the mapping:
  158 \begin{verbatim}
  159         forall a b d. [Type (List a), Type b, Var d]  ===>  f' a b
  160 \end{verbatim}
  161 then when we find an application of f to matching types, we simply replace
  162 it by the matching RHS:
  163 \begin{verbatim}
  164         f (List Int) Bool dict ===>  f' Int Bool
  165 \end{verbatim}
  166 All the stuff about how many dictionaries to discard, and what types
  167 to apply the specialised function to, are handled by the fact that the
  168 Rule contains a template for the result of the specialisation.
  169 
  170 There is one more exciting case, which is dealt with in exactly the same
  171 way.  If the specialised value is unboxed then it is lifted at its
  172 definition site and unlifted at its uses.  For example:
  173 
  174         pi :: forall a. Num a => a
  175 
  176 might have a specialisation
  177 
  178         [Int#] ===>  (case pi' of Lift pi# -> pi#)
  179 
  180 where pi' :: Lift Int# is the specialised version of pi.
  181 -}
  182 
  183 mkRule :: Module -> Bool -> Bool -> RuleName -> Activation
  184        -> Name -> [CoreBndr] -> [CoreExpr] -> CoreExpr -> CoreRule
  185 -- ^ Used to make 'CoreRule' for an 'Id' defined in the module being
  186 -- compiled. See also 'GHC.Core.CoreRule'
  187 mkRule this_mod is_auto is_local name act fn bndrs args rhs
  188   = Rule { ru_name = name, ru_fn = fn, ru_act = act,
  189            ru_bndrs = bndrs, ru_args = args,
  190            ru_rhs = rhs,
  191            ru_rough = roughTopNames args,
  192            ru_origin = this_mod,
  193            ru_orphan = orph,
  194            ru_auto = is_auto, ru_local = is_local }
  195   where
  196         -- Compute orphanhood.  See Note [Orphans] in GHC.Core.InstEnv
  197         -- A rule is an orphan only if none of the variables
  198         -- mentioned on its left-hand side are locally defined
  199     lhs_names = extendNameSet (exprsOrphNames args) fn
  200 
  201         -- Since rules get eventually attached to one of the free names
  202         -- from the definition when compiling the ABI hash, we should make
  203         -- it deterministic. This chooses the one with minimal OccName
  204         -- as opposed to uniq value.
  205     local_lhs_names = filterNameSet (nameIsLocalOrFrom this_mod) lhs_names
  206     orph = chooseOrphanAnchor local_lhs_names
  207 
  208 --------------
  209 roughTopNames :: [CoreExpr] -> [Maybe Name]
  210 -- ^ Find the \"top\" free names of several expressions.
  211 -- Such names are either:
  212 --
  213 -- 1. The function finally being applied to in an application chain
  214 --    (if that name is a GlobalId: see "GHC.Types.Var#globalvslocal"), or
  215 --
  216 -- 2. The 'TyCon' if the expression is a 'Type'
  217 --
  218 -- This is used for the fast-match-check for rules;
  219 --      if the top names don't match, the rest can't
  220 roughTopNames args = map roughTopName args
  221 
  222 roughTopName :: CoreExpr -> Maybe Name
  223 roughTopName (Type ty) = case tcSplitTyConApp_maybe ty of
  224                                Just (tc,_) -> Just (getName tc)
  225                                Nothing     -> Nothing
  226 roughTopName (Coercion _) = Nothing
  227 roughTopName (App f _) = roughTopName f
  228 roughTopName (Var f)   | isGlobalId f   -- Note [Care with roughTopName]
  229                        , isDataConWorkId f || idArity f > 0
  230                        = Just (idName f)
  231 roughTopName (Tick t e) | tickishFloatable t
  232                         = roughTopName e
  233 roughTopName _ = Nothing
  234 
  235 ruleCantMatch :: [Maybe Name] -> [Maybe Name] -> Bool
  236 -- ^ @ruleCantMatch tpl actual@ returns True only if @actual@
  237 -- definitely can't match @tpl@ by instantiating @tpl@.
  238 -- It's only a one-way match; unlike instance matching we
  239 -- don't consider unification.
  240 --
  241 -- Notice that [_$_]
  242 --      @ruleCantMatch [Nothing] [Just n2] = False@
  243 --      Reason: a template variable can be instantiated by a constant
  244 -- Also:
  245 --      @ruleCantMatch [Just n1] [Nothing] = False@
  246 --      Reason: a local variable @v@ in the actuals might [_$_]
  247 
  248 ruleCantMatch (Just n1 : ts) (Just n2 : as) = n1 /= n2 || ruleCantMatch ts as
  249 ruleCantMatch (_       : ts) (_       : as) = ruleCantMatch ts as
  250 ruleCantMatch _              _              = False
  251 
  252 {-
  253 Note [Care with roughTopName]
  254 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  255 Consider this
  256     module M where { x = a:b }
  257     module N where { ...f x...
  258                      RULE f (p:q) = ... }
  259 You'd expect the rule to match, because the matcher can
  260 look through the unfolding of 'x'.  So we must avoid roughTopName
  261 returning 'M.x' for the call (f x), or else it'll say "can't match"
  262 and we won't even try!!
  263 
  264 However, suppose we have
  265          RULE g (M.h x) = ...
  266          foo = ...(g (M.k v))....
  267 where k is a *function* exported by M.  We never really match
  268 functions (lambdas) except by name, so in this case it seems like
  269 a good idea to treat 'M.k' as a roughTopName of the call.
  270 -}
  271 
  272 pprRulesForUser :: [CoreRule] -> SDoc
  273 -- (a) tidy the rules
  274 -- (b) sort them into order based on the rule name
  275 -- (c) suppress uniques (unless -dppr-debug is on)
  276 -- This combination makes the output stable so we can use in testing
  277 -- It's here rather than in GHC.Core.Ppr because it calls tidyRules
  278 pprRulesForUser rules
  279   = withPprStyle defaultUserStyle $
  280     pprRules $
  281     sortBy (lexicalCompareFS `on` ruleName) $
  282     tidyRules emptyTidyEnv rules
  283 
  284 {-
  285 ************************************************************************
  286 *                                                                      *
  287                 RuleInfo: the rules in an IdInfo
  288 *                                                                      *
  289 ************************************************************************
  290 -}
  291 
  292 extendRuleInfo :: RuleInfo -> [CoreRule] -> RuleInfo
  293 extendRuleInfo (RuleInfo rs1 fvs1) rs2
  294   = RuleInfo (rs2 ++ rs1) (rulesFreeVarsDSet rs2 `unionDVarSet` fvs1)
  295 
  296 addRuleInfo :: RuleInfo -> RuleInfo -> RuleInfo
  297 addRuleInfo (RuleInfo rs1 fvs1) (RuleInfo rs2 fvs2)
  298   = RuleInfo (rs1 ++ rs2) (fvs1 `unionDVarSet` fvs2)
  299 
  300 addIdSpecialisations :: Id -> [CoreRule] -> Id
  301 addIdSpecialisations id rules
  302   | null rules
  303   = id
  304   | otherwise
  305   = setIdSpecialisation id $
  306     extendRuleInfo (idSpecialisation id) rules
  307 
  308 -- | Gather all the rules for locally bound identifiers from the supplied bindings
  309 rulesOfBinds :: [CoreBind] -> [CoreRule]
  310 rulesOfBinds binds = concatMap (concatMap idCoreRules . bindersOf) binds
  311 
  312 getRules :: RuleEnv -> Id -> [CoreRule]
  313 -- See Note [Where rules are found]
  314 getRules (RuleEnv { re_base = rule_base, re_visible_orphs = orphs }) fn
  315   = idCoreRules fn ++ filter (ruleIsVisible orphs) imp_rules
  316   where
  317     imp_rules = lookupNameEnv rule_base (idName fn) `orElse` []
  318 
  319 ruleIsVisible :: ModuleSet -> CoreRule -> Bool
  320 ruleIsVisible _ BuiltinRule{} = True
  321 ruleIsVisible vis_orphs Rule { ru_orphan = orph, ru_origin = origin }
  322     = notOrphan orph || origin `elemModuleSet` vis_orphs
  323 
  324 {- Note [Where rules are found]
  325 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  326 The rules for an Id come from two places:
  327   (a) the ones it is born with, stored inside the Id itself (idCoreRules fn),
  328   (b) rules added in other modules, stored in the global RuleBase (imp_rules)
  329 
  330 It's tempting to think that
  331      - LocalIds have only (a)
  332      - non-LocalIds have only (b)
  333 
  334 but that isn't quite right:
  335 
  336      - PrimOps and ClassOps are born with a bunch of rules inside the Id,
  337        even when they are imported
  338 
  339      - The rules in GHC.Core.Opt.ConstantFold.builtinRules should be active even
  340        in the module defining the Id (when it's a LocalId), but
  341        the rules are kept in the global RuleBase
  342 
  343 
  344 ************************************************************************
  345 *                                                                      *
  346                 RuleBase
  347 *                                                                      *
  348 ************************************************************************
  349 -}
  350 
  351 -- RuleBase itself is defined in GHC.Core, along with CoreRule
  352 
  353 emptyRuleBase :: RuleBase
  354 emptyRuleBase = emptyNameEnv
  355 
  356 mkRuleBase :: [CoreRule] -> RuleBase
  357 mkRuleBase rules = extendRuleBaseList emptyRuleBase rules
  358 
  359 extendRuleBaseList :: RuleBase -> [CoreRule] -> RuleBase
  360 extendRuleBaseList rule_base new_guys
  361   = foldl' extendRuleBase rule_base new_guys
  362 
  363 unionRuleBase :: RuleBase -> RuleBase -> RuleBase
  364 unionRuleBase rb1 rb2 = plusNameEnv_C (++) rb1 rb2
  365 
  366 extendRuleBase :: RuleBase -> CoreRule -> RuleBase
  367 extendRuleBase rule_base rule
  368   = extendNameEnv_Acc (:) Utils.singleton rule_base (ruleIdName rule) rule
  369 
  370 pprRuleBase :: RuleBase -> SDoc
  371 pprRuleBase rules = pprUFM rules $ \rss ->
  372   vcat [ pprRules (tidyRules emptyTidyEnv rs)
  373        | rs <- rss ]
  374 
  375 {-
  376 ************************************************************************
  377 *                                                                      *
  378                         Matching
  379 *                                                                      *
  380 ************************************************************************
  381 -}
  382 
  383 -- | The main rule matching function. Attempts to apply all (active)
  384 -- supplied rules to this instance of an application in a given
  385 -- context, returning the rule applied and the resulting expression if
  386 -- successful.
  387 lookupRule :: RuleOpts -> InScopeEnv
  388            -> (Activation -> Bool)      -- When rule is active
  389            -> Id -> [CoreExpr]
  390            -> [CoreRule] -> Maybe (CoreRule, CoreExpr)
  391 
  392 -- See Note [Extra args in rule matching]
  393 -- See comments on matchRule
  394 lookupRule opts rule_env@(in_scope,_) is_active fn args rules
  395   = -- pprTrace "matchRules" (ppr fn <+> ppr args $$ ppr rules ) $
  396     case go [] rules of
  397         []     -> Nothing
  398         (m:ms) -> Just (findBest in_scope (fn,args') m ms)
  399   where
  400     rough_args = map roughTopName args
  401 
  402     -- Strip ticks from arguments, see note [Tick annotations in RULE
  403     -- matching]. We only collect ticks if a rule actually matches -
  404     -- this matters for performance tests.
  405     args' = map (stripTicksTopE tickishFloatable) args
  406     ticks = concatMap (stripTicksTopT tickishFloatable) args
  407 
  408     go :: [(CoreRule,CoreExpr)] -> [CoreRule] -> [(CoreRule,CoreExpr)]
  409     go ms [] = ms
  410     go ms (r:rs)
  411       | Just e <- matchRule opts rule_env is_active fn args' rough_args r
  412       = go ((r,mkTicks ticks e):ms) rs
  413       | otherwise
  414       = -- pprTrace "match failed" (ppr r $$ ppr args $$
  415         --   ppr [ (arg_id, unfoldingTemplate unf)
  416         --       | Var arg_id <- args
  417         --       , let unf = idUnfolding arg_id
  418         --       , isCheapUnfolding unf] )
  419         go ms rs
  420 
  421 findBest :: InScopeSet -> (Id, [CoreExpr])
  422          -> (CoreRule,CoreExpr) -> [(CoreRule,CoreExpr)] -> (CoreRule,CoreExpr)
  423 -- All these pairs matched the expression
  424 -- Return the pair the most specific rule
  425 -- The (fn,args) is just for overlap reporting
  426 
  427 findBest _        _      (rule,ans)   [] = (rule,ans)
  428 findBest in_scope target (rule1,ans1) ((rule2,ans2):prs)
  429   | isMoreSpecific in_scope rule1 rule2 = findBest in_scope target (rule1,ans1) prs
  430   | isMoreSpecific in_scope rule2 rule1 = findBest in_scope target (rule2,ans2) prs
  431   | debugIsOn = let pp_rule rule
  432                       = ifPprDebug (ppr rule)
  433                                    (doubleQuotes (ftext (ruleName rule)))
  434                 in pprTrace "Rules.findBest: rule overlap (Rule 1 wins)"
  435                          (vcat [ whenPprDebug $
  436                                  text "Expression to match:" <+> ppr fn
  437                                  <+> sep (map ppr args)
  438                                , text "Rule 1:" <+> pp_rule rule1
  439                                , text "Rule 2:" <+> pp_rule rule2]) $
  440                 findBest in_scope target (rule1,ans1) prs
  441   | otherwise = findBest in_scope target (rule1,ans1) prs
  442   where
  443     (fn,args) = target
  444 
  445 isMoreSpecific :: InScopeSet -> CoreRule -> CoreRule -> Bool
  446 -- This tests if one rule is more specific than another
  447 -- We take the view that a BuiltinRule is less specific than
  448 -- anything else, because we want user-define rules to "win"
  449 -- In particular, class ops have a built-in rule, but we
  450 -- any user-specific rules to win
  451 --   eg (#4397)
  452 --      truncate :: (RealFrac a, Integral b) => a -> b
  453 --      {-# RULES "truncate/Double->Int" truncate = double2Int #-}
  454 --      double2Int :: Double -> Int
  455 --   We want the specific RULE to beat the built-in class-op rule
  456 isMoreSpecific _        (BuiltinRule {}) _                = False
  457 isMoreSpecific _        (Rule {})        (BuiltinRule {}) = True
  458 isMoreSpecific in_scope (Rule { ru_bndrs = bndrs1, ru_args = args1 })
  459                         (Rule { ru_bndrs = bndrs2, ru_args = args2
  460                               , ru_name = rule_name2, ru_rhs = rhs2 })
  461   = isJust (matchN (full_in_scope, id_unfolding_fun)
  462                    rule_name2 bndrs2 args2 args1 rhs2)
  463   where
  464    id_unfolding_fun _ = NoUnfolding     -- Don't expand in templates
  465    full_in_scope = in_scope `extendInScopeSetList` bndrs1
  466 
  467 noBlackList :: Activation -> Bool
  468 noBlackList _ = False           -- Nothing is black listed
  469 
  470 {-
  471 Note [Extra args in rule matching]
  472 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  473 If we find a matching rule, we return (Just (rule, rhs)),
  474 but the rule firing has only consumed as many of the input args
  475 as the ruleArity says.  It's up to the caller to keep track
  476 of any left-over args.  E.g. if you call
  477         lookupRule ... f [e1, e2, e3]
  478 and it returns Just (r, rhs), where r has ruleArity 2
  479 then the real rewrite is
  480         f e1 e2 e3 ==> rhs e3
  481 
  482 You might think it'd be cleaner for lookupRule to deal with the
  483 leftover arguments, by applying 'rhs' to them, but the main call
  484 in the Simplifier works better as it is.  Reason: the 'args' passed
  485 to lookupRule are the result of a lazy substitution
  486 -}
  487 
  488 ------------------------------------
  489 matchRule :: RuleOpts -> InScopeEnv -> (Activation -> Bool)
  490           -> Id -> [CoreExpr] -> [Maybe Name]
  491           -> CoreRule -> Maybe CoreExpr
  492 
  493 -- If (matchRule rule args) returns Just (name,rhs)
  494 -- then (f args) matches the rule, and the corresponding
  495 -- rewritten RHS is rhs
  496 --
  497 -- The returned expression is occurrence-analysed
  498 --
  499 --      Example
  500 --
  501 -- The rule
  502 --      forall f g x. map f (map g x) ==> map (f . g) x
  503 -- is stored
  504 --      CoreRule "map/map"
  505 --               [f,g,x]                -- tpl_vars
  506 --               [f,map g x]            -- tpl_args
  507 --               map (f.g) x)           -- rhs
  508 --
  509 -- Then the call: matchRule the_rule [e1,map e2 e3]
  510 --        = Just ("map/map", (\f,g,x -> rhs) e1 e2 e3)
  511 --
  512 -- Any 'surplus' arguments in the input are simply put on the end
  513 -- of the output.
  514 
  515 matchRule opts rule_env _is_active fn args _rough_args
  516           (BuiltinRule { ru_try = match_fn })
  517 -- Built-in rules can't be switched off, it seems
  518   = case match_fn opts rule_env fn args of
  519         Nothing   -> Nothing
  520         Just expr -> Just expr
  521 
  522 matchRule _ rule_env is_active _ args rough_args
  523           (Rule { ru_name = rule_name, ru_act = act, ru_rough = tpl_tops
  524                 , ru_bndrs = tpl_vars, ru_args = tpl_args, ru_rhs = rhs })
  525   | not (is_active act)               = Nothing
  526   | ruleCantMatch tpl_tops rough_args = Nothing
  527   | otherwise = matchN rule_env rule_name tpl_vars tpl_args args rhs
  528 
  529 
  530 -- | Initialize RuleOpts from DynFlags
  531 initRuleOpts :: DynFlags -> RuleOpts
  532 initRuleOpts dflags = RuleOpts
  533   { roPlatform                = targetPlatform dflags
  534   , roNumConstantFolding      = gopt Opt_NumConstantFolding dflags
  535   , roExcessRationalPrecision = gopt Opt_ExcessPrecision dflags
  536     -- disable bignum rules in ghc-prim and ghc-bignum itself
  537   , roBignumRules             = homeUnitId_ dflags /= primUnitId
  538                                 && homeUnitId_ dflags /= bignumUnitId
  539   }
  540 
  541 
  542 ---------------------------------------
  543 matchN  :: InScopeEnv
  544         -> RuleName -> [Var] -> [CoreExpr]
  545         -> [CoreExpr] -> CoreExpr           -- ^ Target; can have more elements than the template
  546         -> Maybe CoreExpr
  547 -- For a given match template and context, find bindings to wrap around
  548 -- the entire result and what should be substituted for each template variable.
  549 -- Fail if there are two few actual arguments from the target to match the template
  550 
  551 matchN (in_scope, id_unf) rule_name tmpl_vars tmpl_es target_es rhs
  552   = do  { rule_subst <- go init_menv emptyRuleSubst tmpl_es target_es
  553         ; let (_, matched_es) = mapAccumL (lookup_tmpl rule_subst)
  554                                           (mkEmptyTCvSubst in_scope) $
  555                                 tmpl_vars `zip` tmpl_vars1
  556               bind_wrapper = rs_binds rule_subst
  557                              -- Floated bindings; see Note [Matching lets]
  558        ; return (bind_wrapper $
  559                  mkLams tmpl_vars rhs `mkApps` matched_es) }
  560   where
  561     (init_rn_env, tmpl_vars1) = mapAccumL rnBndrL (mkRnEnv2 in_scope) tmpl_vars
  562                   -- See Note [Cloning the template binders]
  563 
  564     init_menv = RV { rv_tmpls = mkVarSet tmpl_vars1
  565                    , rv_lcl   = init_rn_env
  566                    , rv_fltR  = mkEmptySubst (rnInScopeSet init_rn_env)
  567                    , rv_unf   = id_unf }
  568 
  569     go _    subst []     _      = Just subst
  570     go _    _     _      []     = Nothing       -- Fail if too few actual args
  571     go menv subst (t:ts) (e:es) = do { subst1 <- match menv subst t e
  572                                      ; go menv subst1 ts es }
  573 
  574     lookup_tmpl :: RuleSubst -> TCvSubst -> (InVar,OutVar) -> (TCvSubst, CoreExpr)
  575                    -- Need to return a RuleSubst solely for the benefit of mk_fake_ty
  576     lookup_tmpl (RS { rs_tv_subst = tv_subst, rs_id_subst = id_subst })
  577                 tcv_subst (tmpl_var, tmpl_var1)
  578         | isId tmpl_var1
  579         = case lookupVarEnv id_subst tmpl_var1 of
  580             Just e | Coercion co <- e
  581                    -> (Type.extendCvSubst tcv_subst tmpl_var1 co, Coercion co)
  582                    | otherwise
  583                    -> (tcv_subst, e)
  584             Nothing | Just refl_co <- isReflCoVar_maybe tmpl_var1
  585                     , let co = Coercion.substCo tcv_subst refl_co
  586                     -> -- See Note [Unbound RULE binders]
  587                        (Type.extendCvSubst tcv_subst tmpl_var1 co, Coercion co)
  588                     | otherwise
  589                     -> unbound tmpl_var
  590 
  591         | otherwise
  592         = (Type.extendTvSubst tcv_subst tmpl_var1 ty', Type ty')
  593         where
  594           ty' = case lookupVarEnv tv_subst tmpl_var1 of
  595                   Just ty -> ty
  596                   Nothing -> fake_ty   -- See Note [Unbound RULE binders]
  597           fake_ty = anyTypeOfKind (Type.substTy tcv_subst (tyVarKind tmpl_var1))
  598                     -- This substitution is the sole reason we accumulate
  599                     -- TCvSubst in lookup_tmpl
  600 
  601     unbound tmpl_var
  602        = pprPanic "Template variable unbound in rewrite rule" $
  603          vcat [ text "Variable:" <+> ppr tmpl_var <+> dcolon <+> ppr (varType tmpl_var)
  604               , text "Rule" <+> pprRuleName rule_name
  605               , text "Rule bndrs:" <+> ppr tmpl_vars
  606               , text "LHS args:" <+> ppr tmpl_es
  607               , text "Actual args:" <+> ppr target_es ]
  608 
  609 
  610 {- Note [Unbound RULE binders]
  611 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  612 It can be the case that the binder in a rule is not actually
  613 bound on the LHS:
  614 
  615 * Type variables.  Type synonyms with phantom args can give rise to
  616   unbound template type variables.  Consider this (#10689,
  617   simplCore/should_compile/T10689):
  618 
  619     type Foo a b = b
  620 
  621     f :: Eq a => a -> Bool
  622     f x = x==x
  623 
  624     {-# RULES "foo" forall (x :: Foo a Char). f x = True #-}
  625     finkle = f 'c'
  626 
  627   The rule looks like
  628     forall (a::*) (d::Eq Char) (x :: Foo a Char).
  629          f (Foo a Char) d x = True
  630 
  631   Matching the rule won't bind 'a', and legitimately so.  We fudge by
  632   pretending that 'a' is bound to (Any :: *).
  633 
  634 * Coercion variables.  On the LHS of a RULE for a local binder
  635   we might have
  636     RULE forall (c :: a~b). f (x |> c) = e
  637   Now, if that binding is inlined, so that a=b=Int, we'd get
  638     RULE forall (c :: Int~Int). f (x |> c) = e
  639   and now when we simplify the LHS (Simplify.simplRule) we
  640   optCoercion (look at the CoVarCo case) will turn that 'c' into Refl:
  641     RULE forall (c :: Int~Int). f (x |> <Int>) = e
  642   and then perhaps drop it altogether.  Now 'c' is unbound.
  643 
  644   It's tricky to be sure this never happens, so instead I
  645   say it's OK to have an unbound coercion binder in a RULE
  646   provided its type is (c :: t~t).  Then, when the RULE
  647   fires we can substitute <t> for c.
  648 
  649   This actually happened (in a RULE for a local function)
  650   in #13410, and also in test T10602.
  651 
  652 Note [Cloning the template binders]
  653 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  654 Consider the following match (example 1):
  655         Template:  forall x.  f x
  656         Target:               f (x+1)
  657 This should succeed, because the template variable 'x' has nothing to
  658 do with the 'x' in the target.
  659 
  660 Likewise this one (example 2):
  661         Template:  forall x. f (\x.x)
  662         Target:              f (\y.y)
  663 
  664 We achieve this simply by using rnBndrL to clone the template
  665 binders if they are already in scope.
  666 
  667 ------ Historical note -------
  668 At one point I tried simply adding the template binders to the
  669 in-scope set /without/ cloning them, but that failed in a horribly
  670 obscure way in #14777.  Problem was that during matching we look
  671 up target-term variables in the in-scope set (see Note [Lookup
  672 in-scope]).  If a target-term variable happens to name-clash with a
  673 template variable, that lookup will find the template variable, which
  674 is /utterly/ bogus.  In #14777, this transformed a term variable
  675 into a type variable, and then crashed when we wanted its idInfo.
  676 ------ End of historical note -------
  677 
  678 
  679 ************************************************************************
  680 *                                                                      *
  681                    The main matcher
  682 *                                                                      *
  683 ********************************************************************* -}
  684 
  685 -- * The domain of the TvSubstEnv and IdSubstEnv are the template
  686 --   variables passed into the match.
  687 --
  688 -- * The BindWrapper in a RuleSubst are the bindings floated out
  689 --   from nested matches; see the Let case of match, below
  690 --
  691 data RuleMatchEnv
  692   = RV { rv_lcl   :: RnEnv2          -- Renamings for *local bindings*
  693                                      --   (lambda/case)
  694        , rv_tmpls :: VarSet          -- Template variables
  695                                      --   (after applying envL of rv_lcl)
  696        , rv_fltR  :: Subst           -- Renamings for floated let-bindings
  697                                      --   (domain disjoint from envR of rv_lcl)
  698                                      -- See Note [Matching lets]
  699        , rv_unf :: IdUnfoldingFun
  700        }
  701 
  702 rvInScopeEnv :: RuleMatchEnv -> InScopeEnv
  703 rvInScopeEnv renv = (rnInScopeSet (rv_lcl renv), rv_unf renv)
  704 
  705 data RuleSubst = RS { rs_tv_subst :: TvSubstEnv   -- Range is the
  706                     , rs_id_subst :: IdSubstEnv   --   template variables
  707                     , rs_binds    :: BindWrapper  -- Floated bindings
  708                     , rs_bndrs    :: [Var]        -- Variables bound by floated lets
  709                     }
  710 
  711 type BindWrapper = CoreExpr -> CoreExpr
  712   -- See Notes [Matching lets] and [Matching cases]
  713   -- we represent the floated bindings as a core-to-core function
  714 
  715 emptyRuleSubst :: RuleSubst
  716 emptyRuleSubst = RS { rs_tv_subst = emptyVarEnv, rs_id_subst = emptyVarEnv
  717                     , rs_binds = \e -> e, rs_bndrs = [] }
  718 
  719 --      At one stage I tried to match even if there are more
  720 --      template args than real args.
  721 
  722 --      I now think this is probably a bad idea.
  723 --      Should the template (map f xs) match (map g)?  I think not.
  724 --      For a start, in general eta expansion wastes work.
  725 --      SLPJ July 99
  726 
  727 match :: RuleMatchEnv
  728       -> RuleSubst
  729       -> CoreExpr               -- Template
  730       -> CoreExpr               -- Target
  731       -> Maybe RuleSubst
  732 
  733 -- We look through certain ticks. See Note [Tick annotations in RULE matching]
  734 match renv subst e1 (Tick t e2)
  735   | tickishFloatable t
  736   = match renv subst' e1 e2
  737   where subst' = subst { rs_binds = rs_binds subst . mkTick t }
  738 match renv subst (Tick t e1) e2
  739   -- Ignore ticks in rule template.
  740   | tickishFloatable t
  741   =  match renv subst e1 e2
  742 match _ _ e@Tick{} _
  743   = pprPanic "Tick in rule" (ppr e)
  744 
  745 -- See the notes with Unify.match, which matches types
  746 -- Everything is very similar for terms
  747 
  748 -- Interesting examples:
  749 -- Consider matching
  750 --      \x->f      against    \f->f
  751 -- When we meet the lambdas we must remember to rename f to f' in the
  752 -- second expression.  The RnEnv2 does that.
  753 --
  754 -- Consider matching
  755 --      forall a. \b->b    against   \a->3
  756 -- We must rename the \a.  Otherwise when we meet the lambdas we
  757 -- might substitute [a/b] in the template, and then erroneously
  758 -- succeed in matching what looks like the template variable 'a' against 3.
  759 
  760 -- The Var case follows closely what happens in GHC.Core.Unify.match
  761 match renv subst (Var v1) e2
  762   = match_var renv subst v1 e2
  763 
  764 match renv subst e1 (Var v2)      -- Note [Expanding variables]
  765   | not (inRnEnvR rn_env v2) -- Note [Do not expand locally-bound variables]
  766   , Just e2' <- expandUnfolding_maybe (rv_unf renv v2')
  767   = match (renv { rv_lcl = nukeRnEnvR rn_env }) subst e1 e2'
  768   where
  769     v2'    = lookupRnInScope rn_env v2
  770     rn_env = rv_lcl renv
  771         -- Notice that we look up v2 in the in-scope set
  772         -- See Note [Lookup in-scope]
  773         -- No need to apply any renaming first (hence no rnOccR)
  774         -- because of the not-inRnEnvR
  775 
  776 match renv subst e1 (Let bind e2)
  777   | -- pprTrace "match:Let" (vcat [ppr bind, ppr $ okToFloat (rv_lcl renv) (bindFreeVars bind)]) $
  778     not (isJoinBind bind) -- can't float join point out of argument position
  779   , okToFloat (rv_lcl renv) (bindFreeVars bind) -- See Note [Matching lets]
  780   = match (renv { rv_fltR = flt_subst'
  781                 , rv_lcl  = rv_lcl renv `extendRnInScopeSetList` new_bndrs })
  782                 -- We are floating the let-binding out, as if it had enclosed
  783                 -- the entire target from Day 1.  So we must add its binders to
  784                 -- the in-scope set (#20200)
  785           (subst { rs_binds = rs_binds subst . Let bind'
  786                  , rs_bndrs = new_bndrs ++ rs_bndrs subst })
  787           e1 e2
  788   | otherwise
  789   = Nothing
  790   where
  791     (flt_subst', bind') = substBind (rv_fltR renv) bind
  792     new_bndrs           = bindersOf bind'
  793 
  794 {- Disabled: see Note [Matching cases] below
  795 match renv (tv_subst, id_subst, binds) e1
  796       (Case scrut case_bndr ty [(con, alt_bndrs, rhs)])
  797   | exprOkForSpeculation scrut  -- See Note [Matching cases]
  798   , okToFloat rn_env bndrs (exprFreeVars scrut)
  799   = match (renv { me_env = rn_env' })
  800           (tv_subst, id_subst, binds . case_wrap)
  801           e1 rhs
  802   where
  803     rn_env   = me_env renv
  804     rn_env'  = extendRnInScopeList rn_env bndrs
  805     bndrs    = case_bndr : alt_bndrs
  806     case_wrap rhs' = Case scrut case_bndr ty [(con, alt_bndrs, rhs')]
  807 -}
  808 
  809 match _ subst (Lit lit1) (Lit lit2)
  810   | lit1 == lit2
  811   = Just subst
  812 
  813 match renv subst (App f1 a1) (App f2 a2)
  814   = do  { subst' <- match renv subst f1 f2
  815         ; match renv subst' a1 a2 }
  816 
  817 match renv subst (Lam x1 e1) e2
  818   | Just (x2, e2, ts) <- exprIsLambda_maybe (rvInScopeEnv renv) e2
  819   = let renv'  = rnMatchBndr2 renv x1 x2
  820         subst' = subst { rs_binds = rs_binds subst . flip (foldr mkTick) ts }
  821     in  match renv' subst' e1 e2
  822 
  823 match renv subst (Case e1 x1 ty1 alts1) (Case e2 x2 ty2 alts2)
  824   = do  { subst1 <- match_ty renv subst ty1 ty2
  825         ; subst2 <- match renv subst1 e1 e2
  826         ; let renv' = rnMatchBndr2 renv x1 x2
  827         ; match_alts renv' subst2 alts1 alts2   -- Alts are both sorted
  828         }
  829 
  830 match renv subst (Type ty1) (Type ty2)
  831   = match_ty renv subst ty1 ty2
  832 match renv subst (Coercion co1) (Coercion co2)
  833   = match_co renv subst co1 co2
  834 
  835 match renv subst (Cast e1 co1) (Cast e2 co2)
  836   = do  { subst1 <- match_co renv subst co1 co2
  837         ; match renv subst1 e1 e2 }
  838 
  839 -- Everything else fails
  840 match _ _ _e1 _e2 = -- pprTrace "Failing at" ((text "e1:" <+> ppr _e1) $$ (text "e2:" <+> ppr _e2)) $
  841                     Nothing
  842 
  843 -------------
  844 match_co :: RuleMatchEnv
  845          -> RuleSubst
  846          -> Coercion
  847          -> Coercion
  848          -> Maybe RuleSubst
  849 match_co renv subst co1 co2
  850   | Just cv <- getCoVar_maybe co1
  851   = match_var renv subst cv (Coercion co2)
  852   | Just (ty1, r1) <- isReflCo_maybe co1
  853   = do { (ty2, r2) <- isReflCo_maybe co2
  854        ; guard (r1 == r2)
  855        ; match_ty renv subst ty1 ty2 }
  856 match_co renv subst co1 co2
  857   | Just (tc1, cos1) <- splitTyConAppCo_maybe co1
  858   = case splitTyConAppCo_maybe co2 of
  859       Just (tc2, cos2)
  860         |  tc1 == tc2
  861         -> match_cos renv subst cos1 cos2
  862       _ -> Nothing
  863 match_co renv subst co1 co2
  864   | Just (arg1, res1) <- splitFunCo_maybe co1
  865   = case splitFunCo_maybe co2 of
  866       Just (arg2, res2)
  867         -> match_cos renv subst [arg1, res1] [arg2, res2]
  868       _ -> Nothing
  869 match_co _ _ co1 co2
  870     -- Currently just deals with CoVarCo, TyConAppCo and Refl
  871   | debugIsOn
  872   = pprTrace "match_co: needs more cases" (ppr co1 $$ ppr co2) Nothing
  873   | otherwise
  874   = Nothing
  875 
  876 match_cos :: RuleMatchEnv
  877          -> RuleSubst
  878          -> [Coercion]
  879          -> [Coercion]
  880          -> Maybe RuleSubst
  881 match_cos renv subst (co1:cos1) (co2:cos2) =
  882   do { subst' <- match_co renv subst co1 co2
  883      ; match_cos renv subst' cos1 cos2 }
  884 match_cos _ subst [] [] = Just subst
  885 match_cos _ _ cos1 cos2 = pprTrace "match_cos: not same length" (ppr cos1 $$ ppr cos2) Nothing
  886 
  887 -------------
  888 rnMatchBndr2 :: RuleMatchEnv -> Var -> Var -> RuleMatchEnv
  889 rnMatchBndr2 renv x1 x2
  890   = renv { rv_lcl  = rnBndr2 (rv_lcl renv) x1 x2
  891          , rv_fltR = delBndr (rv_fltR renv) x2 }
  892 
  893 
  894 ------------------------------------------
  895 match_alts :: RuleMatchEnv
  896            -> RuleSubst
  897            -> [CoreAlt]         -- Template
  898            -> [CoreAlt]         -- Target
  899            -> Maybe RuleSubst
  900 match_alts _ subst [] []
  901   = return subst
  902 match_alts renv subst (Alt c1 vs1 r1:alts1) (Alt c2 vs2 r2:alts2)
  903   | c1 == c2
  904   = do  { subst1 <- match renv' subst r1 r2
  905         ; match_alts renv subst1 alts1 alts2 }
  906   where
  907     renv' = foldl' mb renv (vs1 `zip` vs2)
  908     mb renv (v1,v2) = rnMatchBndr2 renv v1 v2
  909 
  910 match_alts _ _ _ _
  911   = Nothing
  912 
  913 ------------------------------------------
  914 okToFloat :: RnEnv2 -> VarSet -> Bool
  915 okToFloat rn_env bind_fvs
  916   = allVarSet not_captured bind_fvs
  917   where
  918     not_captured fv = not (inRnEnvR rn_env fv)
  919 
  920 ------------------------------------------
  921 match_var :: RuleMatchEnv
  922           -> RuleSubst
  923           -> Var                -- Template
  924           -> CoreExpr        -- Target
  925           -> Maybe RuleSubst
  926 match_var renv@(RV { rv_tmpls = tmpls, rv_lcl = rn_env, rv_fltR = flt_env })
  927           subst v1 e2
  928   | v1' `elemVarSet` tmpls
  929   = match_tmpl_var renv subst v1' e2
  930 
  931   | otherwise   -- v1' is not a template variable; check for an exact match with e2
  932   = case e2 of  -- Remember, envR of rn_env is disjoint from rv_fltR
  933        Var v2 | Just v2' <- rnOccR_maybe rn_env v2
  934               -> -- v2 was bound by a nested lambda or case
  935                  if v1' == v2' then Just subst
  936                                else Nothing
  937 
  938               -- v2 is not bound nestedly; it is free
  939               -- in the whole expression being matched
  940               -- So it will be in the InScopeSet for flt_env (#20200)
  941               | Var v2' <- lookupIdSubst flt_env v2
  942               , v1' == v2'
  943               -> Just subst
  944               | otherwise
  945               -> Nothing
  946 
  947        _ -> Nothing
  948 
  949   where
  950     v1' = rnOccL rn_env v1
  951         -- If the template is
  952         --      forall x. f x (\x -> x) = ...
  953         -- Then the x inside the lambda isn't the
  954         -- template x, so we must rename first!
  955 
  956 ------------------------------------------
  957 match_tmpl_var :: RuleMatchEnv
  958                -> RuleSubst
  959                -> Var                -- Template
  960                -> CoreExpr              -- Target
  961                -> Maybe RuleSubst
  962 
  963 match_tmpl_var renv@(RV { rv_lcl = rn_env, rv_fltR = flt_env })
  964                subst@(RS { rs_id_subst = id_subst, rs_bndrs = let_bndrs })
  965                v1' e2
  966   | any (inRnEnvR rn_env) (exprFreeVarsList e2)
  967   = Nothing     -- Occurs check failure
  968                 -- e.g. match forall a. (\x-> a x) against (\y. y y)
  969 
  970   | Just e1' <- lookupVarEnv id_subst v1'
  971   = if eqExpr (rnInScopeSet rn_env) e1' e2'
  972     then Just subst
  973     else Nothing
  974 
  975   | otherwise
  976   =             -- Note [Matching variable types]
  977                 -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  978                 -- However, we must match the *types*; e.g.
  979                 --   forall (c::Char->Int) (x::Char).
  980                 --      f (c x) = "RULE FIRED"
  981                 -- We must only match on args that have the right type
  982                 -- It's actually quite difficult to come up with an example that shows
  983                 -- you need type matching, esp since matching is left-to-right, so type
  984                 -- args get matched first.  But it's possible (e.g. simplrun008) and
  985                 -- this is the Right Thing to do
  986     do { subst' <- match_ty renv subst (idType v1') (exprType e2)
  987        ; return (subst' { rs_id_subst = id_subst' }) }
  988   where
  989     -- e2' is the result of applying flt_env to e2
  990     e2' | null let_bndrs = e2
  991         | otherwise = substExpr flt_env e2
  992 
  993     id_subst' = extendVarEnv (rs_id_subst subst) v1' e2'
  994          -- No further renaming to do on e2',
  995          -- because no free var of e2' is in the rnEnvR of the envt
  996 
  997 ------------------------------------------
  998 match_ty :: RuleMatchEnv
  999          -> RuleSubst
 1000          -> Type                -- Template
 1001          -> Type                -- Target
 1002          -> Maybe RuleSubst
 1003 -- Matching Core types: use the matcher in GHC.Tc.Utils.TcType.
 1004 -- Notice that we treat newtypes as opaque.  For example, suppose
 1005 -- we have a specialised version of a function at a newtype, say
 1006 --      newtype T = MkT Int
 1007 -- We only want to replace (f T) with f', not (f Int).
 1008 
 1009 match_ty renv subst ty1 ty2
 1010   = do  { tv_subst'
 1011             <- Unify.ruleMatchTyKiX (rv_tmpls renv) (rv_lcl renv) tv_subst ty1 ty2
 1012         ; return (subst { rs_tv_subst = tv_subst' }) }
 1013   where
 1014     tv_subst = rs_tv_subst subst
 1015 
 1016 {-
 1017 Note [Expanding variables]
 1018 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 1019 Here is another Very Important rule: if the term being matched is a
 1020 variable, we expand it so long as its unfolding is "expandable". (Its
 1021 occurrence information is not necessarily up to date, so we don't use
 1022 it.)  By "expandable" we mean a WHNF or a "constructor-like" application.
 1023 This is the key reason for "constructor-like" Ids.  If we have
 1024      {-# NOINLINE [1] CONLIKE g #-}
 1025      {-# RULE f (g x) = h x #-}
 1026 then in the term
 1027    let v = g 3 in ....(f v)....
 1028 we want to make the rule fire, to replace (f v) with (h 3).
 1029 
 1030 Note [Do not expand locally-bound variables]
 1031 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1032 Do *not* expand locally-bound variables, else there's a worry that the
 1033 unfolding might mention variables that are themselves renamed.
 1034 Example
 1035           case x of y { (p,q) -> ...y... }
 1036 Don't expand 'y' to (p,q) because p,q might themselves have been
 1037 renamed.  Essentially we only expand unfoldings that are "outside"
 1038 the entire match.
 1039 
 1040 Hence, (a) the guard (not (isLocallyBoundR v2))
 1041        (b) when we expand we nuke the renaming envt (nukeRnEnvR).
 1042 
 1043 Note [Tick annotations in RULE matching]
 1044 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1045 
 1046 We used to unconditionally look through ticks in both template and
 1047 expression being matched. This is actually illegal for counting or
 1048 cost-centre-scoped ticks, because we have no place to put them without
 1049 changing entry counts and/or costs. So now we just fail the match in
 1050 these cases.
 1051 
 1052 On the other hand, where we are allowed to insert new cost into the
 1053 tick scope, we can float them upwards to the rule application site.
 1054 
 1055 Moreover, we may encounter ticks in the template of a rule. There are a few
 1056 ways in which these may be introduced (e.g. #18162, #17619). Such ticks are
 1057 ignored by the matcher. See Note [Simplifying rules] in
 1058 GHC.Core.Opt.Simplify.Utils for details.
 1059 
 1060 cf Note [Tick annotations in call patterns] in GHC.Core.Opt.SpecConstr
 1061 
 1062 Note [Matching lets]
 1063 ~~~~~~~~~~~~~~~~~~~~
 1064 Matching a let-expression.  Consider
 1065         RULE forall x.  f (g x) = <rhs>
 1066 and target expression
 1067         f (let { w=R } in g E))
 1068 Then we'd like the rule to match, to generate
 1069         let { w=R } in (\x. <rhs>) E
 1070 In effect, we want to float the let-binding outward, to enable
 1071 the match to happen.  This is the WHOLE REASON for accumulating
 1072 bindings in the RuleSubst
 1073 
 1074 We can only do this if the free variables of R are not bound by the
 1075 part of the target expression outside the let binding; e.g.
 1076         f (\v. let w = v+1 in g E)
 1077 Here we obviously cannot float the let-binding for w.  Hence the
 1078 use of okToFloat.
 1079 
 1080 There are a couple of tricky points.
 1081   (a) What if floating the binding captures a variable?
 1082         f (let v = x+1 in v) v
 1083       --> NOT!
 1084         let v = x+1 in f (x+1) v
 1085 
 1086   (b) What if two non-nested let bindings bind the same variable?
 1087         f (let v = e1 in b1) (let v = e2 in b2)
 1088       --> NOT!
 1089         let v = e1 in let v = e2 in (f b2 b2)
 1090       See testsuite test "RuleFloatLet".
 1091 
 1092 Our cunning plan is this:
 1093   * Along with the growing substitution for template variables
 1094     we maintain a growing set of floated let-bindings (rs_binds)
 1095     plus the set of variables thus bound (rs_bndrs).
 1096 
 1097   * The RnEnv2 in the MatchEnv binds only the local binders
 1098     in the term (lambdas, case), not the floated let-bndrs.
 1099 
 1100   * When we encounter a let in the term to be matched, we use
 1101     okToFloat check that does not mention any locally bound (lambda,
 1102     case) variables.  If so we fail.
 1103 
 1104   * We use GHC.Core.Subst.substBind to freshen the binding, using an
 1105     in-scope set that is the original in-scope variables plus the
 1106     rs_bndrs (currently floated let-bindings).  So in (a) above
 1107     we'll freshen the 'v' binding; in (b) above we'll freshen
 1108     the *second* 'v' binding.
 1109 
 1110   * We apply that freshening substitution, in a lexically-scoped
 1111     way to the term, although lazily; this is the rv_fltR field.
 1112 
 1113 
 1114 Note [Matching cases]
 1115 ~~~~~~~~~~~~~~~~~~~~~
 1116 {- NOTE: This idea is currently disabled.  It really only works if
 1117          the primops involved are OkForSpeculation, and, since
 1118          they have side effects readIntOfAddr and touch are not.
 1119          Maybe we'll get back to this later .  -}
 1120 
 1121 Consider
 1122    f (case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
 1123       case touch# fp s# of { _ ->
 1124       I# n# } } )
 1125 This happened in a tight loop generated by stream fusion that
 1126 Roman encountered.  We'd like to treat this just like the let
 1127 case, because the primops concerned are ok-for-speculation.
 1128 That is, we'd like to behave as if it had been
 1129    case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) ->
 1130    case touch# fp s# of { _ ->
 1131    f (I# n# } } )
 1132 
 1133 Note [Lookup in-scope]
 1134 ~~~~~~~~~~~~~~~~~~~~~~
 1135 Consider this example
 1136         foo :: Int -> Maybe Int -> Int
 1137         foo 0 (Just n) = n
 1138         foo m (Just n) = foo (m-n) (Just n)
 1139 
 1140 SpecConstr sees this fragment:
 1141 
 1142         case w_smT of wild_Xf [Just A] {
 1143           Data.Maybe.Nothing -> lvl_smf;
 1144           Data.Maybe.Just n_acT [Just S(L)] ->
 1145             case n_acT of wild1_ams [Just A] { GHC.Base.I# y_amr [Just L] ->
 1146               $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf
 1147             }};
 1148 
 1149 and correctly generates the rule
 1150 
 1151         RULES: "SC:$wfoo1" [0] __forall {y_amr [Just L] :: GHC.Prim.Int#
 1152                                           sc_snn :: GHC.Prim.Int#}
 1153           $wfoo_smW sc_snn (Data.Maybe.Just @ GHC.Base.Int (GHC.Base.I# y_amr))
 1154           = $s$wfoo_sno y_amr sc_snn ;]
 1155 
 1156 BUT we must ensure that this rule matches in the original function!
 1157 Note that the call to $wfoo is
 1158             $wfoo_smW (GHC.Prim.-# ds_Xmb y_amr) wild_Xf
 1159 
 1160 During matching we expand wild_Xf to (Just n_acT).  But then we must also
 1161 expand n_acT to (I# y_amr).  And we can only do that if we look up n_acT
 1162 in the in-scope set, because in wild_Xf's unfolding it won't have an unfolding
 1163 at all.
 1164 
 1165 That is why the 'lookupRnInScope' call in the (Var v2) case of 'match'
 1166 is so important.
 1167 
 1168 
 1169 ************************************************************************
 1170 *                                                                      *
 1171                    Rule-check the program
 1172 *                                                                      *
 1173 ************************************************************************
 1174 
 1175    We want to know what sites have rules that could have fired but didn't.
 1176    This pass runs over the tree (without changing it) and reports such.
 1177 -}
 1178 
 1179 -- | Report partial matches for rules beginning with the specified
 1180 -- string for the purposes of error reporting
 1181 ruleCheckProgram :: RuleOpts                    -- ^ Rule options
 1182                  -> CompilerPhase               -- ^ Rule activation test
 1183                  -> String                      -- ^ Rule pattern
 1184                  -> (Id -> [CoreRule])          -- ^ Rules for an Id
 1185                  -> CoreProgram                 -- ^ Bindings to check in
 1186                  -> SDoc                        -- ^ Resulting check message
 1187 ruleCheckProgram ropts phase rule_pat rules binds
 1188   | isEmptyBag results
 1189   = text "Rule check results: no rule application sites"
 1190   | otherwise
 1191   = vcat [text "Rule check results:",
 1192           line,
 1193           vcat [ p $$ line | p <- bagToList results ]
 1194          ]
 1195   where
 1196     env = RuleCheckEnv { rc_is_active = isActive phase
 1197                        , rc_id_unf    = idUnfolding     -- Not quite right
 1198                                                         -- Should use activeUnfolding
 1199                        , rc_pattern   = rule_pat
 1200                        , rc_rules     = rules
 1201                        , rc_ropts     = ropts
 1202                        }
 1203     results = unionManyBags (map (ruleCheckBind env) binds)
 1204     line = text (replicate 20 '-')
 1205 
 1206 data RuleCheckEnv = RuleCheckEnv {
 1207     rc_is_active :: Activation -> Bool,
 1208     rc_id_unf  :: IdUnfoldingFun,
 1209     rc_pattern :: String,
 1210     rc_rules :: Id -> [CoreRule],
 1211     rc_ropts :: RuleOpts
 1212 }
 1213 
 1214 ruleCheckBind :: RuleCheckEnv -> CoreBind -> Bag SDoc
 1215    -- The Bag returned has one SDoc for each call site found
 1216 ruleCheckBind env (NonRec _ r) = ruleCheck env r
 1217 ruleCheckBind env (Rec prs)    = unionManyBags [ruleCheck env r | (_,r) <- prs]
 1218 
 1219 ruleCheck :: RuleCheckEnv -> CoreExpr -> Bag SDoc
 1220 ruleCheck _   (Var _)       = emptyBag
 1221 ruleCheck _   (Lit _)       = emptyBag
 1222 ruleCheck _   (Type _)      = emptyBag
 1223 ruleCheck _   (Coercion _)  = emptyBag
 1224 ruleCheck env (App f a)     = ruleCheckApp env (App f a) []
 1225 ruleCheck env (Tick _ e)  = ruleCheck env e
 1226 ruleCheck env (Cast e _)    = ruleCheck env e
 1227 ruleCheck env (Let bd e)    = ruleCheckBind env bd `unionBags` ruleCheck env e
 1228 ruleCheck env (Lam _ e)     = ruleCheck env e
 1229 ruleCheck env (Case e _ _ as) = ruleCheck env e `unionBags`
 1230                                 unionManyBags [ruleCheck env r | Alt _ _ r <- as]
 1231 
 1232 ruleCheckApp :: RuleCheckEnv -> Expr CoreBndr -> [Arg CoreBndr] -> Bag SDoc
 1233 ruleCheckApp env (App f a) as = ruleCheck env a `unionBags` ruleCheckApp env f (a:as)
 1234 ruleCheckApp env (Var f) as   = ruleCheckFun env f as
 1235 ruleCheckApp env other _      = ruleCheck env other
 1236 
 1237 ruleCheckFun :: RuleCheckEnv -> Id -> [CoreExpr] -> Bag SDoc
 1238 -- Produce a report for all rules matching the predicate
 1239 -- saying why it doesn't match the specified application
 1240 
 1241 ruleCheckFun env fn args
 1242   | null name_match_rules = emptyBag
 1243   | otherwise             = unitBag (ruleAppCheck_help env fn args name_match_rules)
 1244   where
 1245     name_match_rules = filter match (rc_rules env fn)
 1246     match rule = (rc_pattern env) `isPrefixOf` unpackFS (ruleName rule)
 1247 
 1248 ruleAppCheck_help :: RuleCheckEnv -> Id -> [CoreExpr] -> [CoreRule] -> SDoc
 1249 ruleAppCheck_help env fn args rules
 1250   =     -- The rules match the pattern, so we want to print something
 1251     vcat [text "Expression:" <+> ppr (mkApps (Var fn) args),
 1252           vcat (map check_rule rules)]
 1253   where
 1254     n_args = length args
 1255     i_args = args `zip` [1::Int ..]
 1256     rough_args = map roughTopName args
 1257 
 1258     check_rule rule = rule_herald rule <> colon <+> rule_info (rc_ropts env) rule
 1259 
 1260     rule_herald (BuiltinRule { ru_name = name })
 1261         = text "Builtin rule" <+> doubleQuotes (ftext name)
 1262     rule_herald (Rule { ru_name = name })
 1263         = text "Rule" <+> doubleQuotes (ftext name)
 1264 
 1265     rule_info opts rule
 1266         | Just _ <- matchRule opts (emptyInScopeSet, rc_id_unf env)
 1267                               noBlackList fn args rough_args rule
 1268         = text "matches (which is very peculiar!)"
 1269 
 1270     rule_info _ (BuiltinRule {}) = text "does not match"
 1271 
 1272     rule_info _ (Rule { ru_act = act,
 1273                         ru_bndrs = rule_bndrs, ru_args = rule_args})
 1274         | not (rc_is_active env act)  = text "active only in later phase"
 1275         | n_args < n_rule_args        = text "too few arguments"
 1276         | n_mismatches == n_rule_args = text "no arguments match"
 1277         | n_mismatches == 0           = text "all arguments match (considered individually), but rule as a whole does not"
 1278         | otherwise                   = text "arguments" <+> ppr mismatches <+> text "do not match (1-indexing)"
 1279         where
 1280           n_rule_args  = length rule_args
 1281           n_mismatches = length mismatches
 1282           mismatches   = [i | (rule_arg, (arg,i)) <- rule_args `zip` i_args,
 1283                               not (isJust (match_fn rule_arg arg))]
 1284 
 1285           lhs_fvs = exprsFreeVars rule_args     -- Includes template tyvars
 1286           match_fn rule_arg arg = match renv emptyRuleSubst rule_arg arg
 1287                 where
 1288                   in_scope = mkInScopeSet (lhs_fvs `unionVarSet` exprFreeVars arg)
 1289                   renv = RV { rv_lcl   = mkRnEnv2 in_scope
 1290                             , rv_tmpls = mkVarSet rule_bndrs
 1291                             , rv_fltR  = mkEmptySubst in_scope
 1292                             , rv_unf   = rc_id_unf env }