Merge pull request #2344 from oli-obk/const_looping

Allow `loop` in constant evaluation
rust-lang · Jul 2, 2018 · c794c75 · c794c75
2 parents 5a44ed0 e4ac9b0
commit c794c75
Showing 1 changed file with 107 additions and 0 deletions.
diff --git a/text/2344-const-looping.md b/text/2344-const-looping.md
@@ -0,0  1,107 @@
 - Feature Name: `const_looping`
 - Start Date: 2018-02-18
 - RFC PR: [rust-lang/rfcs#2344](https://github.com/rust-lang/rfcs/pull/2344)
 - Rust Issue: [rust-lang/rust#52000](https://github.com/rust-lang/rust/issues/52000)
 
 # Summary
 [summary]: #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
 [motivation]: #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
 [guide-level-explanation]: #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
 
 ```rust
 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
 
 ```rust
 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.
 
 ```rust
 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
 [reference-level-explanation]: #reference-level-explanation
 
 A loop in MIR is a cyclic graph of `BasicBlock`s. Evaluating such a loop is no
 different from evaluating a linear sequence of `BasicBlock`s, 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
 [drawbacks]: #drawbacks
 
 * Infinite loops will cause the compiler to never finish if the lint is not denied
 
 # Rationale and alternatives
 [alternatives]: #alternatives
 
 - Do nothing, users can keep using recursion
 
 # Unresolved questions
 [unresolved]: #unresolved-questions
 
 * Should we add a true recursion check that hashes the interpreter state and
   detects if it has reached the same state again?
     * This will slow down const evaluation enormously and for complex iterations
       is essentially useless because it'll take forever (e.g. counting from 0 to
       `u64::max_value()`)