src/librustc_incremental/persist/preds/compress/classify/mod.rs

   1 // Copyright 2014 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 //! First phase. Detect cycles and cross-edges.
  12
  13 use super::*;
  14
  15 #[cfg(test)]
  16 mod test;
  17
  18 pub struct Classify<'a, 'g: 'a, N: 'g, I: 'a, O: 'a>
  19     where N: Debug + Clone + 'g,
  20           I: Fn(&N) -> bool,
  21           O: Fn(&N) -> bool,
  22 {
  23     r: &'a mut GraphReduce<'g, N, I, O>,
  24     stack: Vec<NodeIndex>,
  25     colors: Vec<Color>,
  26     dag: Dag,
  27 }
  28
  29 #[derive(Copy, Clone, Debug, PartialEq)]
  30 enum Color {
  31     // not yet visited
  32     White,
  33
  34     // visiting; usize is index on stack
  35     Grey(usize),
  36
  37     // finished visiting
  38     Black,
  39 }
  40
  41 impl<'a, 'g, N, I, O> Classify<'a, 'g, N, I, O>
  42     where N: Debug + Clone + 'g,
  43           I: Fn(&N) -> bool,
  44           O: Fn(&N) -> bool,
  45 {
  46     pub(super) fn new(r: &'a mut GraphReduce<'g, N, I, O>) -> Self {
  47         Classify {
  48             r: r,
  49             colors: vec![Color::White; r.in_graph.len_nodes()],
  50             stack: vec![],
  51             dag: Dag {
  52                 parents: (0..r.in_graph.len_nodes()).map(|i| NodeIndex(i)).collect(),
  53                 cross_edges: vec![],
  54                 input_nodes: vec![],
  55                 output_nodes: vec![],
  56             },
  57         }
  58     }
  59
  60     pub(super) fn walk(mut self) -> Dag {
  61         for (index, node) in self.r.in_graph.all_nodes().iter().enumerate() {
  62             if (self.r.is_output)(&node.data) {
  63                 let index = NodeIndex(index);
  64                 self.dag.output_nodes.push(index);
  65                 match self.colors[index.0] {
  66                     Color::White => self.open(index),
  67                     Color::Grey(_) => panic!("grey node but have not yet started a walk"),
  68                     Color::Black => (), // already visited, skip
  69                 }
  70             }
  71         }
  72
  73         // At this point we've identifed all the cycles, and we've
  74         // constructed a spanning tree over the original graph
  75         // (encoded in `self.parents`) as well as a list of
  76         // cross-edges that reflect additional edges from the DAG.
  77         //
  78         // If we converted each node to its `cycle-head` (a
  79         // representative choice from each SCC, basically) and then
  80         // take the union of `self.parents` and `self.cross_edges`
  81         // (after canonicalization), that is basically our DAG.
  82         //
  83         // Note that both of those may well contain trivial `X -rf-> X`
  84         // cycle edges after canonicalization, though. e.g., if you
  85         // have a graph `{A -rf-> B, B -rf-> A}`, we will have unioned A and
  86         // B, but A will also be B's parent (or vice versa), and hence
  87         // when we canonicalize the parent edge it would become `A -rf->
  88         // A` (or `B -rf-> B`).
  89         self.dag
  90     }
  91
  92     fn open(&mut self, node: NodeIndex) {
  93         let index = self.stack.len();
  94         self.stack.push(node);
  95         self.colors[node.0] = Color::Grey(index);
  96         for child in self.r.inputs(node) {
  97             self.walk_edge(node, child);
  98         }
  99         self.stack.pop().unwrap();
 100         self.colors[node.0] = Color::Black;
 101
 102         if (self.r.is_input)(&self.r.in_graph.node_data(node)) {
 103             // base inputs should have no inputs
 104             assert!(self.r.inputs(node).next().is_none());
 105             debug!("input: `{:?}`", self.r.in_graph.node_data(node));
 106             self.dag.input_nodes.push(node);
 107         }
 108     }
 109
 110     fn walk_edge(&mut self, parent: NodeIndex, child: NodeIndex) {
 111         debug!("walk_edge: {:?} -rf-> {:?}, {:?}",
 112                self.r.in_graph.node_data(parent),
 113                self.r.in_graph.node_data(child),
 114                self.colors[child.0]);
 115
 116         // Ignore self-edges, just in case they exist.
 117         if child == parent {
 118             return;
 119         }
 120
 121         match self.colors[child.0] {
 122             Color::White => {
 123                 // Not yet visited this node; start walking it.
 124                 assert_eq!(self.dag.parents[child.0], child);
 125                 self.dag.parents[child.0] = parent;
 126                 self.open(child);
 127             }
 128
 129             Color::Grey(stack_index) => {
 130                 // Back-edge; unify everything on stack between here and `stack_index`
 131                 // since we are all participating in a cycle
 132                 assert!(self.stack[stack_index] == child);
 133
 134                 for &n in &self.stack[stack_index..] {
 135                     debug!("cycle `{:?}` and `{:?}`",
 136                            self.r.in_graph.node_data(n),
 137                            self.r.in_graph.node_data(parent));
 138                     self.r.mark_cycle(n, parent);
 139                 }
 140             }
 141
 142             Color::Black => {
 143                 // Cross-edge, record and ignore
 144                 self.dag.cross_edges.push((parent, child));
 145                 debug!("cross-edge `{:?} -rf-> {:?}`",
 146                        self.r.in_graph.node_data(parent),
 147                        self.r.in_graph.node_data(child));
 148             }
 149         }
 150     }
 151 }