1 use std::collections::TryReserveError::*;
2 use std::collections::{vec_deque::Drain, VecDeque};
5 use std::ops::Bound::*;
6 use std::panic::{catch_unwind, AssertUnwindSafe};
15 let mut d = VecDeque::new();
16 assert_eq!(d.len(), 0);
20 assert_eq!(d.len(), 3);
22 assert_eq!(d.len(), 4);
23 assert_eq!(*d.front().unwrap(), 42);
24 assert_eq!(*d.back().unwrap(), 137);
25 let mut i = d.pop_front();
26 assert_eq!(i, Some(42));
28 assert_eq!(i, Some(137));
30 assert_eq!(i, Some(137));
32 assert_eq!(i, Some(17));
33 assert_eq!(d.len(), 0);
35 assert_eq!(d.len(), 1);
37 assert_eq!(d.len(), 2);
39 assert_eq!(d.len(), 3);
41 assert_eq!(d.len(), 4);
48 fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
49 let mut deq = VecDeque::new();
50 assert_eq!(deq.len(), 0);
51 deq.push_front(a.clone());
52 deq.push_front(b.clone());
53 deq.push_back(c.clone());
54 assert_eq!(deq.len(), 3);
55 deq.push_back(d.clone());
56 assert_eq!(deq.len(), 4);
57 assert_eq!((*deq.front().unwrap()).clone(), b.clone());
58 assert_eq!((*deq.back().unwrap()).clone(), d.clone());
59 assert_eq!(deq.pop_front().unwrap(), b.clone());
60 assert_eq!(deq.pop_back().unwrap(), d.clone());
61 assert_eq!(deq.pop_back().unwrap(), c.clone());
62 assert_eq!(deq.pop_back().unwrap(), a.clone());
63 assert_eq!(deq.len(), 0);
64 deq.push_back(c.clone());
65 assert_eq!(deq.len(), 1);
66 deq.push_front(b.clone());
67 assert_eq!(deq.len(), 2);
68 deq.push_back(d.clone());
69 assert_eq!(deq.len(), 3);
70 deq.push_front(a.clone());
71 assert_eq!(deq.len(), 4);
72 assert_eq!(deq[0].clone(), a.clone());
73 assert_eq!(deq[1].clone(), b.clone());
74 assert_eq!(deq[2].clone(), c.clone());
75 assert_eq!(deq[3].clone(), d.clone());
79 fn test_push_front_grow() {
80 let mut deq = VecDeque::new();
84 assert_eq!(deq.len(), 66);
87 assert_eq!(deq[i], 65 - i);
90 let mut deq = VecDeque::new();
96 assert_eq!(deq[i], i);
102 let mut deq = VecDeque::new();
106 assert_eq!(deq[1], 2);
111 fn test_index_out_of_bounds() {
112 let mut deq = VecDeque::new();
121 fn test_range_start_overflow() {
122 let deq = VecDeque::from(vec![1, 2, 3]);
123 deq.range((Included(0), Included(usize::MAX)));
128 fn test_range_end_overflow() {
129 let deq = VecDeque::from(vec![1, 2, 3]);
130 deq.range((Excluded(usize::MAX), Included(0)));
133 #[derive(Clone, PartialEq, Debug)]
137 Three(i32, i32, i32),
140 #[derive(Clone, PartialEq, Debug)]
147 #[derive(Clone, PartialEq, Debug)]
155 fn test_param_int() {
156 test_parameterized::<i32>(5, 72, 64, 175);
160 fn test_param_taggy() {
161 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
165 fn test_param_taggypar() {
166 test_parameterized::<Taggypar<i32>>(
169 Threepar::<i32>(1, 2, 3),
170 Twopar::<i32>(17, 42),
175 fn test_param_reccy() {
176 let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
177 let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
178 let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
179 let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
180 test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
184 fn test_with_capacity() {
185 let mut d = VecDeque::with_capacity(0);
187 assert_eq!(d.len(), 1);
188 let mut d = VecDeque::with_capacity(50);
190 assert_eq!(d.len(), 1);
194 fn test_with_capacity_non_power_two() {
195 let mut d3 = VecDeque::with_capacity(3);
200 assert_eq!(d3.pop_front(), Some(1));
202 assert_eq!(d3.front(), None);
209 assert_eq!(d3.pop_front(), Some(3));
211 // Pushing the lo past half way point to trigger
212 // the 'B' scenario for growth
219 // There used to be a bug here about how the
220 // VecDeque made growth assumptions about the
221 // underlying Vec which didn't hold and lead
223 // (Vec grows to next power of two)
224 // good- [9, 12, 15, X, X, X, X, |6]
225 // bug- [15, 12, X, X, X, |6, X, X]
226 assert_eq!(d3.pop_front(), Some(6));
228 // Which leads us to the following state which
229 // would be a failure case.
230 // bug- [15, 12, X, X, X, X, |X, X]
231 assert_eq!(d3.front(), Some(&9));
235 fn test_reserve_exact() {
236 let mut d = VecDeque::new();
239 assert!(d.capacity() >= 51);
244 let mut d = VecDeque::new();
247 assert!(d.capacity() >= 51);
252 let mut d: VecDeque<_> = (0..5).collect();
255 assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]);
260 let mut d = VecDeque::new();
261 assert_eq!(d.iter().next(), None);
262 assert_eq!(d.iter().size_hint(), (0, Some(0)));
268 let b: &[_] = &[&0, &1, &2, &3, &4];
269 assert_eq!(d.iter().collect::<Vec<_>>(), b);
276 let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4];
277 assert_eq!(d.iter().collect::<Vec<_>>(), b);
280 let mut it = d.iter();
281 let mut len = d.len();
287 assert_eq!(it.size_hint(), (len, Some(len)))
295 let mut d = VecDeque::new();
296 assert_eq!(d.iter().rev().next(), None);
302 let b: &[_] = &[&4, &3, &2, &1, &0];
303 assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
309 let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8];
310 assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
314 fn test_mut_rev_iter_wrap() {
315 let mut d = VecDeque::with_capacity(3);
316 assert!(d.iter_mut().rev().next().is_none());
321 assert_eq!(d.pop_front(), Some(1));
324 assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), vec![4, 3, 2]);
329 let mut d = VecDeque::new();
330 assert!(d.iter_mut().next().is_none());
336 for (i, elt) in d.iter_mut().enumerate() {
337 assert_eq!(*elt, 2 - i);
342 let mut it = d.iter_mut();
343 assert_eq!(*it.next().unwrap(), 0);
344 assert_eq!(*it.next().unwrap(), 1);
345 assert_eq!(*it.next().unwrap(), 2);
346 assert!(it.next().is_none());
351 fn test_mut_rev_iter() {
352 let mut d = VecDeque::new();
353 assert!(d.iter_mut().rev().next().is_none());
359 for (i, elt) in d.iter_mut().rev().enumerate() {
365 let mut it = d.iter_mut().rev();
366 assert_eq!(*it.next().unwrap(), 0);
367 assert_eq!(*it.next().unwrap(), 1);
368 assert_eq!(*it.next().unwrap(), 2);
369 assert!(it.next().is_none());
374 fn test_into_iter() {
377 let d: VecDeque<i32> = VecDeque::new();
378 let mut iter = d.into_iter();
380 assert_eq!(iter.size_hint(), (0, Some(0)));
381 assert_eq!(iter.next(), None);
382 assert_eq!(iter.size_hint(), (0, Some(0)));
387 let mut d = VecDeque::new();
392 let b = vec![0, 1, 2, 3, 4];
393 assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
398 let mut d = VecDeque::new();
406 let b = vec![8, 7, 6, 0, 1, 2, 3, 4];
407 assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
412 let mut d = VecDeque::new();
420 let mut it = d.into_iter();
421 assert_eq!(it.size_hint(), (8, Some(8)));
422 assert_eq!(it.next(), Some(8));
423 assert_eq!(it.size_hint(), (7, Some(7)));
424 assert_eq!(it.next_back(), Some(4));
425 assert_eq!(it.size_hint(), (6, Some(6)));
426 assert_eq!(it.next(), Some(7));
427 assert_eq!(it.size_hint(), (5, Some(5)));
435 let mut d: VecDeque<i32> = VecDeque::new();
438 let mut iter = d.drain(..);
440 assert_eq!(iter.size_hint(), (0, Some(0)));
441 assert_eq!(iter.next(), None);
442 assert_eq!(iter.size_hint(), (0, Some(0)));
445 assert!(d.is_empty());
450 let mut d = VecDeque::new();
455 assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
456 assert!(d.is_empty());
461 let mut d = VecDeque::new();
469 assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
470 assert!(d.is_empty());
475 let mut d: VecDeque<_> = VecDeque::new();
484 let mut it = d.drain(..);
485 assert_eq!(it.size_hint(), (8, Some(8)));
486 assert_eq!(it.next(), Some(8));
487 assert_eq!(it.size_hint(), (7, Some(7)));
488 assert_eq!(it.next_back(), Some(4));
489 assert_eq!(it.size_hint(), (6, Some(6)));
490 assert_eq!(it.next(), Some(7));
491 assert_eq!(it.size_hint(), (5, Some(5)));
493 assert!(d.is_empty());
498 fn test_from_iter() {
499 let v = vec![1, 2, 3, 4, 5, 6, 7];
500 let deq: VecDeque<_> = v.iter().cloned().collect();
501 let u: Vec<_> = deq.iter().cloned().collect();
504 let seq = (0..).step_by(2).take(256);
505 let deq: VecDeque<_> = seq.collect();
506 for (i, &x) in deq.iter().enumerate() {
507 assert_eq!(2 * i, x);
509 assert_eq!(deq.len(), 256);
514 let mut d = VecDeque::new();
519 assert_eq!(d.len(), 4);
520 let mut e = d.clone();
521 assert_eq!(e.len(), 4);
522 while !d.is_empty() {
523 assert_eq!(d.pop_back(), e.pop_back());
525 assert_eq!(d.len(), 0);
526 assert_eq!(e.len(), 0);
531 let mut d = VecDeque::new();
532 assert!(d == VecDeque::with_capacity(0));
537 let mut e = VecDeque::with_capacity(0);
547 assert!(e == VecDeque::new());
551 fn test_partial_eq_array() {
552 let d = VecDeque::<char>::new();
555 let mut d = VecDeque::new();
559 let mut d = VecDeque::new();
563 let mut d = VecDeque::new();
566 assert!(d == ['a', 'b']);
571 let mut x = VecDeque::new();
572 let mut y = VecDeque::new();
584 assert!(hash(&x) == hash(&y));
588 fn test_hash_after_rotation() {
589 // test that two deques hash equal even if elements are laid out differently
591 let mut ring: VecDeque<i32> = (0..len as i32).collect();
592 let orig = ring.clone();
593 for _ in 0..ring.capacity() {
594 // shift values 1 step to the right by pop, sub one, push
596 for elt in &mut ring {
599 ring.push_back(len - 1);
600 assert_eq!(hash(&orig), hash(&ring));
601 assert_eq!(orig, ring);
602 assert_eq!(ring, orig);
607 fn test_eq_after_rotation() {
608 // test that two deques are equal even if elements are laid out differently
610 let mut ring: VecDeque<i32> = (0..len as i32).collect();
611 let mut shifted = ring.clone();
613 // shift values 1 step to the right by pop, sub one, push
615 for elt in &mut ring {
618 ring.push_back(len - 1);
622 for _ in 0..shifted.capacity() {
624 for elt in &mut shifted {
627 shifted.push_back(len - 1);
628 assert_eq!(shifted, ring);
629 assert_eq!(ring, shifted);
635 let x = VecDeque::new();
636 let mut y = VecDeque::new();
648 let ringbuf: VecDeque<_> = (0..10).collect();
649 assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
651 let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
652 assert_eq!(format!("{:?}", ringbuf), "[\"just\", \"one\", \"test\", \"more\"]");
657 static mut DROPS: i32 = 0;
667 let mut ring = VecDeque::new();
668 ring.push_back(Elem);
669 ring.push_front(Elem);
670 ring.push_back(Elem);
671 ring.push_front(Elem);
674 assert_eq!(unsafe { DROPS }, 4);
678 fn test_drop_with_pop() {
679 static mut DROPS: i32 = 0;
689 let mut ring = VecDeque::new();
690 ring.push_back(Elem);
691 ring.push_front(Elem);
692 ring.push_back(Elem);
693 ring.push_front(Elem);
695 drop(ring.pop_back());
696 drop(ring.pop_front());
697 assert_eq!(unsafe { DROPS }, 2);
700 assert_eq!(unsafe { DROPS }, 4);
704 fn test_drop_clear() {
705 static mut DROPS: i32 = 0;
715 let mut ring = VecDeque::new();
716 ring.push_back(Elem);
717 ring.push_front(Elem);
718 ring.push_back(Elem);
719 ring.push_front(Elem);
721 assert_eq!(unsafe { DROPS }, 4);
724 assert_eq!(unsafe { DROPS }, 4);
728 fn test_drop_panic() {
729 static mut DROPS: i32 = 0;
740 panic!("panic in `drop`");
745 let mut q = VecDeque::new();
746 q.push_back(D(false));
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_front(D(false));
752 q.push_front(D(false));
753 q.push_front(D(true));
755 catch_unwind(move || drop(q)).ok();
757 assert_eq!(unsafe { DROPS }, 8);
761 fn test_reserve_grow() {
762 // test growth path A
763 // [T o o H] -> [T o o H . . . . ]
764 let mut ring = VecDeque::with_capacity(4);
770 assert_eq!(ring.pop_front(), Some(i));
773 // test growth path B
774 // [H T o o] -> [. T o o H . . . ]
775 let mut ring = VecDeque::with_capacity(4);
778 assert_eq!(ring.pop_front(), Some(i));
785 assert_eq!(ring.pop_front(), Some(i));
788 // test growth path C
789 // [o o H T] -> [o o H . . . . T ]
790 let mut ring = VecDeque::with_capacity(4);
793 assert_eq!(ring.pop_front(), Some(i));
800 assert_eq!(ring.pop_front(), Some(i));
806 let mut ring = VecDeque::new();
808 assert_eq!(ring.get(0), Some(&0));
809 assert_eq!(ring.get(1), None);
812 assert_eq!(ring.get(0), Some(&0));
813 assert_eq!(ring.get(1), Some(&1));
814 assert_eq!(ring.get(2), None);
817 assert_eq!(ring.get(0), Some(&0));
818 assert_eq!(ring.get(1), Some(&1));
819 assert_eq!(ring.get(2), Some(&2));
820 assert_eq!(ring.get(3), None);
822 assert_eq!(ring.pop_front(), Some(0));
823 assert_eq!(ring.get(0), Some(&1));
824 assert_eq!(ring.get(1), Some(&2));
825 assert_eq!(ring.get(2), None);
827 assert_eq!(ring.pop_front(), Some(1));
828 assert_eq!(ring.get(0), Some(&2));
829 assert_eq!(ring.get(1), None);
831 assert_eq!(ring.pop_front(), Some(2));
832 assert_eq!(ring.get(0), None);
833 assert_eq!(ring.get(1), None);
838 let mut ring = VecDeque::new();
843 match ring.get_mut(1) {
848 assert_eq!(ring.get_mut(0), Some(&mut 0));
849 assert_eq!(ring.get_mut(1), Some(&mut -1));
850 assert_eq!(ring.get_mut(2), Some(&mut 2));
851 assert_eq!(ring.get_mut(3), None);
853 assert_eq!(ring.pop_front(), Some(0));
854 assert_eq!(ring.get_mut(0), Some(&mut -1));
855 assert_eq!(ring.get_mut(1), Some(&mut 2));
856 assert_eq!(ring.get_mut(2), None);
861 let mut ring = VecDeque::new();
864 assert_eq!(ring.front(), Some(&10));
866 assert_eq!(ring.front(), Some(&20));
868 assert_eq!(ring.front(), None);
872 fn test_as_slices() {
873 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
874 let cap = ring.capacity() as i32;
876 let last = cap - first;
880 let (left, right) = ring.as_slices();
881 let expected: Vec<_> = (0..=i).collect();
882 assert_eq!(left, &expected[..]);
883 assert_eq!(right, []);
888 let (left, right) = ring.as_slices();
889 let expected_left: Vec<_> = (-last..=j).rev().collect();
890 let expected_right: Vec<_> = (0..first).collect();
891 assert_eq!(left, &expected_left[..]);
892 assert_eq!(right, &expected_right[..]);
895 assert_eq!(ring.len() as i32, cap);
896 assert_eq!(ring.capacity() as i32, cap);
900 fn test_as_mut_slices() {
901 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
902 let cap = ring.capacity() as i32;
904 let last = cap - first;
908 let (left, right) = ring.as_mut_slices();
909 let expected: Vec<_> = (0..=i).collect();
910 assert_eq!(left, &expected[..]);
911 assert_eq!(right, []);
916 let (left, right) = ring.as_mut_slices();
917 let expected_left: Vec<_> = (-last..=j).rev().collect();
918 let expected_right: Vec<_> = (0..first).collect();
919 assert_eq!(left, &expected_left[..]);
920 assert_eq!(right, &expected_right[..]);
923 assert_eq!(ring.len() as i32, cap);
924 assert_eq!(ring.capacity() as i32, cap);
929 let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
930 let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
934 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
935 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
937 // append nothing to something
939 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
940 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
942 // append something to nothing
944 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
945 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
949 fn test_append_permutations() {
950 fn construct_vec_deque(
955 ) -> VecDeque<usize> {
956 let mut out = VecDeque::new();
957 for a in 0..push_back {
960 for b in 0..push_front {
961 out.push_front(push_back + b);
963 for _ in 0..pop_back {
966 for _ in 0..pop_front {
973 let max = if cfg!(miri) { 3 } else { 5 };
975 // Many different permutations of both the `VecDeque` getting appended to
976 // and the one getting appended are generated to check `append`.
977 // This ensures all 6 code paths of `append` are tested.
978 for src_push_back in 0..max {
979 for src_push_front in 0..max {
980 // doesn't pop more values than are pushed
981 for src_pop_back in 0..(src_push_back + src_push_front) {
982 for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) {
983 let src = construct_vec_deque(
990 for dst_push_back in 0..max {
991 for dst_push_front in 0..max {
992 for dst_pop_back in 0..(dst_push_back + dst_push_front) {
994 0..(dst_push_back + dst_push_front - dst_pop_back)
996 let mut dst = construct_vec_deque(
1002 let mut src = src.clone();
1004 // Assert that appending `src` to `dst` gives the same order
1005 // of values as iterating over both in sequence.
1010 .collect::<Vec<usize>>();
1011 dst.append(&mut src);
1012 assert_eq!(dst, correct);
1013 assert!(src.is_empty());
1024 struct DropCounter<'a> {
1028 impl Drop for DropCounter<'_> {
1029 fn drop(&mut self) {
1035 fn test_append_double_drop() {
1036 let (mut count_a, mut count_b) = (0, 0);
1038 let mut a = VecDeque::new();
1039 let mut b = VecDeque::new();
1040 a.push_back(DropCounter { count: &mut count_a });
1041 b.push_back(DropCounter { count: &mut count_b });
1045 assert_eq!(count_a, 1);
1046 assert_eq!(count_b, 1);
1051 let mut buf = VecDeque::new();
1053 buf.retain(|&x| x % 2 == 0);
1054 let v: Vec<_> = buf.into_iter().collect();
1055 assert_eq!(&v[..], &[2, 4]);
1059 fn test_extend_ref() {
1060 let mut v = VecDeque::new();
1062 v.extend(&[2, 3, 4]);
1064 assert_eq!(v.len(), 4);
1065 assert_eq!(v[0], 1);
1066 assert_eq!(v[1], 2);
1067 assert_eq!(v[2], 3);
1068 assert_eq!(v[3], 4);
1070 let mut w = VecDeque::new();
1075 assert_eq!(v.len(), 6);
1076 assert_eq!(v[0], 1);
1077 assert_eq!(v[1], 2);
1078 assert_eq!(v[2], 3);
1079 assert_eq!(v[3], 4);
1080 assert_eq!(v[4], 5);
1081 assert_eq!(v[5], 6);
1085 fn test_contains() {
1086 let mut v = VecDeque::new();
1087 v.extend(&[2, 3, 4]);
1089 assert!(v.contains(&3));
1090 assert!(!v.contains(&1));
1094 assert!(!v.contains(&3));
1098 fn assert_covariance() {
1099 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1105 fn test_is_empty() {
1106 let mut v = VecDeque::<i32>::new();
1107 assert!(v.is_empty());
1108 assert!(v.iter().is_empty());
1109 assert!(v.iter_mut().is_empty());
1110 v.extend(&[2, 3, 4]);
1111 assert!(!v.is_empty());
1112 assert!(!v.iter().is_empty());
1113 assert!(!v.iter_mut().is_empty());
1114 while let Some(_) = v.pop_front() {
1115 assert_eq!(v.is_empty(), v.len() == 0);
1116 assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
1117 assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
1119 assert!(v.is_empty());
1120 assert!(v.iter().is_empty());
1121 assert!(v.iter_mut().is_empty());
1122 assert!(v.into_iter().is_empty());
1126 fn test_reserve_exact_2() {
1127 // This is all the same as test_reserve
1129 let mut v = VecDeque::new();
1132 assert!(v.capacity() >= 2);
1138 assert!(v.capacity() >= 16);
1139 v.reserve_exact(16);
1140 assert!(v.capacity() >= 32);
1144 v.reserve_exact(16);
1145 assert!(v.capacity() >= 48)
1149 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1150 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1151 fn test_try_reserve() {
1152 // These are the interesting cases:
1153 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1154 // * > isize::MAX should always fail
1155 // * On 16/32-bit should CapacityOverflow
1156 // * On 64-bit should OOM
1157 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1158 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1160 const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1161 const MAX_USIZE: usize = usize::MAX;
1163 // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1164 // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1165 // Any platform that succeeds for these requests is technically broken with
1166 // ptr::offset because LLVM is the worst.
1167 let guards_against_isize = size_of::<usize>() < 8;
1170 // Note: basic stuff is checked by test_reserve
1171 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1173 // Check isize::MAX doesn't count as an overflow
1174 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1175 panic!("isize::MAX shouldn't trigger an overflow!");
1177 // Play it again, frank! (just to be sure)
1178 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1179 panic!("isize::MAX shouldn't trigger an overflow!");
1182 if guards_against_isize {
1183 // Check isize::MAX + 1 does count as overflow
1184 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
1186 panic!("isize::MAX + 1 should trigger an overflow!")
1189 // Check usize::MAX does count as overflow
1190 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
1192 panic!("usize::MAX should trigger an overflow!")
1195 // Check isize::MAX is an OOM
1196 // VecDeque starts with capacity 7, always adds 1 to the capacity
1197 // and also rounds the number to next power of 2 so this is the
1198 // furthest we can go without triggering CapacityOverflow
1199 if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_CAP) {
1201 panic!("isize::MAX + 1 should trigger an OOM!")
1207 // Same basic idea, but with non-zero len
1208 let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1210 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1211 panic!("isize::MAX shouldn't trigger an overflow!");
1213 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1214 panic!("isize::MAX shouldn't trigger an overflow!");
1216 if guards_against_isize {
1217 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
1219 panic!("isize::MAX + 1 should trigger an overflow!");
1222 if let Err(AllocError { .. }) = ten_bytes.try_reserve(MAX_CAP - 9) {
1224 panic!("isize::MAX + 1 should trigger an OOM!")
1227 // Should always overflow in the add-to-len
1228 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
1230 panic!("usize::MAX should trigger an overflow!")
1235 // Same basic idea, but with interesting type size
1236 let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1238 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) {
1239 panic!("isize::MAX shouldn't trigger an overflow!");
1241 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) {
1242 panic!("isize::MAX shouldn't trigger an overflow!");
1244 if guards_against_isize {
1245 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) {
1247 panic!("isize::MAX + 1 should trigger an overflow!");
1250 if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) {
1252 panic!("isize::MAX + 1 should trigger an OOM!")
1255 // Should fail in the mul-by-size
1256 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
1258 panic!("usize::MAX should trigger an overflow!");
1264 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1265 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1266 fn test_try_reserve_exact() {
1267 // This is exactly the same as test_try_reserve with the method changed.
1268 // See that test for comments.
1270 const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1271 const MAX_USIZE: usize = usize::MAX;
1273 let guards_against_isize = size_of::<usize>() < 8;
1276 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1278 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1279 panic!("isize::MAX shouldn't trigger an overflow!");
1281 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1282 panic!("isize::MAX shouldn't trigger an overflow!");
1285 if guards_against_isize {
1286 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1288 panic!("isize::MAX + 1 should trigger an overflow!")
1291 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1293 panic!("usize::MAX should trigger an overflow!")
1296 // Check isize::MAX is an OOM
1297 // VecDeque starts with capacity 7, always adds 1 to the capacity
1298 // and also rounds the number to next power of 2 so this is the
1299 // furthest we can go without triggering CapacityOverflow
1300 if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_CAP) {
1302 panic!("isize::MAX + 1 should trigger an OOM!")
1308 let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1310 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1311 panic!("isize::MAX shouldn't trigger an overflow!");
1313 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1314 panic!("isize::MAX shouldn't trigger an overflow!");
1316 if guards_against_isize {
1317 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1319 panic!("isize::MAX + 1 should trigger an overflow!");
1322 if let Err(AllocError { .. }) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1324 panic!("isize::MAX + 1 should trigger an OOM!")
1327 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
1329 panic!("usize::MAX should trigger an overflow!")
1334 let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1336 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) {
1337 panic!("isize::MAX shouldn't trigger an overflow!");
1339 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) {
1340 panic!("isize::MAX shouldn't trigger an overflow!");
1342 if guards_against_isize {
1343 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) {
1345 panic!("isize::MAX + 1 should trigger an overflow!");
1348 if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) {
1350 panic!("isize::MAX + 1 should trigger an OOM!")
1353 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
1355 panic!("usize::MAX should trigger an overflow!")
1361 fn test_rotate_nop() {
1362 let mut v: VecDeque<_> = (0..10).collect();
1363 assert_unchanged(&v);
1366 assert_unchanged(&v);
1369 assert_unchanged(&v);
1372 assert_unchanged(&v);
1375 assert_unchanged(&v);
1379 assert_unchanged(&v);
1383 assert_unchanged(&v);
1387 assert_unchanged(&v);
1391 assert_unchanged(&v);
1395 assert_unchanged(&v);
1399 assert_unchanged(&v);
1405 assert_unchanged(&v);
1411 assert_unchanged(&v);
1413 fn assert_unchanged(v: &VecDeque<i32>) {
1414 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1419 fn test_rotate_left_parts() {
1420 let mut v: VecDeque<_> = (1..=7).collect();
1422 assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
1424 assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
1426 assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
1428 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
1430 assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
1432 assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
1434 assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
1438 fn test_rotate_right_parts() {
1439 let mut v: VecDeque<_> = (1..=7).collect();
1441 assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1443 assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1445 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1447 assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1449 assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1451 assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1453 assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1457 fn test_rotate_left_random() {
1459 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,
1460 12, 9, 11, 1, 7, 9, 7, 2,
1463 let mut v: VecDeque<_> = (0..n).collect();
1464 let mut total_shift = 0;
1465 for shift in shifts.iter().cloned() {
1466 v.rotate_left(shift);
1467 total_shift += shift;
1469 assert_eq!(v[i], (i + total_shift) % n);
1475 fn test_rotate_right_random() {
1477 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,
1478 12, 9, 11, 1, 7, 9, 7, 2,
1481 let mut v: VecDeque<_> = (0..n).collect();
1482 let mut total_shift = 0;
1483 for shift in shifts.iter().cloned() {
1484 v.rotate_right(shift);
1485 total_shift += shift;
1487 assert_eq!(v[(i + total_shift) % n], i);
1493 fn test_try_fold_empty() {
1494 assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
1498 fn test_try_fold_none() {
1499 let v: VecDeque<u32> = (0..12).collect();
1500 assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None }));
1504 fn test_try_fold_ok() {
1505 let v: VecDeque<u32> = (0..12).collect();
1506 assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b)));
1510 fn test_try_fold_unit() {
1511 let v: VecDeque<()> = std::iter::repeat(()).take(42).collect();
1512 assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
1516 fn test_try_fold_unit_none() {
1517 let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect();
1518 let mut iter = v.into_iter();
1519 assert!(iter.try_fold((), |_, _| None).is_none());
1520 assert_eq!(iter.len(), 9);
1524 fn test_try_fold_rotated() {
1525 let mut v: VecDeque<_> = (0..12).collect();
1532 assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
1537 fn test_try_fold_moves_iter() {
1538 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1539 let mut iter = v.into_iter();
1540 assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
1541 assert_eq!(iter.next(), Some(&60));
1545 fn test_try_fold_exhaust_wrap() {
1546 let mut v = VecDeque::with_capacity(7);
1552 let mut iter = v.iter();
1553 let _ = iter.try_fold(0, |_, _| Some(1));
1554 assert!(iter.is_empty());
1558 fn test_try_fold_wraparound() {
1559 let mut v = VecDeque::with_capacity(8);
1565 let mut iter = v.iter();
1566 let _ = iter.find(|&&x| x == 2);
1567 assert_eq!(Some(&7), iter.next());
1571 fn test_try_rfold_rotated() {
1572 let mut v: VecDeque<_> = (0..12).collect();
1579 assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
1584 fn test_try_rfold_moves_iter() {
1585 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1586 let mut iter = v.into_iter();
1587 assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
1588 assert_eq!(iter.next_back(), Some(&70));
1592 fn truncate_leak() {
1593 static mut DROPS: i32 = 0;
1598 fn drop(&mut self) {
1604 panic!("panic in `drop`");
1609 let mut q = VecDeque::new();
1610 q.push_back(D(false));
1611 q.push_back(D(false));
1612 q.push_back(D(false));
1613 q.push_back(D(false));
1614 q.push_back(D(false));
1615 q.push_front(D(true));
1616 q.push_front(D(false));
1617 q.push_front(D(false));
1619 catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
1621 assert_eq!(unsafe { DROPS }, 7);
1625 fn test_drain_leak() {
1626 static mut DROPS: i32 = 0;
1628 #[derive(Debug, PartialEq)]
1629 struct D(u32, bool);
1632 fn drop(&mut self) {
1638 panic!("panic in `drop`");
1643 let mut v = VecDeque::new();
1644 v.push_back(D(4, false));
1645 v.push_back(D(5, false));
1646 v.push_back(D(6, false));
1647 v.push_front(D(3, false));
1648 v.push_front(D(2, true));
1649 v.push_front(D(1, false));
1650 v.push_front(D(0, false));
1652 catch_unwind(AssertUnwindSafe(|| {
1657 assert_eq!(unsafe { DROPS }, 4);
1658 assert_eq!(v.len(), 3);
1660 assert_eq!(unsafe { DROPS }, 7);
1664 fn test_binary_search() {
1665 // Contiguous (front only) search:
1666 let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1667 assert!(deque.as_slices().1.is_empty());
1668 assert_eq!(deque.binary_search(&3), Ok(2));
1669 assert_eq!(deque.binary_search(&4), Err(3));
1671 // Split search (both front & back non-empty):
1672 let mut deque: VecDeque<_> = vec![5, 6].into();
1673 deque.push_front(3);
1674 deque.push_front(2);
1675 deque.push_front(1);
1676 deque.push_back(10);
1677 assert!(!deque.as_slices().0.is_empty());
1678 assert!(!deque.as_slices().1.is_empty());
1679 assert_eq!(deque.binary_search(&0), Err(0));
1680 assert_eq!(deque.binary_search(&1), Ok(0));
1681 assert_eq!(deque.binary_search(&5), Ok(3));
1682 assert_eq!(deque.binary_search(&7), Err(5));
1683 assert_eq!(deque.binary_search(&20), Err(6));
1687 fn test_binary_search_by() {
1688 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1690 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&3)), Ok(2));
1691 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&4)), Err(3));
1695 fn test_binary_search_by_key() {
1696 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1698 assert_eq!(deque.binary_search_by_key(&3, |&(v,)| v), Ok(2));
1699 assert_eq!(deque.binary_search_by_key(&4, |&(v,)| v), Err(3));
1703 fn test_zero_sized_push() {
1709 // Test that for all possible sequences of push_front / push_back,
1710 // we end up with a deque of the correct size
1713 let mut tester = VecDeque::with_capacity(len);
1714 assert_eq!(tester.len(), 0);
1715 assert!(tester.capacity() >= len);
1716 for case in 0..(1 << len) {
1717 assert_eq!(tester.len(), 0);
1719 if case & (1 << bit) != 0 {
1720 tester.push_front(Zst);
1722 tester.push_back(Zst);
1725 assert_eq!(tester.len(), len);
1726 assert_eq!(tester.iter().count(), len);
1733 fn test_from_zero_sized_vec() {
1734 let v = vec![(); 100];
1735 let queue = VecDeque::from(v);
1736 assert_eq!(queue.len(), 100);