rustc thread stack overflow when iterating recursively

[torkleyy]

There is a bug in the compiler which causes it to crash when I try to iterate through a recursive structure (using flat_map):

thread 'rustc' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)

Here's my code:

#![feature(conservative_impl_trait)]

pub struct Foo {
    children: Vec<Foo>,
}

impl Foo {
    pub fn iter_all_children<'a>(&'a self) -> impl Iterator<Item = &'a Foo> {
        self.children.iter().flat_map(|x| x.iter_all_children())
    }
}

fn main() {
    let foo = Foo { children: Vec::new() };
    let v: Vec<_> = foo.iter_all_children().collect();
}

Version

I'm using the most recent nightly (rustc 1.17.0-nightly (0648517 2017-02-03)), however this is also reproducable with rustc 1.16 using the Playground (https://is.gd/QYkYTk).

---

I don't know much about how rustc works but I think the problem is somewhere in the conversion from MIR to LLVM IR because generating MIR works.

[Stebalien]

It's actually a problem with the type hidden by impl Iterator<Item = &Foo>: it's an infinitely sized recursive type:

struct FlatMap<Iter<'a>, FlatMap<Iter<'a>>, ...> {
    iter: Iter<'a>,
    subiter: Option<Self> // recursive
}

You can fix this by boxing:

use std::slice::Iter;

pub struct Foo {
    children: Vec<Foo>,
}

impl Foo {
    pub fn iter_all_children<'a>(&'a self) -> Box<Iterator<Item=&'a Foo> + 'a> {
        Box::new(self.children.iter().flat_map(|x| x.iter_all_children())) as Box<Iterator<Item=&'a Foo> + 'a>
    }
}

fn main() {
    let foo = Foo { children: Vec::new() };
    let v: Vec<_> = foo.iter_all_children().collect();
}

Note: this is still a bug in rustc (it shouldn't just crash).

[cramertj]

Dup of #38064