Auto merge of #85186 - nikomatsakis:issue-83538-polluted-cache, r=jackh726

have on_completion record subcycles

have on_completion record subcycles

Rework `on_completion` method so that it removes all
provisional cache entries that are "below" a completed
node (while leaving those entries that are not below
the node).

This corrects an imprecise result that could in turn lead
to an incremental compilation failure. Under the old
scheme, if you had:

* A depends on...
   * B depends on A
   * C depends on...
       * D depends on C
 * T: 'static

then the provisional results for A, B, C, and D would all
be entangled. Thus, if A was `EvaluatedToOkModuloRegions`
(because of that final condition), then the result for C and
D would also be demoted to "ok modulo regions".

In reality, though, the result for C depends only on C and itself,
and is not dependent on regions. If we happen to evaluate the
cycle starting from C, we would never reach A, and hence the
result would be "ok".

Under the new scheme, the provisional results for C and D
are moved to the permanent cache immediately and are not affected
by the result of A.

Fixes #83538

r? `@Aaron1011`

9 files changed, 260 insertions, 51 deletions

diff --git a/compiler/rustc_feature/src/builtin_attrs.rs b/compiler/rustc_feature/src/builtin_attrs.rs
index 24b53bcf82a..51d69167f7b 100644
--- a/compiler/rustc_feature/src/builtin_attrs.rs
+++ b/compiler/rustc_feature/src/builtin_attrs.rs
@@ -564,6 +564,7 @@ pub const BUILTIN_ATTRIBUTES: &[BuiltinAttribute] = &[
         template!(Word, List: "delay_span_bug_from_inside_query")
     ),
     rustc_attr!(TEST, rustc_dump_user_substs, AssumedUsed, template!(Word)),
