blob: dc9200c6c2e814ffc5eeb27c8c3811c476ec848d [file]
/-
Copyright (c) 2025 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sebastian Graf
-/
module
prelude
public import Lean.Meta.Tactic.Simp.Types
import Lean.Meta.Tactic.Assumption
import Lean.Meta.Tactic.Refl
import Lean.Meta.Tactic.Simp.Rewrite
public section
namespace Lean.Meta
/--
Tries to rewrite the `ite`, `dite` or `cond` expression `e` with the hypothesis `hc`.
If it fails, it returns a rewrite with `proof? := none` and unchaged expression.
-/
def rwIfWith (hc : Expr) (e : Expr) : MetaM Simp.Result := do
match_expr e with
| ite@ite α c h t f =>
let us := ite.constLevels!
if (← isDefEq c (← inferType hc)) then
return {
expr := t
proof? := (mkAppN (mkConst ``if_pos us) #[c, h, hc, α, t, f])
}
if (← isDefEq (mkNot c) (← inferType hc)) then
return {
expr := f
proof? := (mkAppN (mkConst ``if_neg us) #[c, h, hc, α, t, f])
}
| dite@dite α c h t f =>
let us := dite.constLevels!
if (← isDefEq c (← inferType hc)) then
return {
expr := t.beta #[hc]
proof? := (mkAppN (mkConst ``dif_pos us) #[c, h, hc, α, t, f])
}
if (← isDefEq (mkNot c) (← inferType hc)) then
return {
expr := f.beta #[hc]
proof? := (mkAppN (mkConst ``dif_neg us) #[c, h, hc, α, t, f])
}
| cond@cond α c t f =>
let us := cond.constLevels!
if (← isDefEq (← inferType hc) (← mkEq c (mkConst ``Bool.true))) then
return {
expr := t
proof? := (mkAppN (mkConst ``Bool.cond_pos us) #[α, c, t, f, hc])
}
if (← isDefEq (← inferType hc) (← mkEq c (mkConst ``Bool.false))) then
return {
expr := f
proof? := (mkAppN (mkConst ``Bool.cond_neg us) #[α, c, t, f, hc])
}
| _ => pure ()
return { expr := e }
/--
In the `onAlt` handler of a `MatcherApp.transform`, you can use this function on a properly
substituted matcher application with the alternative `altIdx`.
If it fails, it returns a rewrite with `proof? := none` and the unchanged expression.
"Properly substituted" here means that the discriminants have been substituted according to the
alternative; otherwise, the rewrite might fail because some hypothesis of the congruence
equation theorem cannot be discharged by assumption or reflixivity.
See `Lean.Meta.Tactic.FunInd.buildInductionBody` and `Lean.Elab.Tactic.Do.VCGen.Split` for examples
of how to coerce `MatherApp.transform` into doing the substitution on the motive for you.
-/
def rwMatcher (altIdx : Nat) (e : Expr) : MetaM Simp.Result := do
if e.isAppOf ``PSum.casesOn || e.isAppOf ``PSigma.casesOn then
let mut e := e
while true do
if let some e' ← reduceRecMatcher? e then
e := e'.headBeta
else
let e' := e.headBeta
if e != e' then
e := e'
else
break
return { expr := e }
else
unless (← isMatcherApp e) do
trace[Meta.Match.debug] "Not a matcher application:{indentExpr e}"
return { expr := e }
let matcherDeclName := e.getAppFn.constName!
let eqns ← Match.genMatchCongrEqns matcherDeclName
unless altIdx < eqns.size do
trace[Meta.Match.debug] "When trying to reduce arm {altIdx}, only {eqns.size} equations for {.ofConstName matcherDeclName}"
return { expr := e }
let eqnThm := eqns[altIdx]!
try
withTraceNode `Meta.Match.debug (pure m!"{exceptEmoji ·} rewriting with {.ofConstName eqnThm} in{indentExpr e}") do
let eqProof := mkAppN (mkConst eqnThm e.getAppFn.constLevels!) e.getAppArgs
let (hyps, _, eqType) ← forallMetaTelescope (← inferType eqProof)
trace[Meta.Match.debug] "eqProof has type{indentExpr eqType}"
let proof := mkAppN eqProof hyps
let hyps := hyps.map (·.mvarId!)
let (isHeq, lhs, rhs) ← do
if let some (_, lhs, _, rhs) := eqType.heq? then pure (true, lhs, rhs) else
if let some (_, lhs, rhs) := eqType.eq? then pure (false, lhs, rhs) else
throwError m!"Type of `{.ofConstName eqnThm}` is not an equality"
if !(← isDefEq e lhs) then
throwError m!"Left-hand side `{lhs}` of `{.ofConstName eqnThm}` does not apply to `{e}`"
/-
Here we instantiate the hypotheses of the congruence equation theorem
There are two sets of hypotheses to instantiate:
- `Eq` or `HEq` that relate the discriminants to the patterns
Solving these should instantiate the pattern variables.
- Overlap hypotheses (`isEqnThmHypothesis`)
With more book keeping we could maybe do this very precisely, knowing exactly
which facts provided by the splitter should go where, but it's tedious.
So for now let's use heuristics and try `assumption` and `rfl`.
-/
for h in hyps do
unless (← h.isAssigned) do
let hType ← h.getType
if Simp.isEqnThmHypothesis hType then
-- Using unrestricted h.substVars here does not work well; it could
-- even introduce a dependency on the `oldIH` we want to eliminate
h.assumption <|> throwError "Failed to discharge `{h}`"
else if hType.isEq then
h.assumption <|> h.refl <|> throwError m!"Failed to resolve `{h}`"
else if hType.isHEq then
h.assumption <|> h.hrefl <|> throwError m!"Failed to resolve `{h}`"
let unassignedHyps ← hyps.filterM fun h => return !(← h.isAssigned)
unless unassignedHyps.isEmpty do
throwError m!"Not all hypotheses of `{.ofConstName eqnThm}` could be discharged: {unassignedHyps}"
let rhs ← instantiateMVars rhs
let proof ← instantiateMVars proof
let proof ← if isHeq then
try mkEqOfHEq proof
catch e => throwError m!"Could not un-HEq `{proof}`:{indentD e.toMessageData} "
else
pure proof
return {
expr := rhs
proof? := proof
}
catch ex =>
trace[Meta.Match.debug] "Failed to apply {.ofConstName eqnThm}:{indentD ex.toMessageData}"
return { expr := e }