blob: 0b9fa8b6988938210b60a4a96645e88b474f53fe [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.Refl
import Lean.Meta.Tactic.Assumption
import Lean.Meta.SameCtorUtils
import Init.Omega
import Lean.Meta.Tactic.Injection
import Lean.Meta.Tactic.Simp.Attr
public section
namespace Lean.Meta
private def mkAnd? (args : Array Expr) : Option Expr := Id.run do
if args.isEmpty then
return none
else
let mut result := args.back!
for arg in args.reverse[1...*] do
result := mkApp2 (mkConst ``And) arg result
return result
def elimOptParam (type : Expr) : CoreM Expr := do
Core.transform type fun e =>
if e.isAppOfArity ``optParam 2 then
return TransformStep.visit (e.getArg! 0)
else
return .continue
private def mkEqs (args1 args2 : Array Expr) (skipIfPropOrEq : Bool := true) : MetaM (Array Expr) := do
let mut eqs := #[]
for arg1 in args1, arg2 in args2 do
let arg1Type ← inferType arg1
if !skipIfPropOrEq then
eqs := eqs.push (← mkEqHEq arg1 arg2)
else if !(← isProp arg1Type) && arg1 != arg2 then
eqs := eqs.push (← mkEqHEq arg1 arg2)
return eqs
private def mkInjectiveTheoremTypeCore? (ctorVal : ConstructorVal) (useEq : Bool) : MetaM (Option Expr) := do
let us := ctorVal.levelParams.map mkLevelParam
let type ← elimOptParam ctorVal.type
forallBoundedTelescope type ctorVal.numParams fun params type =>
forallTelescope type fun args1 resultType => do
let k (args2 args2New : Array Expr) : MetaM (Option Expr) := do
let lhs := mkAppN (mkAppN (mkConst ctorVal.name us) params) args1
let rhs := mkAppN (mkAppN (mkConst ctorVal.name us) params) args2
let eq ← mkEq lhs rhs
let eqs ← mkEqs args1 args2
if let some andEqs := mkAnd? eqs then
let result ← if useEq then
mkEq eq andEqs
else
mkArrow eq andEqs
mkForallFVars params (← mkForallFVars args1 (← mkForallFVars args2New result))
else
return none
let rec mkArgs2 (i : Nat) (type : Expr) (args2 args2New : Array Expr) : MetaM (Option Expr) := do
if h : i < args1.size then
let .forallE n d b _ ← whnf type | throwError "unexpected constructor type for `{ctorVal.name}`"
let arg1 := args1[i]
if occursOrInType (← getLCtx) arg1 resultType then
mkArgs2 (i + 1) (b.instantiate1 arg1) (args2.push arg1) args2New
else
withLocalDecl n (if useEq then BinderInfo.default else BinderInfo.implicit) d fun arg2 =>
mkArgs2 (i + 1) (b.instantiate1 arg2) (args2.push arg2) (args2New.push arg2)
else
k args2 args2New
if useEq then
mkArgs2 0 type #[] #[]
else
withImplicitBinderInfos (params ++ args1) do
mkArgs2 0 type #[] #[]
private def mkInjectiveTheoremType? (ctorVal : ConstructorVal) : MetaM (Option Expr) :=
mkInjectiveTheoremTypeCore? ctorVal false
private def injTheoremFailureHeader (ctorName : Name) : MessageData :=
m!"failed to prove injectivity theorem for constructor `{ctorName}`, use 'set_option genInjectivity false' to disable the generation"
private def throwInjectiveTheoremFailure {α} (ctorName : Name) (mvarId : MVarId) : MetaM α :=
throwError "{injTheoremFailureHeader ctorName}{indentD <| MessageData.ofGoal mvarId}"
private def splitAndAssumption (mvarId : MVarId) (ctorName : Name) : MetaM Unit := do
(← mvarId.splitAnd).forM fun mvarId =>
unless (← mvarId.assumptionCore) do
throwInjectiveTheoremFailure ctorName mvarId
private def solveEqOfCtorEq (ctorName : Name) (mvarId : MVarId) (h : FVarId) : MetaM Unit := do
trace[Meta.injective] "solving injectivity goal for {ctorName} with hypothesis {mkFVar h} at\n{mvarId}"
match (← injection mvarId h) with
| InjectionResult.solved => unreachable!
| InjectionResult.subgoal mvarId .. => splitAndAssumption mvarId ctorName
private def mkInjectiveTheoremValue (ctorName : Name) (targetType : Expr) : MetaM Expr :=
forallTelescopeReducing targetType fun xs type => do
let mvar ← mkFreshExprSyntheticOpaqueMVar type
solveEqOfCtorEq ctorName mvar.mvarId! xs.back!.fvarId!
mkLambdaFVars xs mvar
def mkInjectiveTheoremNameFor (ctorName : Name) : Name :=
ctorName ++ `inj
private def mkInjectiveTheorem (ctorVal : ConstructorVal) : MetaM Unit := do
let name := mkInjectiveTheoremNameFor ctorVal.name
withTraceNode `Meta.injective (msg := (return m!"{exceptEmoji ·} generating `{name}`")) do
let some type ← mkInjectiveTheoremType? ctorVal
| return ()
trace[Meta.injective] "type: {type}"
let value ← mkInjectiveTheoremValue ctorVal.name type
addDecl <| Declaration.thmDecl {
name
levelParams := ctorVal.levelParams
type := (← instantiateMVars type)
value := (← instantiateMVars value)
}
def mkInjectiveEqTheoremNameFor (ctorName : Name) : Name :=
ctorName ++ `injEq
private def mkInjectiveEqTheoremType? (ctorVal : ConstructorVal) : MetaM (Option Expr) :=
mkInjectiveTheoremTypeCore? ctorVal true
/--
Collects all components of a nested `And`, as projections.
(Avoids the binders that `MVarId.casesAnd` would introduce.)
-/
private partial def andProjections (e : Expr) : MetaM (Array Expr) := do
let rec go (e : Expr) (t : Expr) (acc : Array Expr) : MetaM (Array Expr) := do
match_expr t with
| And t1 t2 =>
let acc ← go (mkProj ``And 0 e) t1 acc
let acc ← go (mkProj ``And 0 e) t2 acc
return acc
| _ =>
return acc.push e
go e (← inferType e) #[]
private def mkInjectiveEqTheoremValue (ctorVal : ConstructorVal) (targetType : Expr) : MetaM Expr := do
forallTelescopeReducing targetType fun xs type => do
let mvar ← mkFreshExprSyntheticOpaqueMVar type
let [mvarId₁, mvarId₂] ← mvar.mvarId!.apply (mkConst ``Eq.propIntro)
| throwError "unexpected number of subgoals when proving injective theorem for constructor `{ctorVal.name}`"
let injPrf := mkConst (mkInjectiveTheoremNameFor ctorVal.name) (ctorVal.levelParams.map mkLevelParam)
let injPrf := mkAppN injPrf xs
mvarId₁.assign injPrf
let mut mvarId₂ := mvarId₂
while true do
let t ← mvarId₂.getType
let some (conj, body) := t.arrow? | break
match_expr conj with
| And lhs rhs =>
let [mvarId₂'] ← mvarId₂.applyN (mkApp3 (mkConst `Lean.injEq_helper) lhs rhs body) 1
| throwError "unexpected number of goals after applying `Lean.and_imp`"
mvarId₂ := mvarId₂'
| _ => pure ()
(_, mvarId₂) ← introSubstEq mvarId₂
try mvarId₂.refl catch _ => throwError (injTheoremFailureHeader ctorVal.name)
mkLambdaFVars xs mvar
private def mkInjectiveEqTheorem (ctorVal : ConstructorVal) : MetaM Unit := do
let name := mkInjectiveEqTheoremNameFor ctorVal.name
withTraceNode `Meta.injective (msg := (return m!"{exceptEmoji ·} generating `{name}`")) do
let some type ← mkInjectiveEqTheoremType? ctorVal
| return ()
trace[Meta.injective] "type: {type}"
let value ← mkInjectiveEqTheoremValue ctorVal type
addDecl <| Declaration.thmDecl {
name
levelParams := ctorVal.levelParams
type := (← instantiateMVars type)
value := (← instantiateMVars value)
}
addSimpTheorem (ext := simpExtension) name (post := true) (inv := false) AttributeKind.global (prio := eval_prio default)
register_builtin_option genInjectivity : Bool := {
defValue := true
descr := "generate injectivity theorems for inductive datatype constructors. \
Temporarily (for bootstrapping reasons) also controls the generation of the
`ctorIdx` definition."
}
def mkInjectiveTheorems (declName : Name) : MetaM Unit := do
if (← getEnv).contains ``Eq.propIntro && genInjectivity.get (← getOptions) && !(← isInductivePredicate declName) then
withTraceNode `Meta.injective (return m!"{exceptEmoji ·} {declName}") do
let info ← getConstInfoInduct declName
unless info.isUnsafe do
-- We need to reset the local context here because `solveEqOfCtorEq` uses
-- `assumptionCore`, which can reference "outside" free variables that
-- were not introduced by `mkInjective(Eq)Theorem` and are not abstracted
-- by `mkLambdaFVars`, thus adding a declaration with free variables.
-- See https://github.com/leanprover/lean4/issues/2188
withLCtx {} {} do
for ctor in info.ctors do
withExporting (isExporting := !isPrivateName ctor) do
let ctorVal ← getConstInfoCtor ctor
if ctorVal.numFields > 0 then
mkInjectiveTheorem ctorVal
mkInjectiveEqTheorem ctorVal
builtin_initialize
registerTraceClass `Meta.injective
def getCtorAppIndices? (ctorApp : Expr) : MetaM (Option (Array Expr)) := do
let type ← whnfD (← inferType ctorApp)
type.withApp fun typeFn typeArgs => do
let .const declName _ := typeFn | return none
let .inductInfo val ← getConstInfo declName | return none
if val.numIndices == 0 then return some #[]
return some typeArgs[val.numParams...*].toArray
private structure MkHInjTypeResult where
thmType : Expr
us : List Level
numIndices : Nat
private def mkHInjType? (ctorVal : ConstructorVal) : MetaM (Option MkHInjTypeResult) := do
let us := ctorVal.levelParams.map mkLevelParam
let type ← elimOptParam ctorVal.type
forallTelescope type fun args1 _ =>
withImplicitBinderInfos args1 do
let params1 := args1[:ctorVal.numParams]
let k (args2 : Array Expr) : MetaM (Option MkHInjTypeResult) := do
let params2 := args2[:ctorVal.numParams]
let lhs := mkAppN (mkConst ctorVal.name us) args1
let rhs := mkAppN (mkConst ctorVal.name us) args2
let eq ← mkEqHEq lhs rhs
let eqs ← mkEqs args1 args2
if let some andEqs := mkAnd? eqs then
let result ← mkArrow eq andEqs
let some idxs1 ← getCtorAppIndices? lhs | return none
let some idxs2 ← getCtorAppIndices? rhs | return none
-- **Note**: We dot not skip here because the type of `noConfusion` does not.
let idxEqs ← mkEqs (params1 ++ idxs1) (params2 ++ idxs2) (skipIfPropOrEq := false)
let result ← mkArrowN idxEqs result
let thmType ← mkForallFVars args1 (← mkForallFVars args2 result)
return some { thmType, us, numIndices := idxs1.size }
else
return none
let rec mkArgs2 (i : Nat) (type : Expr) (args2 : Array Expr) : MetaM (Option MkHInjTypeResult) := do
if h : i < args1.size then
let .forallE n d b _ ← whnf type | throwError "unexpected constructor type for `{ctorVal.name}`"
let arg1 := args1[i]
withLocalDecl n .implicit d fun arg2 =>
mkArgs2 (i + 1) (b.instantiate1 arg2) (args2.push arg2)
else
k args2
mkArgs2 0 type #[]
private def failedToGenHInj (ctorVal : ConstructorVal) : MetaM α :=
throwError "failed to generate heterogeneous injectivity theorem for `{ctorVal.name}`"
private partial def mkHInjectiveTheoremValue? (ctorVal : ConstructorVal) (typeInfo : MkHInjTypeResult) : MetaM (Option Expr) := do
forallTelescopeReducing typeInfo.thmType fun xs type => do
let noConfusionName := ctorVal.induct.str "noConfusion"
let noConfusion := mkConst noConfusionName (0 :: typeInfo.us)
let noConfusion := mkApp noConfusion type
let n := xs.size - ctorVal.numParams - typeInfo.numIndices - 1
let eqs := xs[n...*].toArray
let eqExprs ← eqs.mapM fun x => do
match_expr (← inferType x) with
| Eq _ lhs rhs => return (lhs, rhs)
| HEq _ lhs _ rhs => return (lhs, rhs)
| _ => failedToGenHInj ctorVal
let (args₁, args₂) := eqExprs.unzip
let noConfusion := mkAppN (mkAppN (mkAppN noConfusion args₁) args₂) eqs
let .forallE _ d _ _ ← whnf (← inferType noConfusion) | failedToGenHInj ctorVal
let mvar ← mkFreshExprSyntheticOpaqueMVar d
let noConfusion := mkApp noConfusion mvar
let mvarId := mvar.mvarId!
let (_, mvarId) ← mvarId.intros
splitAndAssumption mvarId ctorVal.name
let result ← instantiateMVars noConfusion
mkLambdaFVars xs result
private def hinjSuffix := "hinj"
def mkHInjectiveTheoremNameFor (ctorName : Name) : Name :=
ctorName.str hinjSuffix
private def mkHInjectiveTheorem? (thmName : Name) (ctorVal : ConstructorVal) : MetaM (Option TheoremVal) := do
let some typeInfo ← mkHInjType? ctorVal | return none
let some value ← mkHInjectiveTheoremValue? ctorVal typeInfo | return none
return some { name := thmName, value, levelParams := ctorVal.levelParams, type := typeInfo.thmType }
builtin_initialize registerReservedNamePredicate fun env n =>
match n with
| .str p "hinj" => (env.find? p matches some (.ctorInfo _))
| _ => false
builtin_initialize
registerReservedNameAction fun name => do
let .str p "hinj" := name | return false
let some (.ctorInfo ctorVal) := (← getEnv).find? p | return false
MetaM.run' do
let some thmVal ← mkHInjectiveTheorem? name ctorVal | return false
realizeConst p name do
addDecl (← mkThmOrUnsafeDef thmVal)
return true
end Lean.Meta