1 files changed, 173 insertions, 133 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index e8c5a8fab..1b1285e1b 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -5,7 +5,7 @@
 //! [trait-specialization]: https://rustc-dev-guide.rust-lang.org/traits/specialization.html
 
 use crate::infer::outlives::env::OutlivesEnvironment;
-use crate::infer::{CombinedSnapshot, InferOk};
+use crate::infer::InferOk;
 use crate::traits::outlives_bounds::InferCtxtExt as _;
 use crate::traits::select::IntercrateAmbiguityCause;
 use crate::traits::util::impl_subject_and_oblig;
@@ -23,13 +23,14 @@ use rustc_middle::traits::specialization_graph::OverlapMode;
 use rustc_middle::traits::DefiningAnchor;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt};
-use rustc_middle::ty::{self, ImplSubject, Ty, TyCtxt, TypeVisitor};
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor};
 use rustc_span::symbol::sym;
 use rustc_span::DUMMY_SP;
 use std::fmt::Debug;
 use std::iter;
 use std::ops::ControlFlow;
 
+use super::query::evaluate_obligation::InferCtxtExt;
 use super::NormalizeExt;
 
 /// Whether we do the orphan check relative to this crate or
@@ -62,6 +63,21 @@ pub fn add_placeholder_note(err: &mut Diagnostic) {
     );
 }
 
+#[derive(Debug, Clone, Copy)]
+enum TrackAmbiguityCauses {
+    Yes,
+    No,
+}
+
+impl TrackAmbiguityCauses {
+    fn is_yes(self) -> bool {
+        match self {
+            TrackAmbiguityCauses::Yes => true,
+            TrackAmbiguityCauses::No => false,
+        }
+    }
+}
+
 /// If there are types that satisfy both impls, returns `Some`
 /// with a suitably-freshened `ImplHeader` with those types
 /// substituted. Otherwise, returns `None`.
@@ -97,29 +113,28 @@ pub fn overlapping_impls(
         return None;
     }
 
-    let infcx = tcx
-        .infer_ctxt()
-        .with_opaque_type_inference(DefiningAnchor::Bubble)
-        .intercrate(true)
-        .build();
-    let selcx = &mut SelectionContext::new(&infcx);
-    let overlaps =
-        overlap(selcx, skip_leak_check, impl1_def_id, impl2_def_id, overlap_mode).is_some();
-    if !overlaps {
-        return None;
-    }
+    let _overlap_with_bad_diagnostics = overlap(
+        tcx,
+        TrackAmbiguityCauses::No,
+        skip_leak_check,
+        impl1_def_id,
+        impl2_def_id,
+        overlap_mode,
+    )?;
 
     // In the case where we detect an error, run the check again, but
     // this time tracking intercrate ambiguity causes for better
     // diagnostics. (These take time and can lead to false errors.)
