Compiler (effectively) hangs, regression from overflow error

[steffahn]

pub enum Either<L, R> {
    Left(L),
    Right(R),
}

pub trait HasItem<'a, _Constraint = &'a Self> {
    type Item;
}

pub type Item<'a, Self_> = <Self_ as HasItem<'a>>::Item;

pub trait LendingIterator: for<'a> HasItem<'a> {
    fn next(&mut self) -> Option<Item<'_, Self>>;
}

impl<'a, A: 'a, B: 'a> HasItem<'a> for Either<A, B>
where A: LendingIterator, B: LendingIterator,
 for<'b> B: HasItem<'b, Item = Item<'b, Self>>
{
    type Item = Item<'a, Self>;
}

impl<A, B> LendingIterator for Either<A, B>
where A: LendingIterator, B: LendingIterator,
 for<'b> B: HasItem<'b, Item = Item<'b, Self>>
{
    fn next(&mut self) -> Option<Item<'_, Self>> {
        match self {
            Either::Left(iter) => iter.next(),
            Either::Right(iter) => iter.next(),
        }
    }
}

hangs since 1.56
error on 1.55

error[E0275]: overflow evaluating the requirement `for<'b> <B as HasItem<'b>>::Item == <Either<A, B> as HasItem<'b>>::Item`
  --> <source>:16:24
   |
6  | pub trait HasItem<'a, _Constraint = &'a Self> {
   | --------------------------------------------- required by this bound in `HasItem`
...
16 | impl<'a, A: 'a, B: 'a> HasItem<'a> for Either<A, B>
   |                        ^^^^^^^^^^^
   |
note: required because of the requirements on the impl of `HasItem<'a>` for `Either<A, B>`
  --> <source>:16:24
   |
16 | impl<'a, A: 'a, B: 'a> HasItem<'a> for Either<A, B>
   |                        ^^^^^^^^^^^     ^^^^^^^^^^^^

error[E0275]: overflow evaluating the requirement `for<'b> <B as HasItem<'b>>::Item == <Either<A, B> as HasItem<'b>>::Item`
  --> <source>:23:12
   |
12 | pub trait LendingIterator: for<'a> HasItem<'a> {
   |                            ------------------- required by this bound in `LendingIterator`
...
23 | impl<A, B> LendingIterator for Either<A, B>
   |            ^^^^^^^^^^^^^^^
   |
note: required because of the requirements on the impl of `for<'a> HasItem<'a>` for `Either<A, B>`
  --> <source>:16:24
   |
16 | impl<'a, A: 'a, B: 'a> HasItem<'a> for Either<A, B>
   |                        ^^^^^^^^^^^     ^^^^^^^^^^^^

error[E0275]: overflow evaluating the requirement `for<'b> <B as HasItem<'b>>::Item == <Either<A, B> as HasItem<'b>>::Item`
  --> <source>:20:5
   |
20 |     type Item = Item<'a, Self>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: required because of the requirements on the impl of `HasItem<'a>` for `Either<A, B>`
  --> <source>:16:24
   |
16 | impl<'a, A: 'a, B: 'a> HasItem<'a> for Either<A, B>
   |                        ^^^^^^^^^^^     ^^^^^^^^^^^^

error[E0275]: overflow evaluating the requirement `for<'b> <B as HasItem<'b>>::Item == <Either<A, B> as HasItem<'b>>::Item`
  --> <source>:27:8
   |
27 |     fn next(&mut self) -> Option<Item<'_, Self>> {
   |        ^^^^
   |
note: required because of the requirements on the impl of `HasItem<'_>` for `Either<A, B>`
  --> <source>:16:24
   |
16 | impl<'a, A: 'a, B: 'a> HasItem<'a> for Either<A, B>
   |                        ^^^^^^^^^^^     ^^^^^^^^^^^^

error: aborting due to 4 previous errors

@rustbot label I-hang, regression-from-stable-to-stable, A-traits, A-lifetimes, E-needs-bisection, T-compiler

---

Edit:

“Hangs” means “runs for a wile on 100% CPU until I cancel it”. Who knows if it would ever terminate… actually, maybe I should test smaller recursion limits.

Note that this code example is not expected to compile successfully. Here’s a version that works / with the mistakes fixed. (The fixed version also works on some older Rust versions, including 1.55 and older.)

---

Edit2: Using smaller limits (like… around #![recursion_limit = "14"] it starts getting unbearably slow) reveals that this is apparently more like exponential-time slowdown rather than “actual” hanging.

@rustbot label -I-hang, +I-compiletime, +perf-regression

[apiraino]

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

@rustbot label -I-prioritize +P-high

[Badel2]

Run a bisect on this, 8d7707f is the first bad commit.

cargo-bisect-rustc was only able to narrow it down to nightly-2021-08-26, but I checked the remaining range using git bisect.

[steffahn]

Let me remove the bisection label and mention the relevant PR #85499 (cc @jackh726)

@rustbot label -E-needs-bisection

[pnkfelix]

Discussed in T-compiler P-high review

Reassigning to T-types to determine what to do, if anything, in response to this.

@rustbot label -T-compiler +T-types