blob: db6d64896d78b6db5a682957a926e1b7c48ade25 [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.Expr
namespace Lean
namespace Expr
namespace FindImpl
abbrev cacheSize : USize := 8192 - 1
structure State where
keys : Array Expr -- Remark: our "unsafe" implementation relies on the fact that `()` is not a valid Expr
abbrev FindM := StateT State Id
unsafe def visited (e : Expr) (size : USize) : FindM Bool := do
let s ← get
let h := ptrAddrUnsafe e
let i := h % size
let k := s.keys.uget i lcProof
if ptrAddrUnsafe k == h then
pure true
else
modify fun s => { keys := s.keys.uset i e lcProof }
pure false
unsafe def findM? (p : Expr → Bool) (size : USize) (e : Expr) : OptionT FindM Expr :=
let rec visit (e : Expr) := do
if (← visited e size) then
failure
else if p e then
pure e
else match e with
| Expr.forallE _ d b _ => visit d <|> visit b
| Expr.lam _ d b _ => visit d <|> visit b
| Expr.mdata _ b => visit b
| Expr.letE _ t v b _ => visit t <|> visit v <|> visit b
| Expr.app f a => visit f <|> visit a
| Expr.proj _ _ b => visit b
| _ => failure
visit e
unsafe def initCache : State :=
{ keys := mkArray cacheSize.toNat (cast lcProof ()) }
unsafe def findUnsafe? (p : Expr → Bool) (e : Expr) : Option Expr :=
Id.run <| findM? p cacheSize e |>.run' initCache
end FindImpl
@[implemented_by FindImpl.findUnsafe?]
def find? (p : Expr → Bool) (e : Expr) : Option Expr :=
/- This is a reference implementation for the unsafe one above -/
if p e then
some e
else match e with
| Expr.forallE _ d b _ => find? p d <|> find? p b
| Expr.lam _ d b _ => find? p d <|> find? p b
| Expr.mdata _ b => find? p b
| Expr.letE _ t v b _ => find? p t <|> find? p v <|> find? p b
| Expr.app f a => find? p f <|> find? p a
| Expr.proj _ _ b => find? p b
| _ => none
/-- Return true if `e` occurs in `t` -/
def occurs (e : Expr) (t : Expr) : Bool :=
(t.find? fun s => s == e).isSome
/--
Return type for `findExt?` function argument.
-/
inductive FindStep where
/-- Found desired subterm -/ | found
/-- Search subterms -/ | visit
/-- Do not search subterms -/ | done
namespace FindExtImpl
unsafe def findM? (p : Expr → FindStep) (size : USize) (e : Expr) : OptionT FindImpl.FindM Expr :=
visit e
where
visitApp (e : Expr) :=
match e with
| Expr.app f a .. => visitApp f <|> visit a
| e => visit e
visit (e : Expr) := do
if (← FindImpl.visited e size) then
failure
else match p e with
| FindStep.done => failure
| FindStep.found => pure e
| FindStep.visit =>
match e with
| Expr.forallE _ d b _ => visit d <|> visit b
| Expr.lam _ d b _ => visit d <|> visit b
| Expr.mdata _ b => visit b
| Expr.letE _ t v b _ => visit t <|> visit v <|> visit b
| Expr.app .. => visitApp e
| Expr.proj _ _ b => visit b
| _ => failure
unsafe def findUnsafe? (p : Expr → FindStep) (e : Expr) : Option Expr :=
Id.run <| findM? p FindImpl.cacheSize e |>.run' FindImpl.initCache
end FindExtImpl
/--
Similar to `find?`, but `p` can return `FindStep.done` to interrupt the search on subterms.
Remark: Differently from `find?`, we do not invoke `p` for partial applications of an application. -/
@[implemented_by FindExtImpl.findUnsafe?]
opaque findExt? (p : Expr → FindStep) (e : Expr) : Option Expr
end Expr
end Lean