Auto merge of #90104 - spastorino:coherence-for-negative-trait, r=nikomatsakis

Implement coherence checks for negative trait impls

The main purpose of this PR is to be able to [move Error trait to core](https://github.com/rust-lang/project-error-handling/issues/3).

This feature is necessary to handle the following from impl on box.

```rust
impl From<&str> for Box<dyn Error> { ... }
```

Without having negative traits affect coherence moving the error trait into `core` and moving that `From` impl to `alloc` will cause the from impl to no longer compiler because of a potential future incompatibility. The compiler indicates that `&str` _could_ introduce an `Error` impl in the future, and thus prevents the `From` impl in `alloc` that would cause overlap with `From<E: Error> for Box<dyn Error>`. Adding `impl !Error for &str {}` with the negative trait coherence feature will disable this error by encoding a stability guarantee that `&str` will never implement `Error`, making the `From` impl compile.

We would have this in `alloc`:

```rust
impl From<&str> for Box<dyn Error> {} // A
impl<E> From<E> for Box<dyn Error> where E: Error {} // B
```

and this in `core`:

```rust
trait Error {}
impl !Error for &str {}
```

r? `@nikomatsakis`

This PR was built on top of `@yaahc` PR #85764.

Language team proposal: to https://github.com/rust-lang/lang-team/issues/96

38 files changed, 545 insertions, 193 deletions

diff --git a/compiler/rustc_borrowck/src/type_check/canonical.rs b/compiler/rustc_borrowck/src/type_check/canonical.rs
index 7d4df59902a..0fa72ed8241 100644
--- a/compiler/rustc_borrowck/src/type_check/canonical.rs
+++ b/compiler/rustc_borrowck/src/type_check/canonical.rs
@@ -94,6 +94,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
             Some(ty::Binder::dummy(ty::PredicateKind::Trait(ty::TraitPredicate {
                 trait_ref,
                 constness: ty::BoundConstness::NotConst,
+                polarity: ty::ImplPolarity::Positive,
             }))),
             locations,
             category,
diff --git a/compiler/rustc_const_eval/src/transform/check_consts/check.rs b/compiler/rustc_const_eval/src/transform/check_consts/check.rs
index 03e60deea27..85f37c813d8 100644
--- a/compiler/rustc_const_eval/src/transform/check_consts/check.rs
+++ b/compiler/rustc_const_eval/src/transform/check_consts/check.rs
@@ -854,6 +854,7 @@ impl Visitor<'tcx> for Checker<'mir, 'tcx> {
                         Binder::dummy(TraitPredicate {
                             trait_ref,
                             constness: ty::BoundConstness::ConstIfConst,
+                            polarity: ty::ImplPolarity::Positive,
                         }),
                     );
 
diff --git a/compiler/rustc_const_eval/src/transform/check_consts/qualifs.rs b/compiler/rustc_const_eval/src/transform/check_consts/qualifs.rs
index aaeb1eeb043..aa42f8936f3 100644
--- a/compiler/rustc_const_eval/src/transform/check_consts/qualifs.rs
+++ b/compiler/rustc_const_eval/src/transform/check_consts/qualifs.rs
@@ -162,6 +162,7 @@ impl Qualif for NeedsNonConstDrop {
             ty::Binder::dummy(ty::TraitPredicate {
                 trait_ref,
                 constness: ty::BoundConstness::ConstIfConst,
+                polarity: ty::ImplPolarity::Positive,
             }),
         );
 
diff --git a/compiler/rustc_feature/src/builtin_attrs.rs b/compiler/rustc_feature/src/builtin_attrs.rs
index 85b0db468d1..33188d375f5 100644
--- a/compiler/rustc_feature/src/builtin_attrs.rs
+++ b/compiler/rustc_feature/src/builtin_attrs.rs
@@ -556,6 +556,7 @@ pub const BUILTIN_ATTRIBUTES: &[BuiltinAttribute] = &[
     rustc_attr!(TEST, rustc_outlives, Normal, template!(Word)),
     rustc_attr!(TEST, rustc_capture_analysis, Normal, template!(Word)),
     rustc_attr!(TEST, rustc_insignificant_dtor, Normal, template!(Word)),
+    rustc_attr!(TEST, rustc_strict_coherence, Normal, template!(Word)),
     rustc_attr!(TEST, rustc_variance, Normal, template!(Word)),
     rustc_attr!(TEST, rustc_layout, Normal, template!(List: "field1, field2, ...")),
     rustc_attr!(TEST, rustc_regions, Normal, template!(Word)),
diff --git a/compiler/rustc_infer/src/traits/mod.rs b/compiler/rustc_infer/src/traits/mod.rs
index e1d6982f164..e8622b3c819 100644
--- a/compiler/rustc_infer/src/traits/mod.rs
+++ b/compiler/rustc_infer/src/traits/mod.rs
@@ -10,7 +10,7 @@ pub mod util;
 
 use rustc_hir as hir;
 use rustc_middle::ty::error::{ExpectedFound, TypeError};
-use rustc_middle::ty::{self, Const, Ty};
+use rustc_middle::ty::{self, Const, Ty, TyCtxt};
 use rustc_span::Span;
 
 pub use self::FulfillmentErrorCode::*;
@@ -55,6 +55,20 @@ pub struct Obligation<'tcx, T> {
 pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
 
+impl PredicateObligation<'tcx> {
+    /// Flips the polarity of the inner predicate.
+    ///
+    /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
+    pub fn flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<PredicateObligation<'tcx>> {
+        Some(PredicateObligation {
+            cause: self.cause.clone(),
+            param_env: self.param_env,
+            predicate: self.predicate.flip_polarity(tcx)?,
+            recursion_depth: self.recursion_depth,
+        })
+    }
+}
+
 // `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 static_assert_size!(PredicateObligation<'_>, 32);
@@ -129,6 +143,10 @@ impl<'tcx> FulfillmentError<'tcx> {
 }
 
 impl<'tcx> TraitObligation<'tcx> {
+    pub fn polarity(&self) -> ty::ImplPolarity {
+        self.predicate.skip_binder().polarity
+    }
+
     pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
         self.predicate.map_bound(|p| p.self_ty())
     }
diff --git a/compiler/rustc_middle/src/traits/select.rs b/compiler/rustc_middle/src/traits/select.rs
index 6720493cd3c..560660517f3 100644
--- a/compiler/rustc_middle/src/traits/select.rs
+++ b/compiler/rustc_middle/src/traits/select.rs
@@ -12,12 +12,14 @@ use rustc_hir::def_id::DefId;
 use rustc_query_system::cache::Cache;
 
 pub type SelectionCache<'tcx> = Cache<
-    ty::ConstnessAnd<ty::ParamEnvAnd<'tcx, ty::TraitRef<'tcx>>>,
+    (ty::ConstnessAnd<ty::ParamEnvAnd<'tcx, ty::TraitRef<'tcx>>>, ty::ImplPolarity),
     SelectionResult<'tcx, SelectionCandidate<'tcx>>,
 >;
 
-pub type EvaluationCache<'tcx> =
-    Cache<ty::ParamEnvAnd<'tcx, ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>>, EvaluationResult>;
+pub type EvaluationCache<'tcx> = Cache<
+    (ty::ParamEnvAnd<'tcx, ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>>, ty::ImplPolarity),
+    EvaluationResult,
+>;
 
 /// The selection process begins by considering all impls, where
 /// clauses, and so forth that might resolve an obligation. Sometimes
@@ -101,7 +103,7 @@ pub enum SelectionCandidate<'tcx> {
         /// `false` if there are no *further* obligations.
         has_nested: bool,
     },
