# candidate preference

We prefer candidates over other candidates 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

## simplified approach in this PR[^1]

- always prefer trivial builtin impls
- then prefer non-global[^global] where-bounds
- if there are no other where-bounds, guide inference
- if there are any other where-bounds even if trivial, ambig
- then prefer alias bounds
- merge everything ignoring trivial where-bounds[^2], if there are no candidates, try using global where-bounds
- prefer builtin trait object implementation over using impls[^3]
- using global where-bounds only matters if they are unsatisfiable

**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

## Why?

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

#### where-bounds?

fn method_selection<T: Into<u64>>(x: T) -> Option<u32> {
    x.into().try_into().ok()
    // `T: Into<?0>` and them method selection on `?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

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()
        // `Self::Word: Into<?0>` and then method selection
        // 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

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.

### 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 there are unsatisfiable where-bound :3

**If a where-bound is fully implied then any 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 true 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:

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 guide 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 behavior of this approach to be preferrable as it exclusively removes incompleteness. It also doesn't cause any crater breakage.

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

**This is not implemented in this PR 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`, cc 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.