use core::num::NonZeroUsize; use std::assert_matches::assert_matches; use std::collections::TryReserveErrorKind::*; use std::collections::{vec_deque::Drain, VecDeque}; use std::fmt::Debug; use std::ops::Bound::*; use std::panic::{catch_unwind, AssertUnwindSafe}; use crate::hash; use Taggy::*; use Taggypar::*; #[test] fn test_simple() { let mut d = VecDeque::new(); assert_eq!(d.len(), 0); d.push_front(17); d.push_front(42); d.push_back(137); assert_eq!(d.len(), 3); d.push_back(137); assert_eq!(d.len(), 4); assert_eq!(*d.front().unwrap(), 42); assert_eq!(*d.back().unwrap(), 137); let mut i = d.pop_front(); assert_eq!(i, Some(42)); i = d.pop_back(); assert_eq!(i, Some(137)); i = d.pop_back(); assert_eq!(i, Some(137)); i = d.pop_back(); assert_eq!(i, Some(17)); assert_eq!(d.len(), 0); d.push_back(3); assert_eq!(d.len(), 1); d.push_front(2); assert_eq!(d.len(), 2); d.push_back(4); assert_eq!(d.len(), 3); d.push_front(1); assert_eq!(d.len(), 4); assert_eq!(d[0], 1); assert_eq!(d[1], 2); assert_eq!(d[2], 3); assert_eq!(d[3], 4); } fn test_parameterized(a: T, b: T, c: T, d: T) { let mut deq = VecDeque::new(); assert_eq!(deq.len(), 0); deq.push_front(a.clone()); deq.push_front(b.clone()); deq.push_back(c.clone()); assert_eq!(deq.len(), 3); deq.push_back(d.clone()); assert_eq!(deq.len(), 4); assert_eq!((*deq.front().unwrap()).clone(), b.clone()); assert_eq!((*deq.back().unwrap()).clone(), d.clone()); assert_eq!(deq.pop_front().unwrap(), b.clone()); assert_eq!(deq.pop_back().unwrap(), d.clone()); assert_eq!(deq.pop_back().unwrap(), c.clone()); assert_eq!(deq.pop_back().unwrap(), a.clone()); assert_eq!(deq.len(), 0); deq.push_back(c.clone()); assert_eq!(deq.len(), 1); deq.push_front(b.clone()); assert_eq!(deq.len(), 2); deq.push_back(d.clone()); assert_eq!(deq.len(), 3); deq.push_front(a.clone()); assert_eq!(deq.len(), 4); assert_eq!(deq[0].clone(), a.clone()); assert_eq!(deq[1].clone(), b.clone()); assert_eq!(deq[2].clone(), c.clone()); assert_eq!(deq[3].clone(), d.clone()); } #[test] fn test_push_front_grow() { let mut deq = VecDeque::new(); for i in 0..66 { deq.push_front(i); } assert_eq!(deq.len(), 66); for i in 0..66 { assert_eq!(deq[i], 65 - i); } let mut deq = VecDeque::new(); for i in 0..66 { deq.push_back(i); } for i in 0..66 { assert_eq!(deq[i], i); } } #[test] fn test_index() { let mut deq = VecDeque::new(); for i in 1..4 { deq.push_front(i); } assert_eq!(deq[1], 2); } #[test] #[should_panic] fn test_index_out_of_bounds() { let mut deq = VecDeque::new(); for i in 1..4 { deq.push_front(i); } deq[3]; } #[test] #[should_panic] fn test_range_start_overflow() { let deq = VecDeque::from(vec![1, 2, 3]); deq.range((Included(0), Included(usize::MAX))); } #[test] #[should_panic] fn test_range_end_overflow() { let deq = VecDeque::from(vec![1, 2, 3]); deq.range((Excluded(usize::MAX), Included(0))); } #[derive(Clone, PartialEq, Debug)] enum Taggy { One(i32), Two(i32, i32), Three(i32, i32, i32), } #[derive(Clone, PartialEq, Debug)] enum Taggypar { Onepar(T), Twopar(T, T), Threepar(T, T, T), } #[derive(Clone, PartialEq, Debug)] struct RecCy { x: i32, y: i32, t: Taggy, } #[test] fn test_param_int() { test_parameterized::(5, 72, 64, 175); } #[test] fn test_param_taggy() { test_parameterized::(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42)); } #[test] fn test_param_taggypar() { test_parameterized::>( Onepar::(1), Twopar::(1, 2), Threepar::(1, 2, 3), Twopar::(17, 42), ); } #[test] fn test_param_reccy() { let reccy1 = RecCy { x: 1, y: 2, t: One(1) }; let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) }; let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) }; let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) }; test_parameterized::(reccy1, reccy2, reccy3, reccy4); } #[test] fn test_with_capacity() { let mut d = VecDeque::with_capacity(0); d.push_back(1); assert_eq!(d.len(), 1); let mut d = VecDeque::with_capacity(50); d.push_back(1); assert_eq!(d.len(), 1); } #[test] fn test_with_capacity_non_power_two() { let mut d3 = VecDeque::with_capacity(3); d3.push_back(1); // X = None, | = lo // [|1, X, X] assert_eq!(d3.pop_front(), Some(1)); // [X, |X, X] assert_eq!(d3.front(), None); // [X, |3, X] d3.push_back(3); // [X, |3, 6] d3.push_back(6); // [X, X, |6] assert_eq!(d3.pop_front(), Some(3)); // Pushing the lo past half way point to trigger // the 'B' scenario for growth // [9, X, |6] d3.push_back(9); // [9, 12, |6] d3.push_back(12); d3.push_back(15); // There used to be a bug here about how the // VecDeque made growth assumptions about the // underlying Vec which didn't hold and lead // to corruption. // (Vec grows to next power of two) // good- [9, 12, 15, X, X, X, X, |6] // bug- [15, 12, X, X, X, |6, X, X] assert_eq!(d3.pop_front(), Some(6)); // Which leads us to the following state which // would be a failure case. // bug- [15, 12, X, X, X, X, |X, X] assert_eq!(d3.front(), Some(&9)); } #[test] fn test_reserve_exact() { let mut d = VecDeque::new(); d.push_back(0); d.reserve_exact(50); assert!(d.capacity() >= 51); } #[test] fn test_reserve() { let mut d = VecDeque::new(); d.push_back(0); d.reserve(50); assert!(d.capacity() >= 51); } #[test] fn test_swap() { let mut d: VecDeque<_> = (0..5).collect(); d.pop_front(); d.swap(0, 3); assert_eq!(d.iter().cloned().collect::>(), [4, 2, 3, 1]); } #[test] fn test_iter() { let mut d = VecDeque::new(); assert_eq!(d.iter().next(), None); assert_eq!(d.iter().size_hint(), (0, Some(0))); for i in 0..5 { d.push_back(i); } { let b: &[_] = &[&0, &1, &2, &3, &4]; assert_eq!(d.iter().collect::>(), b); } for i in 6..9 { d.push_front(i); } { let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4]; assert_eq!(d.iter().collect::>(), b); } let mut it = d.iter(); let mut len = d.len(); loop { match it.next() { None => break, _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) } } } } #[test] fn test_rev_iter() { let mut d = VecDeque::new(); assert_eq!(d.iter().rev().next(), None); for i in 0..5 { d.push_back(i); } { let b: &[_] = &[&4, &3, &2, &1, &0]; assert_eq!(d.iter().rev().collect::>(), b); } for i in 6..9 { d.push_front(i); } let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8]; assert_eq!(d.iter().rev().collect::>(), b); } #[test] fn test_mut_rev_iter_wrap() { let mut d = VecDeque::with_capacity(3); assert!(d.iter_mut().rev().next().is_none()); d.push_back(1); d.push_back(2); d.push_back(3); assert_eq!(d.pop_front(), Some(1)); d.push_back(4); assert_eq!(d.iter_mut().rev().map(|x| *x).collect::>(), vec![4, 3, 2]); } #[test] fn test_mut_iter() { let mut d = VecDeque::new(); assert!(d.iter_mut().next().is_none()); for i in 0..3 { d.push_front(i); } for (i, elt) in d.iter_mut().enumerate() { assert_eq!(*elt, 2 - i); *elt = i; } { let mut it = d.iter_mut(); assert_eq!(*it.next().unwrap(), 0); assert_eq!(*it.next().unwrap(), 1); assert_eq!(*it.next().unwrap(), 2); assert!(it.next().is_none()); } } #[test] fn test_mut_rev_iter() { let mut d = VecDeque::new(); assert!(d.iter_mut().rev().next().is_none()); for i in 0..3 { d.push_front(i); } for (i, elt) in d.iter_mut().rev().enumerate() { assert_eq!(*elt, i); *elt = i; } { let mut it = d.iter_mut().rev(); assert_eq!(*it.next().unwrap(), 0); assert_eq!(*it.next().unwrap(), 1); assert_eq!(*it.next().unwrap(), 2); assert!(it.next().is_none()); } } #[test] fn test_into_iter() { // Empty iter { let d: VecDeque = VecDeque::new(); let mut iter = d.into_iter(); assert_eq!(iter.size_hint(), (0, Some(0))); assert_eq!(iter.next(), None); assert_eq!(iter.size_hint(), (0, Some(0))); } // simple iter { let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } let b = vec![0, 1, 2, 3, 4]; assert_eq!(d.into_iter().collect::>(), b); } // wrapped iter { let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } for i in 6..9 { d.push_front(i); } let b = vec![8, 7, 6, 0, 1, 2, 3, 4]; assert_eq!(d.into_iter().collect::>(), b); } // partially used { let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } for i in 6..9 { d.push_front(i); } let mut it = d.into_iter(); assert_eq!(it.size_hint(), (8, Some(8))); assert_eq!(it.next(), Some(8)); assert_eq!(it.size_hint(), (7, Some(7))); assert_eq!(it.next_back(), Some(4)); assert_eq!(it.size_hint(), (6, Some(6))); assert_eq!(it.next(), Some(7)); assert_eq!(it.size_hint(), (5, Some(5))); } // advance_by { let mut d = VecDeque::new(); for i in 0..=4 { d.push_back(i); } for i in 6..=8 { d.push_front(i); } let mut it = d.into_iter(); assert_eq!(it.advance_by(1), Ok(())); assert_eq!(it.next(), Some(7)); assert_eq!(it.advance_back_by(1), Ok(())); assert_eq!(it.next_back(), Some(3)); let mut it = VecDeque::from(vec![1, 2, 3, 4, 5]).into_iter(); assert_eq!(it.advance_by(10), Err(NonZeroUsize::new(5).unwrap())); let mut it = VecDeque::from(vec![1, 2, 3, 4, 5]).into_iter(); assert_eq!(it.advance_back_by(10), Err(NonZeroUsize::new(5).unwrap())); } } #[test] fn test_drain() { // Empty iter { let mut d: VecDeque = VecDeque::new(); { let mut iter = d.drain(..); assert_eq!(iter.size_hint(), (0, Some(0))); assert_eq!(iter.next(), None); assert_eq!(iter.size_hint(), (0, Some(0))); } assert!(d.is_empty()); } // simple iter { let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } assert_eq!(d.drain(..).collect::>(), [0, 1, 2, 3, 4]); assert!(d.is_empty()); } // wrapped iter { let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } for i in 6..9 { d.push_front(i); } assert_eq!(d.drain(..).collect::>(), [8, 7, 6, 0, 1, 2, 3, 4]); assert!(d.is_empty()); } // partially used { let mut d: VecDeque<_> = VecDeque::new(); for i in 0..5 { d.push_back(i); } for i in 6..9 { d.push_front(i); } { let mut it = d.drain(..); assert_eq!(it.size_hint(), (8, Some(8))); assert_eq!(it.next(), Some(8)); assert_eq!(it.size_hint(), (7, Some(7))); assert_eq!(it.next_back(), Some(4)); assert_eq!(it.size_hint(), (6, Some(6))); assert_eq!(it.next(), Some(7)); assert_eq!(it.size_hint(), (5, Some(5))); } assert!(d.is_empty()); } } #[test] fn test_from_iter() { let v = vec![1, 2, 3, 4, 5, 6, 7]; let deq: VecDeque<_> = v.iter().cloned().collect(); let u: Vec<_> = deq.iter().cloned().collect(); assert_eq!(u, v); let seq = (0..).step_by(2).take(256); let deq: VecDeque<_> = seq.collect(); for (i, &x) in deq.iter().enumerate() { assert_eq!(2 * i, x); } assert_eq!(deq.len(), 256); } #[test] fn test_clone() { let mut d = VecDeque::new(); d.push_front(17); d.push_front(42); d.push_back(137); d.push_back(137); assert_eq!(d.len(), 4); let mut e = d.clone(); assert_eq!(e.len(), 4); while !d.is_empty() { assert_eq!(d.pop_back(), e.pop_back()); } assert_eq!(d.len(), 0); assert_eq!(e.len(), 0); } #[test] fn test_eq() { let mut d = VecDeque::new(); assert!(d == VecDeque::with_capacity(0)); d.push_front(137); d.push_front(17); d.push_front(42); d.push_back(137); let mut e = VecDeque::with_capacity(0); e.push_back(42); e.push_back(17); e.push_back(137); e.push_back(137); assert!(&e == &d); e.pop_back(); e.push_back(0); assert!(e != d); e.clear(); assert!(e == VecDeque::new()); } #[test] fn test_partial_eq_array() { let d = VecDeque::::new(); assert!(d == []); let mut d = VecDeque::new(); d.push_front('a'); assert!(d == ['a']); let mut d = VecDeque::new(); d.push_back('a'); assert!(d == ['a']); let mut d = VecDeque::new(); d.push_back('a'); d.push_back('b'); assert!(d == ['a', 'b']); } #[test] fn test_hash() { let mut x = VecDeque::new(); let mut y = VecDeque::new(); x.push_back(1); x.push_back(2); x.push_back(3); y.push_back(0); y.push_back(1); y.pop_front(); y.push_back(2); y.push_back(3); assert!(hash(&x) == hash(&y)); } #[test] fn test_hash_after_rotation() { // test that two deques hash equal even if elements are laid out differently let len = 28; let mut ring: VecDeque = (0..len as i32).collect(); let orig = ring.clone(); for _ in 0..ring.capacity() { // shift values 1 step to the right by pop, sub one, push ring.pop_front(); for elt in &mut ring { *elt -= 1; } ring.push_back(len - 1); assert_eq!(hash(&orig), hash(&ring)); assert_eq!(orig, ring); assert_eq!(ring, orig); } } #[test] fn test_eq_after_rotation() { // test that two deques are equal even if elements are laid out differently let len = 28; let mut ring: VecDeque = (0..len as i32).collect(); let mut shifted = ring.clone(); for _ in 0..10 { // shift values 1 step to the right by pop, sub one, push ring.pop_front(); for elt in &mut ring { *elt -= 1; } ring.push_back(len - 1); } // try every shift for _ in 0..shifted.capacity() { shifted.pop_front(); for elt in &mut shifted { *elt -= 1; } shifted.push_back(len - 1); assert_eq!(shifted, ring); assert_eq!(ring, shifted); } } #[test] fn test_ord() { let x = VecDeque::new(); let mut y = VecDeque::new(); y.push_back(1); y.push_back(2); y.push_back(3); assert!(x < y); assert!(y > x); assert!(x <= x); assert!(x >= x); } #[test] fn test_show() { let ringbuf: VecDeque<_> = (0..10).collect(); assert_eq!(format!("{ringbuf:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect(); assert_eq!(format!("{ringbuf:?}"), "[\"just\", \"one\", \"test\", \"more\"]"); } #[test] fn test_drop() { static mut DROPS: i32 = 0; struct Elem; impl Drop for Elem { fn drop(&mut self) { unsafe { DROPS += 1; } } } let mut ring = VecDeque::new(); ring.push_back(Elem); ring.push_front(Elem); ring.push_back(Elem); ring.push_front(Elem); drop(ring); assert_eq!(unsafe { DROPS }, 4); } #[test] fn test_drop_with_pop() { static mut DROPS: i32 = 0; struct Elem; impl Drop for Elem { fn drop(&mut self) { unsafe { DROPS += 1; } } } let mut ring = VecDeque::new(); ring.push_back(Elem); ring.push_front(Elem); ring.push_back(Elem); ring.push_front(Elem); drop(ring.pop_back()); drop(ring.pop_front()); assert_eq!(unsafe { DROPS }, 2); drop(ring); assert_eq!(unsafe { DROPS }, 4); } #[test] fn test_drop_clear() { static mut DROPS: i32 = 0; struct Elem; impl Drop for Elem { fn drop(&mut self) { unsafe { DROPS += 1; } } } let mut ring = VecDeque::new(); ring.push_back(Elem); ring.push_front(Elem); ring.push_back(Elem); ring.push_front(Elem); ring.clear(); assert_eq!(unsafe { DROPS }, 4); drop(ring); assert_eq!(unsafe { DROPS }, 4); } #[test] #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_drop_panic() { static mut DROPS: i32 = 0; struct D(bool); impl Drop for D { fn drop(&mut self) { unsafe { DROPS += 1; } if self.0 { panic!("panic in `drop`"); } } } let mut q = VecDeque::new(); q.push_back(D(false)); q.push_back(D(false)); q.push_back(D(false)); q.push_back(D(false)); q.push_back(D(false)); q.push_front(D(false)); q.push_front(D(false)); q.push_front(D(true)); catch_unwind(move || drop(q)).ok(); assert_eq!(unsafe { DROPS }, 8); } #[test] fn test_reserve_grow() { // test growth path A // [T o o H] -> [T o o H . . . . ] let mut ring = VecDeque::with_capacity(4); for i in 0..3 { ring.push_back(i); } ring.reserve(7); for i in 0..3 { assert_eq!(ring.pop_front(), Some(i)); } // test growth path B // [H T o o] -> [. T o o H . . . ] let mut ring = VecDeque::with_capacity(4); for i in 0..1 { ring.push_back(i); assert_eq!(ring.pop_front(), Some(i)); } for i in 0..3 { ring.push_back(i); } ring.reserve(7); for i in 0..3 { assert_eq!(ring.pop_front(), Some(i)); } // test growth path C // [o o H T] -> [o o H . . . . T ] let mut ring = VecDeque::with_capacity(4); for i in 0..3 { ring.push_back(i); assert_eq!(ring.pop_front(), Some(i)); } for i in 0..3 { ring.push_back(i); } ring.reserve(7); for i in 0..3 { assert_eq!(ring.pop_front(), Some(i)); } } #[test] fn test_get() { let mut ring = VecDeque::new(); ring.push_back(0); assert_eq!(ring.get(0), Some(&0)); assert_eq!(ring.get(1), None); ring.push_back(1); assert_eq!(ring.get(0), Some(&0)); assert_eq!(ring.get(1), Some(&1)); assert_eq!(ring.get(2), None); ring.push_back(2); assert_eq!(ring.get(0), Some(&0)); assert_eq!(ring.get(1), Some(&1)); assert_eq!(ring.get(2), Some(&2)); assert_eq!(ring.get(3), None); assert_eq!(ring.pop_front(), Some(0)); assert_eq!(ring.get(0), Some(&1)); assert_eq!(ring.get(1), Some(&2)); assert_eq!(ring.get(2), None); assert_eq!(ring.pop_front(), Some(1)); assert_eq!(ring.get(0), Some(&2)); assert_eq!(ring.get(1), None); assert_eq!(ring.pop_front(), Some(2)); assert_eq!(ring.get(0), None); assert_eq!(ring.get(1), None); } #[test] fn test_get_mut() { let mut ring = VecDeque::new(); for i in 0..3 { ring.push_back(i); } match ring.get_mut(1) { Some(x) => *x = -1, None => (), }; assert_eq!(ring.get_mut(0), Some(&mut 0)); assert_eq!(ring.get_mut(1), Some(&mut -1)); assert_eq!(ring.get_mut(2), Some(&mut 2)); assert_eq!(ring.get_mut(3), None); assert_eq!(ring.pop_front(), Some(0)); assert_eq!(ring.get_mut(0), Some(&mut -1)); assert_eq!(ring.get_mut(1), Some(&mut 2)); assert_eq!(ring.get_mut(2), None); } #[test] fn test_front() { let mut ring = VecDeque::new(); ring.push_back(10); ring.push_back(20); assert_eq!(ring.front(), Some(&10)); ring.pop_front(); assert_eq!(ring.front(), Some(&20)); ring.pop_front(); assert_eq!(ring.front(), None); } #[test] fn test_as_slices() { let mut ring: VecDeque = VecDeque::with_capacity(127); let cap = ring.capacity() as i32; let first = cap / 2; let last = cap - first; for i in 0..first { ring.push_back(i); let (left, right) = ring.as_slices(); let expected: Vec<_> = (0..=i).collect(); assert_eq!(left, &expected[..]); assert_eq!(right, []); } for j in -last..0 { ring.push_front(j); let (left, right) = ring.as_slices(); let expected_left: Vec<_> = (-last..=j).rev().collect(); let expected_right: Vec<_> = (0..first).collect(); assert_eq!(left, &expected_left[..]); assert_eq!(right, &expected_right[..]); } assert_eq!(ring.len() as i32, cap); assert_eq!(ring.capacity() as i32, cap); } #[test] fn test_as_mut_slices() { let mut ring: VecDeque = VecDeque::with_capacity(127); let cap = ring.capacity() as i32; let first = cap / 2; let last = cap - first; for i in 0..first { ring.push_back(i); let (left, right) = ring.as_mut_slices(); let expected: Vec<_> = (0..=i).collect(); assert_eq!(left, &expected[..]); assert_eq!(right, []); } for j in -last..0 { ring.push_front(j); let (left, right) = ring.as_mut_slices(); let expected_left: Vec<_> = (-last..=j).rev().collect(); let expected_right: Vec<_> = (0..first).collect(); assert_eq!(left, &expected_left[..]); assert_eq!(right, &expected_right[..]); } assert_eq!(ring.len() as i32, cap); assert_eq!(ring.capacity() as i32, cap); } #[test] fn test_append() { let mut a: VecDeque<_> = [1, 2, 3].into_iter().collect(); let mut b: VecDeque<_> = [4, 5, 6].into_iter().collect(); // normal append a.append(&mut b); assert_eq!(a.iter().cloned().collect::>(), [1, 2, 3, 4, 5, 6]); assert_eq!(b.iter().cloned().collect::>(), []); // append nothing to something a.append(&mut b); assert_eq!(a.iter().cloned().collect::>(), [1, 2, 3, 4, 5, 6]); assert_eq!(b.iter().cloned().collect::>(), []); // append something to nothing b.append(&mut a); assert_eq!(b.iter().cloned().collect::>(), [1, 2, 3, 4, 5, 6]); assert_eq!(a.iter().cloned().collect::>(), []); } #[test] fn test_append_permutations() { fn construct_vec_deque( push_back: usize, pop_back: usize, push_front: usize, pop_front: usize, ) -> VecDeque { let mut out = VecDeque::new(); for a in 0..push_back { out.push_back(a); } for b in 0..push_front { out.push_front(push_back + b); } for _ in 0..pop_back { out.pop_back(); } for _ in 0..pop_front { out.pop_front(); } out } // Miri is too slow let max = if cfg!(miri) { 3 } else { 5 }; // Many different permutations of both the `VecDeque` getting appended to // and the one getting appended are generated to check `append`. // This ensures all 6 code paths of `append` are tested. for src_push_back in 0..max { for src_push_front in 0..max { // doesn't pop more values than are pushed for src_pop_back in 0..(src_push_back + src_push_front) { for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) { let src = construct_vec_deque( src_push_back, src_pop_back, src_push_front, src_pop_front, ); for dst_push_back in 0..max { for dst_push_front in 0..max { for dst_pop_back in 0..(dst_push_back + dst_push_front) { for dst_pop_front in 0..(dst_push_back + dst_push_front - dst_pop_back) { let mut dst = construct_vec_deque( dst_push_back, dst_pop_back, dst_push_front, dst_pop_front, ); let mut src = src.clone(); // Assert that appending `src` to `dst` gives the same order // of values as iterating over both in sequence. let correct = dst .iter() .chain(src.iter()) .cloned() .collect::>(); dst.append(&mut src); assert_eq!(dst, correct); assert!(src.is_empty()); } } } } } } } } } struct DropCounter<'a> { count: &'a mut u32, } impl Drop for DropCounter<'_> { fn drop(&mut self) { *self.count += 1; } } #[test] fn test_append_double_drop() { let (mut count_a, mut count_b) = (0, 0); { let mut a = VecDeque::new(); let mut b = VecDeque::new(); a.push_back(DropCounter { count: &mut count_a }); b.push_back(DropCounter { count: &mut count_b }); a.append(&mut b); } assert_eq!(count_a, 1); assert_eq!(count_b, 1); } #[test] #[should_panic] fn test_append_zst_capacity_overflow() { let mut v = Vec::with_capacity(usize::MAX); // note: using resize instead of set_len here would // be *extremely* slow in unoptimized builds. // SAFETY: `v` has capacity `usize::MAX`, and no initialization // is needed for empty tuples. unsafe { v.set_len(usize::MAX) }; let mut v = VecDeque::from(v); let mut w = vec![()].into(); v.append(&mut w); } #[test] fn test_retain() { let mut buf = VecDeque::new(); buf.extend(1..5); buf.retain(|&x| x % 2 == 0); let v: Vec<_> = buf.into_iter().collect(); assert_eq!(&v[..], &[2, 4]); } #[test] fn test_extend_ref() { let mut v = VecDeque::new(); v.push_back(1); v.extend(&[2, 3, 4]); assert_eq!(v.len(), 4); assert_eq!(v[0], 1); assert_eq!(v[1], 2); assert_eq!(v[2], 3); assert_eq!(v[3], 4); let mut w = VecDeque::new(); w.push_back(5); w.push_back(6); v.extend(&w); assert_eq!(v.len(), 6); assert_eq!(v[0], 1); assert_eq!(v[1], 2); assert_eq!(v[2], 3); assert_eq!(v[3], 4); assert_eq!(v[4], 5); assert_eq!(v[5], 6); } #[test] fn test_contains() { let mut v = VecDeque::new(); v.extend(&[2, 3, 4]); assert!(v.contains(&3)); assert!(!v.contains(&1)); v.clear(); assert!(!v.contains(&3)); } #[allow(dead_code)] fn assert_covariance() { fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { d } } #[test] fn test_is_empty() { let mut v = VecDeque::::new(); assert!(v.is_empty()); assert!(v.iter().is_empty()); assert!(v.iter_mut().is_empty()); v.extend(&[2, 3, 4]); assert!(!v.is_empty()); assert!(!v.iter().is_empty()); assert!(!v.iter_mut().is_empty()); while let Some(_) = v.pop_front() { assert_eq!(v.is_empty(), v.len() == 0); assert_eq!(v.iter().is_empty(), v.iter().len() == 0); assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0); } assert!(v.is_empty()); assert!(v.iter().is_empty()); assert!(v.iter_mut().is_empty()); assert!(v.into_iter().is_empty()); } #[test] fn test_reserve_exact_2() { // This is all the same as test_reserve let mut v = VecDeque::new(); v.reserve_exact(2); assert!(v.capacity() >= 2); for i in 0..16 { v.push_back(i); } assert!(v.capacity() >= 16); v.reserve_exact(16); assert!(v.capacity() >= 32); v.push_back(16); v.reserve_exact(16); assert!(v.capacity() >= 33) } #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve() { // These are the interesting cases: // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM) // * > isize::MAX should always fail // * On 16/32-bit should CapacityOverflow // * On 64-bit should OOM // * overflow may trigger when adding `len` to `cap` (in number of elements) // * overflow may trigger when multiplying `new_cap` by size_of:: (to get bytes) const MAX_CAP: usize = isize::MAX as usize; const MAX_USIZE: usize = usize::MAX; { // Note: basic stuff is checked by test_reserve let mut empty_bytes: VecDeque = VecDeque::new(); // Check isize::MAX doesn't count as an overflow if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } // Play it again, frank! (just to be sure) if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } // Check isize::MAX + 1 does count as overflow assert_matches!( empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()), Err(CapacityOverflow), "isize::MAX + 1 should trigger an overflow!" ); // Check usize::MAX does count as overflow assert_matches!( empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()), Err(CapacityOverflow), "usize::MAX should trigger an overflow!" ); } { // Same basic idea, but with non-zero len let mut ten_bytes: VecDeque = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } assert_matches!( ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()), Err(CapacityOverflow), "isize::MAX + 1 should trigger an overflow!" ); // Should always overflow in the add-to-len assert_matches!( ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()), Err(CapacityOverflow), "usize::MAX should trigger an overflow!" ); } { // Same basic idea, but with interesting type size let mut ten_u32s: VecDeque = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } assert_matches!( ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()), Err(CapacityOverflow), "isize::MAX + 1 should trigger an overflow!" ); // Should fail in the mul-by-size assert_matches!( ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()), Err(CapacityOverflow), "usize::MAX should trigger an overflow!" ); } } #[test] #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc fn test_try_reserve_exact() { // This is exactly the same as test_try_reserve with the method changed. // See that test for comments. const MAX_CAP: usize = isize::MAX as usize; const MAX_USIZE: usize = usize::MAX; { let mut empty_bytes: VecDeque = VecDeque::new(); if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } assert_matches!( empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()), Err(CapacityOverflow), "isize::MAX + 1 should trigger an overflow!" ); assert_matches!( empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()), Err(CapacityOverflow), "usize::MAX should trigger an overflow!" ); } { let mut ten_bytes: VecDeque = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } assert_matches!( ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()), Err(CapacityOverflow), "isize::MAX + 1 should trigger an overflow!" ); assert_matches!( ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()), Err(CapacityOverflow), "usize::MAX should trigger an overflow!" ); } { let mut ten_u32s: VecDeque = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind()) { panic!("isize::MAX shouldn't trigger an overflow!"); } assert_matches!( ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()), Err(CapacityOverflow), "isize::MAX + 1 should trigger an overflow!" ); assert_matches!( ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()), Err(CapacityOverflow), "usize::MAX should trigger an overflow!" ); } } #[test] fn test_rotate_nop() { let mut v: VecDeque<_> = (0..10).collect(); assert_unchanged(&v); v.rotate_left(0); assert_unchanged(&v); v.rotate_left(10); assert_unchanged(&v); v.rotate_right(0); assert_unchanged(&v); v.rotate_right(10); assert_unchanged(&v); v.rotate_left(3); v.rotate_right(3); assert_unchanged(&v); v.rotate_right(3); v.rotate_left(3); assert_unchanged(&v); v.rotate_left(6); v.rotate_right(6); assert_unchanged(&v); v.rotate_right(6); v.rotate_left(6); assert_unchanged(&v); v.rotate_left(3); v.rotate_left(7); assert_unchanged(&v); v.rotate_right(4); v.rotate_right(6); assert_unchanged(&v); v.rotate_left(1); v.rotate_left(2); v.rotate_left(3); v.rotate_left(4); assert_unchanged(&v); v.rotate_right(1); v.rotate_right(2); v.rotate_right(3); v.rotate_right(4); assert_unchanged(&v); fn assert_unchanged(v: &VecDeque) { assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); } } #[test] fn test_rotate_left_parts() { let mut v: VecDeque<_> = VecDeque::with_capacity(8); v.extend(1..=7); v.rotate_left(2); assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..])); v.rotate_left(2); assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..])); v.rotate_left(2); assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..])); v.rotate_left(2); assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..])); v.rotate_left(2); assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..])); v.rotate_left(2); assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..])); v.rotate_left(2); assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..])); } #[test] fn test_rotate_right_parts() { let mut v: VecDeque<_> = VecDeque::with_capacity(8); v.extend(1..=7); v.rotate_right(2); assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..])); v.rotate_right(2); assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..])); v.rotate_right(2); assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..])); v.rotate_right(2); assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..])); v.rotate_right(2); assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..])); v.rotate_right(2); assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..])); v.rotate_right(2); assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..])); } #[test] fn test_rotate_left_random() { let shifts = [ 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, 12, 9, 11, 1, 7, 9, 7, 2, ]; let n = 12; let mut v: VecDeque<_> = (0..n).collect(); let mut total_shift = 0; for shift in shifts.iter().cloned() { v.rotate_left(shift); total_shift += shift; for i in 0..n { assert_eq!(v[i], (i + total_shift) % n); } } } #[test] fn test_rotate_right_random() { let shifts = [ 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, 12, 9, 11, 1, 7, 9, 7, 2, ]; let n = 12; let mut v: VecDeque<_> = (0..n).collect(); let mut total_shift = 0; for shift in shifts.iter().cloned() { v.rotate_right(shift); total_shift += shift; for i in 0..n { assert_eq!(v[(i + total_shift) % n], i); } } } #[test] fn test_try_fold_empty() { assert_eq!(Some(0), VecDeque::::new().iter().try_fold(0, |_, _| None)); } #[test] fn test_try_fold_none() { let v: VecDeque = (0..12).collect(); assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None })); } #[test] fn test_try_fold_ok() { let v: VecDeque = (0..12).collect(); assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b))); } #[test] fn test_try_fold_unit() { let v: VecDeque<()> = std::iter::repeat(()).take(42).collect(); assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(()))); } #[test] fn test_try_fold_unit_none() { let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect(); let mut iter = v.into_iter(); assert!(iter.try_fold((), |_, _| None).is_none()); assert_eq!(iter.len(), 9); } #[test] fn test_try_fold_rotated() { let mut v: VecDeque<_> = (0..12).collect(); for n in 0..10 { if n & 1 == 0 { v.rotate_left(n); } else { v.rotate_right(n); } assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b))); } } #[test] fn test_try_fold_moves_iter() { let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect(); let mut iter = v.into_iter(); assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None); assert_eq!(iter.next(), Some(&60)); } #[test] fn test_try_fold_exhaust_wrap() { let mut v = VecDeque::with_capacity(7); v.push_back(1); v.push_back(1); v.push_back(1); v.pop_front(); v.pop_front(); let mut iter = v.iter(); let _ = iter.try_fold(0, |_, _| Some(1)); assert!(iter.is_empty()); } #[test] fn test_try_fold_wraparound() { let mut v = VecDeque::with_capacity(8); v.push_back(7); v.push_back(8); v.push_back(9); v.push_front(2); v.push_front(1); let mut iter = v.iter(); let _ = iter.find(|&&x| x == 2); assert_eq!(Some(&7), iter.next()); } #[test] fn test_try_rfold_rotated() { let mut v: VecDeque<_> = (0..12).collect(); for n in 0..10 { if n & 1 == 0 { v.rotate_left(n); } else { v.rotate_right(n); } assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b))); } } #[test] fn test_try_rfold_moves_iter() { let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect(); let mut iter = v.into_iter(); assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None); assert_eq!(iter.next_back(), Some(&70)); } #[test] #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn truncate_leak() { static mut DROPS: i32 = 0; struct D(bool); impl Drop for D { fn drop(&mut self) { unsafe { DROPS += 1; } if self.0 { panic!("panic in `drop`"); } } } let mut q = VecDeque::new(); q.push_back(D(false)); q.push_back(D(false)); q.push_back(D(false)); q.push_back(D(false)); q.push_back(D(false)); q.push_front(D(true)); q.push_front(D(false)); q.push_front(D(false)); catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok(); assert_eq!(unsafe { DROPS }, 7); } #[test] #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_drain_leak() { static mut DROPS: i32 = 0; #[derive(Debug, PartialEq)] struct D(u32, bool); impl Drop for D { fn drop(&mut self) { unsafe { DROPS += 1; } if self.1 { panic!("panic in `drop`"); } } } let mut v = VecDeque::new(); v.push_back(D(4, false)); v.push_back(D(5, false)); v.push_back(D(6, false)); v.push_front(D(3, false)); v.push_front(D(2, true)); v.push_front(D(1, false)); v.push_front(D(0, false)); catch_unwind(AssertUnwindSafe(|| { v.drain(1..=4); })) .ok(); assert_eq!(unsafe { DROPS }, 4); assert_eq!(v.len(), 3); drop(v); assert_eq!(unsafe { DROPS }, 7); } #[test] fn test_binary_search() { // Contiguous (front only) search: let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into(); assert!(deque.as_slices().1.is_empty()); assert_eq!(deque.binary_search(&3), Ok(2)); assert_eq!(deque.binary_search(&4), Err(3)); // Split search (both front & back non-empty): let mut deque: VecDeque<_> = vec![5, 6].into(); deque.push_front(3); deque.push_front(2); deque.push_front(1); deque.push_back(10); assert!(!deque.as_slices().0.is_empty()); assert!(!deque.as_slices().1.is_empty()); assert_eq!(deque.binary_search(&0), Err(0)); assert_eq!(deque.binary_search(&1), Ok(0)); assert_eq!(deque.binary_search(&5), Ok(3)); assert_eq!(deque.binary_search(&7), Err(5)); assert_eq!(deque.binary_search(&20), Err(6)); } #[test] fn test_binary_search_by() { let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into(); assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&3)), Ok(2)); assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&4)), Err(3)); } #[test] fn test_binary_search_by_key() { let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into(); assert_eq!(deque.binary_search_by_key(&3, |&(v,)| v), Ok(2)); assert_eq!(deque.binary_search_by_key(&4, |&(v,)| v), Err(3)); } #[test] fn test_partition_point() { // Contiguous (front only) search: let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into(); assert!(deque.as_slices().1.is_empty()); assert_eq!(deque.partition_point(|&v| v <= 3), 3); // Split search (both front & back non-empty): let mut deque: VecDeque<_> = vec![5, 6].into(); deque.push_front(3); deque.push_front(2); deque.push_front(1); deque.push_back(10); assert!(!deque.as_slices().0.is_empty()); assert!(!deque.as_slices().1.is_empty()); assert_eq!(deque.partition_point(|&v| v <= 5), 4); } #[test] fn test_zero_sized_push() { const N: usize = 8; // Zero sized type struct Zst; // Test that for all possible sequences of push_front / push_back, // we end up with a deque of the correct size for len in 0..N { let mut tester = VecDeque::with_capacity(len); assert_eq!(tester.len(), 0); assert!(tester.capacity() >= len); for case in 0..(1 << len) { assert_eq!(tester.len(), 0); for bit in 0..len { if case & (1 << bit) != 0 { tester.push_front(Zst); } else { tester.push_back(Zst); } } assert_eq!(tester.len(), len); assert_eq!(tester.iter().count(), len); tester.clear(); } } } #[test] fn test_from_zero_sized_vec() { let v = vec![(); 100]; let queue = VecDeque::from(v); assert_eq!(queue.len(), 100); } #[test] fn test_resize_keeps_reserved_space_from_item() { let v = Vec::::with_capacity(1234); let mut d = VecDeque::new(); d.resize(1, v); assert_eq!(d[0].capacity(), 1234); } #[test] fn test_collect_from_into_iter_keeps_allocation() { let mut v = Vec::with_capacity(13); v.extend(0..7); check(v.as_ptr(), v.last().unwrap(), v.into_iter()); let mut v = VecDeque::with_capacity(13); v.extend(0..7); check(&v[0], &v[v.len() - 1], v.into_iter()); fn check(buf: *const i32, last: *const i32, mut it: impl Iterator) { assert_eq!(it.next(), Some(0)); assert_eq!(it.next(), Some(1)); let mut v: VecDeque = it.collect(); assert_eq!(v.capacity(), 13); assert_eq!(v.as_slices().0.as_ptr(), buf.wrapping_add(2)); assert_eq!(&v[v.len() - 1] as *const _, last); assert_eq!(v.as_slices(), ([2, 3, 4, 5, 6].as_slice(), [].as_slice())); v.push_front(7); assert_eq!(v.as_slices(), ([7, 2, 3, 4, 5, 6].as_slice(), [].as_slice())); v.push_front(8); assert_eq!(v.as_slices(), ([8, 7, 2, 3, 4, 5, 6].as_slice(), [].as_slice())); // Now that we've adding thing in place of the two that we removed from // the front of the iterator, we're back to matching the buffer pointer. assert_eq!(v.as_slices().0.as_ptr(), buf); assert_eq!(&v[v.len() - 1] as *const _, last); v.push_front(9); assert_eq!(v.as_slices(), ([9].as_slice(), [8, 7, 2, 3, 4, 5, 6].as_slice())); assert_eq!(v.capacity(), 13); } }