From 6bc8f164b09b9994e6a2d4c4ca60d7d36c09d3fe Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Wed, 1 Nov 2017 12:32:13 -0700 Subject: std: Remove `rand` crate and module This commit removes the `rand` crate from the standard library facade as well as the `__rand` module in the standard library. Neither of these were used in any meaningful way in the standard library itself. The only need for randomness in libstd is to initialize the thread-local keys of a `HashMap`, and that unconditionally used `OsRng` defined in the standard library anyway. The cruft of the `rand` crate and the extra `rand` support in the standard library makes libstd slightly more difficult to port to new platforms, namely WebAssembly which doesn't have any randomness at all (without interfacing with JS). The purpose of this commit is to clarify and streamline randomness in libstd, focusing on how it's only required in one location, hashmap seeds. Note that the `rand` crate out of tree has almost always been a drop-in replacement for the `rand` crate in-tree, so any usage (accidental or purposeful) of the crate in-tree should switch to the `rand` crate on crates.io. This then also has the further benefit of avoiding duplication (mostly) between the two crates! --- src/test/compile-fail/task-rng-isnt-sendable.rs | 21 --- .../run-pass-fulldeps/binary-heap-panic-safe.rs | 101 ++++++++++++ src/test/run-pass-fulldeps/env.rs | 99 +++++++++++ .../run-pass-fulldeps/vector-sort-panic-safe.rs | 182 +++++++++++++++++++++ src/test/run-pass/binary-heap-panic-safe.rs | 99 ----------- src/test/run-pass/env.rs | 98 ----------- src/test/run-pass/vector-sort-panic-safe.rs | 180 -------------------- 7 files changed, 382 insertions(+), 398 deletions(-) delete mode 100644 src/test/compile-fail/task-rng-isnt-sendable.rs create mode 100644 src/test/run-pass-fulldeps/binary-heap-panic-safe.rs create mode 100644 src/test/run-pass-fulldeps/env.rs create mode 100644 src/test/run-pass-fulldeps/vector-sort-panic-safe.rs delete mode 100644 src/test/run-pass/binary-heap-panic-safe.rs delete mode 100644 src/test/run-pass/env.rs delete mode 100644 src/test/run-pass/vector-sort-panic-safe.rs (limited to 'src/test') diff --git a/src/test/compile-fail/task-rng-isnt-sendable.rs b/src/test/compile-fail/task-rng-isnt-sendable.rs deleted file mode 100644 index d85717f8ce5..00000000000 --- a/src/test/compile-fail/task-rng-isnt-sendable.rs +++ /dev/null @@ -1,21 +0,0 @@ -// Copyright 2013 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 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -#![feature(rand)] - -// ensure that the ThreadRng isn't/doesn't become accidentally sendable. - -use std::__rand::ThreadRng; - -fn test_send() {} - -pub fn main() { - test_send::(); //~ ERROR std::marker::Send` is not satisfied -} diff --git a/src/test/run-pass-fulldeps/binary-heap-panic-safe.rs b/src/test/run-pass-fulldeps/binary-heap-panic-safe.rs new file mode 100644 index 00000000000..6139a7d3201 --- /dev/null +++ b/src/test/run-pass-fulldeps/binary-heap-panic-safe.rs @@ -0,0 +1,101 @@ +// 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#![feature(rustc_private, std_panic)] + +extern crate rand; + +use rand::{thread_rng, Rng}; +use std::panic::{self, AssertUnwindSafe}; + +use std::collections::BinaryHeap; +use std::cmp; +use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering}; + +static DROP_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT; + +// 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. +fn test_integrity() { + #[derive(Eq, PartialEq, Ord, Clone, Debug)] + struct PanicOrd(T, bool); + + impl Drop for PanicOrd { + fn drop(&mut self) { + // update global drop count + DROP_COUNTER.fetch_add(1, Ordering::SeqCst); + } + } + + impl PartialOrd for PanicOrd { + fn partial_cmp(&self, other: &Self) -> Option { + 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::>(); + + // 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::>(); + data_sorted.sort(); + assert_eq!(data_sorted, data); + } + } +} + +fn main() { + test_integrity(); +} + diff --git a/src/test/run-pass-fulldeps/env.rs b/src/test/run-pass-fulldeps/env.rs new file mode 100644 index 00000000000..cf2ea732ee1 --- /dev/null +++ b/src/test/run-pass-fulldeps/env.rs @@ -0,0 +1,99 @@ +// 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// compile-flags: --test + +#![feature(rustc_private, std_panic)] + +extern crate rand; + +use std::env::*; +use std::iter::repeat; +use std::ffi::{OsString, OsStr}; + +use rand::Rng; + +fn make_rand_name() -> OsString { + let mut rng = rand::thread_rng(); + let n = format!("TEST{}", rng.gen_ascii_chars().take(10) + .collect::()); + let n = OsString::from(n); + assert!(var_os(&n).is_none()); + n +} + +fn eq(a: Option, b: Option<&str>) { + assert_eq!(a.as_ref().map(|s| &**s), b.map(OsStr::new).map(|s| &*s)); +} + +#[test] +fn test_set_var() { + let n = make_rand_name(); + set_var(&n, "VALUE"); + eq(var_os(&n), Some("VALUE")); +} + +#[test] +fn test_remove_var() { + let n = make_rand_name(); + set_var(&n, "VALUE"); + remove_var(&n); + eq(var_os(&n), None); +} + +#[test] +fn test_set_var_overwrite() { + let n = make_rand_name(); + set_var(&n, "1"); + set_var(&n, "2"); + eq(var_os(&n), Some("2")); + set_var(&n, ""); + eq(var_os(&n), Some("")); +} + +#[test] +#[cfg_attr(target_os = "emscripten", ignore)] +fn test_var_big() { + let mut s = "".to_string(); + let mut i = 0; + while i < 100 { + s.push_str("aaaaaaaaaa"); + i += 1; + } + let n = make_rand_name(); + set_var(&n, &s); + eq(var_os(&n), Some(&s)); +} + +#[test] +#[cfg_attr(target_os = "emscripten", ignore)] +fn test_env_set_get_huge() { + let n = make_rand_name(); + let s = repeat("x").take(10000).collect::(); + set_var(&n, &s); + eq(var_os(&n), Some(&s)); + remove_var(&n); + eq(var_os(&n), None); +} + +#[test] +fn test_env_set_var() { + let n = make_rand_name(); + + let mut e = vars_os(); + set_var(&n, "VALUE"); + assert!(!e.any(|(k, v)| { + &*k == &*n && &*v == "VALUE" + })); + + assert!(vars_os().any(|(k, v)| { + &*k == &*n && &*v == "VALUE" + })); +} diff --git a/src/test/run-pass-fulldeps/vector-sort-panic-safe.rs b/src/test/run-pass-fulldeps/vector-sort-panic-safe.rs new file mode 100644 index 00000000000..82305045f80 --- /dev/null +++ b/src/test/run-pass-fulldeps/vector-sort-panic-safe.rs @@ -0,0 +1,182 @@ +// Copyright 2013 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// ignore-emscripten no threads support + +#![feature(rustc_private)] +#![feature(sort_unstable)] +#![feature(const_atomic_usize_new)] + +extern crate rand; + +use rand::{thread_rng, Rng}; +use std::cell::Cell; +use std::cmp::Ordering; +use std::panic; +use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize}; +use std::sync::atomic::Ordering::Relaxed; +use std::thread; + +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, +} + +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 { + 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 = Cell::new(false)); + +fn main() { + 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::>(); + + if has_runs { + for c in &mut input { + c.x = c.id as u32; + } + + for _ in 0..5 { + let a = rng.gen::() % len; + let b = rng.gen::() % len; + if a < b { + input[a..b].reverse(); + } else { + input.swap(a, b); + } + } + } + + test!(input, sort_by); + test!(input, sort_unstable_by); + } + } + } +} diff --git a/src/test/run-pass/binary-heap-panic-safe.rs b/src/test/run-pass/binary-heap-panic-safe.rs deleted file mode 100644 index 93d3345a809..00000000000 --- a/src/test/run-pass/binary-heap-panic-safe.rs +++ /dev/null @@ -1,99 +0,0 @@ -// 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 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -#![feature(rand, std_panic)] - -use std::__rand::{thread_rng, Rng}; -use std::panic::{self, AssertUnwindSafe}; - -use std::collections::BinaryHeap; -use std::cmp; -use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering}; - -static DROP_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT; - -// 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. -fn test_integrity() { - #[derive(Eq, PartialEq, Ord, Clone, Debug)] - struct PanicOrd(T, bool); - - impl Drop for PanicOrd { - fn drop(&mut self) { - // update global drop count - DROP_COUNTER.fetch_add(1, Ordering::SeqCst); - } - } - - impl PartialOrd for PanicOrd { - fn partial_cmp(&self, other: &Self) -> Option { - 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::>(); - - // 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::>(); - data_sorted.sort(); - assert_eq!(data_sorted, data); - } - } -} - -fn main() { - test_integrity(); -} - diff --git a/src/test/run-pass/env.rs b/src/test/run-pass/env.rs deleted file mode 100644 index e602fb2d7d2..00000000000 --- a/src/test/run-pass/env.rs +++ /dev/null @@ -1,98 +0,0 @@ -// 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 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// compile-flags: --test - -#![feature(rand, std_panic)] - -use std::env::*; -use std::__rand as rand; -use std::__rand::Rng; -use std::iter::repeat; -use std::ffi::{OsString, OsStr}; - - -fn make_rand_name() -> OsString { - let mut rng = rand::thread_rng(); - let n = format!("TEST{}", rng.gen_ascii_chars().take(10) - .collect::()); - let n = OsString::from(n); - assert!(var_os(&n).is_none()); - n -} - -fn eq(a: Option, b: Option<&str>) { - assert_eq!(a.as_ref().map(|s| &**s), b.map(OsStr::new).map(|s| &*s)); -} - -#[test] -fn test_set_var() { - let n = make_rand_name(); - set_var(&n, "VALUE"); - eq(var_os(&n), Some("VALUE")); -} - -#[test] -fn test_remove_var() { - let n = make_rand_name(); - set_var(&n, "VALUE"); - remove_var(&n); - eq(var_os(&n), None); -} - -#[test] -fn test_set_var_overwrite() { - let n = make_rand_name(); - set_var(&n, "1"); - set_var(&n, "2"); - eq(var_os(&n), Some("2")); - set_var(&n, ""); - eq(var_os(&n), Some("")); -} - -#[test] -#[cfg_attr(target_os = "emscripten", ignore)] -fn test_var_big() { - let mut s = "".to_string(); - let mut i = 0; - while i < 100 { - s.push_str("aaaaaaaaaa"); - i += 1; - } - let n = make_rand_name(); - set_var(&n, &s); - eq(var_os(&n), Some(&s)); -} - -#[test] -#[cfg_attr(target_os = "emscripten", ignore)] -fn test_env_set_get_huge() { - let n = make_rand_name(); - let s = repeat("x").take(10000).collect::(); - set_var(&n, &s); - eq(var_os(&n), Some(&s)); - remove_var(&n); - eq(var_os(&n), None); -} - -#[test] -fn test_env_set_var() { - let n = make_rand_name(); - - let mut e = vars_os(); - set_var(&n, "VALUE"); - assert!(!e.any(|(k, v)| { - &*k == &*n && &*v == "VALUE" - })); - - assert!(vars_os().any(|(k, v)| { - &*k == &*n && &*v == "VALUE" - })); -} diff --git a/src/test/run-pass/vector-sort-panic-safe.rs b/src/test/run-pass/vector-sort-panic-safe.rs deleted file mode 100644 index c6a1859de30..00000000000 --- a/src/test/run-pass/vector-sort-panic-safe.rs +++ /dev/null @@ -1,180 +0,0 @@ -// Copyright 2013 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 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// ignore-emscripten no threads support - -#![feature(rand)] -#![feature(sort_unstable)] -#![feature(const_atomic_usize_new)] - -use std::__rand::{thread_rng, Rng}; -use std::cell::Cell; -use std::cmp::Ordering; -use std::panic; -use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize}; -use std::sync::atomic::Ordering::Relaxed; -use std::thread; - -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, -} - -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 { - 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 = Cell::new(false)); - -fn main() { - 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::>(); - - if has_runs { - for c in &mut input { - c.x = c.id as u32; - } - - for _ in 0..5 { - let a = rng.gen::() % len; - let b = rng.gen::() % len; - if a < b { - input[a..b].reverse(); - } else { - input.swap(a, b); - } - } - } - - test!(input, sort_by); - test!(input, sort_unstable_by); - } - } - } -} -- cgit 1.4.1-3-g733a5