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^[2] 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^[3], if there are no candidates, try using global where-bounds
  • prefer builtin trait object implementation over using impls^[4]
  • 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.

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.

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.

An alternative would be to eagerly detect trivial where-bounds when constructing the ParamEnv. We can't entirely drop them as explained above, 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.