Merge remote-tracking branch 'origin/master' into mpk/add-long-error-message-for-E0311

13 files changed, 445 insertions, 196 deletions

diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs
index 9c252fcfe1c..77cc2c164c3 100644
--- a/compiler/rustc_trait_selection/src/lib.rs
+++ b/compiler/rustc_trait_selection/src/lib.rs
@@ -16,10 +16,12 @@
 #![feature(control_flow_enum)]
 #![feature(drain_filter)]
 #![feature(hash_drain_filter)]
-#![feature(label_break_value)]
+#![cfg_attr(bootstrap, feature(label_break_value))]
+#![feature(let_chains)]
 #![feature(let_else)]
 #![feature(if_let_guard)]
 #![feature(never_type)]
+#![feature(type_alias_impl_trait)]
 #![recursion_limit = "512"] // For rustdoc
 
 #[macro_use]
diff --git a/compiler/rustc_trait_selection/src/traits/auto_trait.rs b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
index 6b230210888..4bab9935501 100644
--- a/compiler/rustc_trait_selection/src/traits/auto_trait.rs
+++ b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
@@ -341,7 +341,7 @@ impl<'tcx> AutoTraitFinder<'tcx> {
                         }
                     }
 
-                    let obligations = impl_source.clone().nested_obligations().into_iter();
+                    let obligations = impl_source.borrow_nested_obligations().iter().cloned();
 
                     if !self.evaluate_nested_obligations(
                         ty,
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 985600d9ebc..292787d4dbb 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -6,16 +6,18 @@
 
 use crate::infer::outlives::env::OutlivesEnvironment;
 use crate::infer::{CombinedSnapshot, InferOk};
+use crate::traits::outlives_bounds::InferCtxtExt as _;
 use crate::traits::select::IntercrateAmbiguityCause;
 use crate::traits::util::impl_subject_and_oblig;
 use crate::traits::SkipLeakCheck;
 use crate::traits::{
-    self, Normalized, Obligation, ObligationCause, PredicateObligation, PredicateObligations,
-    SelectionContext,
+    self, Normalized, Obligation, ObligationCause, ObligationCtxt, PredicateObligation,
+    PredicateObligations, SelectionContext,
 };
 use rustc_data_structures::fx::FxIndexSet;
 use rustc_errors::Diagnostic;
-use rustc_hir::def_id::{DefId, LOCAL_CRATE};
+use rustc_hir::def_id::{DefId, CRATE_DEF_ID, LOCAL_CRATE};
+use rustc_hir::CRATE_HIR_ID;
 use rustc_infer::infer::{InferCtxt, TyCtxtInferExt};
 use rustc_infer::traits::util;
 use rustc_middle::traits::specialization_graph::OverlapMode;
@@ -322,7 +324,7 @@ fn negative_impl<'cx, 'tcx>(
         let (subject2, obligations) =
             impl_subject_and_oblig(selcx, impl_env, impl2_def_id, impl2_substs);
 
-        !equate(&infcx, impl_env, subject1, subject2, obligations)
+        !equate(&infcx, impl_env, subject1, subject2, obligations, impl1_def_id)
     })
 }
 
