Rollup merge of #98718 - yoshuawuyts:stabilize-into-future, r=yaahc

[rust.git] / compiler / rustc_trait_selection / src / traits / select / mod.rs

diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index f33864024b0adab6f791752abe2093265fef18c9..596ee43562234421e37fe7153cdbe3d1bc22fa61 100644 (file)
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -39,7 +39,7 @@
 use rustc_middle::ty::relate::TypeRelation;
 use rustc_middle::ty::subst::{Subst, SubstsRef};
 use rustc_middle::ty::{self, EarlyBinder, PolyProjectionPredicate, ToPolyTraitRef, ToPredicate};
-use rustc_middle::ty::{Ty, TyCtxt, TypeFoldable};
+use rustc_middle::ty::{Ty, TyCtxt, TypeFoldable, TypeVisitable};
 use rustc_span::symbol::sym;
 
 use std::cell::{Cell, RefCell};
@@ -512,13 +512,36 @@ fn evaluate_predicate_recursively<'o>(
                     let cache = previous_stack.cache;
                     let dfn = cache.next_dfn();
 
-                    for stack_arg in previous_stack.cache.wf_tys.borrow().iter().rev() {
+                    for stack_arg in previous_stack.cache.wf_args.borrow().iter().rev() {
                         if stack_arg.0 != arg {
                             continue;
                         }
                         debug!("WellFormed({:?}) on stack", arg);
                         if let Some(stack) = previous_stack.head {
-                            stack.update_reached_depth(stack_arg.1);
+                            // Okay, let's imagine we have two different stacks:
+                            //   `T: NonAutoTrait -> WF(T) -> T: NonAutoTrait`
+                            //   `WF(T) -> T: NonAutoTrait -> WF(T)`
+                            // Because of this, we need to check that all
+                            // predicates between the WF goals are coinductive.
+                            // Otherwise, we can say that `T: NonAutoTrait` is
+                            // true.
+                            // Let's imagine we have a predicate stack like
+                            //         `Foo: Bar -> WF(T) -> T: NonAutoTrait -> T: Auto
+                            // depth   ^1                    ^2                 ^3
+                            // and the current predicate is `WF(T)`. `wf_args`
+                            // would contain `(T, 1)`. We want to check all
+                            // trait predicates greater than `1`. The previous
+                            // stack would be `T: Auto`.
+                            let cycle = stack.iter().take_while(|s| s.depth > stack_arg.1);
+                            let tcx = self.tcx();
+                            let cycle =
+                                cycle.map(|stack| stack.obligation.predicate.to_predicate(tcx));
+                            if self.coinductive_match(cycle) {
+                                stack.update_reached_depth(stack_arg.1);
+                                return Ok(EvaluatedToOk);
+                            } else {
+                                return Ok(EvaluatedToRecur);
+                            }
                         }
                         return Ok(EvaluatedToOk);
                     }
@@ -534,10 +557,10 @@ fn evaluate_predicate_recursively<'o>(
                         Some(mut obligations) => {
                             self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
 
-                            cache.wf_tys.borrow_mut().push((arg, previous_stack.depth()));
+                            cache.wf_args.borrow_mut().push((arg, previous_stack.depth()));
                             let result =
                                 self.evaluate_predicates_recursively(previous_stack, obligations);
-                            cache.wf_tys.borrow_mut().pop();
+                            cache.wf_args.borrow_mut().pop();
 
                             let result = result?;
 
@@ -1172,8 +1195,7 @@ fn filter_impls(
             if obligation.is_const() {
                 match candidate {
                     // const impl
-                    ImplCandidate(def_id)
-                        if tcx.impl_constness(def_id) == hir::Constness::Const => {}
+                    ImplCandidate(def_id) if tcx.constness(def_id) == hir::Constness::Const => {}
                     // const param
                     ParamCandidate(trait_pred) if trait_pred.is_const_if_const() => {}
                     // auto trait impl
@@ -2465,7 +2487,14 @@ struct ProvisionalEvaluationCache<'tcx> {
     ///   means the cached value for `F`.
     map: RefCell<FxHashMap<ty::PolyTraitPredicate<'tcx>, ProvisionalEvaluation>>,
 
-    wf_tys: RefCell<Vec<(ty::GenericArg<'tcx>, usize)>>,
+    /// The stack of args that we assume to be true because a `WF(arg)` predicate
+    /// is on the stack above (and because of wellformedness is coinductive).
+    /// In an "ideal" world, this would share a stack with trait predicates in
+    /// `TraitObligationStack`. However, trait predicates are *much* hotter than
+    /// `WellFormed` predicates, and it's very likely that the additional matches
+    /// will have a perf effect. The value here is the well-formed `GenericArg`
+    /// and the depth of the trait predicate *above* that well-formed predicate.
+    wf_args: RefCell<Vec<(ty::GenericArg<'tcx>, usize)>>,
 }
 
 /// A cache value for the provisional cache: contains the depth-first
@@ -2479,7 +2508,7 @@ struct ProvisionalEvaluation {
 
 impl<'tcx> Default for ProvisionalEvaluationCache<'tcx> {
     fn default() -> Self {
-        Self { dfn: Cell::new(0), map: Default::default(), wf_tys: Default::default() }
+        Self { dfn: Cell::new(0), map: Default::default(), wf_args: Default::default() }
     }
 }