1 use core::num::NonZeroUsize;
2 use std::assert_matches::assert_matches;
3 use std::collections::TryReserveErrorKind::*;
4 use std::collections::{vec_deque::Drain, VecDeque};
5 use std::fmt::Debug;
6 use std::ops::Bound::*;
7 use std::panic::{catch_unwind, AssertUnwindSafe};
8
9 use crate::hash;
10
11 use Taggy::*;
12 use Taggypar::*;
13
14 #[test]
test_simple()15 fn test_simple() {
16 let mut d = VecDeque::new();
17 assert_eq!(d.len(), 0);
18 d.push_front(17);
19 d.push_front(42);
20 d.push_back(137);
21 assert_eq!(d.len(), 3);
22 d.push_back(137);
23 assert_eq!(d.len(), 4);
24 assert_eq!(*d.front().unwrap(), 42);
25 assert_eq!(*d.back().unwrap(), 137);
26 let mut i = d.pop_front();
27 assert_eq!(i, Some(42));
28 i = d.pop_back();
29 assert_eq!(i, Some(137));
30 i = d.pop_back();
31 assert_eq!(i, Some(137));
32 i = d.pop_back();
33 assert_eq!(i, Some(17));
34 assert_eq!(d.len(), 0);
35 d.push_back(3);
36 assert_eq!(d.len(), 1);
37 d.push_front(2);
38 assert_eq!(d.len(), 2);
39 d.push_back(4);
40 assert_eq!(d.len(), 3);
41 d.push_front(1);
42 assert_eq!(d.len(), 4);
43 assert_eq!(d[0], 1);
44 assert_eq!(d[1], 2);
45 assert_eq!(d[2], 3);
46 assert_eq!(d[3], 4);
47 }
48
test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T)49 fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
50 let mut deq = VecDeque::new();
51 assert_eq!(deq.len(), 0);
52 deq.push_front(a.clone());
53 deq.push_front(b.clone());
54 deq.push_back(c.clone());
55 assert_eq!(deq.len(), 3);
56 deq.push_back(d.clone());
57 assert_eq!(deq.len(), 4);
58 assert_eq!((*deq.front().unwrap()).clone(), b.clone());
59 assert_eq!((*deq.back().unwrap()).clone(), d.clone());
60 assert_eq!(deq.pop_front().unwrap(), b.clone());
61 assert_eq!(deq.pop_back().unwrap(), d.clone());
62 assert_eq!(deq.pop_back().unwrap(), c.clone());
63 assert_eq!(deq.pop_back().unwrap(), a.clone());
64 assert_eq!(deq.len(), 0);
65 deq.push_back(c.clone());
66 assert_eq!(deq.len(), 1);
67 deq.push_front(b.clone());
68 assert_eq!(deq.len(), 2);
69 deq.push_back(d.clone());
70 assert_eq!(deq.len(), 3);
71 deq.push_front(a.clone());
72 assert_eq!(deq.len(), 4);
73 assert_eq!(deq[0].clone(), a.clone());
74 assert_eq!(deq[1].clone(), b.clone());
75 assert_eq!(deq[2].clone(), c.clone());
76 assert_eq!(deq[3].clone(), d.clone());
77 }
78
79 #[test]
test_push_front_grow()80 fn test_push_front_grow() {
81 let mut deq = VecDeque::new();
82 for i in 0..66 {
83 deq.push_front(i);
84 }
85 assert_eq!(deq.len(), 66);
86
87 for i in 0..66 {
88 assert_eq!(deq[i], 65 - i);
89 }
90
91 let mut deq = VecDeque::new();
92 for i in 0..66 {
93 deq.push_back(i);
94 }
95
96 for i in 0..66 {
97 assert_eq!(deq[i], i);
98 }
99 }
100
101 #[test]
test_index()102 fn test_index() {
103 let mut deq = VecDeque::new();
104 for i in 1..4 {
105 deq.push_front(i);
106 }
107 assert_eq!(deq[1], 2);
108 }
109
110 #[test]
111 #[should_panic]
test_index_out_of_bounds()112 fn test_index_out_of_bounds() {
113 let mut deq = VecDeque::new();
114 for i in 1..4 {
115 deq.push_front(i);
116 }
117 deq[3];
118 }
119
120 #[test]
121 #[should_panic]
test_range_start_overflow()122 fn test_range_start_overflow() {
123 let deq = VecDeque::from(vec![1, 2, 3]);
124 deq.range((Included(0), Included(usize::MAX)));
125 }
126
127 #[test]
128 #[should_panic]
test_range_end_overflow()129 fn test_range_end_overflow() {
130 let deq = VecDeque::from(vec![1, 2, 3]);
131 deq.range((Excluded(usize::MAX), Included(0)));
132 }
133
134 #[derive(Clone, PartialEq, Debug)]
135 enum Taggy {
136 One(i32),
137 Two(i32, i32),
138 Three(i32, i32, i32),
139 }
140
141 #[derive(Clone, PartialEq, Debug)]
142 enum Taggypar<T> {
143 Onepar(T),
144 Twopar(T, T),
145 Threepar(T, T, T),
146 }
147
148 #[derive(Clone, PartialEq, Debug)]
149 struct RecCy {
150 x: i32,
151 y: i32,
152 t: Taggy,
153 }
154
155 #[test]
test_param_int()156 fn test_param_int() {
157 test_parameterized::<i32>(5, 72, 64, 175);
158 }
159
160 #[test]
test_param_taggy()161 fn test_param_taggy() {
162 test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
163 }
164
165 #[test]
test_param_taggypar()166 fn test_param_taggypar() {
167 test_parameterized::<Taggypar<i32>>(
168 Onepar::<i32>(1),
169 Twopar::<i32>(1, 2),
170 Threepar::<i32>(1, 2, 3),
171 Twopar::<i32>(17, 42),
172 );
173 }
174
175 #[test]
test_param_reccy()176 fn test_param_reccy() {
177 let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
178 let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
179 let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
180 let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
181 test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
182 }
183
184 #[test]
test_with_capacity()185 fn test_with_capacity() {
186 let mut d = VecDeque::with_capacity(0);
187 d.push_back(1);
188 assert_eq!(d.len(), 1);
189 let mut d = VecDeque::with_capacity(50);
190 d.push_back(1);
191 assert_eq!(d.len(), 1);
192 }
193
194 #[test]
test_with_capacity_non_power_two()195 fn test_with_capacity_non_power_two() {
196 let mut d3 = VecDeque::with_capacity(3);
197 d3.push_back(1);
198
199 // X = None, | = lo
200 // [|1, X, X]
201 assert_eq!(d3.pop_front(), Some(1));
202 // [X, |X, X]
203 assert_eq!(d3.front(), None);
204
205 // [X, |3, X]
206 d3.push_back(3);
207 // [X, |3, 6]
208 d3.push_back(6);
209 // [X, X, |6]
210 assert_eq!(d3.pop_front(), Some(3));
211
212 // Pushing the lo past half way point to trigger
213 // the 'B' scenario for growth
214 // [9, X, |6]
215 d3.push_back(9);
216 // [9, 12, |6]
217 d3.push_back(12);
218
219 d3.push_back(15);
220 // There used to be a bug here about how the
221 // VecDeque made growth assumptions about the
222 // underlying Vec which didn't hold and lead
223 // to corruption.
224 // (Vec grows to next power of two)
225 // good- [9, 12, 15, X, X, X, X, |6]
226 // bug- [15, 12, X, X, X, |6, X, X]
227 assert_eq!(d3.pop_front(), Some(6));
228
229 // Which leads us to the following state which
230 // would be a failure case.
231 // bug- [15, 12, X, X, X, X, |X, X]
232 assert_eq!(d3.front(), Some(&9));
233 }
234
235 #[test]
test_reserve_exact()236 fn test_reserve_exact() {
237 let mut d = VecDeque::new();
238 d.push_back(0);
239 d.reserve_exact(50);
240 assert!(d.capacity() >= 51);
241 }
242
243 #[test]
test_reserve()244 fn test_reserve() {
245 let mut d = VecDeque::new();
246 d.push_back(0);
247 d.reserve(50);
248 assert!(d.capacity() >= 51);
249 }
250
251 #[test]
test_swap()252 fn test_swap() {
253 let mut d: VecDeque<_> = (0..5).collect();
254 d.pop_front();
255 d.swap(0, 3);
256 assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]);
257 }
258
259 #[test]
test_iter()260 fn test_iter() {
261 let mut d = VecDeque::new();
262 assert_eq!(d.iter().next(), None);
263 assert_eq!(d.iter().size_hint(), (0, Some(0)));
264
265 for i in 0..5 {
266 d.push_back(i);
267 }
268 {
269 let b: &[_] = &[&0, &1, &2, &3, &4];
270 assert_eq!(d.iter().collect::<Vec<_>>(), b);
271 }
272
273 for i in 6..9 {
274 d.push_front(i);
275 }
276 {
277 let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4];
278 assert_eq!(d.iter().collect::<Vec<_>>(), b);
279 }
280
281 let mut it = d.iter();
282 let mut len = d.len();
283 loop {
284 match it.next() {
285 None => break,
286 _ => {
287 len -= 1;
288 assert_eq!(it.size_hint(), (len, Some(len)))
289 }
290 }
291 }
292 }
293
294 #[test]
test_rev_iter()295 fn test_rev_iter() {
296 let mut d = VecDeque::new();
297 assert_eq!(d.iter().rev().next(), None);
298
299 for i in 0..5 {
300 d.push_back(i);
301 }
302 {
303 let b: &[_] = &[&4, &3, &2, &1, &0];
304 assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
305 }
306
307 for i in 6..9 {
308 d.push_front(i);
309 }
310 let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8];
311 assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
312 }
313
314 #[test]
test_mut_rev_iter_wrap()315 fn test_mut_rev_iter_wrap() {
316 let mut d = VecDeque::with_capacity(3);
317 assert!(d.iter_mut().rev().next().is_none());
318
319 d.push_back(1);
320 d.push_back(2);
321 d.push_back(3);
322 assert_eq!(d.pop_front(), Some(1));
323 d.push_back(4);
324
325 assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), vec![4, 3, 2]);
326 }
327
328 #[test]
test_mut_iter()329 fn test_mut_iter() {
330 let mut d = VecDeque::new();
331 assert!(d.iter_mut().next().is_none());
332
333 for i in 0..3 {
334 d.push_front(i);
335 }
336
337 for (i, elt) in d.iter_mut().enumerate() {
338 assert_eq!(*elt, 2 - i);
339 *elt = i;
340 }
341
342 {
343 let mut it = d.iter_mut();
344 assert_eq!(*it.next().unwrap(), 0);
345 assert_eq!(*it.next().unwrap(), 1);
346 assert_eq!(*it.next().unwrap(), 2);
347 assert!(it.next().is_none());
348 }
349 }
350
351 #[test]
test_mut_rev_iter()352 fn test_mut_rev_iter() {
353 let mut d = VecDeque::new();
354 assert!(d.iter_mut().rev().next().is_none());
355
356 for i in 0..3 {
357 d.push_front(i);
358 }
359
360 for (i, elt) in d.iter_mut().rev().enumerate() {
361 assert_eq!(*elt, i);
362 *elt = i;
363 }
364
365 {
366 let mut it = d.iter_mut().rev();
367 assert_eq!(*it.next().unwrap(), 0);
368 assert_eq!(*it.next().unwrap(), 1);
369 assert_eq!(*it.next().unwrap(), 2);
370 assert!(it.next().is_none());
371 }
372 }
373
374 #[test]
test_into_iter()375 fn test_into_iter() {
376 // Empty iter
377 {
378 let d: VecDeque<i32> = VecDeque::new();
379 let mut iter = d.into_iter();
380
381 assert_eq!(iter.size_hint(), (0, Some(0)));
382 assert_eq!(iter.next(), None);
383 assert_eq!(iter.size_hint(), (0, Some(0)));
384 }
385
386 // simple iter
387 {
388 let mut d = VecDeque::new();
389 for i in 0..5 {
390 d.push_back(i);
391 }
392
393 let b = vec![0, 1, 2, 3, 4];
394 assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
395 }
396
397 // wrapped iter
398 {
399 let mut d = VecDeque::new();
400 for i in 0..5 {
401 d.push_back(i);
402 }
403 for i in 6..9 {
404 d.push_front(i);
405 }
406
407 let b = vec![8, 7, 6, 0, 1, 2, 3, 4];
408 assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
409 }
410
411 // partially used
412 {
413 let mut d = VecDeque::new();
414 for i in 0..5 {
415 d.push_back(i);
416 }
417 for i in 6..9 {
418 d.push_front(i);
419 }
420
421 let mut it = d.into_iter();
422 assert_eq!(it.size_hint(), (8, Some(8)));
423 assert_eq!(it.next(), Some(8));
424 assert_eq!(it.size_hint(), (7, Some(7)));
425 assert_eq!(it.next_back(), Some(4));
426 assert_eq!(it.size_hint(), (6, Some(6)));
427 assert_eq!(it.next(), Some(7));
428 assert_eq!(it.size_hint(), (5, Some(5)));
429 }
430
431 // advance_by
432 {
433 let mut d = VecDeque::new();
434 for i in 0..=4 {
435 d.push_back(i);
436 }
437 for i in 6..=8 {
438 d.push_front(i);
439 }
440
441 let mut it = d.into_iter();
442 assert_eq!(it.advance_by(1), Ok(()));
443 assert_eq!(it.next(), Some(7));
444 assert_eq!(it.advance_back_by(1), Ok(()));
445 assert_eq!(it.next_back(), Some(3));
446
447 let mut it = VecDeque::from(vec![1, 2, 3, 4, 5]).into_iter();
448 assert_eq!(it.advance_by(10), Err(NonZeroUsize::new(5).unwrap()));
449 let mut it = VecDeque::from(vec![1, 2, 3, 4, 5]).into_iter();
450 assert_eq!(it.advance_back_by(10), Err(NonZeroUsize::new(5).unwrap()));
451 }
452 }
453
454 #[test]
test_drain()455 fn test_drain() {
456 // Empty iter
457 {
458 let mut d: VecDeque<i32> = VecDeque::new();
459
460 {
461 let mut iter = d.drain(..);
462
463 assert_eq!(iter.size_hint(), (0, Some(0)));
464 assert_eq!(iter.next(), None);
465 assert_eq!(iter.size_hint(), (0, Some(0)));
466 }
467
468 assert!(d.is_empty());
469 }
470
471 // simple iter
472 {
473 let mut d = VecDeque::new();
474 for i in 0..5 {
475 d.push_back(i);
476 }
477
478 assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
479 assert!(d.is_empty());
480 }
481
482 // wrapped iter
483 {
484 let mut d = VecDeque::new();
485 for i in 0..5 {
486 d.push_back(i);
487 }
488 for i in 6..9 {
489 d.push_front(i);
490 }
491 assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
492 assert!(d.is_empty());
493 }
494
495 // partially used
496 {
497 let mut d: VecDeque<_> = VecDeque::new();
498 for i in 0..5 {
499 d.push_back(i);
500 }
501 for i in 6..9 {
502 d.push_front(i);
503 }
504
505 {
506 let mut it = d.drain(..);
507 assert_eq!(it.size_hint(), (8, Some(8)));
508 assert_eq!(it.next(), Some(8));
509 assert_eq!(it.size_hint(), (7, Some(7)));
510 assert_eq!(it.next_back(), Some(4));
511 assert_eq!(it.size_hint(), (6, Some(6)));
512 assert_eq!(it.next(), Some(7));
513 assert_eq!(it.size_hint(), (5, Some(5)));
514 }
515 assert!(d.is_empty());
516 }
517 }
518
519 #[test]
test_from_iter()520 fn test_from_iter() {
521 let v = vec![1, 2, 3, 4, 5, 6, 7];
522 let deq: VecDeque<_> = v.iter().cloned().collect();
523 let u: Vec<_> = deq.iter().cloned().collect();
524 assert_eq!(u, v);
525
526 let seq = (0..).step_by(2).take(256);
527 let deq: VecDeque<_> = seq.collect();
528 for (i, &x) in deq.iter().enumerate() {
529 assert_eq!(2 * i, x);
530 }
531 assert_eq!(deq.len(), 256);
532 }
533
534 #[test]
test_clone()535 fn test_clone() {
536 let mut d = VecDeque::new();
537 d.push_front(17);
538 d.push_front(42);
539 d.push_back(137);
540 d.push_back(137);
541 assert_eq!(d.len(), 4);
542 let mut e = d.clone();
543 assert_eq!(e.len(), 4);
544 while !d.is_empty() {
545 assert_eq!(d.pop_back(), e.pop_back());
546 }
547 assert_eq!(d.len(), 0);
548 assert_eq!(e.len(), 0);
549 }
550
551 #[test]
test_eq()552 fn test_eq() {
553 let mut d = VecDeque::new();
554 assert!(d == VecDeque::with_capacity(0));
555 d.push_front(137);
556 d.push_front(17);
557 d.push_front(42);
558 d.push_back(137);
559 let mut e = VecDeque::with_capacity(0);
560 e.push_back(42);
561 e.push_back(17);
562 e.push_back(137);
563 e.push_back(137);
564 assert!(&e == &d);
565 e.pop_back();
566 e.push_back(0);
567 assert!(e != d);
568 e.clear();
569 assert!(e == VecDeque::new());
570 }
571
572 #[test]
test_partial_eq_array()573 fn test_partial_eq_array() {
574 let d = VecDeque::<char>::new();
575 assert!(d == []);
576
577 let mut d = VecDeque::new();
578 d.push_front('a');
579 assert!(d == ['a']);
580
581 let mut d = VecDeque::new();
582 d.push_back('a');
583 assert!(d == ['a']);
584
585 let mut d = VecDeque::new();
586 d.push_back('a');
587 d.push_back('b');
588 assert!(d == ['a', 'b']);
589 }
590
591 #[test]
test_hash()592 fn test_hash() {
593 let mut x = VecDeque::new();
594 let mut y = VecDeque::new();
595
596 x.push_back(1);
597 x.push_back(2);
598 x.push_back(3);
599
600 y.push_back(0);
601 y.push_back(1);
602 y.pop_front();
603 y.push_back(2);
604 y.push_back(3);
605
606 assert!(hash(&x) == hash(&y));
607 }
608
609 #[test]
test_hash_after_rotation()610 fn test_hash_after_rotation() {
611 // test that two deques hash equal even if elements are laid out differently
612 let len = 28;
613 let mut ring: VecDeque<i32> = (0..len as i32).collect();
614 let orig = ring.clone();
615 for _ in 0..ring.capacity() {
616 // shift values 1 step to the right by pop, sub one, push
617 ring.pop_front();
618 for elt in &mut ring {
619 *elt -= 1;
620 }
621 ring.push_back(len - 1);
622 assert_eq!(hash(&orig), hash(&ring));
623 assert_eq!(orig, ring);
624 assert_eq!(ring, orig);
625 }
626 }
627
628 #[test]
test_eq_after_rotation()629 fn test_eq_after_rotation() {
630 // test that two deques are equal even if elements are laid out differently
631 let len = 28;
632 let mut ring: VecDeque<i32> = (0..len as i32).collect();
633 let mut shifted = ring.clone();
634 for _ in 0..10 {
635 // shift values 1 step to the right by pop, sub one, push
636 ring.pop_front();
637 for elt in &mut ring {
638 *elt -= 1;
639 }
640 ring.push_back(len - 1);
641 }
642
643 // try every shift
644 for _ in 0..shifted.capacity() {
645 shifted.pop_front();
646 for elt in &mut shifted {
647 *elt -= 1;
648 }
649 shifted.push_back(len - 1);
650 assert_eq!(shifted, ring);
651 assert_eq!(ring, shifted);
652 }
653 }
654
655 #[test]
test_ord()656 fn test_ord() {
657 let x = VecDeque::new();
658 let mut y = VecDeque::new();
659 y.push_back(1);
660 y.push_back(2);
661 y.push_back(3);
662 assert!(x < y);
663 assert!(y > x);
664 assert!(x <= x);
665 assert!(x >= x);
666 }
667
668 #[test]
test_show()669 fn test_show() {
670 let ringbuf: VecDeque<_> = (0..10).collect();
671 assert_eq!(format!("{ringbuf:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
672
673 let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
674 assert_eq!(format!("{ringbuf:?}"), "[\"just\", \"one\", \"test\", \"more\"]");
675 }
676
677 #[test]
test_drop()678 fn test_drop() {
679 static mut DROPS: i32 = 0;
680 struct Elem;
681 impl Drop for Elem {
682 fn drop(&mut self) {
683 unsafe {
684 DROPS += 1;
685 }
686 }
687 }
688
689 let mut ring = VecDeque::new();
690 ring.push_back(Elem);
691 ring.push_front(Elem);
692 ring.push_back(Elem);
693 ring.push_front(Elem);
694 drop(ring);
695
696 assert_eq!(unsafe { DROPS }, 4);
697 }
698
699 #[test]
test_drop_with_pop()700 fn test_drop_with_pop() {
701 static mut DROPS: i32 = 0;
702 struct Elem;
703 impl Drop for Elem {
704 fn drop(&mut self) {
705 unsafe {
706 DROPS += 1;
707 }
708 }
709 }
710
711 let mut ring = VecDeque::new();
712 ring.push_back(Elem);
713 ring.push_front(Elem);
714 ring.push_back(Elem);
715 ring.push_front(Elem);
716
717 drop(ring.pop_back());
718 drop(ring.pop_front());
719 assert_eq!(unsafe { DROPS }, 2);
720
721 drop(ring);
722 assert_eq!(unsafe { DROPS }, 4);
723 }
724
725 #[test]
test_drop_clear()726 fn test_drop_clear() {
727 static mut DROPS: i32 = 0;
728 struct Elem;
729 impl Drop for Elem {
730 fn drop(&mut self) {
731 unsafe {
732 DROPS += 1;
733 }
734 }
735 }
736
737 let mut ring = VecDeque::new();
738 ring.push_back(Elem);
739 ring.push_front(Elem);
740 ring.push_back(Elem);
741 ring.push_front(Elem);
742 ring.clear();
743 assert_eq!(unsafe { DROPS }, 4);
744
745 drop(ring);
746 assert_eq!(unsafe { DROPS }, 4);
747 }
748
749 #[test]
750 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
test_drop_panic()751 fn test_drop_panic() {
752 static mut DROPS: i32 = 0;
753
754 struct D(bool);
755
756 impl Drop for D {
757 fn drop(&mut self) {
758 unsafe {
759 DROPS += 1;
760 }
761
762 if self.0 {
763 panic!("panic in `drop`");
764 }
765 }
766 }
767
768 let mut q = VecDeque::new();
769 q.push_back(D(false));
770 q.push_back(D(false));
771 q.push_back(D(false));
772 q.push_back(D(false));
773 q.push_back(D(false));
774 q.push_front(D(false));
775 q.push_front(D(false));
776 q.push_front(D(true));
777
778 catch_unwind(move || drop(q)).ok();
779
780 assert_eq!(unsafe { DROPS }, 8);
781 }
782
783 #[test]
test_reserve_grow()784 fn test_reserve_grow() {
785 // test growth path A
786 // [T o o H] -> [T o o H . . . . ]
787 let mut ring = VecDeque::with_capacity(4);
788 for i in 0..3 {
789 ring.push_back(i);
790 }
791 ring.reserve(7);
792 for i in 0..3 {
793 assert_eq!(ring.pop_front(), Some(i));
794 }
795
796 // test growth path B
797 // [H T o o] -> [. T o o H . . . ]
798 let mut ring = VecDeque::with_capacity(4);
799 for i in 0..1 {
800 ring.push_back(i);
801 assert_eq!(ring.pop_front(), Some(i));
802 }
803 for i in 0..3 {
804 ring.push_back(i);
805 }
806 ring.reserve(7);
807 for i in 0..3 {
808 assert_eq!(ring.pop_front(), Some(i));
809 }
810
811 // test growth path C
812 // [o o H T] -> [o o H . . . . T ]
813 let mut ring = VecDeque::with_capacity(4);
814 for i in 0..3 {
815 ring.push_back(i);
816 assert_eq!(ring.pop_front(), Some(i));
817 }
818 for i in 0..3 {
819 ring.push_back(i);
820 }
821 ring.reserve(7);
822 for i in 0..3 {
823 assert_eq!(ring.pop_front(), Some(i));
824 }
825 }
826
827 #[test]
test_get()828 fn test_get() {
829 let mut ring = VecDeque::new();
830 ring.push_back(0);
831 assert_eq!(ring.get(0), Some(&0));
832 assert_eq!(ring.get(1), None);
833
834 ring.push_back(1);
835 assert_eq!(ring.get(0), Some(&0));
836 assert_eq!(ring.get(1), Some(&1));
837 assert_eq!(ring.get(2), None);
838
839 ring.push_back(2);
840 assert_eq!(ring.get(0), Some(&0));
841 assert_eq!(ring.get(1), Some(&1));
842 assert_eq!(ring.get(2), Some(&2));
843 assert_eq!(ring.get(3), None);
844
845 assert_eq!(ring.pop_front(), Some(0));
846 assert_eq!(ring.get(0), Some(&1));
847 assert_eq!(ring.get(1), Some(&2));
848 assert_eq!(ring.get(2), None);
849
850 assert_eq!(ring.pop_front(), Some(1));
851 assert_eq!(ring.get(0), Some(&2));
852 assert_eq!(ring.get(1), None);
853
854 assert_eq!(ring.pop_front(), Some(2));
855 assert_eq!(ring.get(0), None);
856 assert_eq!(ring.get(1), None);
857 }
858
859 #[test]
test_get_mut()860 fn test_get_mut() {
861 let mut ring = VecDeque::new();
862 for i in 0..3 {
863 ring.push_back(i);
864 }
865
866 match ring.get_mut(1) {
867 Some(x) => *x = -1,
868 None => (),
869 };
870
871 assert_eq!(ring.get_mut(0), Some(&mut 0));
872 assert_eq!(ring.get_mut(1), Some(&mut -1));
873 assert_eq!(ring.get_mut(2), Some(&mut 2));
874 assert_eq!(ring.get_mut(3), None);
875
876 assert_eq!(ring.pop_front(), Some(0));
877 assert_eq!(ring.get_mut(0), Some(&mut -1));
878 assert_eq!(ring.get_mut(1), Some(&mut 2));
879 assert_eq!(ring.get_mut(2), None);
880 }
881
882 #[test]
test_front()883 fn test_front() {
884 let mut ring = VecDeque::new();
885 ring.push_back(10);
886 ring.push_back(20);
887 assert_eq!(ring.front(), Some(&10));
888 ring.pop_front();
889 assert_eq!(ring.front(), Some(&20));
890 ring.pop_front();
891 assert_eq!(ring.front(), None);
892 }
893
894 #[test]
test_as_slices()895 fn test_as_slices() {
896 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
897 let cap = ring.capacity() as i32;
898 let first = cap / 2;
899 let last = cap - first;
900 for i in 0..first {
901 ring.push_back(i);
902
903 let (left, right) = ring.as_slices();
904 let expected: Vec<_> = (0..=i).collect();
905 assert_eq!(left, &expected[..]);
906 assert_eq!(right, []);
907 }
908
909 for j in -last..0 {
910 ring.push_front(j);
911 let (left, right) = ring.as_slices();
912 let expected_left: Vec<_> = (-last..=j).rev().collect();
913 let expected_right: Vec<_> = (0..first).collect();
914 assert_eq!(left, &expected_left[..]);
915 assert_eq!(right, &expected_right[..]);
916 }
917
918 assert_eq!(ring.len() as i32, cap);
919 assert_eq!(ring.capacity() as i32, cap);
920 }
921
922 #[test]
test_as_mut_slices()923 fn test_as_mut_slices() {
924 let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
925 let cap = ring.capacity() as i32;
926 let first = cap / 2;
927 let last = cap - first;
928 for i in 0..first {
929 ring.push_back(i);
930
931 let (left, right) = ring.as_mut_slices();
932 let expected: Vec<_> = (0..=i).collect();
933 assert_eq!(left, &expected[..]);
934 assert_eq!(right, []);
935 }
936
937 for j in -last..0 {
938 ring.push_front(j);
939 let (left, right) = ring.as_mut_slices();
940 let expected_left: Vec<_> = (-last..=j).rev().collect();
941 let expected_right: Vec<_> = (0..first).collect();
942 assert_eq!(left, &expected_left[..]);
943 assert_eq!(right, &expected_right[..]);
944 }
945
946 assert_eq!(ring.len() as i32, cap);
947 assert_eq!(ring.capacity() as i32, cap);
948 }
949
950 #[test]
test_append()951 fn test_append() {
952 let mut a: VecDeque<_> = [1, 2, 3].into_iter().collect();
953 let mut b: VecDeque<_> = [4, 5, 6].into_iter().collect();
954
955 // normal append
956 a.append(&mut b);
957 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
958 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
959
960 // append nothing to something
961 a.append(&mut b);
962 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
963 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
964
965 // append something to nothing
966 b.append(&mut a);
967 assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
968 assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
969 }
970
971 #[test]
test_append_permutations()972 fn test_append_permutations() {
973 fn construct_vec_deque(
974 push_back: usize,
975 pop_back: usize,
976 push_front: usize,
977 pop_front: usize,
978 ) -> VecDeque<usize> {
979 let mut out = VecDeque::new();
980 for a in 0..push_back {
981 out.push_back(a);
982 }
983 for b in 0..push_front {
984 out.push_front(push_back + b);
985 }
986 for _ in 0..pop_back {
987 out.pop_back();
988 }
989 for _ in 0..pop_front {
990 out.pop_front();
991 }
992 out
993 }
994
995 // Miri is too slow
996 let max = if cfg!(miri) { 3 } else { 5 };
997
998 // Many different permutations of both the `VecDeque` getting appended to
999 // and the one getting appended are generated to check `append`.
1000 // This ensures all 6 code paths of `append` are tested.
1001 for src_push_back in 0..max {
1002 for src_push_front in 0..max {
1003 // doesn't pop more values than are pushed
1004 for src_pop_back in 0..(src_push_back + src_push_front) {
1005 for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) {
1006 let src = construct_vec_deque(
1007 src_push_back,
1008 src_pop_back,
1009 src_push_front,
1010 src_pop_front,
1011 );
1012
1013 for dst_push_back in 0..max {
1014 for dst_push_front in 0..max {
1015 for dst_pop_back in 0..(dst_push_back + dst_push_front) {
1016 for dst_pop_front in
1017 0..(dst_push_back + dst_push_front - dst_pop_back)
1018 {
1019 let mut dst = construct_vec_deque(
1020 dst_push_back,
1021 dst_pop_back,
1022 dst_push_front,
1023 dst_pop_front,
1024 );
1025 let mut src = src.clone();
1026
1027 // Assert that appending `src` to `dst` gives the same order
1028 // of values as iterating over both in sequence.
1029 let correct = dst
1030 .iter()
1031 .chain(src.iter())
1032 .cloned()
1033 .collect::<Vec<usize>>();
1034 dst.append(&mut src);
1035 assert_eq!(dst, correct);
1036 assert!(src.is_empty());
1037 }
1038 }
1039 }
1040 }
1041 }
1042 }
1043 }
1044 }
1045 }
1046
1047 struct DropCounter<'a> {
1048 count: &'a mut u32,
1049 }
1050
1051 impl Drop for DropCounter<'_> {
drop(&mut self)1052 fn drop(&mut self) {
1053 *self.count += 1;
1054 }
1055 }
1056
1057 #[test]
test_append_double_drop()1058 fn test_append_double_drop() {
1059 let (mut count_a, mut count_b) = (0, 0);
1060 {
1061 let mut a = VecDeque::new();
1062 let mut b = VecDeque::new();
1063 a.push_back(DropCounter { count: &mut count_a });
1064 b.push_back(DropCounter { count: &mut count_b });
1065
1066 a.append(&mut b);
1067 }
1068 assert_eq!(count_a, 1);
1069 assert_eq!(count_b, 1);
1070 }
1071
1072 #[test]
1073 #[should_panic]
test_append_zst_capacity_overflow()1074 fn test_append_zst_capacity_overflow() {
1075 let mut v = Vec::with_capacity(usize::MAX);
1076 // note: using resize instead of set_len here would
1077 // be *extremely* slow in unoptimized builds.
1078 // SAFETY: `v` has capacity `usize::MAX`, and no initialization
1079 // is needed for empty tuples.
1080 unsafe { v.set_len(usize::MAX) };
1081 let mut v = VecDeque::from(v);
1082 let mut w = vec![()].into();
1083 v.append(&mut w);
1084 }
1085
1086 #[test]
test_retain()1087 fn test_retain() {
1088 let mut buf = VecDeque::new();
1089 buf.extend(1..5);
1090 buf.retain(|&x| x % 2 == 0);
1091 let v: Vec<_> = buf.into_iter().collect();
1092 assert_eq!(&v[..], &[2, 4]);
1093 }
1094
1095 #[test]
test_extend_ref()1096 fn test_extend_ref() {
1097 let mut v = VecDeque::new();
1098 v.push_back(1);
1099 v.extend(&[2, 3, 4]);
1100
1101 assert_eq!(v.len(), 4);
1102 assert_eq!(v[0], 1);
1103 assert_eq!(v[1], 2);
1104 assert_eq!(v[2], 3);
1105 assert_eq!(v[3], 4);
1106
1107 let mut w = VecDeque::new();
1108 w.push_back(5);
1109 w.push_back(6);
1110 v.extend(&w);
1111
1112 assert_eq!(v.len(), 6);
1113 assert_eq!(v[0], 1);
1114 assert_eq!(v[1], 2);
1115 assert_eq!(v[2], 3);
1116 assert_eq!(v[3], 4);
1117 assert_eq!(v[4], 5);
1118 assert_eq!(v[5], 6);
1119 }
1120
1121 #[test]
test_contains()1122 fn test_contains() {
1123 let mut v = VecDeque::new();
1124 v.extend(&[2, 3, 4]);
1125
1126 assert!(v.contains(&3));
1127 assert!(!v.contains(&1));
1128
1129 v.clear();
1130
1131 assert!(!v.contains(&3));
1132 }
1133
1134 #[allow(dead_code)]
assert_covariance()1135 fn assert_covariance() {
1136 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1137 d
1138 }
1139 }
1140
1141 #[test]
test_is_empty()1142 fn test_is_empty() {
1143 let mut v = VecDeque::<i32>::new();
1144 assert!(v.is_empty());
1145 assert!(v.iter().is_empty());
1146 assert!(v.iter_mut().is_empty());
1147 v.extend(&[2, 3, 4]);
1148 assert!(!v.is_empty());
1149 assert!(!v.iter().is_empty());
1150 assert!(!v.iter_mut().is_empty());
1151 while let Some(_) = v.pop_front() {
1152 assert_eq!(v.is_empty(), v.len() == 0);
1153 assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
1154 assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
1155 }
1156 assert!(v.is_empty());
1157 assert!(v.iter().is_empty());
1158 assert!(v.iter_mut().is_empty());
1159 assert!(v.into_iter().is_empty());
1160 }
1161
1162 #[test]
test_reserve_exact_2()1163 fn test_reserve_exact_2() {
1164 // This is all the same as test_reserve
1165
1166 let mut v = VecDeque::new();
1167
1168 v.reserve_exact(2);
1169 assert!(v.capacity() >= 2);
1170
1171 for i in 0..16 {
1172 v.push_back(i);
1173 }
1174
1175 assert!(v.capacity() >= 16);
1176 v.reserve_exact(16);
1177 assert!(v.capacity() >= 32);
1178
1179 v.push_back(16);
1180
1181 v.reserve_exact(16);
1182 assert!(v.capacity() >= 33)
1183 }
1184
1185 #[test]
1186 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1187 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
test_try_reserve()1188 fn test_try_reserve() {
1189 // These are the interesting cases:
1190 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1191 // * > isize::MAX should always fail
1192 // * On 16/32-bit should CapacityOverflow
1193 // * On 64-bit should OOM
1194 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1195 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1196
1197 const MAX_CAP: usize = isize::MAX as usize;
1198 const MAX_USIZE: usize = usize::MAX;
1199
1200 {
1201 // Note: basic stuff is checked by test_reserve
1202 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1203
1204 // Check isize::MAX doesn't count as an overflow
1205 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1206 panic!("isize::MAX shouldn't trigger an overflow!");
1207 }
1208 // Play it again, frank! (just to be sure)
1209 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1210 panic!("isize::MAX shouldn't trigger an overflow!");
1211 }
1212
1213 // Check isize::MAX + 1 does count as overflow
1214 assert_matches!(
1215 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1216 Err(CapacityOverflow),
1217 "isize::MAX + 1 should trigger an overflow!"
1218 );
1219
1220 // Check usize::MAX does count as overflow
1221 assert_matches!(
1222 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1223 Err(CapacityOverflow),
1224 "usize::MAX should trigger an overflow!"
1225 );
1226 }
1227
1228 {
1229 // Same basic idea, but with non-zero len
1230 let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1231
1232 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1233 panic!("isize::MAX shouldn't trigger an overflow!");
1234 }
1235 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1236 panic!("isize::MAX shouldn't trigger an overflow!");
1237 }
1238
1239 assert_matches!(
1240 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1241 Err(CapacityOverflow),
1242 "isize::MAX + 1 should trigger an overflow!"
1243 );
1244
1245 // Should always overflow in the add-to-len
1246 assert_matches!(
1247 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1248 Err(CapacityOverflow),
1249 "usize::MAX should trigger an overflow!"
1250 );
1251 }
1252
1253 {
1254 // Same basic idea, but with interesting type size
1255 let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1256
1257 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1258 {
1259 panic!("isize::MAX shouldn't trigger an overflow!");
1260 }
1261 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1262 {
1263 panic!("isize::MAX shouldn't trigger an overflow!");
1264 }
1265
1266 assert_matches!(
1267 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1268 Err(CapacityOverflow),
1269 "isize::MAX + 1 should trigger an overflow!"
1270 );
1271
1272 // Should fail in the mul-by-size
1273 assert_matches!(
1274 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1275 Err(CapacityOverflow),
1276 "usize::MAX should trigger an overflow!"
1277 );
1278 }
1279 }
1280
1281 #[test]
1282 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1283 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
test_try_reserve_exact()1284 fn test_try_reserve_exact() {
1285 // This is exactly the same as test_try_reserve with the method changed.
1286 // See that test for comments.
1287
1288 const MAX_CAP: usize = isize::MAX as usize;
1289 const MAX_USIZE: usize = usize::MAX;
1290
1291 {
1292 let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1293
1294 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1295 {
1296 panic!("isize::MAX shouldn't trigger an overflow!");
1297 }
1298 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1299 {
1300 panic!("isize::MAX shouldn't trigger an overflow!");
1301 }
1302
1303 assert_matches!(
1304 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1305 Err(CapacityOverflow),
1306 "isize::MAX + 1 should trigger an overflow!"
1307 );
1308
1309 assert_matches!(
1310 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1311 Err(CapacityOverflow),
1312 "usize::MAX should trigger an overflow!"
1313 );
1314 }
1315
1316 {
1317 let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1318
1319 if let Err(CapacityOverflow) =
1320 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1321 {
1322 panic!("isize::MAX shouldn't trigger an overflow!");
1323 }
1324 if let Err(CapacityOverflow) =
1325 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1326 {
1327 panic!("isize::MAX shouldn't trigger an overflow!");
1328 }
1329
1330 assert_matches!(
1331 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1332 Err(CapacityOverflow),
1333 "isize::MAX + 1 should trigger an overflow!"
1334 );
1335
1336 assert_matches!(
1337 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1338 Err(CapacityOverflow),
1339 "usize::MAX should trigger an overflow!"
1340 );
1341 }
1342
1343 {
1344 let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1345
1346 if let Err(CapacityOverflow) =
1347 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1348 {
1349 panic!("isize::MAX shouldn't trigger an overflow!");
1350 }
1351 if let Err(CapacityOverflow) =
1352 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1353 {
1354 panic!("isize::MAX shouldn't trigger an overflow!");
1355 }
1356
1357 assert_matches!(
1358 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1359 Err(CapacityOverflow),
1360 "isize::MAX + 1 should trigger an overflow!"
1361 );
1362
1363 assert_matches!(
1364 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1365 Err(CapacityOverflow),
1366 "usize::MAX should trigger an overflow!"
1367 );
1368 }
1369 }
1370
1371 #[test]
test_rotate_nop()1372 fn test_rotate_nop() {
1373 let mut v: VecDeque<_> = (0..10).collect();
1374 assert_unchanged(&v);
1375
1376 v.rotate_left(0);
1377 assert_unchanged(&v);
1378
1379 v.rotate_left(10);
1380 assert_unchanged(&v);
1381
1382 v.rotate_right(0);
1383 assert_unchanged(&v);
1384
1385 v.rotate_right(10);
1386 assert_unchanged(&v);
1387
1388 v.rotate_left(3);
1389 v.rotate_right(3);
1390 assert_unchanged(&v);
1391
1392 v.rotate_right(3);
1393 v.rotate_left(3);
1394 assert_unchanged(&v);
1395
1396 v.rotate_left(6);
1397 v.rotate_right(6);
1398 assert_unchanged(&v);
1399
1400 v.rotate_right(6);
1401 v.rotate_left(6);
1402 assert_unchanged(&v);
1403
1404 v.rotate_left(3);
1405 v.rotate_left(7);
1406 assert_unchanged(&v);
1407
1408 v.rotate_right(4);
1409 v.rotate_right(6);
1410 assert_unchanged(&v);
1411
1412 v.rotate_left(1);
1413 v.rotate_left(2);
1414 v.rotate_left(3);
1415 v.rotate_left(4);
1416 assert_unchanged(&v);
1417
1418 v.rotate_right(1);
1419 v.rotate_right(2);
1420 v.rotate_right(3);
1421 v.rotate_right(4);
1422 assert_unchanged(&v);
1423
1424 fn assert_unchanged(v: &VecDeque<i32>) {
1425 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1426 }
1427 }
1428
1429 #[test]
test_rotate_left_parts()1430 fn test_rotate_left_parts() {
1431 let mut v: VecDeque<_> = VecDeque::with_capacity(8);
1432 v.extend(1..=7);
1433 v.rotate_left(2);
1434 assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
1435 v.rotate_left(2);
1436 assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
1437 v.rotate_left(2);
1438 assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
1439 v.rotate_left(2);
1440 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
1441 v.rotate_left(2);
1442 assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
1443 v.rotate_left(2);
1444 assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
1445 v.rotate_left(2);
1446 assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
1447 }
1448
1449 #[test]
test_rotate_right_parts()1450 fn test_rotate_right_parts() {
1451 let mut v: VecDeque<_> = VecDeque::with_capacity(8);
1452 v.extend(1..=7);
1453 v.rotate_right(2);
1454 assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1455 v.rotate_right(2);
1456 assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1457 v.rotate_right(2);
1458 assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1459 v.rotate_right(2);
1460 assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1461 v.rotate_right(2);
1462 assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1463 v.rotate_right(2);
1464 assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1465 v.rotate_right(2);
1466 assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1467 }
1468
1469 #[test]
test_rotate_left_random()1470 fn test_rotate_left_random() {
1471 let shifts = [
1472 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,
1473 12, 9, 11, 1, 7, 9, 7, 2,
1474 ];
1475 let n = 12;
1476 let mut v: VecDeque<_> = (0..n).collect();
1477 let mut total_shift = 0;
1478 for shift in shifts.iter().cloned() {
1479 v.rotate_left(shift);
1480 total_shift += shift;
1481 for i in 0..n {
1482 assert_eq!(v[i], (i + total_shift) % n);
1483 }
1484 }
1485 }
1486
1487 #[test]
test_rotate_right_random()1488 fn test_rotate_right_random() {
1489 let shifts = [
1490 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3,
1491 12, 9, 11, 1, 7, 9, 7, 2,
1492 ];
1493 let n = 12;
1494 let mut v: VecDeque<_> = (0..n).collect();
1495 let mut total_shift = 0;
1496 for shift in shifts.iter().cloned() {
1497 v.rotate_right(shift);
1498 total_shift += shift;
1499 for i in 0..n {
1500 assert_eq!(v[(i + total_shift) % n], i);
1501 }
1502 }
1503 }
1504
1505 #[test]
test_try_fold_empty()1506 fn test_try_fold_empty() {
1507 assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
1508 }
1509
1510 #[test]
test_try_fold_none()1511 fn test_try_fold_none() {
1512 let v: VecDeque<u32> = (0..12).collect();
1513 assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None }));
1514 }
1515
1516 #[test]
test_try_fold_ok()1517 fn test_try_fold_ok() {
1518 let v: VecDeque<u32> = (0..12).collect();
1519 assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b)));
1520 }
1521
1522 #[test]
test_try_fold_unit()1523 fn test_try_fold_unit() {
1524 let v: VecDeque<()> = std::iter::repeat(()).take(42).collect();
1525 assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
1526 }
1527
1528 #[test]
test_try_fold_unit_none()1529 fn test_try_fold_unit_none() {
1530 let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect();
1531 let mut iter = v.into_iter();
1532 assert!(iter.try_fold((), |_, _| None).is_none());
1533 assert_eq!(iter.len(), 9);
1534 }
1535
1536 #[test]
test_try_fold_rotated()1537 fn test_try_fold_rotated() {
1538 let mut v: VecDeque<_> = (0..12).collect();
1539 for n in 0..10 {
1540 if n & 1 == 0 {
1541 v.rotate_left(n);
1542 } else {
1543 v.rotate_right(n);
1544 }
1545 assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
1546 }
1547 }
1548
1549 #[test]
test_try_fold_moves_iter()1550 fn test_try_fold_moves_iter() {
1551 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1552 let mut iter = v.into_iter();
1553 assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
1554 assert_eq!(iter.next(), Some(&60));
1555 }
1556
1557 #[test]
test_try_fold_exhaust_wrap()1558 fn test_try_fold_exhaust_wrap() {
1559 let mut v = VecDeque::with_capacity(7);
1560 v.push_back(1);
1561 v.push_back(1);
1562 v.push_back(1);
1563 v.pop_front();
1564 v.pop_front();
1565 let mut iter = v.iter();
1566 let _ = iter.try_fold(0, |_, _| Some(1));
1567 assert!(iter.is_empty());
1568 }
1569
1570 #[test]
test_try_fold_wraparound()1571 fn test_try_fold_wraparound() {
1572 let mut v = VecDeque::with_capacity(8);
1573 v.push_back(7);
1574 v.push_back(8);
1575 v.push_back(9);
1576 v.push_front(2);
1577 v.push_front(1);
1578 let mut iter = v.iter();
1579 let _ = iter.find(|&&x| x == 2);
1580 assert_eq!(Some(&7), iter.next());
1581 }
1582
1583 #[test]
test_try_rfold_rotated()1584 fn test_try_rfold_rotated() {
1585 let mut v: VecDeque<_> = (0..12).collect();
1586 for n in 0..10 {
1587 if n & 1 == 0 {
1588 v.rotate_left(n);
1589 } else {
1590 v.rotate_right(n);
1591 }
1592 assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
1593 }
1594 }
1595
1596 #[test]
test_try_rfold_moves_iter()1597 fn test_try_rfold_moves_iter() {
1598 let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1599 let mut iter = v.into_iter();
1600 assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
1601 assert_eq!(iter.next_back(), Some(&70));
1602 }
1603
1604 #[test]
1605 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
truncate_leak()1606 fn truncate_leak() {
1607 static mut DROPS: i32 = 0;
1608
1609 struct D(bool);
1610
1611 impl Drop for D {
1612 fn drop(&mut self) {
1613 unsafe {
1614 DROPS += 1;
1615 }
1616
1617 if self.0 {
1618 panic!("panic in `drop`");
1619 }
1620 }
1621 }
1622
1623 let mut q = VecDeque::new();
1624 q.push_back(D(false));
1625 q.push_back(D(false));
1626 q.push_back(D(false));
1627 q.push_back(D(false));
1628 q.push_back(D(false));
1629 q.push_front(D(true));
1630 q.push_front(D(false));
1631 q.push_front(D(false));
1632
1633 catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
1634
1635 assert_eq!(unsafe { DROPS }, 7);
1636 }
1637
1638 #[test]
1639 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
test_drain_leak()1640 fn test_drain_leak() {
1641 static mut DROPS: i32 = 0;
1642
1643 #[derive(Debug, PartialEq)]
1644 struct D(u32, bool);
1645
1646 impl Drop for D {
1647 fn drop(&mut self) {
1648 unsafe {
1649 DROPS += 1;
1650 }
1651
1652 if self.1 {
1653 panic!("panic in `drop`");
1654 }
1655 }
1656 }
1657
1658 let mut v = VecDeque::new();
1659 v.push_back(D(4, false));
1660 v.push_back(D(5, false));
1661 v.push_back(D(6, false));
1662 v.push_front(D(3, false));
1663 v.push_front(D(2, true));
1664 v.push_front(D(1, false));
1665 v.push_front(D(0, false));
1666
1667 catch_unwind(AssertUnwindSafe(|| {
1668 v.drain(1..=4);
1669 }))
1670 .ok();
1671
1672 assert_eq!(unsafe { DROPS }, 4);
1673 assert_eq!(v.len(), 3);
1674 drop(v);
1675 assert_eq!(unsafe { DROPS }, 7);
1676 }
1677
1678 #[test]
test_binary_search()1679 fn test_binary_search() {
1680 // Contiguous (front only) search:
1681 let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1682 assert!(deque.as_slices().1.is_empty());
1683 assert_eq!(deque.binary_search(&3), Ok(2));
1684 assert_eq!(deque.binary_search(&4), Err(3));
1685
1686 // Split search (both front & back non-empty):
1687 let mut deque: VecDeque<_> = vec![5, 6].into();
1688 deque.push_front(3);
1689 deque.push_front(2);
1690 deque.push_front(1);
1691 deque.push_back(10);
1692 assert!(!deque.as_slices().0.is_empty());
1693 assert!(!deque.as_slices().1.is_empty());
1694 assert_eq!(deque.binary_search(&0), Err(0));
1695 assert_eq!(deque.binary_search(&1), Ok(0));
1696 assert_eq!(deque.binary_search(&5), Ok(3));
1697 assert_eq!(deque.binary_search(&7), Err(5));
1698 assert_eq!(deque.binary_search(&20), Err(6));
1699 }
1700
1701 #[test]
test_binary_search_by()1702 fn test_binary_search_by() {
1703 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1704
1705 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&3)), Ok(2));
1706 assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&4)), Err(3));
1707 }
1708
1709 #[test]
test_binary_search_by_key()1710 fn test_binary_search_by_key() {
1711 let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1712
1713 assert_eq!(deque.binary_search_by_key(&3, |&(v,)| v), Ok(2));
1714 assert_eq!(deque.binary_search_by_key(&4, |&(v,)| v), Err(3));
1715 }
1716
1717 #[test]
test_partition_point()1718 fn test_partition_point() {
1719 // Contiguous (front only) search:
1720 let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1721 assert!(deque.as_slices().1.is_empty());
1722 assert_eq!(deque.partition_point(|&v| v <= 3), 3);
1723
1724 // Split search (both front & back non-empty):
1725 let mut deque: VecDeque<_> = vec![5, 6].into();
1726 deque.push_front(3);
1727 deque.push_front(2);
1728 deque.push_front(1);
1729 deque.push_back(10);
1730 assert!(!deque.as_slices().0.is_empty());
1731 assert!(!deque.as_slices().1.is_empty());
1732 assert_eq!(deque.partition_point(|&v| v <= 5), 4);
1733 }
1734
1735 #[test]
test_zero_sized_push()1736 fn test_zero_sized_push() {
1737 const N: usize = 8;
1738
1739 // Zero sized type
1740 struct Zst;
1741
1742 // Test that for all possible sequences of push_front / push_back,
1743 // we end up with a deque of the correct size
1744
1745 for len in 0..N {
1746 let mut tester = VecDeque::with_capacity(len);
1747 assert_eq!(tester.len(), 0);
1748 assert!(tester.capacity() >= len);
1749 for case in 0..(1 << len) {
1750 assert_eq!(tester.len(), 0);
1751 for bit in 0..len {
1752 if case & (1 << bit) != 0 {
1753 tester.push_front(Zst);
1754 } else {
1755 tester.push_back(Zst);
1756 }
1757 }
1758 assert_eq!(tester.len(), len);
1759 assert_eq!(tester.iter().count(), len);
1760 tester.clear();
1761 }
1762 }
1763 }
1764
1765 #[test]
test_from_zero_sized_vec()1766 fn test_from_zero_sized_vec() {
1767 let v = vec![(); 100];
1768 let queue = VecDeque::from(v);
1769 assert_eq!(queue.len(), 100);
1770 }
1771
1772 #[test]
test_resize_keeps_reserved_space_from_item()1773 fn test_resize_keeps_reserved_space_from_item() {
1774 let v = Vec::<i32>::with_capacity(1234);
1775 let mut d = VecDeque::new();
1776 d.resize(1, v);
1777 assert_eq!(d[0].capacity(), 1234);
1778 }
1779
1780 #[test]
test_collect_from_into_iter_keeps_allocation()1781 fn test_collect_from_into_iter_keeps_allocation() {
1782 let mut v = Vec::with_capacity(13);
1783 v.extend(0..7);
1784 check(v.as_ptr(), v.last().unwrap(), v.into_iter());
1785
1786 let mut v = VecDeque::with_capacity(13);
1787 v.extend(0..7);
1788 check(&v[0], &v[v.len() - 1], v.into_iter());
1789
1790 fn check(buf: *const i32, last: *const i32, mut it: impl Iterator<Item = i32>) {
1791 assert_eq!(it.next(), Some(0));
1792 assert_eq!(it.next(), Some(1));
1793
1794 let mut v: VecDeque<i32> = it.collect();
1795 assert_eq!(v.capacity(), 13);
1796 assert_eq!(v.as_slices().0.as_ptr(), buf.wrapping_add(2));
1797 assert_eq!(&v[v.len() - 1] as *const _, last);
1798
1799 assert_eq!(v.as_slices(), ([2, 3, 4, 5, 6].as_slice(), [].as_slice()));
1800 v.push_front(7);
1801 assert_eq!(v.as_slices(), ([7, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
1802 v.push_front(8);
1803 assert_eq!(v.as_slices(), ([8, 7, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
1804
1805 // Now that we've adding thing in place of the two that we removed from
1806 // the front of the iterator, we're back to matching the buffer pointer.
1807 assert_eq!(v.as_slices().0.as_ptr(), buf);
1808 assert_eq!(&v[v.len() - 1] as *const _, last);
1809
1810 v.push_front(9);
1811 assert_eq!(v.as_slices(), ([9].as_slice(), [8, 7, 2, 3, 4, 5, 6].as_slice()));
1812 assert_eq!(v.capacity(), 13);
1813 }
1814 }
1815