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.
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.
11 #![feature(recover, rand, std_panic)]
13 use std::__rand::{thread_rng, Rng};
14 use std::panic::{self, AssertRecoverSafe};
16 use std::collections::BinaryHeap;
18 use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
20 static DROP_COUNTER: AtomicUsize = ATOMIC_USIZE_INIT;
22 // old binaryheap failed this test
24 // Integrity means that all elements are present after a comparison panics,
25 // even if the order may not be correct.
27 // Destructors must be called exactly once per element.
29 #[derive(Eq, PartialEq, Ord, Clone, Debug)]
30 struct PanicOrd<T>(T, bool);
32 impl<T> Drop for PanicOrd<T> {
34 // update global drop count
35 DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
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");
44 self.0.partial_cmp(&other.0)
47 let mut rng = thread_rng();
48 const DATASZ: usize = 32;
49 const NTEST: usize = 10;
51 // don't use 0 in the data -- we want to catch the zeroed-out case.
52 let data = (1..DATASZ + 1).collect::<Vec<_>>();
54 // since it's a fuzzy test, run several tries.
56 for i in 1..DATASZ + 1 {
57 DROP_COUNTER.store(0, Ordering::SeqCst);
59 let mut panic_ords: Vec<_> = data.iter()
61 .map(|&x| PanicOrd(x, false))
63 let panic_item = PanicOrd(i, true);
65 // heapify the sane items
66 rng.shuffle(&mut panic_ords);
67 let mut heap = BinaryHeap::from(panic_ords);
71 // push the panicking item to the heap and catch the panic
73 let mut heap_ref = AssertRecoverSafe::new(&mut heap);
74 panic::recover(move || {
75 heap_ref.push(panic_item);
78 assert!(thread_result.is_err());
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();
86 let drops = DROP_COUNTER.load(Ordering::SeqCst);
87 assert_eq!(drops, DATASZ);
89 let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
91 assert_eq!(data_sorted, data);