blob: 188fd930df21c7278f8c150e2ef2a623a4b95604 [file]
/-
Copyright (c) 2021 Gabriel Ebner. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Gabriel Ebner, Mario Carneiro
-/
module
prelude
import Lean.Meta.Tactic.Ext
import Lean.Elab.Tactic.RCases
import Lean.Elab.Command
import Lean.Linter.Basic
-- These public imports are needed because for now we make `extCore` public.
public import Lean.Elab.Term.TermElabM
/-!
# Implementation of the `@[ext]` attribute
-/
namespace Lean.Elab.Tactic.Ext
open Meta Term
/-!
### Meta code for creating ext theorems
-/
/--
Constructs the hypotheses for the structure extensionality theorem that
states that two structures are equal if their fields are equal.
Calls the continuation `k` with the list of parameters to the structure,
two structure variables `x` and `y`, and a list of pairs `(field, ty)`
where each `ty` is of the form `x.field = y.field` or `x.field ≍ y.field`.
If `flat` parses to `true`, any fields inherited from parent structures
are treated as fields of the given structure type.
If it is `false`, then the behind-the-scenes encoding of inherited fields
is visible in the extensionality lemma.
-/
def withExtHyps (struct : Name) (flat : Bool)
(k : Array Expr → (x y : Expr) → Array (Name × Expr) → MetaM α) : MetaM α := do
unless isStructure (← getEnv) struct do
throwError "Internal error when constructing `ext` hypotheses: `{struct}` is not a structure"
let structC ← mkConstWithLevelParams struct
forallTelescope (← inferType structC) fun params _ => do
withImplicitBinderInfos params do
withLocalDecl `x .implicit (mkAppN structC params) fun x => do
withLocalDecl `y .implicit (mkAppN structC params) fun y => do
let mut hyps := #[]
let fields ← if flat then
pure <| getStructureFieldsFlattened (← getEnv) struct (includeSubobjectFields := false)
else
pure <| getStructureFields (← getEnv) struct
for field in fields do
let x_f ← mkProjection x field
let y_f ← mkProjection y field
unless ← isProof x_f do
hyps := hyps.push (field, ← mkEqHEq x_f y_f)
k params x y hyps
/--
Creates the type of the extensionality theorem for the given structure,
returning `∀ {x y : Struct}, x.1 = y.1 → x.2 = y.2 → x = y`, for example.
-/
def mkExtType (structName : Name) (flat : Bool) : MetaM Expr := withLCtx {} {} do
withExtHyps structName flat fun params x y hyps => do
let ty := hyps.foldr (init := ← mkEq x y) fun (f, h) ty => .forallE f h ty .default
mkForallFVars (params |>.push x |>.push y) ty
/--
Derives the type of the `iff` form of an ext theorem.
-/
def mkExtIffType (extThmName : Name) : MetaM Expr := withLCtx {} {} do
forallTelescopeReducing (← getConstInfo extThmName).type fun args ty => do
let failNotEq := throwError "Expected a theorem proving a proposition of the form `x = y`, but `{.ofConstName extThmName}` proves{indentD ty}"
let some (_, x, y) := ty.eq? | failNotEq
let some xIdx := args.findIdx? (· == x) | failNotEq
let some yIdx := args.findIdx? (· == y) | failNotEq
unless xIdx + 1 == yIdx do
throwError "Expected `{x}` and `{y}` to be consecutive arguments"
let startIdx := yIdx + 1
let toRevert := args[startIdx...*].toArray
let fvars ← toRevert.foldlM (init := {}) (fun st e => return collectFVars st (← inferType e))
for fvar in toRevert do
unless ← Meta.isProof fvar do
throwError "Argument `{fvar}` is not a proof, but all arguments after `{x}` and `{y}` must be proofs"
if fvars.fvarSet.contains fvar.fvarId! then
throwError "Argument `{fvar}` is depended upon by a subsequent argument, which is not supported for arguments after `{x}` and `{y}`"
let conj := mkAndN (← toRevert.mapM (inferType ·)).toList
-- Make everything implicit except for inst implicits
let mut newBis := #[]
for fvar in args[*...startIdx] do
if (← fvar.fvarId!.getBinderInfo) matches .default | .strictImplicit then
newBis := newBis.push (fvar.fvarId!, .implicit)
withNewBinderInfos newBis do
mkForallFVars args[*...startIdx] <| mkIff ty conj
/--
Ensures that the given structure has an ext theorem, without validating any pre-existing theorems.
Returns the name of the ext theorem.
See `Lean.Elab.Tactic.Ext.withExtHyps` for an explanation of the `flat` argument.
-/
def realizeExtTheorem (structName : Name) (flat : Bool) : Elab.Command.CommandElabM Name := do
unless isStructure (← getEnv) structName do
throwError "Internal error when realizing `ext` theorem: `{structName}` is not a structure"
let extName := structName.mkStr "ext"
unless (← getEnv).contains extName do
try
Elab.Command.liftTermElabM <| withoutErrToSorry <| withDeclName extName do
let type ← mkExtType structName flat
let pf ← withoutExporting <| withSynthesize do
let indVal ← getConstInfoInduct structName
let params := Array.replicate indVal.numParams (← `(_))
Elab.Term.elabTermEnsuringType (expectedType? := type) (implicitLambda := false)
-- introduce the params, do cases on 'x' and 'y', and then substitute each equation
(← `(by intro $params* {..} {..}; intros; subst_eqs; rfl))
let pf ← instantiateMVars pf
if pf.hasMVar then throwError "Internal error: Synthesized `ext` proof contains metavariables{indentD pf}"
let info ← getConstInfo structName
addDecl <| Declaration.thmDecl {
name := extName
type
value := pf
levelParams := info.levelParams
}
modifyEnv fun env => addProtected env extName
addDeclarationRangesFromSyntax extName (← getRef)
catch e =>
throwError m!"\
Failed to generate an `ext` theorem for `{.ofConstName structName}`: {e.toMessageData}"
return extName
/--
Given an 'ext' theorem, ensures that there is an iff version of the theorem (if possible),
without validating any pre-existing theorems.
Returns the name of the 'ext_iff' theorem.
-/
def realizeExtIffTheorem (extName : Name) : Elab.Command.CommandElabM Name := do
let extIffName : Name :=
match extName with
| .str n s => .str n (s ++ "_iff")
| _ => .str extName "ext_iff"
unless (← getEnv).contains extIffName do
try
let info ← getConstInfo extName
Elab.Command.liftTermElabM <| withoutErrToSorry <| withDeclName extIffName do
let type ← mkExtIffType extName
let pf ← withoutExporting <| withSynthesize do
Elab.Term.elabTermEnsuringType (expectedType? := type) <| ← `(by
intros
refine ⟨?_, ?_⟩
· intro h; cases h; and_intros <;> (intros; first | rfl | simp | fail "Failed to prove converse of ext theorem")
· intro; (repeat cases ‹_ ∧ _›); apply $(mkCIdent extName) <;> assumption)
let pf ← instantiateMVars pf
if pf.hasMVar then throwError "Internal error: Synthesized `ext_iff` proof contains metavariables{indentD pf}"
addDecl <| Declaration.thmDecl {
name := extIffName
type
value := pf
levelParams := info.levelParams
}
-- Only declarations in a namespace can be protected:
unless extIffName.isAtomic do
modifyEnv fun env => addProtected env extIffName
addDeclarationRangesFromSyntax extIffName (← getRef)
catch e =>
throwError m!"\
Failed to generate an `ext_iff` theorem from `{.ofConstName extName}`: {e.toMessageData}"
++ .hint' m!"Try `@[ext (iff := false)]` to prevent generating an `ext_iff` theorem."
return extIffName
/-!
### Attribute
-/
open Ext
builtin_initialize registerBuiltinAttribute {
name := `ext
descr := "Marks a theorem as an extensionality theorem"
add := fun declName stx kind => MetaM.run' do
let `(attr| ext $[(iff := false%$iffFalse?)]? $[(flat := false%$flatFalse?)]? $(prio)?) := stx
| throwError "Invalid `[ext]` attribute syntax"
let iff := iffFalse?.isNone
let flat := flatFalse?.isNone
let mut declName := declName
if isStructure (← getEnv) declName then
declName ← liftCommandElabM <| withRef stx <| realizeExtTheorem declName flat
else if let some stx := flatFalse? then
throwErrorAt stx "Unexpected `flat` configuration on `[ext]` theorem"
-- Validate and add theorem to environment extension
let declTy := (← getConstInfo declName).type
let (_, _, declTy) ← withDefault <| forallMetaTelescopeReducing declTy
let failNotEq := throwError "\
`[ext]` attribute only applies to structures and to theorems proving `x = y` where `x` and `y` are variables, \
but this theorem proves{indentD declTy}"
let some (ty, lhs, rhs) := declTy.eq? | failNotEq
unless lhs.isMVar && rhs.isMVar do failNotEq
let keys ← withReducible <| DiscrTree.mkPath ty
let priority ← liftCommandElabM <| Elab.liftMacroM do evalPrio (prio.getD (← `(prio| default)))
extExtension.add {declName, keys, priority} kind
-- Realize iff theorem
if iff then
discard <| liftCommandElabM <| withRef stx <| realizeExtIffTheorem declName
erase := fun declName => do
let s := extExtension.getState (← getEnv)
let s ← s.erase declName
modifyEnv fun env => extExtension.modifyState env fun _ => s
}
/-!
### Implementation of `ext` tactic
-/
/-- Apply a single extensionality theorem to `goal`. -/
-- Tis is public for now as it is used internally in `aesop`.
public def applyExtTheoremAt (goal : MVarId) : MetaM (List MVarId) := goal.withContext do
let tgt ← goal.getType'
unless tgt.isAppOfArity ``Eq 3 do
throwError "This extensionality tactic only applies to equalities, not{indentExpr tgt}"
let ty := tgt.getArg! 0
let s ← saveState
for lem in ← getExtTheorems ty do
try
-- Note: We have to do this extra check to ensure that we don't apply e.g.
-- funext to a goal `(?a₁ : ?b) = ?a₂` to produce `(?a₁ x : ?b') = ?a₂ x`,
-- since this will loop.
-- We require that the type of the equality is not changed by the `goal.apply c` line
-- TODO: add flag to apply tactic to toggle unification vs. matching
withNewMCtxDepth do
let c ← mkConstWithFreshMVarLevels lem.declName
let (_, _, declTy) ← withDefault <| forallMetaTelescopeReducing (← inferType c)
guard (← isDefEq tgt declTy)
-- We use `newGoals := .all` as this is
-- more useful in practice with dependently typed arguments of `@[ext]` theorems.
return ← goal.apply (cfg := { newGoals := .all }) (← mkConstWithFreshMVarLevels lem.declName)
catch _ => s.restore
throwError m!"No applicable extensionality theorem found for type{indentExpr ty}"
++ .note m!"Extensionality theorems can be registered by marking them with the `[ext]` attribute"
/-- Apply a single extensionality theorem to the current goal. -/
@[builtin_tactic applyExtTheorem] def evalApplyExtTheorem : Tactic := fun _ => do
liftMetaTactic applyExtTheoremAt
/--
Postprocessor for `withExt` which runs `rintro` with the given patterns when the target is a
pi type.
-/
def tryIntros [Monad m] [MonadLiftT TermElabM m] (g : MVarId) (pats : List (TSyntax `rcasesPat))
(k : MVarId → List (TSyntax `rcasesPat) → m Nat) : m Nat := do
match pats with
| [] => k (← (g.intros : TermElabM _)).2 []
| p::ps =>
if (← (g.withContext g.getType' : TermElabM _)).isForall then
let mut n := 0
for g in ← RCases.rintro #[p] none g do
n := n.max (← tryIntros g ps k)
pure (n + 1)
else k g pats
/--
Applies a single extensionality theorem, using `pats` to introduce variables in the result.
Runs continuation `k` on each subgoal.
-/
def withExt1 [Monad m] [MonadLiftT TermElabM m] (g : MVarId) (pats : List (TSyntax `rcasesPat))
(k : MVarId → List (TSyntax `rcasesPat) → m Nat) : m Nat := do
let mut n := 0
for g in ← (applyExtTheoremAt g : TermElabM _) do
n := n.max (← tryIntros g pats k)
pure n
/--
Applies extensionality theorems recursively, using `pats` to introduce variables in the result.
Runs continuation `k` on each subgoal.
-/
def withExtN [Monad m] [MonadLiftT TermElabM m] [MonadExcept Exception m]
(g : MVarId) (pats : List (TSyntax `rcasesPat)) (k : MVarId → List (TSyntax `rcasesPat) → m Nat)
(depth := 100) (failIfUnchanged := true) : m Nat :=
match depth with
| 0 => k g pats
| depth+1 => do
if failIfUnchanged then
withExt1 g pats fun g pats => withExtN g pats k depth (failIfUnchanged := false)
else try
withExt1 g pats fun g pats => withExtN g pats k depth (failIfUnchanged := false)
catch _ => k g pats
/--
Apply extensionality theorems as much as possible, using `pats` to introduce the variables
in extensionality theorems like `funext`. Returns a list of subgoals.
This is built on top of `withExtN`, running in `TermElabM` to build the list of new subgoals.
(And, for each goal, the patterns consumed.)
-/
-- This is public as it is used in the implementation of `rcongr` in Batteries.
public def extCore (g : MVarId) (pats : List (TSyntax `rcasesPat))
(depth := 100) (failIfUnchanged := true) :
TermElabM (Nat × Array (MVarId × List (TSyntax `rcasesPat))) := do
StateT.run (m := TermElabM) (s := #[])
(withExtN g pats (fun g qs => modify (·.push (g, qs)) *> pure 0) depth failIfUnchanged)
@[builtin_tactic ext] def evalExt : Tactic := fun stx => do
match stx with
| `(tactic| ext $pats* $[: $n]?) => do
let pats := RCases.expandRIntroPats pats
let depth := n.map (·.getNat) |>.getD 100
let (used, gs) ← extCore (← getMainGoal) pats.toList depth
if RCases.linter.unusedRCasesPattern.get (← getOptions) then
if used < pats.size then
let unused := MessageData.andList <| pats[used...*].toList.map (m!"`{·}`")
Linter.logLint RCases.linter.unusedRCasesPattern (mkNullNode pats[used...*].toArray)
m!"`ext` did not consume the patterns {unused}"
replaceMainGoal <| gs.map (·.1) |>.toList
| _ => throwUnsupportedSyntax
end Lean.Elab.Tactic.Ext