src/librustc/dep_graph/graph.rs

   1 // Copyright 2014 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;
  12 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
  13                                            StableHashingContextProvider};
  14 use session::config::OutputType;
  15 use std::cell::{Ref, RefCell};
  16 use std::rc::Rc;
  17 use util::common::{ProfileQueriesMsg, profq_msg};
  18
  19 use ich::Fingerprint;
  20
  21 use super::dep_node::{DepNode, DepKind, WorkProductId};
  22 use super::query::DepGraphQuery;
  23 use super::raii;
  24 use super::safe::DepGraphSafe;
  25 use super::edges::{DepGraphEdges, DepNodeIndex};
  26
  27 #[derive(Clone)]
  28 pub struct DepGraph {
  29     data: Option<Rc<DepGraphData>>,
  30
  31     // At the moment we are using DepNode as key here. In the future it might
  32     // be possible to use an IndexVec<DepNodeIndex, _> here. At the moment there
  33     // are a few problems with that:
  34     // - Some fingerprints are needed even if incr. comp. is disabled -- yet
  35     //   we need to have a dep-graph to generate DepNodeIndices.
  36     // - The architecture is still in flux and it's not clear what how to best
  37     //   implement things.
  38     fingerprints: Rc<RefCell<FxHashMap<DepNode, Fingerprint>>>
  39 }
  40
  41 struct DepGraphData {
  42     /// The actual graph data.
  43     edges: RefCell<DepGraphEdges>,
  44
  45     /// When we load, there may be `.o` files, cached mir, or other such
  46     /// things available to us. If we find that they are not dirty, we
  47     /// load the path to the file storing those work-products here into
  48     /// this map. We can later look for and extract that data.
  49     previous_work_products: RefCell<FxHashMap<WorkProductId, WorkProduct>>,
  50
  51     /// Work-products that we generate in this run.
  52     work_products: RefCell<FxHashMap<WorkProductId, WorkProduct>>,
  53
  54     dep_node_debug: RefCell<FxHashMap<DepNode, String>>,
  55 }
  56
  57 impl DepGraph {
  58     pub fn new(enabled: bool) -> DepGraph {
  59         DepGraph {
  60             data: if enabled {
  61                 Some(Rc::new(DepGraphData {
  62                     previous_work_products: RefCell::new(FxHashMap()),
  63                     work_products: RefCell::new(FxHashMap()),
  64                     edges: RefCell::new(DepGraphEdges::new()),
  65                     dep_node_debug: RefCell::new(FxHashMap()),
  66                 }))
  67             } else {
  68                 None
  69             },
  70             fingerprints: Rc::new(RefCell::new(FxHashMap())),
  71         }
  72     }
  73
  74     /// True if we are actually building the full dep-graph.
  75     #[inline]
  76     pub fn is_fully_enabled(&self) -> bool {
  77         self.data.is_some()
  78     }
  79
  80     pub fn query(&self) -> DepGraphQuery {
  81         self.data.as_ref().unwrap().edges.borrow().query()
  82     }
  83
  84     pub fn in_ignore<'graph>(&'graph self) -> Option<raii::IgnoreTask<'graph>> {
  85         self.data.as_ref().map(|data| raii::IgnoreTask::new(&data.edges))
  86     }
  87
  88     pub fn with_ignore<OP,R>(&self, op: OP) -> R
  89         where OP: FnOnce() -> R
  90     {
  91         let _task = self.in_ignore();
  92         op()
  93     }
  94
  95     /// Starts a new dep-graph task. Dep-graph tasks are specified
  96     /// using a free function (`task`) and **not** a closure -- this
  97     /// is intentional because we want to exercise tight control over
  98     /// what state they have access to. In particular, we want to
  99     /// prevent implicit 'leaks' of tracked state into the task (which
 100     /// could then be read without generating correct edges in the
 101     /// dep-graph -- see the [README] for more details on the
 102     /// dep-graph). To this end, the task function gets exactly two
 103     /// pieces of state: the context `cx` and an argument `arg`. Both
 104     /// of these bits of state must be of some type that implements
 105     /// `DepGraphSafe` and hence does not leak.
 106     ///
 107     /// The choice of two arguments is not fundamental. One argument
 108     /// would work just as well, since multiple values can be
 109     /// collected using tuples. However, using two arguments works out
 110     /// to be quite convenient, since it is common to need a context
 111     /// (`cx`) and some argument (e.g., a `DefId` identifying what
 112     /// item to process).
 113     ///
 114     /// For cases where you need some other number of arguments:
 115     ///
 116     /// - If you only need one argument, just use `()` for the `arg`
 117     ///   parameter.
 118     /// - If you need 3+ arguments, use a tuple for the
 119     ///   `arg` parameter.
 120     ///
 121     /// [README]: README.md
 122     pub fn with_task<C, A, R, HCX>(&self,
 123                                    key: DepNode,
 124                                    cx: C,
 125                                    arg: A,
 126                                    task: fn(C, A) -> R)
 127                                    -> (R, DepNodeIndex)
 128         where C: DepGraphSafe + StableHashingContextProvider<ContextType=HCX>,
 129               R: HashStable<HCX>,
 130     {
 131         if let Some(ref data) = self.data {
 132             data.edges.borrow_mut().push_task(key);
 133             if cfg!(debug_assertions) {
 134                 profq_msg(ProfileQueriesMsg::TaskBegin(key.clone()))
 135             };
 136
 137             // In incremental mode, hash the result of the task. We don't
 138             // do anything with the hash yet, but we are computing it
 139             // anyway so that
 140             //  - we make sure that the infrastructure works and
 141             //  - we can get an idea of the runtime cost.
 142             let mut hcx = cx.create_stable_hashing_context();
 143
 144             let result = task(cx, arg);
 145             if cfg!(debug_assertions) {
 146                 profq_msg(ProfileQueriesMsg::TaskEnd)
 147             };
 148             let dep_node_index = data.edges.borrow_mut().pop_task(key);
 149
 150             let mut stable_hasher = StableHasher::new();
 151             result.hash_stable(&mut hcx, &mut stable_hasher);
 152
 153             assert!(self.fingerprints
 154                         .borrow_mut()
 155                         .insert(key, stable_hasher.finish())
 156                         .is_none());
 157
 158             (result, dep_node_index)
 159         } else {
 160             if key.kind.fingerprint_needed_for_crate_hash() {
 161                 let mut hcx = cx.create_stable_hashing_context();
 162                 let result = task(cx, arg);
 163                 let mut stable_hasher = StableHasher::new();
 164                 result.hash_stable(&mut hcx, &mut stable_hasher);
 165                 assert!(self.fingerprints
 166                             .borrow_mut()
 167                             .insert(key, stable_hasher.finish())
 168                             .is_none());
 169                 (result, DepNodeIndex::INVALID)
 170             } else {
 171                 (task(cx, arg), DepNodeIndex::INVALID)
 172             }
 173         }
 174     }
 175
 176     /// Execute something within an "anonymous" task, that is, a task the
 177     /// DepNode of which is determined by the list of inputs it read from.
 178     pub fn with_anon_task<OP,R>(&self, dep_kind: DepKind, op: OP) -> (R, DepNodeIndex)
 179         where OP: FnOnce() -> R
 180     {
 181         if let Some(ref data) = self.data {
 182             data.edges.borrow_mut().push_anon_task();
 183             let result = op();
 184             let dep_node = data.edges.borrow_mut().pop_anon_task(dep_kind);
 185             (result, dep_node)
 186         } else {
 187             (op(), DepNodeIndex::INVALID)
 188         }
 189     }
 190
 191     #[inline]
 192     pub fn read(&self, v: DepNode) {
 193         if let Some(ref data) = self.data {
 194             data.edges.borrow_mut().read(v);
 195         }
 196     }
 197
 198     #[inline]
 199     pub fn read_index(&self, v: DepNodeIndex) {
 200         if let Some(ref data) = self.data {
 201             data.edges.borrow_mut().read_index(v);
 202         }
 203     }
 204
 205     /// Only to be used during graph loading
 206     #[inline]
 207     pub fn add_edge_directly(&self, source: DepNode, target: DepNode) {
 208         self.data.as_ref().unwrap().edges.borrow_mut().add_edge(source, target);
 209     }
 210
 211     /// Only to be used during graph loading
 212     pub fn add_node_directly(&self, node: DepNode) {
 213         self.data.as_ref().unwrap().edges.borrow_mut().add_node(node);
 214     }
 215
 216     pub fn alloc_input_node(&self, node: DepNode) -> DepNodeIndex {
 217         if let Some(ref data) = self.data {
 218             data.edges.borrow_mut().add_node(node)
 219         } else {
 220             DepNodeIndex::INVALID
 221         }
 222     }
 223
 224     pub fn fingerprint_of(&self, dep_node: &DepNode) -> Option<Fingerprint> {
 225         self.fingerprints.borrow().get(dep_node).cloned()
 226     }
 227
 228     /// Indicates that a previous work product exists for `v`. This is
 229     /// invoked during initial start-up based on what nodes are clean
 230     /// (and what files exist in the incr. directory).
 231     pub fn insert_previous_work_product(&self, v: &WorkProductId, data: WorkProduct) {
 232         debug!("insert_previous_work_product({:?}, {:?})", v, data);
 233         self.data
 234             .as_ref()
 235             .unwrap()
 236             .previous_work_products
 237             .borrow_mut()
 238             .insert(v.clone(), data);
 239     }
 240
 241     /// Indicates that we created the given work-product in this run
 242     /// for `v`. This record will be preserved and loaded in the next
 243     /// run.
 244     pub fn insert_work_product(&self, v: &WorkProductId, data: WorkProduct) {
 245         debug!("insert_work_product({:?}, {:?})", v, data);
 246         self.data
 247             .as_ref()
 248             .unwrap()
 249             .work_products
 250             .borrow_mut()
 251             .insert(v.clone(), data);
 252     }
 253
 254     /// Check whether a previous work product exists for `v` and, if
 255     /// so, return the path that leads to it. Used to skip doing work.
 256     pub fn previous_work_product(&self, v: &WorkProductId) -> Option<WorkProduct> {
 257         self.data
 258             .as_ref()
 259             .and_then(|data| {
 260                 data.previous_work_products.borrow().get(v).cloned()
 261             })
 262     }
 263
 264     /// Access the map of work-products created during this run. Only
 265     /// used during saving of the dep-graph.
 266     pub fn work_products(&self) -> Ref<FxHashMap<WorkProductId, WorkProduct>> {
 267         self.data.as_ref().unwrap().work_products.borrow()
 268     }
 269
 270     /// Access the map of work-products created during the cached run. Only
 271     /// used during saving of the dep-graph.
 272     pub fn previous_work_products(&self) -> Ref<FxHashMap<WorkProductId, WorkProduct>> {
 273         self.data.as_ref().unwrap().previous_work_products.borrow()
 274     }
 275
 276     #[inline(always)]
 277     pub fn register_dep_node_debug_str<F>(&self,
 278                                           dep_node: DepNode,
 279                                           debug_str_gen: F)
 280         where F: FnOnce() -> String
 281     {
 282         let dep_node_debug = &self.data.as_ref().unwrap().dep_node_debug;
 283
 284         if dep_node_debug.borrow().contains_key(&dep_node) {
 285             return
 286         }
 287         let debug_str = debug_str_gen();
 288         dep_node_debug.borrow_mut().insert(dep_node, debug_str);
 289     }
 290
 291     pub(super) fn dep_node_debug_str(&self, dep_node: DepNode) -> Option<String> {
 292         self.data.as_ref().and_then(|t| t.dep_node_debug.borrow().get(&dep_node).cloned())
 293     }
 294 }
 295
 296 /// A "work product" is an intermediate result that we save into the
 297 /// incremental directory for later re-use. The primary example are
 298 /// the object files that we save for each partition at code
 299 /// generation time.
 300 ///
 301 /// Each work product is associated with a dep-node, representing the
 302 /// process that produced the work-product. If that dep-node is found
 303 /// to be dirty when we load up, then we will delete the work-product
 304 /// at load time. If the work-product is found to be clean, then we
 305 /// will keep a record in the `previous_work_products` list.
 306 ///
 307 /// In addition, work products have an associated hash. This hash is
 308 /// an extra hash that can be used to decide if the work-product from
 309 /// a previous compilation can be re-used (in addition to the dirty
 310 /// edges check).
 311 ///
 312 /// As the primary example, consider the object files we generate for
 313 /// each partition. In the first run, we create partitions based on
 314 /// the symbols that need to be compiled. For each partition P, we
 315 /// hash the symbols in P and create a `WorkProduct` record associated
 316 /// with `DepNode::TransPartition(P)`; the hash is the set of symbols
 317 /// in P.
 318 ///
 319 /// The next time we compile, if the `DepNode::TransPartition(P)` is
 320 /// judged to be clean (which means none of the things we read to
 321 /// generate the partition were found to be dirty), it will be loaded
 322 /// into previous work products. We will then regenerate the set of
 323 /// symbols in the partition P and hash them (note that new symbols
 324 /// may be added -- for example, new monomorphizations -- even if
 325 /// nothing in P changed!). We will compare that hash against the
 326 /// previous hash. If it matches up, we can reuse the object file.
 327 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 328 pub struct WorkProduct {
 329     pub cgu_name: String,
 330     /// Extra hash used to decide if work-product is still suitable;
 331     /// note that this is *not* a hash of the work-product itself.
 332     /// See documentation on `WorkProduct` type for an example.
 333     pub input_hash: u64,
 334
 335     /// Saved files associated with this CGU
 336     pub saved_files: Vec<(OutputType, String)>,
 337 }