Recursive instantiation for Iterator trait with closure-taking adaptors hangs rustc

[PaulDance]

Hello all,

This is probably a revival of #21403 and might be linked to #77173 and #76351, but I am not quite sure.

When defining a function that accepts a type implementing Iterator<Item = ...> and making a recursive call with the iterator adapted, the compiler reports a recursive instantiation error, which is to be expected. However, when considering some corner cases, the compiler can take quite a bit of time to reach this conclusion and in some others, it hangs "indefinitely".

Code

Consider the following simple example, which does not fail:

fn traverse(mut iter: impl Iterator<Item = u8>) {
    if dbg!(iter.next()).is_some() {
        traverse(iter);
    }
}

fn main() {
    traverse(vec![1, 2, 3, 4].into_iter());
}

It simply traverses the given iterator - in a really weird way yes - and displays each value, yielding:

➜ ./bug 
[bug.rs:2] iter.next() = Some(
    1,
)
[bug.rs:2] iter.next() = Some(
    2,
)
[bug.rs:2] iter.next() = Some(
    3,
)
[bug.rs:2] iter.next() = Some(
    4,
)
[bug.rs:2] iter.next() = None

So no infinite recursion call here. When applying an iterator adaptor to the recursive call, such as by replacing traverse(iter) with traverse(iter.skip(1)), then as expected it yields the error:

➜ rustc bug.rs   
error: reached the recursion limit while instantiating `traverse::<std::iter::Skip<std::...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
 --> bug.rs:3:9
  |
3 |         traverse(iter.skip(1));
  |         ^^^^^^^^^^^^^^^^^^^^^^
  |
note: `traverse` defined here
 --> bug.rs:1:1
  |
1 | fn traverse(mut iter: impl Iterator<Item = u8>) {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

However, when using adaptors that require a closure to be passed as an argument, such as skip_while, it becomes much slower. On my machine:

➜ time rustc bug.rs
error: reached the recursion limit while instantiating `traverse::<std::iter::SkipWhile<...>, [closure@bug.rs:3:34: 3:45]>>`
 --> bug.rs:3:9
  |
3 |         traverse(iter.skip_while(|&x| x != 3));
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
note: `traverse` defined here
 --> bug.rs:1:1
  |
1 | fn traverse(mut iter: impl Iterator<Item = u8>) {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

rustc bug.rs  15,28s user 0,03s system 99% cpu 15,317 total

Duration can vary between 10 and 15 seconds from my tests. Now, when applying the same adaptor but taking the iterator by reference, it completely hangs the compiler:

fn traverse(iter: &mut impl Iterator<Item = u8>) {
    if dbg!(iter.next()).is_some() {
        traverse(&mut iter.skip_while(|&x| x != 3));
    }
}

fn main() {
    traverse(&mut vec![1, 2, 3, 4].into_iter());
}

This does not reach the expected error, at least from my testing where rustc did not exit even after more than two hours. The previous example also hangs when using other closure-taking adaptors such as take_while, map and filter, but not with ones like skip, take nor step_by.

Obviously, a quick fix in a comparable situation is to use dyn trait objects in order to skip the iterator type monomorphization entirely, but I think the compiler shouldn't get stuck and still be able to report the instantiation recursion limit error successfully.

Meta

Tested on stable, beta and nightly:

rustc +stable --version --verbose:

rustc 1.48.0 (7eac88abb 2020-11-16)
binary: rustc
commit-hash: 7eac88abb2e57e752f3302f02be5f3ce3d7adfb4
commit-date: 2020-11-16
host: x86_64-unknown-linux-gnu
release: 1.48.0
LLVM version: 11.0

rustc +beta --version --verbose:

rustc 1.49.0-beta.3 (19ccb6c3c 2020-12-08)
binary: rustc
commit-hash: 19ccb6c3cc1af6b8d8350756bbe29b02fd6d6ffe
commit-date: 2020-12-08
host: x86_64-unknown-linux-gnu
release: 1.49.0-beta.3

rustc +nightly --version --verbose:

rustc 1.50.0-nightly (f0f68778f 2020-12-09)
binary: rustc
commit-hash: f0f68778f798d6d34649745b41770829b17ba5b8
commit-date: 2020-12-09
host: x86_64-unknown-linux-gnu
release: 1.50.0-nightly

Hope this helps.

Cheers,
Paul.

[gomain]

I ran into this and narrowed down to this code...

fn recursive<I: Iterator<Item = i32> + Clone>(is: I) {
    let _ = is.clone().collect::<Vec<_>>();
    recursive(is.map(|i| i))
}


fn main() {
    recursive(Vec::new().into_iter());
}

Interestingly, it was collection from a clone that pushed the compiler to hang. This code results in the recursion limit error.

fn recursive<I: Iterator<Item = i32> + Clone>(is: I) {
    let _ = is.clone()/* .collect::<Vec<_>>() */;
    recursive(is.map(|i| i))
}


fn main() {
    recursive(Vec::new().into_iter());
}

[PaulDance]

@gomain Interesting other approach 👍