Repository: rust
Issue: Compiler (effectively) hangs, regression from overflow error
Labels: A-lifetimes,A-trait-system,I-compiletime,P-high,regression-from-stable-to-stable,C-bug,perf-regression,T-types

```rs
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`](https://godbolt.org/z/Er3v1xrPd)
```
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

<hr>

_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](https://godbolt.org/z/cehTbs9cz). (The fixed version also works on some older Rust versions, including `1.55` and older.)


<hr>

_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