-    let infcx = tcx
-        .infer_ctxt()
-        .with_opaque_type_inference(DefiningAnchor::Bubble)
-        .intercrate(true)
-        .build();
-    let selcx = &mut SelectionContext::new(&infcx);
-    selcx.enable_tracking_intercrate_ambiguity_causes();
-    Some(overlap(selcx, skip_leak_check, impl1_def_id, impl2_def_id, overlap_mode).unwrap())
+    let overlap = overlap(
+        tcx,
+        TrackAmbiguityCauses::Yes,
+        skip_leak_check,
+        impl1_def_id,
+        impl2_def_id,
+        overlap_mode,
+    )
+    .unwrap();
+    Some(overlap)
 }
 
 fn with_fresh_ty_vars<'cx, 'tcx>(
@@ -134,7 +149,12 @@ fn with_fresh_ty_vars<'cx, 'tcx>(
         impl_def_id,
         self_ty: tcx.type_of(impl_def_id).subst(tcx, impl_substs),
         trait_ref: tcx.impl_trait_ref(impl_def_id).map(|i| i.subst(tcx, impl_substs)),
-        predicates: tcx.predicates_of(impl_def_id).instantiate(tcx, impl_substs).predicates,
+        predicates: tcx
+            .predicates_of(impl_def_id)
+            .instantiate(tcx, impl_substs)
+            .iter()
+            .map(|(c, _)| c.as_predicate())
+            .collect(),
     };
 
     let InferOk { value: mut header, obligations } =
@@ -146,40 +166,35 @@ fn with_fresh_ty_vars<'cx, 'tcx>(
 
 /// Can both impl `a` and impl `b` be satisfied by a common type (including
 /// where-clauses)? If so, returns an `ImplHeader` that unifies the two impls.
-fn overlap<'cx, 'tcx>(
-    selcx: &mut SelectionContext<'cx, 'tcx>,
+#[instrument(level = "debug", skip(tcx))]
+fn overlap<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    track_ambiguity_causes: TrackAmbiguityCauses,
     skip_leak_check: SkipLeakCheck,
     impl1_def_id: DefId,
     impl2_def_id: DefId,
     overlap_mode: OverlapMode,
 ) -> Option<OverlapResult<'tcx>> {
-    debug!(
-        "overlap(impl1_def_id={:?}, impl2_def_id={:?}, overlap_mode={:?})",
-        impl1_def_id, impl2_def_id, overlap_mode
-    );
-
-    selcx.infcx.probe_maybe_skip_leak_check(skip_leak_check.is_yes(), |snapshot| {
-        overlap_within_probe(selcx, impl1_def_id, impl2_def_id, overlap_mode, snapshot)
-    })
-}
-
-fn overlap_within_probe<'cx, 'tcx>(
-    selcx: &mut SelectionContext<'cx, 'tcx>,
-    impl1_def_id: DefId,
-    impl2_def_id: DefId,
-    overlap_mode: OverlapMode,
-    snapshot: &CombinedSnapshot<'tcx>,
-) -> Option<OverlapResult<'tcx>> {
-    let infcx = selcx.infcx;
-
     if overlap_mode.use_negative_impl() {
-        if negative_impl(infcx.tcx, impl1_def_id, impl2_def_id)
-            || negative_impl(infcx.tcx, impl2_def_id, impl1_def_id)
+        if impl_intersection_has_negative_obligation(tcx, impl1_def_id, impl2_def_id)
+            || impl_intersection_has_negative_obligation(tcx, impl2_def_id, impl1_def_id)
         {
             return None;
         }
     }
 
+    let infcx = tcx
+        .infer_ctxt()
+        .with_opaque_type_inference(DefiningAnchor::Bubble)
+        .skip_leak_check(skip_leak_check.is_yes())
+        .intercrate(true)
+        .with_next_trait_solver(tcx.next_trait_solver_in_coherence())
+        .build();
+    let selcx = &mut SelectionContext::new(&infcx);
+    if track_ambiguity_causes.is_yes() {
+        selcx.enable_tracking_intercrate_ambiguity_causes();
+    }
+
     // For the purposes of this check, we don't bring any placeholder
     // types into scope; instead, we replace the generic types with
     // fresh type variables, and hence we do our evaluations in an
@@ -189,27 +204,40 @@ fn overlap_within_probe<'cx, 'tcx>(
     let impl1_header = with_fresh_ty_vars(selcx, param_env, impl1_def_id);
     let impl2_header = with_fresh_ty_vars(selcx, param_env, impl2_def_id);
 
-    let obligations = equate_impl_headers(selcx.infcx, &impl1_header, &impl2_header)?;
+    // Equate the headers to find their intersection (the general type, with infer vars,
+    // that may apply both impls).
+    let equate_obligations = equate_impl_headers(selcx.infcx, &impl1_header, &impl2_header)?;
     debug!("overlap: unification check succeeded");
 
-    if overlap_mode.use_implicit_negative() {
-        if implicit_negative(selcx, param_env, &impl1_header, impl2_header, obligations) {
-            return None;
-        }
+    if overlap_mode.use_implicit_negative()
+        && impl_intersection_has_impossible_obligation(
+            selcx,
+            param_env,
+            &impl1_header,
+            impl2_header,
+            equate_obligations,
+        )
+    {
+        return None;
     }
 
-    // We disable the leak when creating the `snapshot` by using
-    // `infcx.probe_maybe_disable_leak_check`.
-    if infcx.leak_check(true, snapshot).is_err() {
+    // We toggle the `leak_check` by using `skip_leak_check` when constructing the
+    // inference context, so this may be a noop.
+    if infcx.leak_check(ty::UniverseIndex::ROOT, None).is_err() {
         debug!("overlap: leak check failed");
         return None;
     }
 
     let intercrate_ambiguity_causes = selcx.take_intercrate_ambiguity_causes();
     debug!("overlap: intercrate_ambiguity_causes={:#?}", intercrate_ambiguity_causes);
-
-    let involves_placeholder =
-        matches!(selcx.infcx.region_constraints_added_in_snapshot(snapshot), Some(true));
+    let involves_placeholder = infcx
+        .inner
+        .borrow_mut()
+        .unwrap_region_constraints()
+        .data()
+        .constraints
+        .iter()
+        .any(|c| c.0.involves_placeholders());
 
     let impl_header = selcx.infcx.resolve_vars_if_possible(impl1_header);
     Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder })
@@ -236,55 +264,55 @@ fn equate_impl_headers<'tcx>(
     result.map(|infer_ok| infer_ok.obligations).ok()
 }
 
-/// Given impl1 and impl2 check if both impls can be satisfied by a common type (including
-/// where-clauses) If so, return false, otherwise return true, they are disjoint.
-fn implicit_negative<'cx, 'tcx>(
+/// Check if both impls can be satisfied by a common type by considering whether
+/// any of either impl's obligations is not known to hold.
+///
+/// For example, given these two impls:
+///     `impl From<MyLocalType> for Box<dyn Error>` (in my crate)
+///     `impl<E> From<E> for Box<dyn Error> where E: Error` (in libstd)
+///
+/// After replacing both impl headers with inference vars (which happens before
+/// this function is called), we get:
+///     `Box<dyn Error>: From<MyLocalType>`
+///     `Box<dyn Error>: From<?E>`
+///
+/// This gives us `?E = MyLocalType`. We then certainly know that `MyLocalType: Error`
+/// never holds in intercrate mode since a local impl does not exist, and a
+/// downstream impl cannot be added -- therefore can consider the intersection
+/// of the two impls above to be empty.
+///
+/// Importantly, this works even if there isn't a `impl !Error for MyLocalType`.
+fn impl_intersection_has_impossible_obligation<'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     impl1_header: &ty::ImplHeader<'tcx>,
     impl2_header: ty::ImplHeader<'tcx>,
     obligations: PredicateObligations<'tcx>,
 ) -> bool {
-    // There's no overlap if obligations are unsatisfiable or if the obligation negated is
-    // satisfied.
-    //
-    // For example, given these two impl headers:
-    //
-    // `impl<'a> From<&'a str> for Box<dyn Error>`
-    // `impl<E> From<E> for Box<dyn Error> where E: Error`
-    //
-    // So we have:
-    //
-    // `Box<dyn Error>: From<&'?a str>`
-    // `Box<dyn Error>: From<?E>`
-    //
-    // After equating the two headers:
-    //
-    // `Box<dyn Error> = Box<dyn Error>`
-    // So, `?E = &'?a str` and then given the where clause `&'?a str: Error`.
-    //
-    // If the obligation `&'?a str: Error` holds, it means that there's overlap. If that doesn't
-    // hold we need to check if `&'?a str: !Error` holds, if doesn't hold there's overlap because
-    // at some point an impl for `&'?a str: Error` could be added.
-    debug!(
-        "implicit_negative(impl1_header={:?}, impl2_header={:?}, obligations={:?})",
-        impl1_header, impl2_header, obligations
-    );
     let infcx = selcx.infcx;
-    let opt_failing_obligation = impl1_header
-        .predicates
-        .iter()
-        .copied()
-        .chain(impl2_header.predicates)
-        .map(|p| infcx.resolve_vars_if_possible(p))
-        .map(|p| Obligation {
-            cause: ObligationCause::dummy(),
-            param_env,
-            recursion_depth: 0,
-            predicate: p,
+
+    let obligation_guaranteed_to_fail = move |obligation: &PredicateObligation<'tcx>| {
+        if infcx.next_trait_solver() {
+            infcx.evaluate_obligation(obligation).map_or(false, |result| !result.may_apply())
+        } else {
+            // We use `evaluate_root_obligation` to correctly track
+            // intercrate ambiguity clauses. We do not need this in the
+            // new solver.
+            selcx.evaluate_root_obligation(obligation).map_or(
+                false, // Overflow has occurred, and treat the obligation as possibly holding.
+                |result| !result.may_apply(),
+            )
+        }
+    };
+
+    let opt_failing_obligation = [&impl1_header.predicates, &impl2_header.predicates]
+        .into_iter()
+        .flatten()
+        .map(|&predicate| {
+            Obligation::new(infcx.tcx, ObligationCause::dummy(), param_env, predicate)
         })
         .chain(obligations)
-        .find(|o| !selcx.predicate_may_hold_fatal(o));
+        .find(obligation_guaranteed_to_fail);
 
     if let Some(failing_obligation) = opt_failing_obligation {
         debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
@@ -294,9 +322,27 @@ fn implicit_negative<'cx, 'tcx>(
     }
 }
 
-/// Given impl1 and impl2 check if both impls are never satisfied by a common type (including
-/// where-clauses) If so, return true, they are disjoint and false otherwise.
-fn negative_impl(tcx: TyCtxt<'_>, impl1_def_id: DefId, impl2_def_id: DefId) -> bool {
+/// Check if both impls can be satisfied by a common type by considering whether
+/// any of first impl's obligations is known not to hold *via a negative predicate*.
+///
+/// For example, given these two impls:
+///     `struct MyCustomBox<T: ?Sized>(Box<T>);`
+///     `impl From<&str> for MyCustomBox<dyn Error>` (in my crate)
+///     `impl<E> From<E> for MyCustomBox<dyn Error> where E: Error` (in my crate)
+///
+/// After replacing the second impl's header with inference vars, we get:
+///     `MyCustomBox<dyn Error>: From<&str>`
+///     `MyCustomBox<dyn Error>: From<?E>`
+///
+/// This gives us `?E = &str`. We then try to prove the first impl's predicates
+/// after negating, giving us `&str: !Error`. This is a negative impl provided by
+/// libstd, and therefore we can guarantee for certain that libstd will never add
+/// a positive impl for `&str: Error` (without it being a breaking change).
+fn impl_intersection_has_negative_obligation(
+    tcx: TyCtxt<'_>,
+    impl1_def_id: DefId,
+    impl2_def_id: DefId,
+) -> bool {
     debug!("negative_impl(impl1_def_id={:?}, impl2_def_id={:?})", impl1_def_id, impl2_def_id);
 
     // Create an infcx, taking the predicates of impl1 as assumptions:
@@ -322,57 +368,45 @@ fn negative_impl(tcx: TyCtxt<'_>, impl1_def_id: DefId, impl2_def_id: DefId) -> b
     // Attempt to prove that impl2 applies, given all of the above.
     let selcx = &mut SelectionContext::new(&infcx);
     let impl2_substs = infcx.fresh_substs_for_item(DUMMY_SP, impl2_def_id);
-    let (subject2, obligations) =
+    let (subject2, normalization_obligations) =
         impl_subject_and_oblig(selcx, impl_env, impl2_def_id, impl2_substs, |_, _| {
             ObligationCause::dummy()
         });
 
-    !equate(&infcx, impl_env, subject1, subject2, obligations, impl1_def_id)
-}
-
-fn equate<'tcx>(
-    infcx: &InferCtxt<'tcx>,
-    impl_env: ty::ParamEnv<'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, .. }) =
+    // do the impls unify? If not, then it's not currently possible to prove any
+    // obligations about their intersection.
+    let Ok(InferOk { obligations: equate_obligations, .. }) =
         infcx.at(&ObligationCause::dummy(), impl_env).eq(DefineOpaqueTypes::No,subject1, subject2)
     else {
         debug!("explicit_disjoint: {:?} does not unify with {:?}", subject1, subject2);
-        return true;
+        return false;
     };
 
-    let opt_failing_obligation = obligations
-        .into_iter()
-        .chain(more_obligations)
-        .find(|o| negative_impl_exists(infcx, o, body_def_id));
-
-    if let Some(failing_obligation) = opt_failing_obligation {
-        debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
-        false
-    } else {
-        true
+    for obligation in normalization_obligations.into_iter().chain(equate_obligations) {
+        if negative_impl_exists(&infcx, &obligation, impl1_def_id) {
+            debug!("overlap: obligation unsatisfiable {:?}", obligation);
+            return true;
+        }
     }
+
+    false
 }
 
-/// Try to prove that a negative impl exist for the given obligation and its super predicates.
+/// Try to prove that a negative impl exist for the obligation or its supertraits.
+///
+/// If such a negative impl exists, then the obligation definitely must not hold
+/// due to coherence, even if it's not necessarily "knowable" in this crate. Any
+/// valid impl downstream would not be able to exist due to the overlapping
+/// negative impl.
 #[instrument(level = "debug", skip(infcx))]
 fn negative_impl_exists<'tcx>(
     infcx: &InferCtxt<'tcx>,
     o: &PredicateObligation<'tcx>,
     body_def_id: DefId,
 ) -> bool {
-    if resolve_negative_obligation(infcx.fork(), o, body_def_id) {
-        return true;
-    }
-
     // Try to prove a negative obligation exists for super predicates
     for pred in util::elaborate(infcx.tcx, iter::once(o.predicate)) {
-        if resolve_negative_obligation(infcx.fork(), &o.with(infcx.tcx, pred), body_def_id) {
+        if prove_negated_obligation(infcx.fork(), &o.with(infcx.tcx, pred), body_def_id) {
             return true;
         }
     }
@@ -381,7 +415,7 @@ fn negative_impl_exists<'tcx>(
 }
 
 #[instrument(level = "debug", skip(infcx))]
-fn resolve_negative_obligation<'tcx>(
+fn prove_negated_obligation<'tcx>(
     infcx: InferCtxt<'tcx>,
     o: &PredicateObligation<'tcx>,
     body_def_id: DefId,
@@ -403,7 +437,11 @@ fn resolve_negative_obligation<'tcx>(
     let body_def_id = body_def_id.as_local().unwrap_or(CRATE_DEF_ID);
 
     let ocx = ObligationCtxt::new(&infcx);
-    let wf_tys = ocx.assumed_wf_types(param_env, DUMMY_SP, body_def_id);
+    let Ok(wf_tys) = ocx.assumed_wf_types(param_env, body_def_id)
+    else {
+        return false;
+    };
+
     let outlives_env = OutlivesEnvironment::with_bounds(
         param_env,
         infcx.implied_bounds_tys(param_env, body_def_id, wf_tys),
@@ -676,7 +714,9 @@ impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for OrphanChecker<'tcx> {
             | ty::RawPtr(..)
             | ty::Never
             | ty::Tuple(..)
-            | ty::Alias(ty::Projection | ty::Inherent, ..) => self.found_non_local_ty(ty),
+            | ty::Alias(ty::Projection | ty::Inherent | ty::Weak, ..) => {
+                self.found_non_local_ty(ty)
+            }
 
             ty::Param(..) => self.found_param_ty(ty),