| use rand::distributions::Uniform; |
| use rand::{thread_rng, Rng}; |
| use rayon::prelude::*; |
| use std::cell::Cell; |
| use std::cmp::{self, Ordering}; |
| use std::panic; |
| use std::sync::atomic::AtomicUsize; |
| use std::sync::atomic::Ordering::Relaxed; |
| use std::thread; |
| |
| static VERSIONS: AtomicUsize = AtomicUsize::new(0); |
| |
| lazy_static::lazy_static! { |
| static ref DROP_COUNTS: Vec<AtomicUsize> = (0..20_000).map(|_| AtomicUsize::new(0)).collect(); |
| } |
| |
| #[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 count = AtomicUsize::new(0); |
| $input.to_owned().$func(|a, b| { |
| count.fetch_add(1, Relaxed); |
| a.cmp(b) |
| }); |
| |
| let mut panic_countdown = count.load(Relaxed); |
| let step = if len <= 100 { |
| 1 |
| } else { |
| cmp::max(1, panic_countdown / 10) |
| }; |
| |
| // ... and then panic after each `step` comparisons. |
| loop { |
| // 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 panic_countdown = AtomicUsize::new(panic_countdown); |
| v.$func(|a, b| { |
| if panic_countdown.fetch_sub(1, Relaxed) == 1 { |
| SILENCE_PANIC.with(|s| s.set(true)); |
| panic!(); |
| } |
| 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); |
| |
| if panic_countdown < step { |
| break; |
| } |
| panic_countdown -= step; |
| } |
| }; |
| } |
| |
| thread_local!(static SILENCE_PANIC: Cell<bool> = Cell::new(false)); |
| |
| #[test] |
| fn sort_panic_safe() { |
| let prev = panic::take_hook(); |
| panic::set_hook(Box::new(move |info| { |
| if !SILENCE_PANIC.with(Cell::get) { |
| prev(info); |
| } |
| })); |
| |
| for &len in &[1, 2, 3, 4, 5, 10, 20, 100, 500, 5_000, 20_000] { |
| let len_dist = Uniform::new(0, len); |
| for &modulus in &[5, 30, 1_000, 20_000] { |
| for &has_runs in &[false, true] { |
| let mut rng = thread_rng(); |
| let mut input = (0..len) |
| .map(|id| DropCounter { |
| x: rng.gen_range(0..modulus), |
| 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.sample(&len_dist); |
| let b = rng.sample(&len_dist); |
| if a < b { |
| input[a..b].reverse(); |
| } else { |
| input.swap(a, b); |
| } |
| } |
| } |
| |
| test!(input, par_sort_by); |
| test!(input, par_sort_unstable_by); |
| } |
| } |
| } |
| } |