blob: 01f7ac8cb9bb64bf9842646cd5dff21bef0685d1 [file]
/-
Copyright (c) 2020 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
module
prelude
public import Lean.Meta.AppBuilder
public import Lean.Meta.MatchUtil
public import Lean.Meta.KAbstract
public import Lean.Meta.Tactic.Apply
public import Lean.Meta.BinderNameHint
public section
namespace Lean.Meta
structure RewriteResult where
eNew : Expr
eqProof : Expr
mvarIds : List MVarId -- new goals
/--
Rewrite `e` using `heq` in the context of `mvarId`.
Returns the result of the rewrite, the metavariable `mvarId` is not assigned.
-/
def _root_.Lean.MVarId.rewrite (mvarId : MVarId) (e : Expr) (heq : Expr)
(symm : Bool := false) (config := { : Rewrite.Config }) : MetaM RewriteResult :=
mvarId.withContext do
mvarId.checkNotAssigned `rewrite
let heqIn := heq
let heqType ← instantiateMVars (← inferType heq)
let (newMVars, binderInfos, heqType) ← forallMetaTelescopeReducing heqType
let heq := mkAppN heq newMVars
let cont (heq heqType : Expr) : MetaM RewriteResult := do
match (← matchEq? heqType) with
| none =>
let valueDescr := if (← Meta.isProp heqType) then "a proof of" else "a value of type"
throwError m!"Invalid rewrite argument: Expected an equality or iff proof \
or definition name, but{inlineExpr heq}is {valueDescr}{indentExpr heqType}"
| some (α, lhs, rhs) =>
let cont (heq heqType lhs rhs : Expr) : MetaM RewriteResult := do
if lhs.getAppFn.isMVar then
throwError "Invalid rewrite argument: The pattern to be substituted is a metavariable (`{lhs}`) in this equality{indentExpr heqType}"
let e ← instantiateMVars e
let eAbst ← withConfig (fun oldConfig => { config, oldConfig with }) <| kabstract e lhs config.occs
unless eAbst.hasLooseBVars do
let (tgt, pat) ← addPPExplicitToExposeDiff e lhs
throwTacticEx `rewrite mvarId m!"Did not find an occurrence of the pattern{indentExpr pat}\nin the target expression{indentExpr tgt}"
-- construct rewrite proof
let eNew := eAbst.instantiate1 rhs
let eNew ← instantiateMVars eNew
let eNew ← if rhs.hasBinderNameHint then eNew.resolveBinderNameHint else pure eNew
let eType ← inferType e
let motive := Lean.mkLambda `_a BinderInfo.default α eAbst
try
check motive
catch ex =>
throwTacticEx `rewrite mvarId m!"\
motive is not type correct:{indentD motive}\nError: {ex.toMessageData}\
\n\n\
Explanation: The rewrite tactic rewrites an expression 'e' using an equality 'a = b' by the following process. \
First, it looks for all 'a' in 'e'. Second, it tries to abstract these occurrences of 'a' to create a function 'm := fun _a => ...', called the *motive*, \
with the property that 'm a' is definitionally equal to 'e'. \
Third, we observe that '{.ofConstName ``congrArg}' implies that 'm a = m b', which can be used with lemmas such as '{.ofConstName ``Eq.mpr}' to change the goal. \
However, if 'e' depends on specific properties of 'a', then the motive 'm' might not typecheck.\
\n\n\
Possible solutions: use rewrite's 'occs' configuration option to limit which occurrences are rewritten, \
or use 'simp' or 'conv' mode, which have strategies for certain kinds of dependencies \
(these tactics can handle proofs and '{.ofConstName ``Decidable}' instances whose types depend on the rewritten term, \
and 'simp' can apply user-defined '@[congr]' theorems as well)."
unless (← withLocalDeclD `_a α fun a => do isDefEq (← inferType (eAbst.instantiate1 a)) eType) do
-- NB: using motive.arrow? would disallow motives where the dependency
-- can be reduced away
throwTacticEx `rewrite mvarId <| m!"Motive is dependent:{indentD motive}"
++ MessageData.note m!"The rewrite tactic cannot substitute terms on which the type of the target expression depends. \
The type of the expression{indentExpr e}\ndepends on the value{indentExpr lhs}"
let u1 ← getLevel α
let u2 ← getLevel eType
let eqPrf := mkApp6 (.const ``congrArg [u1, u2]) α eType lhs rhs motive heq
postprocessAppMVars `rewrite mvarId newMVars binderInfos
(synthAssignedInstances := !tactic.skipAssignedInstances.get (← getOptions))
let newMVarIds ← newMVars.map Expr.mvarId! |>.filterM fun mvarId => not <$> mvarId.isAssigned
let otherMVarIds ← getMVarsNoDelayed heqIn
let otherMVarIds := otherMVarIds.filter (!newMVarIds.contains ·)
let newMVarIds := newMVarIds ++ otherMVarIds
pure { eNew := eNew, eqProof := eqPrf, mvarIds := newMVarIds.toList }
match symm with
| false => cont heq heqType lhs rhs
| true => do
let heq ← mkEqSymm heq
let heqType ← mkEq rhs lhs
cont heq heqType rhs lhs
match heqType.iff? with
| some (lhs, rhs) =>
let heqType ← mkEq lhs rhs
let heq := mkApp3 (mkConst `propext) lhs rhs heq
cont heq heqType
| none =>
cont heq heqType
end Lean.Meta