Auto merge of #112875 - compiler-errors:negative-coherence-rework, r=lcnr

Rework negative coherence to properly consider impls that only partly overlap

This PR implements a modified negative coherence that handles impls that only have partial overlap.

It does this by:
1. taking both impl trait refs, instantiating them with infer vars
2. equating both trait refs
3. taking the equated trait ref (which represents the two impls' intersection), and resolving any vars
4. plugging all remaining infer vars with placeholder types

these placeholder-plugged trait refs can then be used normally with the new trait solver, since we no longer have to worry about the issue with infer vars in param-envs.

We use the **new trait solver** to reason correctly about unnormalized trait refs (due to deferred projection equality), since this avoid having to normalize anything under param-envs with infer vars in them.

This PR then additionally:
* removes the `FnPtr` knowable hack by implementing proper negative `FnPtr` trait bounds for rigid types.

---

An example:

Consider these two partially overlapping impls:

```
impl<T, U> PartialEq<&U> for &T where T: PartialEq<U> {}
impl<F> PartialEq<F> for F where F: FnPtr {}
```

Under the old algorithm, we would take one of these impls and replace it with infer vars, then try unifying it with the other impl under identity substitutions. This is not possible in either direction, since it either sets `T = U`, or tries to equate `F = &?0`.

Under the new algorithm, we try to unify `?0: PartialEq<?0>` with `&?1: PartialEq<&?2>`. This gives us `?0 = &?1 = &?2` and thus `?1 = ?2`. The intersection of these two trait refs therefore looks like: `&?1: PartialEq<&?1>`. After plugging this with placeholders, we get a trait ref that looks like `&!0: PartialEq<&!0>`, with the first impl having substs `?T = ?U = !0` and the second having substs `?F = &!0`[^1].

Then we can take the param-env from the first impl, and try to prove the negated where clause of the second.

We know that `&!0: !FnPtr` never holds, since it's a rigid type that is also not a fn ptr, we successfully detect that these impls may never overlap.

[^1]: For the purposes of this example, I just ignored lifetimes, since it doesn't really matter.

19 files changed, 314 insertions, 143 deletions

diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 5d6d46e16b7..739d4fa886e 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -233,6 +233,7 @@ impl MainDefinition {
 #[derive(Clone, Debug, TypeFoldable, TypeVisitable)]
 pub struct ImplHeader<'tcx> {
     pub impl_def_id: DefId,
+    pub impl_args: ty::GenericArgsRef<'tcx>,
     pub self_ty: Ty<'tcx>,
     pub trait_ref: Option<TraitRef<'tcx>>,
     pub predicates: Vec<Predicate<'tcx>>,
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 0c214ca8753..6562bc86f99 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -37,6 +37,8 @@ pub(super) trait GoalKind<'tcx>:
 
     fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>;
 
+    fn polarity(self) -> ty::ImplPolarity;
+
     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
 
     fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs b/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs
index 4950a444ffb..be631552c57 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs
@@ -101,6 +101,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         self.projection_ty.trait_ref(tcx)
     }
 
+    fn polarity(self) -> ty::ImplPolarity {
+        ty::ImplPolarity::Positive
+    }
+
     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
         self.with_self_ty(tcx, self_ty)
     }
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index fa91a125b6a..7c4f6562f10 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -22,6 +22,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         self.trait_ref
     }
 
+    fn polarity(self) -> ty::ImplPolarity {
+        self.polarity
+    }
+
     fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
         self.with_self_ty(tcx, self_ty)
     }
