user0/rust
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
rust/library/alloctests/tests/vec_deque.rs
Jeremy Smart b0d96492d0
fix undefined behavior in VecDeque::splice
2026-01-27 19:30:37 -05:00

2349 lines
65 KiB
Rust
Raw Permalink Blame History

use core::cell::Cell;
use core::num::NonZero;
use std::assert_matches;
use std::collections::TryReserveErrorKind::*;
use std::collections::VecDeque;
use std::collections::vec_deque::Drain;
use std::fmt::Debug;
use std::ops::Bound::*;
use std::panic::{AssertUnwindSafe, catch_unwind};
use Taggy::*;
use Taggypar::*;
use crate::hash;
use crate::testing::macros::struct_with_counted_drop;
#[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<T: Clone + PartialEq + Debug>(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_pop_if() {
let mut deq: VecDeque<_> = vec![0, 1, 2, 3, 4].into();
let pred = |x: &mut i32| *x % 2 == 0;
assert_eq!(deq.pop_front_if(pred), Some(0));
assert_eq!(deq, [1, 2, 3, 4]);
assert_eq!(deq.pop_front_if(pred), None);
assert_eq!(deq, [1, 2, 3, 4]);
assert_eq!(deq.pop_back_if(pred), Some(4));
assert_eq!(deq, [1, 2, 3]);
assert_eq!(deq.pop_back_if(pred), None);
assert_eq!(deq, [1, 2, 3]);
}
#[test]
fn test_pop_if_empty() {
let mut deq = VecDeque::<i32>::new();
assert_eq!(deq.pop_front_if(|_| true), None);
assert_eq!(deq.pop_back_if(|_| true), None);
assert!(deq.is_empty());
}
#[test]
fn test_pop_if_mutates() {
let mut v: VecDeque<_> = vec![-1, 1].into();
let pred = |x: &mut i32| {
*x *= 2;
false
};
assert_eq!(v.pop_front_if(pred), None);
assert_eq!(v, [-2, 1]);
assert_eq!(v.pop_back_if(pred), None);
assert_eq!(v, [-2, 2]);
}
#[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<T> {
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::<i32>(5, 72, 64, 175);
}
#[test]
fn test_param_taggy() {
test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
}
#[test]
fn test_param_taggypar() {
test_parameterized::<Taggypar<i32>>(
Onepar::<i32>(1),
Twopar::<i32>(1, 2),
Threepar::<i32>(1, 2, 3),
Twopar::<i32>(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::<RecCy>(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::<Vec<_>>(), [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::<Vec<_>>(), 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::<Vec<_>>(), 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::<Vec<_>>(), 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::<Vec<_>>(), 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<_>>(), 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<i32> = 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::<Vec<_>>(), 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::<Vec<_>>(), 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(NonZero::new(5).unwrap()));
let mut it = VecDeque::from(vec![1, 2, 3, 4, 5]).into_iter();
assert_eq!(it.advance_back_by(10), Err(NonZero::new(5).unwrap()));
}
}
#[test]
fn test_drain() {
// Empty iter
{
let mut d: VecDeque<i32> = 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::<Vec<_>>(), [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::<Vec<_>>(), [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::<char>::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<i32> = (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<i32> = (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() {
struct_with_counted_drop!(Elem, DROPS);
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!(DROPS.get(), 4);
}
#[test]
fn test_drop_with_pop() {
struct_with_counted_drop!(Elem, DROPS);
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!(DROPS.get(), 2);
drop(ring);
assert_eq!(DROPS.get(), 4);
}
#[test]
fn test_drop_clear() {
struct_with_counted_drop!(Elem, DROPS);
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!(DROPS.get(), 4);
drop(ring);
assert_eq!(DROPS.get(), 4);
}
#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn test_drop_panic() {
struct_with_counted_drop!(D(bool), DROPS => |this: &D| if this.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!(DROPS.get(), 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<i32> = 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<i32> = 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::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
// append nothing to something
a.append(&mut b);
assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
// append something to nothing
b.append(&mut a);
assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
}
#[test]
fn test_append_permutations() {
fn construct_vec_deque(
push_back: usize,
pop_back: usize,
push_front: usize,
pop_front: usize,
) -> VecDeque<usize> {
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::<Vec<usize>>();
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::<i32>::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
fn test_try_with_capacity() {
let vec: VecDeque<u32> = VecDeque::try_with_capacity(5).unwrap();
assert_eq!(0, vec.len());
assert!(vec.capacity() >= 5 && vec.capacity() <= isize::MAX as usize / 4);
assert!(VecDeque::<u16>::try_with_capacity(isize::MAX as usize + 1).is_err());
}
#[test]
#[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
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::<T> (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<u8> = 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<u8> = [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<u32> = [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
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<u8> = 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<u8> = [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<u32> = [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<i32>) {
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::<u32>::new().iter().try_fold(0, |_, _| None));
}
#[test]
fn test_try_fold_none() {
let v: VecDeque<u32> = (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<u32> = (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() {
struct_with_counted_drop!(D(bool), DROPS => |this: &D| if this.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!(DROPS.get(), 7);
}
#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn truncate_front_leak() {
struct_with_counted_drop!(D(bool), DROPS => |this: &D| if this.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_front(1))).ok();
assert_eq!(DROPS.get(), 7);
}
#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn test_drain_leak() {
struct_with_counted_drop!(D(u32, bool), DROPS => |this: &D| if this.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!(DROPS.get(), 4);
assert_eq!(v.len(), 3);
drop(v);
assert_eq!(DROPS.get(), 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::<i32>::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<Item = i32>) {
assert_eq!(it.next(), Some(0));
assert_eq!(it.next(), Some(1));
let mut v: VecDeque<i32> = 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);
}
}
#[test]
fn test_truncate_front() {
let mut v = VecDeque::with_capacity(13);
v.extend(0..7);
assert_eq!(v.as_slices(), ([0, 1, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
v.truncate_front(10);
assert_eq!(v.len(), 7);
assert_eq!(v.as_slices(), ([0, 1, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
v.truncate_front(7);
assert_eq!(v.len(), 7);
assert_eq!(v.as_slices(), ([0, 1, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
v.truncate_front(3);
assert_eq!(v.as_slices(), ([4, 5, 6].as_slice(), [].as_slice()));
assert_eq!(v.len(), 3);
v.truncate_front(0);
assert_eq!(v.as_slices(), ([].as_slice(), [].as_slice()));
assert_eq!(v.len(), 0);
v.clear();
v.extend(0..7);
assert_eq!(v.as_slices(), ([0, 1, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
v.push_front(9);
v.push_front(8);
v.push_front(7);
assert_eq!(v.as_slices(), ([7, 8, 9].as_slice(), [0, 1, 2, 3, 4, 5, 6].as_slice()));
v.truncate_front(12);
assert_eq!(v.as_slices(), ([7, 8, 9].as_slice(), [0, 1, 2, 3, 4, 5, 6].as_slice()));
v.truncate_front(10);
assert_eq!(v.as_slices(), ([7, 8, 9].as_slice(), [0, 1, 2, 3, 4, 5, 6].as_slice()));
v.truncate_front(8);
assert_eq!(v.as_slices(), ([9].as_slice(), [0, 1, 2, 3, 4, 5, 6].as_slice()));
v.truncate_front(5);
assert_eq!(v.as_slices(), ([2, 3, 4, 5, 6].as_slice(), [].as_slice()));
}
#[test]
fn test_extend_from_within() {
let mut v = VecDeque::with_capacity(8);
v.extend(0..6);
v.truncate_front(4);
assert_eq!(v, [2, 3, 4, 5]);
v.extend_from_within(1..4);
assert_eq!(v, [2, 3, 4, 5, 3, 4, 5]);
// check it really wrapped
assert_eq!(v.as_slices(), ([2, 3, 4, 5, 3, 4].as_slice(), [5].as_slice()));
v.extend_from_within(1..=2);
assert_eq!(v, [2, 3, 4, 5, 3, 4, 5, 3, 4]);
v.extend_from_within(..3);
assert_eq!(v, [2, 3, 4, 5, 3, 4, 5, 3, 4, 2, 3, 4]);
}
/// Struct that allows tracking clone and drop calls and can be set to panic on calling clone.
struct CloneTracker<'a> {
id: usize,
// Counters can be set to None if not needed.
clone: Option<&'a Cell<u32>>,
drop: Option<&'a Cell<u32>>,
panic: bool,
}
impl<'a> CloneTracker<'a> {
pub const DUMMY: Self = Self { id: 999, clone: None, drop: None, panic: false };
}
impl<'a> Clone for CloneTracker<'a> {
fn clone(&self) -> Self {
if self.panic {
panic!();
}
if let Some(clone_count) = self.clone {
clone_count.update(|c| c + 1);
}
Self { id: self.id, clone: self.clone, drop: self.drop, panic: false }
}
}
impl<'a> Drop for CloneTracker<'a> {
fn drop(&mut self) {
if let Some(drop_count) = self.drop {
drop_count.update(|c| c + 1);
}
}
}
#[test]
fn test_extend_from_within_clone() {
let clone_counts = [const { Cell::new(0) }; 4];
let mut v = VecDeque::with_capacity(10);
// insert 2 dummy elements to have the buffer wrap later
v.extend([CloneTracker::DUMMY; 2]);
v.extend(clone_counts.iter().enumerate().map(|(id, clone_count)| CloneTracker {
id,
clone: Some(clone_count),
drop: None,
panic: false,
}));
// remove the dummy elements
v.truncate_front(4);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 2, 3]);
v.extend_from_within(2..);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 2, 3, 2, 3]);
// elements at index 2 and 3 should have been cloned once
assert_eq!(clone_counts.each_ref().map(Cell::get), [0, 0, 1, 1]);
// it is important that the deque wraps because of this operation, we want to test if wrapping is handled correctly
v.extend_from_within(1..5);
// total length is 10, 8 in the first part and 2 in the second part
assert_eq!(v.as_slices().0.len(), 8);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 2, 3, 2, 3, 1, 2, 3, 2]);
// the new elements are from indices 1, 2, 3 and 2, those elements should have their clone count
// incremented (clone count at index 2 gets incremented twice so ends up at 3)
assert_eq!(clone_counts.each_ref().map(Cell::get), [0, 1, 3, 2]);
}
#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn test_extend_from_within_clone_panic() {
let clone_counts = [const { Cell::new(0) }; 4];
let drop_count = Cell::new(0);
let mut v = VecDeque::with_capacity(8);
// insert 2 dummy elements to have the buffer wrap later
v.extend([CloneTracker::DUMMY; 2]);
v.extend(clone_counts.iter().enumerate().map(|(id, clone_count)| CloneTracker {
id,
clone: Some(clone_count),
drop: Some(&drop_count),
panic: false,
}));
// remove the dummy elements
v.truncate_front(4);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 2, 3]);
// panic after wrapping
v[2].panic = true;
catch_unwind(AssertUnwindSafe(|| {
v.extend_from_within(..);
}))
.unwrap_err();
v[2].panic = false;
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 2, 3, 0, 1]);
// the first 2 elements were cloned
assert_eq!(clone_counts.each_ref().map(Cell::get), [1, 1, 0, 0]);
// nothing should have been dropped
assert_eq!(drop_count.get(), 0);
v.truncate_front(2);
assert_eq!(drop_count.get(), 4);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1]);
// panic before wrapping
v[1].panic = true;
catch_unwind(AssertUnwindSafe(|| {
v.extend_from_within(..);
}))
.unwrap_err();
v[1].panic = false;
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 0]);
// only the first element was cloned
assert_eq!(clone_counts.each_ref().map(Cell::get), [2, 1, 0, 0]);
// nothing more should have been dropped
assert_eq!(drop_count.get(), 4);
}
#[test]
fn test_prepend_from_within() {
let mut v = VecDeque::with_capacity(8);
v.extend(0..6);
v.truncate_front(4);
v.prepend_from_within(..=0);
assert_eq!(v.as_slices(), ([2, 2, 3, 4, 5].as_slice(), [].as_slice()));
v.prepend_from_within(2..);
assert_eq!(v.as_slices(), ([3, 4].as_slice(), [5, 2, 2, 3, 4, 5].as_slice()));
v.prepend_from_within(..);
assert_eq!(v, [[3, 4, 5, 2, 2, 3, 4, 5]; 2].as_flattened());
}
#[test]
fn test_prepend_from_within_clone() {
let clone_counts = [const { Cell::new(0) }; 4];
// insert 2 dummy elements to have the buffer wrap later
let mut v = VecDeque::with_capacity(10);
v.extend([CloneTracker::DUMMY; 2]);
v.extend(clone_counts.iter().enumerate().map(|(id, clone_count)| CloneTracker {
id,
clone: Some(clone_count),
drop: None,
panic: false,
}));
// remove the dummy elements
v.truncate_front(4);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 2, 3]);
v.prepend_from_within(..2);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 0, 1, 2, 3]);
v.prepend_from_within(1..5);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [1, 0, 1, 2, 0, 1, 0, 1, 2, 3]);
// count the number of each element and subtract one (clone should have been called n-1 times if we have n elements)
// example: 0 appears 3 times so should have been cloned twice, 1 appears 4 times so cloned 3 times, etc
assert_eq!(clone_counts.each_ref().map(Cell::get), [2, 3, 1, 0]);
}
#[test]
#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
fn test_prepend_from_within_clone_panic() {
let clone_counts = [const { Cell::new(0) }; 4];
let drop_count = Cell::new(0);
let mut v = VecDeque::with_capacity(8);
// insert 2 dummy elements to have the buffer wrap later
v.extend([CloneTracker::DUMMY; 2]);
v.extend(clone_counts.iter().enumerate().map(|(id, clone_count)| CloneTracker {
id,
clone: Some(clone_count),
drop: Some(&drop_count),
panic: false,
}));
// remove the dummy elements
v.truncate_front(4);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [0, 1, 2, 3]);
// panic after wrapping
v[1].panic = true;
catch_unwind(AssertUnwindSafe(|| {
v.prepend_from_within(..);
}))
.unwrap_err();
v[1].panic = false;
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [2, 3, 0, 1, 2, 3]);
// the last 2 elements were cloned
assert_eq!(clone_counts.each_ref().map(Cell::get), [0, 0, 1, 1]);
// nothing should have been dropped
assert_eq!(drop_count.get(), 0);
v.truncate_front(2);
assert_eq!(drop_count.get(), 4);
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [2, 3]);
// panic before wrapping
v[0].panic = true;
catch_unwind(AssertUnwindSafe(|| {
v.prepend_from_within(..);
}))
.unwrap_err();
v[0].panic = false;
assert_eq!(v.iter().map(|tr| tr.id).collect::<Vec<_>>(), [3, 2, 3]);
// only the first element was cloned
assert_eq!(clone_counts.each_ref().map(Cell::get), [0, 0, 1, 2]);
// nothing more should have been dropped
assert_eq!(drop_count.get(), 4);
}
#[test]
fn test_extend_and_prepend_from_within() {
let mut v = ('0'..='9').map(String::from).collect::<VecDeque<_>>();
v.truncate_front(5);
v.extend_from_within(4..);
v.prepend_from_within(..2);
assert_eq!(v.iter().map(|s| &**s).collect::<String>(), "56567899");
v.clear();
v.extend(['1', '2', '3'].map(String::from));
v.prepend_from_within(..);
v.extend_from_within(..);
assert_eq!(v.iter().map(|s| &**s).collect::<String>(), "123123123123");
}
#[test]
fn test_extend_front() {
let mut v = VecDeque::new();
v.extend_front(0..3);
assert_eq!(v, [2, 1, 0]);
v.extend_front(3..6);
assert_eq!(v, [5, 4, 3, 2, 1, 0]);
v.prepend([1; 4]);
assert_eq!(v, [1, 1, 1, 1, 5, 4, 3, 2, 1, 0]);
let mut v = VecDeque::with_capacity(8);
let cap = v.capacity();
v.extend(0..4);
v.truncate_front(2);
v.extend_front(4..8);
assert_eq!(v.as_slices(), ([7, 6].as_slice(), [5, 4, 2, 3].as_slice()));
assert_eq!(v.capacity(), cap);
let mut v = VecDeque::new();
v.extend_front([]);
v.extend_front(None);
v.extend_front(vec![]);
v.prepend([]);
v.prepend(None);
v.prepend(vec![]);
assert_eq!(v.capacity(), 0);
v.extend_front(Some(123));
assert_eq!(v, [123]);
}
#[test]
fn test_extend_front_specialization_vec_into_iter() {
// trigger 4 code paths: all combinations of prepend and extend_front, wrap and no wrap
let mut v = VecDeque::with_capacity(4);
v.prepend(vec![1, 2, 3]);
assert_eq!(v, [1, 2, 3]);
v.pop_back();
// this should wrap around the physical buffer
v.prepend(vec![-1, 0]);
// check it really wrapped
assert_eq!(v.as_slices(), ([-1].as_slice(), [0, 1, 2].as_slice()));
let mut v = VecDeque::with_capacity(4);
v.extend_front(vec![1, 2, 3]);
assert_eq!(v, [3, 2, 1]);
v.pop_back();
// this should wrap around the physical buffer
v.extend_front(vec![4, 5]);
// check it really wrapped
assert_eq!(v.as_slices(), ([5].as_slice(), [4, 3, 2].as_slice()));
}
#[test]
fn test_extend_front_specialization_copy_slice() {
// trigger 4 code paths: all combinations of prepend and extend_front, wrap and no wrap
let mut v = VecDeque::with_capacity(4);
v.prepend([1, 2, 3].as_slice().iter().copied());
assert_eq!(v, [1, 2, 3]);
v.pop_back();
// this should wrap around the physical buffer
v.prepend([-1, 0].as_slice().iter().copied());
// check it really wrapped
assert_eq!(v.as_slices(), ([-1].as_slice(), [0, 1, 2].as_slice()));
let mut v = VecDeque::with_capacity(4);
v.extend_front([1, 2, 3].as_slice().iter().copied());
assert_eq!(v, [3, 2, 1]);
v.pop_back();
// this should wrap around the physical buffer
v.extend_front([4, 5].as_slice().iter().copied());
// check it really wrapped
assert_eq!(v.as_slices(), ([5].as_slice(), [4, 3, 2].as_slice()));
}
#[test]
fn test_extend_front_specialization_deque_drain() {
// trigger 8 code paths: all combinations of prepend and extend_front, wrap and no wrap (src deque), wrap and no wrap (dst deque)
/// Get deque containing `[1, 2, 3, 4]`, possibly wrapping in the middle (between the 2 and 3).
fn test_deque(wrap: bool) -> VecDeque<i32> {
if wrap {
let mut v = VecDeque::with_capacity(4);
v.extend([3, 4]);
v.prepend([1, 2]);
assert_eq!(v.as_slices(), ([1, 2].as_slice(), [3, 4].as_slice()));
v
} else {
VecDeque::from([1, 2, 3, 4])
}
}
// prepend, v2.head == 0
let mut v1 = VecDeque::with_capacity(7);
let mut v2 = test_deque(false);
v1.prepend(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
assert_eq!(v1, [1, 2, 3, 4]);
v1.pop_back();
let mut v2 = test_deque(false);
// this should wrap around the physical buffer
v1.prepend(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
// check it really wrapped
assert_eq!(v1.as_slices(), ([1].as_slice(), [2, 3, 4, 1, 2, 3].as_slice()));
// extend_front, v2.head == 0
let mut v1 = VecDeque::with_capacity(7);
let mut v2 = test_deque(false);
v1.extend_front(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
assert_eq!(v1, [4, 3, 2, 1]);
v1.pop_back();
let mut v2 = test_deque(false);
// this should wrap around the physical buffer
v1.extend_front(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
// check it really wrapped
assert_eq!(v1.as_slices(), ([4].as_slice(), [3, 2, 1, 4, 3, 2].as_slice()));
// prepend, v2.head != 0
let mut v1 = VecDeque::with_capacity(7);
let mut v2 = test_deque(true);
v1.prepend(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
assert_eq!(v1, [1, 2, 3, 4]);
v1.pop_back();
let mut v2 = test_deque(true);
// this should wrap around the physical buffer
v1.prepend(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
// check it really wrapped
assert_eq!(v1.as_slices(), ([1].as_slice(), [2, 3, 4, 1, 2, 3].as_slice()));
// extend_front, v2.head != 0
let mut v1 = VecDeque::with_capacity(7);
let mut v2 = test_deque(true);
v1.extend_front(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
assert_eq!(v1, [4, 3, 2, 1]);
v1.pop_back();
let mut v2 = test_deque(true);
// this should wrap around the physical buffer
v1.extend_front(v2.drain(..));
// drain removes all elements but keeps the buffer
assert_eq!(v2, []);
assert!(v2.capacity() >= 4);
// check it really wrapped
assert_eq!(v1.as_slices(), ([4].as_slice(), [3, 2, 1, 4, 3, 2].as_slice()));
}
#[test]
fn test_splice() {
let mut v = VecDeque::from(vec![1, 2, 3, 4, 5]);
let a = [10, 11, 12];
v.splice(2..4, a);
assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
v.splice(1..3, Some(20));
assert_eq!(v, &[1, 20, 11, 12, 5]);
}
#[test]
fn test_splice_inclusive_range() {
let mut v = VecDeque::from(vec![1, 2, 3, 4, 5]);
let a = [10, 11, 12];
let t1: Vec<_> = v.splice(2..=3, a).collect();
assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
assert_eq!(t1, &[3, 4]);
let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
assert_eq!(v, &[1, 20, 11, 12, 5]);
assert_eq!(t2, &[2, 10]);
}
#[test]
fn test_splice_inclusive_range2() {
let mut v = VecDeque::from(vec![1, 2, 10, 11, 12, 5]);
let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
assert_eq!(v, &[1, 20, 11, 12, 5]);
assert_eq!(t2, &[2, 10]);
}
#[test]
#[should_panic]
fn test_splice_out_of_bounds() {
let mut v = VecDeque::from(vec![1, 2, 3, 4, 5]);
let a = [10, 11, 12];
v.splice(5..6, a);
}
#[test]
#[should_panic]
fn test_splice_inclusive_out_of_bounds() {
let mut v = VecDeque::from(vec![1, 2, 3, 4, 5]);
let a = [10, 11, 12];
v.splice(5..=5, a);
}
#[test]
fn test_splice_items_zero_sized() {
let mut vec = VecDeque::from(vec![(), (), ()]);
let vec2 = VecDeque::from(vec![]);
let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
assert_eq!(vec, &[(), ()]);
assert_eq!(t, &[()]);
}
#[test]
fn test_splice_unbounded() {
let mut vec = VecDeque::from(vec![1, 2, 3, 4, 5]);
let t: Vec<_> = vec.splice(.., None).collect();
assert_eq!(vec, &[]);
assert_eq!(t, &[1, 2, 3, 4, 5]);
}
#[test]
fn test_splice_forget() {
let mut v = VecDeque::from(vec![1, 2, 3, 4, 5]);
let a = [10, 11, 12];
std::mem::forget(v.splice(2..4, a));
assert_eq!(v, &[1, 2]);
}
#[test]
fn test_splice_wrapping() {
let mut vec = VecDeque::with_capacity(10);
vec.push_front(7u8);
vec.push_back(9);
vec.splice(1..1, [8]);
assert_eq!(Vec::from(vec), [7, 8, 9]);
}
Reference in a new issue View git blame Copy permalink