src/librustc_data_structures/graph/scc/mod.rs

   1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Routine to compute the strongly connected components (SCCs) of a
  12 //! graph, as well as the resulting DAG if each SCC is replaced with a
  13 //! node in the graph. This uses Tarjan's algorithm that completes in
  14 //! O(n) time.
  15
  16 use fx::FxHashSet;
  17 use graph::{DirectedGraph, WithNumNodes, WithSuccessors};
  18 use indexed_vec::{Idx, IndexVec};
  19 use std::ops::Range;
  20
  21 mod test;
  22
  23 /// Strongly connected components (SCC) of a graph. The type `N` is
  24 /// the index type for the graph nodes and `S` is the index type for
  25 /// the SCCs. We can map from each node to the SCC that it
  26 /// participates in, and we also have the successors of each SCC.
  27 pub struct Sccs<N: Idx, S: Idx> {
  28     /// For each node, what is the SCC index of the SCC to which it
  29     /// belongs.
  30     scc_indices: IndexVec<N, S>,
  31
  32     /// Data about each SCC.
  33     scc_data: SccData<S>,
  34 }
  35
  36 struct SccData<S: Idx> {
  37     /// For each SCC, the range of `all_successors` where its
  38     /// successors can be found.
  39     ranges: IndexVec<S, Range<usize>>,
  40
  41     /// Contains the succcessors for all the Sccs, concatenated. The
  42     /// range of indices corresponding to a given SCC is found in its
  43     /// SccData.
  44     all_successors: Vec<S>,
  45 }
  46
  47 impl<N: Idx, S: Idx> Sccs<N, S> {
  48     pub fn new(graph: &(impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors)) -> Self {
  49         SccsConstruction::construct(graph)
  50     }
  51
  52     /// Returns the number of SCCs in the graph.
  53     pub fn num_sccs(&self) -> usize {
  54         self.scc_data.len()
  55     }
  56
  57     /// Returns the number of SCCs in the graph.
  58     pub fn all_sccs(&self) -> impl Iterator<Item = S> {
  59         (0 .. self.scc_data.len()).map(S::new)
  60     }
  61
  62     /// Returns the SCC to which a node `r` belongs.
  63     pub fn scc(&self, r: N) -> S {
  64         self.scc_indices[r]
  65     }
  66
  67     /// Returns the successors of the given SCC.
  68     pub fn successors(&self, scc: S) -> &[S] {
  69         self.scc_data.successors(scc)
  70     }
  71 }
  72
  73 impl<S: Idx> SccData<S> {
  74     /// Number of SCCs,
  75     fn len(&self) -> usize {
  76         self.ranges.len()
  77     }
  78
  79     /// Returns the successors of the given SCC.
  80     fn successors(&self, scc: S) -> &[S] {
  81         // Annoyingly, `range` does not implement `Copy`, so we have
  82         // to do `range.start..range.end`:
  83         let range = &self.ranges[scc];
  84         &self.all_successors[range.start..range.end]
  85     }
  86
  87     /// Creates a new SCC with `successors` as its successors and
  88     /// returns the resulting index.
  89     fn create_scc(&mut self, successors: impl IntoIterator<Item = S>) -> S {
  90         // Store the successors on `scc_successors_vec`, remembering
  91         // the range of indices.
  92         let all_successors_start = self.all_successors.len();
  93         self.all_successors.extend(successors);
  94         let all_successors_end = self.all_successors.len();
  95
  96         debug!(
  97             "create_scc({:?}) successors={:?}",
  98             self.ranges.len(),
  99             &self.all_successors[all_successors_start..all_successors_end],
 100         );
 101
 102         self.ranges.push(all_successors_start..all_successors_end)
 103     }
 104 }
 105
 106 struct SccsConstruction<'c, G: DirectedGraph + WithNumNodes + WithSuccessors + 'c, S: Idx> {
 107     graph: &'c G,
 108
 109     /// The state of each node; used during walk to record the stack
 110     /// and after walk to record what cycle each node ended up being
 111     /// in.
 112     node_states: IndexVec<G::Node, NodeState<G::Node, S>>,
 113
 114     /// The stack of nodes that we are visiting as part of the DFS.
 115     node_stack: Vec<G::Node>,
 116
 117     /// The stack of successors: as we visit a node, we mark our
 118     /// position in this stack, and when we encounter a successor SCC,
 119     /// we push it on the stack. When we complete an SCC, we can pop
 120     /// everything off the stack that was found along the way.
 121     successors_stack: Vec<S>,
 122
 123     /// A set used to strip duplicates. As we accumulate successors
 124     /// into the successors_stack, we sometimes get duplicate entries.
 125     /// We use this set to remove those -- we also keep its storage
 126     /// around between successors to amortize memory allocation costs.
 127     duplicate_set: FxHashSet<S>,
 128
 129     scc_data: SccData<S>,
 130 }
 131
 132 #[derive(Copy, Clone, Debug)]
 133 enum NodeState<N, S> {
 134     /// This node has not yet been visited as part of the DFS.
 135     ///
 136     /// After SCC construction is complete, this state ought to be
 137     /// impossible.
 138     NotVisited,
 139
 140     /// This node is currently being walk as part of our DFS. It is on
 141     /// the stack at the depth `depth`.
 142     ///
 143     /// After SCC construction is complete, this state ought to be
 144     /// impossible.
 145     BeingVisited { depth: usize },
 146
 147     /// Indicates that this node is a member of the given cycle.
 148     InCycle { scc_index: S },
 149
 150     /// Indicates that this node is a member of whatever cycle
 151     /// `parent` is a member of. This state is transient: whenever we
 152     /// see it, we try to overwrite it with the current state of
 153     /// `parent` (this is the "path compression" step of a union-find
 154     /// algorithm).
 155     InCycleWith { parent: N },
 156 }
 157
 158 #[derive(Copy, Clone, Debug)]
 159 enum WalkReturn<S> {
 160     Cycle { min_depth: usize },
 161     Complete { scc_index: S },
 162 }
 163
 164 impl<'c, G, S> SccsConstruction<'c, G, S>
 165 where
 166     G: DirectedGraph + WithNumNodes + WithSuccessors,
 167     S: Idx,
 168 {
 169     /// Identifies SCCs in the graph `G` and computes the resulting
 170     /// DAG. This uses a variant of [Tarjan's
 171     /// algorithm][wikipedia]. The high-level summary of the algorithm
 172     /// is that we do a depth-first search. Along the way, we keep a
 173     /// stack of each node whose successors are being visited. We
 174     /// track the depth of each node on this stack (there is no depth
 175     /// if the node is not on the stack). When we find that some node
 176     /// N with depth D can reach some other node N' with lower depth
 177     /// D' (i.e., D' < D), we know that N, N', and all nodes in
 178     /// between them on the stack are part of an SCC.
 179     ///
 180     /// For each node, we track the lowest depth of any successor we
 181     /// have found, along with that
 182     ///
 183     /// [wikipedia]: https://bit.ly/2EZIx84
 184     fn construct(graph: &'c G) -> Sccs<G::Node, S> {
 185         let num_nodes = graph.num_nodes();
 186
 187         let mut this = Self {
 188             graph,
 189             node_states: IndexVec::from_elem_n(NodeState::NotVisited, num_nodes),
 190             node_stack: Vec::with_capacity(num_nodes),
 191             successors_stack: Vec::new(),
 192             scc_data: SccData {
 193                 ranges: IndexVec::new(),
 194                 all_successors: Vec::new(),
 195             },
 196             duplicate_set: FxHashSet::default(),
 197         };
 198
 199         let scc_indices = (0..num_nodes)
 200             .map(G::Node::new)
 201             .map(|node| match this.walk_node(0, node) {
 202                 WalkReturn::Complete { scc_index } => scc_index,
 203                 WalkReturn::Cycle { min_depth } => panic!(
 204                     "`walk_node(0, {:?})` returned cycle with depth {:?}",
 205                     node, min_depth
 206                 ),
 207             })
 208             .collect();
 209
 210         Sccs {
 211             scc_indices,
 212             scc_data: this.scc_data,
 213         }
 214     }
 215
 216     fn walk_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> {
 217         debug!("walk_node(depth = {:?}, node = {:?})", depth, node);
 218         match self.find_state(node) {
 219             NodeState::InCycle { scc_index } => WalkReturn::Complete { scc_index },
 220
 221             NodeState::BeingVisited { depth: min_depth } => WalkReturn::Cycle { min_depth },
 222
 223             NodeState::NotVisited => self.walk_unvisited_node(depth, node),
 224
 225             NodeState::InCycleWith { parent } => panic!(
 226                 "`find_state` returned `InCycleWith({:?})`, which ought to be impossible",
 227                 parent
 228             ),
 229         }
 230     }
 231
 232     /// Fetches the state of the node `r`. If `r` is recorded as being
 233     /// in a cycle with some other node `r2`, then fetches the state
 234     /// of `r2` (and updates `r` to reflect current result). This is
 235     /// basically the "find" part of a standard union-find algorithm
 236     /// (with path compression).
 237     fn find_state(&mut self, r: G::Node) -> NodeState<G::Node, S> {
 238         debug!("find_state(r = {:?} in state {:?})", r, self.node_states[r]);
 239         match self.node_states[r] {
 240             NodeState::InCycle { scc_index } => NodeState::InCycle { scc_index },
 241             NodeState::BeingVisited { depth } => NodeState::BeingVisited { depth },
 242             NodeState::NotVisited => NodeState::NotVisited,
 243             NodeState::InCycleWith { parent } => {
 244                 let parent_state = self.find_state(parent);
 245                 debug!("find_state: parent_state = {:?}", parent_state);
 246                 match parent_state {
 247                     NodeState::InCycle { .. } => {
 248                         self.node_states[r] = parent_state;
 249                         parent_state
 250                     }
 251
 252                     NodeState::BeingVisited { depth } => {
 253                         self.node_states[r] = NodeState::InCycleWith {
 254                             parent: self.node_stack[depth],
 255                         };
 256                         parent_state
 257                     }
 258
 259                     NodeState::NotVisited | NodeState::InCycleWith { .. } => {
 260                         panic!("invalid parent state: {:?}", parent_state)
 261                     }
 262                 }
 263             }
 264         }
 265     }
 266
 267     /// Walks a node that has never been visited before.
 268     fn walk_unvisited_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> {
 269         debug!(
 270             "walk_unvisited_node(depth = {:?}, node = {:?})",
 271             depth, node
 272         );
 273
 274         debug_assert!(match self.node_states[node] {
 275             NodeState::NotVisited => true,
 276             _ => false,
 277         });
 278
 279         self.node_states[node] = NodeState::BeingVisited { depth };
 280         self.node_stack.push(node);
 281
 282         // Walk each successor of the node, looking to see if any of
 283         // them can reach a node that is presently on the stack. If
 284         // so, that means they can also reach us.
 285         let mut min_depth = depth;
 286         let mut min_cycle_root = node;
 287         let successors_len = self.successors_stack.len();
 288         for successor_node in self.graph.successors(node) {
 289             debug!(
 290                 "walk_unvisited_node: node = {:?} successor_ode = {:?}",
 291                 node, successor_node
 292             );
 293             match self.walk_node(depth + 1, successor_node) {
 294                 WalkReturn::Cycle {
 295                     min_depth: successor_min_depth,
 296                 } => {
 297                     assert!(successor_min_depth <= depth);
 298                     if successor_min_depth < min_depth {
 299                         debug!(
 300                             "walk_unvisited_node: node = {:?} successor_min_depth = {:?}",
 301                             node, successor_min_depth
 302                         );
 303                         min_depth = successor_min_depth;
 304                         min_cycle_root = successor_node;
 305                     }
 306                 }
 307
 308                 WalkReturn::Complete {
 309                     scc_index: successor_scc_index,
 310                 } => {
 311                     debug!(
 312                         "walk_unvisited_node: node = {:?} successor_scc_index = {:?}",
 313                         node, successor_scc_index
 314                     );
 315                     self.successors_stack.push(successor_scc_index);
 316                 }
 317             }
 318         }
 319
 320         let r = self.node_stack.pop();
 321         debug_assert_eq!(r, Some(node));
 322
 323         if min_depth == depth {
 324             // Note that successor stack may have duplicates, so we
 325             // want to remove those:
 326             let deduplicated_successors = {
 327                 let duplicate_set = &mut self.duplicate_set;
 328                 duplicate_set.clear();
 329                 self.successors_stack
 330                     .drain(successors_len..)
 331                     .filter(move |&i| duplicate_set.insert(i))
 332             };
 333             let scc_index = self.scc_data.create_scc(deduplicated_successors);
 334             self.node_states[node] = NodeState::InCycle { scc_index };
 335             WalkReturn::Complete { scc_index }
 336         } else {
 337             // We are not the head of the cycle. Return back to our
 338             // caller.  They will take ownership of the
 339             // `self.successors` data that we pushed.
 340             self.node_states[node] = NodeState::InCycleWith {
 341                 parent: min_cycle_root,
 342             };
 343             WalkReturn::Cycle { min_depth }
 344         }
 345     }
 346 }