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();
468 assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
469 assert!(d.is_empty());
474 let mut d: VecDeque<_> = VecDeque::new();
483 let mut it = d.drain(..);
484 assert_eq!(it.size_hint(), (8, Some(8)));
485 assert_eq!(it.next(), Some(8));
486 assert_eq!(it.size_hint(), (7, Some(7)));
487 assert_eq!(it.next_back(), Some(4));
488 assert_eq!(it.size_hint(), (6, Some(6)));
489 assert_eq!(it.next(), Some(7));
490 assert_eq!(it.size_hint(), (5, Some(5)));
492 assert!(d.is_empty());
497 fn test_from_iter() {
498 let v = vec![1, 2, 3, 4, 5, 6, 7];
499 let deq: VecDeque<_> = v.iter().cloned().collect();
500 let u: Vec<_> = deq.iter().cloned().collect();
503 let seq = (0..).step_by(2).take(256);
504 let deq: VecDeque<_> = seq.collect();
505 for (i, &x) in deq.iter().enumerate() {
506 assert_eq!(2 * i, x);
508 assert_eq!(deq.len(), 256);
513 let mut d = VecDeque::new();
518 assert_eq!(d.len(), 4);
519 let mut e = d.clone();
520 assert_eq!(e.len(), 4);
521 while !d.is_empty() {
522 assert_eq!(d.pop_back(), e.pop_back());
524 assert_eq!(d.len(), 0);
525 assert_eq!(e.len(), 0);
530 let mut d = VecDeque::new();
531 assert!(d == VecDeque::with_capacity(0));
536 let mut e = VecDeque::with_capacity(0);
546 assert!(e == VecDeque::new());
550 fn test_partial_eq_array() {
551 let d = VecDeque::<char>::new();
554 let mut d = VecDeque::new();
558 let mut d = VecDeque::new();
562 let mut d = VecDeque::new();
565 assert!(d == ['a', 'b']);
570 let mut x = VecDeque::new();
571 let mut y = VecDeque::new();
583 assert!(hash(&x) == hash(&y));
587 fn test_hash_after_rotation() {
588 // test that two deques hash equal even if elements are laid out differently
590 let mut ring: VecDeque<i32> = (0..len as i32).collect();
591 let orig = ring.clone();
592 for _ in 0..ring.capacity() {
593 // shift values 1 step to the right by pop, sub one, push
595 for elt in &mut ring {
598 ring.push_back(len - 1);
599 assert_eq!(hash(&orig), hash(&ring));
600 assert_eq!(orig, ring);
601 assert_eq!(ring, orig);
606 fn test_eq_after_rotation() {
607 // test that two deques are equal even if elements are laid out differently
609 let mut ring: VecDeque<i32> = (0..len as i32).collect();
610 let mut shifted = ring.clone();
612 // shift values 1 step to the right by pop, sub one, push
614 for elt in &mut ring {
617 ring.push_back(len - 1);
621 for _ in 0..shifted.capacity() {
623 for elt in &mut shifted {
626 shifted.push_back(len - 1);
627 assert_eq!(shifted, ring);
628 assert_eq!(ring, shifted);
634 let x = VecDeque::new();
635 let mut y = VecDeque::new();
647 let ringbuf: VecDeque<_> = (0..10).collect();
648 assert_eq!(format!("{ringbuf:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
650 let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
651 assert_eq!(format!("{ringbuf:?}"), "[\"just\", \"one\", \"test\", \"more\"]");
656 static mut DROPS: i32 = 0;
666 let mut ring = VecDeque::new();
667 ring.push_back(Elem);
668 ring.push_front(Elem);
669 ring.push_back(Elem);
670 ring.push_front(Elem);
673 assert_eq!(unsafe { DROPS }, 4);
677 fn test_drop_with_pop() {
678 static mut DROPS: i32 = 0;
688 let mut ring = VecDeque::new();
689 ring.push_back(Elem);
690 ring.push_front(Elem);
691 ring.push_back(Elem);
692 ring.push_front(Elem);
694 drop(ring.pop_back());
695 drop(ring.pop_front());
696 assert_eq!(unsafe { DROPS }, 2);
699 assert_eq!(unsafe { DROPS }, 4);
703 fn test_drop_clear() {
704 static mut DROPS: i32 = 0;
714 let mut ring = VecDeque::new();
715 ring.push_back(Elem);
716 ring.push_front(Elem);
717 ring.push_back(Elem);
718 ring.push_front(Elem);
720 assert_eq!(unsafe { DROPS }, 4);
723 assert_eq!(unsafe { DROPS }, 4);
727 fn test_drop_panic() {
728 static mut DROPS: i32 = 0;
739 panic!("panic in `drop`");
744 let mut q = VecDeque::new();
745 q.push_back(D(false));
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_front(D(false));
751 q.push_front(D(false));
752 q.push_front(D(true));
754 catch_unwind(move || drop(q)).ok();
756 assert_eq!(unsafe { DROPS }, 8);
760 fn test_reserve_grow() {
761 // test growth path A
762 // [T o o H] -> [T o o H . . . . ]
763 let mut ring = VecDeque::with_capacity(4);
769 assert_eq!(ring.pop_front(), Some(i));
772 // test growth path B
773 // [H T o o] -> [. T o o H . . . ]
774 let mut ring = VecDeque::with_capacity(4);
777 assert_eq!(ring.pop_front(), Some(i));
784 assert_eq!(ring.pop_front(), Some(i));
787 // test growth path C
788 // [o o H T] -> [o o H . . . . T ]
789 let mut ring = VecDeque::with_capacity(4);
792 assert_eq!(ring.pop_front(), Some(i));
799 assert_eq!(ring.pop_front(), Some(i));
805 let mut ring = VecDeque::new();
807 assert_eq!(ring.get(0), Some(&0));
808 assert_eq!(ring.get(1), None);
811 assert_eq!(ring.get(0), Some(&0));
812 assert_eq!(ring.get(1), Some(&1));
813 assert_eq!(ring.get(2), None);
816 assert_eq!(ring.get(0), Some(&0));
817 assert_eq!(ring.get(1), Some(&1));
818 assert_eq!(ring.get(2), Some(&2));
819 assert_eq!(ring.get(3), None);
821 assert_eq!(ring.pop_front(), Some(0));
822 assert_eq!(ring.get(0), Some(&1));
823 assert_eq!(ring.get(1), Some(&2));
824 assert_eq!(ring.get(2), None);
826 assert_eq!(ring.pop_front(), Some(1));
827 assert_eq!(ring.get(0), Some(&2));
828 assert_eq!(ring.get(1), None);
830 assert_eq!(ring.pop_front(), Some(2));
831 assert_eq!(ring.get(0), None);
832 assert_eq!(ring.get(1), None);
837 let mut ring = VecDeque::new();
842 match ring.get_mut(1) {
847 assert_eq!(ring.get_mut(0), Some(&mut 0));
848 assert_eq!(ring.get_mut(1), Some(&mut -1));
849 assert_eq!(ring.get_mut(2), Some(&mut 2));
850 assert_eq!(ring.get_mut(3), None);
852 assert_eq!(ring.pop_front(), Some(0));
853 assert_eq!(ring.get_mut(0), Some(&mut -1));
854 assert_eq!(ring.get_mut(1), Some(&mut 2));
855 assert_eq!(ring.get_mut(2), None);
860 let mut ring = VecDeque::new();
863 assert_eq!(ring.front(), Some(&10));
865 assert_eq!(ring.front(), Some(&20));
867 assert_eq!(ring.front(), None);
871 fn test_as_slices() {
872 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
873 let cap = ring.capacity() as i32;
875 let last = cap - first;
879 let (left, right) = ring.as_slices();
880 let expected: Vec<_> = (0..=i).collect();
881 assert_eq!(left, &expected[..]);
882 assert_eq!(right, []);
887 let (left, right) = ring.as_slices();
888 let expected_left: Vec<_> = (-last..=j).rev().collect();
889 let expected_right: Vec<_> = (0..first).collect();
890 assert_eq!(left, &expected_left[..]);
891 assert_eq!(right, &expected_right[..]);
894 assert_eq!(ring.len() as i32, cap);
895 assert_eq!(ring.capacity() as i32, cap);
899 fn test_as_mut_slices() {
900 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
901 let cap = ring.capacity() as i32;
903 let last = cap - first;
907 let (left, right) = ring.as_mut_slices();
908 let expected: Vec<_> = (0..=i).collect();
909 assert_eq!(left, &expected[..]);
910 assert_eq!(right, []);
915 let (left, right) = ring.as_mut_slices();
916 let expected_left: Vec<_> = (-last..=j).rev().collect();
917 let expected_right: Vec<_> = (0..first).collect();
918 assert_eq!(left, &expected_left[..]);
919 assert_eq!(right, &expected_right[..]);
922 assert_eq!(ring.len() as i32, cap);
923 assert_eq!(ring.capacity() as i32, cap);
928 let mut a: VecDeque<_> = [1, 2, 3].into_iter().collect();
929 let mut b: VecDeque<_> = [4, 5, 6].into_iter().collect();
933 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
934 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
936 // append nothing to something
938 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
939 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
941 // append something to nothing
943 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
944 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
948 fn test_append_permutations() {
949 fn construct_vec_deque(
954 ) -> VecDeque<usize> {
955 let mut out = VecDeque::new();
956 for a in 0..push_back {
959 for b in 0..push_front {
960 out.push_front(push_back + b);
962 for _ in 0..pop_back {
965 for _ in 0..pop_front {
972 let max = if cfg!(miri) { 3 } else { 5 };
974 // Many different permutations of both the `VecDeque` getting appended to
975 // and the one getting appended are generated to check `append`.
976 // This ensures all 6 code paths of `append` are tested.
977 for src_push_back in 0..max {
978 for src_push_front in 0..max {
979 // doesn't pop more values than are pushed
980 for src_pop_back in 0..(src_push_back + src_push_front) {
981 for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) {
982 let src = construct_vec_deque(
989 for dst_push_back in 0..max {
990 for dst_push_front in 0..max {
991 for dst_pop_back in 0..(dst_push_back + dst_push_front) {
993 0..(dst_push_back + dst_push_front - dst_pop_back)
995 let mut dst = construct_vec_deque(
1001 let mut src = src.clone();
1003 // Assert that appending `src` to `dst` gives the same order
1004 // of values as iterating over both in sequence.
1009 .collect::<Vec<usize>>();
1010 dst.append(&mut src);
1011 assert_eq!(dst, correct);
1012 assert!(src.is_empty());
1023 struct DropCounter<'a> {
1027 impl Drop for DropCounter<'_> {
1028 fn drop(&mut self) {
1034 fn test_append_double_drop() {
1035 let (mut count_a, mut count_b) = (0, 0);
1037 let mut a = VecDeque::new();
1038 let mut b = VecDeque::new();
1039 a.push_back(DropCounter { count: &mut count_a });
1040 b.push_back(DropCounter { count: &mut count_b });
1044 assert_eq!(count_a, 1);
1045 assert_eq!(count_b, 1);
1050 let mut buf = VecDeque::new();
1052 buf.retain(|&x| x % 2 == 0);
1053 let v: Vec<_> = buf.into_iter().collect();
1054 assert_eq!(&v[..], &[2, 4]);
1058 fn test_extend_ref() {
1059 let mut v = VecDeque::new();
1061 v.extend(&[2, 3, 4]);
1063 assert_eq!(v.len(), 4);
1064 assert_eq!(v[0], 1);
1065 assert_eq!(v[1], 2);
1066 assert_eq!(v[2], 3);
1067 assert_eq!(v[3], 4);
1069 let mut w = VecDeque::new();
1074 assert_eq!(v.len(), 6);
1075 assert_eq!(v[0], 1);
1076 assert_eq!(v[1], 2);
1077 assert_eq!(v[2], 3);
1078 assert_eq!(v[3], 4);
1079 assert_eq!(v[4], 5);
1080 assert_eq!(v[5], 6);
1084 fn test_contains() {
1085 let mut v = VecDeque::new();
1086 v.extend(&[2, 3, 4]);
1088 assert!(v.contains(&3));
1089 assert!(!v.contains(&1));
1093 assert!(!v.contains(&3));
1097 fn assert_covariance() {
1098 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1104 fn test_is_empty() {
1105 let mut v = VecDeque::<i32>::new();
1106 assert!(v.is_empty());
1107 assert!(v.iter().is_empty());
1108 assert!(v.iter_mut().is_empty());
1109 v.extend(&[2, 3, 4]);
1110 assert!(!v.is_empty());
1111 assert!(!v.iter().is_empty());
1112 assert!(!v.iter_mut().is_empty());
1113 while let Some(_) = v.pop_front() {
1114 assert_eq!(v.is_empty(), v.len() == 0);
1115 assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
1116 assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
1118 assert!(v.is_empty());
1119 assert!(v.iter().is_empty());
1120 assert!(v.iter_mut().is_empty());
1121 assert!(v.into_iter().is_empty());
1125 fn test_reserve_exact_2() {
1126 // This is all the same as test_reserve
1128 let mut v = VecDeque::new();
1131 assert!(v.capacity() >= 2);
1137 assert!(v.capacity() >= 16);
1138 v.reserve_exact(16);
1139 assert!(v.capacity() >= 32);
1143 v.reserve_exact(16);
1144 assert!(v.capacity() >= 33)
1148 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1149 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1150 fn test_try_reserve() {
1151 // These are the interesting cases:
1152 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1153 // * > isize::MAX should always fail
1154 // * On 16/32-bit should CapacityOverflow
1155 // * On 64-bit should OOM
1156 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1157 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1159 const MAX_CAP: usize = isize::MAX as usize;
1160 const MAX_USIZE: usize = usize::MAX;
1163 // Note: basic stuff is checked by test_reserve
1164 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1166 // Check isize::MAX doesn't count as an overflow
1167 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1168 panic!("isize::MAX shouldn't trigger an overflow!");
1170 // Play it again, frank! (just to be sure)
1171 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1172 panic!("isize::MAX shouldn't trigger an overflow!");
1175 // Check isize::MAX + 1 does count as overflow
1177 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1178 Err(CapacityOverflow),
1179 "isize::MAX + 1 should trigger an overflow!"
1182 // Check usize::MAX does count as overflow
1184 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1185 Err(CapacityOverflow),
1186 "usize::MAX should trigger an overflow!"
1191 // Same basic idea, but with non-zero len
1192 let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1194 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1195 panic!("isize::MAX shouldn't trigger an overflow!");
1197 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1198 panic!("isize::MAX shouldn't trigger an overflow!");
1202 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1203 Err(CapacityOverflow),
1204 "isize::MAX + 1 should trigger an overflow!"
1207 // Should always overflow in the add-to-len
1209 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1210 Err(CapacityOverflow),
1211 "usize::MAX should trigger an overflow!"
1216 // Same basic idea, but with interesting type size
1217 let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1219 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1221 panic!("isize::MAX shouldn't trigger an overflow!");
1223 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1225 panic!("isize::MAX shouldn't trigger an overflow!");
1229 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1230 Err(CapacityOverflow),
1231 "isize::MAX + 1 should trigger an overflow!"
1234 // Should fail in the mul-by-size
1236 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1237 Err(CapacityOverflow),
1238 "usize::MAX should trigger an overflow!"
1244 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1245 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1246 fn test_try_reserve_exact() {
1247 // This is exactly the same as test_try_reserve with the method changed.
1248 // See that test for comments.
1250 const MAX_CAP: usize = isize::MAX as usize;
1251 const MAX_USIZE: usize = usize::MAX;
1254 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1256 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1258 panic!("isize::MAX shouldn't trigger an overflow!");
1260 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1262 panic!("isize::MAX shouldn't trigger an overflow!");
1266 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1267 Err(CapacityOverflow),
1268 "isize::MAX + 1 should trigger an overflow!"
1272 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1273 Err(CapacityOverflow),
1274 "usize::MAX should trigger an overflow!"
1279 let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1281 if let Err(CapacityOverflow) =
1282 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1284 panic!("isize::MAX shouldn't trigger an overflow!");
1286 if let Err(CapacityOverflow) =
1287 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1289 panic!("isize::MAX shouldn't trigger an overflow!");
1293 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1294 Err(CapacityOverflow),
1295 "isize::MAX + 1 should trigger an overflow!"
1299 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1300 Err(CapacityOverflow),
1301 "usize::MAX should trigger an overflow!"
1306 let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1308 if let Err(CapacityOverflow) =
1309 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1311 panic!("isize::MAX shouldn't trigger an overflow!");
1313 if let Err(CapacityOverflow) =
1314 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1316 panic!("isize::MAX shouldn't trigger an overflow!");
1320 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1321 Err(CapacityOverflow),
1322 "isize::MAX + 1 should trigger an overflow!"
1326 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1327 Err(CapacityOverflow),
1328 "usize::MAX should trigger an overflow!"
1334 fn test_rotate_nop() {
1335 let mut v: VecDeque<_> = (0..10).collect();
1336 assert_unchanged(&v);
1339 assert_unchanged(&v);
1342 assert_unchanged(&v);
1345 assert_unchanged(&v);
1348 assert_unchanged(&v);
1352 assert_unchanged(&v);
1356 assert_unchanged(&v);
1360 assert_unchanged(&v);
1364 assert_unchanged(&v);
1368 assert_unchanged(&v);
1372 assert_unchanged(&v);
1378 assert_unchanged(&v);
1384 assert_unchanged(&v);
1386 fn assert_unchanged(v: &VecDeque<i32>) {
1387 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1392 fn test_rotate_left_parts() {
1393 let mut v: VecDeque<_> = VecDeque::with_capacity(8);
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<_> = VecDeque::with_capacity(8);
1416 assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1418 assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1420 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1422 assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1424 assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1426 assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1428 assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1432 fn test_rotate_left_random() {
1434 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,
1435 12, 9, 11, 1, 7, 9, 7, 2,
1438 let mut v: VecDeque<_> = (0..n).collect();
1439 let mut total_shift = 0;
1440 for shift in shifts.iter().cloned() {
1441 v.rotate_left(shift);
1442 total_shift += shift;
1444 assert_eq!(v[i], (i + total_shift) % n);
1450 fn test_rotate_right_random() {
1452 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,
1453 12, 9, 11, 1, 7, 9, 7, 2,
1456 let mut v: VecDeque<_> = (0..n).collect();
1457 let mut total_shift = 0;
1458 for shift in shifts.iter().cloned() {
1459 v.rotate_right(shift);
1460 total_shift += shift;
1462 assert_eq!(v[(i + total_shift) % n], i);
1468 fn test_try_fold_empty() {
1469 assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
1473 fn test_try_fold_none() {
1474 let v: VecDeque<u32> = (0..12).collect();
1475 assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None }));
1479 fn test_try_fold_ok() {
1480 let v: VecDeque<u32> = (0..12).collect();
1481 assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b)));
1485 fn test_try_fold_unit() {
1486 let v: VecDeque<()> = std::iter::repeat(()).take(42).collect();
1487 assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
1491 fn test_try_fold_unit_none() {
1492 let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect();
1493 let mut iter = v.into_iter();
1494 assert!(iter.try_fold((), |_, _| None).is_none());
1495 assert_eq!(iter.len(), 9);
1499 fn test_try_fold_rotated() {
1500 let mut v: VecDeque<_> = (0..12).collect();
1507 assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
1512 fn test_try_fold_moves_iter() {
1513 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1514 let mut iter = v.into_iter();
1515 assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
1516 assert_eq!(iter.next(), Some(&60));
1520 fn test_try_fold_exhaust_wrap() {
1521 let mut v = VecDeque::with_capacity(7);
1527 let mut iter = v.iter();
1528 let _ = iter.try_fold(0, |_, _| Some(1));
1529 assert!(iter.is_empty());
1533 fn test_try_fold_wraparound() {
1534 let mut v = VecDeque::with_capacity(8);
1540 let mut iter = v.iter();
1541 let _ = iter.find(|&&x| x == 2);
1542 assert_eq!(Some(&7), iter.next());
1546 fn test_try_rfold_rotated() {
1547 let mut v: VecDeque<_> = (0..12).collect();
1554 assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
1559 fn test_try_rfold_moves_iter() {
1560 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1561 let mut iter = v.into_iter();
1562 assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
1563 assert_eq!(iter.next_back(), Some(&70));
1567 fn truncate_leak() {
1568 static mut DROPS: i32 = 0;
1573 fn drop(&mut self) {
1579 panic!("panic in `drop`");
1584 let mut q = VecDeque::new();
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_back(D(false));
1590 q.push_front(D(true));
1591 q.push_front(D(false));
1592 q.push_front(D(false));
1594 catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
1596 assert_eq!(unsafe { DROPS }, 7);
1600 fn test_drain_leak() {
1601 static mut DROPS: i32 = 0;
1603 #[derive(Debug, PartialEq)]
1604 struct D(u32, bool);
1607 fn drop(&mut self) {
1613 panic!("panic in `drop`");
1618 let mut v = VecDeque::new();
1619 v.push_back(D(4, false));
1620 v.push_back(D(5, false));
1621 v.push_back(D(6, false));
1622 v.push_front(D(3, false));
1623 v.push_front(D(2, true));
1624 v.push_front(D(1, false));
1625 v.push_front(D(0, false));
1627 catch_unwind(AssertUnwindSafe(|| {
1632 assert_eq!(unsafe { DROPS }, 4);
1633 assert_eq!(v.len(), 3);
1635 assert_eq!(unsafe { DROPS }, 7);
1639 fn test_binary_search() {
1640 // Contiguous (front only) search:
1641 let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1642 assert!(deque.as_slices().1.is_empty());
1643 assert_eq!(deque.binary_search(&3), Ok(2));
1644 assert_eq!(deque.binary_search(&4), Err(3));
1646 // Split search (both front & back non-empty):
1647 let mut deque: VecDeque<_> = vec![5, 6].into();
1648 deque.push_front(3);
1649 deque.push_front(2);
1650 deque.push_front(1);
1651 deque.push_back(10);
1652 assert!(!deque.as_slices().0.is_empty());
1653 assert!(!deque.as_slices().1.is_empty());
1654 assert_eq!(deque.binary_search(&0), Err(0));
1655 assert_eq!(deque.binary_search(&1), Ok(0));
1656 assert_eq!(deque.binary_search(&5), Ok(3));
1657 assert_eq!(deque.binary_search(&7), Err(5));
1658 assert_eq!(deque.binary_search(&20), Err(6));
1662 fn test_binary_search_by() {
1663 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1665 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&3)), Ok(2));
1666 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&4)), Err(3));
1670 fn test_binary_search_by_key() {
1671 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1673 assert_eq!(deque.binary_search_by_key(&3, |&(v,)| v), Ok(2));
1674 assert_eq!(deque.binary_search_by_key(&4, |&(v,)| v), Err(3));
1678 fn test_partition_point() {
1679 // Contiguous (front only) search:
1680 let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1681 assert!(deque.as_slices().1.is_empty());
1682 assert_eq!(deque.partition_point(|&v| v <= 3), 3);
1684 // Split search (both front & back non-empty):
1685 let mut deque: VecDeque<_> = vec![5, 6].into();
1686 deque.push_front(3);
1687 deque.push_front(2);
1688 deque.push_front(1);
1689 deque.push_back(10);
1690 assert!(!deque.as_slices().0.is_empty());
1691 assert!(!deque.as_slices().1.is_empty());
1692 assert_eq!(deque.partition_point(|&v| v <= 5), 4);
1696 fn test_zero_sized_push() {
1702 // Test that for all possible sequences of push_front / push_back,
1703 // we end up with a deque of the correct size
1706 let mut tester = VecDeque::with_capacity(len);
1707 assert_eq!(tester.len(), 0);
1708 assert!(tester.capacity() >= len);
1709 for case in 0..(1 << len) {
1710 assert_eq!(tester.len(), 0);
1712 if case & (1 << bit) != 0 {
1713 tester.push_front(Zst);
1715 tester.push_back(Zst);
1718 assert_eq!(tester.len(), len);
1719 assert_eq!(tester.iter().count(), len);
1726 fn test_from_zero_sized_vec() {
1727 let v = vec![(); 100];
1728 let queue = VecDeque::from(v);
1729 assert_eq!(queue.len(), 100);
1733 fn test_resize_keeps_reserved_space_from_item() {
1734 let v = Vec::<i32>::with_capacity(1234);
1735 let mut d = VecDeque::new();
1737 assert_eq!(d[0].capacity(), 1234);