rollup merge of #23536: pnkfelix/arith-oflo-shifts

overflow-checking for rhs of shift operators

Subtask of #22020 ([RFC 560](https://github.com/rust-lang/rfcs/blob/master/text/0560-integer-overflow.md))

10 files changed, 283 insertions, 1 deletions

diff --git a/src/test/run-fail/overflowing-lsh-1.rs b/src/test/run-fail/overflowing-lsh-1.rs
new file mode 100644
index 00000000000..54159153382
--- /dev/null
+++ b/src/test/run-fail/overflowing-lsh-1.rs
@@ -0,0 +1,19 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    let _x = 1_i32 << id(32);
+}
diff --git a/src/test/run-fail/overflowing-lsh-2.rs b/src/test/run-fail/overflowing-lsh-2.rs
new file mode 100644
index 00000000000..fd3e801457c
--- /dev/null
+++ b/src/test/run-fail/overflowing-lsh-2.rs
@@ -0,0 +1,19 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    let _x = 1 << id(-1);
+}
diff --git a/src/test/run-fail/overflowing-lsh-3.rs b/src/test/run-fail/overflowing-lsh-3.rs
new file mode 100644
index 00000000000..58914bab3fb
--- /dev/null
+++ b/src/test/run-fail/overflowing-lsh-3.rs
@@ -0,0 +1,19 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    let _x = 1_u64 << id(64);
+}
diff --git a/src/test/run-fail/overflowing-lsh-4.rs b/src/test/run-fail/overflowing-lsh-4.rs
new file mode 100644
index 00000000000..ed25876cec4
--- /dev/null
+++ b/src/test/run-fail/overflowing-lsh-4.rs
@@ -0,0 +1,34 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// This function is checking that our automatic truncation does not
+// sidestep the overflow checking.
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    // this signals overflow when checking is on
+    let x = 1_i8 << id(17);
+
+    // ... but when checking is off, the fallback will truncate the
+    // input to its lower three bits (= 1). Note that this is *not*
+    // the behavior of the x86 processor for 8- and 16-bit types,
+    // but it is necessary to avoid undefined behavior from LLVM.
+    //
+    // We check that here, by ensuring the result has only been
+    // shifted by one place; if overflow checking is turned off, then
+    // this assertion will pass (and the compiletest driver will
+    // report that the test did not produce the error expected above).
+    assert_eq!(x, 2_i8);
+}
diff --git a/src/test/run-fail/overflowing-rsh-1.rs b/src/test/run-fail/overflowing-rsh-1.rs
new file mode 100644
index 00000000000..c36a16f18f8
--- /dev/null
+++ b/src/test/run-fail/overflowing-rsh-1.rs
@@ -0,0 +1,19 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    let _x = -1_i32 >> id(32);
+}
diff --git a/src/test/run-fail/overflowing-rsh-2.rs b/src/test/run-fail/overflowing-rsh-2.rs
new file mode 100644
index 00000000000..f619ebe9fb4
--- /dev/null
+++ b/src/test/run-fail/overflowing-rsh-2.rs
@@ -0,0 +1,19 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    let _x = -1_i32 >> id(-1);
+}
diff --git a/src/test/run-fail/overflowing-rsh-3.rs b/src/test/run-fail/overflowing-rsh-3.rs
new file mode 100644
index 00000000000..c261e195fd7
--- /dev/null
+++ b/src/test/run-fail/overflowing-rsh-3.rs
@@ -0,0 +1,19 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    let _x = -1_i64 >> id(64);
+}
diff --git a/src/test/run-fail/overflowing-rsh-4.rs b/src/test/run-fail/overflowing-rsh-4.rs
new file mode 100644
index 00000000000..6e79a13d4e1
--- /dev/null
+++ b/src/test/run-fail/overflowing-rsh-4.rs
@@ -0,0 +1,34 @@
+// Copyright 2015 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.
+
+// error-pattern:thread '<main>' panicked at 'shift operation overflowed'
+// compile-flags: -C debug-assertions
+
+// This function is checking that our (type-based) automatic
+// truncation does not sidestep the overflow checking.
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    // this signals overflow when checking is on
+    let x = 2_i8 >> id(17);
+
+    // ... but when checking is off, the fallback will truncate the
+    // input to its lower three bits (= 1). Note that this is *not*
+    // the behavior of the x86 processor for 8- and 16-bit types,
+    // but it is necessary to avoid undefined behavior from LLVM.
+    //
+    // We check that here, by ensuring the result is not zero; if
+    // overflow checking is turned off, then this assertion will pass
+    // (and the compiletest driver will report that the test did not
+    // produce the error expected above).
+    assert_eq!(x, 1_i8);
+}
diff --git a/src/test/run-pass/over-constrained-vregs.rs b/src/test/run-pass/over-constrained-vregs.rs
index 1118638fe07..c2b42ac1c81 100644
--- a/src/test/run-pass/over-constrained-vregs.rs
+++ b/src/test/run-pass/over-constrained-vregs.rs
@@ -11,7 +11,7 @@
 // Regression test for issue #152.
 pub fn main() {
     let mut b: uint = 1_usize;
-    while b <= 32_usize {
+    while b < std::mem::size_of::<usize>() {
         0_usize << b;
         b <<= 1_usize;
         println!("{}", b);
diff --git a/src/test/run-pass/shift-near-oflo.rs b/src/test/run-pass/shift-near-oflo.rs
new file mode 100644
index 00000000000..4ff058f3366
--- /dev/null
+++ b/src/test/run-pass/shift-near-oflo.rs
@@ -0,0 +1,100 @@
+// Copyright 2015 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.
+
+// compile-flags: -C debug-assertions
+
+// Check that we do *not* overflow on a number of edge cases.
+// (compare with test/run-fail/overflowing-{lsh,rsh}*.rs)
+
+// (Work around constant-evaluation)
+fn id<T>(x: T) -> T { x }
+
+fn main() {
+    test_left_shift();
+    test_right_shift();
+}
+
+fn test_left_shift() {
+    // negative rhs can panic, but values in [0,N-1] are okay for iN
+
+    macro_rules! tests {
+        ($iN:ty, $uN:ty, $max_rhs:expr, $expect_i:expr, $expect_u:expr) => { {
+            let x = (1 as $iN) << id(0);
+            assert_eq!(x, 1);
+            let x = (1 as $uN) << id(0);
+            assert_eq!(x, 1);
+            let x = (1 as $iN) << id($max_rhs);
+            assert_eq!(x, $expect_i);
+            let x = (1 as $uN) << id($max_rhs);
+            assert_eq!(x, $expect_u);
+            // high-order bits on LHS are silently discarded without panic.
+            let x = (3 as $iN) << id($max_rhs);
+            assert_eq!(x, $expect_i);
+            let x = (3 as $uN) << id($max_rhs);
+            assert_eq!(x, $expect_u);
+        } }
+    }
+
+    let x = 1_i8 << id(0);
+    assert_eq!(x, 1);
+    let x = 1_u8 << id(0);
+    assert_eq!(x, 1);
+    let x = 1_i8 << id(7);
+    assert_eq!(x, std::i8::MIN);
+    let x = 1_u8 << id(7);
+    assert_eq!(x, 0x80);
+    // high-order bits on LHS are silently discarded without panic.
+    let x = 3_i8 << id(7);
+    assert_eq!(x, std::i8::MIN);
+    let x = 3_u8 << id(7);
+    assert_eq!(x, 0x80);
+
+    // above is (approximately) expanded from:
+    tests!(i8, u8, 7, std::i8::MIN, 0x80_u8);
+
+    tests!(i16, u16, 15, std::i16::MIN, 0x8000_u16);
+    tests!(i32, u32, 31, std::i32::MIN, 0x8000_0000_u32);
+    tests!(i64, u64, 63, std::i64::MIN, 0x8000_0000_0000_0000_u64);
+}
+
+fn test_right_shift() {
+    // negative rhs can panic, but values in [0,N-1] are okay for iN
+
+    macro_rules! tests {
+        ($iN:ty, $uN:ty, $max_rhs:expr,
+         $signbit_i:expr, $highbit_i:expr, $highbit_u:expr) =>
+        { {
+            let x = (1 as $iN) >> id(0);
+            assert_eq!(x, 1);
+            let x = (1 as $uN) >> id(0);
+            assert_eq!(x, 1);
+            let x = ($highbit_i) >> id($max_rhs-1);
+            assert_eq!(x, 1);
+            let x = ($highbit_u) >> id($max_rhs);
+            assert_eq!(x, 1);
+            // sign-bit is carried by arithmetic right shift
+            let x = ($signbit_i) >> id($max_rhs);
+            assert_eq!(x, -1);
+            // low-order bits on LHS are silently discarded without panic.
+            let x = ($highbit_i + 1) >> id($max_rhs-1);
+            assert_eq!(x, 1);
+            let x = ($highbit_u + 1) >> id($max_rhs);
+            assert_eq!(x, 1);
+            let x = ($signbit_i + 1) >> id($max_rhs);
+            assert_eq!(x, -1);
+        } }
+    }
+
+    tests!(i8, u8, 7, std::i8::MIN, 0x40_i8, 0x80_u8);
+    tests!(i16, u16, 15, std::i16::MIN, 0x4000_u16, 0x8000_u16);
+    tests!(i32, u32, 31, std::i32::MIN, 0x4000_0000_u32, 0x8000_0000_u32);
+    tests!(i64, u64, 63, std::i64::MIN,
+           0x4000_0000_0000_0000_u64, 0x8000_0000_0000_0000_u64);
+}