| /- | |
| Copyright (c) 2021 Microsoft Corporation. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Leonardo de Moura | |
| -/ | |
| import Lean.MetavarContext | |
| namespace Lean | |
| /-- | |
| Return true if `e` does **not** contain `mvarId` directly or indirectly | |
| This function considers assigments and delayed assignments. -/ | |
| partial def occursCheck [Monad m] [MonadMCtx m] (mvarId : MVarId) (e : Expr) : m Bool := do | |
| if !e.hasExprMVar then | |
| return true | |
| else | |
| match (← visit e |>.run |>.run {}) with | |
| | (.ok .., _) => return true | |
| | (.error .., _) => return false | |
| where | |
| visitMVar (mvarId' : MVarId) : ExceptT Unit (StateT ExprSet m) Unit := do | |
| if mvarId == mvarId' then | |
| throw () -- found | |
| else | |
| match (← getExprMVarAssignment? mvarId') with | |
| | some v => visit v | |
| | none => | |
| match (← getDelayedMVarAssignment? mvarId') with | |
| | some d => visitMVar d.mvarIdPending | |
| | none => return () | |
| visit (e : Expr) : ExceptT Unit (StateT ExprSet m) Unit := do | |
| if !e.hasExprMVar then | |
| return () | |
| else if (← get).contains e then | |
| return () | |
| else | |
| modify fun s => s.insert e | |
| match e with | |
| | Expr.proj _ _ s => visit s | |
| | Expr.forallE _ d b _ => visit d; visit b | |
| | Expr.lam _ d b _ => visit d; visit b | |
| | Expr.letE _ t v b _ => visit t; visit v; visit b | |
| | Expr.mdata _ b => visit b | |
| | Expr.app f a => visit f; visit a | |
| | Expr.mvar mvarId => visitMVar mvarId | |
| | _ => return () | |
| end Lean |