blob: 6eb1bd574770be48d16b06b0e3048e9c0d3a6f48 [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.Tactic.Assert
public section
namespace Lean.Meta
def substCore (mvarId : MVarId) (hFVarId : FVarId) (symm := false) (fvarSubst : FVarSubst := {}) (clearH := true) (tryToSkip := false) : MetaM (FVarSubst × MVarId) :=
mvarId.withContext do
let tag ← mvarId.getTag
mvarId.checkNotAssigned `subst
let hFVarIdOriginal := hFVarId
let hLocalDecl ← hFVarId.getDecl
match (← matchEq? hLocalDecl.type) with
| none => throwTacticEx `subst mvarId "argument must be an equality proof"
| some (_, lhs, rhs) => do
let a ← instantiateMVars <| if symm then rhs else lhs
let b ← instantiateMVars <| if symm then lhs else rhs
match a with
| Expr.fvar aFVarId => do
let aFVarIdOriginal := aFVarId
trace[Meta.Tactic.subst] "substituting {a} (id: {aFVarId.name}) with {b}"
if (← exprDependsOn b aFVarId) then
throwTacticEx `subst mvarId m!"'{a}' occurs at{indentExpr b}"
let (vars, mvarId) ← mvarId.revert #[aFVarId, hFVarId] true
trace[Meta.Tactic.subst] "after revert {MessageData.ofGoal mvarId}"
let (twoVars, mvarId) ← mvarId.introNP 2
trace[Meta.Tactic.subst] "after intro2 {MessageData.ofGoal mvarId}"
trace[Meta.Tactic.subst] "reverted variables {vars.map (·.name)}"
let aFVarId := twoVars[0]!
let a := mkFVar aFVarId
let hFVarId := twoVars[1]!
let h := mkFVar hFVarId
/- Set skip to true if there is no local variable nor the target depend on the equality -/
let skip ← if !tryToSkip || vars.size != 2 then
pure false
else
let mvarType ← mvarId.getType
if (← exprDependsOn mvarType aFVarId) then pure false
else if (← exprDependsOn mvarType hFVarId) then pure false
else pure true
if skip then
if clearH then
let mvarId ← mvarId.clear hFVarId
let mvarId ← mvarId.clear aFVarId
pure (fvarSubst, mvarId)
else
pure (fvarSubst, mvarId)
else
mvarId.withContext do
let mvarDecl ← mvarId.getDecl
let type := mvarDecl.type
let hLocalDecl ← hFVarId.getDecl
match (← matchEq? hLocalDecl.type) with
| none => unreachable!
| some (_, lhs, rhs) => do
let b ← instantiateMVars <| if symm then lhs else rhs
let depElim ← exprDependsOn mvarDecl.type hFVarId
let cont (motive : Expr) (newType : Expr) : MetaM (FVarSubst × MVarId) := do
let major ← if symm then pure h else mkEqSymm h
let newMVar ← mkFreshExprSyntheticOpaqueMVar newType tag
let minor := newMVar
let newVal ← if depElim then mkEqRec motive minor major else mkEqNDRec motive minor major
mvarId.assign newVal
let mvarId := newMVar.mvarId!
let mvarId ← if clearH then
let mvarId ← mvarId.clear hFVarId
mvarId.clear aFVarId
else
pure mvarId
let (newFVars, mvarId) ← mvarId.introNP (vars.size - 2)
trace[Meta.Tactic.subst] "after intro rest {vars.size - 2} {MessageData.ofGoal mvarId}"
let fvarSubst ← newFVars.size.foldM (init := fvarSubst) fun i _ (fvarSubst : FVarSubst) =>
let var := vars[i+2]!
let newFVar := newFVars[i]
pure $ fvarSubst.insert var (mkFVar newFVar)
let fvarSubst := fvarSubst.insert aFVarIdOriginal (if clearH then b else mkFVar aFVarId)
let fvarSubst := fvarSubst.insert hFVarIdOriginal (mkFVar hFVarId)
pure (fvarSubst, mvarId)
if depElim then do
let newType := type.replaceFVar a b
let reflB ← mkEqRefl b
let newType := newType.replaceFVar h reflB
if symm then
let motive ← mkLambdaFVars #[a, h] type
cont motive newType
else
/- `type` depends on (h : a = b). So, we use the following trick to avoid a type incorrect motive.
1- Create a new local (hAux : b = a)
2- Create newType := type [hAux.symm / h]
`newType` is type correct because `h` and `hAux.symm` are definitionally equal by proof irrelevance.
3- Create motive by abstracting `a` and `hAux` in `newType`. -/
let hAuxType ← mkEq b a
let motive ← withLocalDeclD `_h hAuxType fun hAux => do
let hAuxSymm ← mkEqSymm hAux
/- replace h in type with hAuxSymm -/
let newType := type.replaceFVar h hAuxSymm
mkLambdaFVars #[a, hAux] newType
cont motive newType
else
let motive ← mkLambdaFVars #[a] type
let newType := type.replaceFVar a b
cont motive newType
| _ =>
let eqMsg := if symm then "(t = x)" else "(x = t)"
throwTacticEx `subst mvarId
m!"invalid equality proof, it is not of the form {eqMsg}{indentExpr hLocalDecl.type}\nafter WHNF, variable expected, but obtained{indentExpr a}"
/--
Given `h : @HEq α a α b` in the given goal, produce a new goal where `h : @Eq α a b`.
If `h` is not of the give form, then just return `(h, mvarId)`
-/
def heqToEq (mvarId : MVarId) (fvarId : FVarId) (tryToClear : Bool := true) : MetaM (FVarId × MVarId) :=
mvarId.withContext do
let decl ← fvarId.getDecl
let type ← whnf decl.type
match type.heq? with
| none => pure (fvarId, mvarId)
| some (α, a, β, b) =>
if (← isDefEq α β) then
let pr ← mkEqOfHEq (mkFVar fvarId)
let eq ← mkEq a b
let mut mvarId ← mvarId.assert decl.userName eq pr
if tryToClear then
mvarId ← mvarId.tryClear fvarId
let (fvarId, mvarId') ← mvarId.intro1P
return (fvarId, mvarId')
else
return (fvarId, mvarId)
/--
Given `x`, try to find an equation of the form `heq : x = rhs` or `heq : lhs = x`,
and runs `substCore` on it. Throws an exception if no such equation is found.
-/
partial def substVar (mvarId : MVarId) (x : FVarId) : MetaM MVarId :=
mvarId.withContext do
let localDecl ← x.getDecl
if localDecl.isLet then
throwTacticEx `subst mvarId m!"variable '{mkFVar x}' is a let-declaration"
let lctx ← getLCtx
let some (fvarId, symm) ← lctx.findDeclM? fun localDecl => do
if localDecl.isImplementationDetail then
return none
else
match (← matchEq? localDecl.type) with
| some (_, lhs, rhs) =>
let lhs ← instantiateMVars lhs
let rhs ← instantiateMVars rhs
if rhs.isFVar && rhs.fvarId! == x then
if !(← exprDependsOn lhs x) then
return some (localDecl.fvarId, true)
if lhs.isFVar && lhs.fvarId! == x then
if !(← exprDependsOn rhs x) then
return some (localDecl.fvarId, false)
return none
| _ => return none
| throwTacticEx `subst mvarId m!"did not find equation for eliminating '{mkFVar x}'"
return (← substCore mvarId fvarId (symm := symm) (tryToSkip := true)).2
/--
If `hFVarId` is an `Eq` (or a `HEq` that can be turned into an `Eq`) with a free variable
on the LHS or RHS, eliminates the variable by substitution.
-/
def substEq (mvarId : MVarId) (hFVarId : FVarId)
(fvarSubst : FVarSubst := {}) : MetaM (FVarSubst × MVarId) := do
let (hFVarId, mvarId) ← heqToEq mvarId hFVarId
mvarId.withContext do
let localDecl ← hFVarId.getDecl
let error {α} _ : MetaM α := throwTacticEx `subst mvarId
m!"invalid equality proof, it is not of the form (x = t) or (t = x){indentExpr localDecl.type}"
let some (_, lhs, rhs) ← matchEq? localDecl.type | error ()
let substReduced (newType : Expr) (symm : Bool) : MetaM (FVarSubst × MVarId) := do
let mvarId ← mvarId.assert localDecl.userName newType (mkFVar hFVarId)
let (hFVarId', mvarId) ← mvarId.intro1P
let mvarId ← mvarId.clear hFVarId
substCore mvarId hFVarId' (symm := symm) (tryToSkip := true) (fvarSubst := fvarSubst)
let rhs' ← whnf rhs
if rhs'.isFVar then
if rhs != rhs' then
substReduced (← mkEq lhs rhs') true
else
substCore mvarId hFVarId (symm := true) (tryToSkip := true) (fvarSubst := fvarSubst)
else
let lhs' ← whnf lhs
if lhs'.isFVar then
if lhs != lhs' then
substReduced (← mkEq lhs' rhs) false
else
substCore mvarId hFVarId (symm := false) (tryToSkip := true) (fvarSubst := fvarSubst)
else error ()
partial def subst (mvarId : MVarId) (h : FVarId) : MetaM MVarId :=
mvarId.withContext do
let type ← h.getType
match (← matchEq? type) with
| some _ => return (← substEq mvarId h).2
| none => match (← matchHEq? type) with
| some _ =>
let (h', mvarId') ← heqToEq mvarId h
if mvarId == mvarId' then
substVar mvarId h
else
subst mvarId' h'
| none => substVar mvarId h
/--
Given a goal `(a = b) → goal[b]`, creates a new goal `goal[a]`, clearing `b`.
This is essentially `intro h; subst h`, but in the case that `b` is a free variable and has no
forward dependencies implements this without introducing the equality, which can make a difference
in terms of performance.
If `substLHS = true`, assume `(a = b) → goal[a]` and create goal `goal[b]`, clearing `a`.
Also handles heterogeneous equalities in cases where `eq_of_heq` would apply.
-/
def introSubstEq (mvarId : MVarId) (substLHS := false) : MetaM (FVarSubst × MVarId) := do
mvarId.checkNotAssigned `introSubstEq
try commitIfNoEx do mvarId.withContext do
let goalType ← mvarId.getType'
let some (heq, body) := goalType.arrow? | throwError "not an arrow type"
let (α, a, b, ndrec) ←
match_expr heq with
| Eq α a b =>
if substLHS then
pure (α, b, a, ``Eq.ndrec_symm)
else
pure (α, a, b, ``Eq.ndrec)
| HEq α a β b =>
unless (← isDefEq α β) do throwError "hetereogenenous equality isn't homogeneous"
if substLHS then
pure (α, b, a, ``HEq.homo_ndrec_symm)
else
pure (α, a, b, ``HEq.homo_ndrec)
| _ => throwError "not an equality"
unless b.isFVar do throwError "equality rhs not a free variable"
let (reverted, mvarId) ← mvarId.revert #[b.fvarId!]
unless reverted.size = 1 do throwError "variable {b} has forward dependencies"
let motive ← mkLambdaFVars #[b] body
let goal := motive.beta #[a]
let e ← mkFreshExprSyntheticOpaqueMVar goal (tag := (← mvarId.getTag))
let u1 ← getLevel goal
let u2 ← getLevel α
mvarId.assign <| mkApp4 (mkConst ndrec [u1, u2]) α a motive e
let subst : FVarSubst := FVarSubst.empty.insert b.fvarId! a
return (subst, e.mvarId!)
catch e =>
trace[Meta.Tactic.subst] "introSubstEq falling back to intro\n{e.toMessageData}\n{mvarId}"
if (← mvarId.isAssigned) then throwError "introSubstEq: now assigned?"
let (h, mvarId) ← mvarId.intro1
let (subst, mvarId) ← substEq mvarId h
return (subst, mvarId)
/--
Given `x`, try to find an equation of the form `heq : x = rhs` or `heq : lhs = x`,
and runs `substCore` on it. Returns `none` if no such equation is found, or if `substCore` fails.
-/
def substVar? (mvarId : MVarId) (hFVarId : FVarId) : MetaM (Option MVarId) :=
observing? (substVar mvarId hFVarId)
def subst? (mvarId : MVarId) (hFVarId : FVarId) : MetaM (Option MVarId) :=
observing? (subst mvarId hFVarId)
def substCore? (mvarId : MVarId) (hFVarId : FVarId) (symm := false) (fvarSubst : FVarSubst := {}) (clearH := true) (tryToSkip := false) : MetaM (Option (FVarSubst × MVarId)) :=
observing? (substCore mvarId hFVarId symm fvarSubst clearH tryToSkip)
def trySubstVar (mvarId : MVarId) (hFVarId : FVarId) : MetaM MVarId := do
return (← substVar? mvarId hFVarId).getD mvarId
def trySubst (mvarId : MVarId) (hFVarId : FVarId) : MetaM MVarId := do
return (← subst? mvarId hFVarId).getD mvarId
def substSomeVar? (mvarId : MVarId) : MetaM (Option MVarId) := mvarId.withContext do
for localDecl in (← getLCtx) do
if let some mvarId ← subst? mvarId localDecl.fvarId then
return some mvarId
return none
partial def substVars (mvarId : MVarId) : MetaM MVarId := do
if let some mvarId ← substSomeVar? mvarId then
substVars mvarId
else
return mvarId
builtin_initialize registerTraceClass `Meta.Tactic.subst
end Meta
end Lean