Strange rust compiler recursion

I’m not able to understand why this playground piece of code generate an infinite recursion:

#![recursion_limit="10"]

use std::marker::PhantomData;

pub struct Join<T>(T);

impl<T> Join<T>
    where for<'a> &'a T: IntoIterator
{}

pub struct JoinIter<Iter>(PhantomData<Iter>);


impl<'a, T> IntoIterator for &'a Join<T>
    where &'a T: IntoIterator
{
    type IntoIter = JoinIter<<&'a T as IntoIterator>::IntoIter>;
    type Item = ();

    fn into_iter(self) -> Self::IntoIter {
    }
}

fn main() {
}

It is a non-sense code that just exposes the problem. It originate from this SO question

It the above code I would expect an error like:

expected struct JoinIter, found ()

not the error:

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

Is it the problem related to the constructor <&'a T as IntoIterator>::IntoIter?

Could be it a bug?

I’m wandering if it is related in same way with some wrong logic related to the reference &T and the as operator.

This line is the problem. Rust will only search so deep recursively so that compilation ends, because of this it can’t handle recursive definitions that well in some cases. Try and use type erasure to solve this. That can be done with trait objects.

Like this

type IntoIter = JoinIter<Box<dyn Iterator + 'a>>;

Also to me at first seemed a recursive definition.

But now what I not understand is why the compiler search recursively.

This code use generics and T could be anything, not only Join<T>, for example could be Vec<T>: in this case there is no recursion at all.

Moreover in the code above there isn’t any Join monomorphization driven by explicit Join usage like
let join: Join<Vec<i32>>, so what is trying to resolve the compiler?

It is searching recursively to find out what the type of IntoIter is. This is because Rust makes sure that traits are valid when they are defined rather than when they are used, like C++. There is work for lazy normalization, which may solve this problem.


edit links:

http://smallcultfollowing.com/babysteps/blog/2017/01/26/lowering-rust-traits-to-logic/

It is clear for me.
Many Thanks for all the related information!