Auto merge of #43184 - nikomatsakis:incr-comp-anonymize-trait-selection, r=michaelwoerister

integrate anon dep nodes into trait selection

Use anonymous nodes for trait selection. In all cases, we use the same basic "memoization" strategy:

- Store the `DepNodeIndex` in the slot along with value.
- If value is present, return it, and add a read of the dep-node-index.
- Else, start an anonymous task, and store resulting node.

We apply this strategy to a number of caches in trait selection:

- The "trans" caches of selection and projection
- The "evaluation" cache
- The "candidate selection" cache

In general, for our cache strategy to be "dep-correct", the computation of the value is permitted to rely on the *value in the key* but nothing else. The basic argument is this: in order to look something up, you have to produce the key, and to do that you must have whatever reads were needed to create the key. Then, you get whatever reads were further needed to produce the value. But if the "closure" that produced the value made use of *other* environmental data, not derivable from the key, that would be bad -- but that would **also** suggest that the cache is messed up (though it's not proof).

The structure of these caches do not obviously prove that the correctness criteria are met, and I aim to address that in further refactorings. But I *believe* it to be the case that, if we assume that the existing caches are correct, there are also no dependency failures (in other words, if there's a bug, it's a pre-existing one). Specifically:

- The trans caches: these take as input just a `tcx`, which is "by definition" not leaky, the `trait-ref` etc, which is part of the key, and sometimes a span (doesn't influence the result). So they seem fine.
- The evaluation cache:
    - This computation takes as input the "stack" and has access to the infcx.
    - The infcx is a problem -- would be better to take the tcx -- and this is exactly one of the things I plan to improve in later PRs. Let's ignore it for now. =)
    - The stack itself is also not great, in that the *key* only consists of the top-entry in the stack.
    - However, the stack can cause a problem in two ways:
        - overflow (we panic)
        - cycle check fails (we do not update the cache, I believe)
- The candidate selection cache:
    - as before, takes the "stack" and has access to the infcx.
    - here it is not as obvious that we avoid caching stack-dependent computations. However, to the extent that we do, this is a pre-existing bug, in that we are making cache entries we shouldn't.
    - I aim to resolve this by -- following the chalk-style of evaluation -- merging candidate selection and evaluation.
    - The infcx is a problem -- would be better to take the tcx -- and this is exactly one of the things I plan to improve in later PRs. Let's ignore it for now. =)
    - The stack itself is also not great, in that the *key* only consists of the top-entry in the stack.
    - Moreover, the stack would generally just introduce ambiguities and errors anyhow, so that lessens the risk.

Anyway, the existing approach to handle dependencies in the trait code carries the same risks or worse, so this seems like a strict improvement!

r? @michaelwoerister

cc @arielb1

6 files changed, 83 insertions, 120 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index c6275e84645..8e2c44a427b 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -495,7 +495,7 @@ define_dep_nodes!( <'tcx>
     // imprecision in our dep-graph tracking.  The important thing is
     // that for any given trait-ref, we always map to the **same**
     // trait-select node.
-    [] TraitSelect { trait_def_id: DefId, input_def_id: DefId },
+    [anon] TraitSelect,
 
     // For proj. cache, we just keep a list of all def-ids, since it is
     // not a hotspot.
diff --git a/src/librustc/dep_graph/dep_tracking_map.rs b/src/librustc/dep_graph/dep_tracking_map.rs
index ca53fd7a433..2d19b34c504 100644
--- a/src/librustc/dep_graph/dep_tracking_map.rs
+++ b/src/librustc/dep_graph/dep_tracking_map.rs
@@ -12,10 +12,9 @@ use rustc_data_structures::fx::FxHashMap;
 use std::cell::RefCell;
 use std::hash::Hash;
 use std::marker::PhantomData;
-use ty::TyCtxt;
 use util::common::MemoizationMap;
 
-use super::{DepNode, DepGraph};
+use super::{DepKind, DepNodeIndex, DepGraph};
 
 /// A DepTrackingMap offers a subset of the `Map` API and ensures that
 /// we make calls to `read` and `write` as appropriate. We key the
@@ -23,13 +22,13 @@ use super::{DepNode, DepGraph};
 pub struct DepTrackingMap<M: DepTrackingMapConfig> {
     phantom: PhantomData<M>,
     graph: DepGraph,
-    map: FxHashMap<M::Key, M::Value>,
+    map: FxHashMap<M::Key, (M::Value, DepNodeIndex)>,
 }
 
 pub trait DepTrackingMapConfig {
     type Key: Eq + Hash + Clone;
     type Value: Clone;
-    fn to_dep_node(tcx: TyCtxt, key: &Self::Key) -> DepNode;
+    fn to_dep_kind() -> DepKind;
 }
 
 impl<M: DepTrackingMapConfig> DepTrackingMap<M> {
@@ -40,27 +39,6 @@ impl<M: DepTrackingMapConfig> DepTrackingMap<M> {
             map: FxHashMap(),
         }
     }
-
-    /// Registers a (synthetic) read from the key `k`. Usually this
-    /// is invoked automatically by `get`.
-    fn read(&self, tcx: TyCtxt, k: &M::Key) {
-        let dep_node = M::to_dep_node(tcx, k);
-        self.graph.read(dep_node);
-    }
-
-    pub fn get(&self, tcx: TyCtxt, k: &M::Key) -> Option<&M::Value> {
-        self.read(tcx, k);
-        self.map.get(k)
-    }
-
-    pub fn contains_key(&self, tcx: TyCtxt, k: &M::Key) -> bool {
-        self.read(tcx, k);
-        self.map.contains_key(k)
-    }
-
-    pub fn keys(&self) -> Vec<M::Key> {
-        self.map.keys().cloned().collect()
-    }
 }
 
 impl<M: DepTrackingMapConfig> MemoizationMap for RefCell<DepTrackingMap<M>> {
@@ -98,22 +76,22 @@ impl<M: DepTrackingMapConfig> MemoizationMap for RefCell<DepTrackingMap<M>> {
     /// The key is the line marked `(*)`: the closure implicitly
     /// accesses the body of the item `item`, so we register a read
     /// from `Hir(item_def_id)`.
-    fn memoize<OP>(&self, tcx: TyCtxt, key: M::Key, op: OP) -> M::Value
+    fn memoize<OP>(&self, key: M::Key, op: OP) -> M::Value
         where OP: FnOnce() -> M::Value
     {
         let graph;
         {
             let this = self.borrow();
-            if let Some(result) = this.map.get(&key) {
-                this.read(tcx, &key);
+            if let Some(&(ref result, dep_node)) = this.map.get(&key) {
+                this.graph.read_index(dep_node);
                 return result.clone();
             }
             graph = this.graph.clone();
         }
 
-        let _task = graph.in_task(M::to_dep_node(tcx, &key));
-        let result = op();
-        self.borrow_mut().map.insert(key, result.clone());
+        let (result, dep_node) = graph.with_anon_task(M::to_dep_kind(), op);
+        self.borrow_mut().map.insert(key, (result.clone(), dep_node));
+        graph.read_index(dep_node);
         result
     }
 }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 79da04df1df..c690bebed8c 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -30,6 +30,7 @@ use super::{VtableImplData, VtableObjectData, VtableBuiltinData,
             VtableClosureData, VtableDefaultImplData, VtableFnPointerData};
 use super::util;
 
+use dep_graph::{DepNodeIndex, DepKind};
 use hir::def_id::DefId;
 use infer;
 use infer::{InferCtxt, InferOk, TypeFreshener};
@@ -105,7 +106,7 @@ struct TraitObligationStack<'prev, 'tcx: 'prev> {
 #[derive(Clone)]
 pub struct SelectionCache<'tcx> {
     hashmap: RefCell<FxHashMap<ty::TraitRef<'tcx>,
-                               SelectionResult<'tcx, SelectionCandidate<'tcx>>>>,
+                               WithDepNode<SelectionResult<'tcx, SelectionCandidate<'tcx>>>>>,
 }
 
 /// The selection process begins by considering all impls, where
@@ -369,7 +370,7 @@ impl EvaluationResult {
 
 #[derive(Clone)]
 pub struct EvaluationCache<'tcx> {
-    hashmap: RefCell<FxHashMap<ty::PolyTraitRef<'tcx>, EvaluationResult>>
+    hashmap: RefCell<FxHashMap<ty::PolyTraitRef<'tcx>, WithDepNode<EvaluationResult>>>
 }
 
 impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
@@ -466,8 +467,6 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         assert!(!obligation.predicate.has_escaping_regions());
 
         let tcx = self.tcx();
-        let dep_node = obligation.predicate.dep_node(tcx);
-        let _task = tcx.dep_graph.in_task(dep_node);
 
         let stack = self.push_stack(TraitObligationStackList::empty(), obligation);
         let ret = match self.candidate_from_obligation(&stack)? {
@@ -710,12 +709,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             return result;
         }
 
-        let result = self.evaluate_stack(&stack);
+        let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack));
 
         debug!("CACHE MISS: EVAL({:?})={:?}",
                fresh_trait_ref,
                result);
-        self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, result);
+        self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result);
 
         result
     }