@@ -238,14 +242,25 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         ecx: &mut EvalCtxt<'_, 'tcx>,
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
-        if goal.predicate.polarity != ty::ImplPolarity::Positive {
-            return Err(NoSolution);
-        }
-
-        if let ty::FnPtr(..) = goal.predicate.self_ty().kind() {
-            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-        } else {
-            Err(NoSolution)
+        let self_ty = goal.predicate.self_ty();
+        match goal.predicate.polarity {
+            ty::ImplPolarity::Positive => {
+                if self_ty.is_fn_ptr() {
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                } else {
+                    Err(NoSolution)
+                }
+            }
+            ty::ImplPolarity::Negative => {
+                // If a type is rigid and not a fn ptr, then we know for certain
+                // that it does *not* implement `FnPtr`.
+                if !self_ty.is_fn_ptr() && self_ty.is_known_rigid() {
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                } else {
+                    Err(NoSolution)
+                }
+            }
+            ty::ImplPolarity::Reservation => bug!(),
         }
     }
 
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 29b0c7189f9..dcf5fd86929 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -9,20 +9,18 @@ use crate::infer::InferOk;
 use crate::solve::inspect;
 use crate::solve::inspect::{InspectGoal, ProofTreeInferCtxtExt, ProofTreeVisitor};
 use crate::traits::engine::TraitEngineExt;
-use crate::traits::outlives_bounds::InferCtxtExt as _;
 use crate::traits::query::evaluate_obligation::InferCtxtExt;
 use crate::traits::select::{IntercrateAmbiguityCause, TreatInductiveCycleAs};
 use crate::traits::structural_normalize::StructurallyNormalizeExt;
-use crate::traits::util::impl_subject_and_oblig;
 use crate::traits::NormalizeExt;
 use crate::traits::SkipLeakCheck;
 use crate::traits::{
-    self, Obligation, ObligationCause, ObligationCtxt, PredicateObligation, PredicateObligations,
+    Obligation, ObligationCause, ObligationCtxt, PredicateObligation, PredicateObligations,
     SelectionContext,
 };
 use rustc_data_structures::fx::FxIndexSet;
 use rustc_errors::Diagnostic;
-use rustc_hir::def_id::{DefId, CRATE_DEF_ID, LOCAL_CRATE};
+use rustc_hir::def_id::{DefId, LOCAL_CRATE};
 use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, TyCtxtInferExt};
 use rustc_infer::traits::{util, TraitEngine};
 use rustc_middle::traits::query::NoSolution;
@@ -32,12 +30,11 @@ use rustc_middle::traits::DefiningAnchor;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::print::with_no_trimmed_paths;
 use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt};
-use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor};
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitor};
 use rustc_session::lint::builtin::COINDUCTIVE_OVERLAP_IN_COHERENCE;
 use rustc_span::symbol::sym;
 use rustc_span::DUMMY_SP;
 use std::fmt::Debug;
-use std::iter;
 use std::ops::ControlFlow;
 
 /// Whether we do the orphan check relative to this crate or
@@ -142,16 +139,13 @@ pub fn overlapping_impls(
     Some(overlap)
 }
 
-fn with_fresh_ty_vars<'cx, 'tcx>(
-    selcx: &mut SelectionContext<'cx, 'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
-    impl_def_id: DefId,
-) -> ty::ImplHeader<'tcx> {
-    let tcx = selcx.tcx();
-    let impl_args = selcx.infcx.fresh_args_for_item(DUMMY_SP, impl_def_id);
+fn fresh_impl_header<'tcx>(infcx: &InferCtxt<'tcx>, impl_def_id: DefId) -> ty::ImplHeader<'tcx> {
+    let tcx = infcx.tcx;
+    let impl_args = infcx.fresh_args_for_item(DUMMY_SP, impl_def_id);
 
-    let header = ty::ImplHeader {
+    ty::ImplHeader {
         impl_def_id,
+        impl_args,
         self_ty: tcx.type_of(impl_def_id).instantiate(tcx, impl_args),
         trait_ref: tcx.impl_trait_ref(impl_def_id).map(|i| i.instantiate(tcx, impl_args)),
         predicates: tcx
@@ -160,10 +154,18 @@ fn with_fresh_ty_vars<'cx, 'tcx>(
             .iter()
             .map(|(c, _)| c.as_predicate())
             .collect(),
-    };
+    }
+}
+
+fn fresh_impl_header_normalized<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    impl_def_id: DefId,
+) -> ty::ImplHeader<'tcx> {
+    let header = fresh_impl_header(infcx, impl_def_id);
 
     let InferOk { value: mut header, obligations } =
-        selcx.infcx.at(&ObligationCause::dummy(), param_env).normalize(header);
+        infcx.at(&ObligationCause::dummy(), param_env).normalize(header);
 
     header.predicates.extend(obligations.into_iter().map(|o| o.predicate));
     header
