Apparent infinite loop when passing infinitely recursive type using Iterator::filter

[shepmaster]

I tried this code:

fn recur(lines: impl Iterator) {
    recur(lines.filter(|_| true))
}

fn main() {
    recur([0u8].into_iter());
}

I expected the compiler would provide an error message, akin to reached the recursion limit while instantiating.

Instead, the compiler appears to hang indefinitely — I killed the process after a while.

Meta

% rustc +stable --version --verbose
rustc 1.57.0 (f1edd0429 2021-11-29)
binary: rustc
commit-hash: f1edd0429582dd29cccacaf50fd134b05593bd9c
commit-date: 2021-11-29
host: aarch64-apple-darwin
release: 1.57.0
LLVM version: 13.0.0

% rustc +nightly --version --verbose
rustc 1.59.0-nightly (acbe4443c 2021-12-02)
binary: rustc
commit-hash: acbe4443cc4c9695c0b74a7b64b60333c990a400
commit-date: 2021-12-02
host: aarch64-apple-darwin
release: 1.59.0-nightly
LLVM version: 13.0.0

[hkratz]

rustc -Zno-codegen finishes without error message.

[tocklime]

I think I came across this problem too - Constructing an infinite type for a recursive iterator function doesn't ever finish or error out. My repro: https://github.com/tocklime/rustc_iterwrapper_hang/blob/main/src/main.rs

[honnza]

Related issue: sometimes the instantiation does stop - by reaching a type that requires 128 steps to verify its bounds - and then blames the leaf node for it!

error[E0275]: overflow evaluating the requirement `&[u8]: Sized`
...
required because of the requirements on the <actual culprit>

[01mf02]

A slight variation on (probably) the same bug:

fn foo(iter: &mut impl Iterator<Item = ()>) {
    foo(&mut std::iter::once(()).chain(iter))
}

fn main() {
    foo(&mut std::iter::repeat(()));
}

Here, cargo run and cargo run --release (Rust 1.57) loop infinitely without error, but cargo check terminates.
Removing &mut everywhere from this example makes cargo run report an error, but still loop infinitely afterwards.

The (last) error is:

error: overflow while checking whether std::iter::Chain<std::iter::Once<()>, std::iter::Chain<std::iter::Once<()>, [...], std::iter::Chain<std::iter::Once<()>, std::iter::Chain<std::iter::Once<()>, std::iter::Repeat<()>> [...] >> requires drop

[dceddia]

I ran into what I think is a similar problem, although in my case the hang happens even though the code doesn't call the iterator. Repro here: https://github.com/dceddia/rustc-iterator-hang/blob/main/src/main.rs

It hangs on both cargo build and cargo check, and adding the -Zno-codegen flag does not seem to have any effect.

This is my first foray into writing an iterator extension so I'm probably doing something terribly wrong, but still, I figure it's not supposed to hang forever 😅

edit - I found that the compile will finish normally (with errors, because my code is broken) if I comment out the code that implements the iterator (this section)

edit 2 - I narrowed it down to this one difference in how I was specifying one of the trait bounds, using &Option<Self::Item> vs. &Option<T>.

impl<T, Cond, F> Iterator for OnChange<T, Cond, F>
where
    Cond: Fn(&Option<Self::Item>) -> bool,   // (a) hangs the compiler
    Cond: Fn(&Option<T>) -> bool,   // (b) does not hang
    F: Fn((Option<T>, Option<T>)) -> Option<T>,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        todo!()
    }
}