lazy param_env normalization causes ambiguity due to different region constraints

[lcnr]

trait Trait {
    type Assoc<'a>
    where
        Self: 'a;
}

trait Bound<'a> {}
fn impls_bound<'a, T: Bound<'a>>() {}
fn foo<'a, T: 'a>()
where
    T: Trait<Assoc<'a> = T> + Bound<'a>,
    // This env candidate has the additional region constraint: `T: 'a`
    // from normalization, while both candidates constrain `'_` to `'a`.
    T::Assoc<'a>: Bound<'a>,
{
    impls_bound::<'_, T>();
}

affects algar, thanks @adwinwhite for minimizing this issue https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/crater.20triage.20.3A3/near/569445167

This does not affect the following example as there the first candidate has no region constraints, so we simply choose that one

trait Trait {
    type Assoc<'a>
    where
        Self: 'a;
}

trait Bound<'a> {}
fn impls_bound<T: Bound<>() {}
fn foo<'a, T: 'a>()
where
    T: Trait<Assoc<'a> = T> + Bound,
    T::Assoc<'a>: Bound,
{
    impls_bound::<'_, T>();
}

The behavior is implemented in https://github.com/rust-lang/rust/blob/c6936c309add33a7008747866aee081ff5289946/compiler/rustc_next_trait_solver/src/solve/mod.rs#L256-L278

We could prefer candidates over others if they only differ in region constraints and the constraints of one are a strict subset of the others, solving this (and probably a bunch of related) issues.

This is somewhat annoying to implement as we end up unifying regions if they are constrained to be equal, so we can't simply check that all constraits of one candidate are present in the other candidate. Implementing this still doesn't seem too bad.

The other question is whether we want this stronger candidate unification behavior. Slightly unsure about this rn

[lcnr]

https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/crater.20triage.20.3A3/near/573704487 also affects tokio-par-util

trait Trait1 {
    type Assoc1;
}

trait Trait2 {
    type Assoc2;
}

struct Indir<T>(T);
impl<T> Trait2 for Indir<T>
where
    T: Trait1,
    T::Assoc1: Trait2 + 'static,
{
    type Assoc2 = <T::Assoc1 as Trait2>::Assoc2;
}

struct WrapperTwo<T, U>(T, U);

impl<T, U> Trait1 for WrapperTwo<T, U>
where
    T: Trait1,
    T::Assoc1: Trait2 + 'static,
    // additional region constraint in this candidate so they
    // can't be merged.
    U: Trait1<Assoc1 = <Indir<T> as Trait2>::Assoc2>,
    U: Trait1<Assoc1 = <T::Assoc1 as Trait2>::Assoc2>,
{
    type Assoc1 = i32;
}

[adwinwhite]

also affects qazer:

trait Value {
    type SelfType<'a>
    where
        Self: 'a;
}

trait Repository<T> {}
struct RedbRepo<From, Into>(From, Into);

impl<From, Into> Repository<Into> for RedbRepo<From, Into>
where
    for<'a> From: Value<SelfType<'a> = From> + Clone + 'static,
    for<'a> <From as Value>::SelfType<'a>: Clone,
{
}

[adwinwhite]

This case can't be fixed at the moment. See https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/Merge.20env.20candidates/with/580391973

trait Id1 {
    type SelfType<'a>
    where
        Self: 'a;
}

trait Id2 {
    type SelfType<'a>
    where
        Self: 'a;
}

trait Trait {}
struct Wrap<T>(T);

impl<'b, T> Trait for Wrap<&'b T>
where
    T: 'static,
    T: Clone,
    for<'a> T: Id1<SelfType<'a> = T>,
    for<'a> <T as Id1>::SelfType<'a>: Clone,
    T: Id2<SelfType<'b> = T>,
    <T as Id2>::SelfType<'b>: Clone,
{
}