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