@@ -206,12 +208,13 @@ fn overlap<'tcx>(
     // empty environment.
     let param_env = ty::ParamEnv::empty();
 
-    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 impl1_header = fresh_impl_header_normalized(selcx.infcx, param_env, impl1_def_id);
+    let impl2_header = fresh_impl_header_normalized(selcx.infcx, param_env, impl2_def_id);
 
     // Equate the headers to find their intersection (the general type, with infer vars,
     // that may apply both impls).
-    let mut obligations = equate_impl_headers(selcx.infcx, &impl1_header, &impl2_header)?;
+    let mut obligations =
+        equate_impl_headers(selcx.infcx, param_env, &impl1_header, &impl2_header)?;
     debug!("overlap: unification check succeeded");
 
     obligations.extend(
@@ -312,20 +315,22 @@ fn overlap<'tcx>(
 #[instrument(level = "debug", skip(infcx), ret)]
 fn equate_impl_headers<'tcx>(
     infcx: &InferCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
     impl1: &ty::ImplHeader<'tcx>,
     impl2: &ty::ImplHeader<'tcx>,
 ) -> Option<PredicateObligations<'tcx>> {
-    let result = match (impl1.trait_ref, impl2.trait_ref) {
-        (Some(impl1_ref), Some(impl2_ref)) => infcx
-            .at(&ObligationCause::dummy(), ty::ParamEnv::empty())
-            .eq(DefineOpaqueTypes::Yes, impl1_ref, impl2_ref),
-        (None, None) => infcx.at(&ObligationCause::dummy(), ty::ParamEnv::empty()).eq(
-            DefineOpaqueTypes::Yes,
-            impl1.self_ty,
-            impl2.self_ty,
-        ),
-        _ => bug!("mk_eq_impl_headers given mismatched impl kinds"),
-    };
+    let result =
+        match (impl1.trait_ref, impl2.trait_ref) {
+            (Some(impl1_ref), Some(impl2_ref)) => infcx
+                .at(&ObligationCause::dummy(), param_env)
+                .eq(DefineOpaqueTypes::Yes, impl1_ref, impl2_ref),
+            (None, None) => infcx.at(&ObligationCause::dummy(), param_env).eq(
+                DefineOpaqueTypes::Yes,
+                impl1.self_ty,
+                impl2.self_ty,
+            ),
+            _ => bug!("mk_eq_impl_headers given mismatched impl kinds"),
+        };
 
     result.map(|infer_ok| infer_ok.obligations).ok()
 }
@@ -391,107 +396,182 @@ fn impl_intersection_has_negative_obligation(
 ) -> 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:
-    let infcx = tcx.infer_ctxt().build();
-    // create a parameter environment corresponding to a (placeholder) instantiation of impl1
-    let impl_env = tcx.param_env(impl1_def_id);
-    let subject1 = match traits::fully_normalize(
-        &infcx,
-        ObligationCause::dummy(),
-        impl_env,
-        tcx.impl_subject(impl1_def_id).instantiate_identity(),
-    ) {
-        Ok(s) => s,
-        Err(err) => {
-            tcx.sess.delay_span_bug(
-                tcx.def_span(impl1_def_id),
-                format!("failed to fully normalize {impl1_def_id:?}: {err:?}"),
-            );
-            return false;
-        }
-    };
+    let ref infcx = tcx.infer_ctxt().intercrate(true).with_next_trait_solver(true).build();
+    let universe = infcx.universe();
 
