blob: d1b6f7ccc094f03c66976254996c4afc32809e27 [file]
/-
Copyright (c) 2020 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
import Lean.Meta.RecursorInfo
import Lean.Meta.SynthInstance
import Lean.Meta.Tactic.Util
import Lean.Meta.Tactic.Revert
import Lean.Meta.Tactic.Intro
import Lean.Meta.Tactic.Clear
import Lean.Meta.Tactic.FVarSubst
namespace Lean.Meta
private partial def getTargetArity : Expr → Nat
| Expr.mdata _ b _ => getTargetArity b
| Expr.forallE _ _ b _ => getTargetArity b + 1
| e => if e.isHeadBetaTarget then getTargetArity e.headBeta else 0
private def addRecParams (mvarId : MVarId) (majorTypeArgs : Array Expr) : List (Option Nat) → Expr → MetaM Expr
| [], recursor => pure recursor
| some pos :: rest, recursor =>
if h : pos < majorTypeArgs.size then
addRecParams mvarId majorTypeArgs rest (mkApp recursor (majorTypeArgs.get ⟨pos, h⟩))
else
throwTacticEx `induction mvarId "ill-formed recursor"
| none :: rest, recursor => do
let recursorType ← inferType recursor
let recursorType ← whnfForall recursorType
match recursorType with
| Expr.forallE _ d _ _ => do
let param ← try synthInstance d catch _ => throwTacticEx `induction mvarId "failed to generate type class instance parameter"
addRecParams mvarId majorTypeArgs rest (mkApp recursor param)
| _ =>
throwTacticEx `induction mvarId "ill-formed recursor"
structure InductionSubgoal where
mvarId : MVarId
fields : Array Expr := #[]
subst : FVarSubst := {}
deriving Inhabited
private def getTypeBody (mvarId : MVarId) (type : Expr) (x : Expr) : MetaM Expr := do
let type ← whnfForall type
match type with
| Expr.forallE _ _ b _ => pure $ b.instantiate1 x
| _ => throwTacticEx `induction mvarId "ill-formed recursor"
structure AltVarNames where
explicit : Bool := false -- true if `@` modifier was used
varNames : List Name := []
deriving Inhabited
private partial def finalize
(mvarId : MVarId) (givenNames : Array AltVarNames) (recursorInfo : RecursorInfo)
(reverted : Array FVarId) (major : Expr) (indices : Array Expr) (baseSubst : FVarSubst) (recursor : Expr)
: MetaM (Array InductionSubgoal) := do
let target ← getMVarType mvarId
let initialArity := getTargetArity target
let recursorType ← inferType recursor
let numMinors := recursorInfo.produceMotive.length
let rec loop (pos : Nat) (minorIdx : Nat) (recursor recursorType : Expr) (consumedMajor : Bool) (subgoals : Array InductionSubgoal) := do
let recursorType ← whnfForall recursorType
if recursorType.isForall && pos < recursorInfo.numArgs then
if pos == recursorInfo.firstIndexPos then
let (recursor, recursorType) ← indices.foldlM (init := (recursor, recursorType)) fun (recursor, recursorType) index => do
let recursor := mkApp recursor index
let recursorType ← getTypeBody mvarId recursorType index
pure (recursor, recursorType)
let recursor := mkApp recursor major
let recursorType ← getTypeBody mvarId recursorType major
loop (pos+1+indices.size) minorIdx recursor recursorType true subgoals
else
-- consume motive
let tag ← getMVarTag mvarId
if minorIdx ≥ numMinors then throwTacticEx `induction mvarId "ill-formed recursor"
match recursorType with
| Expr.forallE n d b c =>
let d := d.headBeta
-- Remark is givenNames is not empty, then user provided explicit alternatives for each minor premise
if c.binderInfo.isInstImplicit && givenNames.isEmpty then
match (← synthInstance? d) with
| some inst =>
let recursor := mkApp recursor inst
let recursorType ← getTypeBody mvarId recursorType inst
loop (pos+1) (minorIdx+1) recursor recursorType consumedMajor subgoals
| none => do
-- Add newSubgoal if type class resolution failed
let mvar ← mkFreshExprSyntheticOpaqueMVar d (tag ++ n)
let recursor := mkApp recursor mvar
let recursorType ← getTypeBody mvarId recursorType mvar
loop (pos+1) (minorIdx+1) recursor recursorType consumedMajor (subgoals.push { mvarId := mvar.mvarId! })
else
let arity := getTargetArity d
if arity < initialArity then throwTacticEx `induction mvarId "ill-formed recursor"
let nparams := arity - initialArity -- number of fields due to minor premise
let nextra := reverted.size - indices.size - 1 -- extra dependencies that have been reverted
let minorGivenNames := if h : minorIdx < givenNames.size then givenNames.get ⟨minorIdx, h⟩ else {}
let mvar ← mkFreshExprSyntheticOpaqueMVar d (tag ++ n)
let recursor := mkApp recursor mvar
let recursorType ← getTypeBody mvarId recursorType mvar
-- Try to clear major premise from new goal
let mvarId' ← tryClear mvar.mvarId! major.fvarId!
let (fields, mvarId') ← introN mvarId' nparams minorGivenNames.varNames (useNamesForExplicitOnly := !minorGivenNames.explicit)
let (extra, mvarId') ← introNP mvarId' nextra
let subst := reverted.size.fold (init := baseSubst) fun i (subst : FVarSubst) =>
if i < indices.size + 1 then subst
else
let revertedFVarId := reverted[i]
let newFVarId := extra[i - indices.size - 1]
subst.insert revertedFVarId (mkFVar newFVarId)
let fields := fields.map mkFVar
loop (pos+1) (minorIdx+1) recursor recursorType consumedMajor (subgoals.push { mvarId := mvarId', fields := fields, subst := subst })
| _ => unreachable!
else
unless consumedMajor do throwTacticEx `induction mvarId "ill-formed recursor"
assignExprMVar mvarId recursor
pure subgoals
loop (recursorInfo.paramsPos.length + 1) 0 recursor recursorType false #[]
private def throwUnexpectedMajorType {α} (mvarId : MVarId) (majorType : Expr) : MetaM α :=
throwTacticEx `induction mvarId m!"unexpected major premise type{indentExpr majorType}"
def induction (mvarId : MVarId) (majorFVarId : FVarId) (recursorName : Name) (givenNames : Array AltVarNames := #[]) : MetaM (Array InductionSubgoal) :=
withMVarContext mvarId do
trace[Meta.Tactic.induction] "initial\n{MessageData.ofGoal mvarId}"
checkNotAssigned mvarId `induction
let majorLocalDecl ← getLocalDecl majorFVarId
let recursorInfo ← mkRecursorInfo recursorName
let some majorType ← whnfUntil majorLocalDecl.type recursorInfo.typeName | throwUnexpectedMajorType mvarId majorLocalDecl.type
majorType.withApp fun _ majorTypeArgs => do
recursorInfo.paramsPos.forM fun paramPos? => do
match paramPos? with
| none => pure ()
| some paramPos => if paramPos ≥ majorTypeArgs.size then throwTacticEx `induction mvarId m!"major premise type is ill-formed{indentExpr majorType}"
let mctx ← getMCtx
let indices ← recursorInfo.indicesPos.toArray.mapM fun idxPos => do
if idxPos ≥ majorTypeArgs.size then throwTacticEx `induction mvarId m!"major premise type is ill-formed{indentExpr majorType}"
let idx := majorTypeArgs.get! idxPos
unless idx.isFVar do throwTacticEx `induction mvarId m!"major premise type index {idx} is not a variable{indentExpr majorType}"
majorTypeArgs.size.forM fun i => do
let arg := majorTypeArgs[i]
if i != idxPos && arg == idx then
throwTacticEx `induction mvarId m!"'{idx}' is an index in major premise, but it occurs more than once{indentExpr majorType}"
if i < idxPos && mctx.exprDependsOn arg idx.fvarId! then
throwTacticEx `induction mvarId m!"'{idx}' is an index in major premise, but it occurs in previous arguments{indentExpr majorType}"
-- If arg is also and index and a variable occurring after `idx`, we need to make sure it doesn't depend on `idx`.
-- Note that if `arg` is not a variable, we will fail anyway when we visit it.
if i > idxPos && recursorInfo.indicesPos.contains i && arg.isFVar then
let idxDecl ← getLocalDecl idx.fvarId!
if mctx.localDeclDependsOn idxDecl arg.fvarId! then
throwTacticEx `induction mvarId m!"'{idx}' is an index in major premise, but it depends on index occurring at position #{i+1}"
pure idx
let target ← getMVarType mvarId
if !recursorInfo.depElim && mctx.exprDependsOn target majorFVarId then
throwTacticEx `induction mvarId m!"recursor '{recursorName}' does not support dependent elimination, but conclusion depends on major premise"
-- Revert indices and major premise preserving variable order
let (reverted, mvarId) ← revert mvarId ((indices.map Expr.fvarId!).push majorFVarId) true
-- Re-introduce indices and major
let (indices', mvarId) ← introNP mvarId indices.size
let (majorFVarId', mvarId) ← intro1P mvarId
-- Create FVarSubst with indices
let baseSubst := do
let mut subst : FVarSubst := {}
let mut i := 0
for index in indices do
subst := subst.insert index.fvarId! (mkFVar indices'[i])
i := i + 1
pure subst
trace[Meta.Tactic.induction] "after revert&intro\n{MessageData.ofGoal mvarId}"
-- Update indices and major
let indices := indices'.map mkFVar
let majorFVarId := majorFVarId'
let major := mkFVar majorFVarId
withMVarContext mvarId do
let target ← getMVarType mvarId
let targetLevel ← getLevel target
let targetLevel ← normalizeLevel targetLevel
let majorLocalDecl ← getLocalDecl majorFVarId
let some majorType ← whnfUntil majorLocalDecl.type recursorInfo.typeName | throwUnexpectedMajorType mvarId majorLocalDecl.type
majorType.withApp fun majorTypeFn majorTypeArgs => do
match majorTypeFn with
| Expr.const majorTypeFnName majorTypeFnLevels _ => do
let majorTypeFnLevels := majorTypeFnLevels.toArray
let (recursorLevels, foundTargetLevel) ← recursorInfo.univLevelPos.foldlM (init := (#[], false))
fun (recursorLevels, foundTargetLevel) (univPos : RecursorUnivLevelPos) => do
match univPos with
| RecursorUnivLevelPos.motive => pure (recursorLevels.push targetLevel, true)
| RecursorUnivLevelPos.majorType idx =>
if idx ≥ majorTypeFnLevels.size then throwTacticEx `induction mvarId "ill-formed recursor"
pure (recursorLevels.push (majorTypeFnLevels.get! idx), foundTargetLevel)
if !foundTargetLevel && !targetLevel.isZero then
throwTacticEx `induction mvarId m!"recursor '{recursorName}' can only eliminate into Prop"
let recursor := mkConst recursorName recursorLevels.toList
let recursor ← addRecParams mvarId majorTypeArgs recursorInfo.paramsPos recursor
-- Compute motive
let motive := target
let motive ← if recursorInfo.depElim then mkLambdaFVars #[major] motive else pure motive
let motive ← mkLambdaFVars indices motive
let recursor := mkApp recursor motive
finalize mvarId givenNames recursorInfo reverted major indices baseSubst recursor
| _ =>
throwTacticEx `induction mvarId "major premise is not of the form (C ...)"
builtin_initialize registerTraceClass `Meta.Tactic.induction
end Lean.Meta