blob: 8beacfc459998e040689ba7bb59463c2c8a9379d [file]
/-
Copyright (c) 2021 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.Basic
import Lean.Meta.Tactic.Contradiction
namespace Lean.Meta.Match.SimpH
/--
State for the equational theorem hypothesis simplifier.
Recall that each equation contains additional hypotheses to ensure the associated case does not taken by previous cases.
We have one hypothesis for each previous case.
Each hypothesis is of the form `forall xs, eqs → False`
We use tactics to minimize code duplication.
-/
structure State where
mvarId : MVarId -- Goal representing the hypothesis
xs : List FVarId -- Pattern variables for a previous case
eqs : List FVarId -- Equations to be processed
eqsNew : List FVarId := [] -- Simplified (already processed) equations
abbrev M := StateRefT State MetaM
/--
Apply the given substitution to `fvarIds`.
This is an auxiliary method for `substRHS`.
-/
def applySubst (s : FVarSubst) (fvarIds : List FVarId) : List FVarId :=
fvarIds.filterMap fun fvarId => match s.apply (mkFVar fvarId) with
| Expr.fvar fvarId .. => some fvarId
| _ => none
/--
Given an equation of the form `lhs = rhs` where `rhs` is variable in `xs`,
replace it everywhere with `lhs`.
-/
def substRHS (eq : FVarId) (rhs : FVarId) : M Unit := do
assert! (← get).xs.contains rhs
let (subst, mvarId) ← substCore (← get).mvarId eq (symm := true)
modify fun s => { s with
mvarId,
xs := applySubst subst (s.xs.erase rhs)
eqs := applySubst subst s.eqs
eqsNew := applySubst subst s.eqsNew
}
def isDone : M Bool :=
return (← get).eqs.isEmpty
/-- Customized `contradiction` tactic for `simpH?` -/
def contradiction (mvarId : MVarId) : MetaM Bool :=
mvarId.contradictionCore { genDiseq := false, emptyType := false }
/--
Auxiliary tactic that tries to replace as many variables as possible and then apply `contradiction`.
We use it to discard redundant hypotheses.
-/
partial def trySubstVarsAndContradiction (mvarId : MVarId) (forbidden : FVarIdSet := {}) : MetaM Bool :=
commitWhen do
let mvarId ← substVars mvarId
match (← injections mvarId (forbidden := forbidden)) with
| .solved => return true -- closed goal
| .subgoal mvarId' _ forbidden =>
if mvarId' == mvarId then
contradiction mvarId
else
trySubstVarsAndContradiction mvarId' forbidden
def processNextEq : M Bool := do
let s ← get
s.mvarId.withContext do
if let eq :: eqs := s.eqs then
modify fun s => { s with eqs }
let eqType ← inferType (mkFVar eq)
-- See `substRHS`. Recall that if `rhs` is a variable then if must be in `s.xs`
if let some (_, lhs, rhs) ← matchEq? eqType then
if (← isDefEq lhs rhs) then
let mvarId ← s.mvarId.clear eq
modify fun s => { s with mvarId }
return true
if rhs.isFVar && s.xs.contains rhs.fvarId! then
substRHS eq rhs.fvarId!
return true
if let some _ ← matchHEq? eqType then
-- Try to convert `HEq` into `Eq`
let (eqNew, mvarId) ← heqToEq s.mvarId eq (tryToClear := true)
if mvarId != s.mvarId then
modify fun s => { s with mvarId, eqs := eqNew :: s.eqs }
return true
-- If it is not possible, we try to show the hypothesis is redundant by substituting even
-- variables that are not at `s.xs`, and then use contradiction.
else
if (← trySubstVarsAndContradiction s.mvarId) then
return false
try
-- Try to simplify equation using `injection` tactic.
match (← injection s.mvarId eq) with
| InjectionResult.solved => return false
| InjectionResult.subgoal mvarId eqNews .. =>
modify fun s => { s with mvarId, eqs := eqNews.toList ++ s.eqs }
catch _ =>
modify fun s => { s with eqsNew := eq :: s.eqsNew }
return true
partial def go : M Bool := do
if (← isDone) then
return true
else if (← processNextEq) then
go
else
return false
end SimpH
/--
Like `simpH?`, but works directly on a goal corresponding to the unsimplified equational theorem
hypothesis, and either closes it or returns a residual goal whose type is the simplified equational
theorem hypothesis.
-/
public partial def simpH (mvarId : MVarId) (numEqs : Nat) : MetaM (Option MVarId) := withDefault do
let numVars ← forallTelescope (← mvarId.getType) fun ys _ => pure (ys.size - numEqs)
let mvarId ← mvarId.tryClearMany (← getLCtx).getFVarIds
let (xs, mvarId) ← mvarId.introN numVars
let (eqs, mvarId) ← mvarId.introN numEqs
let (r, s) ← SimpH.go |>.run { mvarId, xs := xs.toList, eqs := eqs.toList }
if r then
s.mvarId.withContext do
let eqs := s.eqsNew.reverse.toArray
let mvarId' := s.mvarId
let mvarId' := (← mvarId'.revert eqs).2
/- We only include variables in `xs` if there is a dependency. -/
let r ← mvarId'.getType
mvarId'.withContext do
let xs ← s.xs.toArray.reverse.filterM (dependsOn r ·)
let mvarId' := (← mvarId'.revert xs).2
return (some mvarId')
else
return none
/--
Auxiliary method for simplifying equational theorem hypotheses.
Recall that each equation contains additional hypotheses to ensure the associated case was not taken by previous cases.
We have one hypothesis for each previous case.
-/
public def simpH? (h : Expr) (numEqs : Nat) : MetaM (Option Expr) := do
let prf ← mkFreshExprSyntheticOpaqueMVar h
match (← simpH prf.mvarId! numEqs) with
| none => return none
| some mvarId' =>
return some (← mvarId'.getType)