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.

[jackh726]

This could potentially be fixed by removing this:

rust/compiler/rustc_infer/src/traits/project.rs

Line 148 in 175b8db

if let Some(ProjectionCacheEntry::Recur) = map.get(&key) {

But that has other implications.

[Mark-Simulacrum]

@rust-lang/wg-traits @Aaron1011 This was marked as P-critical by wg-pri, but it doesn't look like we've seen much progress on resolving this issue (I don't see a linked PR). We missed it in our earlier T-release triage as it wasn't milestoned, but the release is next week -- do we think there's a minimal patch likely that we could backport in time?

We also discuss this in today's release team meeting and there was a general feeling I think that if the crater run we just started doesn't show this to be widespread breakage we're probably OK to accept this breakage (rather than e.g. delaying the release or trying to revert 371f3cd which seems pretty difficult and introduces other regressions, I believe).

[jackh726]

Yeah, this is really rough. #89503 (comment) is one potential patch, but I've tried it before and it ends up causing other fallout that needs its own fixes. Unfortunately, through a series of relatively small bug fixes, we've ended up in a rut that needs larger design decisions/discussions to get out of.

I think we need to see what comes out of the crater run. If this isn't widespread, then I think accepting that this has regressed into a larger class of bugs is better than reverting and running into incremental bugs.

[pietroalbini]

The crater run only reported one crate failing due to this: https://crater-reports.s3.amazonaws.com/beta-1.56-3/beta-2021-10-15/reg/mpstthree-0.0.13/log.txt

[apiraino]

Demoting to P-high after reading the latest comments

@rustbot label -P-critical +P-high

[pnkfelix]

@rustbot label: +T-types -T-compiler