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