Auto merge of #66821 - eddyb:global-trait-caching, r=nikomatsakis

rustc: allow non-empty ParamEnv's in global trait select/eval caches.

*Based on #66963*

This appears to alleviate the symptoms of #65510 locally (without fixing WF directly), and is potentially easier to validate as sound (since it's a more ad-hoc version of queries we already have).

I'm opening this PR primarily to test the effects on perf.

r? @nikomatsakis cc @rust-lang/wg-traits

4 files changed, 36 insertions, 26 deletions

diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index c345b9a969c..1fdec5f0152 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -1079,12 +1079,10 @@ fn assemble_candidates_from_impls<'cx, 'tcx>(
                 if !is_default {
                     true
                 } else if obligation.param_env.reveal == Reveal::All {
-                    debug_assert!(!poly_trait_ref.needs_infer());
-                    if !poly_trait_ref.needs_subst() {
-                        true
-                    } else {
-                        false
-                    }
+                    // NOTE(eddyb) inference variables can resolve to parameters, so
+                    // assume `poly_trait_ref` isn't monomorphic, if it contains any.
+                    let poly_trait_ref = selcx.infcx().resolve_vars_if_possible(&poly_trait_ref);
+                    !poly_trait_ref.needs_infer() && !poly_trait_ref.needs_subst()
                 } else {
                     false
                 }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 5f324527a27..94a77c553e5 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -204,7 +204,10 @@ struct TraitObligationStack<'prev, 'tcx> {
 #[derive(Clone, Default)]
 pub struct SelectionCache<'tcx> {
     hashmap: Lock<
-        FxHashMap<ty::TraitRef<'tcx>, WithDepNode<SelectionResult<'tcx, SelectionCandidate<'tcx>>>>,
+        FxHashMap<
+            ty::ParamEnvAnd<'tcx, ty::TraitRef<'tcx>>,
+            WithDepNode<SelectionResult<'tcx, SelectionCandidate<'tcx>>>,
+        >,
     >,
 }
 
@@ -490,7 +493,9 @@ impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
 
 #[derive(Clone, Default)]
 pub struct EvaluationCache<'tcx> {
-    hashmap: Lock<FxHashMap<ty::PolyTraitRef<'tcx>, WithDepNode<EvaluationResult>>>,
+    hashmap: Lock<
+        FxHashMap<ty::ParamEnvAnd<'tcx, ty::PolyTraitRef<'tcx>>, WithDepNode<EvaluationResult>>,
+    >,
 }
 
 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
@@ -1143,7 +1148,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let tcx = self.tcx();
         if self.can_use_global_caches(param_env) {
             let cache = tcx.evaluation_cache.hashmap.borrow();
-            if let Some(cached) = cache.get(&trait_ref) {
+            if let Some(cached) = cache.get(&param_env.and(trait_ref)) {
                 return Some(cached.get(tcx));
             }
         }
@@ -1151,7 +1156,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             .evaluation_cache
             .hashmap
             .borrow()
-            .get(&trait_ref)
+            .get(&param_env.and(trait_ref))
             .map(|v| v.get(tcx))
     }
 
@@ -1182,7 +1187,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     .evaluation_cache
                     .hashmap
                     .borrow_mut()
-                    .insert(trait_ref, WithDepNode::new(dep_node, result));
+                    .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, result));
                 return;
             }
         }
@@ -1195,7 +1200,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             .evaluation_cache
             .hashmap
             .borrow_mut()
-            .insert(trait_ref, WithDepNode::new(dep_node, result));
+            .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, result));
     }
 
     /// For various reasons, it's possible for a subobligation