@@ -870,22 +869,23 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                               trait_ref: ty::PolyTraitRef<'tcx>)
                               -> Option<EvaluationResult>
     {
+        let tcx = self.tcx();
         if self.can_use_global_caches(param_env) {
-            let cache = self.tcx().evaluation_cache.hashmap.borrow();
+            let cache = tcx.evaluation_cache.hashmap.borrow();
             if let Some(cached) = cache.get(&trait_ref) {
-                let dep_node = trait_ref
-                    .to_poly_trait_predicate()
-                    .dep_node(self.tcx());
-                self.tcx().hir.dep_graph.read(dep_node);
-                return Some(cached.clone());
+                return Some(cached.get(tcx));
             }
         }
-        self.infcx.evaluation_cache.hashmap.borrow().get(&trait_ref).cloned()
+        self.infcx.evaluation_cache.hashmap
+                                   .borrow()
+                                   .get(&trait_ref)
+                                   .map(|v| v.get(tcx))
     }
 
     fn insert_evaluation_cache(&mut self,
                                param_env: ty::ParamEnv<'tcx>,
                                trait_ref: ty::PolyTraitRef<'tcx>,
+                               dep_node: DepNodeIndex,
                                result: EvaluationResult)
     {
         // Avoid caching results that depend on more than just the trait-ref:
@@ -902,12 +902,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         if self.can_use_global_caches(param_env) {
             let mut cache = self.tcx().evaluation_cache.hashmap.borrow_mut();
             if let Some(trait_ref) = self.tcx().lift_to_global(&trait_ref) {
-                cache.insert(trait_ref, result);
+                cache.insert(trait_ref, WithDepNode::new(dep_node, result));
                 return;
             }
         }
 
-        self.infcx.evaluation_cache.hashmap.borrow_mut().insert(trait_ref, result);
+        self.infcx.evaluation_cache.hashmap
+                                   .borrow_mut()
+                                   .insert(trait_ref, WithDepNode::new(dep_node, result));
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -949,19 +951,32 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
 
         // If no match, compute result and insert into cache.
-        let candidate = self.candidate_from_obligation_no_cache(stack);
+        let (candidate, dep_node) = self.in_task(|this| {
+            this.candidate_from_obligation_no_cache(stack)
+        });
 
         if self.should_update_candidate_cache(&cache_fresh_trait_pred, &candidate) {
             debug!("CACHE MISS: SELECT({:?})={:?}",
                    cache_fresh_trait_pred, candidate);
             self.insert_candidate_cache(stack.obligation.param_env,
                                         cache_fresh_trait_pred,
+                                        dep_node,
                                         candidate.clone());
         }
 
         candidate
     }
 
