RFC 2344: const-looping

lang (typesystem | machine | control-flow | const-eval)

Summary

Allow the use of loop, while and while let during constant evaluation. for loops are technically allowed, too, but can't be used in practice because each iteration calls iterator.next(), which is not a const fn and thus can't be called within constants. Future RFCs (like https://github.com/rust-lang/rfcs/pull/2237) might lift that restriction.

Motivation

Any iteration is expressible with recursion. Since we already allow recursion via const fn and termination of said recursion via if or match, all code enabled by const recursion is already legal now. Some algorithms are better expressed as imperative loops and a lot of Rust code uses loops instead of recursion. Allowing loops in constants will allow more functions to become const fn without requiring any changes.

Guide-level explanation

If you previously had to write functional code inside constants, you can now change it to imperative code. For example if you wrote a fibonacci like

const fn fib(n: u128) -> u128 {
    match n {
        0 => 1,
        1 => 1,
        n => fib(n - 1) + fib(n + 1)
    }
}

which takes exponential time to compute a fibonacci number, you could have changed it to the functional loop

const fn fib(n: u128) -> u128 {
    const fn helper(n: u128, a: u128, b: u128, i: u128) -> u128 {
        if i <= n {
            helper(n, b, a + b, i + 1)
        } else {
            b
        }
    }
    helper(n, 1, 1, 2)
}

but now you can just write it as an imperative loop, which also finishes in linear time.

const fn fib(n: u128) -> u128 {
    let mut a = 1;
    let mut b = 1;
    let mut i = 2;
    while i <= n {
        let tmp = a + b;
        a = b;
        b = tmp;
        i += 1;
    }
    b
}

Reference-level explanation

A loop in MIR is a cyclic graph of BasicBlocks. Evaluating such a loop is no different from evaluating a linear sequence of BasicBlocks, except that termination is not guaranteed. To ensure that the compiler never hangs indefinitely, we count the number of terminators processed and whenever we reach a fixed limit, we report a lint mentioning that we cannot guarantee that the evaluation will terminate and reset the counter to zero. This lint should recur in a non-annoying amount of time (e.g. at least 30 seconds between occurrences). This means that there's an internal deterministic counter (for the terminators) and a timestamp of the last (if any) loop warning emission. Both the counter needs to reach its limit and 30 seconds have to have passed since the last warning emission in order for a new warning to be emitted.

Drawbacks

Rationale and alternatives

Unresolved questions