+    rustc_attr!(TEST, rustc_evaluate_where_clauses, AssumedUsed, template!(Word)),
     rustc_attr!(TEST, rustc_if_this_changed, AssumedUsed, template!(Word, List: "DepNode")),
     rustc_attr!(TEST, rustc_then_this_would_need, AssumedUsed, template!(List: "DepNode")),
     rustc_attr!(
diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs
index ab8537b088c..0b3dece09ae 100644
--- a/compiler/rustc_span/src/symbol.rs
+++ b/compiler/rustc_span/src/symbol.rs
@@ -1011,6 +1011,7 @@ symbols! {
         rustc_dump_program_clauses,
         rustc_dump_user_substs,
         rustc_error,
+        rustc_evaluate_where_clauses,
         rustc_expected_cgu_reuse,
         rustc_if_this_changed,
         rustc_inherit_overflow_checks,
diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs
index 4097e1577e1..bf3c8643f0d 100644
--- a/compiler/rustc_trait_selection/src/lib.rs
+++ b/compiler/rustc_trait_selection/src/lib.rs
@@ -14,6 +14,7 @@
 #![feature(bool_to_option)]
 #![feature(box_patterns)]
 #![feature(drain_filter)]
+#![feature(hash_drain_filter)]
 #![feature(in_band_lifetimes)]
 #![feature(iter_zip)]
 #![feature(never_type)]
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 08d452900c8..a292de148a6 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -636,8 +636,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         if let Some(result) = stack.cache().get_provisional(fresh_trait_ref) {
             debug!(?result, "PROVISIONAL CACHE HIT");
-            stack.update_reached_depth(stack.cache().current_reached_depth());
-            return Ok(result);
+            stack.update_reached_depth(result.reached_depth);
+            return Ok(result.result);
         }
 
         // Check if this is a match for something already on the
@@ -661,7 +661,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             debug!(?result, "CACHE MISS");
             self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result);
 
-            stack.cache().on_completion(stack.depth, |fresh_trait_ref, provisional_result| {
+            stack.cache().on_completion(stack.dfn, |fresh_trait_ref, provisional_result| {
                 self.insert_evaluation_cache(
                     obligation.param_env,
                     fresh_trait_ref,
@@ -2162,7 +2162,7 @@ impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> {
     /// required accessing something from the stack at depth `reached_depth`.
     fn update_reached_depth(&self, reached_depth: usize) {
         assert!(
-            self.depth > reached_depth,
+            self.depth >= reached_depth,
             "invoked `update_reached_depth` with something under this stack: \
              self.depth={} reached_depth={}",
             self.depth,
@@ -2235,23 +2235,6 @@ struct ProvisionalEvaluationCache<'tcx> {
     /// next "depth first number" to issue -- just a counter
     dfn: Cell<usize>,
 
-    /// Stores the "coldest" depth (bottom of stack) reached by any of
-    /// the evaluation entries. The idea here is that all things in the provisional
-    /// cache are always dependent on *something* that is colder in the stack:
-    /// therefore, if we add a new entry that is dependent on something *colder still*,
-    /// we have to modify the depth for all entries at once.
-    ///
-    /// Example:
-    ///
-    /// Imagine we have a stack `A B C D E` (with `E` being the top of
-    /// the stack).  We cache something with depth 2, which means that
-    /// it was dependent on C.  Then we pop E but go on and process a
-    /// new node F: A B C D F.  Now F adds something to the cache with
-    /// depth 1, meaning it is dependent on B.  Our original cache
-    /// entry is also dependent on B, because there is a path from E
-    /// to C and then from C to F and from F to B.
-    reached_depth: Cell<usize>,
-
     /// Map from cache key to the provisionally evaluated thing.
     /// The cache entries contain the result but also the DFN in which they
     /// were added. The DFN is used to clear out values on failure.
@@ -2275,12 +2258,13 @@ struct ProvisionalEvaluationCache<'tcx> {
 #[derive(Copy, Clone, Debug)]
 struct ProvisionalEvaluation {
     from_dfn: usize,
+    reached_depth: usize,
     result: EvaluationResult,
 }
 
 impl<'tcx> Default for ProvisionalEvaluationCache<'tcx> {
     fn default() -> Self {
-        Self { dfn: Cell::new(0), reached_depth: Cell::new(usize::MAX), map: Default::default() }
+        Self { dfn: Cell::new(0), map: Default::default() }
     }
 }
 
@@ -2295,22 +2279,17 @@ impl<'tcx> ProvisionalEvaluationCache<'tcx> {
     /// Check the provisional cache for any result for
     /// `fresh_trait_ref`. If there is a hit, then you must consider
     /// it an access to the stack slots at depth
-    /// `self.current_reached_depth()` and above.
-    fn get_provisional(&self, fresh_trait_ref: ty::PolyTraitRef<'tcx>) -> Option<EvaluationResult> {
+    /// `reached_depth` (from the returned value).
+    fn get_provisional(
+        &self,
+        fresh_trait_ref: ty::PolyTraitRef<'tcx>,
+    ) -> Option<ProvisionalEvaluation> {
         debug!(
             ?fresh_trait_ref,
-            reached_depth = ?self.reached_depth.get(),
             "get_provisional = {:#?}",
             self.map.borrow().get(&fresh_trait_ref),
         );
-        Some(self.map.borrow().get(&fresh_trait_ref)?.result)
-    }
-
-    /// Current value of the `reached_depth` counter -- all the
-    /// provisional cache entries are dependent on the item at this
-    /// depth.
-    fn current_reached_depth(&self) -> usize {
-        self.reached_depth.get()
+        Some(self.map.borrow().get(&fresh_trait_ref)?.clone())
     }
 
     /// Insert a provisional result into the cache. The result came
@@ -2324,13 +2303,31 @@ impl<'tcx> ProvisionalEvaluationCache<'tcx> {
         fresh_trait_ref: ty::PolyTraitRef<'tcx>,
         result: EvaluationResult,
     ) {
-        debug!(?from_dfn, ?reached_depth, ?fresh_trait_ref, ?result, "insert_provisional");
-        let r_d = self.reached_depth.get();
-        self.reached_depth.set(r_d.min(reached_depth));
+        debug!(?from_dfn, ?fresh_trait_ref, ?result, "insert_provisional");
 
-        debug!(reached_depth = self.reached_depth.get());
+        let mut map = self.map.borrow_mut();
+
+        // Subtle: when we complete working on the DFN `from_dfn`, anything
+        // that remains in the provisional cache must be dependent on some older
+        // stack entry than `from_dfn`. We have to update their depth with our transitive
+        // depth in that case or else it would be referring to some popped note.
+        //
+        // Example:
+        // A (reached depth 0)
+        //   ...
+        //      B // depth 1 -- reached depth = 0
+        //          C // depth 2 -- reached depth = 1 (should be 0)
+        //              B
+        //          A // depth 0
+        //   D (reached depth 1)
+        //      C (cache -- reached depth = 2)
+        for (_k, v) in &mut *map {
+            if v.from_dfn >= from_dfn {
+                v.reached_depth = reached_depth.min(v.reached_depth);
+            }
+        }
 
-        self.map.borrow_mut().insert(fresh_trait_ref, ProvisionalEvaluation { from_dfn, result });
+        map.insert(fresh_trait_ref, ProvisionalEvaluation { from_dfn, reached_depth, result });
     }
 
     /// Invoked when the node with dfn `dfn` does not get a successful
@@ -2358,25 +2355,40 @@ impl<'tcx> ProvisionalEvaluationCache<'tcx> {
     /// was a failure, then `on_failure` should have been invoked
     /// already). The callback `op` will be invoked for each
     /// provisional entry that we can now confirm.
+    ///
+    /// Note that we may still have provisional cache items remaining
+    /// in the cache when this is done. For example, if there is a
+    /// cycle:
+    ///
+    /// * A depends on...
+    ///     * B depends on A
+    ///     * C depends on...
+    ///         * D depends on C
+    ///     * ...
+    ///
+    /// Then as we complete the C node we will have a provisional cache
+    /// with results for A, B, C, and D. This method would clear out
+    /// the C and D results, but leave A and B provisional.
+    ///
+    /// This is determined based on the DFN: we remove any provisional
+    /// results created since `dfn` started (e.g., in our example, dfn
+    /// would be 2, representing the C node, and hence we would
+    /// remove the result for D, which has DFN 3, but not the results for
+    /// A and B, which have DFNs 0 and 1 respectively).
     fn on_completion(
         &self,
-        depth: usize,
+        dfn: usize,
         mut op: impl FnMut(ty::PolyTraitRef<'tcx>, EvaluationResult),
     ) {
-        debug!(?depth, reached_depth = ?self.reached_depth.get(), "on_completion");
+        debug!(?dfn, "on_completion");
 
-        if self.reached_depth.get() < depth {
-            debug!("on_completion: did not yet reach depth to complete");
-            return;
-        }
-
-        for (fresh_trait_ref, eval) in self.map.borrow_mut().drain() {
+        for (fresh_trait_ref, eval) in
+            self.map.borrow_mut().drain_filter(|_k, eval| eval.from_dfn >= dfn)
+        {
             debug!(?fresh_trait_ref, ?eval, "on_completion");
 
             op(fresh_trait_ref, eval.result);
         }
-
-        self.reached_depth.set(usize::MAX);
     }
 }
 
diff --git a/compiler/rustc_typeck/src/check/callee.rs b/compiler/rustc_typeck/src/check/callee.rs
index b48102e0fc9..cb8f336721a 100644
--- a/compiler/rustc_typeck/src/check/callee.rs
+++ b/compiler/rustc_typeck/src/check/callee.rs
@@ -6,8 +6,14 @@ use rustc_errors::{struct_span_err, Applicability, DiagnosticBuilder};
 use rustc_hir as hir;
 use rustc_hir::def::{Namespace, Res};
 use rustc_hir::def_id::{DefId, LOCAL_CRATE};
-use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
-use rustc_infer::{infer, traits};
+use rustc_infer::{
+    infer,
+    traits::{self, Obligation},
+};
+use rustc_infer::{
+    infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind},
+    traits::ObligationCause,
+};
 use rustc_middle::ty::adjustment::{
     Adjust, Adjustment, AllowTwoPhase, AutoBorrow, AutoBorrowMutability,
 };
@@ -17,6 +23,7 @@ use rustc_span::symbol::{sym, Ident};
 use rustc_span::Span;
 use rustc_target::spec::abi;
 use rustc_trait_selection::autoderef::Autoderef;
+use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt;
 use std::iter;
 
 /// Checks that it is legal to call methods of the trait corresponding
@@ -294,7 +301,34 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         expected: Expectation<'tcx>,
     ) -> Ty<'tcx> {
         let (fn_sig, def_id) = match *callee_ty.kind() {
-            ty::FnDef(def_id, _) => (callee_ty.fn_sig(self.tcx), Some(def_id)),
+            ty::FnDef(def_id, subst) => {
+                // Unit testing: function items annotated with
+                // `#[rustc_evaluate_where_clauses]` trigger special output
+                // to let us test the trait evaluation system.
+                if self.tcx.has_attr(def_id, sym::rustc_evaluate_where_clauses) {
+                    let predicates = self.tcx.predicates_of(def_id);
+                    let predicates = predicates.instantiate(self.tcx, subst);
+                    for (predicate, predicate_span) in
+                        predicates.predicates.iter().zip(&predicates.spans)
+                    {
+                        let obligation = Obligation::new(
+                            ObligationCause::dummy_with_span(callee_expr.span),
+                            self.param_env,
+                            predicate.clone(),
+                        );
+                        let result = self.infcx.evaluate_obligation(&obligation);
+                        self.tcx
+                            .sess
+                            .struct_span_err(
+                                callee_expr.span,
+                                &format!("evaluate({:?}) = {:?}", predicate, result),
+                            )
+                            .span_label(*predicate_span, "predicate")
+                            .emit();
+                    }
+                }
+                (callee_ty.fn_sig(self.tcx), Some(def_id))
+            }
             ty::FnPtr(sig) => (sig, None),
             ref t => {
                 let mut unit_variant = None;
diff --git a/src/test/ui/traits/cache-reached-depth-ice.rs b/src/test/ui/traits/cache-reached-depth-ice.rs
new file mode 100644
index 00000000000..4318e07d07a
--- /dev/null
+++ b/src/test/ui/traits/cache-reached-depth-ice.rs
@@ -0,0 +1,45 @@
+#![feature(rustc_attrs)]
+
+// Test for a particular corner case where the evaluation
+// cache can get out of date. The problem here is that
+// when we cache C, we have observed that it reaches
+// to depth 2 (the node for B), but we later realize
+// that B itself depends on A (reached depth 0). We
+// failed to update the depth for C transitively, which
+// resulted in an assertion failure when it was referenced
+// from D.
+//
+// A (reached depth 0)
+//   E
+//      B // depth 2 -- reached depth = 0
+//          C // depth 3 -- reached depth = 2 (should be 0)
+//              B
+//          A // depth 0
+//   D (depth 1)
+//      C (cache -- reached depth = 2)
+
+struct A {
+    e: E,
+    d: C,
+}
+
+struct E {
+    b: B,
+}
+
+struct B {
+    a: Option<Box<A>>,
+    c: C,
+}
+
+struct C {
+    b: Option<Box<B>>,
+}
+
+#[rustc_evaluate_where_clauses]
+fn test<X: ?Sized + Send>() {}
+
+fn main() {
+    test::<A>();
+    //~^ ERROR evaluate(Binder(TraitPredicate(<A as std::marker::Send>), [])) = Ok(EvaluatedToOk)
+}
diff --git a/src/test/ui/traits/cache-reached-depth-ice.stderr b/src/test/ui/traits/cache-reached-depth-ice.stderr
new file mode 100644
index 00000000000..5e662970bb9
--- /dev/null
+++ b/src/test/ui/traits/cache-reached-depth-ice.stderr
@@ -0,0 +1,11 @@
+error: evaluate(Binder(TraitPredicate(<A as std::marker::Send>), [])) = Ok(EvaluatedToOk)
+  --> $DIR/cache-reached-depth-ice.rs:43:5
+   |
+LL | fn test<X: ?Sized + Send>() {}
+   |                     ---- predicate
+...
+LL |     test::<A>();
+   |     ^^^^^^^^^
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.rs b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.rs
new file mode 100644
index 00000000000..e186570167d
--- /dev/null
+++ b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.rs
@@ -0,0 +1,66 @@
+// Regression test for issue #83538. The problem here is that we have
+// two cycles:
+//
+// * `Ty` embeds `Box<Ty>` indirectly, which depends on `Global: 'static`, which is OkModuloRegions.
+// * But `Ty` also references `First`, which has a cycle on itself. That should just be `Ok`.
+//
+// But our caching mechanism was blending both cycles and giving the incorrect result.
+
+#![feature(rustc_attrs)]
+#![allow(bad_style)]
+
+struct First {
+    b: Vec<First>,
+}
+
+pub struct Second {
+    d: Vec<First>,
+}
+
+struct Third<f> {
+    g: Vec<f>,
+}
+
+enum Ty {
+    j(Fourth, Fifth, Sixth),
+}
+
+struct Fourth {
+    o: Vec<Ty>,
+}
+
+struct Fifth {
+    bounds: First,
+}
+
+struct Sixth {
+    p: Box<Ty>,
+}
+
+#[rustc_evaluate_where_clauses]
+fn forward()
+where
+    Vec<First>: Unpin,
+    Third<Ty>: Unpin,
+{
+}
+
+#[rustc_evaluate_where_clauses]
+fn reverse()
+where
+    Third<Ty>: Unpin,
+    Vec<First>: Unpin,
+{
+}
+
+fn main() {
+    // Key is that Vec<First> is "ok" and Third<Ty> is "ok modulo regions":
+
+    forward();
+    //~^ ERROR evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
+    //~| ERROR evaluate(Binder(TraitPredicate(<Third<Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+
+    reverse();
+    //~^ ERROR evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
+    //~| ERROR evaluate(Binder(TraitPredicate(<Third<Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+}
diff --git a/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.stderr b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.stderr
new file mode 100644
index 00000000000..bfe3e76b214
--- /dev/null
+++ b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.stderr
@@ -0,0 +1,38 @@
+error: evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
+  --> $DIR/issue-83538-tainted-cache-after-cycle.rs:59:5
+   |
+LL |     Vec<First>: Unpin,
+   |                 ----- predicate
+...
+LL |     forward();
+   |     ^^^^^^^
+
+error: evaluate(Binder(TraitPredicate(<Third<Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+  --> $DIR/issue-83538-tainted-cache-after-cycle.rs:59:5
+   |
+LL |     Third<Ty>: Unpin,
+   |                ----- predicate
+...
+LL |     forward();
+   |     ^^^^^^^
+
+error: evaluate(Binder(TraitPredicate(<Third<Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+  --> $DIR/issue-83538-tainted-cache-after-cycle.rs:63:5
+   |
+LL |     Third<Ty>: Unpin,
+   |                ----- predicate
+...
+LL |     reverse();
+   |     ^^^^^^^
+
+error: evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
+  --> $DIR/issue-83538-tainted-cache-after-cycle.rs:63:5
+   |
+LL |     Vec<First>: Unpin,
+   |                 ----- predicate
+...
+LL |     reverse();
+   |     ^^^^^^^
+
+error: aborting due to 4 previous errors
+