For loop in unbounded range is not assumed to never terminate

In code like this

fn some_complicated_check(x:i32)->bool{
    return x==10;
}

fn f()->i32{
    for x in 2i32..{
        if some_complicated_check(x){
            return x;
        }
    }
    return 0i32; // this line is not reachable
}

While the last line is not necessary, it's required to avoid the compiler failing with mismatched types: expected i32, found ().

Isn't it a better idea if the compiler detect if the loop is infinite?

(It's possible to do that manually with unreachable!() or use a while loop, and I know that there are more complex cases, but I think this case is common enough)

In debug mode, the integer overflow will panic, but that still leaves the following statement unreachable.

Generally speaking, rustc does not do interprocedural analysis for this kind of thing, so it doesn't know that the loop is unbounded. RangeFrom is not a language item, just a pure library construct.

5 Likes

The compiler doesn't even see while true {} as an infinite loop. Rust has exactly one looping construct that is known to the compiler to never terminate on its own, and that is loop. For example, this compiles:

fn f() -> i32{
    let mut x = 2;
    loop {
        if some_complicated_check(x){
            return x;
        }
        x += 1;
    }
}
6 Likes

As a Rust neophyte I question the very idea that the loop is infinite.

I read "for x in 2i32.." as meaning "for signed integer values of x from 2 to whatever the maximum possible positive value of a 32 bit integer is"

Ergo the loop will terminate even if "some_complicated_check(x)" never returns true. There are only a finite number of positive 32 bit integers.

Ergo your last line is reachable and you had better cater for it.

Also, as a Rust neophyte, I see that your function f() has two possible outcomes:

a) It finds an x and returns it from withing the loop.
b) It does not find an x and returns a zero.

That is to say f() returns the same thing, an i32, no matter if it succeeds or not. The caller has to know about that special not found value of zero. This is the same mess as we have in C with it's valid return values being mixed up with special failure/error return values.

Looks like your function f() should return an Error or perhaps an Option so as to ensure the caller is forced to check the return value properly.

31 posts were split to a new topic: Panic vs Result/Option

Isn't it a better idea if the compiler could magically infer what you meant and just do the right thing every time?

Detecting if a loop is finite or infinite is the textbook example of something that can't be done in general.

5 Likes

I said in original post that

I know that there are more complex cases, but I think this case is common enough

1 Like

Yes, for now unreachable is the best way. The call is completely eliminated by the optimizer.

I think that there should be some way for the iterator to communicate to the caller that it will never return None. Just like a function can return Result<T, !> to signify that it cannot error, the next function could return something like Option<T, !> or T to signify that it cannot be None. (of course this is currently not valid Rust)

1 Like

I guess the best way to do that in stable is to use an enum without variants.

// Cannot be instantiated
enum Never {}

let a: Result<usize, Never> = …;
// This will never be undefined behavior (pun intended)
let a: usize = a.unwrap_or_else(|| unsafe { unreachable_unchecked() });

EDIT:
You could also make a trait for this case.

trait AlwaysOk<T> {
    fn into_ok(self) -> T
}

impl<T> AlwaysOk<T> for Result<T, Never> {
    fn into_ok(self) -> T {
        self.unwrap_or_else(|| unsafe { unreachable_unchecked() })
    }
}

EDIT2:
Not sure if this works, but according to 1.41 patch notes, this should also be possible, now:

impl<T> From<Result<T, Never>> for T {
    fn from(from: Result<T, Never>) -> Self {
        from.unwrap_or_else(|| unsafe { unreachable_unchecked() })
    }
}

Moderation note: Folks, please try to stay on topic. I split off a huge tangential discussion about panicking vs Result/Option to a different thread: https://users.rust-lang.org/t/panic-vs-result-option

3 Likes

There's no way for an iterator to communicate through the type system that it's infinite, which would be required for a non-fragile implementation of this. (Rust intentionally doesn't look into the bodies of other functions -- that's why you need to specify the full signature on functions.)

Iterator::next returns an Option<Self::Item>, which can always be None. If instead it returned Result<Self::Item, Self::Error>, then one could use Error=! to note that it always returns Ok (never Err) and thus it's infinite. But that's not how the trait works right now.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.