1 use super::*;
2 use crate::boxed::Box;
3 use crate::testing::crash_test::{CrashTestDummy, Panic};
4 use core::mem;
5 use std::iter::TrustedLen;
6 use std::panic::{catch_unwind, AssertUnwindSafe};
7
8 #[test]
test_iterator()9 fn test_iterator() {
10 let data = vec![5, 9, 3];
11 let iterout = [9, 5, 3];
12 let heap = BinaryHeap::from(data);
13 let mut i = 0;
14 for el in &heap {
15 assert_eq!(*el, iterout[i]);
16 i += 1;
17 }
18 }
19
20 #[test]
test_iter_rev_cloned_collect()21 fn test_iter_rev_cloned_collect() {
22 let data = vec![5, 9, 3];
23 let iterout = vec![3, 5, 9];
24 let pq = BinaryHeap::from(data);
25
26 let v: Vec<_> = pq.iter().rev().cloned().collect();
27 assert_eq!(v, iterout);
28 }
29
30 #[test]
test_into_iter_collect()31 fn test_into_iter_collect() {
32 let data = vec![5, 9, 3];
33 let iterout = vec![9, 5, 3];
34 let pq = BinaryHeap::from(data);
35
36 let v: Vec<_> = pq.into_iter().collect();
37 assert_eq!(v, iterout);
38 }
39
40 #[test]
test_into_iter_size_hint()41 fn test_into_iter_size_hint() {
42 let data = vec![5, 9];
43 let pq = BinaryHeap::from(data);
44
45 let mut it = pq.into_iter();
46
47 assert_eq!(it.size_hint(), (2, Some(2)));
48 assert_eq!(it.next(), Some(9));
49
50 assert_eq!(it.size_hint(), (1, Some(1)));
51 assert_eq!(it.next(), Some(5));
52
53 assert_eq!(it.size_hint(), (0, Some(0)));
54 assert_eq!(it.next(), None);
55 }
56
57 #[test]
test_into_iter_rev_collect()58 fn test_into_iter_rev_collect() {
59 let data = vec![5, 9, 3];
60 let iterout = vec![3, 5, 9];
61 let pq = BinaryHeap::from(data);
62
63 let v: Vec<_> = pq.into_iter().rev().collect();
64 assert_eq!(v, iterout);
65 }
66
67 #[test]
test_into_iter_sorted_collect()68 fn test_into_iter_sorted_collect() {
69 let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
70 let it = heap.into_iter_sorted();
71 let sorted = it.collect::<Vec<_>>();
72 assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
73 }
74
75 #[test]
test_drain_sorted_collect()76 fn test_drain_sorted_collect() {
77 let mut heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
78 let it = heap.drain_sorted();
79 let sorted = it.collect::<Vec<_>>();
80 assert_eq!(sorted, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 0]);
81 }
82
check_exact_size_iterator<I: ExactSizeIterator>(len: usize, it: I)83 fn check_exact_size_iterator<I: ExactSizeIterator>(len: usize, it: I) {
84 let mut it = it;
85
86 for i in 0..it.len() {
87 let (lower, upper) = it.size_hint();
88 assert_eq!(Some(lower), upper);
89 assert_eq!(lower, len - i);
90 assert_eq!(it.len(), len - i);
91 it.next();
92 }
93 assert_eq!(it.len(), 0);
94 assert!(it.is_empty());
95 }
96
97 #[test]
test_exact_size_iterator()98 fn test_exact_size_iterator() {
99 let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
100 check_exact_size_iterator(heap.len(), heap.iter());
101 check_exact_size_iterator(heap.len(), heap.clone().into_iter());
102 check_exact_size_iterator(heap.len(), heap.clone().into_iter_sorted());
103 check_exact_size_iterator(heap.len(), heap.clone().drain());
104 check_exact_size_iterator(heap.len(), heap.clone().drain_sorted());
105 }
106
check_trusted_len<I: TrustedLen>(len: usize, it: I)107 fn check_trusted_len<I: TrustedLen>(len: usize, it: I) {
108 let mut it = it;
109 for i in 0..len {
110 let (lower, upper) = it.size_hint();
111 if upper.is_some() {
112 assert_eq!(Some(lower), upper);
113 assert_eq!(lower, len - i);
114 }
115 it.next();
116 }
117 }
118
119 #[test]
test_trusted_len()120 fn test_trusted_len() {
121 let heap = BinaryHeap::from(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
122 check_trusted_len(heap.len(), heap.clone().into_iter_sorted());
123 check_trusted_len(heap.len(), heap.clone().drain_sorted());
124 }
125
126 #[test]
test_peek_and_pop()127 fn test_peek_and_pop() {
128 let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
129 let mut sorted = data.clone();
130 sorted.sort();
131 let mut heap = BinaryHeap::from(data);
132 while !heap.is_empty() {
133 assert_eq!(heap.peek().unwrap(), sorted.last().unwrap());
134 assert_eq!(heap.pop().unwrap(), sorted.pop().unwrap());
135 }
136 }
137
138 #[test]
test_peek_mut()139 fn test_peek_mut() {
140 let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
141 let mut heap = BinaryHeap::from(data);
142 assert_eq!(heap.peek(), Some(&10));
143 {
144 let mut top = heap.peek_mut().unwrap();
145 *top -= 2;
146 }
147 assert_eq!(heap.peek(), Some(&9));
148 }
149
150 #[test]
test_peek_mut_leek()151 fn test_peek_mut_leek() {
152 let data = vec![4, 2, 7];
153 let mut heap = BinaryHeap::from(data);
154 let mut max = heap.peek_mut().unwrap();
155 *max = -1;
156
157 // The PeekMut object's Drop impl would have been responsible for moving the
158 // -1 out of the max position of the BinaryHeap, but we don't run it.
159 mem::forget(max);
160
161 // Absent some mitigation like leak amplification, the -1 would incorrectly
162 // end up in the last position of the returned Vec, with the rest of the
163 // heap's original contents in front of it in sorted order.
164 let sorted_vec = heap.into_sorted_vec();
165 assert!(sorted_vec.is_sorted(), "{:?}", sorted_vec);
166 }
167
168 #[test]
test_peek_mut_pop()169 fn test_peek_mut_pop() {
170 let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
171 let mut heap = BinaryHeap::from(data);
172 assert_eq!(heap.peek(), Some(&10));
173 {
174 let mut top = heap.peek_mut().unwrap();
175 *top -= 2;
176 assert_eq!(PeekMut::pop(top), 8);
177 }
178 assert_eq!(heap.peek(), Some(&9));
179 }
180
181 #[test]
test_push()182 fn test_push() {
183 let mut heap = BinaryHeap::from(vec![2, 4, 9]);
184 assert_eq!(heap.len(), 3);
185 assert!(*heap.peek().unwrap() == 9);
186 heap.push(11);
187 assert_eq!(heap.len(), 4);
188 assert!(*heap.peek().unwrap() == 11);
189 heap.push(5);
190 assert_eq!(heap.len(), 5);
191 assert!(*heap.peek().unwrap() == 11);
192 heap.push(27);
193 assert_eq!(heap.len(), 6);
194 assert!(*heap.peek().unwrap() == 27);
195 heap.push(3);
196 assert_eq!(heap.len(), 7);
197 assert!(*heap.peek().unwrap() == 27);
198 heap.push(103);
199 assert_eq!(heap.len(), 8);
200 assert!(*heap.peek().unwrap() == 103);
201 }
202
203 #[test]
test_push_unique()204 fn test_push_unique() {
205 let mut heap = BinaryHeap::<Box<_>>::from(vec![Box::new(2), Box::new(4), Box::new(9)]);
206 assert_eq!(heap.len(), 3);
207 assert!(**heap.peek().unwrap() == 9);
208 heap.push(Box::new(11));
209 assert_eq!(heap.len(), 4);
210 assert!(**heap.peek().unwrap() == 11);
211 heap.push(Box::new(5));
212 assert_eq!(heap.len(), 5);
213 assert!(**heap.peek().unwrap() == 11);
214 heap.push(Box::new(27));
215 assert_eq!(heap.len(), 6);
216 assert!(**heap.peek().unwrap() == 27);
217 heap.push(Box::new(3));
218 assert_eq!(heap.len(), 7);
219 assert!(**heap.peek().unwrap() == 27);
220 heap.push(Box::new(103));
221 assert_eq!(heap.len(), 8);
222 assert!(**heap.peek().unwrap() == 103);
223 }
224
check_to_vec(mut data: Vec<i32>)225 fn check_to_vec(mut data: Vec<i32>) {
226 let heap = BinaryHeap::from(data.clone());
227 let mut v = heap.clone().into_vec();
228 v.sort();
229 data.sort();
230
231 assert_eq!(v, data);
232 assert_eq!(heap.into_sorted_vec(), data);
233 }
234
235 #[test]
test_to_vec()236 fn test_to_vec() {
237 check_to_vec(vec![]);
238 check_to_vec(vec![5]);
239 check_to_vec(vec![3, 2]);
240 check_to_vec(vec![2, 3]);
241 check_to_vec(vec![5, 1, 2]);
242 check_to_vec(vec![1, 100, 2, 3]);
243 check_to_vec(vec![1, 3, 5, 7, 9, 2, 4, 6, 8, 0]);
244 check_to_vec(vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]);
245 check_to_vec(vec![9, 11, 9, 9, 9, 9, 11, 2, 3, 4, 11, 9, 0, 0, 0, 0]);
246 check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
247 check_to_vec(vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
248 check_to_vec(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 1, 2]);
249 check_to_vec(vec![5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1]);
250 }
251
252 #[test]
test_in_place_iterator_specialization()253 fn test_in_place_iterator_specialization() {
254 let src: Vec<usize> = vec![1, 2, 3];
255 let src_ptr = src.as_ptr();
256 let heap: BinaryHeap<_> = src.into_iter().map(std::convert::identity).collect();
257 let heap_ptr = heap.iter().next().unwrap() as *const usize;
258 assert_eq!(src_ptr, heap_ptr);
259 let sink: Vec<_> = heap.into_iter().map(std::convert::identity).collect();
260 let sink_ptr = sink.as_ptr();
261 assert_eq!(heap_ptr, sink_ptr);
262 }
263
264 #[test]
test_empty_pop()265 fn test_empty_pop() {
266 let mut heap = BinaryHeap::<i32>::new();
267 assert!(heap.pop().is_none());
268 }
269
270 #[test]
test_empty_peek()271 fn test_empty_peek() {
272 let empty = BinaryHeap::<i32>::new();
273 assert!(empty.peek().is_none());
274 }
275
276 #[test]
test_empty_peek_mut()277 fn test_empty_peek_mut() {
278 let mut empty = BinaryHeap::<i32>::new();
279 assert!(empty.peek_mut().is_none());
280 }
281
282 #[test]
test_from_iter()283 fn test_from_iter() {
284 let xs = vec![9, 8, 7, 6, 5, 4, 3, 2, 1];
285
286 let mut q: BinaryHeap<_> = xs.iter().rev().cloned().collect();
287
288 for &x in &xs {
289 assert_eq!(q.pop().unwrap(), x);
290 }
291 }
292
293 #[test]
test_drain()294 fn test_drain() {
295 let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
296
297 assert_eq!(q.drain().take(5).count(), 5);
298
299 assert!(q.is_empty());
300 }
301
302 #[test]
test_drain_sorted()303 fn test_drain_sorted() {
304 let mut q: BinaryHeap<_> = [9, 8, 7, 6, 5, 4, 3, 2, 1].iter().cloned().collect();
305
306 assert_eq!(q.drain_sorted().take(5).collect::<Vec<_>>(), vec![9, 8, 7, 6, 5]);
307
308 assert!(q.is_empty());
309 }
310
311 #[test]
312 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
test_drain_sorted_leak()313 fn test_drain_sorted_leak() {
314 let d0 = CrashTestDummy::new(0);
315 let d1 = CrashTestDummy::new(1);
316 let d2 = CrashTestDummy::new(2);
317 let d3 = CrashTestDummy::new(3);
318 let d4 = CrashTestDummy::new(4);
319 let d5 = CrashTestDummy::new(5);
320 let mut q = BinaryHeap::from(vec![
321 d0.spawn(Panic::Never),
322 d1.spawn(Panic::Never),
323 d2.spawn(Panic::Never),
324 d3.spawn(Panic::InDrop),
325 d4.spawn(Panic::Never),
326 d5.spawn(Panic::Never),
327 ]);
328
329 catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).unwrap_err();
330
331 assert_eq!(d0.dropped(), 1);
332 assert_eq!(d1.dropped(), 1);
333 assert_eq!(d2.dropped(), 1);
334 assert_eq!(d3.dropped(), 1);
335 assert_eq!(d4.dropped(), 1);
336 assert_eq!(d5.dropped(), 1);
337 assert!(q.is_empty());
338 }
339
340 #[test]
test_drain_forget()341 fn test_drain_forget() {
342 let a = CrashTestDummy::new(0);
343 let b = CrashTestDummy::new(1);
344 let c = CrashTestDummy::new(2);
345 let mut q =
346 BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]);
347
348 catch_unwind(AssertUnwindSafe(|| {
349 let mut it = q.drain();
350 it.next();
351 mem::forget(it);
352 }))
353 .unwrap();
354 // Behaviour after leaking is explicitly unspecified and order is arbitrary,
355 // so it's fine if these start failing, but probably worth knowing.
356 assert!(q.is_empty());
357 assert_eq!(a.dropped() + b.dropped() + c.dropped(), 1);
358 assert_eq!(a.dropped(), 0);
359 assert_eq!(b.dropped(), 0);
360 assert_eq!(c.dropped(), 1);
361 drop(q);
362 assert_eq!(a.dropped(), 0);
363 assert_eq!(b.dropped(), 0);
364 assert_eq!(c.dropped(), 1);
365 }
366
367 #[test]
test_drain_sorted_forget()368 fn test_drain_sorted_forget() {
369 let a = CrashTestDummy::new(0);
370 let b = CrashTestDummy::new(1);
371 let c = CrashTestDummy::new(2);
372 let mut q =
373 BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]);
374
375 catch_unwind(AssertUnwindSafe(|| {
376 let mut it = q.drain_sorted();
377 it.next();
378 mem::forget(it);
379 }))
380 .unwrap();
381 // Behaviour after leaking is explicitly unspecified,
382 // so it's fine if these start failing, but probably worth knowing.
383 assert_eq!(q.len(), 2);
384 assert_eq!(a.dropped(), 0);
385 assert_eq!(b.dropped(), 0);
386 assert_eq!(c.dropped(), 1);
387 drop(q);
388 assert_eq!(a.dropped(), 1);
389 assert_eq!(b.dropped(), 1);
390 assert_eq!(c.dropped(), 1);
391 }
392
393 #[test]
test_extend_ref()394 fn test_extend_ref() {
395 let mut a = BinaryHeap::new();
396 a.push(1);
397 a.push(2);
398
399 a.extend(&[3, 4, 5]);
400
401 assert_eq!(a.len(), 5);
402 assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
403
404 let mut a = BinaryHeap::new();
405 a.push(1);
406 a.push(2);
407 let mut b = BinaryHeap::new();
408 b.push(3);
409 b.push(4);
410 b.push(5);
411
412 a.extend(&b);
413
414 assert_eq!(a.len(), 5);
415 assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
416 }
417
418 #[test]
test_append()419 fn test_append() {
420 let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
421 let mut b = BinaryHeap::from(vec![-20, 5, 43]);
422
423 a.append(&mut b);
424
425 assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
426 assert!(b.is_empty());
427 }
428
429 #[test]
test_append_to_empty()430 fn test_append_to_empty() {
431 let mut a = BinaryHeap::new();
432 let mut b = BinaryHeap::from(vec![-20, 5, 43]);
433
434 a.append(&mut b);
435
436 assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
437 assert!(b.is_empty());
438 }
439
440 #[test]
test_extend_specialization()441 fn test_extend_specialization() {
442 let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
443 let b = BinaryHeap::from(vec![-20, 5, 43]);
444
445 a.extend(b);
446
447 assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
448 }
449
450 #[allow(dead_code)]
assert_covariance()451 fn assert_covariance() {
452 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
453 d
454 }
455 }
456
457 #[test]
test_retain()458 fn test_retain() {
459 let mut a = BinaryHeap::from(vec![100, 10, 50, 1, 2, 20, 30]);
460 a.retain(|&x| x != 2);
461
462 // Check that 20 moved into 10's place.
463 assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
464
465 a.retain(|_| true);
466
467 assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
468
469 a.retain(|&x| x < 50);
470
471 assert_eq!(a.clone().into_vec(), [30, 20, 10, 1]);
472
473 a.retain(|_| false);
474
475 assert!(a.is_empty());
476 }
477
478 #[test]
479 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
test_retain_catch_unwind()480 fn test_retain_catch_unwind() {
481 let mut heap = BinaryHeap::from(vec![3, 1, 2]);
482
483 // Removes the 3, then unwinds out of retain.
484 let _ = catch_unwind(AssertUnwindSafe(|| {
485 heap.retain(|e| {
486 if *e == 1 {
487 panic!();
488 }
489 false
490 });
491 }));
492
493 // Naively this would be [1, 2] (an invalid heap) if BinaryHeap delegates to
494 // Vec's retain impl and then does not rebuild the heap after that unwinds.
495 assert_eq!(heap.into_vec(), [2, 1]);
496 }
497
498 // old binaryheap failed this test
499 //
500 // Integrity means that all elements are present after a comparison panics,
501 // even if the order might not be correct.
502 //
503 // Destructors must be called exactly once per element.
504 // FIXME: re-enable emscripten once it can unwind again
505 #[test]
506 #[cfg(not(target_os = "emscripten"))]
507 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
panic_safe()508 fn panic_safe() {
509 use rand::seq::SliceRandom;
510 use std::cmp;
511 use std::panic::{self, AssertUnwindSafe};
512 use std::sync::atomic::{AtomicUsize, Ordering};
513
514 static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
515
516 #[derive(Eq, PartialEq, Ord, Clone, Debug)]
517 struct PanicOrd<T>(T, bool);
518
519 impl<T> Drop for PanicOrd<T> {
520 fn drop(&mut self) {
521 // update global drop count
522 DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
523 }
524 }
525
526 impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
527 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
528 if self.1 || other.1 {
529 panic!("Panicking comparison");
530 }
531 self.0.partial_cmp(&other.0)
532 }
533 }
534 let mut rng = crate::test_helpers::test_rng();
535 const DATASZ: usize = 32;
536 // Miri is too slow
537 let ntest = if cfg!(miri) { 1 } else { 10 };
538
539 // don't use 0 in the data -- we want to catch the zeroed-out case.
540 let data = (1..=DATASZ).collect::<Vec<_>>();
541
542 // since it's a fuzzy test, run several tries.
543 for _ in 0..ntest {
544 for i in 1..=DATASZ {
545 DROP_COUNTER.store(0, Ordering::SeqCst);
546
547 let mut panic_ords: Vec<_> =
548 data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect();
549 let panic_item = PanicOrd(i, true);
550
551 // heapify the sane items
552 panic_ords.shuffle(&mut rng);
553 let mut heap = BinaryHeap::from(panic_ords);
554 let inner_data;
555
556 {
557 // push the panicking item to the heap and catch the panic
558 let thread_result = {
559 let mut heap_ref = AssertUnwindSafe(&mut heap);
560 panic::catch_unwind(move || {
561 heap_ref.push(panic_item);
562 })
563 };
564 assert!(thread_result.is_err());
565
566 // Assert no elements were dropped
567 let drops = DROP_COUNTER.load(Ordering::SeqCst);
568 assert!(drops == 0, "Must not drop items. drops={}", drops);
569 inner_data = heap.clone().into_vec();
570 drop(heap);
571 }
572 let drops = DROP_COUNTER.load(Ordering::SeqCst);
573 assert_eq!(drops, DATASZ);
574
575 let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
576 data_sorted.sort();
577 assert_eq!(data_sorted, data);
578 }
579 }
580 }
581