-    ParamCandidate(ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>),
+    ParamCandidate((ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>, ty::ImplPolarity)),
     ImplCandidate(DefId),
     AutoImplCandidate(DefId),
 
diff --git a/compiler/rustc_middle/src/ty/error.rs b/compiler/rustc_middle/src/ty/error.rs
index bac681bd96f..2bd9415171d 100644
--- a/compiler/rustc_middle/src/ty/error.rs
+++ b/compiler/rustc_middle/src/ty/error.rs
@@ -34,6 +34,7 @@ impl<T> ExpectedFound<T> {
 pub enum TypeError<'tcx> {
     Mismatch,
     ConstnessMismatch(ExpectedFound<ty::BoundConstness>),
+    PolarityMismatch(ExpectedFound<ty::ImplPolarity>),
     UnsafetyMismatch(ExpectedFound<hir::Unsafety>),
     AbiMismatch(ExpectedFound<abi::Abi>),
     Mutability,
@@ -104,6 +105,9 @@ impl<'tcx> fmt::Display for TypeError<'tcx> {
             ConstnessMismatch(values) => {
                 write!(f, "expected {} bound, found {} bound", values.expected, values.found)
             }
+            PolarityMismatch(values) => {
+                write!(f, "expected {} polarity, found {} polarity", values.expected, values.found)
+            }
             UnsafetyMismatch(values) => {
                 write!(f, "expected {} fn, found {} fn", values.expected, values.found)
             }
@@ -212,10 +216,9 @@ impl<'tcx> TypeError<'tcx> {
         use self::TypeError::*;
         match self {
             CyclicTy(_) | CyclicConst(_) | UnsafetyMismatch(_) | ConstnessMismatch(_)
-            | Mismatch | AbiMismatch(_) | FixedArraySize(_) | ArgumentSorts(..) | Sorts(_)
-            | IntMismatch(_) | FloatMismatch(_) | VariadicMismatch(_) | TargetFeatureCast(_) => {
-                false
-            }
+            | PolarityMismatch(_) | Mismatch | AbiMismatch(_) | FixedArraySize(_)
+            | ArgumentSorts(..) | Sorts(_) | IntMismatch(_) | FloatMismatch(_)
+            | VariadicMismatch(_) | TargetFeatureCast(_) => false,
 
             Mutability
             | ArgumentMutability(_)
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 20d07bdc48a..cf47da157d1 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -164,7 +164,18 @@ pub struct ImplHeader<'tcx> {
     pub predicates: Vec<Predicate<'tcx>>,
 }
 
-#[derive(Copy, Clone, PartialEq, TyEncodable, TyDecodable, HashStable, Debug)]
+#[derive(
+    Copy,
+    Clone,
+    PartialEq,
+    Eq,
+    Hash,
+    TyEncodable,
+    TyDecodable,
+    HashStable,
+    Debug,
+    TypeFoldable
+)]
 pub enum ImplPolarity {
     /// `impl Trait for Type`
     Positive,
@@ -177,6 +188,27 @@ pub enum ImplPolarity {
     Reservation,
 }
 
+impl ImplPolarity {
+    /// Flips polarity by turning `Positive` into `Negative` and `Negative` into `Positive`.
+    pub fn flip(&self) -> Option<ImplPolarity> {
+        match self {
+            ImplPolarity::Positive => Some(ImplPolarity::Negative),
+            ImplPolarity::Negative => Some(ImplPolarity::Positive),
+            ImplPolarity::Reservation => None,
+        }
+    }
+}
+
+impl fmt::Display for ImplPolarity {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Positive => f.write_str("positive"),
+            Self::Negative => f.write_str("negative"),
+            Self::Reservation => f.write_str("reservation"),
+        }
+    }
+}
+
 #[derive(Clone, Debug, PartialEq, Eq, Copy, Hash, TyEncodable, TyDecodable, HashStable)]
 pub enum Visibility {
     /// Visible everywhere (including in other crates).
@@ -459,6 +491,29 @@ impl<'tcx> Predicate<'tcx> {
     pub fn kind(self) -> Binder<'tcx, PredicateKind<'tcx>> {
         self.inner.kind
     }
+
+    /// Flips the polarity of a Predicate.
+    ///
+    /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
+    pub fn flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<Predicate<'tcx>> {
+        let kind = self
+            .inner
+            .kind
+            .map_bound(|kind| match kind {
+                PredicateKind::Trait(TraitPredicate { trait_ref, constness, polarity }) => {
+                    Some(PredicateKind::Trait(TraitPredicate {
+                        trait_ref,
+                        constness,
+                        polarity: polarity.flip()?,
+                    }))
+                }
+
+                _ => None,
+            })
+            .transpose()?;
+
+        Some(tcx.mk_predicate(kind))
+    }
 }
 
 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Predicate<'tcx> {
@@ -654,6 +709,8 @@ pub struct TraitPredicate<'tcx> {
     pub trait_ref: TraitRef<'tcx>,
 
     pub constness: BoundConstness,
+
+    pub polarity: ImplPolarity,
 }
 
 pub type PolyTraitPredicate<'tcx> = ty::Binder<'tcx, TraitPredicate<'tcx>>;
@@ -788,7 +845,11 @@ impl<'tcx> ToPredicate<'tcx> for ConstnessAnd<PolyTraitRef<'tcx>> {
     fn to_predicate(self, tcx: TyCtxt<'tcx>) -> Predicate<'tcx> {
         self.value
             .map_bound(|trait_ref| {
-                PredicateKind::Trait(ty::TraitPredicate { trait_ref, constness: self.constness })
+                PredicateKind::Trait(ty::TraitPredicate {
+                    trait_ref,
+                    constness: self.constness,
+                    polarity: ty::ImplPolarity::Positive,
+                })
             })
             .to_predicate(tcx)
     }
diff --git a/compiler/rustc_middle/src/ty/relate.rs b/compiler/rustc_middle/src/ty/relate.rs
index 2c786538014..8b20e1eec9a 100644
--- a/compiler/rustc_middle/src/ty/relate.rs
+++ b/compiler/rustc_middle/src/ty/relate.rs
@@ -797,6 +797,20 @@ impl<'tcx> Relate<'tcx> for GenericArg<'tcx> {
     }
 }
 
+impl<'tcx> Relate<'tcx> for ty::ImplPolarity {
+    fn relate<R: TypeRelation<'tcx>>(
+        relation: &mut R,
+        a: ty::ImplPolarity,
+        b: ty::ImplPolarity,
+    ) -> RelateResult<'tcx, ty::ImplPolarity> {
+        if a != b {
+            Err(TypeError::PolarityMismatch(expected_found(relation, a, b)))
+        } else {
+            Ok(a)
+        }
+    }
+}
+
 impl<'tcx> Relate<'tcx> for ty::TraitPredicate<'tcx> {
     fn relate<R: TypeRelation<'tcx>>(
         relation: &mut R,
@@ -806,6 +820,7 @@ impl<'tcx> Relate<'tcx> for ty::TraitPredicate<'tcx> {
         Ok(ty::TraitPredicate {
             trait_ref: relation.relate(a.trait_ref, b.trait_ref)?,
             constness: relation.relate(a.constness, b.constness)?,
+            polarity: relation.relate(a.polarity, b.polarity)?,
         })
     }
 }
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index 8f343ba9fec..d6069395474 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -157,7 +157,7 @@ impl fmt::Debug for ty::TraitPredicate<'tcx> {
         if let ty::BoundConstness::ConstIfConst = self.constness {
             write!(f, "~const ")?;
         }
