| /- | |
| 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.Data.HashMap | |
| namespace Lean.SCC | |
| /-! | |
| Very simple implementation of Tarjan's SCC algorithm. | |
| Performance is not a goal here since we use this module to | |
| compiler mutually recursive definitions, where each function | |
| (and nested let-rec) in the mutual block is a vertex. | |
| So, the graphs are small. -/ | |
| section | |
| variable (α : Type) [BEq α] [Hashable α] | |
| structure Data where | |
| index? : Option Nat := none | |
| lowlink? : Option Nat := none | |
| onStack : Bool := false | |
| structure State where | |
| stack : List α := [] | |
| nextIndex : Nat := 0 | |
| data : HashMap α Data := {} | |
| sccs : List (List α) := [] | |
| abbrev M := StateM (State α) | |
| end | |
| variable {α : Type} [BEq α] [Hashable α] | |
| private def getDataOf (a : α) : M α Data := do | |
| let s ← get | |
| match s.data.find? a with | |
| | some d => pure d | |
| | none => pure {} | |
| private def push (a : α) : M α Unit := | |
| modify fun s => { s with | |
| stack := a :: s.stack, | |
| nextIndex := s.nextIndex + 1, | |
| data := s.data.insert a { | |
| index? := s.nextIndex, | |
| lowlink? := s.nextIndex, | |
| onStack := true | |
| } | |
| } | |
| private def modifyDataOf (a : α) (f : Data → Data) : M α Unit := | |
| modify fun s => { s with | |
| data := match s.data.find? a with | |
| | none => s.data | |
| | some d => s.data.insert a (f d) | |
| } | |
| private def resetOnStack (a : α) : M α Unit := | |
| modifyDataOf a fun d => { d with onStack := false } | |
| private def updateLowLinkOf (a : α) (v : Option Nat) : M α Unit := | |
| modifyDataOf a fun d => { d with | |
| lowlink? := match d.lowlink?, v with | |
| | i, none => i | |
| | none, i => i | |
| | some i, some j => if i < j then i else j | |
| } | |
| private def addSCC (a : α) : M α Unit := do | |
| let rec add | |
| | [], newSCC => modify fun s => { s with stack := [], sccs := newSCC :: s.sccs } | |
| | b::bs, newSCC => do | |
| resetOnStack b; | |
| let newSCC := b::newSCC; | |
| if a != b then | |
| add bs newSCC | |
| else | |
| modify fun s => { s with stack := bs, sccs := newSCC :: s.sccs } | |
| add (← get).stack [] | |
| private partial def sccAux (successorsOf : α → List α) (a : α) : M α Unit := do | |
| push a | |
| (successorsOf a).forM fun b => do | |
| let bData ← getDataOf b; | |
| if bData.index?.isNone then | |
| -- `b` has not been visited yet | |
| sccAux successorsOf b; | |
| let bData ← getDataOf b; | |
| updateLowLinkOf a bData.lowlink? | |
| else if bData.onStack then do | |
| -- `b` is on the stack. So, it must be in the current SCC | |
| -- The edge `(a, b)` is pointing to an SCC already found and must be ignored | |
| updateLowLinkOf a bData.index? | |
| else | |
| pure () | |
| let aData ← getDataOf a; | |
| if aData.lowlink? == aData.index? then | |
| addSCC a | |
| def scc (vertices : List α) (successorsOf : α → List α) : List (List α) := | |
| let main : M α Unit := vertices.forM fun a => do | |
| let aData ← getDataOf a | |
| if aData.index?.isNone then sccAux successorsOf a | |
| let (_, s) := main.run {} | |
| s.sccs.reverse | |
| end Lean.SCC |