Type inference in the presence of recursive impls may result in an error message that mentions seemingly unrelated types

[alexwl]

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

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
   ...

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

#[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

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<_>>>`
  ...

It seems that there are a number of existing issues that have the same underlying cause (type inference in the presence of recursive impls):

#61800
#60603
#57854
#39959
#49017
#37748
#34137

[programmerjake]

affecting me too, I know I missed something in my code, but the compiler's error message is entirely unhelpful.

[trinity-1686a]

I think I'm hitting the same issue, with Vec<u8>, &mut T and Write. Do you know what kind of type annotations may help me?

[alexwl]

@fdb-hiroshima Can you post the error message you get?

This is an example with Vec, Write and &mut, but I'm not sure if it is relevant to
your problem:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7837c900ee87fbe2e6c8043365480316

trait Write {}

impl <'a,T> Write for &'a mut std::vec::Vec<T> where &'a mut T:Write {}
impl <'a> Write for &'a mut u8 {}

fn foo<T: Write>(_arg:T) {}

fn main() {
    let mut v = vec![];
    foo(&mut v);
}

This code fails with "overflow evaluating the requirement &mut std::vec::Vec<_>: Write"

Type annotation for v fixes the error:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e577573dab034eefc496c996fc6cf639

trait Write {}

impl <'a,T> Write for &'a mut std::vec::Vec<T> where &'a mut T:Write {}
impl <'a> Write for &'a mut u8 {}

fn foo<T: Write>(_arg:T) {}

fn main() {
    let mut v:std::vec::Vec<u8> = vec![];
    foo(&mut v);
}