src/test/run-pass/binary-heap-panic-safe.rs

   1 // Copyright 2015 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 #![feature(std_misc, binary_heap_extras, catch_panic, rand, sync_poison)]
  12
  13 use std::__rand::{thread_rng, Rng};
  14 use std::thread;
  15
  16 use std::collections::BinaryHeap;
  17 use std::cmp;
  18 use std::sync::Arc;
  19 use std::sync::Mutex;
  20 use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
  21
  22 static DROP_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT;
  23
  24 // old binaryheap failed this test
  25 //
  26 // Integrity means that all elements are present after a comparison panics,
  27 // even if the order may not be correct.
  28 //
  29 // Destructors must be called exactly once per element.
  30 fn test_integrity() {
  31     #[derive(Eq, PartialEq, Ord, Clone, Debug)]
  32     struct PanicOrd<T>(T, bool);
  33
  34     impl<T> Drop for PanicOrd<T> {
  35         fn drop(&mut self) {
  36             // update global drop count
  37             DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
  38         }
  39     }
  40
  41     impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
  42         fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
  43             if self.1 || other.1 {
  44                 panic!("Panicking comparison");
  45             }
  46             self.0.partial_cmp(&other.0)
  47         }
  48     }
  49     let mut rng = thread_rng();
  50     const DATASZ: usize = 32;
  51     const NTEST: usize = 10;
  52
  53     // don't use 0 in the data -- we want to catch the zeroed-out case.
  54     let data = (1..DATASZ + 1).collect::<Vec<_>>();
  55
  56     // since it's a fuzzy test, run several tries.
  57     for _ in 0..NTEST {
  58         for i in 1..DATASZ + 1 {
  59             DROP_COUNTER.store(0, Ordering::SeqCst);
  60
  61             let mut panic_ords: Vec<_> = data.iter()
  62                                              .filter(|&&x| x != i)
  63                                              .map(|&x| PanicOrd(x, false))
  64                                              .collect();
  65             let panic_item = PanicOrd(i, true);
  66
  67             // heapify the sane items
  68             rng.shuffle(&mut panic_ords);
  69             let heap = Arc::new(Mutex::new(BinaryHeap::from_vec(panic_ords)));
  70             let inner_data;
  71
  72             {
  73                 let heap_ref = heap.clone();
  74
  75
  76                 // push the panicking item to the heap and catch the panic
  77                 let thread_result = thread::catch_panic(move || {
  78                     heap.lock().unwrap().push(panic_item);
  79                 });
  80                 assert!(thread_result.is_err());
  81
  82                 // Assert no elements were dropped
  83                 let drops = DROP_COUNTER.load(Ordering::SeqCst);
  84                 //assert!(drops == 0, "Must not drop items. drops={}", drops);
  85
  86                 {
  87                     // now fetch the binary heap's data vector
  88                     let mutex_guard = match heap_ref.lock() {
  89                         Ok(x) => x,
  90                         Err(poison) => poison.into_inner(),
  91                     };
  92                     inner_data = mutex_guard.clone().into_vec();
  93                 }
  94             }
  95             let drops = DROP_COUNTER.load(Ordering::SeqCst);
  96             assert_eq!(drops, DATASZ);
  97
  98             let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
  99             data_sorted.sort();
 100             assert_eq!(data_sorted, data);
 101         }
 102     }
 103 }
 104
 105 fn main() {
 106     test_integrity();
 107 }
 108