How does Rust know when to stop iterating over a range with no upper limit?

user_13749561 0
Viewed 303

For the Nth Prime Rust exercise on exercism.io, I found that some solutions choose to filter() over a range with no upper limit.

Here's an example:

pub fn nth(n: u32) -> u32 {
    let mut primes = Vec::with_capacity((n as usize) + 1);

    (2..)
        .filter(|candidate| {
            if !primes.iter().any(|i| candidate % i == 0) {
                primes.push(*candidate);
                true
            } else {
                false
            }
        })
        .nth(n as usize)
        .unwrap()
}

I'm wondering when Rust stops iterating over the range in such a scenario. Does it perhaps iterate until the maximum value of the type, or could it figure out when it can stop iterating by checking code that follows the iterator (e.g. by checking when .unwrap() doesn't panic in the example)?

rust infinite-loop range iterator loops
2 Answers

Iterators in Rust are lazily evaluated, so they only "go to infinity" if you call the next method on them infinitely many times. Iterator methods like nth and take internally call next a finite amount of times, hence there's no issue.

However, if you're iterating over the Iterator in a non-terminating loop and the Iterator produces some primitive number type then you will eventually hit an overflow when you try to iterator past the max value representable by the type. Example program:

fn main() {
    for _ in (usize::MAX-1..) {
        println!("counting...");
    }
}

Run-time panic:

thread 'main' panicked at 'attempt to add with overflow', /rustc/7eac88abb2e57e752f3302f02be5f3ce3d7adfb4/library/core/src/ops/arith.rs:107:1

But that doesn't mean it isn't possible to iterate forever! Some methods like cycle allow you to create an infinitely repeating sequence which really will go on for forever until you manually terminate the program:

fn main() {
    let a = [1, 2, 3];
    
    let mut infinite_123 = a.iter().cycle();
    
    for _ in infinite_123 {
        println!("uh oh, forever loop");
    }
}
user_27669080

This is due to the use of Iterator::nth. This method will call the next method on the iterator exactly n times, then stop.

user_17044110
Related