-        write!(f, "TraitPredicate({:?})", self.trait_ref)
+        write!(f, "TraitPredicate({:?}, polarity:{:?})", self.trait_ref, self.polarity)
     }
 }
 
@@ -365,8 +365,11 @@ impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialPredicate<'a> {
 impl<'a, 'tcx> Lift<'tcx> for ty::TraitPredicate<'a> {
     type Lifted = ty::TraitPredicate<'tcx>;
     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<ty::TraitPredicate<'tcx>> {
-        tcx.lift(self.trait_ref)
-            .map(|trait_ref| ty::TraitPredicate { trait_ref, constness: self.constness })
+        tcx.lift(self.trait_ref).map(|trait_ref| ty::TraitPredicate {
+            trait_ref,
+            constness: self.constness,
+            polarity: self.polarity,
+        })
     }
 }
 
@@ -591,6 +594,7 @@ impl<'a, 'tcx> Lift<'tcx> for ty::error::TypeError<'a> {
         Some(match self {
             Mismatch => Mismatch,
             ConstnessMismatch(x) => ConstnessMismatch(x),
+            PolarityMismatch(x) => PolarityMismatch(x),
             UnsafetyMismatch(x) => UnsafetyMismatch(x),
             AbiMismatch(x) => AbiMismatch(x),
             Mutability => Mutability,
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index d3094b3e6ff..874de3366d7 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -882,6 +882,7 @@ impl<'tcx> PolyTraitRef<'tcx> {
         self.map_bound(|trait_ref| ty::TraitPredicate {
             trait_ref,
             constness: ty::BoundConstness::NotConst,
+            polarity: ty::ImplPolarity::Positive,
         })
     }
 }
diff --git a/compiler/rustc_privacy/src/lib.rs b/compiler/rustc_privacy/src/lib.rs
index 4d4e9432e87..fa34b9abc1e 100644
--- a/compiler/rustc_privacy/src/lib.rs
+++ b/compiler/rustc_privacy/src/lib.rs
@@ -124,9 +124,11 @@ where
 
     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<V::BreakTy> {
         match predicate.kind().skip_binder() {
-            ty::PredicateKind::Trait(ty::TraitPredicate { trait_ref, constness: _ }) => {
-                self.visit_trait(trait_ref)
-            }
+            ty::PredicateKind::Trait(ty::TraitPredicate {
+                trait_ref,
+                constness: _,
+                polarity: _,
+            }) => self.visit_trait(trait_ref),
             ty::PredicateKind::Projection(ty::ProjectionPredicate { projection_ty, ty }) => {
                 ty.visit_with(self)?;
                 self.visit_projection_ty(projection_ty)
diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs
index 476809c787f..3e6526d147e 100644
--- a/compiler/rustc_span/src/symbol.rs
+++ b/compiler/rustc_span/src/symbol.rs
@@ -1141,6 +1141,7 @@ symbols! {
         rustc_specialization_trait,
         rustc_stable,
         rustc_std_internal_symbol,
+        rustc_strict_coherence,
         rustc_symbol_name,
         rustc_synthetic,
         rustc_test_marker,
diff --git a/compiler/rustc_trait_selection/src/traits/auto_trait.rs b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
index 622c9edc434..6452b520452 100644
--- a/compiler/rustc_trait_selection/src/traits/auto_trait.rs
+++ b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
@@ -286,6 +286,8 @@ impl AutoTraitFinder<'tcx> {
                 substs: infcx.tcx.mk_substs_trait(ty, &[]),
             },
             constness: ty::BoundConstness::NotConst,
+            // Auto traits are positive
+            polarity: ty::ImplPolarity::Positive,
         }));
 
         let computed_preds = param_env.caller_bounds().iter();
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 668a74bd697..42d3194aed4 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -5,9 +5,12 @@
 //! [trait-specialization]: https://rustc-dev-guide.rust-lang.org/traits/specialization.html
 
 use crate::infer::{CombinedSnapshot, InferOk, TyCtxtInferExt};
+use crate::traits::query::evaluate_obligation::InferCtxtExt;
 use crate::traits::select::IntercrateAmbiguityCause;
 use crate::traits::SkipLeakCheck;
-use crate::traits::{self, Normalized, Obligation, ObligationCause, SelectionContext};
+use crate::traits::{
+    self, Normalized, Obligation, ObligationCause, PredicateObligation, SelectionContext,
+};
 use rustc_hir::def_id::{DefId, LOCAL_CRATE};
 use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::subst::Subst;
@@ -158,6 +161,19 @@ fn overlap_within_probe(
     b_def_id: DefId,
     snapshot: &CombinedSnapshot<'_, 'tcx>,
 ) -> Option<OverlapResult<'tcx>> {
+    fn loose_check(selcx: &mut SelectionContext<'cx, 'tcx>, o: &PredicateObligation<'tcx>) -> bool {
+        !selcx.predicate_may_hold_fatal(o)
+    }
+
+    fn strict_check(selcx: &SelectionContext<'cx, 'tcx>, o: &PredicateObligation<'tcx>) -> bool {
+        let infcx = selcx.infcx();
+        let tcx = infcx.tcx;
+        o.flip_polarity(tcx)
+            .as_ref()
+            .map(|o| selcx.infcx().predicate_must_hold_modulo_regions(o))
+            .unwrap_or(false)
+    }
+
     // 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
@@ -184,8 +200,29 @@ fn overlap_within_probe(
 
     debug!("overlap: unification check succeeded");
 
-    // Are any of the obligations unsatisfiable? If so, no overlap.
+    // 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.
     let infcx = selcx.infcx();
+    let tcx = infcx.tcx;
     let opt_failing_obligation = a_impl_header
         .predicates
         .iter()
@@ -199,7 +236,17 @@ fn overlap_within_probe(
             predicate: p,
         })
         .chain(obligations)
-        .find(|o| !selcx.predicate_may_hold_fatal(o));
+        .find(|o| {
+            // if both impl headers are set to strict coherence it means that this will be accepted
+            // only if it's stated that T: !Trait. So only prove that the negated obligation holds.
+            if tcx.has_attr(a_def_id, sym::rustc_strict_coherence)
+                && tcx.has_attr(b_def_id, sym::rustc_strict_coherence)
+            {
+                strict_check(selcx, o)
+            } else {
+                loose_check(selcx, o) || tcx.features().negative_impls && strict_check(selcx, o)
+            }
+        });
     // FIXME: the call to `selcx.predicate_may_hold_fatal` above should be ported
     // to the canonical trait query form, `infcx.predicate_may_hold`, once
     // the new system supports intercrate mode (which coherence needs).
diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs
index b31d6d68b0a..428873b8d3d 100644
--- a/compiler/rustc_trait_selection/src/traits/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/mod.rs
@@ -804,6 +804,7 @@ pub fn vtable_trait_upcasting_coercion_new_vptr_slot(
         ty::Binder::dummy(ty::TraitPredicate {
             trait_ref,
             constness: ty::BoundConstness::NotConst,
+            polarity: ty::ImplPolarity::Positive,
         }),
     );
 
diff --git a/compiler/rustc_trait_selection/src/traits/relationships.rs b/compiler/rustc_trait_selection/src/traits/relationships.rs
index 7751dd84f4c..e0098cc92d5 100644
--- a/compiler/rustc_trait_selection/src/traits/relationships.rs
+++ b/compiler/rustc_trait_selection/src/traits/relationships.rs
@@ -44,6 +44,7 @@ pub(crate) fn update<'tcx, T>(
                             ty::PredicateKind::Trait(ty::TraitPredicate {
                                 trait_ref,
                                 constness: predicate.constness,
+                                polarity: predicate.polarity,
                             })
                         })
                         .to_predicate(infcx.tcx),
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 74e132097cc..e12b84742bf 100644
--- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
@@ -121,7 +121,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             return Ok(None);
         }
 
