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 super::{DepGraphQuery, DepNode};
  13
  14 pub struct DepGraphEdges {
  15     nodes: Vec<DepNode>,
  16     indices: FxHashMap<DepNode, IdIndex>,
  17     edges: FxHashSet<(IdIndex, IdIndex)>,
  18     open_nodes: Vec<OpenNode>,
  19 }
  20
  21 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  22 struct IdIndex {
  23     index: u32
  24 }
  25
  26 impl IdIndex {
  27     fn new(v: usize) -> IdIndex {
  28         assert!((v & 0xFFFF_FFFF) == v);
  29         IdIndex { index: v as u32 }
  30     }
  31
  32     fn index(self) -> usize {
  33         self.index as usize
  34     }
  35 }
  36
  37 #[derive(Clone, Debug, PartialEq)]
  38 enum OpenNode {
  39     Node(IdIndex),
  40     Ignore,
  41 }
  42
  43 impl DepGraphEdges {
  44     pub fn new() -> DepGraphEdges {
  45         DepGraphEdges {
  46             nodes: vec![],
  47             indices: FxHashMap(),
  48             edges: FxHashSet(),
  49             open_nodes: Vec::new()
  50         }
  51     }
  52
  53     fn id(&self, index: IdIndex) -> DepNode {
  54         self.nodes[index.index()].clone()
  55     }
  56
  57     /// Creates a node for `id` in the graph.
  58     fn make_node(&mut self, id: DepNode) -> IdIndex {
  59         if let Some(&i) = self.indices.get(&id) {
  60             return i;
  61         }
  62
  63         let index = IdIndex::new(self.nodes.len());
  64         self.nodes.push(id.clone());
  65         self.indices.insert(id, index);
  66         index
  67     }
  68
  69     /// Top of the stack of open nodes.
  70     fn current_node(&self) -> Option<OpenNode> {
  71         self.open_nodes.last().cloned()
  72     }
  73
  74     pub fn push_ignore(&mut self) {
  75         self.open_nodes.push(OpenNode::Ignore);
  76     }
  77
  78     pub fn pop_ignore(&mut self) {
  79         let popped_node = self.open_nodes.pop().unwrap();
  80         assert_eq!(popped_node, OpenNode::Ignore);
  81     }
  82
  83     pub fn push_task(&mut self, key: DepNode) {
  84         let top_node = self.current_node();
  85
  86         let new_node = self.make_node(key);
  87         self.open_nodes.push(OpenNode::Node(new_node));
  88
  89         // if we are in the midst of doing task T, then this new task
  90         // N is a subtask of T, so add an edge N -> T.
  91         if let Some(top_node) = top_node {
  92             self.add_edge_from_open_node(top_node, |t| (new_node, t));
  93         }
  94     }
  95
  96     pub fn pop_task(&mut self, key: DepNode) {
  97         let popped_node = self.open_nodes.pop().unwrap();
  98         assert_eq!(OpenNode::Node(self.indices[&key]), popped_node);
  99     }
 100
 101     /// Indicates that the current task `C` reads `v` by adding an
 102     /// edge from `v` to `C`. If there is no current task, has no
 103     /// effect. Note that *reading* from tracked state is harmless if
 104     /// you are not in a task; what is bad is *writing* to tracked
 105     /// state (and leaking data that you read into a tracked task).
 106     pub fn read(&mut self, v: DepNode) {
 107         if self.current_node().is_some() {
 108             let source = self.make_node(v);
 109             self.add_edge_from_current_node(|current| (source, current))
 110         }
 111     }
 112
 113     /// Indicates that the current task `C` writes `v` by adding an
 114     /// edge from `C` to `v`. If there is no current task, panics. If
 115     /// you want to suppress this edge, use `ignore`.
 116     pub fn write(&mut self, v: DepNode) {
 117         let target = self.make_node(v);
 118         self.add_edge_from_current_node(|current| (current, target))
 119     }
 120
 121     /// Invoke `add_edge_from_open_node` with the top of the stack, or
 122     /// panic if stack is empty.
 123     fn add_edge_from_current_node<OP>(&mut self,
 124                                       op: OP)
 125         where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex)
 126     {
 127         match self.current_node() {
 128             Some(open_node) => self.add_edge_from_open_node(open_node, op),
 129             None => bug!("no current node, cannot add edge into dependency graph")
 130         }
 131     }
 132
 133     /// Adds an edge to or from the `open_node`, assuming `open_node`
 134     /// is not `Ignore`. The direction of the edge is determined by
 135     /// the closure `op` --- we pass as argument the open node `n`,
 136     /// and the closure returns a (source, target) tuple, which should
 137     /// include `n` in one spot or another.
 138     fn add_edge_from_open_node<OP>(&mut self,
 139                                    open_node: OpenNode,
 140                                    op: OP)
 141         where OP: FnOnce(IdIndex) -> (IdIndex, IdIndex)
 142     {
 143         let (source, target) = match open_node {
 144             OpenNode::Node(n) => op(n),
 145             OpenNode::Ignore => { return; }
 146         };
 147
 148         // ignore trivial self edges, which are not very interesting
 149         if source == target {
 150             return;
 151         }
 152
 153         if self.edges.insert((source, target)) {
 154             debug!("adding edge from {:?} to {:?}",
 155                    self.id(source),
 156                    self.id(target));
 157         }
 158     }
 159
 160     pub fn query(&self) -> DepGraphQuery {
 161         let edges: Vec<_> = self.edges.iter()
 162                                       .map(|&(i, j)| (self.id(i), self.id(j)))
 163                                       .collect();
 164         DepGraphQuery::new(&self.nodes, &edges)
 165     }
 166 }