@@ -1567,14 +1572,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// Do note that if the type itself is not in the
     /// global tcx, the local caches will be used.
     fn can_use_global_caches(&self, param_env: ty::ParamEnv<'tcx>) -> bool {
-        // If there are any where-clauses in scope, then we always use
-        // a cache local to this particular scope. Otherwise, we
-        // switch to a global cache. We used to try and draw
-        // finer-grained distinctions, but that led to a serious of
-        // annoying and weird bugs like #22019 and #18290. This simple
-        // rule seems to be pretty clearly safe and also still retains
-        // a very high hit rate (~95% when compiling rustc).
-        if !param_env.caller_bounds.is_empty() {
+        // If there are any e.g. inference variables in the `ParamEnv`, then we
+        // always use a cache local to this particular scope. Otherwise, we
+        // switch to a global cache.
+        if param_env.has_local_value() {
             return false;
         }
 
@@ -1602,7 +1603,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let trait_ref = &cache_fresh_trait_pred.skip_binder().trait_ref;
         if self.can_use_global_caches(param_env) {
             let cache = tcx.selection_cache.hashmap.borrow();
-            if let Some(cached) = cache.get(&trait_ref) {
+            if let Some(cached) = cache.get(&param_env.and(*trait_ref)) {
                 return Some(cached.get(tcx));
             }
         }
@@ -1610,7 +1611,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             .selection_cache
             .hashmap
             .borrow()
-            .get(trait_ref)
+            .get(&param_env.and(*trait_ref))
             .map(|v| v.get(tcx))
     }
 
@@ -1671,7 +1672,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     tcx.selection_cache
                         .hashmap
                         .borrow_mut()
-                        .insert(trait_ref, WithDepNode::new(dep_node, candidate));
+                        .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, candidate));
                     return;
                 }
             }
@@ -1685,7 +1686,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             .selection_cache
             .hashmap
             .borrow_mut()
-            .insert(trait_ref, WithDepNode::new(dep_node, candidate));
+            .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, candidate));
     }
 
     fn assemble_candidates<'o>(
diff --git a/src/test/ui/type-alias-impl-trait/bound_reduction2.rs b/src/test/ui/type-alias-impl-trait/bound_reduction2.rs
index 919446877a1..1becb1e83a5 100644
--- a/src/test/ui/type-alias-impl-trait/bound_reduction2.rs
+++ b/src/test/ui/type-alias-impl-trait/bound_reduction2.rs
@@ -9,6 +9,7 @@ trait TraitWithAssoc {
 
 type Foo<V> = impl Trait<V>;
 //~^ ERROR could not find defining uses
+//~| ERROR the trait bound `T: TraitWithAssoc` is not satisfied
 
 trait Trait<U> {}
 
diff --git a/src/test/ui/type-alias-impl-trait/bound_reduction2.stderr b/src/test/ui/type-alias-impl-trait/bound_reduction2.stderr
index bb22d582f21..1eb4cf2a802 100644
--- a/src/test/ui/type-alias-impl-trait/bound_reduction2.stderr
+++ b/src/test/ui/type-alias-impl-trait/bound_reduction2.stderr
@@ -1,5 +1,14 @@
+error[E0277]: the trait bound `T: TraitWithAssoc` is not satisfied
+  --> $DIR/bound_reduction2.rs:10:1
+   |
+LL | type Foo<V> = impl Trait<V>;
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `TraitWithAssoc` is not implemented for `T`
+...
+LL | fn foo_desugared<T: TraitWithAssoc>(_: T) -> Foo<T::Assoc> {
+   |                  -- help: consider further restricting this bound: `T: TraitWithAssoc +`
+
 error: defining opaque type use does not fully define opaque type: generic parameter `V` is specified as concrete type `<T as TraitWithAssoc>::Assoc`
-  --> $DIR/bound_reduction2.rs:17:1
+  --> $DIR/bound_reduction2.rs:18:1
    |
 LL | / fn foo_desugared<T: TraitWithAssoc>(_: T) -> Foo<T::Assoc> {
 LL | |     ()
@@ -12,5 +21,6 @@ error: could not find defining uses
 LL | type Foo<V> = impl Trait<V>;
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-error: aborting due to 2 previous errors
+error: aborting due to 3 previous errors
 
+For more information about this error, try `rustc --explain E0277`.