Using never_type and unbounded for loops (RangeFrom)

[udoprog]

I noticed that never_type (!) when used with an unbounded loop (RangeFrom) doesn’t realize that the end of the function will never be reached:

#![feature(never_type)]

fn forever() -> ! {
    for index in 0u64.. {
    }

    // TODO: should not be needed?
    unreachable!()
}

fn forever_cool() -> ! {
    let mut index = 0u64;

    loop {
        index += 1;
    }
}

fn main() {
}

I’m guessing this is a limitation in what kind of expression the for-loop evaluates to (() in this case). It seems like loop is a bit more sophisticated since the compiler notices when a break is present.

Is it desirable to make this work with the never type? If so, Is there already a tracking issue for this? I couldn’t find one.

[hanna-kruppe]

RangeFrom is not unbounded, there’s an arithmetic overflows when you reach the limit of the underlying integer type (and all primitive integer types have such a limit). That overflow triggers a panic when overflow checks are enabled. Admittedly, that panic is also consistent with saying the loop is divergent, but it complicates the analysis somewhat.

More fundamentally, iterators are library code, even though the traits involved are known to the compiler and some compiler-known types are iterators. Therefore, it seems inappropriate for the compiler to reason even when possible (the only example I can think of is iter::repeat, which is not known to the compiler). Especially when the impl that makes RangeFrom<u64> an iterator is the same (generic) impl that makes a hypothetical RangeFrom<LibraryBigInt> an iterator.

On a more technical level, since for loops are desugared before control flow analysis happens, it seems quite difficult to implement this analysis (at least, in a clean and composable way). For example, it would be very unfortunate to not desugar for loops early (complicates the later parts of the compiler) or to pattern match the desugaring of for loops.

[canndrew]

I would like to marry for-loops with generators in such a way that this would be possible. If you consider a Generator trait with 3 associated types: Yield, Resume and Return, then an Iterator<item=T> is just a Generator<Yield=T, Resume=(), Return=()>. We could make Generator the for-loop lang item instead of Iterator and extend for-loop syntax to allow it to handle these extra type parameters.

For Resume, we’d just allow continue to take an argument and have “continue” with no argument just be sugar for “continue ()”. A continue statement at the end of a for-loop block would be mandatory if the generator needs to resume with anything other than (). To demonstrate:

// These three are equivalent
for x in my_iter {
}

for x in my_iter {
    continue;
}

for x in my_iter {
    continue ();
}

// But we can also have iterators/generators where next/resume takes an argument.
// Here, continue is necessary.
for x in my_generator {
    continue 123;
}

For Return, make the return value of the entire for expression be the return value of the generator. All iterators currently return () when they complete, but we could make RangeFrom a generator which returns !. So, in general, we’d allow code that does stuff like this:

let my_generator: impl Generator<Yield=T, Resume=(), Return=String> = ...;
let y: String = for x in my_generator {
    ...
}

Also, for the hell of it, allow for-loops to end in a then clause which can map the generator’s return value.

let my_generator: impl Generator<Yield=u32, Resume=(), Return=String> = ...;
let y: u32 = for x in my_generator {
    if x < 123 {
        break x;
    }
} then z {
    u32::parse(z).unwrap()
}

// `z` can be omitted if it has type `()`
let my_generator: impl Generator<Yield=u32, Resume=(), Return=()> = ...;
let y: u32 = for x in my_generator {
    if x < 123 {
        break x;
    }
} then {
    456
}

As a final touch, treat the argument to for as being mutably borrowed inside the main body of the for-loop, but as having been moved after the for-loop or within the then clause. Combined with non-lexical-lifetimes this would allow you to break or return with the generator before it’s finished being consumed. eg. this would be legal:

fn take_three<G: Generator<Yield=u32, Resume=(), Return=!>>(g: G) -> (Vec<u32>, Option<G>) {
    let mut ret = Vec::new();
    for x in g {
        ret.push(x);
        if ret.len() == 3 {
            return (ret, Some(g));
        }
    }
    (ret, None)
}

This would provide a way to use generators without any of those nasty runtime assertions which panic if we call .resume() on a generator which has already returned.

Edit: I actually have an RFC baking for this but it’s part of a much much larger effects-system RFC which I don’t know if I’ll ever get round to finishing.

[scottmcm]

@udoprog

I’m guessing this is a limitation in what kind of expression the for-loop evaluates to (() in this case). It seems like loop is a bit more sophisticated since the compiler notices when a break is present.

This is a limitation of the iterator interface using Option<Item>. There's no way for that to communicate in the type system that it never returns None.

In an alternate universe where it returned Result<Self::Item, Self::EmptyReason>, then the RangeFrom iterator could use EmptyReason = !;, and the compiler would be able to know it's diverging.

[udoprog]

@scottmcm

@udoprog

I’m guessing this is a limitation in what kind of expression the for-loop evaluates to (() in this case). It seems like loop is a bit more sophisticated since the compiler notices when a break is present.

This is a limitation of the iterator interface using Option<Item>. There's no way for that to communicate in the type system that it never returns None.

In an alternate universe where it returned Result<Self::Item, Self::EmptyReason>, then the RangeFrom iterator could use EmptyReason = !;, and the compiler would be able to know it's diverging.

Ah. That makes sense. Thanks for the succinct explanation!

Pushing loops towards using generators as proposed by @canndrew seems like a good approach to address this.