-    // Attempt to prove that impl2 applies, given all of the above.
-    let selcx = &mut SelectionContext::new(&infcx);
-    let impl2_args = infcx.fresh_args_for_item(DUMMY_SP, impl2_def_id);
-    let (subject2, normalization_obligations) =
-        impl_subject_and_oblig(selcx, impl_env, impl2_def_id, impl2_args, |_, _| {
-            ObligationCause::dummy()
-        });
-
-    // 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)
+    let impl1_header = fresh_impl_header(infcx, impl1_def_id);
+    let param_env =
+        ty::EarlyBinder::bind(tcx.param_env(impl1_def_id)).instantiate(tcx, impl1_header.impl_args);
+
+    let impl2_header = fresh_impl_header(infcx, impl2_def_id);
+
+    // Equate the headers to find their intersection (the general type, with infer vars,
+    // that may apply both impls).
+    let Some(_equate_obligations) =
+        equate_impl_headers(infcx, param_env, &impl1_header, &impl2_header)
     else {
-        debug!("explicit_disjoint: {:?} does not unify with {:?}", subject1, subject2);
         return false;
     };
 
-    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;
-        }
-    }
+    plug_infer_with_placeholders(infcx, universe, (impl1_header.impl_args, impl2_header.impl_args));
 
-    false
+    util::elaborate(tcx, tcx.predicates_of(impl2_def_id).instantiate(tcx, impl2_header.impl_args))
+        .any(|(clause, _)| try_prove_negated_where_clause(infcx, clause, param_env))
 }
 
-/// 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>(
+fn plug_infer_with_placeholders<'tcx>(
     infcx: &InferCtxt<'tcx>,
-    o: &PredicateObligation<'tcx>,
-    body_def_id: DefId,
-) -> bool {
-    // Try to prove a negative obligation exists for super predicates
-    for pred in util::elaborate(infcx.tcx, iter::once(o.predicate)) {
-        if prove_negated_obligation(infcx.fork(), &o.with(infcx.tcx, pred), body_def_id) {
-            return true;
+    universe: ty::UniverseIndex,
+    value: impl TypeVisitable<TyCtxt<'tcx>>,
+) {
+    struct PlugInferWithPlaceholder<'a, 'tcx> {
+        infcx: &'a InferCtxt<'tcx>,
+        universe: ty::UniverseIndex,
+        var: ty::BoundVar,
+    }
+
+    impl<'tcx> PlugInferWithPlaceholder<'_, 'tcx> {
+        fn next_var(&mut self) -> ty::BoundVar {
+            let var = self.var;
+            self.var = self.var + 1;
+            var
+        }
+    }
+
+    impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for PlugInferWithPlaceholder<'_, 'tcx> {
+        fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+            let ty = self.infcx.shallow_resolve(ty);
+            if ty.is_ty_var() {
+                let Ok(InferOk { value: (), obligations }) =
+                    self.infcx.at(&ObligationCause::dummy(), ty::ParamEnv::empty()).eq(
+                        DefineOpaqueTypes::No,
+                        ty,
+                        Ty::new_placeholder(
+                            self.infcx.tcx,
+                            ty::Placeholder {
+                                universe: self.universe,
+                                bound: ty::BoundTy {
+                                    var: self.next_var(),
+                                    kind: ty::BoundTyKind::Anon,
+                                },
+                            },
+                        ),
+                    )
+                else {
+                    bug!()
+                };
+                assert_eq!(obligations, &[]);
+                ControlFlow::Continue(())
+            } else {
+                ty.super_visit_with(self)
+            }
+        }
+
+        fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+            let ct = self.infcx.shallow_resolve(ct);
+            if ct.is_ct_infer() {
+                let Ok(InferOk { value: (), obligations }) =
+                    self.infcx.at(&ObligationCause::dummy(), ty::ParamEnv::empty()).eq(
+                        DefineOpaqueTypes::No,
+                        ct,
+                        ty::Const::new_placeholder(
+                            self.infcx.tcx,
+                            ty::Placeholder { universe: self.universe, bound: self.next_var() },
+                            ct.ty(),
+                        ),
+                    )
+                else {
+                    bug!()
+                };
+                assert_eq!(obligations, &[]);
+                ControlFlow::Continue(())
+            } else {
+                ct.super_visit_with(self)
+            }
+        }
+
+        fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+            if let ty::ReVar(vid) = *r {
+                let r = self
+                    .infcx
+                    .inner
+                    .borrow_mut()
+                    .unwrap_region_constraints()
+                    .opportunistic_resolve_var(self.infcx.tcx, vid);
+                if r.is_var() {
+                    let Ok(InferOk { value: (), obligations }) =
+                        self.infcx.at(&ObligationCause::dummy(), ty::ParamEnv::empty()).eq(
+                            DefineOpaqueTypes::No,
+                            r,
+                            ty::Region::new_placeholder(
+                                self.infcx.tcx,
+                                ty::Placeholder {
+                                    universe: self.universe,
+                                    bound: ty::BoundRegion {
+                                        var: self.next_var(),
+                                        kind: ty::BoundRegionKind::BrAnon,
+                                    },
+                                },
+                            ),
+                        )
+                    else {
+                        bug!()
+                    };
+                    assert_eq!(obligations, &[]);
+                }
+            }
+            ControlFlow::Continue(())
         }
     }
 
