src/librustc/dep_graph/edges.rs

   1 // Copyright 2012-2015 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 ich::Fingerprint;
  12 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  13 use rustc_data_structures::stable_hasher::StableHasher;
  14 use std::env;
  15 use std::hash::Hash;
  16 use std::mem;
  17 use super::{DepGraphQuery, DepKind, DepNode};
  18 use super::debug::EdgeFilter;
  19
  20 pub struct DepGraphEdges {
  21     nodes: Vec<DepNode>,
  22     indices: FxHashMap<DepNode, DepNodeIndex>,
  23     edges: FxHashSet<(DepNodeIndex, DepNodeIndex)>,
  24     task_stack: Vec<OpenTask>,
  25     forbidden_edge: Option<EdgeFilter>,
  26 }
  27
  28 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  29 pub struct DepNodeIndex {
  30     index: u32
  31 }
  32
  33 impl DepNodeIndex {
  34
  35     pub const INVALID: DepNodeIndex = DepNodeIndex { index: ::std::u32::MAX };
  36
  37     fn new(v: usize) -> DepNodeIndex {
  38         assert!((v & 0xFFFF_FFFF) == v);
  39         DepNodeIndex { index: v as u32 }
  40     }
  41
  42     fn index(self) -> usize {
  43         self.index as usize
  44     }
  45 }
  46
  47 #[derive(Clone, Debug, PartialEq)]
  48 enum OpenTask {
  49     Regular {
  50         node: DepNode,
  51         reads: Vec<DepNode>,
  52         read_set: FxHashSet<DepNode>,
  53     },
  54     Anon {
  55         reads: Vec<DepNode>,
  56         read_set: FxHashSet<DepNode>,
  57     },
  58     Ignore,
  59 }
  60
  61 impl DepGraphEdges {
  62     pub fn new() -> DepGraphEdges {
  63         let forbidden_edge = if cfg!(debug_assertions) {
  64             match env::var("RUST_FORBID_DEP_GRAPH_EDGE") {
  65                 Ok(s) => {
  66                     match EdgeFilter::new(&s) {
  67                         Ok(f) => Some(f),
  68                         Err(err) => bug!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err),
  69                     }
  70                 }
  71                 Err(_) => None,
  72             }
  73         } else {
  74             None
  75         };
  76
  77         DepGraphEdges {
  78             nodes: vec![],
  79             indices: FxHashMap(),
  80             edges: FxHashSet(),
  81             task_stack: Vec::new(),
  82             forbidden_edge,
  83         }
  84     }
  85
  86     fn id(&self, index: DepNodeIndex) -> DepNode {
  87         self.nodes[index.index()]
  88     }
  89
  90     pub fn push_ignore(&mut self) {
  91         self.task_stack.push(OpenTask::Ignore);
  92     }
  93
  94     pub fn pop_ignore(&mut self) {
  95         let popped_node = self.task_stack.pop().unwrap();
  96         debug_assert_eq!(popped_node, OpenTask::Ignore);
  97     }
  98
  99     pub fn push_task(&mut self, key: DepNode) {
 100         self.task_stack.push(OpenTask::Regular {
 101             node: key,
 102             reads: Vec::new(),
 103             read_set: FxHashSet(),
 104         });
 105     }
 106
 107     pub fn pop_task(&mut self, key: DepNode) -> DepNodeIndex {
 108         let popped_node = self.task_stack.pop().unwrap();
 109
 110         if let OpenTask::Regular {
 111             node,
 112             read_set: _,
 113             reads
 114         } = popped_node {
 115             debug_assert_eq!(node, key);
 116
 117             let target_id = self.get_or_create_node(node);
 118
 119             for read in reads.into_iter() {
 120                 let source_id = self.get_or_create_node(read);
 121                 self.edges.insert((source_id, target_id));
 122             }
 123
 124             target_id
 125         } else {
 126             bug!("pop_task() - Expected regular task to be popped")
 127         }
 128     }
 129
 130     pub fn push_anon_task(&mut self) {
 131         self.task_stack.push(OpenTask::Anon {
 132             reads: Vec::new(),
 133             read_set: FxHashSet(),
 134         });
 135     }
 136
 137     pub fn pop_anon_task(&mut self, kind: DepKind) -> DepNodeIndex {
 138         let popped_node = self.task_stack.pop().unwrap();
 139
 140         if let OpenTask::Anon {
 141             read_set: _,
 142             reads
 143         } = popped_node {
 144             let mut fingerprint = Fingerprint::zero();
 145             let mut hasher = StableHasher::new();
 146
 147             for read in reads.iter() {
 148                 mem::discriminant(&read.kind).hash(&mut hasher);
 149
 150                 // Fingerprint::combine() is faster than sending Fingerprint
 151                 // through the StableHasher (at least as long as StableHasher
 152                 // is so slow).
 153                 fingerprint = fingerprint.combine(read.hash);
 154             }
 155
 156             fingerprint = fingerprint.combine(hasher.finish());
 157
 158             let target_dep_node = DepNode {
 159                 kind,
 160                 hash: fingerprint,
 161             };
 162
 163             if let Some(&index) = self.indices.get(&target_dep_node) {
 164                 return index;
 165             }
 166
 167             let target_id = self.get_or_create_node(target_dep_node);
 168
 169             for read in reads.into_iter() {
 170                 let source_id = self.get_or_create_node(read);
 171                 self.edges.insert((source_id, target_id));
 172             }
 173
 174             target_id
 175         } else {
 176             bug!("pop_anon_task() - Expected anonymous task to be popped")
 177         }
 178     }
 179
 180     /// Indicates that the current task `C` reads `v` by adding an
 181     /// edge from `v` to `C`. If there is no current task, has no
 182     /// effect. Note that *reading* from tracked state is harmless if
 183     /// you are not in a task; what is bad is *writing* to tracked
 184     /// state (and leaking data that you read into a tracked task).
 185     pub fn read(&mut self, source: DepNode) {
 186         match self.task_stack.last_mut() {
 187             Some(&mut OpenTask::Regular {
 188                 node: target,
 189                 ref mut reads,
 190                 ref mut read_set,
 191             }) => {
 192                 if read_set.insert(source) {
 193                     reads.push(source);
 194
 195                     if cfg!(debug_assertions) {
 196                         if let Some(ref forbidden_edge) = self.forbidden_edge {
 197                             if forbidden_edge.test(&source, &target) {
 198                                 bug!("forbidden edge {:?} -> {:?} created", source, target)
 199                             }
 200                         }
 201                     }
 202                 }
 203             }
 204             Some(&mut OpenTask::Anon {
 205                 ref mut reads,
 206                 ref mut read_set,
 207             }) => {
 208                 if read_set.insert(source) {
 209                     reads.push(source);
 210                 }
 211             }
 212             Some(&mut OpenTask::Ignore) | None => {
 213                 // ignore
 214             }
 215         }
 216     }
 217
 218     pub fn read_index(&mut self, source: DepNodeIndex) {
 219         let dep_node = self.nodes[source.index()];
 220         self.read(dep_node);
 221     }
 222
 223     pub fn query(&self) -> DepGraphQuery {
 224         let edges: Vec<_> = self.edges.iter()
 225                                       .map(|&(i, j)| (self.id(i), self.id(j)))
 226                                       .collect();
 227         DepGraphQuery::new(&self.nodes, &edges)
 228     }
 229
 230     #[inline]
 231     pub fn add_edge(&mut self, source: DepNode, target: DepNode) {
 232         let source = self.get_or_create_node(source);
 233         let target = self.get_or_create_node(target);
 234         self.edges.insert((source, target));
 235     }
 236
 237     pub fn add_node(&mut self, node: DepNode) {
 238         self.get_or_create_node(node);
 239     }
 240
 241     #[inline]
 242     fn get_or_create_node(&mut self, dep_node: DepNode) -> DepNodeIndex {
 243         let DepGraphEdges {
 244             ref mut indices,
 245             ref mut nodes,
 246             ..
 247         } = *self;
 248
 249         *indices.entry(dep_node).or_insert_with(|| {
 250             let next_id = nodes.len();
 251             nodes.push(dep_node);
 252             DepNodeIndex::new(next_id)
 253         })
 254      }
 255 }