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 rustc_data_structures::fx::{FxHashMap, FxHashSet};
  12 use std::env;
  13 use super::{DepGraphQuery, DepNode};
  14 use super::debug::EdgeFilter;
  15
  16 pub struct DepGraphEdges {
  17     nodes: Vec<DepNode>,
  18     indices: FxHashMap<DepNode, IdIndex>,
  19     edges: FxHashSet<(IdIndex, IdIndex)>,
  20     task_stack: Vec<OpenTask>,
  21     forbidden_edge: Option<EdgeFilter>,
  22 }
  23
  24 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  25 struct IdIndex {
  26     index: u32
  27 }
  28
  29 impl IdIndex {
  30     fn new(v: usize) -> IdIndex {
  31         assert!((v & 0xFFFF_FFFF) == v);
  32         IdIndex { index: v as u32 }
  33     }
  34
  35     fn index(self) -> usize {
  36         self.index as usize
  37     }
  38 }
  39
  40 #[derive(Clone, Debug, PartialEq)]
  41 enum OpenTask {
  42     Regular {
  43         node: DepNode,
  44         reads: Vec<DepNode>,
  45         read_set: FxHashSet<DepNode>,
  46     },
  47     Ignore,
  48 }
  49
  50 impl DepGraphEdges {
  51     pub fn new() -> DepGraphEdges {
  52         let forbidden_edge = if cfg!(debug_assertions) {
  53             match env::var("RUST_FORBID_DEP_GRAPH_EDGE") {
  54                 Ok(s) => {
  55                     match EdgeFilter::new(&s) {
  56                         Ok(f) => Some(f),
  57                         Err(err) => bug!("RUST_FORBID_DEP_GRAPH_EDGE invalid: {}", err),
  58                     }
  59                 }
  60                 Err(_) => None,
  61             }
  62         } else {
  63             None
  64         };
  65
  66         DepGraphEdges {
  67             nodes: vec![],
  68             indices: FxHashMap(),
  69             edges: FxHashSet(),
  70             task_stack: Vec::new(),
  71             forbidden_edge,
  72         }
  73     }
  74
  75     fn id(&self, index: IdIndex) -> DepNode {
  76         self.nodes[index.index()]
  77     }
  78
  79     pub fn push_ignore(&mut self) {
  80         self.task_stack.push(OpenTask::Ignore);
  81     }
  82
  83     pub fn pop_ignore(&mut self) {
  84         let popped_node = self.task_stack.pop().unwrap();
  85         debug_assert_eq!(popped_node, OpenTask::Ignore);
  86     }
  87
  88     pub fn push_task(&mut self, key: DepNode) {
  89         self.task_stack.push(OpenTask::Regular {
  90             node: key,
  91             reads: Vec::new(),
  92             read_set: FxHashSet(),
  93         });
  94     }
  95
  96     pub fn pop_task(&mut self, key: DepNode) {
  97         let popped_node = self.task_stack.pop().unwrap();
  98
  99         if let OpenTask::Regular {
 100             node,
 101             read_set: _,
 102             reads
 103         } = popped_node {
 104             debug_assert_eq!(node, key);
 105
 106             let target_id = self.get_or_create_node(node);
 107
 108             for read in reads.into_iter() {
 109                 let source_id = self.get_or_create_node(read);
 110                 self.edges.insert((source_id, target_id));
 111             }
 112         } else {
 113             bug!("pop_task() - Expected regular task to be popped")
 114         }
 115     }
 116
 117     /// Indicates that the current task `C` reads `v` by adding an
 118     /// edge from `v` to `C`. If there is no current task, has no
 119     /// effect. Note that *reading* from tracked state is harmless if
 120     /// you are not in a task; what is bad is *writing* to tracked
 121     /// state (and leaking data that you read into a tracked task).
 122     pub fn read(&mut self, source: DepNode) {
 123         match self.task_stack.last_mut() {
 124             Some(&mut OpenTask::Regular {
 125                 node: target,
 126                 ref mut reads,
 127                 ref mut read_set,
 128             }) => {
 129                 if read_set.insert(source) {
 130                     reads.push(source);
 131
 132                     if cfg!(debug_assertions) {
 133                         if let Some(ref forbidden_edge) = self.forbidden_edge {
 134                             if forbidden_edge.test(&source, &target) {
 135                                 bug!("forbidden edge {:?} -> {:?} created", source, target)
 136                             }
 137                         }
 138                     }
 139                 }
 140             }
 141             Some(&mut OpenTask::Ignore) | None => {
 142                 // ignore
 143             }
 144         }
 145     }
 146
 147     pub fn query(&self) -> DepGraphQuery {
 148         let edges: Vec<_> = self.edges.iter()
 149                                       .map(|&(i, j)| (self.id(i), self.id(j)))
 150                                       .collect();
 151         DepGraphQuery::new(&self.nodes, &edges)
 152     }
 153
 154     #[inline]
 155     pub fn add_edge(&mut self, source: DepNode, target: DepNode) {
 156         let source = self.get_or_create_node(source);
 157         let target = self.get_or_create_node(target);
 158         self.edges.insert((source, target));
 159     }
 160
 161     pub fn add_node(&mut self, node: DepNode) {
 162         self.get_or_create_node(node);
 163     }
 164
 165     #[inline]
 166     fn get_or_create_node(&mut self, dep_node: DepNode) -> IdIndex {
 167         let DepGraphEdges {
 168             ref mut indices,
 169             ref mut nodes,
 170             ..
 171         } = *self;
 172
 173         *indices.entry(dep_node).or_insert_with(|| {
 174             let next_id = nodes.len();
 175             nodes.push(dep_node);
 176             IdIndex::new(next_id)
 177         })
 178      }
 179 }