Update Cargo submodule

Required moving all fulldeps tests depending on `rand` to different locations as
now there's multiple `rand` crates that can't be implicitly linked against.

4 files changed, 232 insertions, 1 deletions

diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs
index a9c5683e0ef..d08d6b3215d 100644
--- a/src/libcore/tests/lib.rs
+++ b/src/libcore/tests/lib.rs
@@ -50,6 +50,7 @@
 
 extern crate core;
 extern crate test;
+extern crate rand;
 
 mod any;
 mod array;
diff --git a/src/libcore/tests/num/flt2dec/mod.rs b/src/libcore/tests/num/flt2dec/mod.rs
index ef0178815f9..04567e25e25 100644
--- a/src/libcore/tests/num/flt2dec/mod.rs
+++ b/src/libcore/tests/num/flt2dec/mod.rs
@@ -23,6 +23,7 @@ mod strategy {
     mod dragon;
     mod grisu;
 }
+mod random;
 
 pub fn decode_finite<T: DecodableFloat>(v: T) -> Decoded {
     match decode(v).1 {
diff --git a/src/libcore/tests/num/flt2dec/random.rs b/src/libcore/tests/num/flt2dec/random.rs
new file mode 100644
index 00000000000..315ac4d7d99
--- /dev/null
+++ b/src/libcore/tests/num/flt2dec/random.rs
@@ -0,0 +1,160 @@
+// Copyright 2017 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.
+
+#![cfg(not(target_arch = "wasm32"))]
+
+use std::i16;
+use std::mem;
+use std::str;
+
+use core::num::flt2dec::MAX_SIG_DIGITS;
+use core::num::flt2dec::strategy::grisu::format_exact_opt;
+use core::num::flt2dec::strategy::grisu::format_shortest_opt;
+use core::num::flt2dec::{decode, DecodableFloat, FullDecoded, Decoded};
+
+use rand::{self, Rand, XorShiftRng};
+use rand::distributions::{IndependentSample, Range};
+
+pub fn decode_finite<T: DecodableFloat>(v: T) -> Decoded {
+    match decode(v).1 {
+        FullDecoded::Finite(decoded) => decoded,
+        full_decoded => panic!("expected finite, got {:?} instead", full_decoded)
+    }
+}
+
+
+fn iterate<F, G, V>(func: &str, k: usize, n: usize, mut f: F, mut g: G, mut v: V) -> (usize, usize)
+        where F: FnMut(&Decoded, &mut [u8]) -> Option<(usize, i16)>,
+              G: FnMut(&Decoded, &mut [u8]) -> (usize, i16),
+              V: FnMut(usize) -> Decoded {
+    assert!(k <= 1024);
+
+    let mut npassed = 0; // f(x) = Some(g(x))
+    let mut nignored = 0; // f(x) = None
+
+    for i in 0..n {
+        if (i & 0xfffff) == 0 {
+            println!("in progress, {:x}/{:x} (ignored={} passed={} failed={})",
+                     i, n, nignored, npassed, i - nignored - npassed);
+        }
+
+        let decoded = v(i);
+        let mut buf1 = [0; 1024];
+        if let Some((len1, e1)) = f(&decoded, &mut buf1[..k]) {
+            let mut buf2 = [0; 1024];
+            let (len2, e2) = g(&decoded, &mut buf2[..k]);
+            if e1 == e2 && &buf1[..len1] == &buf2[..len2] {
+                npassed += 1;
+            } else {
+                println!("equivalence test failed, {:x}/{:x}: {:?} f(i)={}e{} g(i)={}e{}",
+                         i, n, decoded, str::from_utf8(&buf1[..len1]).unwrap(), e1,
+                                        str::from_utf8(&buf2[..len2]).unwrap(), e2);
+            }
+        } else {
+            nignored += 1;
+        }
+    }
+    println!("{}({}): done, ignored={} passed={} failed={}",
+             func, k, nignored, npassed, n - nignored - npassed);
+    assert!(nignored + npassed == n,
+            "{}({}): {} out of {} values returns an incorrect value!",
+            func, k, n - nignored - npassed, n);
+    (npassed, nignored)
+}
+
+pub fn f32_random_equivalence_test<F, G>(f: F, g: G, k: usize, n: usize)
+        where F: FnMut(&Decoded, &mut [u8]) -> Option<(usize, i16)>,
+              G: FnMut(&Decoded, &mut [u8]) -> (usize, i16) {
+    let mut rng: XorShiftRng = Rand::rand(&mut rand::thread_rng());
+    let f32_range = Range::new(0x0000_0001u32, 0x7f80_0000);
+    iterate("f32_random_equivalence_test", k, n, f, g, |_| {
+        let i: u32 = f32_range.ind_sample(&mut rng);
+        let x: f32 = unsafe {mem::transmute(i)};
+        decode_finite(x)
+    });
+}
+
+pub fn f64_random_equivalence_test<F, G>(f: F, g: G, k: usize, n: usize)
+        where F: FnMut(&Decoded, &mut [u8]) -> Option<(usize, i16)>,
+              G: FnMut(&Decoded, &mut [u8]) -> (usize, i16) {
+    let mut rng: XorShiftRng = Rand::rand(&mut rand::thread_rng());
+    let f64_range = Range::new(0x0000_0000_0000_0001u64, 0x7ff0_0000_0000_0000);
+    iterate("f64_random_equivalence_test", k, n, f, g, |_| {
+        let i: u64 = f64_range.ind_sample(&mut rng);
+        let x: f64 = unsafe {mem::transmute(i)};
+        decode_finite(x)
+    });
+}
+
+pub fn f32_exhaustive_equivalence_test<F, G>(f: F, g: G, k: usize)
+        where F: FnMut(&Decoded, &mut [u8]) -> Option<(usize, i16)>,
+              G: FnMut(&Decoded, &mut [u8]) -> (usize, i16) {
+    // we have only 2^23 * (2^8 - 1) - 1 = 2,139,095,039 positive finite f32 values,
+    // so why not simply testing all of them?
+    //
+    // this is of course very stressful (and thus should be behind an `#[ignore]` attribute),
+    // but with `-C opt-level=3 -C lto` this only takes about an hour or so.
+
+    // iterate from 0x0000_0001 to 0x7f7f_ffff, i.e. all finite ranges
+    let (npassed, nignored) = iterate("f32_exhaustive_equivalence_test",
+                                      k, 0x7f7f_ffff, f, g, |i: usize| {
+        let x: f32 = unsafe {mem::transmute(i as u32 + 1)};
+        decode_finite(x)
+    });
+    assert_eq!((npassed, nignored), (2121451881, 17643158));
+}
+
+#[test]
+fn shortest_random_equivalence_test() {
+    use core::num::flt2dec::strategy::dragon::format_shortest as fallback;
+    f64_random_equivalence_test(format_shortest_opt, fallback, MAX_SIG_DIGITS, 10_000);
+    f32_random_equivalence_test(format_shortest_opt, fallback, MAX_SIG_DIGITS, 10_000);
+}
+
+#[test] #[ignore] // it is too expensive
+fn shortest_f32_exhaustive_equivalence_test() {
+    // it is hard to directly test the optimality of the output, but we can at least test if
+    // two different algorithms agree to each other.
+    //
+    // this reports the progress and the number of f32 values returned `None`.
+    // with `--nocapture` (and plenty of time and appropriate rustc flags), this should print:
+    // `done, ignored=17643158 passed=2121451881 failed=0`.
+
+    use core::num::flt2dec::strategy::dragon::format_shortest as fallback;
+    f32_exhaustive_equivalence_test(format_shortest_opt, fallback, MAX_SIG_DIGITS);
+}
+
+#[test] #[ignore] // it is too expensive
+fn shortest_f64_hard_random_equivalence_test() {
+    // this again probably has to use appropriate rustc flags.
+
+    use core::num::flt2dec::strategy::dragon::format_shortest as fallback;
+    f64_random_equivalence_test(format_shortest_opt, fallback,
+                                         MAX_SIG_DIGITS, 100_000_000);
+}
+
+#[test]
+fn exact_f32_random_equivalence_test() {
+    use core::num::flt2dec::strategy::dragon::format_exact as fallback;
+    for k in 1..21 {
+        f32_random_equivalence_test(|d, buf| format_exact_opt(d, buf, i16::MIN),
+                                             |d, buf| fallback(d, buf, i16::MIN), k, 1_000);
+    }
+}
+
+#[test]
+fn exact_f64_random_equivalence_test() {
+    use core::num::flt2dec::strategy::dragon::format_exact as fallback;
+    for k in 1..21 {
+        f64_random_equivalence_test(|d, buf| format_exact_opt(d, buf, i16::MIN),
+                                             |d, buf| fallback(d, buf, i16::MIN), k, 1_000);
+    }
+}
+
diff --git a/src/libcore/tests/slice.rs b/src/libcore/tests/slice.rs
index 13740b95802..53fdfa06827 100644
--- a/src/libcore/tests/slice.rs
+++ b/src/libcore/tests/slice.rs
@@ -10,7 +10,6 @@
 
 use core::result::Result::{Ok, Err};
 
-
 #[test]
 fn test_position() {
     let b = [1, 2, 3, 5, 5];
@@ -481,3 +480,73 @@ fn test_rotate_right() {
         assert_eq!(a[(i + 42) % N], i);
     }
 }
+
+#[test]
+#[cfg(not(target_arch = "wasm32"))]
+fn sort_unstable() {
+    use core::cmp::Ordering::{Equal, Greater, Less};
+    use core::slice::heapsort;
+    use rand::{Rng, XorShiftRng};
+
+    let mut v = [0; 600];
+    let mut tmp = [0; 600];
+    let mut rng = XorShiftRng::new_unseeded();
+
+    for len in (2..25).chain(500..510) {
+        let v = &mut v[0..len];
+        let tmp = &mut tmp[0..len];
+
+        for &modulus in &[5, 10, 100, 1000] {
+            for _ in 0..100 {
+                for i in 0..len {
+                    v[i] = rng.gen::<i32>() % modulus;
+                }
+
+                // Sort in default order.
+                tmp.copy_from_slice(v);
+                tmp.sort_unstable();
+                assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
+
+                // Sort in ascending order.
+                tmp.copy_from_slice(v);
+                tmp.sort_unstable_by(|a, b| a.cmp(b));
+                assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
+
+                // Sort in descending order.
+                tmp.copy_from_slice(v);
+                tmp.sort_unstable_by(|a, b| b.cmp(a));
+                assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
+
+                // Test heapsort using `<` operator.
+                tmp.copy_from_slice(v);
+                heapsort(tmp, |a, b| a < b);
+                assert!(tmp.windows(2).all(|w| w[0] <= w[1]));
+
+                // Test heapsort using `>` operator.
+                tmp.copy_from_slice(v);
+                heapsort(tmp, |a, b| a > b);
+                assert!(tmp.windows(2).all(|w| w[0] >= w[1]));
+            }
+        }
+    }
+
+    // Sort using a completely random comparison function.
+    // This will reorder the elements *somehow*, but won't panic.
+    for i in 0..v.len() {
+        v[i] = i as i32;
+    }
+    v.sort_unstable_by(|_, _| *rng.choose(&[Less, Equal, Greater]).unwrap());
+    v.sort_unstable();
+    for i in 0..v.len() {
+        assert_eq!(v[i], i as i32);
+    }
+
+    // Should not panic.
+    [0i32; 0].sort_unstable();
+    [(); 10].sort_unstable();
+    [(); 100].sort_unstable();
+
+    let mut v = [0xDEADBEEFu64];
+    v.sort_unstable();
+    assert!(v == [0xDEADBEEF]);
+}