+    fn in_task<OP, R>(&mut self, op: OP) -> (R, DepNodeIndex)
+        where OP: FnOnce(&mut Self) -> R
+    {
+        let (result, dep_node) = self.tcx().dep_graph.with_anon_task(DepKind::TraitSelect, || {
+            op(self)
+        });
+        self.tcx().dep_graph.read_index(dep_node);
+        (result, dep_node)
+    }
+
     // Treat negative impls as unimplemented
     fn filter_negative_impls(&self, candidate: SelectionCandidate<'tcx>)
                              -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
@@ -1151,33 +1166,41 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                              cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>)
                              -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>>
     {
+        let tcx = self.tcx();
         let trait_ref = &cache_fresh_trait_pred.0.trait_ref;
         if self.can_use_global_caches(param_env) {
-            let cache = self.tcx().selection_cache.hashmap.borrow();
+            let cache = tcx.selection_cache.hashmap.borrow();
             if let Some(cached) = cache.get(&trait_ref) {
-                return Some(cached.clone());
+                return Some(cached.get(tcx));
             }
         }
-        self.infcx.selection_cache.hashmap.borrow().get(trait_ref).cloned()
+        self.infcx.selection_cache.hashmap
+                                  .borrow()
+                                  .get(trait_ref)
+                                  .map(|v| v.get(tcx))
     }
 
     fn insert_candidate_cache(&mut self,
                               param_env: ty::ParamEnv<'tcx>,
                               cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
+                              dep_node: DepNodeIndex,
                               candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>)
     {
+        let tcx = self.tcx();
         let trait_ref = cache_fresh_trait_pred.0.trait_ref;
         if self.can_use_global_caches(param_env) {
-            let mut cache = self.tcx().selection_cache.hashmap.borrow_mut();
-            if let Some(trait_ref) = self.tcx().lift_to_global(&trait_ref) {
-                if let Some(candidate) = self.tcx().lift_to_global(&candidate) {
-                    cache.insert(trait_ref, candidate);
+            let mut cache = tcx.selection_cache.hashmap.borrow_mut();
+            if let Some(trait_ref) = tcx.lift_to_global(&trait_ref) {
+                if let Some(candidate) = tcx.lift_to_global(&candidate) {
+                    cache.insert(trait_ref, WithDepNode::new(dep_node, candidate));
                     return;
                 }
             }
         }
 
-        self.infcx.selection_cache.hashmap.borrow_mut().insert(trait_ref, candidate);
+        self.infcx.selection_cache.hashmap
+                                  .borrow_mut()
+                                  .insert(trait_ref, WithDepNode::new(dep_node, candidate));
     }
 
     fn should_update_candidate_cache(&mut self,
@@ -3138,3 +3161,20 @@ impl<'o,'tcx> fmt::Debug for TraitObligationStack<'o,'tcx> {
         write!(f, "TraitObligationStack({:?})", self.obligation)
     }
 }
+
+#[derive(Clone)]
+pub struct WithDepNode<T> {
+    dep_node: DepNodeIndex,
+    cached_value: T
+}
+
+impl<T: Clone> WithDepNode<T> {
+    pub fn new(dep_node: DepNodeIndex, cached_value: T) -> Self {
+        WithDepNode { dep_node, cached_value }
+    }
+
+    pub fn get(&self, tcx: TyCtxt) -> T {
+        tcx.dep_graph.read_index(self.dep_node);
+        self.cached_value.clone()
+    }
+}
diff --git a/src/librustc/traits/trans/mod.rs b/src/librustc/traits/trans/mod.rs
index 9c6047b28b5..827a5092c00 100644
--- a/src/librustc/traits/trans/mod.rs
+++ b/src/librustc/traits/trans/mod.rs
@@ -13,9 +13,7 @@
 // seems likely that they should eventually be merged into more
 // general routines.
 
-use dep_graph::{DepGraph, DepNode, DepTrackingMap, DepTrackingMapConfig,
-                DepConstructor};
-use hir::def_id::DefId;
+use dep_graph::{DepGraph, DepKind, DepTrackingMap, DepTrackingMapConfig};
 use infer::TransNormalize;
 use std::cell::RefCell;
 use std::marker::PhantomData;
@@ -41,7 +39,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
         // Remove any references to regions; this helps improve caching.
         let trait_ref = self.erase_regions(&trait_ref);
 
-        self.trans_trait_caches.trait_cache.memoize(self, trait_ref, || {
+        self.trans_trait_caches.trait_cache.memoize(trait_ref, || {
             debug!("trans::fulfill_obligation(trait_ref={:?}, def_id={:?})",
                    trait_ref, trait_ref.def_id());
 
@@ -139,7 +137,7 @@ impl<'a, 'gcx> TypeFolder<'gcx, 'gcx> for AssociatedTypeNormalizer<'a, 'gcx> {
         if !ty.has_projection_types() {
             ty
         } else {
-            self.tcx.trans_trait_caches.project_cache.memoize(self.tcx, ty, || {
+            self.tcx.trans_trait_caches.project_cache.memoize(ty, || {
                 debug!("AssociatedTypeNormalizer: ty={:?}", ty);
                 self.tcx.normalize_associated_type(&ty)
             })
@@ -171,8 +169,8 @@ pub struct TraitSelectionCache<'tcx> {
 impl<'tcx> DepTrackingMapConfig for TraitSelectionCache<'tcx> {
     type Key = ty::PolyTraitRef<'tcx>;
     type Value = Vtable<'tcx, ()>;
-    fn to_dep_node(tcx: TyCtxt, key: &ty::PolyTraitRef<'tcx>) -> DepNode {
-        key.to_poly_trait_predicate().dep_node(tcx)
+    fn to_dep_kind() -> DepKind {
+        DepKind::TraitSelect
     }
 }
 
@@ -185,31 +183,8 @@ pub struct ProjectionCache<'gcx> {
 impl<'gcx> DepTrackingMapConfig for ProjectionCache<'gcx> {
     type Key = Ty<'gcx>;
     type Value = Ty<'gcx>;
-    fn to_dep_node(tcx: TyCtxt, key: &Self::Key) -> DepNode {
-        // Ideally, we'd just put `key` into the dep-node, but we
-        // can't put full types in there. So just collect up all the
-        // def-ids of structs/enums as well as any traits that we
-        // project out of. It doesn't matter so much what we do here,
-        // except that if we are too coarse, we'll create overly
-        // coarse edges between impls and the trans. For example, if
-        // we just used the def-id of things we are projecting out of,
-        // then the key for `<Foo as SomeTrait>::T` and `<Bar as
-        // SomeTrait>::T` would both share a dep-node
-        // (`TraitSelect(SomeTrait)`), and hence the impls for both
-        // `Foo` and `Bar` would be considered inputs. So a change to
-        // `Bar` would affect things that just normalized `Foo`.
-        // Anyway, this heuristic is not ideal, but better than
-        // nothing.
-        let def_ids: Vec<DefId> =
-            key.walk()
-               .filter_map(|t| match t.sty {
-                    ty::TyAdt(adt_def, _) => Some(adt_def.did),
-                    ty::TyProjection(ref proj) => Some(proj.item_def_id),
-                    _ => None,
-               })
-               .collect();
-
-        DepNode::new(tcx, DepConstructor::ProjectionCache { def_ids: def_ids })
+    fn to_dep_kind() -> DepKind {
+        DepKind::TraitSelect
     }
 }
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 3f1302e72e9..5aaba526e26 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -15,7 +15,6 @@ pub use self::IntVarValue::*;
 pub use self::LvaluePreference::*;
 pub use self::fold::TypeFoldable;
 
-use dep_graph::{DepNode, DepConstructor};
 use hir::{map as hir_map, FreevarMap, TraitMap};
 use hir::def::{Def, CtorKind, ExportMap};
 use hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
@@ -947,28 +946,6 @@ impl<'tcx> TraitPredicate<'tcx> {
         self.trait_ref.def_id
     }
 
-    /// Creates the dep-node for selecting/evaluating this trait reference.
-    fn dep_node(&self, tcx: TyCtxt) -> DepNode {
-        // Extact the trait-def and first def-id from inputs.  See the
-        // docs for `DepNode::TraitSelect` for more information.
-        let trait_def_id = self.def_id();
-        let input_def_id =
-            self.input_types()
-                .flat_map(|t| t.walk())
-                .filter_map(|t| match t.sty {
-                    ty::TyAdt(adt_def, ..) => Some(adt_def.did),
-                    ty::TyClosure(def_id, ..) => Some(def_id),
-                    ty::TyFnDef(def_id, ..) => Some(def_id),
-                    _ => None
-                })
-                .next()
-                .unwrap_or(trait_def_id);
-        DepNode::new(tcx, DepConstructor::TraitSelect {
-            trait_def_id,
-            input_def_id,
-        })
-    }
-
     pub fn input_types<'a>(&'a self) -> impl DoubleEndedIterator<Item=Ty<'tcx>> + 'a {
         self.trait_ref.input_types()
     }
@@ -983,11 +960,6 @@ impl<'tcx> PolyTraitPredicate<'tcx> {
         // ok to skip binder since trait def-id does not care about regions
         self.0.def_id()
     }
-
-    pub fn dep_node(&self, tcx: TyCtxt) -> DepNode {
-        // ok to skip binder since depnode does not care about regions
-        self.0.dep_node(tcx)
-    }
 }
 
 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index 40ee3cd28f5..17564671a1e 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -19,8 +19,6 @@ use std::iter::repeat;
 use std::path::Path;
 use std::time::{Duration, Instant};
 
-use ty::TyCtxt;
-
 // The name of the associated type for `Fn` return types
 pub const FN_OUTPUT_NAME: &'static str = "Output";
 
@@ -211,7 +209,7 @@ pub trait MemoizationMap {
     /// needed in the `op` to ensure that the correct edges are
     /// added into the dep graph. See the `DepTrackingMap` impl for
     /// more details!
-    fn memoize<OP>(&self, tcx: TyCtxt, key: Self::Key, op: OP) -> Self::Value
+    fn memoize<OP>(&self, key: Self::Key, op: OP) -> Self::Value
         where OP: FnOnce() -> Self::Value;
 }
 
@@ -221,7 +219,7 @@ impl<K, V, S> MemoizationMap for RefCell<HashMap<K,V,S>>
     type Key = K;
     type Value = V;
 
-    fn memoize<OP>(&self, _tcx: TyCtxt, key: K, op: OP) -> V
+    fn memoize<OP>(&self, key: K, op: OP) -> V
         where OP: FnOnce() -> V
     {
         let result = self.borrow().get(&key).cloned();