Where bounds with associated types equality cause overflow.

[mixal-iirec]

Code

I tried this code:

trait Assoc {
    type B;
}
struct Test<U, T>
where
    U: Assoc,
    T: Assoc<B = <U as Assoc>::B>,
{
    a: U,
    c: T,
}
impl<U, T> Assoc for Test<U, T>
where
    U: Assoc,
    T: Assoc<B = <U as Assoc>::B>,
{
    type B = <U as Assoc>::B;
}
trait TestTrait: Assoc {}
impl<U, T> TestTrait for Test<U, T>
where
    U: Assoc,
    T: Assoc<B = <Self as Assoc>::B>,
{
}

It used to compile but now it doesn't because:

error[E0275]: overflow evaluating the requirement `<T as Assoc>::B == <U as Assoc>::B`
  --> src/main.rs:20:1
   |
20 | / impl<U: Assoc, T> TestTrait for Test<U, T>
21 | | where
22 | |     U: Assoc,
23 | |     T: Assoc<B = <Self as Assoc>::B>,
24 | | {
25 | | }
   | |_^
   |
note: required because of the requirements on the impl of `Assoc` for `Test<U, T>`
  --> src/main.rs:12:12
   |
12 | impl<U, T> Assoc for Test<U, T>
   |

Version it worked on

It most recently worked on:
Stable: 1.55.0
Nightly: rustc 1.56.0-nightly (50171c310 2021-09-01)

Version with regression

rustc --version --verbose:

rustc 1.57.0-nightly (f03eb6bef 2021-10-02)
rustc 1.56.0-beta.3 (deef86610 2021-09-17)

(Probably all nightly versions after 2021-09-01)

@rustbot modify labels: +regression-from-stable-to-beta -regression-untriaged

[apiraino]

if it helps, a bisection seems to lead to #85868

searched nightlies: from nightly-2021-08-15 to nightly-2021-10-04
regressed nightly: nightly-2021-09-03
searched commits: from 50171c3 to 371f3cd
regressed commit: 371f3cd

bisected with cargo-bisect-rustc v0.6.0

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo bisect-rustc --start=2021-08-15 

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-critical

[Aaron1011]

It appears that 371f3cd exposed a bug in the handling of projection sub-obligations. If I modify the code to unconditionally cache all sub-obligations (or avoid updating the projection cache entirely), the overflow error still occurs. It looks like the code previous compiled because we used to only store a small subset of the projection subobligations in the cache. Some of the previously-discarded subobligations appear to cause an overflow error when we process them again (when we read the cached projection result).

[Aaron1011]

Minimized:

trait Assoc {
    type B;
}
struct Test<U, T>(U, T);
impl<U, T> Assoc for Test<U, T>
where
    U: Assoc,
    T: Assoc<B = <U as Assoc>::B>,
{
    type B = <U as Assoc>::B;
}
trait TestTrait {}
impl<U, T> TestTrait for Test<U, T>
where
    U: Assoc,
    T: Assoc<B = <Self as Assoc>::B>,
{
}

fn main() {}

produces the following error on Nightly (and succeeds on stable):

error[E0275]: overflow evaluating the requirement `<T as Assoc>::B == <U as Assoc>::B`
  --> src/main.rs:13:1
   |
13 | / impl<U, T> TestTrait for Test<U, T>
14 | | where
15 | |     U: Assoc,
16 | |     T: Assoc<B = <Self as Assoc>::B>,
17 | | {
18 | | }
   | |_^
   |
note: required because of the requirements on the impl of `Assoc` for `Test<U, T>`
  --> src/main.rs:5:12
   |
5  | impl<U, T> Assoc for Test<U, T>
   |            ^^^^^     ^^^^^^^^^^

For more information about this error, try `rustc --explain E0275`.
error: could not compile `playground` due to previous error

[Aaron1011]

I think that this error is actually legitimate:

1. During WF checking of the TestTrait impl, we try to normalize T: Assoc<B = <Self as Assoc>::B>, which requires normalizing <Self as Assoc>::B.
2. We find the Assoc impl, and try to use it. This requires evaluating its where clauses - specifically, T: Assoc<B = <U as Assoc>::B>.
3. However, we are already trying to project <T as Assoc>::B from the first step, so this is a cycle.

cc @rust-lang/wg-traits

[jackh726]

Yeah, this is rough. Essentially the same underlying issue as #87755 and #87758 (among other non-GAT issues) (I think). I've tried to look into this and it's really difficult to solve.

[jackh726]

Oh I see...this is maybe slightly different.