blob: 463c850993fb6f74f324475c0a97e7b9ed6ffc43 [file]
/-
Copyright (c) 2021 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Dany Fabian
-/
module
prelude
public import Lean.Elab.PreDefinition.Structural.Basic
public import Lean.Elab.PreDefinition.Structural.RecArgInfo
import Lean.Util.HasConstCache
import Lean.Meta.IndPredBelow
import Init.Omega
namespace Lean.Elab.Structural
open Meta
open IndPredBelow (RecursionContext)
/-- Return the `i`th projection of the type `e` where `e` has `n` Ands. -/
def andProj (i n : Nat) (e : Expr) : Expr :=
match i, n with
| 0, 1 => e
| 0, _ + 1 => .proj ``And 0 e
| i + 1, k + 1 => andProj i k (.proj ``And 1 e)
| _, _ => e
def replaceIndPredRecApp (recArgInfo : RecArgInfo) (ctx : RecursionContext) (fidx : Nat)
(positions : Positions) (e : Expr) (args : Array Expr) : MetaM Expr := do
let some recArg := args[recArgInfo.recArgPos]? |
throwError "insufficient number of parameters at recursive application {indentExpr e}"
let recArg ← whnfCore recArg
let fail {α} : MetaM α := do throwError "failed to eliminate recursive application{indentExpr e}"
let .fvar recVar := recArg.getAppFn | fail
let some (motiveIdx, e) := ctx.motives.get? recVar | fail
let recApp := mkAppN e recArg.getAppArgs
let some pos := positions[motiveIdx]!.idxOf? fidx | fail
let mut ys := #[]
for h : i in *...args.size do
unless recArgInfo.indicesPos.contains i || i == recArgInfo.recArgPos do
unless recArgInfo.fixedParamPerm.isFixed i do
ys := ys.push args[i]
let recApp := andProj pos positions[motiveIdx]!.size recApp
return mkAppN recApp ys
partial def replaceIndPredRecApps (recArgInfos : Array RecArgInfo) (positions : Positions)
(params : Array Expr) (ctx : RecursionContext) (e : Expr) : M Expr := do
let recFnNames := recArgInfos.map (·.fnName)
let containsRecFn (e : Expr) : StateRefT (HasConstCache recFnNames) M Bool :=
modifyGet (·.contains e)
let rec loop (ctx : RecursionContext) (e : Expr) : StateRefT (HasConstCache recFnNames) M Expr := do
unless ← containsRecFn e do
return e
match e with
| .lam n d b c =>
withLocalDecl n c (← loop ctx d) fun x => do
mkLambdaFVars #[x] (← loop ctx (b.instantiate1 x))
| .forallE n d b c =>
withLocalDecl n c (← loop ctx d) fun x => do
mkForallFVars #[x] (← loop ctx (b.instantiate1 x))
| .letE n type val body nondep =>
mapLetDecl n (← loop ctx type) (← loop ctx val) (nondep := nondep) fun x => do
loop ctx (body.instantiate1 x)
| .mdata _ b => do
if let some stx := getRecAppSyntax? e then
withRef stx <| loop ctx b
else
return e.updateMData! (← loop ctx b)
| .proj _ _ e' => return e.updateProj! (← loop ctx e')
| .app _ _ =>
let processApp (e : Expr) : StateRefT (HasConstCache recFnNames) M Expr := do
e.withApp fun f args => do
let args ← args.mapM (loop ctx)
if let .const c _ := f then
if let some fidx := recFnNames.idxOf? c then
return ← replaceIndPredRecApp recArgInfos[fidx]! ctx fidx positions e args
return mkAppN (← loop ctx f) args
let some matcherApp ← matchMatcherApp? e | processApp e
if recArgInfos.all (fun i => !recArgHasLooseBVarsAt i.fnName i.recArgPos e) then
return ← processApp e
trace[Elab.definition.structural] "matcherApp before adding below transformation:\n{matcherApp.toExpr}"
let nrealParams := recArgInfos[0]!.indGroupInst.params.size
let matcherResult ← controlAt MetaM fun g =>
IndPredBelow.mkBelowMatcher matcherApp params nrealParams ctx fun ctx e =>
g (loop ctx e)
if let some (newApp, addMatcher) := matcherResult then
modifyThe State fun s => { s with addMatchers := s.addMatchers.push addMatcher }
processApp newApp -- recursive applications may still be hidden in e.g. the discriminants
else
-- Note: `recArgHasLooseBVarsAt` has false positives, so sometimes everything might stay
-- the same
processApp e
| _ =>
ensureNoRecFn recFnNames e
pure e
loop ctx e |>.run' {}
/--
Turns `fun a b => x` into `let funType := fun a b => α` (where `x : α`).
The continuation is the called with all `funType`s corresponding to the values.
-/
public def withFunTypes (values : Array Expr) (k : Array Expr → M α) : M α := do
go 0 #[]
where
go (i : Nat) (res : Array Expr) : M α :=
if h : i < values.size then
lambdaTelescope values[i] fun xs value => do
let type := (← inferType value).headBeta
let funType ← mkLambdaFVars xs type
withLetDecl ((`funType).appendIndexAfter (i + 1)) (← inferType funType) funType
fun funType => go (i + 1) (res.push funType)
else
k res
termination_by values.size - i
/--
Calculates the `.brecOn` motive corresponding to one structural recursive function.
The `value` is the function with (only) the fixed parameters moved into the context.
-/
public def mkIndPredBRecOnMotive (recArgInfo : RecArgInfo) (value funType : Expr) : M Expr := do
lambdaTelescope value fun xs _ => do
let type := mkAppN funType xs
let (indexMajorArgs, otherArgs) := recArgInfo.pickIndicesMajor xs
let motive ← mkForallFVars otherArgs type
mkLambdaFVars indexMajorArgs motive
/--
Calculates the `.brecOn` functional argument corresponding to one structural recursive function.
The `value` is the function with (only) the fixed parameters moved into the context,
The `FType` is the expected type of the argument.
The `recArgInfos` is used to transform the body of the function to replace recursive calls with
uses of the `below` induction hypothesis.
-/
public def mkIndPredBRecOnF (recArgInfos : Array RecArgInfo) (positions : Positions)
(recArgInfo : RecArgInfo) (value : Expr) (FType : Expr) (params : Array Expr) : M Expr := do
lambdaTelescope value fun xs value => do
let (indicesMajorArgs, otherArgs) := recArgInfo.pickIndicesMajor xs
let FType ← instantiateForall FType indicesMajorArgs
forallBoundedTelescope FType (some 1) fun below _ => do
let below := below[0]!
let belowName := (← inferType below).getForallBody.getAppFn.constName!
let ctx := {
belows := .insert {} indicesMajorArgs.back!.fvarId! (belowName, below)
motives := {}
}
let valueNew ← withDeclNameForAuxNaming recArgInfo.fnName <|
replaceIndPredRecApps recArgInfos positions params ctx value
mkLambdaFVars (indicesMajorArgs ++ #[below] ++ otherArgs) valueNew
end Lean.Elab.Structural