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