@@ -332,6 +334,7 @@ fn equate<'cx, 'tcx>(
     subject1: ImplSubject<'tcx>,
     subject2: ImplSubject<'tcx>,
     obligations: impl Iterator<Item = PredicateObligation<'tcx>>,
+    body_def_id: DefId,
 ) -> bool {
     // do the impls unify? If not, not disjoint.
     let Ok(InferOk { obligations: more_obligations, .. }) =
@@ -345,7 +348,7 @@ fn equate<'cx, 'tcx>(
     let opt_failing_obligation = obligations
         .into_iter()
         .chain(more_obligations)
-        .find(|o| negative_impl_exists(selcx, impl_env, o));
+        .find(|o| negative_impl_exists(selcx, o, body_def_id));
 
     if let Some(failing_obligation) = opt_failing_obligation {
         debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
@@ -359,18 +362,16 @@ fn equate<'cx, 'tcx>(
 #[instrument(level = "debug", skip(selcx))]
 fn negative_impl_exists<'cx, 'tcx>(
     selcx: &SelectionContext<'cx, 'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
     o: &PredicateObligation<'tcx>,
+    body_def_id: DefId,
 ) -> bool {
-    let infcx = &selcx.infcx().fork();
-
-    if resolve_negative_obligation(infcx, param_env, o) {
+    if resolve_negative_obligation(selcx.infcx().fork(), o, body_def_id) {
         return true;
     }
 
     // Try to prove a negative obligation exists for super predicates
-    for o in util::elaborate_predicates(infcx.tcx, iter::once(o.predicate)) {
-        if resolve_negative_obligation(infcx, param_env, &o) {
+    for o in util::elaborate_predicates(selcx.tcx(), iter::once(o.predicate)) {
+        if resolve_negative_obligation(selcx.infcx().fork(), &o, body_def_id) {
             return true;
         }
     }
@@ -380,9 +381,9 @@ fn negative_impl_exists<'cx, 'tcx>(
 
 #[instrument(level = "debug", skip(infcx))]
 fn resolve_negative_obligation<'cx, 'tcx>(
-    infcx: &InferCtxt<'cx, 'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
+    infcx: InferCtxt<'cx, 'tcx>,
     o: &PredicateObligation<'tcx>,
+    body_def_id: DefId,
 ) -> bool {
     let tcx = infcx.tcx;
 
@@ -390,12 +391,25 @@ fn resolve_negative_obligation<'cx, 'tcx>(
         return false;
     };
 
-    let errors = super::fully_solve_obligation(infcx, o);
-    if !errors.is_empty() {
+    let param_env = o.param_env;
+    if !super::fully_solve_obligation(&infcx, o).is_empty() {
         return false;
     }
 
-    let outlives_env = OutlivesEnvironment::new(param_env);
+    let (body_id, body_def_id) = if let Some(body_def_id) = body_def_id.as_local() {
+        (tcx.hir().local_def_id_to_hir_id(body_def_id), body_def_id)
+    } else {
+        (CRATE_HIR_ID, CRATE_DEF_ID)
+    };
+
+    let ocx = ObligationCtxt::new(&infcx);
+    let wf_tys = ocx.assumed_wf_types(param_env, DUMMY_SP, body_def_id);
+    let outlives_env = OutlivesEnvironment::with_bounds(
+        param_env,
+        Some(&infcx),
+        infcx.implied_bounds_tys(param_env, body_id, wf_tys),
+    );
+
     infcx.process_registered_region_obligations(outlives_env.region_bound_pairs(), param_env);
 
     infcx.resolve_regions(&outlives_env).is_empty()
diff --git a/compiler/rustc_trait_selection/src/traits/engine.rs b/compiler/rustc_trait_selection/src/traits/engine.rs
index 6c177f63887..dba4d4f69da 100644
--- a/compiler/rustc_trait_selection/src/traits/engine.rs
+++ b/compiler/rustc_trait_selection/src/traits/engine.rs
@@ -3,7 +3,8 @@ use std::cell::RefCell;
 use super::TraitEngine;
 use super::{ChalkFulfillmentContext, FulfillmentContext};
 use crate::infer::InferCtxtExt;
-use rustc_hir::def_id::DefId;
+use rustc_data_structures::fx::FxHashSet;
+use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_infer::infer::{InferCtxt, InferOk};
 use rustc_infer::traits::{
     FulfillmentError, Obligation, ObligationCause, PredicateObligation, TraitEngineExt as _,
@@ -12,9 +13,11 @@ use rustc_middle::ty::error::TypeError;
 use rustc_middle::ty::ToPredicate;
 use rustc_middle::ty::TypeFoldable;
 use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_span::Span;
 
 pub trait TraitEngineExt<'tcx> {
     fn new(tcx: TyCtxt<'tcx>) -> Box<Self>;
+    fn new_in_snapshot(tcx: TyCtxt<'tcx>) -> Box<Self>;
 }
 
 impl<'tcx> TraitEngineExt<'tcx> for dyn TraitEngine<'tcx> {
@@ -25,6 +28,14 @@ impl<'tcx> TraitEngineExt<'tcx> for dyn TraitEngine<'tcx> {
             Box::new(FulfillmentContext::new())
         }
     }
+
+    fn new_in_snapshot(tcx: TyCtxt<'tcx>) -> Box<Self> {
+        if tcx.sess.opts.unstable_opts.chalk {
+            Box::new(ChalkFulfillmentContext::new())
+        } else {
+            Box::new(FulfillmentContext::new_in_snapshot())
+        }
+    }
 }
 
 /// Used if you want to have pleasant experience when dealing
@@ -39,6 +50,10 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> {
         Self { infcx, engine: RefCell::new(<dyn TraitEngine<'_>>::new(infcx.tcx)) }
     }
 
+    pub fn new_in_snapshot(infcx: &'a InferCtxt<'a, 'tcx>) -> Self {
+        Self { infcx, engine: RefCell::new(<dyn TraitEngine<'_>>::new_in_snapshot(infcx.tcx)) }
+    }
+
     pub fn register_obligation(&self, obligation: PredicateObligation<'tcx>) {
         self.engine.borrow_mut().register_predicate_obligation(self.infcx, obligation);
     }
@@ -109,4 +124,34 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> {
     pub fn select_all_or_error(&self) -> Vec<FulfillmentError<'tcx>> {
         self.engine.borrow_mut().select_all_or_error(self.infcx)
     }
+
+    pub fn assumed_wf_types(
+        &self,
+        param_env: ty::ParamEnv<'tcx>,
+        span: Span,
+        def_id: LocalDefId,
+    ) -> FxHashSet<Ty<'tcx>> {
+        let tcx = self.infcx.tcx;
+        let assumed_wf_types = tcx.assumed_wf_types(def_id);
+        let mut implied_bounds = FxHashSet::default();
+        let hir_id = tcx.hir().local_def_id_to_hir_id(def_id);
+        let cause = ObligationCause::misc(span, hir_id);
+        for ty in assumed_wf_types {
+            // FIXME(@lcnr): rustc currently does not check wf for types
+            // pre-normalization, meaning that implied bounds are sometimes
+            // incorrect. See #100910 for more details.
+            //
+            // Not adding the unnormalized types here mostly fixes that, except
+            // that there are projections which are still ambiguous in the item definition
+            // but do normalize successfully when using the item, see #98543.
+            //
+            // Anyways, I will hopefully soon change implied bounds to make all of this
+            // sound and then uncomment this line again.
+
+            // implied_bounds.insert(ty);
+            let normalized = self.normalize(cause.clone(), param_env, ty);
+            implied_bounds.insert(normalized);
+        }
+        implied_bounds
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index 1a39a168038..e4af7022239 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -860,8 +860,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                             }
                         }
 
-                        err.emit();
-                        return;
+                        err
                     }
 
                     ty::PredicateKind::WellFormed(ty) => {
@@ -1507,13 +1506,28 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
                 .emit();
             }
             FulfillmentErrorCode::CodeConstEquateError(ref expected_found, ref err) => {
-                self.report_mismatched_consts(
+                let mut diag = self.report_mismatched_consts(
                     &error.obligation.cause,
                     expected_found.expected,
                     expected_found.found,
                     err.clone(),
-                )
-                .emit();
+                );
+                let code = error.obligation.cause.code().peel_derives().peel_match_impls();
+                if let ObligationCauseCode::BindingObligation(..)
+                | ObligationCauseCode::ItemObligation(..)
+                | ObligationCauseCode::ExprBindingObligation(..)
+                | ObligationCauseCode::ExprItemObligation(..) = code
+                {
+                    self.note_obligation_cause_code(
+                        &mut diag,
+                        &error.obligation.predicate,
+                        error.obligation.param_env,
+                        code,
+                        &mut vec![],
+                        &mut Default::default(),
+                    );
+                }
+                diag.emit();
             }
         }
     }
@@ -1564,6 +1578,8 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
                     obligation.cause.code().peel_derives(),
                     ObligationCauseCode::ItemObligation(_)
                         | ObligationCauseCode::BindingObligation(_, _)
+                        | ObligationCauseCode::ExprItemObligation(..)
+                        | ObligationCauseCode::ExprBindingObligation(..)
                         | ObligationCauseCode::ObjectCastObligation(..)
                         | ObligationCauseCode::OpaqueType
                 );
@@ -2091,13 +2107,11 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
                     }
                 }
 
-                if let ObligationCauseCode::ItemObligation(def_id) = *obligation.cause.code() {
+                if let ObligationCauseCode::ItemObligation(def_id) | ObligationCauseCode::ExprItemObligation(def_id, ..) = *obligation.cause.code() {
                     self.suggest_fully_qualified_path(&mut err, def_id, span, trait_ref.def_id());
-                } else if let (
-                    Ok(ref snippet),
-                    &ObligationCauseCode::BindingObligation(def_id, _),
-                ) =
-                    (self.tcx.sess.source_map().span_to_snippet(span), obligation.cause.code())
+                } else if let Ok(snippet) = &self.tcx.sess.source_map().span_to_snippet(span)
+                    && let ObligationCauseCode::BindingObligation(def_id, _) | ObligationCauseCode::ExprBindingObligation(def_id, ..)
+                        = *obligation.cause.code()
                 {
                     let generics = self.tcx.generics_of(def_id);
                     if generics.params.iter().any(|p| p.name != kw::SelfUpper)
@@ -2520,15 +2534,10 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
         err: &mut Diagnostic,
         obligation: &PredicateObligation<'tcx>,
     ) {
-        let (
-            ty::PredicateKind::Trait(pred),
-            &ObligationCauseCode::BindingObligation(item_def_id, span),
-        ) = (
-            obligation.predicate.kind().skip_binder(),
-            obligation.cause.code().peel_derives(),
-        )  else {
-            return;
-        };
+        let ty::PredicateKind::Trait(pred) = obligation.predicate.kind().skip_binder() else { return; };
+        let (ObligationCauseCode::BindingObligation(item_def_id, span)
+        | ObligationCauseCode::ExprBindingObligation(item_def_id, span, ..))
+            = *obligation.cause.code().peel_derives() else { return; };
         debug!(?pred, ?item_def_id, ?span);
 
         let (Some(node), true) = (
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
index e6907637c57..6b03555bc69 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
@@ -143,7 +143,9 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         }
 
         if let ObligationCauseCode::ItemObligation(item)
-        | ObligationCauseCode::BindingObligation(item, _) = *obligation.cause.code()
+        | ObligationCauseCode::BindingObligation(item, _)
+        | ObligationCauseCode::ExprItemObligation(item, ..)
+        | ObligationCauseCode::ExprBindingObligation(item, ..) = *obligation.cause.code()
         {
             // FIXME: maybe also have some way of handling methods
             // from other traits? That would require name resolution,
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
index cae1509e640..02adae5bde1 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
@@ -20,7 +20,7 @@ use rustc_hir::def_id::DefId;
 use rustc_hir::intravisit::Visitor;
 use rustc_hir::lang_items::LangItem;
 use rustc_hir::{AsyncGeneratorKind, GeneratorKind, Node};
-use rustc_infer::infer::TyCtxtInferExt;
+use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
 use rustc_middle::hir::map;
 use rustc_middle::ty::{
     self, suggest_arbitrary_trait_bound, suggest_constraining_type_param, AdtKind, DefIdTree,
@@ -671,11 +671,16 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         trait_pred: ty::PolyTraitPredicate<'tcx>,
     ) -> bool {
         // It only make sense when suggesting dereferences for arguments
-        let ObligationCauseCode::FunctionArgumentObligation { .. } = obligation.cause.code() else {
-            return false;
-        };
-        let param_env = obligation.param_env;
-        let body_id = obligation.cause.body_id;
+        let ObligationCauseCode::FunctionArgumentObligation { arg_hir_id, .. } = obligation.cause.code()
+            else { return false; };
+        let Some(typeck_results) = self.in_progress_typeck_results
+            else { return false; };
+        let typeck_results = typeck_results.borrow();
+        let hir::Node::Expr(expr) = self.tcx.hir().get(*arg_hir_id)
+            else { return false; };
+        let Some(arg_ty) = typeck_results.expr_ty_adjusted_opt(expr)
+            else { return false; };
+
         let span = obligation.cause.span;
         let mut real_trait_pred = trait_pred;
         let mut code = obligation.cause.code();
@@ -685,11 +690,25 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                 real_trait_pred = parent_trait_pred;
             }
 
-            // Skipping binder here, remapping below
-            let real_ty = real_trait_pred.self_ty().skip_binder();
+            let real_ty = real_trait_pred.self_ty();
+            // We `erase_late_bound_regions` here because `make_subregion` does not handle
+            // `ReLateBound`, and we don't particularly care about the regions.
+            if self
+                .can_eq(obligation.param_env, self.tcx.erase_late_bound_regions(real_ty), arg_ty)
+                .is_err()
+            {
+                continue;
+            }
 
-            if let ty::Ref(region, base_ty, mutbl) = *real_ty.kind() {
-                let mut autoderef = Autoderef::new(self, param_env, body_id, span, base_ty, span);
+            if let ty::Ref(region, base_ty, mutbl) = *real_ty.skip_binder().kind() {
+                let mut autoderef = Autoderef::new(
+                    self,
+                    obligation.param_env,
+                    obligation.cause.body_id,
+                    span,
+                    base_ty,
+                    span,
+                );
                 if let Some(steps) = autoderef.find_map(|(ty, steps)| {
                     // Re-add the `&`
                     let ty = self.tcx.mk_ref(region, TypeAndMut { ty, mutbl });
@@ -697,24 +716,29 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                     // Remapping bound vars here
                     let real_trait_pred_and_ty =
                         real_trait_pred.map_bound(|inner_trait_pred| (inner_trait_pred, ty));
-                    let obligation = self
-                        .mk_trait_obligation_with_new_self_ty(param_env, real_trait_pred_and_ty);
+                    let obligation = self.mk_trait_obligation_with_new_self_ty(
+                        obligation.param_env,
+                        real_trait_pred_and_ty,
+                    );
                     Some(steps).filter(|_| self.predicate_may_hold(&obligation))
                 }) {
                     if steps > 0 {
-                        if let Ok(src) = self.tcx.sess.source_map().span_to_snippet(span) {
-                            // Don't care about `&mut` because `DerefMut` is used less
-                            // often and user will not expect autoderef happens.
-                            if src.starts_with('&') && !src.starts_with("&mut ") {
-                                let derefs = "*".repeat(steps);
-                                err.span_suggestion(
-                                    span,
-                                    "consider dereferencing here",
-                                    format!("&{}{}", derefs, &src[1..]),
-                                    Applicability::MachineApplicable,
-                                );
-                                return true;
-                            }
+                        // Don't care about `&mut` because `DerefMut` is used less
+                        // often and user will not expect autoderef happens.
+                        if let Some(hir::Node::Expr(hir::Expr {
+                            kind:
+                                hir::ExprKind::AddrOf(hir::BorrowKind::Ref, hir::Mutability::Not, expr),
+                            ..
+                        })) = self.tcx.hir().find(*arg_hir_id)
+                        {
+                            let derefs = "*".repeat(steps);
+                            err.span_suggestion_verbose(
+                                expr.span.shrink_to_lo(),
+                                "consider dereferencing here",
+                                derefs,
+                                Applicability::MachineApplicable,
+                            );
+                            return true;
                         }
                     }
                 } else if real_trait_pred != trait_pred {
@@ -724,7 +748,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                     let real_trait_pred_and_base_ty =
                         real_trait_pred.map_bound(|inner_trait_pred| (inner_trait_pred, base_ty));
                     let obligation = self.mk_trait_obligation_with_new_self_ty(
-                        param_env,
+                        obligation.param_env,
                         real_trait_pred_and_base_ty,
                     );
                     if self.predicate_may_hold(&obligation) {
@@ -852,6 +876,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
             _ => return false,
         };
         if matches!(obligation.cause.code(), ObligationCauseCode::FunctionArgumentObligation { .. })
+            && obligation.cause.span.can_be_used_for_suggestions()
         {
             // When the obligation error has been ensured to have been caused by
             // an argument, the `obligation.cause.span` points at the expression
@@ -882,6 +907,10 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
             obligation.cause.code()
         {
             &parent_code
+        } else if let ObligationCauseCode::ItemObligation(_)
+        | ObligationCauseCode::ExprItemObligation(..) = obligation.cause.code()
+        {
+            obligation.cause.code()
         } else if let ExpnKind::Desugaring(DesugaringKind::ForLoop) =
             span.ctxt().outer_expn_data().kind
         {
@@ -906,102 +935,121 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         let param_env = obligation.param_env;
 
         // Try to apply the original trait binding obligation by borrowing.
-        let mut try_borrowing =
-            |old_pred: ty::PolyTraitPredicate<'tcx>, blacklist: &[DefId]| -> bool {
-                if blacklist.contains(&old_pred.def_id()) {
-                    return false;
-                }
-                // We map bounds to `&T` and `&mut T`
-                let trait_pred_and_imm_ref = old_pred.map_bound(|trait_pred| {
-                    (
-                        trait_pred,
-                        self.tcx.mk_imm_ref(self.tcx.lifetimes.re_static, trait_pred.self_ty()),
-                    )
-                });
-                let trait_pred_and_mut_ref = old_pred.map_bound(|trait_pred| {
+        let mut try_borrowing = |old_pred: ty::PolyTraitPredicate<'tcx>,
+                                 blacklist: &[DefId]|
+         -> bool {
+            if blacklist.contains(&old_pred.def_id()) {
+                return false;
+            }
+            // We map bounds to `&T` and `&mut T`
+            let trait_pred_and_imm_ref = old_pred.map_bound(|trait_pred| {
+                (
+                    trait_pred,
+                    self.tcx.mk_imm_ref(self.tcx.lifetimes.re_static, trait_pred.self_ty()),
+                )
+            });
+            let trait_pred_and_mut_ref = old_pred.map_bound(|trait_pred| {
+                (
+                    trait_pred,
+                    self.tcx.mk_mut_ref(self.tcx.lifetimes.re_static, trait_pred.self_ty()),
+                )
+            });
+
+            let mk_result = |trait_pred_and_new_ty| {
+                let obligation =
+                    self.mk_trait_obligation_with_new_self_ty(param_env, trait_pred_and_new_ty);
+                self.predicate_must_hold_modulo_regions(&obligation)
+            };
+            let imm_ref_self_ty_satisfies_pred = mk_result(trait_pred_and_imm_ref);
+            let mut_ref_self_ty_satisfies_pred = mk_result(trait_pred_and_mut_ref);
+
+            let (ref_inner_ty_satisfies_pred, ref_inner_ty_mut) =
+                if let ObligationCauseCode::ItemObligation(_) | ObligationCauseCode::ExprItemObligation(..) = obligation.cause.code()
+                    && let ty::Ref(_, ty, mutability) = old_pred.self_ty().skip_binder().kind()
+                {
                     (
-                        trait_pred,
-                        self.tcx.mk_mut_ref(self.tcx.lifetimes.re_static, trait_pred.self_ty()),
+                        mk_result(old_pred.map_bound(|trait_pred| (trait_pred, *ty))),
+                        matches!(mutability, hir::Mutability::Mut),
                     )
-                });
-
-                let mk_result = |trait_pred_and_new_ty| {
-                    let obligation =
-                        self.mk_trait_obligation_with_new_self_ty(param_env, trait_pred_and_new_ty);
-                    self.predicate_must_hold_modulo_regions(&obligation)
+                } else {
+                    (false, false)
                 };
-                let imm_result = mk_result(trait_pred_and_imm_ref);
-                let mut_result = mk_result(trait_pred_and_mut_ref);
-
-                if imm_result || mut_result {
-                    if let Ok(snippet) = self.tcx.sess.source_map().span_to_snippet(span) {
-                        // We have a very specific type of error, where just borrowing this argument
-                        // might solve the problem. In cases like this, the important part is the
-                        // original type obligation, not the last one that failed, which is arbitrary.
-                        // Because of this, we modify the error to refer to the original obligation and
-                        // return early in the caller.
-
-                        let msg = format!("the trait bound `{}` is not satisfied", old_pred);
-                        if has_custom_message {
-                            err.note(&msg);
-                        } else {
-                            err.message =
-                                vec![(rustc_errors::DiagnosticMessage::Str(msg), Style::NoStyle)];
-                        }
-                        if snippet.starts_with('&') {
-                            // This is already a literal borrow and the obligation is failing
-                            // somewhere else in the obligation chain. Do not suggest non-sense.
-                            return false;
-                        }
-                        err.span_label(
-                            span,
+
+            if imm_ref_self_ty_satisfies_pred
+                || mut_ref_self_ty_satisfies_pred
+                || ref_inner_ty_satisfies_pred
+            {
+                if let Ok(snippet) = self.tcx.sess.source_map().span_to_snippet(span) {
+                    // We don't want a borrowing suggestion on the fields in structs,
+                    // ```
+                    // struct Foo {
+                    //  the_foos: Vec<Foo>
+                    // }
+                    // ```
+                    if !matches!(
+                        span.ctxt().outer_expn_data().kind,
+                        ExpnKind::Root | ExpnKind::Desugaring(DesugaringKind::ForLoop)
+                    ) {
+                        return false;
+                    }
+                    if snippet.starts_with('&') {
+                        // This is already a literal borrow and the obligation is failing
+                        // somewhere else in the obligation chain. Do not suggest non-sense.
+                        return false;
+                    }
+                    // We have a very specific type of error, where just borrowing this argument
+                    // might solve the problem. In cases like this, the important part is the
+                    // original type obligation, not the last one that failed, which is arbitrary.
+                    // Because of this, we modify the error to refer to the original obligation and
+                    // return early in the caller.
+
+                    let msg = format!("the trait bound `{}` is not satisfied", old_pred);
+                    if has_custom_message {
+                        err.note(&msg);
+                    } else {
+                        err.message =
+                            vec![(rustc_errors::DiagnosticMessage::Str(msg), Style::NoStyle)];
+                    }
+                    err.span_label(
+                        span,
+                        format!(
+                            "the trait `{}` is not implemented for `{}`",
+                            old_pred.print_modifiers_and_trait_path(),
+                            old_pred.self_ty().skip_binder(),
+                        ),
+                    );
+
+                    if imm_ref_self_ty_satisfies_pred && mut_ref_self_ty_satisfies_pred {
+                        err.span_suggestions(
+                            span.shrink_to_lo(),
+                            "consider borrowing here",
+                            ["&".to_string(), "&mut ".to_string()].into_iter(),
+                            Applicability::MaybeIncorrect,
+                        );
+                    } else {
+                        let is_mut = mut_ref_self_ty_satisfies_pred || ref_inner_ty_mut;
+                        err.span_suggestion_verbose(
+                            span.shrink_to_lo(),
                             &format!(
-                                "expected an implementor of trait `{}`",
-                                old_pred.print_modifiers_and_trait_path(),
+                                "consider{} borrowing here",
+                                if is_mut { " mutably" } else { "" }
                             ),
+                            format!("&{}", if is_mut { "mut " } else { "" }),
+                            Applicability::MaybeIncorrect,
                         );
-
-                        // This if is to prevent a special edge-case
-                        if matches!(
-                            span.ctxt().outer_expn_data().kind,
-                            ExpnKind::Root | ExpnKind::Desugaring(DesugaringKind::ForLoop)
-                        ) {
-                            // We don't want a borrowing suggestion on the fields in structs,
-                            // ```
-                            // struct Foo {
-                            //  the_foos: Vec<Foo>
-                            // }
-                            // ```
-
-                            if imm_result && mut_result {
-                                err.span_suggestions(
-                                    span.shrink_to_lo(),
-                                    "consider borrowing here",
-                                    ["&".to_string(), "&mut ".to_string()].into_iter(),
-                                    Applicability::MaybeIncorrect,
-                                );
-                            } else {
-                                err.span_suggestion_verbose(
-                                    span.shrink_to_lo(),
-                                    &format!(
-                                        "consider{} borrowing here",
-                                        if mut_result { " mutably" } else { "" }
-                                    ),
-                                    format!("&{}", if mut_result { "mut " } else { "" }),
-                                    Applicability::MaybeIncorrect,
-                                );
-                            }
-                        }
-                        return true;
                     }
+                    return true;
                 }
-                return false;
-            };
+            }
+            return false;
+        };
 
         if let ObligationCauseCode::ImplDerivedObligation(cause) = &*code {
             try_borrowing(cause.derived.parent_trait_pred, &[])
         } else if let ObligationCauseCode::BindingObligation(_, _)
-        | ObligationCauseCode::ItemObligation(_) = code
+        | ObligationCauseCode::ItemObligation(_)
+        | ObligationCauseCode::ExprItemObligation(..)
+        | ObligationCauseCode::ExprBindingObligation(..) = code
         {
             try_borrowing(poly_trait_pred, &never_suggest_borrow)
         } else {
@@ -1541,32 +1589,38 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         expected: ty::PolyTraitRef<'tcx>,
     ) -> DiagnosticBuilder<'tcx, ErrorGuaranteed> {
         pub(crate) fn build_fn_sig_ty<'tcx>(
-            tcx: TyCtxt<'tcx>,
+            infcx: &InferCtxt<'_, 'tcx>,
             trait_ref: ty::PolyTraitRef<'tcx>,
         ) -> Ty<'tcx> {
             let inputs = trait_ref.skip_binder().substs.type_at(1);
             let sig = match inputs.kind() {
                 ty::Tuple(inputs)
-                    if tcx.fn_trait_kind_from_lang_item(trait_ref.def_id()).is_some() =>
+                    if infcx.tcx.fn_trait_kind_from_lang_item(trait_ref.def_id()).is_some() =>
                 {
-                    tcx.mk_fn_sig(
+                    infcx.tcx.mk_fn_sig(
                         inputs.iter(),
-                        tcx.mk_ty_infer(ty::TyVar(ty::TyVid::from_u32(0))),
+                        infcx.next_ty_var(TypeVariableOrigin {
+                            span: DUMMY_SP,
+                            kind: TypeVariableOriginKind::MiscVariable,
+                        }),
                         false,
                         hir::Unsafety::Normal,
                         abi::Abi::Rust,
                     )
                 }
-                _ => tcx.mk_fn_sig(
+                _ => infcx.tcx.mk_fn_sig(
                     std::iter::once(inputs),
-                    tcx.mk_ty_infer(ty::TyVar(ty::TyVid::from_u32(0))),
+                    infcx.next_ty_var(TypeVariableOrigin {
+                        span: DUMMY_SP,
+                        kind: TypeVariableOriginKind::MiscVariable,
+                    }),
                     false,
                     hir::Unsafety::Normal,
                     abi::Abi::Rust,
                 ),
             };
 
-            tcx.mk_fn_ptr(trait_ref.rebind(sig))
+            infcx.tcx.mk_fn_ptr(trait_ref.rebind(sig))
         }
 
         let argument_kind = match expected.skip_binder().self_ty().kind() {
@@ -1586,11 +1640,10 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         let found_span = found_span.unwrap_or(span);
         err.span_label(found_span, "found signature defined here");
 
-        let expected = build_fn_sig_ty(self.tcx, expected);
-        let found = build_fn_sig_ty(self.tcx, found);
+        let expected = build_fn_sig_ty(self, expected);
+        let found = build_fn_sig_ty(self, found);
 
-        let (expected_str, found_str) =
-            self.tcx.infer_ctxt().enter(|infcx| infcx.cmp(expected, found));
+        let (expected_str, found_str) = self.cmp(expected, found);
 
         let signature_kind = format!("{argument_kind} signature");
         err.note_expected_found(&signature_kind, expected_str, &signature_kind, found_str);
@@ -2223,11 +2276,13 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                     region, object_ty,
                 ));
             }
-            ObligationCauseCode::ItemObligation(_item_def_id) => {
+            ObligationCauseCode::ItemObligation(_)
+            | ObligationCauseCode::ExprItemObligation(..) => {
                 // We hold the `DefId` of the item introducing the obligation, but displaying it
                 // doesn't add user usable information. It always point at an associated item.
             }
-            ObligationCauseCode::BindingObligation(item_def_id, span) => {
+            ObligationCauseCode::BindingObligation(item_def_id, span)
+            | ObligationCauseCode::ExprBindingObligation(item_def_id, span, ..) => {
                 let item_name = tcx.def_path_str(item_def_id);
                 let mut multispan = MultiSpan::from(span);
                 if let Some(ident) = tcx.opt_item_ident(item_def_id) {
diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs
index 556ef466cd1..d840677f1ca 100644
--- a/compiler/rustc_trait_selection/src/traits/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs
@@ -597,6 +597,7 @@ impl<'a, 'b, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'tcx> {
         }
     }
 
+    #[inline(never)]
     fn process_backedge<'c, I>(
         &mut self,
         cycle: I,
diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs
index b6d6df1eec6..e11ea7751aa 100644
--- a/compiler/rustc_trait_selection/src/traits/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/mod.rs
@@ -13,6 +13,7 @@ mod fulfill;
 pub mod misc;
 mod object_safety;
 mod on_unimplemented;
+pub mod outlives_bounds;
 mod project;
 pub mod query;
 pub(crate) mod relationships;
@@ -117,11 +118,21 @@ pub enum TraitQueryMode {
 
 /// Creates predicate obligations from the generic bounds.
 pub fn predicates_for_generics<'tcx>(
-    cause: ObligationCause<'tcx>,
+    cause: impl Fn(usize, Span) -> ObligationCause<'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     generic_bounds: ty::InstantiatedPredicates<'tcx>,
 ) -> impl Iterator<Item = PredicateObligation<'tcx>> {
-    util::predicates_for_generics(cause, 0, param_env, generic_bounds)
+    let generic_bounds = generic_bounds;
+    debug!("predicates_for_generics(generic_bounds={:?})", generic_bounds);
+
+    std::iter::zip(generic_bounds.predicates, generic_bounds.spans).enumerate().map(
+        move |(idx, (predicate, span))| Obligation {
+            cause: cause(idx, span),
+            recursion_depth: 0,
+            param_env: param_env,
+            predicate,
+        },
+    )
 }
 
 /// Determines whether the type `ty` is known to meet `bound` and
@@ -463,9 +474,6 @@ pub fn impossible_predicates<'tcx>(
     debug!("impossible_predicates(predicates={:?})", predicates);
 
     let result = tcx.infer_ctxt().enter(|infcx| {
-        // HACK: Set tainted by errors to gracefully exit in case of overflow.
-        infcx.set_tainted_by_errors();
-
         let param_env = ty::ParamEnv::reveal_all();
         let ocx = ObligationCtxt::new(&infcx);
         let predicates = ocx.normalize(ObligationCause::dummy(), param_env, predicates);
@@ -571,9 +579,16 @@ fn is_impossible_method<'tcx>(
     });
 
     tcx.infer_ctxt().ignoring_regions().enter(|ref infcx| {
-        let mut fulfill_ctxt = <dyn TraitEngine<'_>>::new(tcx);
-        fulfill_ctxt.register_predicate_obligations(infcx, predicates_for_trait);
-        !fulfill_ctxt.select_all_or_error(infcx).is_empty()
+        for obligation in predicates_for_trait {
+            // Ignore overflow error, to be conservative.
+            if let Ok(result) = infcx.evaluate_obligation(&obligation)
+                && !result.may_apply()
+            {
+                return true;
+            }
+        }
+
+        false
     })
 }
 
diff --git a/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs b/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs
new file mode 100644
index 00000000000..a4b54018228
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs
@@ -0,0 +1,114 @@
+use crate::infer::InferCtxt;
+use crate::traits::query::type_op::{self, TypeOp, TypeOpOutput};
+use crate::traits::query::NoSolution;
+use crate::traits::{ObligationCause, TraitEngine, TraitEngineExt};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_hir as hir;
+use rustc_hir::HirId;
+use rustc_middle::ty::{self, ParamEnv, Ty};
+
+pub use rustc_middle::traits::query::OutlivesBound;
+
+type Bounds<'a, 'tcx: 'a> = impl Iterator<Item = OutlivesBound<'tcx>> + 'a;
+pub trait InferCtxtExt<'a, 'tcx> {
+    fn implied_outlives_bounds(
+        &self,
+        param_env: ty::ParamEnv<'tcx>,
+        body_id: hir::HirId,
+        ty: Ty<'tcx>,
+    ) -> Vec<OutlivesBound<'tcx>>;
+
+    fn implied_bounds_tys(
+        &'a self,
+        param_env: ty::ParamEnv<'tcx>,
+        body_id: hir::HirId,
+        tys: FxHashSet<Ty<'tcx>>,
+    ) -> Bounds<'a, 'tcx>;
+}
+
+impl<'a, 'cx, 'tcx: 'a> InferCtxtExt<'a, 'tcx> for InferCtxt<'cx, 'tcx> {
+    /// Implied bounds are region relationships that we deduce
+    /// automatically. The idea is that (e.g.) a caller must check that a
+    /// function's argument types are well-formed immediately before
+    /// calling that fn, and hence the *callee* can assume that its
+    /// argument types are well-formed. This may imply certain relationships
+    /// between generic parameters. For example:
+    /// ```
+    /// fn foo<'a,T>(x: &'a T) {}
+    /// ```
+    /// can only be called with a `'a` and `T` such that `&'a T` is WF.
+    /// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`.
+    ///
+    /// # Parameters
+    ///
+    /// - `param_env`, the where-clauses in scope
+    /// - `body_id`, the body-id to use when normalizing assoc types.
+    ///   Note that this may cause outlives obligations to be injected
+    ///   into the inference context with this body-id.
+    /// - `ty`, the type that we are supposed to assume is WF.
+    #[instrument(level = "debug", skip(self, param_env, body_id))]
+    fn implied_outlives_bounds(
+        &self,
+        param_env: ty::ParamEnv<'tcx>,
+        body_id: hir::HirId,
+        ty: Ty<'tcx>,
+    ) -> Vec<OutlivesBound<'tcx>> {
+        let span = self.tcx.hir().span(body_id);
+        let result = param_env
+            .and(type_op::implied_outlives_bounds::ImpliedOutlivesBounds { ty })
+            .fully_perform(self);
+        let result = match result {
+            Ok(r) => r,
+            Err(NoSolution) => {
+                self.tcx.sess.delay_span_bug(
+                    span,
+                    "implied_outlives_bounds failed to solve all obligations",
+                );
+                return vec![];
+            }
+        };
+
+        let TypeOpOutput { output, constraints, .. } = result;
+
+        if let Some(constraints) = constraints {
+            // Instantiation may have produced new inference variables and constraints on those
+            // variables. Process these constraints.
+            let mut fulfill_cx = <dyn TraitEngine<'tcx>>::new(self.tcx);
+            let cause = ObligationCause::misc(span, body_id);
+            for &constraint in &constraints.outlives {
+                let obligation = self.query_outlives_constraint_to_obligation(
+                    constraint,
+                    cause.clone(),
+                    param_env,
+                );
+                fulfill_cx.register_predicate_obligation(self, obligation);
+            }
+            if !constraints.member_constraints.is_empty() {
+                span_bug!(span, "{:#?}", constraints.member_constraints);
+            }
+            let errors = fulfill_cx.select_all_or_error(self);
+            if !errors.is_empty() {
+                self.tcx.sess.delay_span_bug(
+                    span,
+                    "implied_outlives_bounds failed to solve obligations from instantiation",
+                );
+            }
+        };
+
+        output
+    }
+
+    fn implied_bounds_tys(
+        &'a self,
+        param_env: ParamEnv<'tcx>,
+        body_id: HirId,
+        tys: FxHashSet<Ty<'tcx>>,
+    ) -> Bounds<'a, 'tcx> {
+        tys.into_iter()
+            .map(move |ty| {
+                let ty = self.resolve_vars_if_possible(ty);
+                self.implied_outlives_bounds(param_env, body_id, ty)
+            })
+            .flatten()
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index 715b9749268..444ca6471e2 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -554,6 +554,21 @@ impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> {
                     .flatten()
                     .unwrap_or_else(|| ty::Term::Ty(ty.super_fold_with(self)))
                 };
+                // For cases like #95134 we would like to catch overflows early
+                // otherwise they slip away away and cause ICE.
+                let recursion_limit = self.tcx().recursion_limit();
+                if !recursion_limit.value_within_limit(self.depth)
+                    // HACK: Don't overflow when running cargo doc see #100991
+                    && !self.tcx().sess.opts.actually_rustdoc
+                {
+                    let obligation = Obligation::with_depth(
+                        self.cause.clone(),
+                        recursion_limit.0,
+                        self.param_env,
+                        ty,
+                    );
+                    self.selcx.infcx().report_overflow_error(&obligation, true);
+                }
                 debug!(
                     ?self.depth,
                     ?ty,
diff --git a/compiler/rustc_trait_selection/src/traits/util.rs b/compiler/rustc_trait_selection/src/traits/util.rs
index d2500601662..0f5dff01c66 100644
--- a/compiler/rustc_trait_selection/src/traits/util.rs
+++ b/compiler/rustc_trait_selection/src/traits/util.rs
@@ -11,8 +11,6 @@ use rustc_middle::ty::{self, ImplSubject, ToPredicate, Ty, TyCtxt, TypeVisitable
 use super::{Normalized, Obligation, ObligationCause, PredicateObligation, SelectionContext};
 pub use rustc_infer::traits::{self, util::*};
 
-use std::iter;
-
 ///////////////////////////////////////////////////////////////////////////
 // `TraitAliasExpander` iterator
 ///////////////////////////////////////////////////////////////////////////
@@ -210,7 +208,7 @@ pub fn impl_subject_and_oblig<'a, 'tcx>(
     let Normalized { value: predicates, obligations: normalization_obligations2 } =
         super::normalize(selcx, param_env, ObligationCause::dummy(), predicates);
     let impl_obligations =
-        predicates_for_generics(ObligationCause::dummy(), 0, param_env, predicates);
+        super::predicates_for_generics(|_, _| ObligationCause::dummy(), param_env, predicates);
 
     let impl_obligations = impl_obligations
         .chain(normalization_obligations1.into_iter())
@@ -219,27 +217,6 @@ pub fn impl_subject_and_oblig<'a, 'tcx>(
     (subject, impl_obligations)
 }
 
-pub fn predicates_for_generics<'tcx>(
-    cause: ObligationCause<'tcx>,
-    recursion_depth: usize,
-    param_env: ty::ParamEnv<'tcx>,
-    generic_bounds: ty::InstantiatedPredicates<'tcx>,
-) -> impl Iterator<Item = PredicateObligation<'tcx>> {
-    debug!("predicates_for_generics(generic_bounds={:?})", generic_bounds);
-
-    iter::zip(generic_bounds.predicates, generic_bounds.spans).map(move |(predicate, span)| {
-        let cause = match *cause.code() {
-            traits::ItemObligation(def_id) if !span.is_dummy() => traits::ObligationCause::new(
-                cause.span,
-                cause.body_id,
-                traits::BindingObligation(def_id, span),
-            ),
-            _ => cause.clone(),
-        };
-        Obligation { cause, recursion_depth, param_env, predicate }
-    })
-}
-
 pub fn predicate_for_trait_ref<'tcx>(
     tcx: TyCtxt<'tcx>,
     cause: ObligationCause<'tcx>,
diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs
index 7a5e67ff74b..4bd179d2391 100644
--- a/compiler/rustc_trait_selection/src/traits/wf.rs
+++ b/compiler/rustc_trait_selection/src/traits/wf.rs
@@ -711,7 +711,7 @@ impl<'tcx> WfPredicates<'tcx> {
         iter::zip(iter::zip(predicates.predicates, predicates.spans), origins.into_iter().rev())
             .map(|((mut pred, span), origin_def_id)| {
                 let code = if span.is_dummy() {
-                    traits::MiscObligation
+                    traits::ItemObligation(origin_def_id)
                 } else {
                     traits::BindingObligation(origin_def_id, span)
                 };