Repository: rust
Issue: Recursive instantiation for Iterator trait with closure-taking adaptors hangs rustc
Labels: T-compiler,A-impl-trait,C-bug,I-hang,I-monomorphization

<!--
Thank you for finding an Internal Compiler Error! 🧊  If possible, try to provide
a minimal verifiable example. You can read "Rust Bug Minimization Patterns" for
how to create smaller examples.

http://blog.pnkfx.org/blog/2019/11/18/rust-bug-minimization-patterns/
-->

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:

```rust
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:

```rust
➜ ./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:

```rust
➜ 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:

```rust
➜ 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:

```rust
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
<!--
If you're using the stable version of the compiler, you should also check if the
bug also exists in the beta or nightly versions.
-->

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.