Repository: rust
Issue: Type inference in the presence of recursive impls may result in an error message that mentions seemingly unrelated types
Labels: C-enhancement,A-diagnostics,A-trait-system,T-compiler

Here's an example (tested with 1.36.0 and 1.38.0-nightly):

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=820e0d5fd61e7d9275a4378977488d8a

```rust
trait Trait {}

struct Struct1<T>(T);
struct Struct2<T>(T);

//error message depends on the order of impls
impl <T> Trait for Option<Struct2<T>> where Option<T>:Trait {}
impl <T> Trait for Option<Struct1<T>> where Option<T>:Trait {}

fn foo<E: Trait>() {}

fn main() {
    foo::<Option<Struct1<_>>>();
}
```

The error message:

```
error[E0275]: overflow evaluating the requirement `std::option::Option<Struct2<_>>: Trait`
  --> src/main.rs:13:5
   |
13 |     foo::<Option<Struct1<_>>>();
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because of the requirements on the impl of `Trait` for `std::option::Option<Struct2<Struct2<_>>>`
   = note: required because of the requirements on the impl of `Trait` for `std::option::Option<Struct2<Struct2<Struct2<_>>>>`
   ....
```

I understand that Rust doesn't guarantee that trait resolution is decidable, so overflows are expected in certain cases. Of course, message "type annotations needed" would be much more helpful than "overflow evaluating the requirement", but I guess this is the price we have to pay for 'aggressive' type inference.

What is really confusing is the fact that the compiler reports that it fails to evaluate `Option<Struct2<_>>:Trait`, when the code clearly shows that the original obligation is `Option<Struct1<_>>:Trait` (`Struct2` is not mentioned anywhere besides the first impl).

It seems that obligations are evaluated in the following order:

1. Option<Struct1<_>> : Trait
2. Option<_> : Trait
3. Option<Struct2<_>>: Trait
4. Option<Struct2<Struct2<_>>>: Trait
5. Option<Struct2<Struct2<Struct2<_>>>>: Trait
...

<br/>

Impls that look like this `impl <T> Trait for Something<Struct<T>> where Something<T>:Trait {..}` are not so rare.

For example, `impl<'a, E> Read for &'a PollEvented<E> where E: Evented, &'a E: Read {..}` from  https://docs.rs/tokio-reactor/0.1.5/tokio_reactor/struct.PollEvented.html.

Here's how this impl may cause confusing error message:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=da7d0c59e214a8536d6872d5069c6500

```rust
#[allow(unused_imports)]
use tokio;

fn foo<T:std::io::Read>() {}

fn main() {
    foo::<&_>();
}
```

The error message:

```
error[E0275]: overflow evaluating the requirement `&tokio_reactor::poll_evented::PollEvented<_>: std::io::Read`
 --> src/main.rs:7:5
  |
7 |     foo::<&_>();
  |     ^^^^^^^^^
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_reactor::poll_evented::PollEvented<tokio_reactor::poll_evented::PollEvented<_>>`
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_reactor::poll_evented::PollEvented<tokio_reactor::poll_evented::PollEvented<tokio_reactor::poll_evented::PollEvented<_>>>`
  ...
```

`PollEvented` is not mentioned anywhere in the code (but the impl is in scope).

Interesting, that if I replace `use tokio;` with an impl for a type that is not in scope:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=5cdebfaedd00f3142924dd256ac1116a

```rust
impl Struct{}//not found in this scope
fn foo<T:std::io::Read>() {}

fn main() {
    foo::<&_>();
}
```

The error message is even more confusing:

```
error[E0275]: overflow evaluating the requirement `&tar::archive::ArchiveInner<_>: std::io::Read`
 --> src/main.rs:6:5
  |
6 |     foo::<&_>();
  |     ^^^^^^^^^
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_reactor::poll_evented::PollEvented<tar::archive::ArchiveInner<_>>`
  = note: required because of the requirements on the impl of `std::io::Read` for `&tokio_reactor::poll_evented::PollEvented<tokio_reactor::poll_evented::PollEvented<tar::archive::ArchiveInner<_>>>`
  ...
```


<br/><br/>

It seems that there are a number of existing issues that have the same underlying cause (type inference in the presence of recursive impls):

https://github.com/rust-lang/rust/issues/61800
https://github.com/rust-lang/rust/issues/60603
https://github.com/rust-lang/rust/issues/57854
https://github.com/rust-lang/rust/issues/39959
https://github.com/rust-lang/rust/issues/49017
https://github.com/rust-lang/rust/issues/37748
https://github.com/rust-lang/rust/issues/34137