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

   1 use super::*;
   2
   3 #[bench]
   4 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
   5 fn bench_push_back_100(b: &mut test::Bencher) {
   6     let mut deq = VecDeque::with_capacity(101);
   7     b.iter(|| {
   8         for i in 0..100 {
   9             deq.push_back(i);
  10         }
  11         deq.head = 0;
  12         deq.tail = 0;
  13     })
  14 }
  15
  16 #[bench]
  17 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
  18 fn bench_push_front_100(b: &mut test::Bencher) {
  19     let mut deq = VecDeque::with_capacity(101);
  20     b.iter(|| {
  21         for i in 0..100 {
  22             deq.push_front(i);
  23         }
  24         deq.head = 0;
  25         deq.tail = 0;
  26     })
  27 }
  28
  29 #[bench]
  30 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
  31 fn bench_pop_back_100(b: &mut test::Bencher) {
  32     let mut deq = VecDeque::<i32>::with_capacity(101);
  33
  34     b.iter(|| {
  35         deq.head = 100;
  36         deq.tail = 0;
  37         while !deq.is_empty() {
  38             test::black_box(deq.pop_back());
  39         }
  40     })
  41 }
  42
  43 #[bench]
  44 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
  45 fn bench_pop_front_100(b: &mut test::Bencher) {
  46     let mut deq = VecDeque::<i32>::with_capacity(101);
  47
  48     b.iter(|| {
  49         deq.head = 100;
  50         deq.tail = 0;
  51         while !deq.is_empty() {
  52             test::black_box(deq.pop_front());
  53         }
  54     })
  55 }
  56
  57 #[test]
  58 fn test_swap_front_back_remove() {
  59     fn test(back: bool) {
  60         // This test checks that every single combination of tail position and length is tested.
  61         // Capacity 15 should be large enough to cover every case.
  62         let mut tester = VecDeque::with_capacity(15);
  63         let usable_cap = tester.capacity();
  64         let final_len = usable_cap / 2;
  65
  66         for len in 0..final_len {
  67             let expected: VecDeque<_> =
  68                 if back { (0..len).collect() } else { (0..len).rev().collect() };
  69             for tail_pos in 0..usable_cap {
  70                 tester.tail = tail_pos;
  71                 tester.head = tail_pos;
  72                 if back {
  73                     for i in 0..len * 2 {
  74                         tester.push_front(i);
  75                     }
  76                     for i in 0..len {
  77                         assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i));
  78                     }
  79                 } else {
  80                     for i in 0..len * 2 {
  81                         tester.push_back(i);
  82                     }
  83                     for i in 0..len {
  84                         let idx = tester.len() - 1 - i;
  85                         assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
  86                     }
  87                 }
  88                 assert!(tester.tail < tester.cap());
  89                 assert!(tester.head < tester.cap());
  90                 assert_eq!(tester, expected);
  91             }
  92         }
  93     }
  94     test(true);
  95     test(false);
  96 }
  97
  98 #[test]
  99 fn test_insert() {
 100     // This test checks that every single combination of tail position, length, and
 101     // insertion position is tested. Capacity 15 should be large enough to cover every case.
 102
 103     let mut tester = VecDeque::with_capacity(15);
 104     // can't guarantee we got 15, so have to get what we got.
 105     // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
 106     // this test isn't covering what it wants to
 107     let cap = tester.capacity();
 108
 109     // len is the length *after* insertion
 110     let minlen = if cfg!(miri) { cap - 1 } else { 1 }; // Miri is too slow
 111     for len in minlen..cap {
 112         // 0, 1, 2, .., len - 1
 113         let expected = (0..).take(len).collect::<VecDeque<_>>();
 114         for tail_pos in 0..cap {
 115             for to_insert in 0..len {
 116                 tester.tail = tail_pos;
 117                 tester.head = tail_pos;
 118                 for i in 0..len {
 119                     if i != to_insert {
 120                         tester.push_back(i);
 121                     }
 122                 }
 123                 tester.insert(to_insert, to_insert);
 124                 assert!(tester.tail < tester.cap());
 125                 assert!(tester.head < tester.cap());
 126                 assert_eq!(tester, expected);
 127             }
 128         }
 129     }
 130 }
 131
 132 #[test]
 133 fn make_contiguous_big_tail() {
 134     let mut tester = VecDeque::with_capacity(15);
 135
 136     for i in 0..3 {
 137         tester.push_back(i);
 138     }
 139
 140     for i in 3..10 {
 141         tester.push_front(i);
 142     }
 143
 144     // 012......9876543
 145     assert_eq!(tester.capacity(), 15);
 146     assert_eq!((&[9, 8, 7, 6, 5, 4, 3] as &[_], &[0, 1, 2] as &[_]), tester.as_slices());
 147
 148     let expected_start = tester.head;
 149     tester.make_contiguous();
 150     assert_eq!(tester.tail, expected_start);
 151     assert_eq!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_], &[] as &[_]), tester.as_slices());
 152 }
 153
 154 #[test]
 155 fn make_contiguous_big_head() {
 156     let mut tester = VecDeque::with_capacity(15);
 157
 158     for i in 0..8 {
 159         tester.push_back(i);
 160     }
 161
 162     for i in 8..10 {
 163         tester.push_front(i);
 164     }
 165
 166     // 01234567......98
 167     let expected_start = 0;
 168     tester.make_contiguous();
 169     assert_eq!(tester.tail, expected_start);
 170     assert_eq!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_], &[] as &[_]), tester.as_slices());
 171 }
 172
 173 #[test]
 174 fn make_contiguous_small_free() {
 175     let mut tester = VecDeque::with_capacity(15);
 176
 177     for i in 'A' as u8..'I' as u8 {
 178         tester.push_back(i as char);
 179     }
 180
 181     for i in 'I' as u8..'N' as u8 {
 182         tester.push_front(i as char);
 183     }
 184
 185     // ABCDEFGH...MLKJI
 186     let expected_start = 0;
 187     tester.make_contiguous();
 188     assert_eq!(tester.tail, expected_start);
 189     assert_eq!(
 190         (&['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] as &[_], &[] as &[_]),
 191         tester.as_slices()
 192     );
 193
 194     tester.clear();
 195     for i in 'I' as u8..'N' as u8 {
 196         tester.push_back(i as char);
 197     }
 198
 199     for i in 'A' as u8..'I' as u8 {
 200         tester.push_front(i as char);
 201     }
 202
 203     // IJKLM...HGFEDCBA
 204     let expected_start = 0;
 205     tester.make_contiguous();
 206     assert_eq!(tester.tail, expected_start);
 207     assert_eq!(
 208         (&['H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'J', 'K', 'L', 'M'] as &[_], &[] as &[_]),
 209         tester.as_slices()
 210     );
 211 }
 212
 213 #[test]
 214 fn make_contiguous_head_to_end() {
 215     let mut dq = VecDeque::with_capacity(3);
 216     dq.push_front('B');
 217     dq.push_front('A');
 218     dq.push_back('C');
 219     dq.make_contiguous();
 220     let expected_tail = 0;
 221     let expected_head = 3;
 222     assert_eq!(expected_tail, dq.tail);
 223     assert_eq!(expected_head, dq.head);
 224     assert_eq!((&['A', 'B', 'C'] as &[_], &[] as &[_]), dq.as_slices());
 225 }
 226
 227 #[test]
 228 fn make_contiguous_head_to_end_2() {
 229     // Another test case for #79808, taken from #80293.
 230
 231     let mut dq = VecDeque::from_iter(0..6);
 232     dq.pop_front();
 233     dq.pop_front();
 234     dq.push_back(6);
 235     dq.push_back(7);
 236     dq.push_back(8);
 237     dq.make_contiguous();
 238     let collected: Vec<_> = dq.iter().copied().collect();
 239     assert_eq!(dq.as_slices(), (&collected[..], &[] as &[_]));
 240 }
 241
 242 #[test]
 243 fn test_remove() {
 244     // This test checks that every single combination of tail position, length, and
 245     // removal position is tested. Capacity 15 should be large enough to cover every case.
 246
 247     let mut tester = VecDeque::with_capacity(15);
 248     // can't guarantee we got 15, so have to get what we got.
 249     // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
 250     // this test isn't covering what it wants to
 251     let cap = tester.capacity();
 252
 253     // len is the length *after* removal
 254     let minlen = if cfg!(miri) { cap - 2 } else { 0 }; // Miri is too slow
 255     for len in minlen..cap - 1 {
 256         // 0, 1, 2, .., len - 1
 257         let expected = (0..).take(len).collect::<VecDeque<_>>();
 258         for tail_pos in 0..cap {
 259             for to_remove in 0..=len {
 260                 tester.tail = tail_pos;
 261                 tester.head = tail_pos;
 262                 for i in 0..len {
 263                     if i == to_remove {
 264                         tester.push_back(1234);
 265                     }
 266                     tester.push_back(i);
 267                 }
 268                 if to_remove == len {
 269                     tester.push_back(1234);
 270                 }
 271                 tester.remove(to_remove);
 272                 assert!(tester.tail < tester.cap());
 273                 assert!(tester.head < tester.cap());
 274                 assert_eq!(tester, expected);
 275             }
 276         }
 277     }
 278 }
 279
 280 #[test]
 281 fn test_range() {
 282     let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
 283
 284     let cap = tester.capacity();
 285     let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
 286     for len in minlen..=cap {
 287         for tail in 0..=cap {
 288             for start in 0..=len {
 289                 for end in start..=len {
 290                     tester.tail = tail;
 291                     tester.head = tail;
 292                     for i in 0..len {
 293                         tester.push_back(i);
 294                     }
 295
 296                     // Check that we iterate over the correct values
 297                     let range: VecDeque<_> = tester.range(start..end).copied().collect();
 298                     let expected: VecDeque<_> = (start..end).collect();
 299                     assert_eq!(range, expected);
 300                 }
 301             }
 302         }
 303     }
 304 }
 305
 306 #[test]
 307 fn test_range_mut() {
 308     let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
 309
 310     let cap = tester.capacity();
 311     for len in 0..=cap {
 312         for tail in 0..=cap {
 313             for start in 0..=len {
 314                 for end in start..=len {
 315                     tester.tail = tail;
 316                     tester.head = tail;
 317                     for i in 0..len {
 318                         tester.push_back(i);
 319                     }
 320
 321                     let head_was = tester.head;
 322                     let tail_was = tester.tail;
 323
 324                     // Check that we iterate over the correct values
 325                     let range: VecDeque<_> = tester.range_mut(start..end).map(|v| *v).collect();
 326                     let expected: VecDeque<_> = (start..end).collect();
 327                     assert_eq!(range, expected);
 328
 329                     // We shouldn't have changed the capacity or made the
 330                     // head or tail out of bounds
 331                     assert_eq!(tester.capacity(), cap);
 332                     assert_eq!(tester.tail, tail_was);
 333                     assert_eq!(tester.head, head_was);
 334                 }
 335             }
 336         }
 337     }
 338 }
 339
 340 #[test]
 341 fn test_drain() {
 342     let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
 343
 344     let cap = tester.capacity();
 345     for len in 0..=cap {
 346         for tail in 0..=cap {
 347             for drain_start in 0..=len {
 348                 for drain_end in drain_start..=len {
 349                     tester.tail = tail;
 350                     tester.head = tail;
 351                     for i in 0..len {
 352                         tester.push_back(i);
 353                     }
 354
 355                     // Check that we drain the correct values
 356                     let drained: VecDeque<_> = tester.drain(drain_start..drain_end).collect();
 357                     let drained_expected: VecDeque<_> = (drain_start..drain_end).collect();
 358                     assert_eq!(drained, drained_expected);
 359
 360                     // We shouldn't have changed the capacity or made the
 361                     // head or tail out of bounds
 362                     assert_eq!(tester.capacity(), cap);
 363                     assert!(tester.tail < tester.cap());
 364                     assert!(tester.head < tester.cap());
 365
 366                     // We should see the correct values in the VecDeque
 367                     let expected: VecDeque<_> = (0..drain_start).chain(drain_end..len).collect();
 368                     assert_eq!(expected, tester);
 369                 }
 370             }
 371         }
 372     }
 373 }
 374
 375 #[test]
 376 fn test_shrink_to_fit() {
 377     // This test checks that every single combination of head and tail position,
 378     // is tested. Capacity 15 should be large enough to cover every case.
 379
 380     let mut tester = VecDeque::with_capacity(15);
 381     // can't guarantee we got 15, so have to get what we got.
 382     // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
 383     // this test isn't covering what it wants to
 384     let cap = tester.capacity();
 385     tester.reserve(63);
 386     let max_cap = tester.capacity();
 387
 388     for len in 0..=cap {
 389         // 0, 1, 2, .., len - 1
 390         let expected = (0..).take(len).collect::<VecDeque<_>>();
 391         for tail_pos in 0..=max_cap {
 392             tester.tail = tail_pos;
 393             tester.head = tail_pos;
 394             tester.reserve(63);
 395             for i in 0..len {
 396                 tester.push_back(i);
 397             }
 398             tester.shrink_to_fit();
 399             assert!(tester.capacity() <= cap);
 400             assert!(tester.tail < tester.cap());
 401             assert!(tester.head < tester.cap());
 402             assert_eq!(tester, expected);
 403         }
 404     }
 405 }
 406
 407 #[test]
 408 fn test_split_off() {
 409     // This test checks that every single combination of tail position, length, and
 410     // split position is tested. Capacity 15 should be large enough to cover every case.
 411
 412     let mut tester = VecDeque::with_capacity(15);
 413     // can't guarantee we got 15, so have to get what we got.
 414     // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
 415     // this test isn't covering what it wants to
 416     let cap = tester.capacity();
 417
 418     // len is the length *before* splitting
 419     let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
 420     for len in minlen..cap {
 421         // index to split at
 422         for at in 0..=len {
 423             // 0, 1, 2, .., at - 1 (may be empty)
 424             let expected_self = (0..).take(at).collect::<VecDeque<_>>();
 425             // at, at + 1, .., len - 1 (may be empty)
 426             let expected_other = (at..).take(len - at).collect::<VecDeque<_>>();
 427
 428             for tail_pos in 0..cap {
 429                 tester.tail = tail_pos;
 430                 tester.head = tail_pos;
 431                 for i in 0..len {
 432                     tester.push_back(i);
 433                 }
 434                 let result = tester.split_off(at);
 435                 assert!(tester.tail < tester.cap());
 436                 assert!(tester.head < tester.cap());
 437                 assert!(result.tail < result.cap());
 438                 assert!(result.head < result.cap());
 439                 assert_eq!(tester, expected_self);
 440                 assert_eq!(result, expected_other);
 441             }
 442         }
 443     }
 444 }
 445
 446 #[test]
 447 fn test_from_vec() {
 448     use crate::vec::Vec;
 449     for cap in 0..35 {
 450         for len in 0..=cap {
 451             let mut vec = Vec::with_capacity(cap);
 452             vec.extend(0..len);
 453
 454             let vd = VecDeque::from(vec.clone());
 455             assert!(vd.cap().is_power_of_two());
 456             assert_eq!(vd.len(), vec.len());
 457             assert!(vd.into_iter().eq(vec));
 458         }
 459     }
 460
 461     let vec = Vec::from([(); MAXIMUM_ZST_CAPACITY - 1]);
 462     let vd = VecDeque::from(vec.clone());
 463     assert!(vd.cap().is_power_of_two());
 464     assert_eq!(vd.len(), vec.len());
 465 }
 466
 467 #[test]
 468 #[should_panic = "capacity overflow"]
 469 fn test_from_vec_zst_overflow() {
 470     use crate::vec::Vec;
 471     let vec = Vec::from([(); MAXIMUM_ZST_CAPACITY]);
 472     let vd = VecDeque::from(vec.clone()); // no room for +1
 473     assert!(vd.cap().is_power_of_two());
 474     assert_eq!(vd.len(), vec.len());
 475 }
 476
 477 #[test]
 478 fn test_vec_from_vecdeque() {
 479     use crate::vec::Vec;
 480
 481     fn create_vec_and_test_convert(capacity: usize, offset: usize, len: usize) {
 482         let mut vd = VecDeque::with_capacity(capacity);
 483         for _ in 0..offset {
 484             vd.push_back(0);
 485             vd.pop_front();
 486         }
 487         vd.extend(0..len);
 488
 489         let vec: Vec<_> = Vec::from(vd.clone());
 490         assert_eq!(vec.len(), vd.len());
 491         assert!(vec.into_iter().eq(vd));
 492     }
 493
 494     // Miri is too slow
 495     let max_pwr = if cfg!(miri) { 5 } else { 7 };
 496
 497     for cap_pwr in 0..max_pwr {
 498         // Make capacity as a (2^x)-1, so that the ring size is 2^x
 499         let cap = (2i32.pow(cap_pwr) - 1) as usize;
 500
 501         // In these cases there is enough free space to solve it with copies
 502         for len in 0..((cap + 1) / 2) {
 503             // Test contiguous cases
 504             for offset in 0..(cap - len) {
 505                 create_vec_and_test_convert(cap, offset, len)
 506             }
 507
 508             // Test cases where block at end of buffer is bigger than block at start
 509             for offset in (cap - len)..(cap - (len / 2)) {
 510                 create_vec_and_test_convert(cap, offset, len)
 511             }
 512
 513             // Test cases where block at start of buffer is bigger than block at end
 514             for offset in (cap - (len / 2))..cap {
 515                 create_vec_and_test_convert(cap, offset, len)
 516             }
 517         }
 518
 519         // Now there's not (necessarily) space to straighten the ring with simple copies,
 520         // the ring will use swapping when:
 521         // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
 522         //  right block size  >   free space    &&      left block size       >    free space
 523         for len in ((cap + 1) / 2)..cap {
 524             // Test contiguous cases
 525             for offset in 0..(cap - len) {
 526                 create_vec_and_test_convert(cap, offset, len)
 527             }
 528
 529             // Test cases where block at end of buffer is bigger than block at start
 530             for offset in (cap - len)..(cap - (len / 2)) {
 531                 create_vec_and_test_convert(cap, offset, len)
 532             }
 533
 534             // Test cases where block at start of buffer is bigger than block at end
 535             for offset in (cap - (len / 2))..cap {
 536                 create_vec_and_test_convert(cap, offset, len)
 537             }
 538         }
 539     }
 540 }
 541
 542 #[test]
 543 fn test_clone_from() {
 544     let m = vec![1; 8];
 545     let n = vec![2; 12];
 546     let limit = if cfg!(miri) { 4 } else { 8 }; // Miri is too slow
 547     for pfv in 0..limit {
 548         for pfu in 0..limit {
 549             for longer in 0..2 {
 550                 let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) };
 551                 let mut v = VecDeque::from(vr.clone());
 552                 for _ in 0..pfv {
 553                     v.push_front(1);
 554                 }
 555                 let mut u = VecDeque::from(ur.clone());
 556                 for _ in 0..pfu {
 557                     u.push_front(2);
 558                 }
 559                 v.clone_from(&u);
 560                 assert_eq!(&v, &u);
 561             }
 562         }
 563     }
 564 }
 565
 566 #[test]
 567 fn test_vec_deque_truncate_drop() {
 568     static mut DROPS: u32 = 0;
 569     #[derive(Clone)]
 570     struct Elem(i32);
 571     impl Drop for Elem {
 572         fn drop(&mut self) {
 573             unsafe {
 574                 DROPS += 1;
 575             }
 576         }
 577     }
 578
 579     let v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
 580     for push_front in 0..=v.len() {
 581         let v = v.clone();
 582         let mut tester = VecDeque::with_capacity(5);
 583         for (index, elem) in v.into_iter().enumerate() {
 584             if index < push_front {
 585                 tester.push_front(elem);
 586             } else {
 587                 tester.push_back(elem);
 588             }
 589         }
 590         assert_eq!(unsafe { DROPS }, 0);
 591         tester.truncate(3);
 592         assert_eq!(unsafe { DROPS }, 2);
 593         tester.truncate(0);
 594         assert_eq!(unsafe { DROPS }, 5);
 595         unsafe {
 596             DROPS = 0;
 597         }
 598     }
 599 }
 600
 601 #[test]
 602 fn issue_53529() {
 603     use crate::boxed::Box;
 604
 605     let mut dst = VecDeque::new();
 606     dst.push_front(Box::new(1));
 607     dst.push_front(Box::new(2));
 608     assert_eq!(*dst.pop_back().unwrap(), 1);
 609
 610     let mut src = VecDeque::new();
 611     src.push_front(Box::new(2));
 612     dst.append(&mut src);
 613     for a in dst {
 614         assert_eq!(*a, 2);
 615     }
 616 }
 617
 618 #[test]
 619 fn issue_80303() {
 620     use core::iter;
 621     use core::num::Wrapping;
 622
 623     // This is a valid, albeit rather bad hash function implementation.
 624     struct SimpleHasher(Wrapping<u64>);
 625
 626     impl Hasher for SimpleHasher {
 627         fn finish(&self) -> u64 {
 628             self.0.0
 629         }
 630
 631         fn write(&mut self, bytes: &[u8]) {
 632             // This particular implementation hashes value 24 in addition to bytes.
 633             // Such an implementation is valid as Hasher only guarantees equivalence
 634             // for the exact same set of calls to its methods.
 635             for &v in iter::once(&24).chain(bytes) {
 636                 self.0 = Wrapping(31) * self.0 + Wrapping(u64::from(v));
 637             }
 638         }
 639     }
 640
 641     fn hash_code(value: impl Hash) -> u64 {
 642         let mut hasher = SimpleHasher(Wrapping(1));
 643         value.hash(&mut hasher);
 644         hasher.finish()
 645     }
 646
 647     // This creates two deques for which values returned by as_slices
 648     // method differ.
 649     let vda: VecDeque<u8> = (0..10).collect();
 650     let mut vdb = VecDeque::with_capacity(10);
 651     vdb.extend(5..10);
 652     (0..5).rev().for_each(|elem| vdb.push_front(elem));
 653     assert_ne!(vda.as_slices(), vdb.as_slices());
 654     assert_eq!(vda, vdb);
 655     assert_eq!(hash_code(vda), hash_code(vdb));
 656 }