src/librustc_data_structures/control_flow_graph/iterate/mod.rs

   1 // Copyright 2016 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 use super::super::indexed_vec::IndexVec;
  12 use super::{DirectedGraph, WithSuccessors, WithNumNodes};
  13
  14 #[cfg(test)]
  15 mod test;
  16
  17 pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>(
  18     graph: &G,
  19     start_node: G::Node,
  20 ) -> Vec<G::Node> {
  21     post_order_from_to(graph, start_node, None)
  22 }
  23
  24 pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>(
  25     graph: &G,
  26     start_node: G::Node,
  27     end_node: Option<G::Node>,
  28 ) -> Vec<G::Node> {
  29     let mut visited: IndexVec<G::Node, bool> = IndexVec::from_elem_n(false, graph.num_nodes());
  30     let mut result: Vec<G::Node> = Vec::with_capacity(graph.num_nodes());
  31     if let Some(end_node) = end_node {
  32         visited[end_node] = true;
  33     }
  34     post_order_walk(graph, start_node, &mut result, &mut visited);
  35     result
  36 }
  37
  38 fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>(
  39     graph: &G,
  40     node: G::Node,
  41     result: &mut Vec<G::Node>,
  42     visited: &mut IndexVec<G::Node, bool>,
  43 ) {
  44     if visited[node] {
  45         return;
  46     }
  47     visited[node] = true;
  48
  49     for successor in graph.successors(node) {
  50         post_order_walk(graph, successor, result, visited);
  51     }
  52
  53     result.push(node);
  54 }
  55
  56 pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>(
  57     graph: &G,
  58     start_node: G::Node,
  59 ) -> Vec<G::Node> {
  60     let mut vec = post_order_from(graph, start_node);
  61     vec.reverse();
  62     vec
  63 }