Auto merge of #48549 - alexcrichton:update-cargo, r=Mark-Simulacrum

Update Cargo submodule

Hopefully a routine update...

3 files changed, 248 insertions, 2 deletions

diff --git a/src/liballoc/Cargo.toml b/src/liballoc/Cargo.toml
index 0a265ee1376..3bf919b0c00 100644
--- a/src/liballoc/Cargo.toml
+++ b/src/liballoc/Cargo.toml
@@ -12,7 +12,7 @@ core = { path = "../libcore" }
 std_unicode = { path = "../libstd_unicode" }
 
 [dev-dependencies]
-rand = "0.3"
+rand = "0.4"
 
 [[test]]
 name = "collectionstests"
diff --git a/src/liballoc/tests/binary_heap.rs b/src/liballoc/tests/binary_heap.rs
index 06d585f8ea8..5c979d82e55 100644
--- a/src/liballoc/tests/binary_heap.rs
+++ b/src/liballoc/tests/binary_heap.rs
@@ -8,9 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::panic;
+use std::cmp;
 use std::collections::BinaryHeap;
 use std::collections::binary_heap::{Drain, PeekMut};
+use std::panic::{self, AssertUnwindSafe};
+use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
+
+use rand::{thread_rng, Rng};
 
 #[test]
 fn test_iterator() {
@@ -300,3 +304,80 @@ fn assert_covariance() {
         d
     }
 }
+
+// old binaryheap failed this test
+//
+// Integrity means that all elements are present after a comparison panics,
+// even if the order may not be correct.
+//
+// Destructors must be called exactly once per element.
+#[test]
+fn panic_safe() {
+    static DROP_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT;
+
+    #[derive(Eq, PartialEq, Ord, Clone, Debug)]
+    struct PanicOrd<T>(T, bool);
+
+    impl<T> Drop for PanicOrd<T> {
+        fn drop(&mut self) {
+            // update global drop count
+            DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
+        }
+    }
+
+    impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
+        fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
+            if self.1 || other.1 {
+                panic!("Panicking comparison");
+            }
+            self.0.partial_cmp(&other.0)
+        }
+    }
+    let mut rng = thread_rng();
+    const DATASZ: usize = 32;
+    const NTEST: usize = 10;
+
+    // don't use 0 in the data -- we want to catch the zeroed-out case.
+    let data = (1..DATASZ + 1).collect::<Vec<_>>();
+
+    // since it's a fuzzy test, run several tries.
+    for _ in 0..NTEST {
+        for i in 1..DATASZ + 1 {
+            DROP_COUNTER.store(0, Ordering::SeqCst);
+
+            let mut panic_ords: Vec<_> = data.iter()
+                                             .filter(|&&x| x != i)
+                                             .map(|&x| PanicOrd(x, false))
+                                             .collect();
+            let panic_item = PanicOrd(i, true);
+
+            // heapify the sane items
+            rng.shuffle(&mut panic_ords);
+            let mut heap = BinaryHeap::from(panic_ords);
+            let inner_data;
+
+            {
+                // push the panicking item to the heap and catch the panic
+                let thread_result = {
+                    let mut heap_ref = AssertUnwindSafe(&mut heap);
+                    panic::catch_unwind(move || {
+                        heap_ref.push(panic_item);
+                    })
+                };
+                assert!(thread_result.is_err());
+
+                // Assert no elements were dropped
+                let drops = DROP_COUNTER.load(Ordering::SeqCst);
+                assert!(drops == 0, "Must not drop items. drops={}", drops);
+                inner_data = heap.clone().into_vec();
+                drop(heap);
+            }
+            let drops = DROP_COUNTER.load(Ordering::SeqCst);
+            assert_eq!(drops, DATASZ);
+
+            let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
+            data_sorted.sort();
+            assert_eq!(data_sorted, data);
+        }
+    }
+}
diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs
index 1a9d26fd1a2..d9e9d91cea8 100644
--- a/src/liballoc/tests/slice.rs
+++ b/src/liballoc/tests/slice.rs
@@ -8,9 +8,15 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use std::cell::Cell;
 use std::cmp::Ordering::{Equal, Greater, Less};
+use std::cmp::Ordering;
 use std::mem;
+use std::panic;
 use std::rc::Rc;
+use std::sync::atomic::Ordering::Relaxed;
+use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize};
+use std::thread;
 
 use rand::{Rng, thread_rng};
 