-        let mut candidates = candidate_set.vec;
+        let candidates = candidate_set.vec;
 
         debug!(?stack, ?candidates, "assembled {} candidates", candidates.len());
 
@@ -134,6 +134,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // candidate which assumes $0 == int, one that assumes `$0 ==
         // usize`, etc. This spells an ambiguity.
 
+        let mut candidates = self.filter_impls(candidates, stack.obligation);
+
         // If there is more than one candidate, first winnow them down
         // by considering extra conditions (nested obligations and so
         // forth). We don't winnow if there is exactly one
@@ -149,7 +151,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // Instead, we select the right impl now but report "`Bar` does
         // not implement `Clone`".
         if candidates.len() == 1 {
-            return self.filter_impls(candidates.pop().unwrap(), stack.obligation);
+            return self.filter_reservation_impls(candidates.pop().unwrap(), stack.obligation);
         }
 
         // Winnow, but record the exact outcome of evaluation, which
@@ -223,7 +225,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
 
         // Just one candidate left.
-        self.filter_impls(candidates.pop().unwrap().candidate, stack.obligation)
+        self.filter_reservation_impls(candidates.pop().unwrap().candidate, stack.obligation)
     }
 
     #[instrument(skip(self, stack), level = "debug")]
@@ -254,68 +256,75 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
 
-        self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
-
-        // Other bounds. Consider both in-scope bounds from fn decl
-        // and applicable impls. There is a certain set of precedence rules here.
-        let def_id = obligation.predicate.def_id();
-        let lang_items = self.tcx().lang_items();
-
-        if lang_items.copy_trait() == Some(def_id) {
-            debug!(obligation_self_ty = ?obligation.predicate.skip_binder().self_ty());
-
-            // User-defined copy impls are permitted, but only for
-            // structs and enums.
+        // The only way to prove a NotImplemented(T: Foo) predicate is via a negative impl.
+        // There are no compiler built-in rules for this.
+        if obligation.polarity() == ty::ImplPolarity::Negative {
+            self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
             self.assemble_candidates_from_impls(obligation, &mut candidates);
-
-            // For other types, we'll use the builtin rules.
-            let copy_conditions = self.copy_clone_conditions(obligation);
-            self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates);
-        } else if lang_items.discriminant_kind_trait() == Some(def_id) {
-            // `DiscriminantKind` is automatically implemented for every type.
-            candidates.vec.push(DiscriminantKindCandidate);
-        } else if lang_items.pointee_trait() == Some(def_id) {
-            // `Pointee` is automatically implemented for every type.
-            candidates.vec.push(PointeeCandidate);
-        } else if lang_items.sized_trait() == Some(def_id) {
-            // Sized is never implementable by end-users, it is
-            // always automatically computed.
-            let sized_conditions = self.sized_conditions(obligation);
-            self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates);
-        } else if lang_items.unsize_trait() == Some(def_id) {
-            self.assemble_candidates_for_unsizing(obligation, &mut candidates);
-        } else if lang_items.drop_trait() == Some(def_id)
-            && obligation.predicate.skip_binder().constness == ty::BoundConstness::ConstIfConst
-        {
-            if self.is_in_const_context {
-                self.assemble_const_drop_candidates(obligation, &mut candidates)?;
-            } else {
-                debug!("passing ~const Drop bound; in non-const context");
-                // `~const Drop` when we are not in a const context has no effect.
-                candidates.vec.push(ConstDropCandidate)
-            }
         } else {
-            if lang_items.clone_trait() == Some(def_id) {
-                // Same builtin conditions as `Copy`, i.e., every type which has builtin support
-                // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
-                // types have builtin support for `Clone`.
-                let clone_conditions = self.copy_clone_conditions(obligation);
-                self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates);
-            }
+            self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
+
+            // Other bounds. Consider both in-scope bounds from fn decl
+            // and applicable impls. There is a certain set of precedence rules here.
+            let def_id = obligation.predicate.def_id();
+            let lang_items = self.tcx().lang_items();
+
+            if lang_items.copy_trait() == Some(def_id) {
+                debug!(obligation_self_ty = ?obligation.predicate.skip_binder().self_ty());
+
+                // User-defined copy impls are permitted, but only for
+                // structs and enums.
+                self.assemble_candidates_from_impls(obligation, &mut candidates);
+
+                // For other types, we'll use the builtin rules.
+                let copy_conditions = self.copy_clone_conditions(obligation);
+                self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates);
+            } else if lang_items.discriminant_kind_trait() == Some(def_id) {
+                // `DiscriminantKind` is automatically implemented for every type.
+                candidates.vec.push(DiscriminantKindCandidate);
+            } else if lang_items.pointee_trait() == Some(def_id) {
+                // `Pointee` is automatically implemented for every type.
+                candidates.vec.push(PointeeCandidate);
+            } else if lang_items.sized_trait() == Some(def_id) {
+                // Sized is never implementable by end-users, it is
+                // always automatically computed.
+                let sized_conditions = self.sized_conditions(obligation);
+                self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates);
+            } else if lang_items.unsize_trait() == Some(def_id) {
+                self.assemble_candidates_for_unsizing(obligation, &mut candidates);
+            } else if lang_items.drop_trait() == Some(def_id)
+                && obligation.predicate.skip_binder().constness == ty::BoundConstness::ConstIfConst
+            {
+                if self.is_in_const_context {
+                    self.assemble_const_drop_candidates(obligation, &mut candidates)?;
+                } else {
+                    debug!("passing ~const Drop bound; in non-const context");
+                    // `~const Drop` when we are not in a const context has no effect.
+                    candidates.vec.push(ConstDropCandidate)
+                }
+            } else {
+                if lang_items.clone_trait() == Some(def_id) {
+                    // Same builtin conditions as `Copy`, i.e., every type which has builtin support
+                    // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
+                    // types have builtin support for `Clone`.
+                    let clone_conditions = self.copy_clone_conditions(obligation);
+                    self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates);
+                }
 
-            self.assemble_generator_candidates(obligation, &mut candidates);
-            self.assemble_closure_candidates(obligation, &mut candidates);
-            self.assemble_fn_pointer_candidates(obligation, &mut candidates);
-            self.assemble_candidates_from_impls(obligation, &mut candidates);
-            self.assemble_candidates_from_object_ty(obligation, &mut candidates);
-        }
+                self.assemble_generator_candidates(obligation, &mut candidates);
+                self.assemble_closure_candidates(obligation, &mut candidates);
+                self.assemble_fn_pointer_candidates(obligation, &mut candidates);
+                self.assemble_candidates_from_impls(obligation, &mut candidates);
+                self.assemble_candidates_from_object_ty(obligation, &mut candidates);
+            }
 
-        self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
-        self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
-        // Auto implementations have lower priority, so we only
-        // consider triggering a default if there is no other impl that can apply.
-        if candidates.vec.is_empty() {
-            self.assemble_candidates_from_auto_impls(obligation, &mut candidates);
+            self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
+            self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
+            // Auto implementations have lower priority, so we only
+            // consider triggering a default if there is no other impl that can apply.
+            if candidates.vec.is_empty() {
+                self.assemble_candidates_from_auto_impls(obligation, &mut candidates);
+            }
         }
         debug!("candidate list size: {}", candidates.vec.len());
         Ok(candidates)
