What's going on with this bizarre recursive type error in Rust?

Question

I have an iterable struct called Join:

use std::iter::Peekable;

#[derive(Debug)]
pub struct Join<T, S> {
    container: T,
    separator: S,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum JoinItem<T, S> {
    Element(T),
    Separator(S),
}

pub struct JoinIter<Iter: Iterator, Sep> {
    iter: Peekable<Iter>,
    sep: Sep,
    next_sep: bool,
}

impl<Iter: Iterator, Sep> JoinIter<Iter, Sep> {
    fn new(iter: Iter, sep: Sep) -> Self {
        JoinIter {
            iter: iter.peekable(),
            sep,
            next_sep: false,
        }
    }
}

impl<I: Iterator, S: Clone> Iterator for JoinIter<I, S> {
    type Item = JoinItem<I::Item, S>;

    /// Advance to the next item in the Join. This will either be the next
    /// element in the underlying iterator, or a clone of the separator.
    fn next(&mut self) -> Option<Self::Item> {
        let sep = &self.sep;
        let next_sep = &mut self.next_sep;

        if *next_sep {
            self.iter.peek().map(|_| {
                *next_sep = false;
                JoinItem::Separator(sep.clone())
            })
        } else {
            self.iter.next().map(|element| {
                *next_sep = true;
                JoinItem::Element(element)
            })
        }
    }
}

A reference to Join implements IntoIterator:

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

    fn into_iter(self) -> Self::IntoIter {
        JoinIter::new(self.container.into_iter(), &self.separator)
    }
}

This compiles and passes usage tests.

I also have an iter method defined on my Join struct:

impl<T, S> Join<T, S>
where
    for<'a> &'a T: IntoIterator,
{
    pub fn iter(&self) -> JoinIter<<&T as IntoIterator>::IntoIter, &S> {
        self.into_iter()
    }
}

This compiles fine, but when I actually try to use it:

fn main() {
    // Create a join struct
    let join = Join {
        container: vec![1, 2, 3],
        separator: ", ",
    };

    // This works fine
    let mut good_ref_iter = (&join).into_iter();
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Element(&1)));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Element(&2)));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(good_ref_iter.next(), Some(JoinItem::Element(&3)));
    assert_eq!(good_ref_iter.next(), None);

    // This line fails to compile; comment out this section and it all works
    let bad_ref_iter = join.iter();
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Element(&1)));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Element(&2)));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Separator(&", ")));
    assert_eq!(bad_ref_iter.next(), Some(JoinItem::Element(&3)));
    assert_eq!(bad_ref_iter.next(), None);
}

I get some kind of weird type recursion error:

error[E0275]: overflow evaluating the requirement `&_: std::marker::Sized`
   --> src/join.rs:288:29
    |
 96 |         let mut iter = join.iter();
    |                             ^^^^
    |
    = help: consider adding a `#![recursion_limit="128"]` 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::Join<_, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<_, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<_, _>, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<join::Join<_, _>, _>, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<join::Join<join::Join<_, _>, _>, _>, _>, _>`
    = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `&join::Join<join::Join<join::Join<join::Join<join::Join<join::Join<_, _>, _>, _>, _>, _>, _>`
...

(I redacted about 100 more lines of recursive type error in the ...)

As best I can tell, it appears to be attempting to proactively evaluate whether &Join<_, _> implements IntoIterator, which requires checking if &Join<Join<_, _>, _> fulfills IntoIterator, and so on forever. What I can't figure out is why it thinks it has to do this, since my actual type is fully qualified as Join<Vec<{integer}, &'static str>. Some things I've tried:

• Moving the trait bound off of the impl header and into the iter function, like so:

  fn iter(&'a self) -> JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S>
  where &'a T: IntoIterator
  

  This has the same result.

• Replacing self.into_iter() with the underlying expression, JoinIter::new(self.container.into_iter(), self.separator), in the hopes that maybe it's struggling to differentiate self.into_iter() from (&self).into_iter(). I've tried all of the following patterns:

  • fn iter(&self) -> ... { self.into_iter() }
  • fn iter(&self) -> ... { (&self).into_iter() }
  • fn iter(&self) -> ... { JoinIter::new(self.container.into_iter(), &self.separator) }
  • fn iter(&self) -> ... { JoinIter::new((&self.container).into_iter(), &self.separator) }
• Speaking of which, replacing the call to self.iter() with (&self).into_iter() fixes the problem, but replacing it with (&self).iter() does not.

Why does (&join).into_iter() work, but join.iter() does not, even though iter() simply calls self.into_iter() under the hood?

This complete example, with identical code, is also available in the Rust Playground

---

For more context about Join, see my older Stack Overflow question and my actual source code.

Answer 1

It seems that the compiler is not able to resolve the trait requirement needed by iter() return type JoinIter<<&T as IntoIterator>::IntoIter, &S>.

I've received an hint for this from rustc --explain E0275 error explanation:

This error occurs when there was a recursive trait requirement that overflowed before it could be evaluated. Often this means that there is unbounded recursion in resolving some type bounds.

I don't know the details of the inference process of rust, I imagine the following is happening.

Take this signature:

fn iter(&self) -> JoinIter<<&T as IntoIterator>::IntoIter, &S>

The compiler try to infer the return type from:

JoinIter<<&T as IntoIterator>::IntoIter, &S>

but <&T as IntoIterator>::IntoIter is inferred from the &'a Join impl:

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

    fn into_iter(self) -> Self::IntoIter {
        JoinIter::new(self.container.into_iter(), &self.separator)
    }
}

and IntoIter is again a JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S> that has an IntoIter and so and so ad infinitum.

A way to make it compile it is to help the compiler with a turbofish:

let mut bad_ref_iter = Join::<Vec<i32>, &str>::iter(&join);

instead of:

let bad_ref_iter = join.iter();

Update

The line:

type IntoIter = JoinIter<<&'a T as IntoIterator>::IntoIter, &'a S>;    

generate a recursion because Rust checks that traits are valid when they are defined rather than when they are used.

See this post for some more details and pointers to the progress of work of lazy normalization, which may solve this problem.