blob: bd20c779acfdaec63fd9fb6278660fa9afb174cf [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
-/
prelude
import Lean.Meta.Match.MatcherApp.Basic
import Lean.Meta.Tactic.Simp.Main
import Lean.Meta.Tactic.SplitIf
import Lean.Meta.Tactic.Apply
import Lean.Meta.Tactic.Generalize
namespace Lean.Meta
namespace Split
def getSimpMatchContext : MetaM Simp.Context :=
return {
simpTheorems := {}
congrTheorems := (← getSimpCongrTheorems)
config := { Simp.neutralConfig with dsimp := false }
}
def simpMatch (e : Expr) : MetaM Simp.Result := do
let discharge? ← SplitIf.mkDischarge?
(·.1) <$> Simp.main e (← getSimpMatchContext) (methods := { pre, discharge? })
where
pre (e : Expr) : SimpM Simp.Step := do
unless (← isMatcherApp e) do
return Simp.Step.continue
let matcherDeclName := e.getAppFn.constName!
-- First try to reduce matcher
match (← reduceRecMatcher? e) with
| some e' => return Simp.Step.done { expr := e' }
| none => Simp.simpMatchCore matcherDeclName e
def simpMatchTarget (mvarId : MVarId) : MetaM MVarId := mvarId.withContext do
let target ← instantiateMVars (← mvarId.getType)
let r ← simpMatch target
applySimpResultToTarget mvarId target r
private def simpMatchCore (matchDeclName : Name) (matchEqDeclName : Name) (e : Expr) : MetaM Simp.Result := do
let discharge? ← SplitIf.mkDischarge?
(·.1) <$> Simp.main e (← getSimpMatchContext) (methods := { pre, discharge? })
where
pre (e : Expr) : SimpM Simp.Step := do
if e.isAppOf matchDeclName then
-- First try to reduce matcher
match (← reduceRecMatcher? e) with
| some e' => return .done { expr := e' }
| none =>
-- Try lemma
let simpTheorem := {
origin := .decl matchEqDeclName
proof := mkConst matchEqDeclName
rfl := (← isRflTheorem matchEqDeclName)
}
match (← withReducible <| Simp.tryTheorem? e simpTheorem) with
| none => return .continue
| some r => return .done r
else
return .continue
private def simpMatchTargetCore (mvarId : MVarId) (matchDeclName : Name) (matchEqDeclName : Name) : MetaM MVarId := do
mvarId.withContext do
let target ← instantiateMVars (← mvarId.getType)
let r ← simpMatchCore matchDeclName matchEqDeclName target
match r.proof? with
| some proof => mvarId.replaceTargetEq r.expr proof
| none => mvarId.replaceTargetDefEq r.expr
private partial def withEqs (lhs rhs : Array Expr) (k : Array Expr → Array Expr → MetaM α) : MetaM α := do
go 0 #[] #[]
where
go (i : Nat) (hs : Array Expr) (rfls : Array Expr) : MetaM α := do
if i < lhs.size then
withLocalDeclD (← mkFreshUserName `heq) (← mkEqHEq lhs[i]! rhs[i]!) fun h => do
let rfl ← if (← inferType h).isEq then mkEqRefl lhs[i]! else mkHEqRefl lhs[i]!
go (i+1) (hs.push h) (rfls.push rfl)
else
k hs rfls
/--
Internal exception for discriminant generalization failures due to type errors.
-/
builtin_initialize discrGenExId : InternalExceptionId ←
registerInternalExceptionId `discrGeneralizationFailure
def isDiscrGenException (ex : Exception) : Bool :=
match ex with
| .internal id => id == discrGenExId
| _ => false
/--
This method makes sure each discriminant is a free variable.
Return the tuple `(discrsNew, discrEqs, mvarId)`. `discrsNew` in an array representing the new discriminants, `discrEqs` is an array of auxiliary equality hypotheses
that connect the new discriminants to the original terms they represent.
Remark: `discrEqs.size ≤ discrsNew.size`
Remark:
We should only generalize `discrs` occurrences as `match`-expression discriminants.
For example, given the following goal.
```
x : Nat
⊢ (match g x with
| 0 => 1
| Nat.succ y => g x) =
2 * x + 1
```
we should not generalize the `g x` in the rhs of the second alternative, and the two resulting goals
for the `split` tactic should be
```
case h_1
x x✝ : Nat
h✝ : g x = 0
⊢ 1 = 2 * x + 1
case h_2
x x✝ y✝ : Nat
h✝ : g x = Nat.succ y✝
⊢ g x = 2 * x + 1
```
-/
private partial def generalizeMatchDiscrs (mvarId : MVarId) (matcherDeclName : Name) (motiveType : Expr) (discrs : Array Expr) : MetaM (Array FVarId × Array FVarId × MVarId) := mvarId.withContext do
if discrs.all (·.isFVar) then
return (discrs.map (·.fvarId!), #[], mvarId)
let some matcherInfo ← getMatcherInfo? matcherDeclName | unreachable!
let numDiscrEqs := matcherInfo.getNumDiscrEqs -- Number of `h : discr = pattern` equations
let (targetNew, rfls) ←
forallTelescope motiveType fun discrVars _ =>
withEqs discrs discrVars fun eqs rfls => do
let foundRef ← IO.mkRef false
let rec mkNewTarget (e : Expr) : MetaM Expr := do
let pre (e : Expr) : MetaM TransformStep := do
if !e.isAppOfArity matcherDeclName matcherInfo.arity then
return .continue
let some matcherApp ← matchMatcherApp? e | return .continue
for matcherDiscr in matcherApp.discrs, discr in discrs do
unless matcherDiscr == discr do
trace[split.debug] "discr mismatch {matcherDiscr} != {discr}"
return .continue
let matcherApp := { matcherApp with discrs := discrVars }
foundRef.set true
let mut altsNew := #[]
for i in [:matcherApp.alts.size] do
let alt := matcherApp.alts[i]!
let altNumParams := matcherApp.altNumParams[i]!
let altNew ← lambdaTelescope alt fun xs body => do
if xs.size < altNumParams || xs.size < numDiscrEqs then
throwError "internal error in `split` tactic: encountered an unexpected `match` expression alternative\nthis error typically occurs when the `match` expression has been constructed using meta-programming."
let body ← mkLambdaFVars xs[altNumParams:] (← mkNewTarget body)
let ys := xs[:altNumParams - numDiscrEqs]
if numDiscrEqs == 0 then
mkLambdaFVars ys body
else
let altEqs := xs[altNumParams - numDiscrEqs : altNumParams]
withNewAltEqs matcherInfo eqs altEqs fun altEqsNew subst => do
let body := body.replaceFVars altEqs subst
mkLambdaFVars (ys++altEqsNew) body
altsNew := altsNew.push altNew
return .done { matcherApp with alts := altsNew }.toExpr
transform (← instantiateMVars e) pre
let targetNew ← mkNewTarget (← mvarId.getType)
unless (← foundRef.get) do
throwError "internal error in `split` tactic: failed to find match-expression discriminants\nthis error typically occurs when the `split` tactic internal functions have been used in a new meta-program"
let targetNew ← mkForallFVars (discrVars ++ eqs) targetNew
unless (← isTypeCorrect targetNew) do
throw <| Exception.internal discrGenExId
return (targetNew, rfls)
let mvarNew ← mkFreshExprSyntheticOpaqueMVar targetNew (← mvarId.getTag)
trace[split.debug] "targetNew:\n{mvarNew.mvarId!}"
mvarId.assign (mkAppN (mkAppN mvarNew discrs) rfls)
let (discrs', mvarId') ← mvarNew.mvarId!.introNP discrs.size
let (discrEqs, mvarId') ← mvarId'.introNP discrs.size
return (discrs', discrEqs, mvarId')
where
/--
- `eqs` are free variables `h_eq : discr = discrVar`. `eqs.size == discrs.size`
- `altEqs` are free variables of the form `h_altEq : discr = pattern`. `altEqs.size = numDiscrEqs ≤ discrs.size`
This method executes `k altEqsNew subst` where
- `altEqsNew` are fresh free variables of the form `h_altEqNew : discrVar = pattern`
- `subst` are terms of the form `h_eq.trans h_altEqNew : discr = pattern`. We use `subst` later to replace occurrences of `h_altEq` with `h_eq.trans h_altEqNew`.
-/
withNewAltEqs (matcherInfo : MatcherInfo) (eqs : Array Expr) (altEqs : Array Expr) (k : Array Expr → Array Expr → MetaM Expr) : MetaM Expr := do
let eqs' := (eqs.zip matcherInfo.discrInfos).filterMap fun (eq, info) => if info.hName?.isNone then none else some eq
-- `eqs'.size == altEqs.size ≤ eqs.size`
let rec go (i : Nat) (altEqsNew : Array Expr) (subst : Array Expr) : MetaM Expr := do
if i < altEqs.size then
let altEqDecl ← getFVarLocalDecl altEqs[i]!
let eq := eqs'[i]!
let eqType ← inferType eq
let altEqType := altEqDecl.type
match eqType.eq?, altEqType.eq? with
| some (_, _, discrVar), some (_, _ /- discr -/, pattern) =>
withLocalDeclD altEqDecl.userName (← mkEq discrVar pattern) fun altEqNew => do
go (i+1) (altEqsNew.push altEqNew) (subst.push (← mkEqTrans eq altEqNew))
| _, _ =>
match eqType.heq?, altEqType.heq? with
| some (_, _, _, discrVar), some (_, _ /- discr -/, _, pattern) =>
withLocalDeclD altEqDecl.userName (← mkHEq discrVar pattern) fun altEqNew => do
go (i+1) (altEqsNew.push altEqNew) (subst.push (← mkHEqTrans eq altEqNew))
| _, _ =>
throwError "internal error in `split` tactic: encountered unexpected auxiliary equalities created to generalize `match`-expression discriminant\nthis error typically occurs when the `split` tactic internal functions have been used in a new meta-program"
else
k altEqsNew subst
go 0 #[] #[]
private def substDiscrEqs (mvarId : MVarId) (fvarSubst : FVarSubst) (discrEqs : Array FVarId) : MetaM MVarId := mvarId.withContext do
let mut mvarId := mvarId
let mut fvarSubst := fvarSubst
for fvarId in discrEqs do
if let .fvar fvarId := fvarSubst.apply (mkFVar fvarId) then
let (fvarId, mvarId') ← heqToEq mvarId fvarId
match (← substCore? mvarId' fvarId (symm := false) fvarSubst) with
| some (fvarSubst', mvarId') => mvarId := mvarId'; fvarSubst := fvarSubst'
| none =>
match (← substCore? mvarId' fvarId (symm := true) fvarSubst) with
| some (fvarSubst', mvarId') => mvarId := mvarId'; fvarSubst := fvarSubst'
| none => mvarId := mvarId'
return mvarId
def applyMatchSplitter (mvarId : MVarId) (matcherDeclName : Name) (us : Array Level) (params : Array Expr) (discrs : Array Expr) : MetaM (List MVarId) := do
let some info ← getMatcherInfo? matcherDeclName | throwError "internal error in `split` tactic: `{matcherDeclName}` is not an auxiliary declaration used to encode `match`-expressions\nthis error typically occurs when the `split` tactic internal functions have been used in a new meta-program"
let matchEqns ← Match.getEquationsFor matcherDeclName
-- splitterPre does not have the correct universe elimination level, but this is fine, we only use it to compute the `motiveType`,
-- and we only care about the `motiveType` arguments, and not the resulting `Sort u`.
let splitterPre := mkAppN (mkConst matchEqns.splitterName us.toList) params
let motiveType := (← whnfForall (← inferType splitterPre)).bindingDomain!
trace[split.debug] "applyMatchSplitter\n{mvarId}"
let (discrFVarIds, discrEqs, mvarId) ← generalizeMatchDiscrs mvarId matcherDeclName motiveType discrs
trace[split.debug] "after generalizeMatchDiscrs\n{mvarId}"
let mvarId ← generalizeTargetsEq mvarId motiveType (discrFVarIds.map mkFVar)
mvarId.withContext do trace[split.debug] "discrEqs after generalizeTargetsEq: {discrEqs.map mkFVar}"
trace[split.debug] "after generalize\n{mvarId}"
let numEqs := discrs.size
let (discrFVarIdsNew, mvarId) ← mvarId.introN discrs.size
trace[split.debug] "after introN\n{mvarId}"
let discrsNew := discrFVarIdsNew.map mkFVar
let mvarType ← mvarId.getType
let elimUniv ← mvarId.withContext <| getLevel mvarType
let us ← if let some uElimPos := info.uElimPos? then
pure <| us.set! uElimPos elimUniv
else
unless elimUniv.isZero do
throwError "`split` tactic failed to split a match-expression: the splitter auxiliary theorem `{matchEqns.splitterName}` can only eliminate into `Prop`"
pure us
let splitter := mkAppN (mkConst matchEqns.splitterName us.toList) params
mvarId.withContext do
let motive ← mkLambdaFVars discrsNew mvarType
let splitter := mkAppN (mkApp splitter motive) discrsNew
check splitter
trace[split.debug] "after check splitter"
let mvarIds ← mvarId.apply splitter
unless mvarIds.length == matchEqns.size do
throwError "internal error in `split` tactic: unexpected number of goals created after applying splitter auxiliary theorem `{matchEqns.splitterName}` for `{matcherDeclName}`"
let (_, mvarIds) ← mvarIds.foldlM (init := (0, [])) fun (i, mvarIds) mvarId => do
let numParams := matchEqns.splitterAltNumParams[i]!
let (_, mvarId) ← mvarId.introN numParams
trace[split.debug] "before unifyEqs\n{mvarId}"
match (← Cases.unifyEqs? (numEqs + info.getNumDiscrEqs) mvarId {}) with
| none => return (i+1, mvarIds) -- case was solved
| some (mvarId, fvarSubst) =>
trace[split.debug] "after unifyEqs\n{mvarId}"
let mvarId ← substDiscrEqs mvarId fvarSubst discrEqs
return (i+1, mvarId::mvarIds)
return mvarIds.reverse
def mkDiscrGenErrorMsg (e : Expr) : MessageData :=
m!"`split` tactic failed to generalize discriminant(s) at{indentExpr e}\nresulting expression was not type correct\npossible solution: generalize discriminant(s) manually before using `split`"
def throwDiscrGenError (e : Expr) : MetaM α :=
throwError (mkDiscrGenErrorMsg e)
def splitMatch (mvarId : MVarId) (e : Expr) : MetaM (List MVarId) := do
let some app ← matchMatcherApp? e | throwError "internal error in `split` tactic: match application expected{indentExpr e}\nthis error typically occurs when the `split` tactic internal functions have been used in a new meta-program"
let matchEqns ← Match.getEquationsFor app.matcherName
let mvarIds ← applyMatchSplitter mvarId app.matcherName app.matcherLevels app.params app.discrs
let (_, mvarIds) ← mvarIds.foldlM (init := (0, [])) fun (i, mvarIds) mvarId => do
let mvarId ← simpMatchTargetCore mvarId app.matcherName matchEqns.eqnNames[i]!
return (i+1, mvarId::mvarIds)
return mvarIds.reverse
/-- Return an `if-then-else` or `match-expr` to split. -/
partial def findSplit? (env : Environment) (e : Expr) (splitIte := true) (exceptionSet : ExprSet := {}) : Option Expr :=
go e
where
go (e : Expr) : Option Expr :=
if let some target := e.find? isCandidate then
if e.isIte || e.isDIte then
let cond := target.getArg! 1 5
-- Try to find a nested `if` in `cond`
go cond |>.getD target
else
some target
else
none
isCandidate (e : Expr) : Bool := Id.run do
if exceptionSet.contains e then
false
else if splitIte && (e.isIte || e.isDIte) then
!(e.getArg! 1 5).hasLooseBVars
else if let some info := isMatcherAppCore? env e then
let args := e.getAppArgs
for i in [info.getFirstDiscrPos : info.getFirstDiscrPos + info.numDiscrs] do
if args[i]!.hasLooseBVars then
return false
return true
else
false
end Split
open Split
partial def splitTarget? (mvarId : MVarId) (splitIte := true) : MetaM (Option (List MVarId)) := commitWhenSome? do
let target ← instantiateMVars (← mvarId.getType)
let rec go (badCases : ExprSet) : MetaM (Option (List MVarId)) := do
if let some e := findSplit? (← getEnv) target splitIte badCases then
if e.isIte || e.isDIte then
return (← splitIfTarget? mvarId).map fun (s₁, s₂) => [s₁.mvarId, s₂.mvarId]
else
try
splitMatch mvarId e
catch ex =>
if isDiscrGenException ex then
trace[split.failure] mkDiscrGenErrorMsg e
else
trace[split.failure] "`split` tactic failed at{indentExpr e}\n{ex.toMessageData}"
go (badCases.insert e)
else
trace[split.debug] "did not find term to split\n{MessageData.ofGoal mvarId}"
return none
go {}
def splitLocalDecl? (mvarId : MVarId) (fvarId : FVarId) : MetaM (Option (List MVarId)) := commitWhenSome? do
mvarId.withContext do
if let some e := findSplit? (← getEnv) (← instantiateMVars (← inferType (mkFVar fvarId))) then
if e.isIte || e.isDIte then
return (← splitIfLocalDecl? mvarId fvarId).map fun (mvarId₁, mvarId₂) => [mvarId₁, mvarId₂]
else
let result? ← commitWhenSome? do try
let (fvarIds, mvarId) ← mvarId.revert #[fvarId]
let num := fvarIds.size
let mvarIds ← splitMatch mvarId e
let mvarIds ← mvarIds.mapM fun mvarId => return (← mvarId.introNP num).2
return some mvarIds
catch ex =>
if isDiscrGenException ex then
return none
else
throw ex
if result?.isSome then
return result?
-- Generalization failed, if `fvarId` is a let-decl or has forward dependencies, we try to `assert` a copy and try again
let localDecl ← fvarId.getDecl
if (← pure localDecl.isLet <||> exprDependsOn (← mvarId.getType) fvarId <||> fvarId.hasForwardDeps) then
try
let mvarId ← mvarId.assert localDecl.userName localDecl.type localDecl.toExpr
let mvarIds ← splitMatch mvarId e
let mvarIds ← mvarIds.mapM fun mvarId => return (← mvarId.intro1P).2
return some mvarIds
catch ex =>
if isDiscrGenException ex then
throwDiscrGenError e
else
throw ex
throwDiscrGenError e
else
return none
builtin_initialize
registerTraceClass `split.debug
registerTraceClass `split.failure
end Lean.Meta