@@ -376,7 +385,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         for bound in matching_bounds {
             let wc = self.evaluate_where_clause(stack, bound.value)?;
             if wc.may_apply() {
-                candidates.vec.push(ParamCandidate(bound));
+                candidates.vec.push(ParamCandidate((bound, stack.obligation.polarity())));
             }
         }
 
@@ -913,6 +922,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         substs: self.tcx().mk_substs_trait(ty, &[]),
                     },
                     constness: ty::BoundConstness::NotConst,
+                    polarity: ty::ImplPolarity::Positive,
                 }));
             copy_obligation.recursion_depth = depth + 1;
             self.assemble_candidates_from_impls(&copy_obligation, &mut copy_candidates);
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index a36cb1358b6..84721922c8d 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -58,8 +58,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
 
             ParamCandidate(param) => {
-                let obligations = self.confirm_param_candidate(obligation, param.value);
-                Ok(ImplSource::Param(obligations, param.constness))
+                let obligations = self.confirm_param_candidate(obligation, param.0.value);
+                Ok(ImplSource::Param(obligations, param.0.constness))
             }
 
             ImplCandidate(impl_def_id) => {
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 85502a399de..43ffa285b8f 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -20,7 +20,7 @@ use super::ObligationCauseCode;
 use super::Selection;
 use super::SelectionResult;
 use super::TraitQueryMode;
-use super::{ErrorReporting, Overflow, SelectionError, Unimplemented};
+use super::{ErrorReporting, Overflow, SelectionError};
 use super::{ObligationCause, PredicateObligation, TraitObligation};
 
 use crate::infer::{InferCtxt, InferOk, TypeFreshener};
@@ -709,7 +709,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         debug!(?fresh_trait_ref);
 
-        if let Some(result) = self.check_evaluation_cache(obligation.param_env, fresh_trait_ref) {
+        if let Some(result) = self.check_evaluation_cache(
+            obligation.param_env,
+            fresh_trait_ref,
+            obligation.polarity(),
+        ) {
             debug!(?result, "CACHE HIT");
             return Ok(result);
         }
@@ -739,12 +743,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let reached_depth = stack.reached_depth.get();
         if reached_depth >= stack.depth {
             debug!(?result, "CACHE MISS");
-            self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result);
+            self.insert_evaluation_cache(
+                obligation.param_env,
+                fresh_trait_ref,
+                obligation.polarity(),
+                dep_node,
+                result,
+            );
 
             stack.cache().on_completion(stack.dfn, |fresh_trait_ref, provisional_result| {
                 self.insert_evaluation_cache(
                     obligation.param_env,
                     fresh_trait_ref,
+                    obligation.polarity(),
                     dep_node,
                     provisional_result.max(result),
                 );
@@ -855,34 +866,39 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // precise still.
         let unbound_input_types =
             stack.fresh_trait_ref.value.skip_binder().substs.types().any(|ty| ty.is_fresh());
-        // This check was an imperfect workaround for a bug in the old
-        // intercrate mode; it should be removed when that goes away.
-        if unbound_input_types && self.intercrate {
-            debug!("evaluate_stack --> unbound argument, intercrate -->  ambiguous",);
-            // Heuristics: show the diagnostics when there are no candidates in crate.
-            if self.intercrate_ambiguity_causes.is_some() {
-                debug!("evaluate_stack: intercrate_ambiguity_causes is some");
-                if let Ok(candidate_set) = self.assemble_candidates(stack) {
-                    if !candidate_set.ambiguous && candidate_set.vec.is_empty() {
-                        let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
-                        let self_ty = trait_ref.self_ty();
-                        let cause =
-                            with_no_trimmed_paths(|| IntercrateAmbiguityCause::DownstreamCrate {
-                                trait_desc: trait_ref.print_only_trait_path().to_string(),
-                                self_desc: if self_ty.has_concrete_skeleton() {
-                                    Some(self_ty.to_string())
-                                } else {
-                                    None
-                                },
+
+        if stack.obligation.polarity() != ty::ImplPolarity::Negative {
+            // This check was an imperfect workaround for a bug in the old
+            // intercrate mode; it should be removed when that goes away.
+            if unbound_input_types && self.intercrate {
+                debug!("evaluate_stack --> unbound argument, intercrate -->  ambiguous",);
+                // Heuristics: show the diagnostics when there are no candidates in crate.
+                if self.intercrate_ambiguity_causes.is_some() {
+                    debug!("evaluate_stack: intercrate_ambiguity_causes is some");
+                    if let Ok(candidate_set) = self.assemble_candidates(stack) {
+                        if !candidate_set.ambiguous && candidate_set.vec.is_empty() {
+                            let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
+                            let self_ty = trait_ref.self_ty();
+                            let cause = with_no_trimmed_paths(|| {
+                                IntercrateAmbiguityCause::DownstreamCrate {
+                                    trait_desc: trait_ref.print_only_trait_path().to_string(),
+                                    self_desc: if self_ty.has_concrete_skeleton() {
+                                        Some(self_ty.to_string())
+                                    } else {
+                                        None
+                                    },
+                                }
                             });
 
-                        debug!(?cause, "evaluate_stack: pushing cause");
-                        self.intercrate_ambiguity_causes.as_mut().unwrap().push(cause);
+                            debug!(?cause, "evaluate_stack: pushing cause");
+                            self.intercrate_ambiguity_causes.as_mut().unwrap().push(cause);
+                        }
                     }
                 }
+                return Ok(EvaluatedToAmbig);
             }
-            return Ok(EvaluatedToAmbig);
         }
+
         if unbound_input_types
             && stack.iter().skip(1).any(|prev| {
                 stack.obligation.param_env == prev.obligation.param_env
@@ -977,6 +993,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         &self,
         param_env: ty::ParamEnv<'tcx>,
         trait_ref: ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>,
+        polarity: ty::ImplPolarity,
     ) -> Option<EvaluationResult> {
         // Neither the global nor local cache is aware of intercrate
         // mode, so don't do any caching. In particular, we might
@@ -988,17 +1005,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         let tcx = self.tcx();
         if self.can_use_global_caches(param_env) {
-            if let Some(res) = tcx.evaluation_cache.get(&param_env.and(trait_ref), tcx) {
+            if let Some(res) = tcx.evaluation_cache.get(&(param_env.and(trait_ref), polarity), tcx)
+            {
                 return Some(res);
             }
         }
-        self.infcx.evaluation_cache.get(&param_env.and(trait_ref), tcx)
+        self.infcx.evaluation_cache.get(&(param_env.and(trait_ref), polarity), tcx)
     }
 
     fn insert_evaluation_cache(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
         trait_ref: ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>,
+        polarity: ty::ImplPolarity,
         dep_node: DepNodeIndex,
         result: EvaluationResult,
     ) {
@@ -1023,13 +1042,17 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // FIXME: Due to #50507 this overwrites the different values
                 // This should be changed to use HashMapExt::insert_same
                 // when that is fixed
-                self.tcx().evaluation_cache.insert(param_env.and(trait_ref), dep_node, result);
+                self.tcx().evaluation_cache.insert(
+                    (param_env.and(trait_ref), polarity),
+                    dep_node,
+                    result,
+                );
                 return;
             }
         }
 
         debug!(?trait_ref, ?result, "insert_evaluation_cache");
-        self.infcx.evaluation_cache.insert(param_env.and(trait_ref), dep_node, result);
+        self.infcx.evaluation_cache.insert((param_env.and(trait_ref), polarity), dep_node, result);
     }
 
     /// For various reasons, it's possible for a subobligation
@@ -1094,67 +1117,89 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         (result, dep_node)
     }
 
+    /// filter_impls filters constant trait obligations and candidates that have a positive impl
+    /// for a negative goal and a negative impl for a positive goal
     #[instrument(level = "debug", skip(self))]
     fn filter_impls(
         &mut self,
-        candidate: SelectionCandidate<'tcx>,
+        candidates: Vec<SelectionCandidate<'tcx>>,
         obligation: &TraitObligation<'tcx>,
-    ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
+    ) -> Vec<SelectionCandidate<'tcx>> {
         let tcx = self.tcx();
-        // Respect const trait obligations
-        if self.is_trait_predicate_const(obligation.predicate.skip_binder()) {
-            match candidate {
-                // const impl
-                ImplCandidate(def_id) if tcx.impl_constness(def_id) == hir::Constness::Const => {}
-                // const param
-                ParamCandidate(ty::ConstnessAnd {
-                    constness: ty::BoundConstness::ConstIfConst,
-                    ..
-                }) => {}
-                // auto trait impl
-                AutoImplCandidate(..) => {}
-                // generator, this will raise error in other places
-                // or ignore error with const_async_blocks feature
-                GeneratorCandidate => {}
-                // FnDef where the function is const
-                FnPointerCandidate { is_const: true } => {}
-                ConstDropCandidate => {}
-                _ => {
-                    // reject all other types of candidates
-                    return Err(Unimplemented);
+        let mut result = Vec::with_capacity(candidates.len());
+
+        for candidate in candidates {
+            // Respect const trait obligations
+            if self.is_trait_predicate_const(obligation.predicate.skip_binder()) {
+                match candidate {
+                    // const impl
+                    ImplCandidate(def_id)
+                        if tcx.impl_constness(def_id) == hir::Constness::Const => {}
+                    // const param
+                    ParamCandidate((
+                        ty::ConstnessAnd { constness: ty::BoundConstness::ConstIfConst, .. },
+                        _,
+                    )) => {}
+                    // auto trait impl
+                    AutoImplCandidate(..) => {}
+                    // generator, this will raise error in other places
+                    // or ignore error with const_async_blocks feature
+                    GeneratorCandidate => {}
+                    // FnDef where the function is const
+                    FnPointerCandidate { is_const: true } => {}
+                    ConstDropCandidate => {}
+                    _ => {
+                        // reject all other types of candidates
+                        continue;
+                    }
+                }
+            }
+
+            if let ImplCandidate(def_id) = candidate {
+                if ty::ImplPolarity::Reservation == tcx.impl_polarity(def_id)
+                    || obligation.polarity() == tcx.impl_polarity(def_id)
+                    || self.allow_negative_impls
+                {
+                    result.push(candidate);
                 }
+            } else {
+                result.push(candidate);
             }
         }
-        // Treat negative impls as unimplemented, and reservation impls as ambiguity.
+
+        result
+    }
+
+    /// filter_reservation_impls filter reservation impl for any goal as ambiguous
+    #[instrument(level = "debug", skip(self))]
+    fn filter_reservation_impls(
+        &mut self,
+        candidate: SelectionCandidate<'tcx>,
+        obligation: &TraitObligation<'tcx>,
+    ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
+        let tcx = self.tcx();
+        // Treat reservation impls as ambiguity.
         if let ImplCandidate(def_id) = candidate {
-            match tcx.impl_polarity(def_id) {
-                ty::ImplPolarity::Negative if !self.allow_negative_impls => {
-                    return Err(Unimplemented);
-                }
-                ty::ImplPolarity::Reservation => {
-                    if let Some(intercrate_ambiguity_clauses) =
-                        &mut self.intercrate_ambiguity_causes
-                    {
-                        let attrs = tcx.get_attrs(def_id);
-                        let attr = tcx.sess.find_by_name(&attrs, sym::rustc_reservation_impl);
-                        let value = attr.and_then(|a| a.value_str());
-                        if let Some(value) = value {
-                            debug!(
-                                "filter_impls: \
+            if let ty::ImplPolarity::Reservation = tcx.impl_polarity(def_id) {
+                if let Some(intercrate_ambiguity_clauses) = &mut self.intercrate_ambiguity_causes {
+                    let attrs = tcx.get_attrs(def_id);
+                    let attr = tcx.sess.find_by_name(&attrs, sym::rustc_reservation_impl);
+                    let value = attr.and_then(|a| a.value_str());
+                    if let Some(value) = value {
+                        debug!(
+                            "filter_reservation_impls: \
                                  reservation impl ambiguity on {:?}",
-                                def_id
-                            );
-                            intercrate_ambiguity_clauses.push(
-                                IntercrateAmbiguityCause::ReservationImpl {
-                                    message: value.to_string(),
-                                },
-                            );
-                        }
+                            def_id
+                        );
+                        intercrate_ambiguity_clauses.push(
+                            IntercrateAmbiguityCause::ReservationImpl {
+                                message: value.to_string(),
+                            },
+                        );
                     }
-                    return Ok(None);
                 }
-                _ => {}
-            };
+                return Ok(None);
+            }
         }
         Ok(Some(candidate))
     }
@@ -1162,7 +1207,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     fn is_knowable<'o>(&mut self, stack: &TraitObligationStack<'o, 'tcx>) -> Option<Conflict> {
         debug!("is_knowable(intercrate={:?})", self.intercrate);
 
-        if !self.intercrate {
+        if !self.intercrate || stack.obligation.polarity() == ty::ImplPolarity::Negative {
             return None;
         }
 
@@ -1219,14 +1264,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         if self.can_use_global_caches(param_env) {
             if let Some(res) = tcx
                 .selection_cache
-                .get(&param_env.and(trait_ref).with_constness(pred.constness), tcx)
+                .get(&(param_env.and(trait_ref).with_constness(pred.constness), pred.polarity), tcx)
             {
                 return Some(res);
             }
         }
         self.infcx
             .selection_cache
-            .get(&param_env.and(trait_ref).with_constness(pred.constness), tcx)
+            .get(&(param_env.and(trait_ref).with_constness(pred.constness), pred.polarity), tcx)
     }
 
     /// Determines whether can we safely cache the result
@@ -1286,7 +1331,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     debug!(?trait_ref, ?candidate, "insert_candidate_cache global");
                     // This may overwrite the cache with the same value.
                     tcx.selection_cache.insert(
-                        param_env.and(trait_ref).with_constness(pred.constness),
+                        (param_env.and(trait_ref).with_constness(pred.constness), pred.polarity),
                         dep_node,
                         candidate,
                     );
@@ -1297,7 +1342,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         debug!(?trait_ref, ?candidate, "insert_candidate_cache local");
         self.infcx.selection_cache.insert(
-            param_env.and(trait_ref).with_constness(pred.constness),
+            (param_env.and(trait_ref).with_constness(pred.constness), pred.polarity),
             dep_node,
             candidate,
         );
@@ -1523,10 +1568,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 | ConstDropCandidate,
             ) => false,
 
-            (ParamCandidate(other), ParamCandidate(victim)) => {
+            (
+                ParamCandidate((other, other_polarity)),
+                ParamCandidate((victim, victim_polarity)),
+            ) => {
                 let same_except_bound_vars = other.value.skip_binder()
                     == victim.value.skip_binder()
                     && other.constness == victim.constness
+                    && other_polarity == victim_polarity
                     && !other.value.skip_binder().has_escaping_bound_vars();
                 if same_except_bound_vars {
                     // See issue #84398. In short, we can generate multiple ParamCandidates which are
@@ -1537,6 +1586,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     other.value.bound_vars().len() <= victim.value.bound_vars().len()
                 } else if other.value == victim.value
                     && victim.constness == ty::BoundConstness::NotConst
+                    && other_polarity == victim_polarity
                 {
                     // Drop otherwise equivalent non-const candidates in favor of const candidates.
                     true
@@ -1566,11 +1616,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 | TraitAliasCandidate(..)
                 | ObjectCandidate(_)
                 | ProjectionCandidate(_),
-            ) => !is_global(&cand.value),
+            ) => !is_global(&cand.0.value),
             (ObjectCandidate(_) | ProjectionCandidate(_), ParamCandidate(ref cand)) => {
                 // Prefer these to a global where-clause bound
                 // (see issue #50825).
-                is_global(&cand.value)
+                is_global(&cand.0.value)
             }
             (
                 ImplCandidate(_)
@@ -1586,7 +1636,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             ) => {
                 // Prefer these to a global where-clause bound
                 // (see issue #50825).
-                is_global(&cand.value) && other.evaluation.must_apply_modulo_regions()
+                is_global(&cand.0.value) && other.evaluation.must_apply_modulo_regions()
             }
 
             (ProjectionCandidate(i), ProjectionCandidate(j))
diff --git a/compiler/rustc_typeck/src/check/_match.rs b/compiler/rustc_typeck/src/check/_match.rs
index 6a231e719e6..c17c42c497f 100644
--- a/compiler/rustc_typeck/src/check/_match.rs
+++ b/compiler/rustc_typeck/src/check/_match.rs
@@ -531,6 +531,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                                         substs: self.infcx.tcx.mk_substs_trait(outer_ty, &[]),
                                     },
                                     constness: t.constness,
+                                    polarity: t.polarity,
                                 }));
                             let obl = Obligation::new(
                                 o.cause.clone(),
diff --git a/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs b/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs
index f4bb5761c19..4fb422c801b 100644
--- a/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs
+++ b/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs
@@ -382,6 +382,7 @@ fn check_specialization_on<'tcx>(tcx: TyCtxt<'tcx>, predicate: ty::Predicate<'tc
         ty::PredicateKind::Trait(ty::TraitPredicate {
             trait_ref,
             constness: ty::BoundConstness::NotConst,
+            polarity: _,
         }) => {
             if !matches!(
                 trait_predicate_kind(tcx, predicate),
@@ -413,6 +414,7 @@ fn trait_predicate_kind<'tcx>(
         ty::PredicateKind::Trait(ty::TraitPredicate {
             trait_ref,
             constness: ty::BoundConstness::NotConst,
+            polarity: _,
         }) => Some(tcx.trait_def(trait_ref.def_id).specialization_kind),
         ty::PredicateKind::Trait(_)
         | ty::PredicateKind::RegionOutlives(_)
diff --git a/src/test/ui/coherence/auxiliary/error_lib.rs b/src/test/ui/coherence/auxiliary/error_lib.rs
new file mode 100644
index 00000000000..43806cb995c
--- /dev/null
+++ b/src/test/ui/coherence/auxiliary/error_lib.rs
@@ -0,0 +1,5 @@
+#![crate_type = "lib"]
+#![feature(negative_impls)]
+
+pub trait Error {}
+impl !Error for &str {}
diff --git a/src/test/ui/coherence/coherence-overlap-negate-alias-strict.rs b/src/test/ui/coherence/coherence-overlap-negate-alias-strict.rs
new file mode 100644
index 00000000000..16ace450b06
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-negate-alias-strict.rs
@@ -0,0 +1,19 @@
+#![feature(negative_impls)]
+#![feature(rustc_attrs)]
+#![feature(trait_alias)]
+
+trait A {}
+trait B {}
+trait AB = A + B;
+
+impl !A for u32 {}
+
+trait C {}
+#[rustc_strict_coherence]
+impl<T: AB> C for T {}
+#[rustc_strict_coherence]
+impl C for u32 {}
+//~^ ERROR: conflicting implementations of trait `C` for type `u32` [E0119]
+// FIXME this should work, we should implement an `assemble_neg_candidates` fn
+
+fn main() {}
diff --git a/src/test/ui/coherence/coherence-overlap-negate-alias-strict.stderr b/src/test/ui/coherence/coherence-overlap-negate-alias-strict.stderr
new file mode 100644
index 00000000000..5e436223119
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-negate-alias-strict.stderr
@@ -0,0 +1,12 @@
+error[E0119]: conflicting implementations of trait `C` for type `u32`
+  --> $DIR/coherence-overlap-negate-alias-strict.rs:15:1
+   |
+LL | impl<T: AB> C for T {}
+   | ------------------- first implementation here
+LL | #[rustc_strict_coherence]
+LL | impl C for u32 {}
+   | ^^^^^^^^^^^^^^ conflicting implementation for `u32`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0119`.
diff --git a/src/test/ui/coherence/coherence-overlap-negate-not-use-feature-gate.rs b/src/test/ui/coherence/coherence-overlap-negate-not-use-feature-gate.rs
new file mode 100644
index 00000000000..a067736f63a
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-negate-not-use-feature-gate.rs
@@ -0,0 +1,8 @@
+use std::ops::DerefMut;
+
+trait Foo {}
+impl<T: DerefMut> Foo for T {}
+impl<U> Foo for &U {}
+//~^ ERROR: conflicting implementations of trait `Foo` for type `&_` [E0119]
+
+fn main() {}
diff --git a/src/test/ui/coherence/coherence-overlap-negate-not-use-feature-gate.stderr b/src/test/ui/coherence/coherence-overlap-negate-not-use-feature-gate.stderr
new file mode 100644
index 00000000000..4b55001ecc0
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-negate-not-use-feature-gate.stderr
@@ -0,0 +1,11 @@
+error[E0119]: conflicting implementations of trait `Foo` for type `&_`
+  --> $DIR/coherence-overlap-negate-not-use-feature-gate.rs:5:1
+   |
+LL | impl<T: DerefMut> Foo for T {}
+   | --------------------------- first implementation here
+LL | impl<U> Foo for &U {}
+   | ^^^^^^^^^^^^^^^^^^ conflicting implementation for `&_`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0119`.
diff --git a/src/test/ui/coherence/coherence-overlap-negate-strict.rs b/src/test/ui/coherence/coherence-overlap-negate-strict.rs
new file mode 100644
index 00000000000..b3ae9a7bf78
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-negate-strict.rs
@@ -0,0 +1,18 @@
+// check-pass
+
+#![feature(negative_impls)]
+#![feature(rustc_attrs)]
+#![feature(trait_alias)]
+
+trait A {}
+trait B {}
+
+impl !A for u32 {}
+
+trait C {}
+#[rustc_strict_coherence]
+impl<T: A + B> C for T {}
+#[rustc_strict_coherence]
+impl C for u32 {}
+
+fn main() {}
diff --git a/src/test/ui/coherence/coherence-overlap-negate-use-feature-gate.rs b/src/test/ui/coherence/coherence-overlap-negate-use-feature-gate.rs
new file mode 100644
index 00000000000..e024eae9819
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-negate-use-feature-gate.rs
@@ -0,0 +1,11 @@
+// check-pass
+
+#![feature(negative_impls)]
+
+use std::ops::DerefMut;
+
+trait Foo {}
+impl<T: DerefMut> Foo for T {}
+impl<U> Foo for &U {}
+
+fn main() {}
diff --git a/src/test/ui/coherence/coherence-overlap-negative-trait.rs b/src/test/ui/coherence/coherence-overlap-negative-trait.rs
new file mode 100644
index 00000000000..ab65163bea4
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-negative-trait.rs
@@ -0,0 +1,16 @@
+// check-pass
+// aux-build:error_lib.rs
+//
+// Check that if we promise to not impl what would overlap it doesn't actually overlap
+
+#![feature(negative_impls)]
+
+extern crate error_lib as lib;
+use lib::Error;
+
+trait From<T> {}
+
+impl From<&str> for Box<dyn Error> {}
+impl<E> From<E> for Box<dyn Error> where E: Error {}
+
+fn main() {}
diff --git a/src/test/ui/coherence/coherence-overlap-trait-alias.rs b/src/test/ui/coherence/coherence-overlap-trait-alias.rs
new file mode 100644
index 00000000000..45b2f086305
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-trait-alias.rs
@@ -0,0 +1,20 @@
+#![feature(rustc_attrs)]
+#![feature(trait_alias)]
+
+trait A {}
+trait B {}
+trait AB = A + B;
+
+impl A for u32 {}
+impl B for u32 {}
+
+trait C {}
+#[rustc_strict_coherence]
+impl<T: AB> C for T {}
+#[rustc_strict_coherence]
+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
+
+fn main() {}
diff --git a/src/test/ui/coherence/coherence-overlap-trait-alias.stderr b/src/test/ui/coherence/coherence-overlap-trait-alias.stderr
new file mode 100644
index 00000000000..e2e8ad54beb
--- /dev/null
+++ b/src/test/ui/coherence/coherence-overlap-trait-alias.stderr
@@ -0,0 +1,16 @@
+error[E0283]: type annotations needed
+  --> $DIR/coherence-overlap-trait-alias.rs:15:6
+   |
+LL | impl C for u32 {}
+   |      ^ cannot infer type for type `u32`
+   |
+   = note: cannot satisfy `u32: C`
+note: required by a bound in `C`
+  --> $DIR/coherence-overlap-trait-alias.rs:11:1
+   |
+LL | trait C {}
+   | ^^^^^^^ required by this bound in `C`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0283`.
diff --git a/src/test/ui/traits/cache-reached-depth-ice.rs b/src/test/ui/traits/cache-reached-depth-ice.rs
index 4318e07d07a..c36ac08579b 100644
--- a/src/test/ui/traits/cache-reached-depth-ice.rs
+++ b/src/test/ui/traits/cache-reached-depth-ice.rs
@@ -41,5 +41,5 @@ fn test<X: ?Sized + Send>() {}
 
 fn main() {
     test::<A>();
-    //~^ ERROR evaluate(Binder(TraitPredicate(<A as std::marker::Send>), [])) = Ok(EvaluatedToOk)
+    //~^ ERROR evaluate(Binder(TraitPredicate(<A as std::marker::Send>, polarity:Positive), [])) = Ok(EvaluatedToOk)
 }
diff --git a/src/test/ui/traits/cache-reached-depth-ice.stderr b/src/test/ui/traits/cache-reached-depth-ice.stderr
index 5e662970bb9..082aa0f5cd9 100644
--- a/src/test/ui/traits/cache-reached-depth-ice.stderr
+++ b/src/test/ui/traits/cache-reached-depth-ice.stderr
@@ -1,4 +1,4 @@
-error: evaluate(Binder(TraitPredicate(<A as std::marker::Send>), [])) = Ok(EvaluatedToOk)
+error: evaluate(Binder(TraitPredicate(<A as std::marker::Send>, polarity:Positive), [])) = Ok(EvaluatedToOk)
   --> $DIR/cache-reached-depth-ice.rs:43:5
    |
 LL | fn test<X: ?Sized + Send>() {}
diff --git a/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.rs b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.rs
index 1be0b05fa2b..3cd68ff6f06 100644
--- a/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.rs
+++ b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.rs
@@ -57,10 +57,10 @@ fn main() {
     // Key is that Vec<First> is "ok" and Third<'_, Ty> is "ok modulo regions":
 
     forward();
-    //~^ ERROR evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
-    //~| ERROR evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+    //~^ ERROR evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOk)
+    //~| ERROR evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOkModuloRegions)
 
     reverse();
-    //~^ ERROR evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
-    //~| ERROR evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+    //~^ ERROR evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOk)
+    //~| ERROR evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOkModuloRegions)
 }
diff --git a/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.stderr b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.stderr
index 43acc66fd73..7c4041144a4 100644
--- a/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.stderr
+++ b/src/test/ui/traits/issue-83538-tainted-cache-after-cycle.stderr
@@ -1,4 +1,4 @@
-error: evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
+error: evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOk)
   --> $DIR/issue-83538-tainted-cache-after-cycle.rs:59:5
    |
 LL |     Vec<First>: Unpin,
@@ -7,7 +7,7 @@ LL |     Vec<First>: Unpin,
 LL |     forward();
    |     ^^^^^^^
 
-error: evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+error: evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOkModuloRegions)
   --> $DIR/issue-83538-tainted-cache-after-cycle.rs:59:5
    |
 LL |     Third<'a, Ty>: Unpin,
@@ -16,7 +16,7 @@ LL |     Third<'a, Ty>: Unpin,
 LL |     forward();
    |     ^^^^^^^
 
-error: evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>), [])) = Ok(EvaluatedToOkModuloRegions)
+error: evaluate(Binder(TraitPredicate(<Third<'_, Ty> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOkModuloRegions)
   --> $DIR/issue-83538-tainted-cache-after-cycle.rs:63:5
    |
 LL |     Third<'a, Ty>: Unpin,
@@ -25,7 +25,7 @@ LL |     Third<'a, Ty>: Unpin,
 LL |     reverse();
    |     ^^^^^^^
 
-error: evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>), [])) = Ok(EvaluatedToOk)
+error: evaluate(Binder(TraitPredicate(<std::vec::Vec<First> as std::marker::Unpin>, polarity:Positive), [])) = Ok(EvaluatedToOk)
   --> $DIR/issue-83538-tainted-cache-after-cycle.rs:63:5
    |
 LL |     Vec<First>: Unpin,
diff --git a/src/test/ui/traits/negative-impls/rely-on-negative-impl-in-coherence.rs b/src/test/ui/traits/negative-impls/rely-on-negative-impl-in-coherence.rs
index db72aaf1803..119ac05c33e 100644
--- a/src/test/ui/traits/negative-impls/rely-on-negative-impl-in-coherence.rs
+++ b/src/test/ui/traits/negative-impls/rely-on-negative-impl-in-coherence.rs
@@ -1,3 +1,5 @@
+// check-pass
+
 #![feature(negative_impls)]
 
 // aux-build: foreign_trait.rs
@@ -16,6 +18,6 @@ use foreign_trait::ForeignTrait;
 
 trait LocalTrait { }
 impl<T: ForeignTrait> LocalTrait for T { }
-impl LocalTrait for String { } //~ ERROR conflicting implementations
+impl LocalTrait for String { }
 
 fn main() { }
diff --git a/src/test/ui/traits/negative-impls/rely-on-negative-impl-in-coherence.stderr b/src/test/ui/traits/negative-impls/rely-on-negative-impl-in-coherence.stderr
deleted file mode 100644
index b970ad76208..00000000000
--- a/src/test/ui/traits/negative-impls/rely-on-negative-impl-in-coherence.stderr
+++ /dev/null
@@ -1,11 +0,0 @@
-error[E0119]: conflicting implementations of trait `LocalTrait` for type `std::string::String`
-  --> $DIR/rely-on-negative-impl-in-coherence.rs:19:1
-   |
-LL | impl<T: ForeignTrait> LocalTrait for T { }
-   | -------------------------------------- first implementation here
-LL | impl LocalTrait for String { }
-   | ^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `std::string::String`
-
-error: aborting due to previous error
-
-For more information about this error, try `rustc --explain E0119`.