blob: b55d3afd640fada1dbf81cd8685ef926ebbcf7f0 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Joachim Breitner
-/
module
prelude
public import Lean.Meta.Tactic.Util
public import Lean.Meta.Tactic.FunIndInfo
public section
/-!
Support for collecting function calls that could be used for `fun_induction` or `fun_cases`.
Used by `fun_induction foo`, and the `Calls` structure is also used by `try?`.
-/
namespace Lean.Meta.FunInd
structure Call where
/- The full function call -/
expr : Expr
/- Used to avoid adding calls that differ only in dropped arguments -/
relevantArgs : Expr
deriving Hashable, BEq
structure SeenCalls where
/-- the full calls -/
calls : Array Expr
/-- only function name and relevant arguments -/
seen : Std.HashSet (Name × Array Expr)
instance : EmptyCollection SeenCalls where
emptyCollection := ⟨#[], {}⟩
def SeenCalls.isEmpty (sc : SeenCalls) : Bool :=
sc.calls.isEmpty
def SeenCalls.push (e : Expr) (funIndInfo : FunIndInfo) (args : Array Expr) (calls : SeenCalls) :
MetaM SeenCalls := do
if funIndInfo.params.size != args.size then return calls
let mut keys := #[]
for arg in args, kind in funIndInfo.params do
if kind matches .target then
if !arg.isFVar then return calls
unless kind matches .dropped do
keys := keys.push arg
let key := (funIndInfo.funName, keys)
if calls.seen.contains key then return calls
return { calls := calls.calls.push e, seen := calls.seen.insert key }
/--
Which functions have exactly one candidate application. Used by `try?` to determine whether
we can use `fun_induction foo` or need `fun_induction foo x y z`.
-/
def SeenCalls.uniques (calls : SeenCalls) : NameSet := Id.run do
let mut seen : NameSet := {}
let mut seenTwice : NameSet := {}
for (n, _) in calls.seen do
unless seenTwice.contains n do
if seen.contains n then
seenTwice := seenTwice.insert n
else
seen := seen.insert n
return seen.filter (! seenTwice.contains ·)
namespace Collector
abbrev M := ReaderT FunIndInfo <| StateRefT SeenCalls MetaM
def saveFunInd (e : Expr) (funIndInfo : FunIndInfo) (args : Array Expr) : M Unit := do
set (← (← get).push e funIndInfo args)
def visitApp (e : Expr) (funIndInfo : FunIndInfo) (args : Array Expr) : M Unit := do
saveFunInd e funIndInfo args
unsafe abbrev Cache := PtrSet Expr
unsafe def visit (e : Expr) : StateRefT Cache M Unit := do
unless (← get).contains e do
modify fun s => s.insert e
match e with
| .const _ _ => pure ()
| .forallE _ d b _ => visit d; visit b
| .lam _ d b _ => visit d; visit b
| .mdata _ b => visit b
| .letE _ t v b _ => visit t; visit v; visit b
| .app .. => e.withApp fun f args => do
if let .const declName _ := f then
if declName = (← read).funName then
unless e.hasLooseBVars do -- TODO: We can allow them in `.dropped` arguments
visitApp e (← read) args
else
visit f
args.forM visit
| .proj _ _ b => visit b
| _ => return ()
unsafe def main (needle : FunIndInfo) (mvarId : MVarId) : MetaM (Array Expr) := mvarId.withContext do
let (_, s) ← go |>.run mkPtrSet |>.run needle |>.run {}
return s.calls
where
go : StateRefT Cache M Unit := do
for localDecl in (← getLCtx) do
unless localDecl.isAuxDecl do
if let some val := localDecl.value? then
visit (← instantiateMVars val)
else
visit (← instantiateMVars localDecl.type)
visit (← instantiateMVars (← mvarId.getType))
end Collector
def collect (needle : FunIndInfo) (mvarId : MVarId) : MetaM (Array Expr) := do
unsafe Collector.main needle mvarId
end Lean.Meta.FunInd