Auto merge of #132325 - lcnr:damn-son, r=oli-obk

rework winnowing to sensibly handle global where-bounds

There may be multiple ways to prove a given trait-bound. In case there are multiple such applicable candidates we need to somehow merge them or bail with ambiguity. When merging candidates we prefer some over others for multiple reasons:

- we want to guide inference during typeck, even if not strictly necessary
- to avoid ambiguity if there if there are at most lifetime differences
    - old solver needs exactly one candidate
    - new solver only needs to handle lifetime differences
- we disable normalization via impls if the goal is proven by using a where-bound

## The approach in this PR[^1]

- always prefer trivial builtin impls[^6]
- then prefer non-global[^global] where-bounds
    - if there exists exactly one where-bound, guide inference
    - if there are multiple where-bounds even if some of them are global, ambig
- then prefer alias bounds[^2] and builtin trait object candidates[^3][^2]
- merge everything ignoring global where-bounds
- if there are no other candidates, try using global where-bounds[^5]

**We disable normalization via impls when using non-global where-bounds or alias-bounds, even if we're unable to normalize by using the where-bound.**

[^1]: see the source for more details
[^2]: [we arbitrary select a single object and alias-bound candidate in case multiple apply and they don't impact inference](https://github.com/rust-lang/rust/blob/a4cedecc9ec76b46dcbb954750068c832cf2dd43/compiler/rustc_trait_selection/src/traits/select/mod.rs#L1906-L1911). This should be unnecessary in the new solver.
[^3]: Necessary for `dyn Any` and https://github.com/rust-lang/rust/issues/57893
[^global]: a where-bound is global if it is not higher-ranked and doesn't contain any generic parameters, `'static` is ok
[^5]: global where-bounds are only used if they are unsatisfiable, i.e. no impl candidate exists
[^6]: they don't constrain inference and don't add any lifetime constraints

## Why this behavior?

### inference guidance via where-bounds and alias-bounds

#### where-bounds

```rust
fn method_selection<T: Into<u64>>(x: T) -> Option<u32> {
    x.into().try_into().ok()
    // prove `T: Into<?0>` and then select a method `?0`,
    // needs eager inference.
}
```

While the above pattern exists in the wild, I think that most inference guidance due to where-bounds is actually unintended. I believe we may want to restrict inference guidance in the future, e.g. limit it to where-bounds whose self-type is a param.

#### alias-bounds

```rust
pub trait Dyn {
    type Word: Into<u64>;
    fn d_tag(&self) -> Self::Word;
    fn tag32(&self) -> Option<u32> {
        self.d_tag().into().try_into().ok()
        // prove `Self::Word: Into<?0>` and then select a method
        // on `?0`, needs eager inference.
    }
}
```

### Disable normalization via impls when using where-bounds

cc https://github.com/rust-lang/trait-system-refactor-initiative/issues/125

```rust
trait Trait<'a> {
    type Assoc;
}

impl<T> Trait<'static> for T {
    type Assoc = ();
}

// normalizing requires `'a == 'static`, the trait bound does not.
fn foo<'a, T: Trait<'a>>(_: T::Assoc) {}
```

If an impl adds constraints not required by a where-bound, using the impl may cause compilation failure avoided by treating the associated type as rigid.

This is also why we can always use trivial builtin impls, even for normalization. They are guaranteed to never add any requirements.

### Lower priority for global where-bounds

A where-bound is considered global if it does not refer to any generic parameters and is not higher-ranked. It may refer to `'static`.

This means global where-bounds are either always fully implied by an impl or unsatisfiable. We don't really care about the inference behavior of unsatisfiable where-bounds :3

If a where-bound is fully implied then using an applicable impl for normalization cannot result in additional constraints. As this is the - afaict only - reason why we disable normalization via impls in the first place, we don't have to disable normalization via impls when encountering global where-bounds.

### Consider global where-bounds at all

Given that we just use impls even if there exists a global where-bounds, you may ask why we don't just ignore these global where-bounds entirely: we use them to weaken the inference guidance from non-global where-bounds.

