src/test/run-pass-fulldeps/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(rustc_private, std_panic)]
  12
  13 extern crate rand;
  14
  15 use rand::{thread_rng, Rng};
  16 use std::panic::{self, AssertUnwindSafe};
  17
  18 use std::collections::BinaryHeap;
  19 use std::cmp;
  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 mut heap = BinaryHeap::from(panic_ords);
  70             let inner_data;
  71
  72             {
  73                 // push the panicking item to the heap and catch the panic
  74                 let thread_result = {
  75                     let mut heap_ref = AssertUnwindSafe(&mut heap);
  76                     panic::catch_unwind(move || {
  77                         heap_ref.push(panic_item);
  78                     })
  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                 inner_data = heap.clone().into_vec();
  86                 drop(heap);
  87             }
  88             let drops = DROP_COUNTER.load(Ordering::SeqCst);
  89             assert_eq!(drops, DATASZ);
  90
  91             let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
  92             data_sorted.sort();
  93             assert_eq!(data_sorted, data);
  94         }
  95     }
  96 }
  97
  98 fn main() {
  99     test_integrity();
 100 }
 101