| 1 |
use rand::distributions::Uniform; |
| 2 |
use rand::{thread_rng, Rng}; |
| 3 |
use rayon::prelude::*; |
| 4 |
use std::cell::Cell; |
| 5 |
use std::cmp::Ordering; |
| 6 |
use std::panic; |
| 7 |
use std::sync::atomic::AtomicUsize; |
| 8 |
use std::sync::atomic::Ordering::Relaxed; |
| 9 |
use std::thread; |
| 10 |
|
| 11 |
// const is needed for array initializer |
| 12 |
#[allow(clippy::declare_interior_mutable_const)] |
| 13 |
const ZERO: AtomicUsize = AtomicUsize::new(0); |
| 14 |
const LEN: usize = 20_000; |
| 15 |
|
| 16 |
static VERSIONS: AtomicUsize = ZERO; |
| 17 |
|
| 18 |
static DROP_COUNTS: [AtomicUsize; LEN] = [ZERO; LEN]; |
| 19 |
|
| 20 |
#[derive(Clone, Eq)] |
| 21 |
struct DropCounter { |
| 22 |
x: u32, |
| 23 |
id: usize, |
| 24 |
version: Cell<usize>, |
| 25 |
} |
| 26 |
|
| 27 |
impl PartialEq for DropCounter { |
| 28 |
fn eq(&self, other: &Self) -> bool { |
| 29 |
self.partial_cmp(other) == Some(Ordering::Equal) |
| 30 |
} |
| 31 |
} |
| 32 |
|
| 33 |
#[allow(clippy::non_canonical_partial_ord_impl)] |
| 34 |
impl PartialOrd for DropCounter { |
| 35 |
fn partial_cmp(&self, other: &Self) -> Option<Ordering> { |
| 36 |
self.version.set(self.version.get() + 1); |
| 37 |
other.version.set(other.version.get() + 1); |
| 38 |
VERSIONS.fetch_add(2, Relaxed); |
| 39 |
self.x.partial_cmp(&other.x) |
| 40 |
} |
| 41 |
} |
| 42 |
|
| 43 |
impl Ord for DropCounter { |
| 44 |
fn cmp(&self, other: &Self) -> Ordering { |
| 45 |
self.partial_cmp(other).unwrap() |
| 46 |
} |
| 47 |
} |
| 48 |
|
| 49 |
impl Drop for DropCounter { |
| 50 |
fn drop(&mut self) { |
| 51 |
DROP_COUNTS[self.id].fetch_add(1, Relaxed); |
| 52 |
VERSIONS.fetch_sub(self.version.get(), Relaxed); |
| 53 |
} |
| 54 |
} |
| 55 |
|
| 56 |
macro_rules! test { |
| 57 |
($input:ident, $func:ident) => { |
| 58 |
let len = $input.len(); |
| 59 |
|
| 60 |
// Work out the total number of comparisons required to sort |
| 61 |
// this array... |
| 62 |
let count = AtomicUsize::new(0); |
| 63 |
$input.to_owned().$func(|a, b| { |
| 64 |
count.fetch_add(1, Relaxed); |
| 65 |
a.cmp(b) |
| 66 |
}); |
| 67 |
|
| 68 |
let mut panic_countdown = count.load(Relaxed); |
| 69 |
let step = if len <= 100 { |
| 70 |
1 |
| 71 |
} else { |
| 72 |
Ord::max(1, panic_countdown / 10) |
| 73 |
}; |
| 74 |
|
| 75 |
// ... and then panic after each `step` comparisons. |
| 76 |
loop { |
| 77 |
// Refresh the counters. |
| 78 |
VERSIONS.store(0, Relaxed); |
| 79 |
for i in 0..len { |
| 80 |
DROP_COUNTS[i].store(0, Relaxed); |
| 81 |
} |
| 82 |
|
| 83 |
let v = $input.to_owned(); |
| 84 |
let _ = thread::spawn(move || { |
| 85 |
let mut v = v; |
| 86 |
let panic_countdown = AtomicUsize::new(panic_countdown); |
| 87 |
v.$func(|a, b| { |
| 88 |
if panic_countdown.fetch_sub(1, Relaxed) == 1 { |
| 89 |
SILENCE_PANIC.with(|s| s.set(true)); |
| 90 |
panic!(); |
| 91 |
} |
| 92 |
a.cmp(b) |
| 93 |
}) |
| 94 |
}) |
| 95 |
.join(); |
| 96 |
|
| 97 |
// Check that the number of things dropped is exactly |
| 98 |
// what we expect (i.e. the contents of `v`). |
| 99 |
for (i, c) in DROP_COUNTS.iter().enumerate().take(len) { |
| 100 |
let count = c.load(Relaxed); |
| 101 |
assert!( |
| 102 |
count == 1, |
| 103 |
"found drop count == {} for i == {}, len == {}", |
| 104 |
count, |
| 105 |
i, |
| 106 |
len |
| 107 |
); |
| 108 |
} |
| 109 |
|
| 110 |
// Check that the most recent versions of values were dropped. |
| 111 |
assert_eq!(VERSIONS.load(Relaxed), 0); |
| 112 |
|
| 113 |
if panic_countdown < step { |
| 114 |
break; |
| 115 |
} |
| 116 |
panic_countdown -= step; |
| 117 |
} |
| 118 |
}; |
| 119 |
} |
| 120 |
|
| 121 |
thread_local!(static SILENCE_PANIC: Cell<bool> = const { Cell::new(false) }); |
| 122 |
|
| 123 |
#[test] |
| 124 |
#[cfg_attr(any(target_os = "emscripten", target_family = "wasm"), ignore)] |
| 125 |
fn sort_panic_safe() { |
| 126 |
let prev = panic::take_hook(); |
| 127 |
panic::set_hook(Box::new(move |info| { |
| 128 |
if !SILENCE_PANIC.with(Cell::get) { |
| 129 |
prev(info); |
| 130 |
} |
| 131 |
})); |
| 132 |
|
| 133 |
for &len in &[1, 2, 3, 4, 5, 10, 20, 100, 500, 5_000, 20_000] { |
| 134 |
let len_dist = Uniform::new(0, len); |
| 135 |
for &modulus in &[5, 30, 1_000, 20_000] { |
| 136 |
for &has_runs in &[false, true] { |
| 137 |
let mut rng = thread_rng(); |
| 138 |
let mut input = (0..len) |
| 139 |
.map(|id| DropCounter { |
| 140 |
x: rng.gen_range(0..modulus), |
| 141 |
id, |
| 142 |
version: Cell::new(0), |
| 143 |
}) |
| 144 |
.collect::<Vec<_>>(); |
| 145 |
|
| 146 |
if has_runs { |
| 147 |
for c in &mut input { |
| 148 |
c.x = c.id as u32; |
| 149 |
} |
| 150 |
|
| 151 |
for _ in 0..5 { |
| 152 |
let a = rng.sample(len_dist); |
| 153 |
let b = rng.sample(len_dist); |
| 154 |
if a < b { |
| 155 |
input[a..b].reverse(); |
| 156 |
} else { |
| 157 |
input.swap(a, b); |
| 158 |
} |
| 159 |
} |
| 160 |
} |
| 161 |
|
| 162 |
test!(input, par_sort_by); |
| 163 |
test!(input, par_sort_unstable_by); |
| 164 |
} |
| 165 |
} |
| 166 |
} |
| 167 |
} |