-    false
+    value.visit_with(&mut PlugInferWithPlaceholder {
+        infcx,
+        universe,
+        var: ty::BoundVar::from_u32(0),
+    });
 }
 
-#[instrument(level = "debug", skip(infcx))]
-fn prove_negated_obligation<'tcx>(
-    infcx: InferCtxt<'tcx>,
-    o: &PredicateObligation<'tcx>,
-    body_def_id: DefId,
+fn try_prove_negated_where_clause<'tcx>(
+    root_infcx: &InferCtxt<'tcx>,
+    clause: ty::Clause<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
 ) -> bool {
-    let tcx = infcx.tcx;
-
-    let Some(o) = o.flip_polarity(tcx) else {
+    let Some(negative_predicate) = clause.as_predicate().flip_polarity(root_infcx.tcx) else {
         return false;
     };
 
-    let param_env = o.param_env;
-    let ocx = ObligationCtxt::new(&infcx);
-    ocx.register_obligation(o);
-    let errors = ocx.select_all_or_error();
-    if !errors.is_empty() {
+    // FIXME(with_negative_coherence): the infcx has region contraints from equating
+    // the impl headers as requirements. Given that the only region constraints we
+    // get are involving inference regions in the root, it shouldn't matter, but
+    // still sus.
+    //
+    // We probably should just throw away the region obligations registered up until
+    // now, or ideally use them as assumptions when proving the region obligations
+    // that we get from proving the negative predicate below.
+    let ref infcx = root_infcx.fork();
+    let ocx = ObligationCtxt::new(infcx);
+
+    ocx.register_obligation(Obligation::new(
+        infcx.tcx,
+        ObligationCause::dummy(),
+        param_env,
+        negative_predicate,
+    ));
+    if !ocx.select_all_or_error().is_empty() {
         return false;
     }
 
-    let body_def_id = body_def_id.as_local().unwrap_or(CRATE_DEF_ID);
+    // FIXME: We could use the assumed_wf_types from both impls, I think,
+    // if that wasn't implemented just for LocalDefId, and we'd need to do
+    // the normalization ourselves since this is totally fallible...
+    let outlives_env = OutlivesEnvironment::new(param_env);
 
-    let ocx = ObligationCtxt::new(&infcx);
-    let Ok(wf_tys) = ocx.assumed_wf_types(param_env, body_def_id) else {
+    let errors = infcx.resolve_regions(&outlives_env);
+    if !errors.is_empty() {
         return false;
-    };
+    }
 
-    let outlives_env = OutlivesEnvironment::with_bounds(
-        param_env,
-        infcx.implied_bounds_tys(param_env, body_def_id, wf_tys),
-    );
-    infcx.resolve_regions(&outlives_env).is_empty()
+    true
 }
 
 /// Returns whether all impls which would apply to the `trait_ref`
@@ -506,13 +586,6 @@ pub fn trait_ref_is_knowable<'tcx, E: Debug>(
     trait_ref: ty::TraitRef<'tcx>,
     mut lazily_normalize_ty: impl FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
 ) -> Result<Result<(), Conflict>, E> {
-    if Some(trait_ref.def_id) == tcx.lang_items().fn_ptr_trait() {
-        // The only types implementing `FnPtr` are function pointers,
-        // so if there's no impl of `FnPtr` in the current crate,
-        // then such an impl will never be added in the future.
-        return Ok(Ok(()));
-    }
-
     if orphan_check_trait_ref(trait_ref, InCrate::Remote, &mut lazily_normalize_ty)?.is_ok() {
         // A downstream or cousin crate is allowed to implement some
         // substitution of this trait-ref.
diff --git a/compiler/rustc_trait_selection/src/traits/engine.rs b/compiler/rustc_trait_selection/src/traits/engine.rs
index 88f47b03cc8..d9a1a98191d 100644
--- a/compiler/rustc_trait_selection/src/traits/engine.rs
+++ b/compiler/rustc_trait_selection/src/traits/engine.rs
@@ -37,10 +37,10 @@ impl<'tcx> TraitEngineExt<'tcx> for dyn TraitEngine<'tcx> {
             (TraitSolver::Classic, false) | (TraitSolver::NextCoherence, false) => {
                 Box::new(FulfillmentContext::new(infcx))
             }
-            (TraitSolver::Next | TraitSolver::NextCoherence, true) => {
+            (TraitSolver::Classic | TraitSolver::Next | TraitSolver::NextCoherence, true) => {
                 Box::new(NextFulfillmentCtxt::new(infcx))
             }
-            _ => bug!(
+            (TraitSolver::Next, false) => bug!(
                 "incompatible combination of -Ztrait-solver flag ({:?}) and InferCtxt::next_trait_solver ({:?})",
                 infcx.tcx.sess.opts.unstable_opts.trait_solver,
                 infcx.next_trait_solver()
diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
index ee50a36be55..123881d9bc6 100644
--- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
@@ -52,8 +52,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
 
-        // The only way to prove a NotImplemented(T: Foo) predicate is via a negative impl.
-        // There are no compiler built-in rules for this.
+        // Negative trait predicates have different rules than positive trait predicates.
         if obligation.polarity() == ty::ImplPolarity::Negative {
             self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
             self.assemble_candidates_from_impls(obligation, &mut candidates);
@@ -1064,6 +1063,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         candidates: &mut SelectionCandidateSet<'tcx>,
     ) {
         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
+
         match self_ty.skip_binder().kind() {
             ty::FnPtr(_) => candidates.vec.push(BuiltinCandidate { has_nested: false }),
             ty::Bool
diff --git a/library/core/src/lib.rs b/library/core/src/lib.rs
index 03243e31348..a1220d45a5c 100644
--- a/library/core/src/lib.rs
+++ b/library/core/src/lib.rs
@@ -253,6 +253,7 @@
 #![feature(try_blocks)]
 #![feature(unboxed_closures)]
 #![feature(unsized_fn_params)]
+#![feature(with_negative_coherence)]
 // tidy-alphabetical-end
 //
 // Target features:
diff --git a/tests/ui/coherence/coherence-negative-outlives-lifetimes.rs b/tests/ui/coherence/coherence-negative-outlives-lifetimes.rs
index 3acf0d8d39a..0e16d12a181 100644
--- a/tests/ui/coherence/coherence-negative-outlives-lifetimes.rs
+++ b/tests/ui/coherence/coherence-negative-outlives-lifetimes.rs
@@ -1,5 +1,5 @@
 // revisions: stock with_negative_coherence
-//[with_negative_coherence] check-pass
+//[with_negative_coherence] known-bug: unknown
 
 #![feature(negative_impls)]
 #![cfg_attr(with_negative_coherence, feature(with_negative_coherence))]
diff --git a/tests/ui/coherence/coherence-negative-outlives-lifetimes.with_negative_coherence.stderr b/tests/ui/coherence/coherence-negative-outlives-lifetimes.with_negative_coherence.stderr
new file mode 100644
index 00000000000..097cc4e0fe3
--- /dev/null
+++ b/tests/ui/coherence/coherence-negative-outlives-lifetimes.with_negative_coherence.stderr
@@ -0,0 +1,11 @@
+error[E0119]: conflicting implementations of trait `MyTrait<'_>` for type `&_`
+  --> $DIR/coherence-negative-outlives-lifetimes.rs:14:1
+   |
+LL | impl<'a, T: MyPredicate<'a>> MyTrait<'a> for T {}
+   | ---------------------------------------------- first implementation here
+LL | impl<'a, T> MyTrait<'a> for &'a T {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `&_`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0119`.
diff --git a/tests/ui/coherence/coherence-overlap-trait-alias.rs b/tests/ui/coherence/coherence-overlap-trait-alias.rs
index 9d9c76af91d..d42a666c54f 100644
--- a/tests/ui/coherence/coherence-overlap-trait-alias.rs
+++ b/tests/ui/coherence/coherence-overlap-trait-alias.rs
@@ -13,8 +13,6 @@ impl B for u32 {}
 trait C {}
 impl<T: AB> C for T {}
 impl C for u32 {}
-//~^ ERROR
-// FIXME it's giving an ungreat error but unsure if we care given that it's using an internal rustc
-// attribute and an artificial code path for testing purposes
+//~^ ERROR conflicting implementations of trait `C` for type `u32`
 
 fn main() {}
diff --git a/tests/ui/coherence/coherence-overlap-trait-alias.stderr b/tests/ui/coherence/coherence-overlap-trait-alias.stderr
index 668b8319b38..687f3af0040 100644
--- a/tests/ui/coherence/coherence-overlap-trait-alias.stderr
+++ b/tests/ui/coherence/coherence-overlap-trait-alias.stderr
@@ -1,17 +1,11 @@
-error[E0283]: type annotations needed: cannot satisfy `u32: C`
-  --> $DIR/coherence-overlap-trait-alias.rs:15:12
-   |
-LL | impl C for u32 {}
-   |            ^^^
-   |
-note: multiple `impl`s satisfying `u32: C` found
-  --> $DIR/coherence-overlap-trait-alias.rs:14:1
+error[E0119]: conflicting implementations of trait `C` for type `u32`
+  --> $DIR/coherence-overlap-trait-alias.rs:15:1
    |
 LL | impl<T: AB> C for T {}
-   | ^^^^^^^^^^^^^^^^^^^
+   | ------------------- first implementation here
 LL | impl C for u32 {}
-   | ^^^^^^^^^^^^^^
+   | ^^^^^^^^^^^^^^ conflicting implementation for `u32`
 
 error: aborting due to previous error
 
-For more information about this error, try `rustc --explain E0283`.
+For more information about this error, try `rustc --explain E0119`.
diff --git a/tests/ui/coherence/coherence-overlap-with-regions.rs b/tests/ui/coherence/coherence-overlap-with-regions.rs
index 32f01f41801..9945c8e6cfd 100644
--- a/tests/ui/coherence/coherence-overlap-with-regions.rs
+++ b/tests/ui/coherence/coherence-overlap-with-regions.rs
@@ -1,4 +1,10 @@
-// check-pass
+// known-bug: unknown
+
+// This fails because we currently perform negative coherence in coherence mode.
+// This means that when looking for a negative predicate, we also assemble a
+// coherence-unknowable predicate. Since confirming the negative impl has region
+// obligations, we don't prefer the impl over the unknowable predicate
+// unconditionally and instead flounder.
 
 #![feature(negative_impls)]
 #![feature(rustc_attrs)]
diff --git a/tests/ui/coherence/coherence-overlap-with-regions.stderr b/tests/ui/coherence/coherence-overlap-with-regions.stderr
new file mode 100644
index 00000000000..fd25f0978ba
--- /dev/null
+++ b/tests/ui/coherence/coherence-overlap-with-regions.stderr
@@ -0,0 +1,11 @@
+error[E0119]: conflicting implementations of trait `Bar` for type `&_`
+  --> $DIR/coherence-overlap-with-regions.rs:20:1
+   |
+LL | impl<T: Foo> Bar for T {}
+   | ---------------------- first implementation here
+LL | impl<T> Bar for &T where T: 'static {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `&_`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0119`.
diff --git a/tests/ui/coherence/negative-coherence-considering-regions.any_lt.stderr b/tests/ui/coherence/negative-coherence-considering-regions.any_lt.stderr
new file mode 100644
index 00000000000..4cf50b4f208
--- /dev/null
+++ b/tests/ui/coherence/negative-coherence-considering-regions.any_lt.stderr
@@ -0,0 +1,12 @@
+error[E0119]: conflicting implementations of trait `Bar` for type `&_`
+  --> $DIR/negative-coherence-considering-regions.rs:22:1
+   |
+LL | impl<T> Bar for T where T: Foo {}
+   | ------------------------------ first implementation here
+...
+LL | impl<T> Bar for &T {}
+   | ^^^^^^^^^^^^^^^^^^ conflicting implementation for `&_`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0119`.
diff --git a/tests/ui/coherence/negative-coherence-considering-regions.rs b/tests/ui/coherence/negative-coherence-considering-regions.rs
new file mode 100644
index 00000000000..597a5972628
--- /dev/null
+++ b/tests/ui/coherence/negative-coherence-considering-regions.rs
@@ -0,0 +1,29 @@
+// revisions: any_lt static_lt
+//[static_lt] known-bug: unknown
+
+// This fails because we currently perform negative coherence in coherence mode.
+// This means that when looking for a negative predicate, we also assemble a
+// coherence-unknowable predicate. Since confirming the negative impl has region
+// obligations, we don't prefer the impl over the unknowable predicate
+// unconditionally and instead flounder.
+
+#![feature(negative_impls)]
+#![feature(with_negative_coherence)]
+
+trait Foo {}
+
+impl<T> !Foo for &'static T {}
+
+trait Bar {}
+
+impl<T> Bar for T where T: Foo {}
+
+#[cfg(any_lt)]
+impl<T> Bar for &T {}
+//[any_lt]~^ ERROR conflicting implementations of trait `Bar` for type `&_`
+
+#[cfg(static_lt)]
+impl<T> Bar for &'static T {}
+
+
+fn main() {}
diff --git a/tests/ui/coherence/negative-coherence-considering-regions.static_lt.stderr b/tests/ui/coherence/negative-coherence-considering-regions.static_lt.stderr
new file mode 100644
index 00000000000..87e7be2aa44
--- /dev/null
+++ b/tests/ui/coherence/negative-coherence-considering-regions.static_lt.stderr
@@ -0,0 +1,12 @@
+error[E0119]: conflicting implementations of trait `Bar` for type `&'static _`
+  --> $DIR/negative-coherence-considering-regions.rs:26:1
+   |
+LL | impl<T> Bar for T where T: Foo {}
+   | ------------------------------ first implementation here
+...
+LL | impl<T> Bar for &'static T {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `&'static _`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0119`.
diff --git a/tests/ui/impl-trait/negative-reasoning.stderr b/tests/ui/impl-trait/negative-reasoning.stderr
index 6b8cc9e7374..ddce5e7ece2 100644
--- a/tests/ui/impl-trait/negative-reasoning.stderr
+++ b/tests/ui/impl-trait/negative-reasoning.stderr
@@ -7,7 +7,7 @@ LL | impl<T: std::fmt::Debug> AnotherTrait for T {}
 LL | impl AnotherTrait for D<OpaqueType> {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `D<OpaqueType>`
    |
-   = note: upstream crates may add a new impl of trait `std::fmt::Debug` for type `OpaqueType` in future versions
+   = note: upstream crates may add a new impl of trait `std::marker::FnPtr` for type `OpaqueType` in future versions
 
 error: aborting due to previous error
 
diff --git a/tests/ui/type-alias-impl-trait/impl_trait_for_same_tait.stderr b/tests/ui/type-alias-impl-trait/impl_trait_for_same_tait.stderr
index aaf75cc3db9..e35913be899 100644
--- a/tests/ui/type-alias-impl-trait/impl_trait_for_same_tait.stderr
+++ b/tests/ui/type-alias-impl-trait/impl_trait_for_same_tait.stderr
@@ -15,6 +15,8 @@ LL | impl Bop for Bar<()> {}
 ...
 LL | impl Bop for Barr {}
    | ^^^^^^^^^^^^^^^^^ conflicting implementation for `Bar<()>`
+   |
+   = note: upstream crates may add a new impl of trait `std::marker::FnPtr` for type `Barr` in future versions
 
 error[E0119]: conflicting implementations of trait `Bop` for type `Bar<()>`
   --> $DIR/impl_trait_for_same_tait.rs:30:1