Incorrect recursion in type inference

[0ndorio]

I encountered a recursion overflow error on a trait implementation of HashMap (Encodable) when I tried to extend an unrelated trait (Inner) by a where clause for the same trait. This might end in a case of 'You are holding it wrong', but I couldn't find any clue why the change should infer with the given implementation:

Minimal Example

Playground

use std::collections::HashMap;

pub trait Encodable {}

pub trait Inner
where
    for<'a> &'a Self: Encodable,
{
}

pub trait Outer {
    type Inner: Inner;
}

impl<'a, K, V, S> Encodable for &'a HashMap<K, V, S>
where
    &'a V: Encodable,
{
}

Error Log

 Compiling playground v0.0.1 (file:///playground)
error[E0275]: overflow evaluating the requirement `_: std::marker::Sized`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
  = note: required because of the requirements on the impl of `for<'a> Encodable` for `&'a std::collections::HashMap<_, _, _>`
  = note: required because of the requirements on the impl of `for<'a> Encodable` for `&'a std::collections::HashMap<_, std::collections::HashMap<_, _, _>, _>`
  = note: required because of the requirements on the impl of `for<'a> Encodable` for `&'a std::collections::HashMap<_, std::collections::HashMap<_, std::collections::HashMap<_, _, _>, _>, _>`
  = note: required because of the requirements on the impl of `for<'a> Encodable` for `&'a std::collections::HashMap<_, std::collections::HashMap<_, std::collections::HashMap<_, std::collections::HashMap<_, _, _>, _>, _>, _>`
  = note: required because of the requirements on the impl of `for<'a> Encodable` for `&'a std::collections::HashMap<_, std::collections::HashMap<_, std::collections::HashMap<_, std::collections::HashMap<_, std::collections::HashMap<_, _, _>, _>, _>, _>, _>`
[...]

Reproduced with:

• stable: rustc 1.24.1 (d3ae9a9 2018-02-27)
• nightly: rustc 1.26.0-nightly (2789b06 2018-03-06)

[o01eg]

Catch this error in my code

error[E0275]: overflow evaluating the requirement `&tokio::reactor::PollEvented2<_>: std::io::Read`
   --> src/xmpp/xmpp_connection.rs:257:48
    |
257 |             stanzas::make_iq_unsupported_error(id, conn.state.client.jid.clone(), from)
    |                                                ^^
    |
    = 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::PollEvented2<tokio::reactor::PollEvented2<_>>`
    = note: required because of the requirements on the impl of `std::io::Read` for `&tokio::reactor::PollEvented2<tokio::reactor::PollEvented2<tokio::reactor::PollEvented2<_>>>`
    = note: required because of the requirements on the impl of `std::io::Read` for `&tokio::reactor::PollEvented2<tokio::reactor::PollEvented2<tokio::reactor::PollEvented2<tokio::reactor::PollEvented2<_>>>>`
...

This commit make error appears: https://bitbucket.org/O01eg/sendxmppd-rust/commits/df0c04b537c0f1fd94f4abcf64af01ff75b97dd5?at=iq-set-processing

Reproduced with rustc 1.34.0 and rustc 1.36.0-dev (316a391 2019-04-19)

[Spoonbender]

Triage: no change

[Dylan-DPC]

Error now:

error[[E0277]](https://doc.rust-lang.org/stable/error_codes/E0277.html): the trait bound `for<'a> &'a <Self as Outer>::Inner: Encodable` is not satisfied
  --> src/main.rs:23:17
   |
23 |     type Inner: Inner;
   |                 ^^^^^ the trait `for<'a> Encodable` is not implemented for `&'a <Self as Outer>::Inner`
   |
   = help: the trait `Encodable` is implemented for `&'a HashMap<K, V, S>`
note: required by a bound in `Inner`
  --> src/main.rs:18:23
   |
16 | pub trait Inner
   |           ----- required by a bound in this
17 | where
18 |     for<'a> &'a Self: Encodable,
   |                       ^^^^^^^^^ required by this bound in `Inner`

[LucasFA]

FWIW, this is a slightly reduced version of the code:

pub trait Encodable {}

pub trait Inner
where
    for<'a> &'a Self: Encodable, {
}

pub trait Outer {
    type Inner: Inner;
}

struct SomeStruct {}

impl<'a> Encodable for SomeStruct 
where
    &'a Self: Encodable, {
}

One way or the other, the original bug has disappeared and the only reason this does not compile is the unsatisfied trait bound which can be fixed with the suggestion, which really is just to explicitly require what the Inner trait requires or instead use this:

pub trait Outer {
    type InnerType where Self::InnerType: Inner;
}

So maybe this can be closed?