library/alloc/tests/vec_deque.rs

   1 use std::assert_matches::assert_matches;
   2 use std::collections::TryReserveErrorKind::*;
   3 use std::collections::{vec_deque::Drain, VecDeque};
   4 use std::fmt::Debug;
   5 use std::mem::size_of;
   6 use std::ops::Bound::*;
   7 use std::panic::{catch_unwind, AssertUnwindSafe};
   8
   9 use crate::hash;
  10
  11 use Taggy::*;
  12 use Taggypar::*;
  13
  14 #[test]
  15 fn test_simple() {
  16     let mut d = VecDeque::new();
  17     assert_eq!(d.len(), 0);
  18     d.push_front(17);
  19     d.push_front(42);
  20     d.push_back(137);
  21     assert_eq!(d.len(), 3);
  22     d.push_back(137);
  23     assert_eq!(d.len(), 4);
  24     assert_eq!(*d.front().unwrap(), 42);
  25     assert_eq!(*d.back().unwrap(), 137);
  26     let mut i = d.pop_front();
  27     assert_eq!(i, Some(42));
  28     i = d.pop_back();
  29     assert_eq!(i, Some(137));
  30     i = d.pop_back();
  31     assert_eq!(i, Some(137));
  32     i = d.pop_back();
  33     assert_eq!(i, Some(17));
  34     assert_eq!(d.len(), 0);
  35     d.push_back(3);
  36     assert_eq!(d.len(), 1);
  37     d.push_front(2);
  38     assert_eq!(d.len(), 2);
  39     d.push_back(4);
  40     assert_eq!(d.len(), 3);
  41     d.push_front(1);
  42     assert_eq!(d.len(), 4);
  43     assert_eq!(d[0], 1);
  44     assert_eq!(d[1], 2);
  45     assert_eq!(d[2], 3);
  46     assert_eq!(d[3], 4);
  47 }
  48
  49 fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
  50     let mut deq = VecDeque::new();
  51     assert_eq!(deq.len(), 0);
  52     deq.push_front(a.clone());
  53     deq.push_front(b.clone());
  54     deq.push_back(c.clone());
  55     assert_eq!(deq.len(), 3);
  56     deq.push_back(d.clone());
  57     assert_eq!(deq.len(), 4);
  58     assert_eq!((*deq.front().unwrap()).clone(), b.clone());
  59     assert_eq!((*deq.back().unwrap()).clone(), d.clone());
  60     assert_eq!(deq.pop_front().unwrap(), b.clone());
  61     assert_eq!(deq.pop_back().unwrap(), d.clone());
  62     assert_eq!(deq.pop_back().unwrap(), c.clone());
  63     assert_eq!(deq.pop_back().unwrap(), a.clone());
  64     assert_eq!(deq.len(), 0);
  65     deq.push_back(c.clone());
  66     assert_eq!(deq.len(), 1);
  67     deq.push_front(b.clone());
  68     assert_eq!(deq.len(), 2);
  69     deq.push_back(d.clone());
  70     assert_eq!(deq.len(), 3);
  71     deq.push_front(a.clone());
  72     assert_eq!(deq.len(), 4);
  73     assert_eq!(deq[0].clone(), a.clone());
  74     assert_eq!(deq[1].clone(), b.clone());
  75     assert_eq!(deq[2].clone(), c.clone());
  76     assert_eq!(deq[3].clone(), d.clone());
  77 }
  78
  79 #[test]
  80 fn test_push_front_grow() {
  81     let mut deq = VecDeque::new();
  82     for i in 0..66 {
  83         deq.push_front(i);
  84     }
  85     assert_eq!(deq.len(), 66);
  86
  87     for i in 0..66 {
  88         assert_eq!(deq[i], 65 - i);
  89     }
  90
  91     let mut deq = VecDeque::new();
  92     for i in 0..66 {
  93         deq.push_back(i);
  94     }
  95
  96     for i in 0..66 {
  97         assert_eq!(deq[i], i);
  98     }
  99 }
 100
 101 #[test]
 102 fn test_index() {
 103     let mut deq = VecDeque::new();
 104     for i in 1..4 {
 105         deq.push_front(i);
 106     }
 107     assert_eq!(deq[1], 2);
 108 }
 109
 110 #[test]
 111 #[should_panic]
 112 fn test_index_out_of_bounds() {
 113     let mut deq = VecDeque::new();
 114     for i in 1..4 {
 115         deq.push_front(i);
 116     }
 117     deq[3];
 118 }
 119
 120 #[test]
 121 #[should_panic]
 122 fn test_range_start_overflow() {
 123     let deq = VecDeque::from(vec![1, 2, 3]);
 124     deq.range((Included(0), Included(usize::MAX)));
 125 }
 126
 127 #[test]
 128 #[should_panic]
 129 fn test_range_end_overflow() {
 130     let deq = VecDeque::from(vec![1, 2, 3]);
 131     deq.range((Excluded(usize::MAX), Included(0)));
 132 }
 133
 134 #[derive(Clone, PartialEq, Debug)]
 135 enum Taggy {
 136     One(i32),
 137     Two(i32, i32),
 138     Three(i32, i32, i32),
 139 }
 140
 141 #[derive(Clone, PartialEq, Debug)]
 142 enum Taggypar<T> {
 143     Onepar(T),
 144     Twopar(T, T),
 145     Threepar(T, T, T),
 146 }
 147
 148 #[derive(Clone, PartialEq, Debug)]
 149 struct RecCy {
 150     x: i32,
 151     y: i32,
 152     t: Taggy,
 153 }
 154
 155 #[test]
 156 fn test_param_int() {
 157     test_parameterized::<i32>(5, 72, 64, 175);
 158 }
 159
 160 #[test]
 161 fn test_param_taggy() {
 162     test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
 163 }
 164
 165 #[test]
 166 fn test_param_taggypar() {
 167     test_parameterized::<Taggypar<i32>>(
 168         Onepar::<i32>(1),
 169         Twopar::<i32>(1, 2),
 170         Threepar::<i32>(1, 2, 3),
 171         Twopar::<i32>(17, 42),
 172     );
 173 }
 174
 175 #[test]
 176 fn test_param_reccy() {
 177     let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
 178     let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
 179     let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
 180     let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
 181     test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
 182 }
 183
 184 #[test]
 185 fn test_with_capacity() {
 186     let mut d = VecDeque::with_capacity(0);
 187     d.push_back(1);
 188     assert_eq!(d.len(), 1);
 189     let mut d = VecDeque::with_capacity(50);
 190     d.push_back(1);
 191     assert_eq!(d.len(), 1);
 192 }
 193
 194 #[test]
 195 fn test_with_capacity_non_power_two() {
 196     let mut d3 = VecDeque::with_capacity(3);
 197     d3.push_back(1);
 198
 199     // X = None, | = lo
 200     // [|1, X, X]
 201     assert_eq!(d3.pop_front(), Some(1));
 202     // [X, |X, X]
 203     assert_eq!(d3.front(), None);
 204
 205     // [X, |3, X]
 206     d3.push_back(3);
 207     // [X, |3, 6]
 208     d3.push_back(6);
 209     // [X, X, |6]
 210     assert_eq!(d3.pop_front(), Some(3));
 211
 212     // Pushing the lo past half way point to trigger
 213     // the 'B' scenario for growth
 214     // [9, X, |6]
 215     d3.push_back(9);
 216     // [9, 12, |6]
 217     d3.push_back(12);
 218
 219     d3.push_back(15);
 220     // There used to be a bug here about how the
 221     // VecDeque made growth assumptions about the
 222     // underlying Vec which didn't hold and lead
 223     // to corruption.
 224     // (Vec grows to next power of two)
 225     // good- [9, 12, 15, X, X, X, X, |6]
 226     // bug-  [15, 12, X, X, X, |6, X, X]
 227     assert_eq!(d3.pop_front(), Some(6));
 228
 229     // Which leads us to the following state which
 230     // would be a failure case.
 231     // bug-  [15, 12, X, X, X, X, |X, X]
 232     assert_eq!(d3.front(), Some(&9));
 233 }
 234
 235 #[test]
 236 fn test_reserve_exact() {
 237     let mut d = VecDeque::new();
 238     d.push_back(0);
 239     d.reserve_exact(50);
 240     assert!(d.capacity() >= 51);
 241 }
 242
 243 #[test]
 244 fn test_reserve() {
 245     let mut d = VecDeque::new();
 246     d.push_back(0);
 247     d.reserve(50);
 248     assert!(d.capacity() >= 51);
 249 }
 250
 251 #[test]
 252 fn test_swap() {
 253     let mut d: VecDeque<_> = (0..5).collect();
 254     d.pop_front();
 255     d.swap(0, 3);
 256     assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]);
 257 }
 258
 259 #[test]
 260 fn test_iter() {
 261     let mut d = VecDeque::new();
 262     assert_eq!(d.iter().next(), None);
 263     assert_eq!(d.iter().size_hint(), (0, Some(0)));
 264
 265     for i in 0..5 {
 266         d.push_back(i);
 267     }
 268     {
 269         let b: &[_] = &[&0, &1, &2, &3, &4];
 270         assert_eq!(d.iter().collect::<Vec<_>>(), b);
 271     }
 272
 273     for i in 6..9 {
 274         d.push_front(i);
 275     }
 276     {
 277         let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4];
 278         assert_eq!(d.iter().collect::<Vec<_>>(), b);
 279     }
 280
 281     let mut it = d.iter();
 282     let mut len = d.len();
 283     loop {
 284         match it.next() {
 285             None => break,
 286             _ => {
 287                 len -= 1;
 288                 assert_eq!(it.size_hint(), (len, Some(len)))
 289             }
 290         }
 291     }
 292 }
 293
 294 #[test]
 295 fn test_rev_iter() {
 296     let mut d = VecDeque::new();
 297     assert_eq!(d.iter().rev().next(), None);
 298
 299     for i in 0..5 {
 300         d.push_back(i);
 301     }
 302     {
 303         let b: &[_] = &[&4, &3, &2, &1, &0];
 304         assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
 305     }
 306
 307     for i in 6..9 {
 308         d.push_front(i);
 309     }
 310     let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8];
 311     assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
 312 }
 313
 314 #[test]
 315 fn test_mut_rev_iter_wrap() {
 316     let mut d = VecDeque::with_capacity(3);
 317     assert!(d.iter_mut().rev().next().is_none());
 318
 319     d.push_back(1);
 320     d.push_back(2);
 321     d.push_back(3);
 322     assert_eq!(d.pop_front(), Some(1));
 323     d.push_back(4);
 324
 325     assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), vec![4, 3, 2]);
 326 }
 327
 328 #[test]
 329 fn test_mut_iter() {
 330     let mut d = VecDeque::new();
 331     assert!(d.iter_mut().next().is_none());
 332
 333     for i in 0..3 {
 334         d.push_front(i);
 335     }
 336
 337     for (i, elt) in d.iter_mut().enumerate() {
 338         assert_eq!(*elt, 2 - i);
 339         *elt = i;
 340     }
 341
 342     {
 343         let mut it = d.iter_mut();
 344         assert_eq!(*it.next().unwrap(), 0);
 345         assert_eq!(*it.next().unwrap(), 1);
 346         assert_eq!(*it.next().unwrap(), 2);
 347         assert!(it.next().is_none());
 348     }
 349 }
 350
 351 #[test]
 352 fn test_mut_rev_iter() {
 353     let mut d = VecDeque::new();
 354     assert!(d.iter_mut().rev().next().is_none());
 355
 356     for i in 0..3 {
 357         d.push_front(i);
 358     }
 359
 360     for (i, elt) in d.iter_mut().rev().enumerate() {
 361         assert_eq!(*elt, i);
 362         *elt = i;
 363     }
 364
 365     {
 366         let mut it = d.iter_mut().rev();
 367         assert_eq!(*it.next().unwrap(), 0);
 368         assert_eq!(*it.next().unwrap(), 1);
 369         assert_eq!(*it.next().unwrap(), 2);
 370         assert!(it.next().is_none());
 371     }
 372 }
 373
 374 #[test]
 375 fn test_into_iter() {
 376     // Empty iter
 377     {
 378         let d: VecDeque<i32> = VecDeque::new();
 379         let mut iter = d.into_iter();
 380
 381         assert_eq!(iter.size_hint(), (0, Some(0)));
 382         assert_eq!(iter.next(), None);
 383         assert_eq!(iter.size_hint(), (0, Some(0)));
 384     }
 385
 386     // simple iter
 387     {
 388         let mut d = VecDeque::new();
 389         for i in 0..5 {
 390             d.push_back(i);
 391         }
 392
 393         let b = vec![0, 1, 2, 3, 4];
 394         assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
 395     }
 396
 397     // wrapped iter
 398     {
 399         let mut d = VecDeque::new();
 400         for i in 0..5 {
 401             d.push_back(i);
 402         }
 403         for i in 6..9 {
 404             d.push_front(i);
 405         }
 406
 407         let b = vec![8, 7, 6, 0, 1, 2, 3, 4];
 408         assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
 409     }
 410
 411     // partially used
 412     {
 413         let mut d = VecDeque::new();
 414         for i in 0..5 {
 415             d.push_back(i);
 416         }
 417         for i in 6..9 {
 418             d.push_front(i);
 419         }
 420
 421         let mut it = d.into_iter();
 422         assert_eq!(it.size_hint(), (8, Some(8)));
 423         assert_eq!(it.next(), Some(8));
 424         assert_eq!(it.size_hint(), (7, Some(7)));
 425         assert_eq!(it.next_back(), Some(4));
 426         assert_eq!(it.size_hint(), (6, Some(6)));
 427         assert_eq!(it.next(), Some(7));
 428         assert_eq!(it.size_hint(), (5, Some(5)));
 429     }
 430 }
 431
 432 #[test]
 433 fn test_drain() {
 434     // Empty iter
 435     {
 436         let mut d: VecDeque<i32> = VecDeque::new();
 437
 438         {
 439             let mut iter = d.drain(..);
 440
 441             assert_eq!(iter.size_hint(), (0, Some(0)));
 442             assert_eq!(iter.next(), None);
 443             assert_eq!(iter.size_hint(), (0, Some(0)));
 444         }
 445
 446         assert!(d.is_empty());
 447     }
 448
 449     // simple iter
 450     {
 451         let mut d = VecDeque::new();
 452         for i in 0..5 {
 453             d.push_back(i);
 454         }
 455
 456         assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
 457         assert!(d.is_empty());
 458     }
 459
 460     // wrapped iter
 461     {
 462         let mut d = VecDeque::new();
 463         for i in 0..5 {
 464             d.push_back(i);
 465         }
 466         for i in 6..9 {
 467             d.push_front(i);
 468         }
 469
 470         assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
 471         assert!(d.is_empty());
 472     }
 473
 474     // partially used
 475     {
 476         let mut d: VecDeque<_> = VecDeque::new();
 477         for i in 0..5 {
 478             d.push_back(i);
 479         }
 480         for i in 6..9 {
 481             d.push_front(i);
 482         }
 483
 484         {
 485             let mut it = d.drain(..);
 486             assert_eq!(it.size_hint(), (8, Some(8)));
 487             assert_eq!(it.next(), Some(8));
 488             assert_eq!(it.size_hint(), (7, Some(7)));
 489             assert_eq!(it.next_back(), Some(4));
 490             assert_eq!(it.size_hint(), (6, Some(6)));
 491             assert_eq!(it.next(), Some(7));
 492             assert_eq!(it.size_hint(), (5, Some(5)));
 493         }
 494         assert!(d.is_empty());
 495     }
 496 }
 497
 498 #[test]
 499 fn test_from_iter() {
 500     let v = vec![1, 2, 3, 4, 5, 6, 7];
 501     let deq: VecDeque<_> = v.iter().cloned().collect();
 502     let u: Vec<_> = deq.iter().cloned().collect();
 503     assert_eq!(u, v);
 504
 505     let seq = (0..).step_by(2).take(256);
 506     let deq: VecDeque<_> = seq.collect();
 507     for (i, &x) in deq.iter().enumerate() {
 508         assert_eq!(2 * i, x);
 509     }
 510     assert_eq!(deq.len(), 256);
 511 }
 512
 513 #[test]
 514 fn test_clone() {
 515     let mut d = VecDeque::new();
 516     d.push_front(17);
 517     d.push_front(42);
 518     d.push_back(137);
 519     d.push_back(137);
 520     assert_eq!(d.len(), 4);
 521     let mut e = d.clone();
 522     assert_eq!(e.len(), 4);
 523     while !d.is_empty() {
 524         assert_eq!(d.pop_back(), e.pop_back());
 525     }
 526     assert_eq!(d.len(), 0);
 527     assert_eq!(e.len(), 0);
 528 }
 529
 530 #[test]
 531 fn test_eq() {
 532     let mut d = VecDeque::new();
 533     assert!(d == VecDeque::with_capacity(0));
 534     d.push_front(137);
 535     d.push_front(17);
 536     d.push_front(42);
 537     d.push_back(137);
 538     let mut e = VecDeque::with_capacity(0);
 539     e.push_back(42);
 540     e.push_back(17);
 541     e.push_back(137);
 542     e.push_back(137);
 543     assert!(&e == &d);
 544     e.pop_back();
 545     e.push_back(0);
 546     assert!(e != d);
 547     e.clear();
 548     assert!(e == VecDeque::new());
 549 }
 550
 551 #[test]
 552 fn test_partial_eq_array() {
 553     let d = VecDeque::<char>::new();
 554     assert!(d == []);
 555
 556     let mut d = VecDeque::new();
 557     d.push_front('a');
 558     assert!(d == ['a']);
 559
 560     let mut d = VecDeque::new();
 561     d.push_back('a');
 562     assert!(d == ['a']);
 563
 564     let mut d = VecDeque::new();
 565     d.push_back('a');
 566     d.push_back('b');
 567     assert!(d == ['a', 'b']);
 568 }
 569
 570 #[test]
 571 fn test_hash() {
 572     let mut x = VecDeque::new();
 573     let mut y = VecDeque::new();
 574
 575     x.push_back(1);
 576     x.push_back(2);
 577     x.push_back(3);
 578
 579     y.push_back(0);
 580     y.push_back(1);
 581     y.pop_front();
 582     y.push_back(2);
 583     y.push_back(3);
 584
 585     assert!(hash(&x) == hash(&y));
 586 }
 587
 588 #[test]
 589 fn test_hash_after_rotation() {
 590     // test that two deques hash equal even if elements are laid out differently
 591     let len = 28;
 592     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 593     let orig = ring.clone();
 594     for _ in 0..ring.capacity() {
 595         // shift values 1 step to the right by pop, sub one, push
 596         ring.pop_front();
 597         for elt in &mut ring {
 598             *elt -= 1;
 599         }
 600         ring.push_back(len - 1);
 601         assert_eq!(hash(&orig), hash(&ring));
 602         assert_eq!(orig, ring);
 603         assert_eq!(ring, orig);
 604     }
 605 }
 606
 607 #[test]
 608 fn test_eq_after_rotation() {
 609     // test that two deques are equal even if elements are laid out differently
 610     let len = 28;
 611     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 612     let mut shifted = ring.clone();
 613     for _ in 0..10 {
 614         // shift values 1 step to the right by pop, sub one, push
 615         ring.pop_front();
 616         for elt in &mut ring {
 617             *elt -= 1;
 618         }
 619         ring.push_back(len - 1);
 620     }
 621
 622     // try every shift
 623     for _ in 0..shifted.capacity() {
 624         shifted.pop_front();
 625         for elt in &mut shifted {
 626             *elt -= 1;
 627         }
 628         shifted.push_back(len - 1);
 629         assert_eq!(shifted, ring);
 630         assert_eq!(ring, shifted);
 631     }
 632 }
 633
 634 #[test]
 635 fn test_ord() {
 636     let x = VecDeque::new();
 637     let mut y = VecDeque::new();
 638     y.push_back(1);
 639     y.push_back(2);
 640     y.push_back(3);
 641     assert!(x < y);
 642     assert!(y > x);
 643     assert!(x <= x);
 644     assert!(x >= x);
 645 }
 646
 647 #[test]
 648 fn test_show() {
 649     let ringbuf: VecDeque<_> = (0..10).collect();
 650     assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 651
 652     let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
 653     assert_eq!(format!("{:?}", ringbuf), "[\"just\", \"one\", \"test\", \"more\"]");
 654 }
 655
 656 #[test]
 657 fn test_drop() {
 658     static mut DROPS: i32 = 0;
 659     struct Elem;
 660     impl Drop for Elem {
 661         fn drop(&mut self) {
 662             unsafe {
 663                 DROPS += 1;
 664             }
 665         }
 666     }
 667
 668     let mut ring = VecDeque::new();
 669     ring.push_back(Elem);
 670     ring.push_front(Elem);
 671     ring.push_back(Elem);
 672     ring.push_front(Elem);
 673     drop(ring);
 674
 675     assert_eq!(unsafe { DROPS }, 4);
 676 }
 677
 678 #[test]
 679 fn test_drop_with_pop() {
 680     static mut DROPS: i32 = 0;
 681     struct Elem;
 682     impl Drop for Elem {
 683         fn drop(&mut self) {
 684             unsafe {
 685                 DROPS += 1;
 686             }
 687         }
 688     }
 689
 690     let mut ring = VecDeque::new();
 691     ring.push_back(Elem);
 692     ring.push_front(Elem);
 693     ring.push_back(Elem);
 694     ring.push_front(Elem);
 695
 696     drop(ring.pop_back());
 697     drop(ring.pop_front());
 698     assert_eq!(unsafe { DROPS }, 2);
 699
 700     drop(ring);
 701     assert_eq!(unsafe { DROPS }, 4);
 702 }
 703
 704 #[test]
 705 fn test_drop_clear() {
 706     static mut DROPS: i32 = 0;
 707     struct Elem;
 708     impl Drop for Elem {
 709         fn drop(&mut self) {
 710             unsafe {
 711                 DROPS += 1;
 712             }
 713         }
 714     }
 715
 716     let mut ring = VecDeque::new();
 717     ring.push_back(Elem);
 718     ring.push_front(Elem);
 719     ring.push_back(Elem);
 720     ring.push_front(Elem);
 721     ring.clear();
 722     assert_eq!(unsafe { DROPS }, 4);
 723
 724     drop(ring);
 725     assert_eq!(unsafe { DROPS }, 4);
 726 }
 727
 728 #[test]
 729 fn test_drop_panic() {
 730     static mut DROPS: i32 = 0;
 731
 732     struct D(bool);
 733
 734     impl Drop for D {
 735         fn drop(&mut self) {
 736             unsafe {
 737                 DROPS += 1;
 738             }
 739
 740             if self.0 {
 741                 panic!("panic in `drop`");
 742             }
 743         }
 744     }
 745
 746     let mut q = VecDeque::new();
 747     q.push_back(D(false));
 748     q.push_back(D(false));
 749     q.push_back(D(false));
 750     q.push_back(D(false));
 751     q.push_back(D(false));
 752     q.push_front(D(false));
 753     q.push_front(D(false));
 754     q.push_front(D(true));
 755
 756     catch_unwind(move || drop(q)).ok();
 757
 758     assert_eq!(unsafe { DROPS }, 8);
 759 }
 760
 761 #[test]
 762 fn test_reserve_grow() {
 763     // test growth path A
 764     // [T o o H] -> [T o o H . . . . ]
 765     let mut ring = VecDeque::with_capacity(4);
 766     for i in 0..3 {
 767         ring.push_back(i);
 768     }
 769     ring.reserve(7);
 770     for i in 0..3 {
 771         assert_eq!(ring.pop_front(), Some(i));
 772     }
 773
 774     // test growth path B
 775     // [H T o o] -> [. T o o H . . . ]
 776     let mut ring = VecDeque::with_capacity(4);
 777     for i in 0..1 {
 778         ring.push_back(i);
 779         assert_eq!(ring.pop_front(), Some(i));
 780     }
 781     for i in 0..3 {
 782         ring.push_back(i);
 783     }
 784     ring.reserve(7);
 785     for i in 0..3 {
 786         assert_eq!(ring.pop_front(), Some(i));
 787     }
 788
 789     // test growth path C
 790     // [o o H T] -> [o o H . . . . T ]
 791     let mut ring = VecDeque::with_capacity(4);
 792     for i in 0..3 {
 793         ring.push_back(i);
 794         assert_eq!(ring.pop_front(), Some(i));
 795     }
 796     for i in 0..3 {
 797         ring.push_back(i);
 798     }
 799     ring.reserve(7);
 800     for i in 0..3 {
 801         assert_eq!(ring.pop_front(), Some(i));
 802     }
 803 }
 804
 805 #[test]
 806 fn test_get() {
 807     let mut ring = VecDeque::new();
 808     ring.push_back(0);
 809     assert_eq!(ring.get(0), Some(&0));
 810     assert_eq!(ring.get(1), None);
 811
 812     ring.push_back(1);
 813     assert_eq!(ring.get(0), Some(&0));
 814     assert_eq!(ring.get(1), Some(&1));
 815     assert_eq!(ring.get(2), None);
 816
 817     ring.push_back(2);
 818     assert_eq!(ring.get(0), Some(&0));
 819     assert_eq!(ring.get(1), Some(&1));
 820     assert_eq!(ring.get(2), Some(&2));
 821     assert_eq!(ring.get(3), None);
 822
 823     assert_eq!(ring.pop_front(), Some(0));
 824     assert_eq!(ring.get(0), Some(&1));
 825     assert_eq!(ring.get(1), Some(&2));
 826     assert_eq!(ring.get(2), None);
 827
 828     assert_eq!(ring.pop_front(), Some(1));
 829     assert_eq!(ring.get(0), Some(&2));
 830     assert_eq!(ring.get(1), None);
 831
 832     assert_eq!(ring.pop_front(), Some(2));
 833     assert_eq!(ring.get(0), None);
 834     assert_eq!(ring.get(1), None);
 835 }
 836
 837 #[test]
 838 fn test_get_mut() {
 839     let mut ring = VecDeque::new();
 840     for i in 0..3 {
 841         ring.push_back(i);
 842     }
 843
 844     match ring.get_mut(1) {
 845         Some(x) => *x = -1,
 846         None => (),
 847     };
 848
 849     assert_eq!(ring.get_mut(0), Some(&mut 0));
 850     assert_eq!(ring.get_mut(1), Some(&mut -1));
 851     assert_eq!(ring.get_mut(2), Some(&mut 2));
 852     assert_eq!(ring.get_mut(3), None);
 853
 854     assert_eq!(ring.pop_front(), Some(0));
 855     assert_eq!(ring.get_mut(0), Some(&mut -1));
 856     assert_eq!(ring.get_mut(1), Some(&mut 2));
 857     assert_eq!(ring.get_mut(2), None);
 858 }
 859
 860 #[test]
 861 fn test_front() {
 862     let mut ring = VecDeque::new();
 863     ring.push_back(10);
 864     ring.push_back(20);
 865     assert_eq!(ring.front(), Some(&10));
 866     ring.pop_front();
 867     assert_eq!(ring.front(), Some(&20));
 868     ring.pop_front();
 869     assert_eq!(ring.front(), None);
 870 }
 871
 872 #[test]
 873 fn test_as_slices() {
 874     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 875     let cap = ring.capacity() as i32;
 876     let first = cap / 2;
 877     let last = cap - first;
 878     for i in 0..first {
 879         ring.push_back(i);
 880
 881         let (left, right) = ring.as_slices();
 882         let expected: Vec<_> = (0..=i).collect();
 883         assert_eq!(left, &expected[..]);
 884         assert_eq!(right, []);
 885     }
 886
 887     for j in -last..0 {
 888         ring.push_front(j);
 889         let (left, right) = ring.as_slices();
 890         let expected_left: Vec<_> = (-last..=j).rev().collect();
 891         let expected_right: Vec<_> = (0..first).collect();
 892         assert_eq!(left, &expected_left[..]);
 893         assert_eq!(right, &expected_right[..]);
 894     }
 895
 896     assert_eq!(ring.len() as i32, cap);
 897     assert_eq!(ring.capacity() as i32, cap);
 898 }
 899
 900 #[test]
 901 fn test_as_mut_slices() {
 902     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 903     let cap = ring.capacity() as i32;
 904     let first = cap / 2;
 905     let last = cap - first;
 906     for i in 0..first {
 907         ring.push_back(i);
 908
 909         let (left, right) = ring.as_mut_slices();
 910         let expected: Vec<_> = (0..=i).collect();
 911         assert_eq!(left, &expected[..]);
 912         assert_eq!(right, []);
 913     }
 914
 915     for j in -last..0 {
 916         ring.push_front(j);
 917         let (left, right) = ring.as_mut_slices();
 918         let expected_left: Vec<_> = (-last..=j).rev().collect();
 919         let expected_right: Vec<_> = (0..first).collect();
 920         assert_eq!(left, &expected_left[..]);
 921         assert_eq!(right, &expected_right[..]);
 922     }
 923
 924     assert_eq!(ring.len() as i32, cap);
 925     assert_eq!(ring.capacity() as i32, cap);
 926 }
 927
 928 #[test]
 929 fn test_append() {
 930     let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
 931     let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
 932
 933     // normal append
 934     a.append(&mut b);
 935     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 936     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
 937
 938     // append nothing to something
 939     a.append(&mut b);
 940     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 941     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
 942
 943     // append something to nothing
 944     b.append(&mut a);
 945     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 946     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
 947 }
 948
 949 #[test]
 950 fn test_append_permutations() {
 951     fn construct_vec_deque(
 952         push_back: usize,
 953         pop_back: usize,
 954         push_front: usize,
 955         pop_front: usize,
 956     ) -> VecDeque<usize> {
 957         let mut out = VecDeque::new();
 958         for a in 0..push_back {
 959             out.push_back(a);
 960         }
 961         for b in 0..push_front {
 962             out.push_front(push_back + b);
 963         }
 964         for _ in 0..pop_back {
 965             out.pop_back();
 966         }
 967         for _ in 0..pop_front {
 968             out.pop_front();
 969         }
 970         out
 971     }
 972
 973     // Miri is too slow
 974     let max = if cfg!(miri) { 3 } else { 5 };
 975
 976     // Many different permutations of both the `VecDeque` getting appended to
 977     // and the one getting appended are generated to check `append`.
 978     // This ensures all 6 code paths of `append` are tested.
 979     for src_push_back in 0..max {
 980         for src_push_front in 0..max {
 981             // doesn't pop more values than are pushed
 982             for src_pop_back in 0..(src_push_back + src_push_front) {
 983                 for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) {
 984                     let src = construct_vec_deque(
 985                         src_push_back,
 986                         src_pop_back,
 987                         src_push_front,
 988                         src_pop_front,
 989                     );
 990
 991                     for dst_push_back in 0..max {
 992                         for dst_push_front in 0..max {
 993                             for dst_pop_back in 0..(dst_push_back + dst_push_front) {
 994                                 for dst_pop_front in
 995                                     0..(dst_push_back + dst_push_front - dst_pop_back)
 996                                 {
 997                                     let mut dst = construct_vec_deque(
 998                                         dst_push_back,
 999                                         dst_pop_back,
1000                                         dst_push_front,
1001                                         dst_pop_front,
1002                                     );
1003                                     let mut src = src.clone();
1004
1005                                     // Assert that appending `src` to `dst` gives the same order
1006                                     // of values as iterating over both in sequence.
1007                                     let correct = dst
1008                                         .iter()
1009                                         .chain(src.iter())
1010                                         .cloned()
1011                                         .collect::<Vec<usize>>();
1012                                     dst.append(&mut src);
1013                                     assert_eq!(dst, correct);
1014                                     assert!(src.is_empty());
1015                                 }
1016                             }
1017                         }
1018                     }
1019                 }
1020             }
1021         }
1022     }
1023 }
1024
1025 struct DropCounter<'a> {
1026     count: &'a mut u32,
1027 }
1028
1029 impl Drop for DropCounter<'_> {
1030     fn drop(&mut self) {
1031         *self.count += 1;
1032     }
1033 }
1034
1035 #[test]
1036 fn test_append_double_drop() {
1037     let (mut count_a, mut count_b) = (0, 0);
1038     {
1039         let mut a = VecDeque::new();
1040         let mut b = VecDeque::new();
1041         a.push_back(DropCounter { count: &mut count_a });
1042         b.push_back(DropCounter { count: &mut count_b });
1043
1044         a.append(&mut b);
1045     }
1046     assert_eq!(count_a, 1);
1047     assert_eq!(count_b, 1);
1048 }
1049
1050 #[test]
1051 fn test_retain() {
1052     let mut buf = VecDeque::new();
1053     buf.extend(1..5);
1054     buf.retain(|&x| x % 2 == 0);
1055     let v: Vec<_> = buf.into_iter().collect();
1056     assert_eq!(&v[..], &[2, 4]);
1057 }
1058
1059 #[test]
1060 fn test_extend_ref() {
1061     let mut v = VecDeque::new();
1062     v.push_back(1);
1063     v.extend(&[2, 3, 4]);
1064
1065     assert_eq!(v.len(), 4);
1066     assert_eq!(v[0], 1);
1067     assert_eq!(v[1], 2);
1068     assert_eq!(v[2], 3);
1069     assert_eq!(v[3], 4);
1070
1071     let mut w = VecDeque::new();
1072     w.push_back(5);
1073     w.push_back(6);
1074     v.extend(&w);
1075
1076     assert_eq!(v.len(), 6);
1077     assert_eq!(v[0], 1);
1078     assert_eq!(v[1], 2);
1079     assert_eq!(v[2], 3);
1080     assert_eq!(v[3], 4);
1081     assert_eq!(v[4], 5);
1082     assert_eq!(v[5], 6);
1083 }
1084
1085 #[test]
1086 fn test_contains() {
1087     let mut v = VecDeque::new();
1088     v.extend(&[2, 3, 4]);
1089
1090     assert!(v.contains(&3));
1091     assert!(!v.contains(&1));
1092
1093     v.clear();
1094
1095     assert!(!v.contains(&3));
1096 }
1097
1098 #[allow(dead_code)]
1099 fn assert_covariance() {
1100     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1101         d
1102     }
1103 }
1104
1105 #[test]
1106 fn test_is_empty() {
1107     let mut v = VecDeque::<i32>::new();
1108     assert!(v.is_empty());
1109     assert!(v.iter().is_empty());
1110     assert!(v.iter_mut().is_empty());
1111     v.extend(&[2, 3, 4]);
1112     assert!(!v.is_empty());
1113     assert!(!v.iter().is_empty());
1114     assert!(!v.iter_mut().is_empty());
1115     while let Some(_) = v.pop_front() {
1116         assert_eq!(v.is_empty(), v.len() == 0);
1117         assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
1118         assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
1119     }
1120     assert!(v.is_empty());
1121     assert!(v.iter().is_empty());
1122     assert!(v.iter_mut().is_empty());
1123     assert!(v.into_iter().is_empty());
1124 }
1125
1126 #[test]
1127 fn test_reserve_exact_2() {
1128     // This is all the same as test_reserve
1129
1130     let mut v = VecDeque::new();
1131
1132     v.reserve_exact(2);
1133     assert!(v.capacity() >= 2);
1134
1135     for i in 0..16 {
1136         v.push_back(i);
1137     }
1138
1139     assert!(v.capacity() >= 16);
1140     v.reserve_exact(16);
1141     assert!(v.capacity() >= 32);
1142
1143     v.push_back(16);
1144
1145     v.reserve_exact(16);
1146     assert!(v.capacity() >= 48)
1147 }
1148
1149 #[test]
1150 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1151 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1152 fn test_try_reserve() {
1153     // These are the interesting cases:
1154     // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1155     // * > isize::MAX should always fail
1156     //    * On 16/32-bit should CapacityOverflow
1157     //    * On 64-bit should OOM
1158     // * overflow may trigger when adding `len` to `cap` (in number of elements)
1159     // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1160
1161     const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1162     const MAX_USIZE: usize = usize::MAX;
1163
1164     // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1165     // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1166     // Any platform that succeeds for these requests is technically broken with
1167     // ptr::offset because LLVM is the worst.
1168     let guards_against_isize = size_of::<usize>() < 8;
1169
1170     {
1171         // Note: basic stuff is checked by test_reserve
1172         let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1173
1174         // Check isize::MAX doesn't count as an overflow
1175         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1176             panic!("isize::MAX shouldn't trigger an overflow!");
1177         }
1178         // Play it again, frank! (just to be sure)
1179         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1180             panic!("isize::MAX shouldn't trigger an overflow!");
1181         }
1182
1183         if guards_against_isize {
1184             // Check isize::MAX + 1 does count as overflow
1185             assert_matches!(
1186                 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1187                 Err(CapacityOverflow),
1188                 "isize::MAX + 1 should trigger an overflow!"
1189             );
1190
1191             // Check usize::MAX does count as overflow
1192             assert_matches!(
1193                 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1194                 Err(CapacityOverflow),
1195                 "usize::MAX should trigger an overflow!"
1196             );
1197         } else {
1198             // Check isize::MAX is an OOM
1199             // VecDeque starts with capacity 7, always adds 1 to the capacity
1200             // and also rounds the number to next power of 2 so this is the
1201             // furthest we can go without triggering CapacityOverflow
1202             assert_matches!(
1203                 empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()),
1204                 Err(AllocError { .. }),
1205                 "isize::MAX + 1 should trigger an OOM!"
1206             );
1207         }
1208     }
1209
1210     {
1211         // Same basic idea, but with non-zero len
1212         let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1213
1214         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1215             panic!("isize::MAX shouldn't trigger an overflow!");
1216         }
1217         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1218             panic!("isize::MAX shouldn't trigger an overflow!");
1219         }
1220         if guards_against_isize {
1221             assert_matches!(
1222                 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1223                 Err(CapacityOverflow),
1224                 "isize::MAX + 1 should trigger an overflow!"
1225             );
1226         } else {
1227             assert_matches!(
1228                 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1229                 Err(AllocError { .. }),
1230                 "isize::MAX + 1 should trigger an OOM!"
1231             );
1232         }
1233         // Should always overflow in the add-to-len
1234         assert_matches!(
1235             ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1236             Err(CapacityOverflow),
1237             "usize::MAX should trigger an overflow!"
1238         );
1239     }
1240
1241     {
1242         // Same basic idea, but with interesting type size
1243         let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1244
1245         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1246         {
1247             panic!("isize::MAX shouldn't trigger an overflow!");
1248         }
1249         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1250         {
1251             panic!("isize::MAX shouldn't trigger an overflow!");
1252         }
1253         if guards_against_isize {
1254             assert_matches!(
1255                 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1256                 Err(CapacityOverflow),
1257                 "isize::MAX + 1 should trigger an overflow!"
1258             );
1259         } else {
1260             assert_matches!(
1261                 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1262                 Err(AllocError { .. }),
1263                 "isize::MAX + 1 should trigger an OOM!"
1264             );
1265         }
1266         // Should fail in the mul-by-size
1267         assert_matches!(
1268             ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1269             Err(CapacityOverflow),
1270             "usize::MAX should trigger an overflow!"
1271         );
1272     }
1273 }
1274
1275 #[test]
1276 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1277 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1278 fn test_try_reserve_exact() {
1279     // This is exactly the same as test_try_reserve with the method changed.
1280     // See that test for comments.
1281
1282     const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1283     const MAX_USIZE: usize = usize::MAX;
1284
1285     let guards_against_isize = size_of::<usize>() < 8;
1286
1287     {
1288         let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1289
1290         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1291         {
1292             panic!("isize::MAX shouldn't trigger an overflow!");
1293         }
1294         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1295         {
1296             panic!("isize::MAX shouldn't trigger an overflow!");
1297         }
1298
1299         if guards_against_isize {
1300             assert_matches!(
1301                 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1302                 Err(CapacityOverflow),
1303                 "isize::MAX + 1 should trigger an overflow!"
1304             );
1305
1306             assert_matches!(
1307                 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1308                 Err(CapacityOverflow),
1309                 "usize::MAX should trigger an overflow!"
1310             );
1311         } else {
1312             // Check isize::MAX is an OOM
1313             // VecDeque starts with capacity 7, always adds 1 to the capacity
1314             // and also rounds the number to next power of 2 so this is the
1315             // furthest we can go without triggering CapacityOverflow
1316             assert_matches!(
1317                 empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind()),
1318                 Err(AllocError { .. }),
1319                 "isize::MAX + 1 should trigger an OOM!"
1320             );
1321         }
1322     }
1323
1324     {
1325         let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1326
1327         if let Err(CapacityOverflow) =
1328             ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1329         {
1330             panic!("isize::MAX shouldn't trigger an overflow!");
1331         }
1332         if let Err(CapacityOverflow) =
1333             ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1334         {
1335             panic!("isize::MAX shouldn't trigger an overflow!");
1336         }
1337         if guards_against_isize {
1338             assert_matches!(
1339                 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1340                 Err(CapacityOverflow),
1341                 "isize::MAX + 1 should trigger an overflow!"
1342             );
1343         } else {
1344             assert_matches!(
1345                 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1346                 Err(AllocError { .. }),
1347                 "isize::MAX + 1 should trigger an OOM!"
1348             );
1349         }
1350         assert_matches!(
1351             ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1352             Err(CapacityOverflow),
1353             "usize::MAX should trigger an overflow!"
1354         );
1355     }
1356
1357     {
1358         let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1359
1360         if let Err(CapacityOverflow) =
1361             ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1362         {
1363             panic!("isize::MAX shouldn't trigger an overflow!");
1364         }
1365         if let Err(CapacityOverflow) =
1366             ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1367         {
1368             panic!("isize::MAX shouldn't trigger an overflow!");
1369         }
1370         if guards_against_isize {
1371             assert_matches!(
1372                 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1373                 Err(CapacityOverflow),
1374                 "isize::MAX + 1 should trigger an overflow!"
1375             );
1376         } else {
1377             assert_matches!(
1378                 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1379                 Err(AllocError { .. }),
1380                 "isize::MAX + 1 should trigger an OOM!"
1381             );
1382         }
1383         assert_matches!(
1384             ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1385             Err(CapacityOverflow),
1386             "usize::MAX should trigger an overflow!"
1387         );
1388     }
1389 }
1390
1391 #[test]
1392 fn test_rotate_nop() {
1393     let mut v: VecDeque<_> = (0..10).collect();
1394     assert_unchanged(&v);
1395
1396     v.rotate_left(0);
1397     assert_unchanged(&v);
1398
1399     v.rotate_left(10);
1400     assert_unchanged(&v);
1401
1402     v.rotate_right(0);
1403     assert_unchanged(&v);
1404
1405     v.rotate_right(10);
1406     assert_unchanged(&v);
1407
1408     v.rotate_left(3);
1409     v.rotate_right(3);
1410     assert_unchanged(&v);
1411
1412     v.rotate_right(3);
1413     v.rotate_left(3);
1414     assert_unchanged(&v);
1415
1416     v.rotate_left(6);
1417     v.rotate_right(6);
1418     assert_unchanged(&v);
1419
1420     v.rotate_right(6);
1421     v.rotate_left(6);
1422     assert_unchanged(&v);
1423
1424     v.rotate_left(3);
1425     v.rotate_left(7);
1426     assert_unchanged(&v);
1427
1428     v.rotate_right(4);
1429     v.rotate_right(6);
1430     assert_unchanged(&v);
1431
1432     v.rotate_left(1);
1433     v.rotate_left(2);
1434     v.rotate_left(3);
1435     v.rotate_left(4);
1436     assert_unchanged(&v);
1437
1438     v.rotate_right(1);
1439     v.rotate_right(2);
1440     v.rotate_right(3);
1441     v.rotate_right(4);
1442     assert_unchanged(&v);
1443
1444     fn assert_unchanged(v: &VecDeque<i32>) {
1445         assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1446     }
1447 }
1448
1449 #[test]
1450 fn test_rotate_left_parts() {
1451     let mut v: VecDeque<_> = (1..=7).collect();
1452     v.rotate_left(2);
1453     assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
1454     v.rotate_left(2);
1455     assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
1456     v.rotate_left(2);
1457     assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
1458     v.rotate_left(2);
1459     assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
1460     v.rotate_left(2);
1461     assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
1462     v.rotate_left(2);
1463     assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
1464     v.rotate_left(2);
1465     assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
1466 }
1467
1468 #[test]
1469 fn test_rotate_right_parts() {
1470     let mut v: VecDeque<_> = (1..=7).collect();
1471     v.rotate_right(2);
1472     assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1473     v.rotate_right(2);
1474     assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1475     v.rotate_right(2);
1476     assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1477     v.rotate_right(2);
1478     assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1479     v.rotate_right(2);
1480     assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1481     v.rotate_right(2);
1482     assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1483     v.rotate_right(2);
1484     assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1485 }
1486
1487 #[test]
1488 fn test_rotate_left_random() {
1489     let shifts = [
1490         6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3,
1491         12, 9, 11, 1, 7, 9, 7, 2,
1492     ];
1493     let n = 12;
1494     let mut v: VecDeque<_> = (0..n).collect();
1495     let mut total_shift = 0;
1496     for shift in shifts.iter().cloned() {
1497         v.rotate_left(shift);
1498         total_shift += shift;
1499         for i in 0..n {
1500             assert_eq!(v[i], (i + total_shift) % n);
1501         }
1502     }
1503 }
1504
1505 #[test]
1506 fn test_rotate_right_random() {
1507     let shifts = [
1508         6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3,
1509         12, 9, 11, 1, 7, 9, 7, 2,
1510     ];
1511     let n = 12;
1512     let mut v: VecDeque<_> = (0..n).collect();
1513     let mut total_shift = 0;
1514     for shift in shifts.iter().cloned() {
1515         v.rotate_right(shift);
1516         total_shift += shift;
1517         for i in 0..n {
1518             assert_eq!(v[(i + total_shift) % n], i);
1519         }
1520     }
1521 }
1522
1523 #[test]
1524 fn test_try_fold_empty() {
1525     assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
1526 }
1527
1528 #[test]
1529 fn test_try_fold_none() {
1530     let v: VecDeque<u32> = (0..12).collect();
1531     assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None }));
1532 }
1533
1534 #[test]
1535 fn test_try_fold_ok() {
1536     let v: VecDeque<u32> = (0..12).collect();
1537     assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b)));
1538 }
1539
1540 #[test]
1541 fn test_try_fold_unit() {
1542     let v: VecDeque<()> = std::iter::repeat(()).take(42).collect();
1543     assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
1544 }
1545
1546 #[test]
1547 fn test_try_fold_unit_none() {
1548     let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect();
1549     let mut iter = v.into_iter();
1550     assert!(iter.try_fold((), |_, _| None).is_none());
1551     assert_eq!(iter.len(), 9);
1552 }
1553
1554 #[test]
1555 fn test_try_fold_rotated() {
1556     let mut v: VecDeque<_> = (0..12).collect();
1557     for n in 0..10 {
1558         if n & 1 == 0 {
1559             v.rotate_left(n);
1560         } else {
1561             v.rotate_right(n);
1562         }
1563         assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
1564     }
1565 }
1566
1567 #[test]
1568 fn test_try_fold_moves_iter() {
1569     let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1570     let mut iter = v.into_iter();
1571     assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
1572     assert_eq!(iter.next(), Some(&60));
1573 }
1574
1575 #[test]
1576 fn test_try_fold_exhaust_wrap() {
1577     let mut v = VecDeque::with_capacity(7);
1578     v.push_back(1);
1579     v.push_back(1);
1580     v.push_back(1);
1581     v.pop_front();
1582     v.pop_front();
1583     let mut iter = v.iter();
1584     let _ = iter.try_fold(0, |_, _| Some(1));
1585     assert!(iter.is_empty());
1586 }
1587
1588 #[test]
1589 fn test_try_fold_wraparound() {
1590     let mut v = VecDeque::with_capacity(8);
1591     v.push_back(7);
1592     v.push_back(8);
1593     v.push_back(9);
1594     v.push_front(2);
1595     v.push_front(1);
1596     let mut iter = v.iter();
1597     let _ = iter.find(|&&x| x == 2);
1598     assert_eq!(Some(&7), iter.next());
1599 }
1600
1601 #[test]
1602 fn test_try_rfold_rotated() {
1603     let mut v: VecDeque<_> = (0..12).collect();
1604     for n in 0..10 {
1605         if n & 1 == 0 {
1606             v.rotate_left(n);
1607         } else {
1608             v.rotate_right(n);
1609         }
1610         assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
1611     }
1612 }
1613
1614 #[test]
1615 fn test_try_rfold_moves_iter() {
1616     let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1617     let mut iter = v.into_iter();
1618     assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
1619     assert_eq!(iter.next_back(), Some(&70));
1620 }
1621
1622 #[test]
1623 fn truncate_leak() {
1624     static mut DROPS: i32 = 0;
1625
1626     struct D(bool);
1627
1628     impl Drop for D {
1629         fn drop(&mut self) {
1630             unsafe {
1631                 DROPS += 1;
1632             }
1633
1634             if self.0 {
1635                 panic!("panic in `drop`");
1636             }
1637         }
1638     }
1639
1640     let mut q = VecDeque::new();
1641     q.push_back(D(false));
1642     q.push_back(D(false));
1643     q.push_back(D(false));
1644     q.push_back(D(false));
1645     q.push_back(D(false));
1646     q.push_front(D(true));
1647     q.push_front(D(false));
1648     q.push_front(D(false));
1649
1650     catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
1651
1652     assert_eq!(unsafe { DROPS }, 7);
1653 }
1654
1655 #[test]
1656 fn test_drain_leak() {
1657     static mut DROPS: i32 = 0;
1658
1659     #[derive(Debug, PartialEq)]
1660     struct D(u32, bool);
1661
1662     impl Drop for D {
1663         fn drop(&mut self) {
1664             unsafe {
1665                 DROPS += 1;
1666             }
1667
1668             if self.1 {
1669                 panic!("panic in `drop`");
1670             }
1671         }
1672     }
1673
1674     let mut v = VecDeque::new();
1675     v.push_back(D(4, false));
1676     v.push_back(D(5, false));
1677     v.push_back(D(6, false));
1678     v.push_front(D(3, false));
1679     v.push_front(D(2, true));
1680     v.push_front(D(1, false));
1681     v.push_front(D(0, false));
1682
1683     catch_unwind(AssertUnwindSafe(|| {
1684         v.drain(1..=4);
1685     }))
1686     .ok();
1687
1688     assert_eq!(unsafe { DROPS }, 4);
1689     assert_eq!(v.len(), 3);
1690     drop(v);
1691     assert_eq!(unsafe { DROPS }, 7);
1692 }
1693
1694 #[test]
1695 fn test_binary_search() {
1696     // Contiguous (front only) search:
1697     let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1698     assert!(deque.as_slices().1.is_empty());
1699     assert_eq!(deque.binary_search(&3), Ok(2));
1700     assert_eq!(deque.binary_search(&4), Err(3));
1701
1702     // Split search (both front & back non-empty):
1703     let mut deque: VecDeque<_> = vec![5, 6].into();
1704     deque.push_front(3);
1705     deque.push_front(2);
1706     deque.push_front(1);
1707     deque.push_back(10);
1708     assert!(!deque.as_slices().0.is_empty());
1709     assert!(!deque.as_slices().1.is_empty());
1710     assert_eq!(deque.binary_search(&0), Err(0));
1711     assert_eq!(deque.binary_search(&1), Ok(0));
1712     assert_eq!(deque.binary_search(&5), Ok(3));
1713     assert_eq!(deque.binary_search(&7), Err(5));
1714     assert_eq!(deque.binary_search(&20), Err(6));
1715 }
1716
1717 #[test]
1718 fn test_binary_search_by() {
1719     let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1720
1721     assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&3)), Ok(2));
1722     assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&4)), Err(3));
1723 }
1724
1725 #[test]
1726 fn test_binary_search_by_key() {
1727     let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1728
1729     assert_eq!(deque.binary_search_by_key(&3, |&(v,)| v), Ok(2));
1730     assert_eq!(deque.binary_search_by_key(&4, |&(v,)| v), Err(3));
1731 }
1732
1733 #[test]
1734 fn test_partition_point() {
1735     // Contiguous (front only) search:
1736     let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1737     assert!(deque.as_slices().1.is_empty());
1738     assert_eq!(deque.partition_point(|&v| v <= 3), 3);
1739
1740     // Split search (both front & back non-empty):
1741     let mut deque: VecDeque<_> = vec![5, 6].into();
1742     deque.push_front(3);
1743     deque.push_front(2);
1744     deque.push_front(1);
1745     deque.push_back(10);
1746     assert!(!deque.as_slices().0.is_empty());
1747     assert!(!deque.as_slices().1.is_empty());
1748     assert_eq!(deque.partition_point(|&v| v <= 5), 4);
1749 }
1750
1751 #[test]
1752 fn test_zero_sized_push() {
1753     const N: usize = 8;
1754
1755     // Zero sized type
1756     struct Zst;
1757
1758     // Test that for all possible sequences of push_front / push_back,
1759     // we end up with a deque of the correct size
1760
1761     for len in 0..N {
1762         let mut tester = VecDeque::with_capacity(len);
1763         assert_eq!(tester.len(), 0);
1764         assert!(tester.capacity() >= len);
1765         for case in 0..(1 << len) {
1766             assert_eq!(tester.len(), 0);
1767             for bit in 0..len {
1768                 if case & (1 << bit) != 0 {
1769                     tester.push_front(Zst);
1770                 } else {
1771                     tester.push_back(Zst);
1772                 }
1773             }
1774             assert_eq!(tester.len(), len);
1775             assert_eq!(tester.iter().count(), len);
1776             tester.clear();
1777         }
1778     }
1779 }
1780
1781 #[test]
1782 fn test_from_zero_sized_vec() {
1783     let v = vec![(); 100];
1784     let queue = VecDeque::from(v);
1785     assert_eq!(queue.len(), 100);
1786 }