1 use std::assert_matches::assert_matches;
2 use std::collections::TryReserveErrorKind::*;
3 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<_> = [1, 2, 3].into_iter().collect();
930 let mut b: VecDeque<_> = [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;
1164 // Note: basic stuff is checked by test_reserve
1165 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1167 // Check isize::MAX doesn't count as an overflow
1168 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1169 panic!("isize::MAX shouldn't trigger an overflow!");
1171 // Play it again, frank! (just to be sure)
1172 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1173 panic!("isize::MAX shouldn't trigger an overflow!");
1176 // Check isize::MAX + 1 does count as overflow
1178 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1179 Err(CapacityOverflow),
1180 "isize::MAX + 1 should trigger an overflow!"
1183 // Check usize::MAX does count as overflow
1185 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1186 Err(CapacityOverflow),
1187 "usize::MAX should trigger an overflow!"
1192 // Same basic idea, but with non-zero len
1193 let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1195 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1196 panic!("isize::MAX shouldn't trigger an overflow!");
1198 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1199 panic!("isize::MAX shouldn't trigger an overflow!");
1203 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1204 Err(CapacityOverflow),
1205 "isize::MAX + 1 should trigger an overflow!"
1208 // Should always overflow in the add-to-len
1210 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1211 Err(CapacityOverflow),
1212 "usize::MAX should trigger an overflow!"
1217 // Same basic idea, but with interesting type size
1218 let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1220 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1222 panic!("isize::MAX shouldn't trigger an overflow!");
1224 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1226 panic!("isize::MAX shouldn't trigger an overflow!");
1230 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1231 Err(CapacityOverflow),
1232 "isize::MAX + 1 should trigger an overflow!"
1235 // Should fail in the mul-by-size
1237 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1238 Err(CapacityOverflow),
1239 "usize::MAX should trigger an overflow!"
1245 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1246 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1247 fn test_try_reserve_exact() {
1248 // This is exactly the same as test_try_reserve with the method changed.
1249 // See that test for comments.
1251 const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1252 const MAX_USIZE: usize = usize::MAX;
1255 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1257 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1259 panic!("isize::MAX shouldn't trigger an overflow!");
1261 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1263 panic!("isize::MAX shouldn't trigger an overflow!");
1267 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1268 Err(CapacityOverflow),
1269 "isize::MAX + 1 should trigger an overflow!"
1273 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1274 Err(CapacityOverflow),
1275 "usize::MAX should trigger an overflow!"
1280 let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1282 if let Err(CapacityOverflow) =
1283 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1285 panic!("isize::MAX shouldn't trigger an overflow!");
1287 if let Err(CapacityOverflow) =
1288 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1290 panic!("isize::MAX shouldn't trigger an overflow!");
1294 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1295 Err(CapacityOverflow),
1296 "isize::MAX + 1 should trigger an overflow!"
1300 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1301 Err(CapacityOverflow),
1302 "usize::MAX should trigger an overflow!"
1307 let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1309 if let Err(CapacityOverflow) =
1310 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1312 panic!("isize::MAX shouldn't trigger an overflow!");
1314 if let Err(CapacityOverflow) =
1315 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1317 panic!("isize::MAX shouldn't trigger an overflow!");
1321 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1322 Err(CapacityOverflow),
1323 "isize::MAX + 1 should trigger an overflow!"
1327 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1328 Err(CapacityOverflow),
1329 "usize::MAX should trigger an overflow!"
1335 fn test_rotate_nop() {
1336 let mut v: VecDeque<_> = (0..10).collect();
1337 assert_unchanged(&v);
1340 assert_unchanged(&v);
1343 assert_unchanged(&v);
1346 assert_unchanged(&v);
1349 assert_unchanged(&v);
1353 assert_unchanged(&v);
1357 assert_unchanged(&v);
1361 assert_unchanged(&v);
1365 assert_unchanged(&v);
1369 assert_unchanged(&v);
1373 assert_unchanged(&v);
1379 assert_unchanged(&v);
1385 assert_unchanged(&v);
1387 fn assert_unchanged(v: &VecDeque<i32>) {
1388 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1393 fn test_rotate_left_parts() {
1394 let mut v: VecDeque<_> = (1..=7).collect();
1396 assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
1398 assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
1400 assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
1402 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
1404 assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
1406 assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
1408 assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
1412 fn test_rotate_right_parts() {
1413 let mut v: VecDeque<_> = (1..=7).collect();
1415 assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1417 assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1419 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1421 assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1423 assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1425 assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1427 assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1431 fn test_rotate_left_random() {
1433 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,
1434 12, 9, 11, 1, 7, 9, 7, 2,
1437 let mut v: VecDeque<_> = (0..n).collect();
1438 let mut total_shift = 0;
1439 for shift in shifts.iter().cloned() {
1440 v.rotate_left(shift);
1441 total_shift += shift;
1443 assert_eq!(v[i], (i + total_shift) % n);
1449 fn test_rotate_right_random() {
1451 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,
1452 12, 9, 11, 1, 7, 9, 7, 2,
1455 let mut v: VecDeque<_> = (0..n).collect();
1456 let mut total_shift = 0;
1457 for shift in shifts.iter().cloned() {
1458 v.rotate_right(shift);
1459 total_shift += shift;
1461 assert_eq!(v[(i + total_shift) % n], i);
1467 fn test_try_fold_empty() {
1468 assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
1472 fn test_try_fold_none() {
1473 let v: VecDeque<u32> = (0..12).collect();
1474 assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None }));
1478 fn test_try_fold_ok() {
1479 let v: VecDeque<u32> = (0..12).collect();
1480 assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b)));
1484 fn test_try_fold_unit() {
1485 let v: VecDeque<()> = std::iter::repeat(()).take(42).collect();
1486 assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
1490 fn test_try_fold_unit_none() {
1491 let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect();
1492 let mut iter = v.into_iter();
1493 assert!(iter.try_fold((), |_, _| None).is_none());
1494 assert_eq!(iter.len(), 9);
1498 fn test_try_fold_rotated() {
1499 let mut v: VecDeque<_> = (0..12).collect();
1506 assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
1511 fn test_try_fold_moves_iter() {
1512 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1513 let mut iter = v.into_iter();
1514 assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
1515 assert_eq!(iter.next(), Some(&60));
1519 fn test_try_fold_exhaust_wrap() {
1520 let mut v = VecDeque::with_capacity(7);
1526 let mut iter = v.iter();
1527 let _ = iter.try_fold(0, |_, _| Some(1));
1528 assert!(iter.is_empty());
1532 fn test_try_fold_wraparound() {
1533 let mut v = VecDeque::with_capacity(8);
1539 let mut iter = v.iter();
1540 let _ = iter.find(|&&x| x == 2);
1541 assert_eq!(Some(&7), iter.next());
1545 fn test_try_rfold_rotated() {
1546 let mut v: VecDeque<_> = (0..12).collect();
1553 assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
1558 fn test_try_rfold_moves_iter() {
1559 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1560 let mut iter = v.into_iter();
1561 assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
1562 assert_eq!(iter.next_back(), Some(&70));
1566 fn truncate_leak() {
1567 static mut DROPS: i32 = 0;
1572 fn drop(&mut self) {
1578 panic!("panic in `drop`");
1583 let mut q = VecDeque::new();
1584 q.push_back(D(false));
1585 q.push_back(D(false));
1586 q.push_back(D(false));
1587 q.push_back(D(false));
1588 q.push_back(D(false));
1589 q.push_front(D(true));
1590 q.push_front(D(false));
1591 q.push_front(D(false));
1593 catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
1595 assert_eq!(unsafe { DROPS }, 7);
1599 fn test_drain_leak() {
1600 static mut DROPS: i32 = 0;
1602 #[derive(Debug, PartialEq)]
1603 struct D(u32, bool);
1606 fn drop(&mut self) {
1612 panic!("panic in `drop`");
1617 let mut v = VecDeque::new();
1618 v.push_back(D(4, false));
1619 v.push_back(D(5, false));
1620 v.push_back(D(6, false));
1621 v.push_front(D(3, false));
1622 v.push_front(D(2, true));
1623 v.push_front(D(1, false));
1624 v.push_front(D(0, false));
1626 catch_unwind(AssertUnwindSafe(|| {
1631 assert_eq!(unsafe { DROPS }, 4);
1632 assert_eq!(v.len(), 3);
1634 assert_eq!(unsafe { DROPS }, 7);
1638 fn test_binary_search() {
1639 // Contiguous (front only) search:
1640 let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1641 assert!(deque.as_slices().1.is_empty());
1642 assert_eq!(deque.binary_search(&3), Ok(2));
1643 assert_eq!(deque.binary_search(&4), Err(3));
1645 // Split search (both front & back non-empty):
1646 let mut deque: VecDeque<_> = vec![5, 6].into();
1647 deque.push_front(3);
1648 deque.push_front(2);
1649 deque.push_front(1);
1650 deque.push_back(10);
1651 assert!(!deque.as_slices().0.is_empty());
1652 assert!(!deque.as_slices().1.is_empty());
1653 assert_eq!(deque.binary_search(&0), Err(0));
1654 assert_eq!(deque.binary_search(&1), Ok(0));
1655 assert_eq!(deque.binary_search(&5), Ok(3));
1656 assert_eq!(deque.binary_search(&7), Err(5));
1657 assert_eq!(deque.binary_search(&20), Err(6));
1661 fn test_binary_search_by() {
1662 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1664 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&3)), Ok(2));
1665 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&4)), Err(3));
1669 fn test_binary_search_by_key() {
1670 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1672 assert_eq!(deque.binary_search_by_key(&3, |&(v,)| v), Ok(2));
1673 assert_eq!(deque.binary_search_by_key(&4, |&(v,)| v), Err(3));
1677 fn test_partition_point() {
1678 // Contiguous (front only) search:
1679 let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1680 assert!(deque.as_slices().1.is_empty());
1681 assert_eq!(deque.partition_point(|&v| v <= 3), 3);
1683 // Split search (both front & back non-empty):
1684 let mut deque: VecDeque<_> = vec![5, 6].into();
1685 deque.push_front(3);
1686 deque.push_front(2);
1687 deque.push_front(1);
1688 deque.push_back(10);
1689 assert!(!deque.as_slices().0.is_empty());
1690 assert!(!deque.as_slices().1.is_empty());
1691 assert_eq!(deque.partition_point(|&v| v <= 5), 4);
1695 fn test_zero_sized_push() {
1701 // Test that for all possible sequences of push_front / push_back,
1702 // we end up with a deque of the correct size
1705 let mut tester = VecDeque::with_capacity(len);
1706 assert_eq!(tester.len(), 0);
1707 assert!(tester.capacity() >= len);
1708 for case in 0..(1 << len) {
1709 assert_eq!(tester.len(), 0);
1711 if case & (1 << bit) != 0 {
1712 tester.push_front(Zst);
1714 tester.push_back(Zst);
1717 assert_eq!(tester.len(), len);
1718 assert_eq!(tester.iter().count(), len);
1725 fn test_from_zero_sized_vec() {
1726 let v = vec![(); 100];
1727 let queue = VecDeque::from(v);
1728 assert_eq!(queue.len(), 100);