blob: 26f716a9da53cbc6d14329f04e2b004267de6358 [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
/--
A custom, approximated, and quick `contradiction` tactic.
It only finds contradictions of the form `(h₁ : p)` and `(h₂ : ¬ p)` where
`p`s are structurally equal. The procedure is not quadratic like `contradiction`.
We use it to improve the performance of `proveSubgoalLoop` at `mkSplitterProof`.
We will eventually have to write more efficient proof automation for this module.
The new proof automation should exploit the structure of the generated goals and avoid general purpose tactics
such as `contradiction`.
-/
private def _root_.Lean.MVarId.contradictionQuick (mvarId : MVarId) : MetaM Bool := do
mvarId.withContext do
let mut posMap : Std.HashMap Expr FVarId := {}
let mut negMap : Std.HashMap Expr FVarId := {}
for localDecl in (← getLCtx) do
unless localDecl.isImplementationDetail do
if let some p ← matchNot? localDecl.type then
if let some pFVarId := posMap[p]? then
mvarId.assign (← mkAbsurd (← mvarId.getType) (mkFVar pFVarId) localDecl.toExpr)
return true
negMap := negMap.insert p localDecl.fvarId
if (← isProp localDecl.type) then
if let some nFVarId := negMap[localDecl.type]? then
mvarId.assign (← mkAbsurd (← mvarId.getType) localDecl.toExpr (mkFVar nFVarId))
return true
posMap := posMap.insert localDecl.type localDecl.fvarId
pure ()
return false
inductive InjectionAnyResult where
| solved
| failed
/-- `fvarId` refers to the local declaration selected for the application of the `injection` tactic. -/
| subgoal (fvarId : FVarId) (mvarId : MVarId)
def injectionAnyCandidate? (type : Expr) : MetaM (Option (Expr × Expr)) := do
if let some (_, lhs, rhs) ← matchEq? type then
return some (lhs, rhs)
else if let some (α, lhs, β, rhs) ← matchHEq? type then
if (← isDefEq α β) then
return some (lhs, rhs)
return none
/--
Try applying `injection` to a local declaration that is not in `forbidden`.
We use `forbidden` because the `injection` tactic might fail to clear the variable if there are forward dependencies.
See `proveSubgoalLoop` for additional details.
-/
def injectionAny (mvarId : MVarId) (forbidden : FVarIdSet := {}) : MetaM InjectionAnyResult := do
mvarId.withContext do
for localDecl in (← getLCtx) do
unless forbidden.contains localDecl.fvarId do
if let some (lhs, rhs) ← injectionAnyCandidate? localDecl.type then
unless (← isDefEq lhs rhs) do
let lhs ← whnf lhs
let rhs ← whnf rhs
unless lhs.isRawNatLit && rhs.isRawNatLit do
try
match (← injection mvarId localDecl.fvarId) with
| InjectionResult.solved => return InjectionAnyResult.solved
| InjectionResult.subgoal mvarId .. => return InjectionAnyResult.subgoal localDecl.fvarId mvarId
catch ex =>
trace[Meta.Match.matchEqs] "injectionAnyFailed at {localDecl.userName}, error\n{ex.toMessageData}"
pure ()
return InjectionAnyResult.failed
/--
Solves the overlap assumptions expected by the alternative of a splitter
-/
public partial def solveOverlap (mvarId : MVarId) : MetaM Unit := do
trace[Meta.Match.matchEqs] "solveOverlap {mkMVar mvarId}, {repr (← mvarId.getDecl).kind}\n{indentD mvarId}"
let (_, mvarId) ← mvarId.intros
loop mvarId {}
where
/-
`forbidden` tracks variables that we have already applied `injection`.
Recall that the `injection` tactic may not be able to eliminate them when
they have forward dependencies.
-/
loop (mvarId : MVarId) (forbidden : FVarIdSet) : MetaM Unit := do
trace[Meta.Match.matchEqs] "proveSubgoalLoop\n{mvarId}"
if (← mvarId.contradictionQuick) then
return ()
match (← injectionAny mvarId forbidden) with
| .solved => return ()
| .failed =>
let mvarId' ← substVars mvarId
if mvarId' == mvarId then
if (← mvarId.contradictionCore {}) then
return ()
throwError "failed to solve overlap assumption, unsolved subgoal{indentD mvarId}"
else
loop mvarId' forbidden
| .subgoal fvarId mvarId => loop mvarId (forbidden.insert fvarId)