@@ -1341,3 +1347,162 @@ fn test_copy_from_slice_dst_shorter() {
     let mut dst = [0; 3];
     dst.copy_from_slice(&src);
 }
+
+const MAX_LEN: usize = 80;
+
+static DROP_COUNTS: [AtomicUsize; MAX_LEN] = [
+    // FIXME #5244: AtomicUsize is not Copy.
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+    AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
+];
+
+static VERSIONS: AtomicUsize = ATOMIC_USIZE_INIT;
+
+#[derive(Clone, Eq)]
+struct DropCounter {
+    x: u32,
+    id: usize,
+    version: Cell<usize>,
+}
+
+impl PartialEq for DropCounter {
+    fn eq(&self, other: &Self) -> bool {
+        self.partial_cmp(other) == Some(Ordering::Equal)
+    }
+}
+
+impl PartialOrd for DropCounter {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        self.version.set(self.version.get() + 1);
+        other.version.set(other.version.get() + 1);
+        VERSIONS.fetch_add(2, Relaxed);
+        self.x.partial_cmp(&other.x)
+    }
+}
+
+impl Ord for DropCounter {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.partial_cmp(other).unwrap()
+    }
+}
+
+impl Drop for DropCounter {
+    fn drop(&mut self) {
+        DROP_COUNTS[self.id].fetch_add(1, Relaxed);
+        VERSIONS.fetch_sub(self.version.get(), Relaxed);
+    }
+}
+
+macro_rules! test {
+    ($input:ident, $func:ident) => {
+        let len = $input.len();
+
+        // Work out the total number of comparisons required to sort
+        // this array...
+        let mut count = 0usize;
+        $input.to_owned().$func(|a, b| { count += 1; a.cmp(b) });
+
+        // ... and then panic on each and every single one.
+        for panic_countdown in 0..count {
+            // Refresh the counters.
+            VERSIONS.store(0, Relaxed);
+            for i in 0..len {
+                DROP_COUNTS[i].store(0, Relaxed);
+            }
+
+            let v = $input.to_owned();
+            let _ = thread::spawn(move || {
+                let mut v = v;
+                let mut panic_countdown = panic_countdown;
+                v.$func(|a, b| {
+                    if panic_countdown == 0 {
+                        SILENCE_PANIC.with(|s| s.set(true));
+                        panic!();
+                    }
+                    panic_countdown -= 1;
+                    a.cmp(b)
+                })
+            }).join();
+
+            // Check that the number of things dropped is exactly
+            // what we expect (i.e. the contents of `v`).
+            for (i, c) in DROP_COUNTS.iter().enumerate().take(len) {
+                let count = c.load(Relaxed);
+                assert!(count == 1,
+                        "found drop count == {} for i == {}, len == {}",
+                        count, i, len);
+            }
+
+            // Check that the most recent versions of values were dropped.
+            assert_eq!(VERSIONS.load(Relaxed), 0);
+        }
+    }
+}
+
+thread_local!(static SILENCE_PANIC: Cell<bool> = Cell::new(false));
+
+#[test]
+#[cfg_attr(target_os = "emscripten", ignore)] // no threads
+fn panic_safe() {
+    let prev = panic::take_hook();
+    panic::set_hook(Box::new(move |info| {
+        if !SILENCE_PANIC.with(|s| s.get()) {
+            prev(info);
+        }
+    }));
+
+    let mut rng = thread_rng();
+
+    for len in (1..20).chain(70..MAX_LEN) {
+        for &modulus in &[5, 20, 50] {
+            for &has_runs in &[false, true] {
+                let mut input = (0..len)
+                    .map(|id| {
+                        DropCounter {
+                            x: rng.next_u32() % modulus,
+                            id: id,
+                            version: Cell::new(0),
+                        }
+                    })
+                    .collect::<Vec<_>>();
+
+                if has_runs {
+                    for c in &mut input {
+                        c.x = c.id as u32;
+                    }
+
+                    for _ in 0..5 {
+                        let a = rng.gen::<usize>() % len;
+                        let b = rng.gen::<usize>() % len;
+                        if a < b {
+                            input[a..b].reverse();
+                        } else {
+                            input.swap(a, b);
+                        }
+                    }
+                }
+
+                test!(input, sort_by);
+                test!(input, sort_unstable_by);
+            }
+        }
+    }
+}