1 use std::assert_matches::assert_matches;
2 use std::collections::TryReserveErrorKind::*;
3 use std::collections::{vec_deque::Drain, VecDeque};
6 use std::ops::Bound::*;
7 use std::panic::{catch_unwind, AssertUnwindSafe};
16 let mut d = VecDeque::new();
17 assert_eq!(d.len(), 0);
21 assert_eq!(d.len(), 3);
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));
29 assert_eq!(i, Some(137));
31 assert_eq!(i, Some(137));
33 assert_eq!(i, Some(17));
34 assert_eq!(d.len(), 0);
36 assert_eq!(d.len(), 1);
38 assert_eq!(d.len(), 2);
40 assert_eq!(d.len(), 3);
42 assert_eq!(d.len(), 4);
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());
80 fn test_push_front_grow() {
81 let mut deq = VecDeque::new();
85 assert_eq!(deq.len(), 66);
88 assert_eq!(deq[i], 65 - i);
91 let mut deq = VecDeque::new();
97 assert_eq!(deq[i], i);
103 let mut deq = VecDeque::new();
107 assert_eq!(deq[1], 2);
112 fn test_index_out_of_bounds() {
113 let mut deq = VecDeque::new();
122 fn test_range_start_overflow() {
123 let deq = VecDeque::from(vec![1, 2, 3]);
124 deq.range((Included(0), Included(usize::MAX)));
129 fn test_range_end_overflow() {
130 let deq = VecDeque::from(vec![1, 2, 3]);
131 deq.range((Excluded(usize::MAX), Included(0)));
134 #[derive(Clone, PartialEq, Debug)]
138 Three(i32, i32, i32),
141 #[derive(Clone, PartialEq, Debug)]
148 #[derive(Clone, PartialEq, Debug)]
156 fn test_param_int() {
157 test_parameterized::<i32>(5, 72, 64, 175);
161 fn test_param_taggy() {
162 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
166 fn test_param_taggypar() {
167 test_parameterized::<Taggypar<i32>>(
170 Threepar::<i32>(1, 2, 3),
171 Twopar::<i32>(17, 42),
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);
185 fn test_with_capacity() {
186 let mut d = VecDeque::with_capacity(0);
188 assert_eq!(d.len(), 1);
189 let mut d = VecDeque::with_capacity(50);
191 assert_eq!(d.len(), 1);
195 fn test_with_capacity_non_power_two() {
196 let mut d3 = VecDeque::with_capacity(3);
201 assert_eq!(d3.pop_front(), Some(1));
203 assert_eq!(d3.front(), None);
210 assert_eq!(d3.pop_front(), Some(3));
212 // Pushing the lo past half way point to trigger
213 // the 'B' scenario for growth
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
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));
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));
236 fn test_reserve_exact() {
237 let mut d = VecDeque::new();
240 assert!(d.capacity() >= 51);
245 let mut d = VecDeque::new();
248 assert!(d.capacity() >= 51);
253 let mut d: VecDeque<_> = (0..5).collect();
256 assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]);
261 let mut d = VecDeque::new();
262 assert_eq!(d.iter().next(), None);
263 assert_eq!(d.iter().size_hint(), (0, Some(0)));
269 let b: &[_] = &[&0, &1, &2, &3, &4];
270 assert_eq!(d.iter().collect::<Vec<_>>(), b);
277 let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4];
278 assert_eq!(d.iter().collect::<Vec<_>>(), b);
281 let mut it = d.iter();
282 let mut len = d.len();
288 assert_eq!(it.size_hint(), (len, Some(len)))
296 let mut d = VecDeque::new();
297 assert_eq!(d.iter().rev().next(), None);
303 let b: &[_] = &[&4, &3, &2, &1, &0];
304 assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
310 let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8];
311 assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
315 fn test_mut_rev_iter_wrap() {
316 let mut d = VecDeque::with_capacity(3);
317 assert!(d.iter_mut().rev().next().is_none());
322 assert_eq!(d.pop_front(), Some(1));
325 assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), vec![4, 3, 2]);
330 let mut d = VecDeque::new();
331 assert!(d.iter_mut().next().is_none());
337 for (i, elt) in d.iter_mut().enumerate() {
338 assert_eq!(*elt, 2 - i);
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());
352 fn test_mut_rev_iter() {
353 let mut d = VecDeque::new();
354 assert!(d.iter_mut().rev().next().is_none());
360 for (i, elt) in d.iter_mut().rev().enumerate() {
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());
375 fn test_into_iter() {
378 let d: VecDeque<i32> = VecDeque::new();
379 let mut iter = d.into_iter();
381 assert_eq!(iter.size_hint(), (0, Some(0)));
382 assert_eq!(iter.next(), None);
383 assert_eq!(iter.size_hint(), (0, Some(0)));
388 let mut d = VecDeque::new();
393 let b = vec![0, 1, 2, 3, 4];
394 assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
399 let mut d = VecDeque::new();
407 let b = vec![8, 7, 6, 0, 1, 2, 3, 4];
408 assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
413 let mut d = VecDeque::new();
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)));
436 let mut d: VecDeque<i32> = VecDeque::new();
439 let mut iter = d.drain(..);
441 assert_eq!(iter.size_hint(), (0, Some(0)));
442 assert_eq!(iter.next(), None);
443 assert_eq!(iter.size_hint(), (0, Some(0)));
446 assert!(d.is_empty());
451 let mut d = VecDeque::new();
456 assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
457 assert!(d.is_empty());
462 let mut d = VecDeque::new();
470 assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
471 assert!(d.is_empty());
476 let mut d: VecDeque<_> = VecDeque::new();
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)));
494 assert!(d.is_empty());
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();
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);
510 assert_eq!(deq.len(), 256);
515 let mut d = VecDeque::new();
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());
526 assert_eq!(d.len(), 0);
527 assert_eq!(e.len(), 0);
532 let mut d = VecDeque::new();
533 assert!(d == VecDeque::with_capacity(0));
538 let mut e = VecDeque::with_capacity(0);
548 assert!(e == VecDeque::new());
552 fn test_partial_eq_array() {
553 let d = VecDeque::<char>::new();
556 let mut d = VecDeque::new();
560 let mut d = VecDeque::new();
564 let mut d = VecDeque::new();
567 assert!(d == ['a', 'b']);
572 let mut x = VecDeque::new();
573 let mut y = VecDeque::new();
585 assert!(hash(&x) == hash(&y));
589 fn test_hash_after_rotation() {
590 // test that two deques hash equal even if elements are laid out differently
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
597 for elt in &mut ring {
600 ring.push_back(len - 1);
601 assert_eq!(hash(&orig), hash(&ring));
602 assert_eq!(orig, ring);
603 assert_eq!(ring, orig);
608 fn test_eq_after_rotation() {
609 // test that two deques are equal even if elements are laid out differently
611 let mut ring: VecDeque<i32> = (0..len as i32).collect();
612 let mut shifted = ring.clone();
614 // shift values 1 step to the right by pop, sub one, push
616 for elt in &mut ring {
619 ring.push_back(len - 1);
623 for _ in 0..shifted.capacity() {
625 for elt in &mut shifted {
628 shifted.push_back(len - 1);
629 assert_eq!(shifted, ring);
630 assert_eq!(ring, shifted);
636 let x = VecDeque::new();
637 let mut y = VecDeque::new();
649 let ringbuf: VecDeque<_> = (0..10).collect();
650 assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
652 let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
653 assert_eq!(format!("{:?}", ringbuf), "[\"just\", \"one\", \"test\", \"more\"]");
658 static mut DROPS: i32 = 0;
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);
675 assert_eq!(unsafe { DROPS }, 4);
679 fn test_drop_with_pop() {
680 static mut DROPS: i32 = 0;
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);
696 drop(ring.pop_back());
697 drop(ring.pop_front());
698 assert_eq!(unsafe { DROPS }, 2);
701 assert_eq!(unsafe { DROPS }, 4);
705 fn test_drop_clear() {
706 static mut DROPS: i32 = 0;
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);
722 assert_eq!(unsafe { DROPS }, 4);
725 assert_eq!(unsafe { DROPS }, 4);
729 fn test_drop_panic() {
730 static mut DROPS: i32 = 0;
741 panic!("panic in `drop`");
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));
756 catch_unwind(move || drop(q)).ok();
758 assert_eq!(unsafe { DROPS }, 8);
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);
771 assert_eq!(ring.pop_front(), Some(i));
774 // test growth path B
775 // [H T o o] -> [. T o o H . . . ]
776 let mut ring = VecDeque::with_capacity(4);
779 assert_eq!(ring.pop_front(), Some(i));
786 assert_eq!(ring.pop_front(), Some(i));
789 // test growth path C
790 // [o o H T] -> [o o H . . . . T ]
791 let mut ring = VecDeque::with_capacity(4);
794 assert_eq!(ring.pop_front(), Some(i));
801 assert_eq!(ring.pop_front(), Some(i));
807 let mut ring = VecDeque::new();
809 assert_eq!(ring.get(0), Some(&0));
810 assert_eq!(ring.get(1), None);
813 assert_eq!(ring.get(0), Some(&0));
814 assert_eq!(ring.get(1), Some(&1));
815 assert_eq!(ring.get(2), None);
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);
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);
828 assert_eq!(ring.pop_front(), Some(1));
829 assert_eq!(ring.get(0), Some(&2));
830 assert_eq!(ring.get(1), None);
832 assert_eq!(ring.pop_front(), Some(2));
833 assert_eq!(ring.get(0), None);
834 assert_eq!(ring.get(1), None);
839 let mut ring = VecDeque::new();
844 match ring.get_mut(1) {
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);
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);
862 let mut ring = VecDeque::new();
865 assert_eq!(ring.front(), Some(&10));
867 assert_eq!(ring.front(), Some(&20));
869 assert_eq!(ring.front(), None);
873 fn test_as_slices() {
874 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
875 let cap = ring.capacity() as i32;
877 let last = cap - first;
881 let (left, right) = ring.as_slices();
882 let expected: Vec<_> = (0..=i).collect();
883 assert_eq!(left, &expected[..]);
884 assert_eq!(right, []);
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[..]);
896 assert_eq!(ring.len() as i32, cap);
897 assert_eq!(ring.capacity() as i32, cap);
901 fn test_as_mut_slices() {
902 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
903 let cap = ring.capacity() as i32;
905 let last = cap - first;
909 let (left, right) = ring.as_mut_slices();
910 let expected: Vec<_> = (0..=i).collect();
911 assert_eq!(left, &expected[..]);
912 assert_eq!(right, []);
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[..]);
924 assert_eq!(ring.len() as i32, cap);
925 assert_eq!(ring.capacity() as i32, cap);
930 let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
931 let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
935 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
936 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
938 // append nothing to something
940 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
941 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
943 // append something to nothing
945 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
946 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
950 fn test_append_permutations() {
951 fn construct_vec_deque(
956 ) -> VecDeque<usize> {
957 let mut out = VecDeque::new();
958 for a in 0..push_back {
961 for b in 0..push_front {
962 out.push_front(push_back + b);
964 for _ in 0..pop_back {
967 for _ in 0..pop_front {
974 let max = if cfg!(miri) { 3 } else { 5 };
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(
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) {
995 0..(dst_push_back + dst_push_front - dst_pop_back)
997 let mut dst = construct_vec_deque(
1003 let mut src = src.clone();
1005 // Assert that appending `src` to `dst` gives the same order
1006 // of values as iterating over both in sequence.
1011 .collect::<Vec<usize>>();
1012 dst.append(&mut src);
1013 assert_eq!(dst, correct);
1014 assert!(src.is_empty());
1025 struct DropCounter<'a> {
1029 impl Drop for DropCounter<'_> {
1030 fn drop(&mut self) {
1036 fn test_append_double_drop() {
1037 let (mut count_a, mut count_b) = (0, 0);
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 });
1046 assert_eq!(count_a, 1);
1047 assert_eq!(count_b, 1);
1052 let mut buf = VecDeque::new();
1054 buf.retain(|&x| x % 2 == 0);
1055 let v: Vec<_> = buf.into_iter().collect();
1056 assert_eq!(&v[..], &[2, 4]);
1060 fn test_extend_ref() {
1061 let mut v = VecDeque::new();
1063 v.extend(&[2, 3, 4]);
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);
1071 let mut w = VecDeque::new();
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);
1086 fn test_contains() {
1087 let mut v = VecDeque::new();
1088 v.extend(&[2, 3, 4]);
1090 assert!(v.contains(&3));
1091 assert!(!v.contains(&1));
1095 assert!(!v.contains(&3));
1099 fn assert_covariance() {
1100 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
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);
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());
1127 fn test_reserve_exact_2() {
1128 // This is all the same as test_reserve
1130 let mut v = VecDeque::new();
1133 assert!(v.capacity() >= 2);
1139 assert!(v.capacity() >= 16);
1140 v.reserve_exact(16);
1141 assert!(v.capacity() >= 32);
1145 v.reserve_exact(16);
1146 assert!(v.capacity() >= 48)
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)
1161 const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1162 const MAX_USIZE: usize = usize::MAX;
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;
1171 // Note: basic stuff is checked by test_reserve
1172 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
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!");
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!");
1183 if guards_against_isize {
1184 // Check isize::MAX + 1 does count as overflow
1186 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1187 Err(CapacityOverflow),
1188 "isize::MAX + 1 should trigger an overflow!"
1191 // Check usize::MAX does count as overflow
1193 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1194 Err(CapacityOverflow),
1195 "usize::MAX should trigger an overflow!"
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
1203 empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()),
1204 Err(AllocError { .. }),
1205 "isize::MAX + 1 should trigger an OOM!"
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();
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!");
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!");
1220 if guards_against_isize {
1222 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1223 Err(CapacityOverflow),
1224 "isize::MAX + 1 should trigger an overflow!"
1228 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1229 Err(AllocError { .. }),
1230 "isize::MAX + 1 should trigger an OOM!"
1233 // Should always overflow in the add-to-len
1235 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1236 Err(CapacityOverflow),
1237 "usize::MAX should trigger an overflow!"
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();
1245 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1247 panic!("isize::MAX shouldn't trigger an overflow!");
1249 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1251 panic!("isize::MAX shouldn't trigger an overflow!");
1253 if guards_against_isize {
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!"
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!"
1266 // Should fail in the mul-by-size
1268 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1269 Err(CapacityOverflow),
1270 "usize::MAX should trigger an overflow!"
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.
1282 const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1283 const MAX_USIZE: usize = usize::MAX;
1285 let guards_against_isize = size_of::<usize>() < 8;
1288 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1290 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1292 panic!("isize::MAX shouldn't trigger an overflow!");
1294 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1296 panic!("isize::MAX shouldn't trigger an overflow!");
1299 if guards_against_isize {
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!"
1307 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1308 Err(CapacityOverflow),
1309 "usize::MAX should trigger an overflow!"
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
1317 empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind()),
1318 Err(AllocError { .. }),
1319 "isize::MAX + 1 should trigger an OOM!"
1325 let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1327 if let Err(CapacityOverflow) =
1328 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1330 panic!("isize::MAX shouldn't trigger an overflow!");
1332 if let Err(CapacityOverflow) =
1333 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1335 panic!("isize::MAX shouldn't trigger an overflow!");
1337 if guards_against_isize {
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!"
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!"
1351 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1352 Err(CapacityOverflow),
1353 "usize::MAX should trigger an overflow!"
1358 let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1360 if let Err(CapacityOverflow) =
1361 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1363 panic!("isize::MAX shouldn't trigger an overflow!");
1365 if let Err(CapacityOverflow) =
1366 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1368 panic!("isize::MAX shouldn't trigger an overflow!");
1370 if guards_against_isize {
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!"
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!"
1384 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1385 Err(CapacityOverflow),
1386 "usize::MAX should trigger an overflow!"
1392 fn test_rotate_nop() {
1393 let mut v: VecDeque<_> = (0..10).collect();
1394 assert_unchanged(&v);
1397 assert_unchanged(&v);
1400 assert_unchanged(&v);
1403 assert_unchanged(&v);
1406 assert_unchanged(&v);
1410 assert_unchanged(&v);
1414 assert_unchanged(&v);
1418 assert_unchanged(&v);
1422 assert_unchanged(&v);
1426 assert_unchanged(&v);
1430 assert_unchanged(&v);
1436 assert_unchanged(&v);
1442 assert_unchanged(&v);
1444 fn assert_unchanged(v: &VecDeque<i32>) {
1445 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1450 fn test_rotate_left_parts() {
1451 let mut v: VecDeque<_> = (1..=7).collect();
1453 assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
1455 assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
1457 assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
1459 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
1461 assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
1463 assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
1465 assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
1469 fn test_rotate_right_parts() {
1470 let mut v: VecDeque<_> = (1..=7).collect();
1472 assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1474 assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1476 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1478 assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1480 assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1482 assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1484 assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1488 fn test_rotate_left_random() {
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,
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;
1500 assert_eq!(v[i], (i + total_shift) % n);
1506 fn test_rotate_right_random() {
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,
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;
1518 assert_eq!(v[(i + total_shift) % n], i);
1524 fn test_try_fold_empty() {
1525 assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
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 }));
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)));
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(())));
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);
1555 fn test_try_fold_rotated() {
1556 let mut v: VecDeque<_> = (0..12).collect();
1563 assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
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));
1576 fn test_try_fold_exhaust_wrap() {
1577 let mut v = VecDeque::with_capacity(7);
1583 let mut iter = v.iter();
1584 let _ = iter.try_fold(0, |_, _| Some(1));
1585 assert!(iter.is_empty());
1589 fn test_try_fold_wraparound() {
1590 let mut v = VecDeque::with_capacity(8);
1596 let mut iter = v.iter();
1597 let _ = iter.find(|&&x| x == 2);
1598 assert_eq!(Some(&7), iter.next());
1602 fn test_try_rfold_rotated() {
1603 let mut v: VecDeque<_> = (0..12).collect();
1610 assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
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));
1623 fn truncate_leak() {
1624 static mut DROPS: i32 = 0;
1629 fn drop(&mut self) {
1635 panic!("panic in `drop`");
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));
1650 catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
1652 assert_eq!(unsafe { DROPS }, 7);
1656 fn test_drain_leak() {
1657 static mut DROPS: i32 = 0;
1659 #[derive(Debug, PartialEq)]
1660 struct D(u32, bool);
1663 fn drop(&mut self) {
1669 panic!("panic in `drop`");
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));
1683 catch_unwind(AssertUnwindSafe(|| {
1688 assert_eq!(unsafe { DROPS }, 4);
1689 assert_eq!(v.len(), 3);
1691 assert_eq!(unsafe { DROPS }, 7);
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));
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));
1718 fn test_binary_search_by() {
1719 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
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));
1726 fn test_binary_search_by_key() {
1727 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
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));
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);
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);
1752 fn test_zero_sized_push() {
1758 // Test that for all possible sequences of push_front / push_back,
1759 // we end up with a deque of the correct size
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);
1768 if case & (1 << bit) != 0 {
1769 tester.push_front(Zst);
1771 tester.push_back(Zst);
1774 assert_eq!(tester.len(), len);
1775 assert_eq!(tester.iter().count(), len);
1782 fn test_from_zero_sized_vec() {
1783 let v = vec![(); 100];
1784 let queue = VecDeque::from(v);
1785 assert_eq!(queue.len(), 100);