Without a global where-bound, we currently prefer non-global where bounds even though there would be an applicable impl as well. By adding a non-global where-bound, this *unnecessary* inference guidance is disabled, allowing the following to compile:
```rust
fn check<Color>(color: Color)
where
    Vec: Into<Color> + Into<f32>,
{
    let _: f32 = Vec.into();
    // Without the global `Vec: Into<f32>`  bound we'd
    // eagerly use the non-global `Vec: Into<Color>` bound
    // here, causing this to fail.
}

struct Vec;
impl From<Vec> for f32 {
    fn from(_: Vec) -> Self {
        loop {}
    }
}
```
[There exist multiple crates which rely on this behavior](https://github.com/rust-lang/rust/pull/124592#issuecomment-2104541495).

## Design considerations

We would like to be able to normalize via impls as much as possible. Disabling normalization simply because there exists a where-bound is undesirable.

For the sake of backwards compatability I intend to mostly mirror the current inference guidance rules and then explore possible improvements once the new solver is done. I do believe that removing unnecessary inference guidance where possible is desirable however.

Whether a where-bound is global depends on whether used lifetimes are `'static`. The where-bound `u32: Trait<'static>` is either entirely implied by an impl, meaning that it does not have to disable normalization via impls, **while `u32: Trait<'a>` needs to disable normalization via impls as the impl may only hold for `'static`**. Considering all where-bounds to be non-global once they contain any region is unfortunately a breaking change.

## How does this differ from stable

The currently stable approach is order dependent:
- it prefers impls over global where-bounds: impl > global
- it prefers non-global where-bounds over impls: non-global > impl
- it treats all where-bounds equally: global = non-global

This means that whether we bail with ambiguity or simply use the non-global where bound depending on the *order of where-clauses* and *number of applicable impl candidates*. See the tests added in the first commit for more details. With this PR we now always bail with ambiguity.

I've previously tried to always use the non-global candidate, causing unnecessary inference guidance and undesirable breakage. This already went through an FCP in #124592. However, I consider the new approach to be preferable as it exclusively removes incompleteness. It also doesn't cause any crater breakage.

## How to support this in the new solver :o

**This is separately implemented in #133643 and not part of this FCP!**

To implement the global vs non-global where-bound distinction, we have to either keep `'static` in the `param_env` when canonicalizing, or eagerly distinguish global from non-global where-bounds and provide that information to the canonical query.

The old solver currently keeps `'static` only the `param_env`, replacing it with an inference variable in the `value`.
https://github.com/rust-lang/rust/blob/a4cedecc9ec76b46dcbb954750068c832cf2dd43/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs#L49-L64

I dislike that based on *vibes* and it may end up being a problem once we extend the environment inside of the solver as [we must not rely on `'static` in the `predicate` as it would get erased in MIR typeck](https://github.com/rust-lang/trait-system-refactor-initiative/issues/30).

An alternative would be to eagerly detect trivial where-bounds when constructing the `ParamEnv`. We can't entirely drop them [as explained above](https://hackmd.io/qoesqyzVTe2v9cOgFXd2SQ#Consider-true-global-where-bounds-at-all), so we'd instead replace them with a new clause kind `TraitImpliedByImpl` which gets entirely ignored except when checking whether we should eagerly guide inference via a where-bound. This approach can be extended to where-bounds which are currently not considered global to stop disabling normalization for them as well.

Keeping `'static` in the `param_env` is the simpler solution here and we should be able to move to the second approach without any breakage. I therefore propose to keep `'static` in the environment for now.

---

r? `@compiler-errors`

7 files changed, 344 insertions, 305 deletions

diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs
index 11d72106b22..1af383e9200 100644
--- a/compiler/rustc_trait_selection/src/lib.rs
+++ b/compiler/rustc_trait_selection/src/lib.rs
@@ -23,6 +23,7 @@
 #![feature(extract_if)]
 #![feature(if_let_guard)]
 #![feature(iter_intersperse)]
+#![feature(iterator_try_reduce)]
 #![feature(let_chains)]
 #![feature(never_type)]
 #![feature(rustdoc_internals)]
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 25fe43e3a0e..32a2d5a6d93 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -445,7 +445,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         // Winnow, but record the exact outcome of evaluation, which
         // is needed for specialization. Propagate overflow if it occurs.
-        let mut candidates = candidates
+        let candidates = candidates
             .into_iter()
             .map(|c| match self.evaluate_candidate(stack, &c) {
                 Ok(eval) if eval.may_apply() => {
@@ -458,40 +458,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             .flat_map(Result::transpose)
             .collect::<Result<Vec<_>, _>>()?;
 
-        debug!(?stack, ?candidates, "winnowed to {} candidates", candidates.len());
-
-        let has_non_region_infer = stack.obligation.predicate.has_non_region_infer();
-
-        // If there are STILL multiple candidates, we can further
-        // reduce the list by dropping duplicates -- including
-        // resolving specializations.
-        if candidates.len() > 1 {
-            let mut i = 0;
-            while i < candidates.len() {
-                let should_drop_i = (0..candidates.len()).filter(|&j| i != j).any(|j| {
-                    self.candidate_should_be_dropped_in_favor_of(
-                        &candidates[i],
-                        &candidates[j],
-                        has_non_region_infer,
-                    ) == DropVictim::Yes
-                });
-                if should_drop_i {
-                    debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
-                    candidates.swap_remove(i);
-                } else {
-                    debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
-                    i += 1;
-
-                    // If there are *STILL* multiple candidates, give up
-                    // and report ambiguity.
-                    if i > 1 {
-                        debug!("multiple matches, ambig");
-                        return Ok(None);
-                    }
-                }
-            }
-        }
-
+        debug!(?stack, ?candidates, "{} potentially applicable candidates", candidates.len());
         // If there are *NO* candidates, then there are no impls --
         // that we know of, anyway. Note that in the case where there
         // are unbound type variables within the obligation, it might
@@ -508,13 +475,18 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             // to have emitted at least one.
             if stack.obligation.predicate.references_error() {
                 debug!(?stack.obligation.predicate, "found error type in predicate, treating as ambiguous");
-                return Ok(None);
+                Ok(None)
+            } else {
+                Err(Unimplemented)
+            }
+        } else {
+            let has_non_region_infer = stack.obligation.predicate.has_non_region_infer();
+            if let Some(candidate) = self.winnow_candidates(has_non_region_infer, candidates) {
+                self.filter_reservation_impls(candidate)
+            } else {
+                Ok(None)
             }
-            return Err(Unimplemented);
         }
-
-        // Just one candidate left.
-        self.filter_reservation_impls(candidates.pop().unwrap().candidate)
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -1803,18 +1775,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 }
 
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
-enum DropVictim {
-    Yes,
-    No,
-}
-
-impl DropVictim {
-    fn drop_if(should_drop: bool) -> DropVictim {
-        if should_drop { DropVictim::Yes } else { DropVictim::No }
-    }
-}
-
 /// ## Winnowing
 ///
 /// Winnowing is the process of attempting to resolve ambiguity by
@@ -1822,131 +1782,149 @@ impl DropVictim {
 /// type variables and then we also attempt to evaluate recursive
 /// bounds to see if they are satisfied.
 impl<'tcx> SelectionContext<'_, 'tcx> {
-    /// Returns `DropVictim::Yes` if `victim` should be dropped in favor of
-    /// `other`. Generally speaking we will drop duplicate
-    /// candidates and prefer where-clause candidates.
+    /// If there are multiple ways to prove a trait goal, we make some
+    /// *fairly arbitrary* choices about which candidate is actually used.
     ///
-    /// See the comment for "SelectionCandidate" for more details.
-    #[instrument(level = "debug", skip(self))]
-    fn candidate_should_be_dropped_in_favor_of(
+    /// For more details, look at the implementation of this method :)
+    #[instrument(level = "debug", skip(self), ret)]
+    fn winnow_candidates(
         &mut self,
-        victim: &EvaluatedCandidate<'tcx>,
-        other: &EvaluatedCandidate<'tcx>,
         has_non_region_infer: bool,
-    ) -> DropVictim {
-        if victim.candidate == other.candidate {
-            return DropVictim::Yes;
+        mut candidates: Vec<EvaluatedCandidate<'tcx>>,
+    ) -> Option<SelectionCandidate<'tcx>> {
+        if candidates.len() == 1 {
+            return Some(candidates.pop().unwrap().candidate);
+        }
+
+        // We prefer trivial builtin candidates, i.e. builtin impls without any nested
+        // requirements, over all others. This is a fix for #53123 and prevents winnowing
+        // from accidentally extending the lifetime of a variable.
+        let mut trivial_builtin = candidates
+            .iter()
+            .filter(|c| matches!(c.candidate, BuiltinCandidate { has_nested: false }));
+        if let Some(_trivial) = trivial_builtin.next() {
+            // There should only ever be a single trivial builtin candidate
+            // as they would otherwise overlap.
+            debug_assert_eq!(trivial_builtin.next(), None);
+            return Some(BuiltinCandidate { has_nested: false });
         }
 
-        // Check if a bound would previously have been removed when normalizing
-        // the param_env so that it can be given the lowest priority. See
-        // #50825 for the motivation for this.
-        let is_global =
-            |cand: ty::PolyTraitPredicate<'tcx>| cand.is_global() && !cand.has_bound_vars();
+        // Before we consider where-bounds, we have to deduplicate them here and also
+        // drop where-bounds in case the same where-bound exists without bound vars.
+        // This is necessary as elaborating super-trait bounds may result in duplicates.
+        'search_victim: loop {
+            for (i, this) in candidates.iter().enumerate() {
+                let ParamCandidate(this) = this.candidate else { continue };
+                for (j, other) in candidates.iter().enumerate() {
+                    if i == j {
+                        continue;
+                    }
 
-        // (*) Prefer `BuiltinCandidate { has_nested: false }`, `PointeeCandidate`,
-        // or `DiscriminantKindCandidate` to anything else.
-        //
-        // This is a fix for #53123 and prevents winnowing from accidentally extending the
-        // lifetime of a variable.
-        match (&other.candidate, &victim.candidate) {
-            // FIXME(@jswrenn): this should probably be more sophisticated
-            (TransmutabilityCandidate, _) | (_, TransmutabilityCandidate) => DropVictim::No,
-
-            // (*)
-            (BuiltinCandidate { has_nested: false }, _) => DropVictim::Yes,
-            (_, BuiltinCandidate { has_nested: false }) => DropVictim::No,
-
-            (ParamCandidate(other), ParamCandidate(victim)) => {
-                let same_except_bound_vars = other.skip_binder().trait_ref
-                    == victim.skip_binder().trait_ref
-                    && other.skip_binder().polarity == victim.skip_binder().polarity
-                    && !other.skip_binder().trait_ref.has_escaping_bound_vars();
-                if same_except_bound_vars {
-                    // See issue #84398. In short, we can generate multiple ParamCandidates which are
-                    // the same except for unused bound vars. Just pick the one with the fewest bound vars
-                    // or the current one if tied (they should both evaluate to the same answer). This is
-                    // probably best characterized as a "hack", since we might prefer to just do our
-                    // best to *not* create essentially duplicate candidates in the first place.
-                    DropVictim::drop_if(other.bound_vars().len() <= victim.bound_vars().len())
-                } else {
-                    DropVictim::No
+                    let ParamCandidate(other) = other.candidate else { continue };
+                    if this == other {
+                        candidates.remove(j);
+                        continue 'search_victim;
+                    }
+
+                    if this.skip_binder().trait_ref == other.skip_binder().trait_ref
+                        && this.skip_binder().polarity == other.skip_binder().polarity
+                        && !this.skip_binder().trait_ref.has_escaping_bound_vars()
+                    {
+                        candidates.remove(j);
+                        continue 'search_victim;
+                    }
                 }
             }
 
-            (
-                ParamCandidate(other_cand),
-                ImplCandidate(..)
-                | AutoImplCandidate
-                | ClosureCandidate { .. }
-                | AsyncClosureCandidate
-                | AsyncFnKindHelperCandidate
-                | CoroutineCandidate
-                | FutureCandidate
-                | IteratorCandidate
-                | AsyncIteratorCandidate
-                | FnPointerCandidate { .. }
-                | BuiltinObjectCandidate
-                | BuiltinUnsizeCandidate
-                | TraitUpcastingUnsizeCandidate(_)
-                | BuiltinCandidate { .. }
-                | TraitAliasCandidate
-                | ObjectCandidate(_)
-                | ProjectionCandidate(_),
-            ) => {
-                // We have a where clause so don't go around looking
-                // for impls. Arbitrarily give param candidates priority
-                // over projection and object candidates.
-                //
-                // Global bounds from the where clause should be ignored
-                // here (see issue #50825).
-                DropVictim::drop_if(!is_global(*other_cand))
-            }
-            (ObjectCandidate(_) | ProjectionCandidate(_), ParamCandidate(victim_cand)) => {
-                // Prefer these to a global where-clause bound
-                // (see issue #50825).
-                if is_global(*victim_cand) { DropVictim::Yes } else { DropVictim::No }
+            break;
+        }
+
+        // The next highest priority is for non-global where-bounds. However, while we don't
+        // prefer global where-clauses here, we do bail with ambiguity when encountering both
+        // a global and a non-global where-clause.
+        //
+        // Our handling of where-bounds is generally fairly messy but necessary for backwards
+        // compatability, see #50825 for why we need to handle global where-bounds like this.
+        let is_global = |c: ty::PolyTraitPredicate<'tcx>| c.is_global() && !c.has_bound_vars();
+        let param_candidates = candidates
+            .iter()
+            .filter_map(|c| if let ParamCandidate(p) = c.candidate { Some(p) } else { None });
+        let mut has_global_bounds = false;
+        let mut param_candidate = None;
+        for c in param_candidates {
+            if is_global(c) {
+                has_global_bounds = true;
+            } else if param_candidate.replace(c).is_some() {
+                // Ambiguity, two potentially different where-clauses
+                return None;
             }
-            (
-                ImplCandidate(_)
-                | AutoImplCandidate
-                | ClosureCandidate { .. }
-                | AsyncClosureCandidate
-                | AsyncFnKindHelperCandidate
-                | CoroutineCandidate
-                | FutureCandidate
-                | IteratorCandidate
-                | AsyncIteratorCandidate
-                | FnPointerCandidate { .. }
-                | BuiltinObjectCandidate
-                | BuiltinUnsizeCandidate
-                | TraitUpcastingUnsizeCandidate(_)
-                | BuiltinCandidate { has_nested: true }
-                | TraitAliasCandidate,
-                ParamCandidate(victim_cand),
-            ) => {
-                // Prefer these to a global where-clause bound
-                // (see issue #50825).
-                DropVictim::drop_if(
-                    is_global(*victim_cand) && other.evaluation.must_apply_modulo_regions(),
-                )
+        }
+        if let Some(predicate) = param_candidate {
+            // Ambiguity, a global and a non-global where-bound.
+            if has_global_bounds {
+                return None;
+            } else {
+                return Some(ParamCandidate(predicate));
             }
+        }
+
+        // Prefer alias-bounds over blanket impls for rigid associated types. This is
+        // fairly arbitrary but once again necessary for backwards compatibility.
+        // If there are multiple applicable candidates which don't affect type inference,
+        // choose the one with the lowest index.
+        let alias_bound = candidates
+            .iter()
+            .filter_map(|c| if let ProjectionCandidate(i) = c.candidate { Some(i) } else { None })
+            .try_reduce(|c1, c2| if has_non_region_infer { None } else { Some(c1.min(c2)) });
+        match alias_bound {
+            Some(Some(index)) => return Some(ProjectionCandidate(index)),
+            Some(None) => {}
+            None => return None,
+        }
+
+        // Need to prioritize builtin trait object impls as `<dyn Any as Any>::type_id`
+        // should use the vtable method and not the method provided by the user-defined
+        // impl `impl<T: ?Sized> Any for T { .. }`. This really shouldn't exist but is
+        // necessary due to #57893. We again arbitrarily prefer the applicable candidate
+        // with the lowest index.
+        let object_bound = candidates
+            .iter()
+            .filter_map(|c| if let ObjectCandidate(i) = c.candidate { Some(i) } else { None })
+            .try_reduce(|c1, c2| if has_non_region_infer { None } else { Some(c1.min(c2)) });
+        match object_bound {
+            Some(Some(index)) => return Some(ObjectCandidate(index)),
+            Some(None) => {}
+            None => return None,
+        }
 
-            (ProjectionCandidate(i), ProjectionCandidate(j))
-            | (ObjectCandidate(i), ObjectCandidate(j)) => {
-                // Arbitrarily pick the lower numbered candidate for backwards
-                // compatibility reasons. Don't let this affect inference.
-                DropVictim::drop_if(i < j && !has_non_region_infer)
+        // Finally, handle overlapping user-written impls.
+        let impls = candidates.iter().filter_map(|c| {
+            if let ImplCandidate(def_id) = c.candidate {
+                Some((def_id, c.evaluation))
+            } else {
+                None
             }
-            (ObjectCandidate(_), ProjectionCandidate(_))
-            | (ProjectionCandidate(_), ObjectCandidate(_)) => {
-                bug!("Have both object and projection candidate")
+        });
+        let mut impl_candidate = None;
+        for c in impls {
+            if let Some(prev) = impl_candidate.replace(c) {
+                if self.prefer_lhs_over_victim(has_non_region_infer, c, prev) {
+                    // Ok, prefer `c` over the previous entry
+                } else if self.prefer_lhs_over_victim(has_non_region_infer, prev, c) {
+                    // Ok, keep `prev` instead of the new entry
+                    impl_candidate = Some(prev);
+                } else {
+                    // Ambiguity, two potentially different where-clauses
+                    return None;
+                }
             }
-
-            // Arbitrarily give projection and object candidates priority.
-            (
-                ObjectCandidate(_) | ProjectionCandidate(_),
-                ImplCandidate(..)
+        }
+        if let Some((def_id, _evaluation)) = impl_candidate {
+            // Don't use impl candidates which overlap with other candidates.
+            // This should pretty much only ever happen with malformed impls.
+            if candidates.iter().all(|c| match c.candidate {
+                BuiltinCandidate { has_nested: _ }
+                | TransmutabilityCandidate
                 | AutoImplCandidate
                 | ClosureCandidate { .. }
                 | AsyncClosureCandidate
@@ -1955,155 +1933,113 @@ impl<'tcx> SelectionContext<'_, 'tcx> {
                 | FutureCandidate
                 | IteratorCandidate
                 | AsyncIteratorCandidate
-                | FnPointerCandidate { .. }
-                | BuiltinObjectCandidate
-                | BuiltinUnsizeCandidate
+                | FnPointerCandidate
+                | TraitAliasCandidate
                 | TraitUpcastingUnsizeCandidate(_)
-                | BuiltinCandidate { .. }
-                | TraitAliasCandidate,
-            ) => DropVictim::Yes,
-
-            (
-                ImplCandidate(..)
-                | AutoImplCandidate
-                | ClosureCandidate { .. }
-                | AsyncClosureCandidate
-                | AsyncFnKindHelperCandidate
-                | CoroutineCandidate
-                | FutureCandidate
-                | IteratorCandidate
-                | AsyncIteratorCandidate
-                | FnPointerCandidate { .. }
                 | BuiltinObjectCandidate
-                | BuiltinUnsizeCandidate
-                | TraitUpcastingUnsizeCandidate(_)
-                | BuiltinCandidate { .. }
-                | TraitAliasCandidate,
-                ObjectCandidate(_) | ProjectionCandidate(_),
-            ) => DropVictim::No,
-
-            (&ImplCandidate(other_def), &ImplCandidate(victim_def)) => {
-                // See if we can toss out `victim` based on specialization.
-                // While this requires us to know *for sure* that the `other` impl applies
-                // we still use modulo regions here.
-                //
-                // This is fine as specialization currently assumes that specializing
-                // impls have to be always applicable, meaning that the only allowed
-                // region constraints may be constraints also present on the default impl.
-                let tcx = self.tcx();
-                if other.evaluation.must_apply_modulo_regions()
-                    && tcx.specializes((other_def, victim_def))
-                {
-                    return DropVictim::Yes;
-                }
-
-                match tcx.impls_are_allowed_to_overlap(other_def, victim_def) {
-                    // For #33140 the impl headers must be exactly equal, the trait must not have
-                    // any associated items and there are no where-clauses.
-                    //
-                    // We can just arbitrarily drop one of the impls.
-                    Some(ty::ImplOverlapKind::FutureCompatOrderDepTraitObjects) => {
-                        assert_eq!(other.evaluation, victim.evaluation);
-                        DropVictim::Yes
-                    }
-                    // For candidates which already reference errors it doesn't really
-                    // matter what we do 🤷
-                    Some(ty::ImplOverlapKind::Permitted { marker: false }) => {
-                        DropVictim::drop_if(other.evaluation.must_apply_considering_regions())
-                    }
-                    Some(ty::ImplOverlapKind::Permitted { marker: true }) => {
-                        // Subtle: If the predicate we are evaluating has inference
-                        // variables, do *not* allow discarding candidates due to
-                        // marker trait impls.
-                        //
-                        // Without this restriction, we could end up accidentally
-                        // constraining inference variables based on an arbitrarily
-                        // chosen trait impl.
-                        //
-                        // Imagine we have the following code:
-                        //
-                        // ```rust
-                        // #[marker] trait MyTrait {}
-                        // impl MyTrait for u8 {}
-                        // impl MyTrait for bool {}
-                        // ```
-                        //
-                        // And we are evaluating the predicate `<_#0t as MyTrait>`.
-                        //
-                        // During selection, we will end up with one candidate for each
-                        // impl of `MyTrait`. If we were to discard one impl in favor
-                        // of the other, we would be left with one candidate, causing
-                        // us to "successfully" select the predicate, unifying
-                        // _#0t with (for example) `u8`.
-                        //
-                        // However, we have no reason to believe that this unification
-                        // is correct - we've essentially just picked an arbitrary
-                        // *possibility* for _#0t, and required that this be the *only*
-                        // possibility.
-                        //
-                        // Eventually, we will either:
-                        // 1) Unify all inference variables in the predicate through
-                        // some other means (e.g. type-checking of a function). We will
-                        // then be in a position to drop marker trait candidates
-                        // without constraining inference variables (since there are
-                        // none left to constrain)
-                        // 2) Be left with some unconstrained inference variables. We
-                        // will then correctly report an inference error, since the
-                        // existence of multiple marker trait impls tells us nothing
-                        // about which one should actually apply.
-                        DropVictim::drop_if(
-                            !has_non_region_infer
-                                && other.evaluation.must_apply_considering_regions(),
-                        )
-                    }
-                    None => DropVictim::No,
-                }
+                | BuiltinUnsizeCandidate => false,
+                // Non-global param candidates have already been handled, global
+                // where-bounds get ignored.
+                ParamCandidate(_) | ImplCandidate(_) => true,
+                ProjectionCandidate(_) | ObjectCandidate(_) => unreachable!(),
+            }) {
+                return Some(ImplCandidate(def_id));
+            } else {
+                return None;
             }
+        }
 
-            (AutoImplCandidate, ImplCandidate(_)) | (ImplCandidate(_), AutoImplCandidate) => {
-                DropVictim::No
-            }
+        if candidates.len() == 1 {
+            Some(candidates.pop().unwrap().candidate)
+        } else {
+            // Also try ignoring all global where-bounds and check whether we end
+            // with a unique candidate in this case.
+            let mut not_a_global_where_bound = candidates
+                .into_iter()
+                .filter(|c| !matches!(c.candidate, ParamCandidate(p) if is_global(p)));
+            not_a_global_where_bound
+                .next()
+                .map(|c| c.candidate)
+                .filter(|_| not_a_global_where_bound.next().is_none())
+        }
+    }
 
-            (AutoImplCandidate, _) | (_, AutoImplCandidate) => {
-                bug!(
-                    "default implementations shouldn't be recorded \
-                    when there are other global candidates: {:?} {:?}",
-                    other,
-                    victim
-                );
+    fn prefer_lhs_over_victim(
+        &self,
+        has_non_region_infer: bool,
+        (lhs, lhs_evaluation): (DefId, EvaluationResult),
+        (victim, victim_evaluation): (DefId, EvaluationResult),
+    ) -> bool {
+        let tcx = self.tcx();
+        // See if we can toss out `victim` based on specialization.
+        //
+        // While this requires us to know *for sure* that the `lhs` impl applies
+        // we still use modulo regions here. This is fine as specialization currently
+        // assumes that specializing impls have to be always applicable, meaning that
+        // the only allowed region constraints may be constraints also present on the default impl.
+        if lhs_evaluation.must_apply_modulo_regions() {
+            if tcx.specializes((lhs, victim)) {
+                return true;
             }
+        }
 
-            // Everything else is ambiguous
-            (
-                ImplCandidate(_)
-                | ClosureCandidate { .. }
-                | AsyncClosureCandidate
-                | AsyncFnKindHelperCandidate
-                | CoroutineCandidate
-                | FutureCandidate
-                | IteratorCandidate
-                | AsyncIteratorCandidate
-                | FnPointerCandidate { .. }
-                | BuiltinObjectCandidate
-                | BuiltinUnsizeCandidate
-                | TraitUpcastingUnsizeCandidate(_)
-                | BuiltinCandidate { has_nested: true }
-                | TraitAliasCandidate,
-                ImplCandidate(_)
-                | ClosureCandidate { .. }
-                | AsyncClosureCandidate
-                | AsyncFnKindHelperCandidate
-                | CoroutineCandidate
-                | FutureCandidate
-                | IteratorCandidate
-                | AsyncIteratorCandidate
-                | FnPointerCandidate { .. }
-                | BuiltinObjectCandidate
-                | BuiltinUnsizeCandidate
-                | TraitUpcastingUnsizeCandidate(_)
-                | BuiltinCandidate { has_nested: true }
-                | TraitAliasCandidate,
-            ) => DropVictim::No,
+        match tcx.impls_are_allowed_to_overlap(lhs, victim) {
+            // For #33140 the impl headers must be exactly equal, the trait must not have
+            // any associated items and there are no where-clauses.
+            //
+            // We can just arbitrarily drop one of the impls.
+            Some(ty::ImplOverlapKind::FutureCompatOrderDepTraitObjects) => {
+                assert_eq!(lhs_evaluation, victim_evaluation);
+                true
+            }
+            // For candidates which already reference errors it doesn't really
+            // matter what we do 🤷
+            Some(ty::ImplOverlapKind::Permitted { marker: false }) => {
+                lhs_evaluation.must_apply_considering_regions()
+            }
+            Some(ty::ImplOverlapKind::Permitted { marker: true }) => {
+                // Subtle: If the predicate we are evaluating has inference
+                // variables, do *not* allow discarding candidates due to
+                // marker trait impls.
+                //
+                // Without this restriction, we could end up accidentally
+                // constraining inference variables based on an arbitrarily
+                // chosen trait impl.
+                //
+                // Imagine we have the following code:
+                //
+                // ```rust
+                // #[marker] trait MyTrait {}
+                // impl MyTrait for u8 {}
+                // impl MyTrait for bool {}
+                // ```
+                //
+                // And we are evaluating the predicate `<_#0t as MyTrait>`.
+                //
+                // During selection, we will end up with one candidate for each
+                // impl of `MyTrait`. If we were to discard one impl in favor
+                // of the other, we would be left with one candidate, causing
+                // us to "successfully" select the predicate, unifying
+                // _#0t with (for example) `u8`.
+                //
+                // However, we have no reason to believe that this unification
+                // is correct - we've essentially just picked an arbitrary
+                // *possibility* for _#0t, and required that this be the *only*
+                // possibility.
+                //
+                // Eventually, we will either:
+                // 1) Unify all inference variables in the predicate through
+                // some other means (e.g. type-checking of a function). We will
+                // then be in a position to drop marker trait candidates
+                // without constraining inference variables (since there are
+                // none left to constrain)
+                // 2) Be left with some unconstrained inference variables. We
+                // will then correctly report an inference error, since the
+                // existence of multiple marker trait impls tells us nothing
+                // about which one should actually apply.
+                !has_non_region_infer && lhs_evaluation.must_apply_considering_regions()
+            }
+            None => false,
         }
     }
 }
diff --git a/tests/ui/const-generics/min_const_generics/param-env-eager-norm-dedup.rs b/tests/ui/const-generics/min_const_generics/param-env-eager-norm-dedup.rs
new file mode 100644
index 00000000000..9600b3875ba
--- /dev/null
+++ b/tests/ui/const-generics/min_const_generics/param-env-eager-norm-dedup.rs
@@ -0,0 +1,23 @@
+//@ check-pass
+
+// This caused a regression in a crater run in #132325.
+//
+// The underlying issue is a really subtle implementation detail.
+//
+// When building the `param_env` for `Trait` we start out with its
+// explicit predicates `Self: Trait` and `Self: for<'a> Super<'a, { 1 + 1 }>`.
+//
+// When normalizing the environment we also elaborate. This implicitly
+// deduplicates its returned predicates. We currently first eagerly
+// normalize constants in the unnormalized param env to avoid issues
+// caused by our lack of deferred alias equality.
+//
+// So we actually elaborate `Self: Trait` and `Self: for<'a> Super<'a, 2>`,
+// resulting in a third `Self: for<'a> Super<'a, { 1 + 1 }>` predicate which
+// then gets normalized to  `Self: for<'a> Super<'a, 2>` at which point we
+// do not deduplicate however. By failing to handle equal where-bounds in
+// candidate selection, this caused ambiguity when checking that `Trait` is
+// well-formed.
+trait Super<'a, const N: usize> {}
+trait Trait: for<'a> Super<'a, { 1 + 1 }> {}
+fn main() {}
diff --git a/tests/ui/traits/winnowing/global-non-global-env-1.rs b/tests/ui/traits/winnowing/global-non-global-env-1.rs
new file mode 100644
index 00000000000..d232d32dddf
--- /dev/null
+++ b/tests/ui/traits/winnowing/global-non-global-env-1.rs
@@ -0,0 +1,18 @@
+//@ check-pass
+
+// A regression test for an edge case of candidate selection
+// in the old trait solver, see #132325 for more details.
+
+trait Trait<T> {}
+impl<T> Trait<T> for () {}
+
+fn impls_trait<T: Trait<U>, U>(_: T) -> U { todo!() }
+fn foo<T>() -> u32
+where
+    (): Trait<u32>,
+    (): Trait<T>,
+{
+    impls_trait(())
+}
+
+fn main() {}
diff --git a/tests/ui/traits/winnowing/global-non-global-env-2.rs b/tests/ui/traits/winnowing/global-non-global-env-2.rs
new file mode 100644
index 00000000000..c73d0f06cd9
--- /dev/null
+++ b/tests/ui/traits/winnowing/global-non-global-env-2.rs
@@ -0,0 +1,20 @@
+//@ check-pass
+
+// A regression test for an edge case of candidate selection
+// in the old trait solver, see #132325 for more details. Unlike
+// the first test, this one has two impl candidates.
+
+trait Trait<T> {}
+impl Trait<u32> for () {}
+impl Trait<u64> for () {}
+
+fn impls_trait<T: Trait<U>, U>(_: T) -> U { todo!() }
+fn foo<T>() -> u32
+where
+    (): Trait<u32>,
+    (): Trait<T>,
+{
+    impls_trait(())
+}
+
+fn main() {}
diff --git a/tests/ui/traits/winnowing/global-non-global-env-3.rs b/tests/ui/traits/winnowing/global-non-global-env-3.rs
new file mode 100644
index 00000000000..008d07e4144
--- /dev/null
+++ b/tests/ui/traits/winnowing/global-non-global-env-3.rs
@@ -0,0 +1,20 @@
+//@ check-pass
+
+// A regression test for an edge case of candidate selection
+// in the old trait solver, see #132325 for more details. Unlike
+// the second test, the where-bounds are in a different order.
+
+trait Trait<T> {}
+impl Trait<u32> for () {}
+impl Trait<u64> for () {}
+
+fn impls_trait<T: Trait<U>, U>(_: T) -> U { todo!() }
+fn foo<T>() -> u32
+where
+    (): Trait<T>,
+    (): Trait<u32>,
+{
+    impls_trait(())
+}
+
+fn main() {}
diff --git a/tests/ui/traits/winnowing/global-non-global-env-4.rs b/tests/ui/traits/winnowing/global-non-global-env-4.rs
new file mode 100644
index 00000000000..74793620c9e
--- /dev/null
+++ b/tests/ui/traits/winnowing/global-non-global-env-4.rs
@@ -0,0 +1,21 @@
+//@ check-pass
+
+// A regression test for an edge case of candidate selection
+// in the old trait solver, see #132325 for more details. Unlike
+// the third test, this one has 3 impl candidates.
+
+trait Trait<T> {}
+impl Trait<u32> for () {}
+impl Trait<u64> for () {}
+impl Trait<u128> for () {}
+
+fn impls_trait<T: Trait<U>, U>(_: T) -> U { todo!() }
+fn foo<T>() -> u32
+where
+    (): Trait<T>,
+    (): Trait<u32>,
+{
+    impls_trait(())
+}
+
+fn main() {}