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