Auto merge of #51702 - ecstatic-morse:infinite-loop-detection, r=oli-obk

Infinite loop detection for const evaluation

Resolves #50637.

An `EvalContext` stores the transient state (stack, heap, etc.) of the MIRI virtual machine while it executing code. As long as MIRI only executes pure functions, we can detect if a program is in a state where it will never terminate by periodically taking a "snapshot" of this transient state and comparing it to previous ones. If any two states are exactly equal, the machine must be in an infinite loop.

Instead of fully cloning a snapshot every time the detector is run, we store a snapshot's hash. Only when a hash collision occurs do we fully clone the interpreter state. Future snapshots which cause a collision will be compared against this clone, causing the interpreter to abort if they are equal.

At the moment, snapshots are not taken until MIRI has progressed a certain amount. After this threshold, snapshots are taken every `DETECTOR_SNAPSHOT_PERIOD` steps. This means that an infinite loop with period `P` will be detected after a maximum of `2 * P * DETECTOR_SNAPSHOT_PERIOD` interpreter steps. The factor of 2 arises because we only clone a snapshot after it causes a hash collision.

2 files changed, 66 insertions, 0 deletions

diff --git a/src/test/ui/const-eval/infinite_loop.rs b/src/test/ui/const-eval/infinite_loop.rs
new file mode 100644
index 00000000000..a1f8ab7f878
--- /dev/null
+++ b/src/test/ui/const-eval/infinite_loop.rs
@@ -0,0 +1,25 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(const_let)]
+
+fn main() {
+    // Tests the Collatz conjecture with an incorrect base case (0 instead of 1).
+    // The value of `n` will loop indefinitely (4 - 2 - 1 - 4).
+    let _ = [(); {
+        //~^ WARNING Constant evaluating a complex constant, this might take some time
+        //~| ERROR could not evaluate repeat length
+        let mut n = 113383; // #20 in https://oeis.org/A006884
+        while n != 0 { //~ ERROR constant contains unimplemented expression type
+            n = if n % 2 == 0 { n/2 } else { 3*n + 1 };
+        }
+        n
+    }];
+}
diff --git a/src/test/ui/const-eval/infinite_loop.stderr b/src/test/ui/const-eval/infinite_loop.stderr
new file mode 100644
index 00000000000..f69aae29203
--- /dev/null
+++ b/src/test/ui/const-eval/infinite_loop.stderr
@@ -0,0 +1,41 @@
+error[E0019]: constant contains unimplemented expression type
+  --> $DIR/infinite_loop.rs:20:9
+   |
+LL | /         while n != 0 { //~ ERROR constant contains unimplemented expression type
+LL | |             n = if n % 2 == 0 { n/2 } else { 3*n + 1 };
+LL | |         }
+   | |_________^
+
+warning: Constant evaluating a complex constant, this might take some time
+  --> $DIR/infinite_loop.rs:16:18
+   |
+LL |       let _ = [(); {
+   |  __________________^
+LL | |         //~^ WARNING Constant evaluating a complex constant, this might take some time
+LL | |         //~| ERROR could not evaluate repeat length
+LL | |         let mut n = 113383; // #20 in https://oeis.org/A006884
+...  |
+LL | |         n
+LL | |     }];
+   | |_____^
+
+error[E0080]: could not evaluate repeat length
+  --> $DIR/infinite_loop.rs:16:18
+   |
+LL |       let _ = [(); {
+   |  __________________^
+LL | |         //~^ WARNING Constant evaluating a complex constant, this might take some time
+LL | |         //~| ERROR could not evaluate repeat length
+LL | |         let mut n = 113383; // #20 in https://oeis.org/A006884
+LL | |         while n != 0 { //~ ERROR constant contains unimplemented expression type
+LL | |             n = if n % 2 == 0 { n/2 } else { 3*n + 1 };
+   | |                    ---------- duplicate interpreter state observed here, const evaluation will never terminate
+LL | |         }
+LL | |         n
+LL | |     }];
+   | |_____^
+
+error: aborting due to 2 previous errors
+
+Some errors occurred: E0019, E0080.
+For more information about an error, try `rustc --explain E0019`.