src/librustc/dep_graph/dep_tracking_map.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 hir::def_id::DefId;
  12 use rustc_data_structures::fx::FxHashMap;
  13 use std::cell::RefCell;
  14 use std::ops::Index;
  15 use std::hash::Hash;
  16 use std::marker::PhantomData;
  17 use util::common::MemoizationMap;
  18
  19 use super::{DepNode, DepGraph};
  20
  21 /// A DepTrackingMap offers a subset of the `Map` API and ensures that
  22 /// we make calls to `read` and `write` as appropriate. We key the
  23 /// maps with a unique type for brevity.
  24 pub struct DepTrackingMap<M: DepTrackingMapConfig> {
  25     phantom: PhantomData<M>,
  26     graph: DepGraph,
  27     map: FxHashMap<M::Key, M::Value>,
  28 }
  29
  30 pub trait DepTrackingMapConfig {
  31     type Key: Eq + Hash + Clone;
  32     type Value: Clone;
  33     fn to_dep_node(key: &Self::Key) -> DepNode<DefId>;
  34 }
  35
  36 impl<M: DepTrackingMapConfig> DepTrackingMap<M> {
  37     pub fn new(graph: DepGraph) -> DepTrackingMap<M> {
  38         DepTrackingMap {
  39             phantom: PhantomData,
  40             graph: graph,
  41             map: FxHashMap(),
  42         }
  43     }
  44
  45     /// Registers a (synthetic) read from the key `k`. Usually this
  46     /// is invoked automatically by `get`.
  47     fn read(&self, k: &M::Key) {
  48         let dep_node = M::to_dep_node(k);
  49         self.graph.read(dep_node);
  50     }
  51
  52     pub fn get(&self, k: &M::Key) -> Option<&M::Value> {
  53         self.read(k);
  54         self.map.get(k)
  55     }
  56
  57     pub fn contains_key(&self, k: &M::Key) -> bool {
  58         self.read(k);
  59         self.map.contains_key(k)
  60     }
  61
  62     pub fn keys(&self) -> Vec<M::Key> {
  63         self.map.keys().cloned().collect()
  64     }
  65 }
  66
  67 impl<M: DepTrackingMapConfig> MemoizationMap for RefCell<DepTrackingMap<M>> {
  68     type Key = M::Key;
  69     type Value = M::Value;
  70
  71     /// Memoizes an entry in the dep-tracking-map. If the entry is not
  72     /// already present, then `op` will be executed to compute its value.
  73     /// The resulting dependency graph looks like this:
  74     ///
  75     ///     [op] -> Map(key) -> CurrentTask
  76     ///
  77     /// Here, `[op]` represents whatever nodes `op` reads in the
  78     /// course of execution; `Map(key)` represents the node for this
  79     /// map; and `CurrentTask` represents the current task when
  80     /// `memoize` is invoked.
  81     ///
  82     /// **Important:* when `op` is invoked, the current task will be
  83     /// switched to `Map(key)`. Therefore, if `op` makes use of any
  84     /// HIR nodes or shared state accessed through its closure
  85     /// environment, it must explicitly register a read of that
  86     /// state. As an example, see `type_of_item` in `collect`,
  87     /// which looks something like this:
  88     ///
  89     /// ```
  90     /// fn type_of_item(..., item: &hir::Item) -> Ty<'tcx> {
  91     ///     let item_def_id = ccx.tcx.hir.local_def_id(it.id);
  92     ///     ccx.tcx.item_types.memoized(item_def_id, || {
  93     ///         ccx.tcx.dep_graph.read(DepNode::Hir(item_def_id)); // (*)
  94     ///         compute_type_of_item(ccx, item)
  95     ///     });
  96     /// }
  97     /// ```
  98     ///
  99     /// The key is the line marked `(*)`: the closure implicitly
 100     /// accesses the body of the item `item`, so we register a read
 101     /// from `Hir(item_def_id)`.
 102     fn memoize<OP>(&self, key: M::Key, op: OP) -> M::Value
 103         where OP: FnOnce() -> M::Value
 104     {
 105         let graph;
 106         {
 107             let this = self.borrow();
 108             if let Some(result) = this.map.get(&key) {
 109                 this.read(&key);
 110                 return result.clone();
 111             }
 112             graph = this.graph.clone();
 113         }
 114
 115         let _task = graph.in_task(M::to_dep_node(&key));
 116         let result = op();
 117         self.borrow_mut().map.insert(key, result.clone());
 118         result
 119     }
 120 }
 121
 122 impl<'k, M: DepTrackingMapConfig> Index<&'k M::Key> for DepTrackingMap<M> {
 123     type Output = M::Value;
 124
 125     #[inline]
 126     fn index(&self, k: &'k M::Key) -> &M::Value {
 127         self.get(k).unwrap()
 128     }
 129 }
 130