blob: eac7e1a55c6c51b7ef5367165fb747120b194240 [file]
/-
Copyright (c) 2019 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
prelude
import Lean.Data.LBool
import Lean.Meta.InferType
import Lean.Meta.NatInstTesters
import Lean.Util.SafeExponentiation
namespace Lean.Meta
private abbrev withInstantiatedMVars (e : Expr) (k : Expr → OptionT MetaM α) : OptionT MetaM α := do
let eNew ← instantiateMVars e
if eNew.getAppFn.isMVar then
failure
else
k eNew
/--
Evaluate simple `Nat` expressions.
Remark: this method assumes the given expression has type `Nat`. -/
partial def evalNat (e : Expr) : OptionT MetaM Nat := do
match e with
| .lit (.natVal n) => return n
| .mdata _ e => evalNat e
| .const ``Nat.zero .. => return 0
| .app .. => visit e
| .mvar .. => visit e
| _ => failure
where
evalPow (b n : Expr) : OptionT MetaM Nat := do
let n ← evalNat n
guard (← checkExponent n)
return (← evalNat b) ^ n
visit e := do
match_expr e with
| OfNat.ofNat _ n i => guard (← isInstOfNatNat i); evalNat n
| Nat.succ a => return (← evalNat a) + 1
| Nat.add a b => return (← evalNat a) + (← evalNat b)
| Add.add _ i a b => guard (← isInstAddNat i); return (← evalNat a) + (← evalNat b)
| HAdd.hAdd _ _ _ i a b => guard (← isInstHAddNat i); return (← evalNat a) + (← evalNat b)
| Nat.sub a b => return (← evalNat a) - (← evalNat b)
| Sub.sub _ i a b => guard (← isInstSubNat i); return (← evalNat a) - (← evalNat b)
| HSub.hSub _ _ _ i a b => guard (← isInstHSubNat i); return (← evalNat a) - (← evalNat b)
| Nat.mul a b => return (← evalNat a) * (← evalNat b)
| Mul.mul _ i a b => guard (← isInstMulNat i); return (← evalNat a) * (← evalNat b)
| HMul.hMul _ _ _ i a b => guard (← isInstHMulNat i); return (← evalNat a) * (← evalNat b)
| Nat.div a b => return (← evalNat a) / (← evalNat b)
| Div.div _ i a b => guard (← isInstDivNat i); return (← evalNat a) / (← evalNat b)
| HDiv.hDiv _ _ _ i a b => guard (← isInstHDivNat i); return (← evalNat a) / (← evalNat b)
| Nat.mod a b => return (← evalNat a) % (← evalNat b)
| Mod.mod _ i a b => guard (← isInstModNat i); return (← evalNat a) % (← evalNat b)
| HMod.hMod _ _ _ i a b => guard (← isInstHModNat i); return (← evalNat a) % (← evalNat b)
| Nat.pow a b => evalPow a b
| NatPow.pow _ i a b => guard (← isInstNatPowNat i); evalPow a b
| Pow.pow _ _ i a b => guard (← isInstPowNat i); evalPow a b
| HPow.hPow _ _ _ i a b => guard (← isInstHPowNat i); evalPow a b
| _ => failure
/--
Checks that expression `e` is definitional equal to `inst`.
Uses `instances` transparency so that reducible terms and instances extended
other instances are unfolded.
-/
def matchesInstance (e inst : Expr) : MetaM Bool :=
-- Note. We use withNewMCtxDepth to avoid assigning meta-variables in isDefEq checks
withNewMCtxDepth (withTransparency .instances (isDefEq e inst))
mutual
/--
Quick function for converting `e` into `s + k` s.t. `e` is definitionally equal to `Nat.add s k`.
This function always succeeds in finding such `s` and `k`
(as a last resort it returns `e` and `0`).
-/
private partial def getOffset (e : Expr) : MetaM (Expr × Nat) :=
return (← isOffset? e).getD (e, 0)
/--
Similar to `getOffset` but returns `none` if the expression is not an offset.
-/
partial def isOffset? (e : Expr) : OptionT MetaM (Expr × Nat) := do
let add (a b : Expr) := do
let v ← evalNat b
let (s, k) ← getOffset a
return (s, k+v)
match_expr e with
| Nat.succ a =>
let (s, k) ← getOffset a
return (s, k+1)
| Nat.add a b => add a b
| Add.add _ i a b => guard (← matchesInstance i Nat.mkInstAdd); add a b
| HAdd.hAdd _ _ _ i a b => guard (← matchesInstance i Nat.mkInstHAdd); add a b
| _ => failure
end
private def isNatZero (e : Expr) : MetaM Bool := do
match (← evalNat e) with
| some v => return v == 0
| _ => return false
private def mkOffset (e : Expr) (offset : Nat) : MetaM Expr := do
if offset == 0 then
return e
else if (← isNatZero e) then
return mkNatLit offset
else
return mkNatAdd e (mkNatLit offset)
def isDefEqOffset (s t : Expr) : MetaM LBool := do
let ifNatExpr (x : MetaM LBool) : MetaM LBool := do
let type ← inferType s
-- Remark: we use `withNewMCtxDepth` to make sure we don't assign metavariables when performing the `isDefEq` test
if (← withNewMCtxDepth <| Meta.isExprDefEqAux type (mkConst ``Nat)) then
x
else
return LBool.undef
let isDefEq (s t) : MetaM LBool :=
ifNatExpr <| toLBoolM <| Meta.isExprDefEqAux s t
if !(← getConfig).offsetCnstrs then
return LBool.undef
else
match (← isOffset? s) with
| some (s, k₁) =>
match (← isOffset? t) with
| some (t, k₂) => -- s+k₁ =?= t+k₂
if k₁ == k₂ then
isDefEq s t
else if k₁ < k₂ then
isDefEq s (← mkOffset t (k₂ - k₁))
else
isDefEq (← mkOffset s (k₁ - k₂)) t
| none =>
match (← evalNat t) with
| some v₂ => -- s+k₁ =?= v₂
if v₂ ≥ k₁ then
isDefEq s (mkNatLit <| v₂ - k₁)
else
ifNatExpr <| return LBool.false
| none =>
return LBool.undef
| none =>
match (← evalNat s) with
| some v₁ =>
match (← isOffset? t) with
| some (t, k₂) => -- v₁ =?= t+k₂
if v₁ ≥ k₂ then
isDefEq (mkNatLit <| v₁ - k₂) t
else
ifNatExpr <| return LBool.false
| none =>
match (← evalNat t) with
| some v₂ => ifNatExpr <| return (v₁ == v₂).toLBool -- v₁ =?= v₂
| none => return LBool.undef
| none => return LBool.undef
end Lean.Meta