library/alloc/src/collections/binary_heap/tests.rs

   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]
   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]
  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]
  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]
  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]
  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]
  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]
  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
  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]
  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
 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]
 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]
 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]
 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]
 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]
 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]
 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]
 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
 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]
 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]
 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]
 265 fn test_empty_pop() {
 266     let mut heap = BinaryHeap::<i32>::new();
 267     assert!(heap.pop().is_none());
 268 }
 269
 270 #[test]
 271 fn test_empty_peek() {
 272     let empty = BinaryHeap::<i32>::new();
 273     assert!(empty.peek().is_none());
 274 }
 275
 276 #[test]
 277 fn test_empty_peek_mut() {
 278     let mut empty = BinaryHeap::<i32>::new();
 279     assert!(empty.peek_mut().is_none());
 280 }
 281
 282 #[test]
 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]
 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]
 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 fn test_drain_sorted_leak() {
 313     let d0 = CrashTestDummy::new(0);
 314     let d1 = CrashTestDummy::new(1);
 315     let d2 = CrashTestDummy::new(2);
 316     let d3 = CrashTestDummy::new(3);
 317     let d4 = CrashTestDummy::new(4);
 318     let d5 = CrashTestDummy::new(5);
 319     let mut q = BinaryHeap::from(vec![
 320         d0.spawn(Panic::Never),
 321         d1.spawn(Panic::Never),
 322         d2.spawn(Panic::Never),
 323         d3.spawn(Panic::InDrop),
 324         d4.spawn(Panic::Never),
 325         d5.spawn(Panic::Never),
 326     ]);
 327
 328     catch_unwind(AssertUnwindSafe(|| drop(q.drain_sorted()))).unwrap_err();
 329
 330     assert_eq!(d0.dropped(), 1);
 331     assert_eq!(d1.dropped(), 1);
 332     assert_eq!(d2.dropped(), 1);
 333     assert_eq!(d3.dropped(), 1);
 334     assert_eq!(d4.dropped(), 1);
 335     assert_eq!(d5.dropped(), 1);
 336     assert!(q.is_empty());
 337 }
 338
 339 #[test]
 340 fn test_drain_forget() {
 341     let a = CrashTestDummy::new(0);
 342     let b = CrashTestDummy::new(1);
 343     let c = CrashTestDummy::new(2);
 344     let mut q =
 345         BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]);
 346
 347     catch_unwind(AssertUnwindSafe(|| {
 348         let mut it = q.drain();
 349         it.next();
 350         mem::forget(it);
 351     }))
 352     .unwrap();
 353     // Behaviour after leaking is explicitly unspecified and order is arbitrary,
 354     // so it's fine if these start failing, but probably worth knowing.
 355     assert!(q.is_empty());
 356     assert_eq!(a.dropped() + b.dropped() + c.dropped(), 1);
 357     assert_eq!(a.dropped(), 0);
 358     assert_eq!(b.dropped(), 0);
 359     assert_eq!(c.dropped(), 1);
 360     drop(q);
 361     assert_eq!(a.dropped(), 0);
 362     assert_eq!(b.dropped(), 0);
 363     assert_eq!(c.dropped(), 1);
 364 }
 365
 366 #[test]
 367 fn test_drain_sorted_forget() {
 368     let a = CrashTestDummy::new(0);
 369     let b = CrashTestDummy::new(1);
 370     let c = CrashTestDummy::new(2);
 371     let mut q =
 372         BinaryHeap::from(vec![a.spawn(Panic::Never), b.spawn(Panic::Never), c.spawn(Panic::Never)]);
 373
 374     catch_unwind(AssertUnwindSafe(|| {
 375         let mut it = q.drain_sorted();
 376         it.next();
 377         mem::forget(it);
 378     }))
 379     .unwrap();
 380     // Behaviour after leaking is explicitly unspecified,
 381     // so it's fine if these start failing, but probably worth knowing.
 382     assert_eq!(q.len(), 2);
 383     assert_eq!(a.dropped(), 0);
 384     assert_eq!(b.dropped(), 0);
 385     assert_eq!(c.dropped(), 1);
 386     drop(q);
 387     assert_eq!(a.dropped(), 1);
 388     assert_eq!(b.dropped(), 1);
 389     assert_eq!(c.dropped(), 1);
 390 }
 391
 392 #[test]
 393 fn test_extend_ref() {
 394     let mut a = BinaryHeap::new();
 395     a.push(1);
 396     a.push(2);
 397
 398     a.extend(&[3, 4, 5]);
 399
 400     assert_eq!(a.len(), 5);
 401     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 402
 403     let mut a = BinaryHeap::new();
 404     a.push(1);
 405     a.push(2);
 406     let mut b = BinaryHeap::new();
 407     b.push(3);
 408     b.push(4);
 409     b.push(5);
 410
 411     a.extend(&b);
 412
 413     assert_eq!(a.len(), 5);
 414     assert_eq!(a.into_sorted_vec(), [1, 2, 3, 4, 5]);
 415 }
 416
 417 #[test]
 418 fn test_append() {
 419     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 420     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 421
 422     a.append(&mut b);
 423
 424     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 425     assert!(b.is_empty());
 426 }
 427
 428 #[test]
 429 fn test_append_to_empty() {
 430     let mut a = BinaryHeap::new();
 431     let mut b = BinaryHeap::from(vec![-20, 5, 43]);
 432
 433     a.append(&mut b);
 434
 435     assert_eq!(a.into_sorted_vec(), [-20, 5, 43]);
 436     assert!(b.is_empty());
 437 }
 438
 439 #[test]
 440 fn test_extend_specialization() {
 441     let mut a = BinaryHeap::from(vec![-10, 1, 2, 3, 3]);
 442     let b = BinaryHeap::from(vec![-20, 5, 43]);
 443
 444     a.extend(b);
 445
 446     assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
 447 }
 448
 449 #[allow(dead_code)]
 450 fn assert_covariance() {
 451     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 452         d
 453     }
 454 }
 455
 456 #[test]
 457 fn test_retain() {
 458     let mut a = BinaryHeap::from(vec![100, 10, 50, 1, 2, 20, 30]);
 459     a.retain(|&x| x != 2);
 460
 461     // Check that 20 moved into 10's place.
 462     assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
 463
 464     a.retain(|_| true);
 465
 466     assert_eq!(a.clone().into_vec(), [100, 20, 50, 1, 10, 30]);
 467
 468     a.retain(|&x| x < 50);
 469
 470     assert_eq!(a.clone().into_vec(), [30, 20, 10, 1]);
 471
 472     a.retain(|_| false);
 473
 474     assert!(a.is_empty());
 475 }
 476
 477 // old binaryheap failed this test
 478 //
 479 // Integrity means that all elements are present after a comparison panics,
 480 // even if the order might not be correct.
 481 //
 482 // Destructors must be called exactly once per element.
 483 // FIXME: re-enable emscripten once it can unwind again
 484 #[test]
 485 #[cfg(not(target_os = "emscripten"))]
 486 fn panic_safe() {
 487     use rand::seq::SliceRandom;
 488     use std::cmp;
 489     use std::panic::{self, AssertUnwindSafe};
 490     use std::sync::atomic::{AtomicUsize, Ordering};
 491
 492     static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0);
 493
 494     #[derive(Eq, PartialEq, Ord, Clone, Debug)]
 495     struct PanicOrd<T>(T, bool);
 496
 497     impl<T> Drop for PanicOrd<T> {
 498         fn drop(&mut self) {
 499             // update global drop count
 500             DROP_COUNTER.fetch_add(1, Ordering::SeqCst);
 501         }
 502     }
 503
 504     impl<T: PartialOrd> PartialOrd for PanicOrd<T> {
 505         fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
 506             if self.1 || other.1 {
 507                 panic!("Panicking comparison");
 508             }
 509             self.0.partial_cmp(&other.0)
 510         }
 511     }
 512     let mut rng = crate::test_helpers::test_rng();
 513     const DATASZ: usize = 32;
 514     // Miri is too slow
 515     let ntest = if cfg!(miri) { 1 } else { 10 };
 516
 517     // don't use 0 in the data -- we want to catch the zeroed-out case.
 518     let data = (1..=DATASZ).collect::<Vec<_>>();
 519
 520     // since it's a fuzzy test, run several tries.
 521     for _ in 0..ntest {
 522         for i in 1..=DATASZ {
 523             DROP_COUNTER.store(0, Ordering::SeqCst);
 524
 525             let mut panic_ords: Vec<_> =
 526                 data.iter().filter(|&&x| x != i).map(|&x| PanicOrd(x, false)).collect();
 527             let panic_item = PanicOrd(i, true);
 528
 529             // heapify the sane items
 530             panic_ords.shuffle(&mut rng);
 531             let mut heap = BinaryHeap::from(panic_ords);
 532             let inner_data;
 533
 534             {
 535                 // push the panicking item to the heap and catch the panic
 536                 let thread_result = {
 537                     let mut heap_ref = AssertUnwindSafe(&mut heap);
 538                     panic::catch_unwind(move || {
 539                         heap_ref.push(panic_item);
 540                     })
 541                 };
 542                 assert!(thread_result.is_err());
 543
 544                 // Assert no elements were dropped
 545                 let drops = DROP_COUNTER.load(Ordering::SeqCst);
 546                 assert!(drops == 0, "Must not drop items. drops={}", drops);
 547                 inner_data = heap.clone().into_vec();
 548                 drop(heap);
 549             }
 550             let drops = DROP_COUNTER.load(Ordering::SeqCst);
 551             assert_eq!(drops, DATASZ);
 552
 553             let mut data_sorted = inner_data.into_iter().map(|p| p.0).collect::<Vec<_>>();
 554             data_sorted.sort();
 555             assert_eq!(data_sorted, data);
 556         }
 557     }
 558 }