src/test/run-pass/vector-sort-panic-safe.rs

   1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // ignore-emscripten no threads support
  12
  13 #![feature(rand)]
  14 #![feature(sort_unstable)]
  15 #![feature(const_atomic_usize_new)]
  16
  17 use std::__rand::{thread_rng, Rng};
  18 use std::cell::Cell;
  19 use std::cmp::Ordering;
  20 use std::panic;
  21 use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize};
  22 use std::sync::atomic::Ordering::Relaxed;
  23 use std::thread;
  24
  25 const MAX_LEN: usize = 80;
  26
  27 static DROP_COUNTS: [AtomicUsize; MAX_LEN] = [
  28     // FIXME #5244: AtomicUsize is not Copy.
  29     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  30     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  31     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  32     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  33     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  34     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  35     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  36     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  37     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  38     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  39     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  40     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  41     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  42     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  43     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  44     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  45     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  46     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  47     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  48     AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
  49 ];
  50
  51 static VERSIONS: AtomicUsize = ATOMIC_USIZE_INIT;
  52
  53 #[derive(Clone, Eq)]
  54 struct DropCounter {
  55     x: u32,
  56     id: usize,
  57     version: Cell<usize>,
  58 }
  59
  60 impl PartialEq for DropCounter {
  61     fn eq(&self, other: &Self) -> bool {
  62         self.partial_cmp(other) == Some(Ordering::Equal)
  63     }
  64 }
  65
  66 impl PartialOrd for DropCounter {
  67     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
  68         self.version.set(self.version.get() + 1);
  69         other.version.set(other.version.get() + 1);
  70         VERSIONS.fetch_add(2, Relaxed);
  71         self.x.partial_cmp(&other.x)
  72     }
  73 }
  74
  75 impl Ord for DropCounter {
  76     fn cmp(&self, other: &Self) -> Ordering {
  77         self.partial_cmp(other).unwrap()
  78     }
  79 }
  80
  81 impl Drop for DropCounter {
  82     fn drop(&mut self) {
  83         DROP_COUNTS[self.id].fetch_add(1, Relaxed);
  84         VERSIONS.fetch_sub(self.version.get(), Relaxed);
  85     }
  86 }
  87
  88 macro_rules! test {
  89     ($input:ident, $func:ident) => {
  90         let len = $input.len();
  91
  92         // Work out the total number of comparisons required to sort
  93         // this array...
  94         let mut count = 0usize;
  95         $input.to_owned().$func(|a, b| { count += 1; a.cmp(b) });
  96
  97         // ... and then panic on each and every single one.
  98         for panic_countdown in 0..count {
  99             // Refresh the counters.
 100             VERSIONS.store(0, Relaxed);
 101             for i in 0..len {
 102                 DROP_COUNTS[i].store(0, Relaxed);
 103             }
 104
 105             let v = $input.to_owned();
 106             let _ = thread::spawn(move || {
 107                 let mut v = v;
 108                 let mut panic_countdown = panic_countdown;
 109                 v.$func(|a, b| {
 110                     if panic_countdown == 0 {
 111                         SILENCE_PANIC.with(|s| s.set(true));
 112                         panic!();
 113                     }
 114                     panic_countdown -= 1;
 115                     a.cmp(b)
 116                 })
 117             }).join();
 118
 119             // Check that the number of things dropped is exactly
 120             // what we expect (i.e. the contents of `v`).
 121             for (i, c) in DROP_COUNTS.iter().enumerate().take(len) {
 122                 let count = c.load(Relaxed);
 123                 assert!(count == 1,
 124                         "found drop count == {} for i == {}, len == {}",
 125                         count, i, len);
 126             }
 127
 128             // Check that the most recent versions of values were dropped.
 129             assert_eq!(VERSIONS.load(Relaxed), 0);
 130         }
 131     }
 132 }
 133
 134 thread_local!(static SILENCE_PANIC: Cell<bool> = Cell::new(false));
 135
 136 fn main() {
 137     let prev = panic::take_hook();
 138     panic::set_hook(Box::new(move |info| {
 139         if !SILENCE_PANIC.with(|s| s.get()) {
 140             prev(info);
 141         }
 142     }));
 143
 144     let mut rng = thread_rng();
 145
 146     for len in (1..20).chain(70..MAX_LEN) {
 147         for &modulus in &[5, 20, 50] {
 148             for &has_runs in &[false, true] {
 149                 let mut input = (0..len)
 150                     .map(|id| {
 151                         DropCounter {
 152                             x: rng.next_u32() % modulus,
 153                             id: id,
 154                             version: Cell::new(0),
 155                         }
 156                     })
 157                     .collect::<Vec<_>>();
 158
 159                 if has_runs {
 160                     for c in &mut input {
 161                         c.x = c.id as u32;
 162                     }
 163
 164                     for _ in 0..5 {
 165                         let a = rng.gen::<usize>() % len;
 166                         let b = rng.gen::<usize>() % len;
 167                         if a < b {
 168                             input[a..b].reverse();
 169                         } else {
 170                             input.swap(a, b);
 171                         }
 172                     }
 173                 }
 174
 175                 test!(input, sort_by);
 176                 test!(input, sort_unstable_by);
 177             }
 178         }
 179     }
 180 }