2 use std::collections::TryReserveError::*;
5 use std::panic::{catch_unwind, AssertUnwindSafe};
6 use std::vec::{Drain, IntoIter};
8 struct DropCounter<'a> {
12 impl Drop for DropCounter<'_> {
19 fn test_small_vec_struct() {
20 assert_eq!(size_of::<Vec<u8>>(), size_of::<usize>() * 3);
24 fn test_double_drop() {
30 let (mut count_x, mut count_y) = (0, 0);
32 let mut tv = TwoVec { x: Vec::new(), y: Vec::new() };
33 tv.x.push(DropCounter { count: &mut count_x });
34 tv.y.push(DropCounter { count: &mut count_y });
36 // If Vec had a drop flag, here is where it would be zeroed.
37 // Instead, it should rely on its internal state to prevent
38 // doing anything significant when dropped multiple times.
41 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
44 assert_eq!(count_x, 1);
45 assert_eq!(count_y, 1);
50 let mut v = Vec::new();
51 assert_eq!(v.capacity(), 0);
54 assert!(v.capacity() >= 2);
60 assert!(v.capacity() >= 16);
62 assert!(v.capacity() >= 32);
67 assert!(v.capacity() >= 33)
71 fn test_zst_capacity() {
72 assert_eq!(Vec::<()>::new().capacity(), usize::MAX);
77 let mut v = Vec::new();
78 let mut w = Vec::new();
97 v.extend(w.clone()); // specializes to `append`
98 assert!(v.iter().eq(w.iter().chain(w.iter())));
101 #[derive(PartialEq, Debug)]
104 let mut a = Vec::new();
105 let b = vec![Foo, Foo];
108 assert_eq!(a, &[Foo, Foo]);
113 let mut x = Vec::new();
114 let y = vec![DropCounter { count: &mut count_x }];
117 assert_eq!(count_x, 1);
121 fn test_extend_ref() {
122 let mut v = vec![1, 2];
123 v.extend(&[3, 4, 5]);
125 assert_eq!(v.len(), 5);
126 assert_eq!(v, [1, 2, 3, 4, 5]);
131 assert_eq!(v.len(), 7);
132 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
136 fn test_remove_item() {
137 let mut v = vec![1, 2, 3];
140 assert_eq!(v.len(), 2);
141 assert_eq!(v, [2, 3]);
143 let mut w = vec![1, 2, 3];
146 assert_eq!(w.len(), 3);
151 fn test_slice_from_mut() {
152 let mut values = vec![1, 2, 3, 4, 5];
154 let slice = &mut values[2..];
155 assert!(slice == [3, 4, 5]);
161 assert!(values == [1, 2, 5, 6, 7]);
165 fn test_slice_to_mut() {
166 let mut values = vec![1, 2, 3, 4, 5];
168 let slice = &mut values[..2];
169 assert!(slice == [1, 2]);
175 assert!(values == [2, 3, 3, 4, 5]);
179 fn test_split_at_mut() {
180 let mut values = vec![1, 2, 3, 4, 5];
182 let (left, right) = values.split_at_mut(2);
184 let left: &[_] = left;
185 assert!(&left[..left.len()] == &[1, 2]);
192 let right: &[_] = right;
193 assert!(&right[..right.len()] == &[3, 4, 5]);
200 assert_eq!(values, [2, 3, 5, 6, 7]);
205 let v: Vec<i32> = vec![];
206 let w = vec![1, 2, 3];
208 assert_eq!(v, v.clone());
212 // they should be disjoint in memory.
213 assert!(w.as_ptr() != z.as_ptr())
217 fn test_clone_from() {
219 let three: Vec<Box<_>> = vec![box 1, box 2, box 3];
220 let two: Vec<Box<_>> = vec![box 4, box 5];
222 v.clone_from(&three);
223 assert_eq!(v, three);
226 v.clone_from(&three);
227 assert_eq!(v, three);
234 v.clone_from(&three);
240 let mut vec = vec![1, 2, 3, 4];
241 vec.retain(|&x| x % 2 == 0);
242 assert_eq!(vec, [2, 4]);
247 fn case(a: Vec<i32>, b: Vec<i32>) {
252 case(vec![], vec![]);
253 case(vec![1], vec![1]);
254 case(vec![1, 1], vec![1]);
255 case(vec![1, 2, 3], vec![1, 2, 3]);
256 case(vec![1, 1, 2, 3], vec![1, 2, 3]);
257 case(vec![1, 2, 2, 3], vec![1, 2, 3]);
258 case(vec![1, 2, 3, 3], vec![1, 2, 3]);
259 case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
263 fn test_dedup_by_key() {
264 fn case(a: Vec<i32>, b: Vec<i32>) {
266 v.dedup_by_key(|i| *i / 10);
269 case(vec![], vec![]);
270 case(vec![10], vec![10]);
271 case(vec![10, 11], vec![10]);
272 case(vec![10, 20, 30], vec![10, 20, 30]);
273 case(vec![10, 11, 20, 30], vec![10, 20, 30]);
274 case(vec![10, 20, 21, 30], vec![10, 20, 30]);
275 case(vec![10, 20, 30, 31], vec![10, 20, 30]);
276 case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
281 let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
282 vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
284 assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
286 let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
287 vec.dedup_by(|a, b| {
294 assert_eq!(vec, [("foo", 3), ("bar", 12)]);
298 fn test_dedup_unique() {
299 let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
301 let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
303 let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
305 // If the boxed pointers were leaked or otherwise misused, valgrind
306 // and/or rt should raise errors.
310 fn zero_sized_values() {
311 let mut v = Vec::new();
312 assert_eq!(v.len(), 0);
314 assert_eq!(v.len(), 1);
316 assert_eq!(v.len(), 2);
317 assert_eq!(v.pop(), Some(()));
318 assert_eq!(v.pop(), Some(()));
319 assert_eq!(v.pop(), None);
321 assert_eq!(v.iter().count(), 0);
323 assert_eq!(v.iter().count(), 1);
325 assert_eq!(v.iter().count(), 2);
329 assert_eq!(v.iter_mut().count(), 2);
331 assert_eq!(v.iter_mut().count(), 3);
333 assert_eq!(v.iter_mut().count(), 4);
335 for &mut () in &mut v {}
339 assert_eq!(v.iter_mut().count(), 0);
343 fn test_partition() {
344 assert_eq!(vec![].into_iter().partition(|x: &i32| *x < 3), (vec![], vec![]));
345 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 4), (vec![1, 2, 3], vec![]));
346 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 2), (vec![1], vec![2, 3]));
347 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 0), (vec![], vec![1, 2, 3]));
351 fn test_zip_unzip() {
352 let z1 = vec![(1, 4), (2, 5), (3, 6)];
354 let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
356 assert_eq!((1, 4), (left[0], right[0]));
357 assert_eq!((2, 5), (left[1], right[1]));
358 assert_eq!((3, 6), (left[2], right[2]));
362 fn test_vec_truncate_drop() {
363 static mut DROPS: u32 = 0;
373 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
374 assert_eq!(unsafe { DROPS }, 0);
376 assert_eq!(unsafe { DROPS }, 2);
378 assert_eq!(unsafe { DROPS }, 5);
383 fn test_vec_truncate_fail() {
385 impl Drop for BadElem {
387 let BadElem(ref mut x) = *self;
389 panic!("BadElem panic: 0xbadbeef")
394 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
400 let vec = vec![1, 2, 3];
401 assert!(vec[1] == 2);
406 fn test_index_out_of_bounds() {
407 let vec = vec![1, 2, 3];
413 fn test_slice_out_of_bounds_1() {
414 let x = vec![1, 2, 3, 4, 5];
420 fn test_slice_out_of_bounds_2() {
421 let x = vec![1, 2, 3, 4, 5];
427 fn test_slice_out_of_bounds_3() {
428 let x = vec![1, 2, 3, 4, 5];
434 fn test_slice_out_of_bounds_4() {
435 let x = vec![1, 2, 3, 4, 5];
441 fn test_slice_out_of_bounds_5() {
442 let x = vec![1, 2, 3, 4, 5];
448 fn test_swap_remove_empty() {
449 let mut vec = Vec::<i32>::new();
454 fn test_move_items() {
455 let vec = vec![1, 2, 3];
456 let mut vec2 = vec![];
460 assert_eq!(vec2, [1, 2, 3]);
464 fn test_move_items_reverse() {
465 let vec = vec![1, 2, 3];
466 let mut vec2 = vec![];
467 for i in vec.into_iter().rev() {
470 assert_eq!(vec2, [3, 2, 1]);
474 fn test_move_items_zero_sized() {
475 let vec = vec![(), (), ()];
476 let mut vec2 = vec![];
480 assert_eq!(vec2, [(), (), ()]);
484 fn test_drain_items() {
485 let mut vec = vec![1, 2, 3];
486 let mut vec2 = vec![];
487 for i in vec.drain(..) {
491 assert_eq!(vec2, [1, 2, 3]);
495 fn test_drain_items_reverse() {
496 let mut vec = vec![1, 2, 3];
497 let mut vec2 = vec![];
498 for i in vec.drain(..).rev() {
502 assert_eq!(vec2, [3, 2, 1]);
506 fn test_drain_items_zero_sized() {
507 let mut vec = vec![(), (), ()];
508 let mut vec2 = vec![];
509 for i in vec.drain(..) {
513 assert_eq!(vec2, [(), (), ()]);
518 fn test_drain_out_of_bounds() {
519 let mut v = vec![1, 2, 3, 4, 5];
524 fn test_drain_range() {
525 let mut v = vec![1, 2, 3, 4, 5];
526 for _ in v.drain(4..) {}
527 assert_eq!(v, &[1, 2, 3, 4]);
529 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
530 for _ in v.drain(1..4) {}
531 assert_eq!(v, &[1.to_string(), 5.to_string()]);
533 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
534 for _ in v.drain(1..4).rev() {}
535 assert_eq!(v, &[1.to_string(), 5.to_string()]);
537 let mut v: Vec<_> = vec![(); 5];
538 for _ in v.drain(1..4).rev() {}
539 assert_eq!(v, &[(), ()]);
543 fn test_drain_inclusive_range() {
544 let mut v = vec!['a', 'b', 'c', 'd', 'e'];
545 for _ in v.drain(1..=3) {}
546 assert_eq!(v, &['a', 'e']);
548 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
549 for _ in v.drain(1..=5) {}
550 assert_eq!(v, &["0".to_string()]);
552 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
553 for _ in v.drain(0..=5) {}
554 assert_eq!(v, Vec::<String>::new());
556 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
557 for _ in v.drain(0..=3) {}
558 assert_eq!(v, &["4".to_string(), "5".to_string()]);
560 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
561 for _ in v.drain(..=0) {}
562 assert_eq!(v, &["1".to_string()]);
566 fn test_drain_max_vec_size() {
567 let mut v = Vec::<()>::with_capacity(usize::MAX);
569 v.set_len(usize::MAX);
571 for _ in v.drain(usize::MAX - 1..) {}
572 assert_eq!(v.len(), usize::MAX - 1);
574 let mut v = Vec::<()>::with_capacity(usize::MAX);
576 v.set_len(usize::MAX);
578 for _ in v.drain(usize::MAX - 1..=usize::MAX - 1) {}
579 assert_eq!(v.len(), usize::MAX - 1);
584 fn test_drain_inclusive_out_of_bounds() {
585 let mut v = vec![1, 2, 3, 4, 5];
590 fn test_drain_leak() {
591 static mut DROPS: i32 = 0;
593 #[derive(Debug, PartialEq)]
603 panic!("panic in `drop`");
618 catch_unwind(AssertUnwindSafe(|| {
623 assert_eq!(unsafe { DROPS }, 4);
624 assert_eq!(v, vec![D(0, false), D(1, false), D(6, false),]);
629 let mut v = vec![1, 2, 3, 4, 5];
630 let a = [10, 11, 12];
631 v.splice(2..4, a.iter().cloned());
632 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
633 v.splice(1..3, Some(20));
634 assert_eq!(v, &[1, 20, 11, 12, 5]);
638 fn test_splice_inclusive_range() {
639 let mut v = vec![1, 2, 3, 4, 5];
640 let a = [10, 11, 12];
641 let t1: Vec<_> = v.splice(2..=3, a.iter().cloned()).collect();
642 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
643 assert_eq!(t1, &[3, 4]);
644 let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
645 assert_eq!(v, &[1, 20, 11, 12, 5]);
646 assert_eq!(t2, &[2, 10]);
651 fn test_splice_out_of_bounds() {
652 let mut v = vec![1, 2, 3, 4, 5];
653 let a = [10, 11, 12];
654 v.splice(5..6, a.iter().cloned());
659 fn test_splice_inclusive_out_of_bounds() {
660 let mut v = vec![1, 2, 3, 4, 5];
661 let a = [10, 11, 12];
662 v.splice(5..=5, a.iter().cloned());
666 fn test_splice_items_zero_sized() {
667 let mut vec = vec![(), (), ()];
669 let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
670 assert_eq!(vec, &[(), ()]);
671 assert_eq!(t, &[()]);
675 fn test_splice_unbounded() {
676 let mut vec = vec![1, 2, 3, 4, 5];
677 let t: Vec<_> = vec.splice(.., None).collect();
678 assert_eq!(vec, &[]);
679 assert_eq!(t, &[1, 2, 3, 4, 5]);
683 fn test_splice_forget() {
684 let mut v = vec![1, 2, 3, 4, 5];
685 let a = [10, 11, 12];
686 std::mem::forget(v.splice(2..4, a.iter().cloned()));
687 assert_eq!(v, &[1, 2]);
691 fn test_into_boxed_slice() {
692 let xs = vec![1, 2, 3];
693 let ys = xs.into_boxed_slice();
694 assert_eq!(&*ys, [1, 2, 3]);
699 let mut vec = vec![1, 2, 3];
700 let mut vec2 = vec![4, 5, 6];
701 vec.append(&mut vec2);
702 assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
703 assert_eq!(vec2, []);
707 fn test_split_off() {
708 let mut vec = vec![1, 2, 3, 4, 5, 6];
709 let vec2 = vec.split_off(4);
710 assert_eq!(vec, [1, 2, 3, 4]);
711 assert_eq!(vec2, [5, 6]);
715 fn test_into_iter_as_slice() {
716 let vec = vec!['a', 'b', 'c'];
717 let mut into_iter = vec.into_iter();
718 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
719 let _ = into_iter.next().unwrap();
720 assert_eq!(into_iter.as_slice(), &['b', 'c']);
721 let _ = into_iter.next().unwrap();
722 let _ = into_iter.next().unwrap();
723 assert_eq!(into_iter.as_slice(), &[]);
727 fn test_into_iter_as_mut_slice() {
728 let vec = vec!['a', 'b', 'c'];
729 let mut into_iter = vec.into_iter();
730 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
731 into_iter.as_mut_slice()[0] = 'x';
732 into_iter.as_mut_slice()[1] = 'y';
733 assert_eq!(into_iter.next().unwrap(), 'x');
734 assert_eq!(into_iter.as_slice(), &['y', 'c']);
738 fn test_into_iter_debug() {
739 let vec = vec!['a', 'b', 'c'];
740 let into_iter = vec.into_iter();
741 let debug = format!("{:?}", into_iter);
742 assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
746 fn test_into_iter_count() {
747 assert_eq!(vec![1, 2, 3].into_iter().count(), 3);
751 fn test_into_iter_clone() {
752 fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
753 let v: Vec<i32> = it.collect();
754 assert_eq!(&v[..], slice);
756 let mut it = vec![1, 2, 3].into_iter();
757 iter_equal(it.clone(), &[1, 2, 3]);
758 assert_eq!(it.next(), Some(1));
759 let mut it = it.rev();
760 iter_equal(it.clone(), &[3, 2]);
761 assert_eq!(it.next(), Some(3));
762 iter_equal(it.clone(), &[2]);
763 assert_eq!(it.next(), Some(2));
764 iter_equal(it.clone(), &[]);
765 assert_eq!(it.next(), None);
769 fn test_into_iter_leak() {
770 static mut DROPS: i32 = 0;
781 panic!("panic in `drop`");
786 let v = vec![D(false), D(true), D(false)];
788 catch_unwind(move || drop(v.into_iter())).ok();
790 assert_eq!(unsafe { DROPS }, 3);
795 let borrowed: &[_] = &["borrowed", "(slice)"];
796 let owned = vec!["owned", "(vec)"];
797 match (Cow::from(owned.clone()), Cow::from(borrowed)) {
798 (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
799 _ => panic!("invalid `Cow::from`"),
805 let borrowed: &[_] = &["borrowed", "(slice)"];
806 let owned = vec!["owned", "(vec)"];
807 assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
808 assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
812 fn assert_covariance() {
813 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
816 fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
822 fn from_into_inner() {
823 let vec = vec![1, 2, 3];
824 let ptr = vec.as_ptr();
825 let vec = vec.into_iter().collect::<Vec<_>>();
826 assert_eq!(vec, [1, 2, 3]);
827 assert_eq!(vec.as_ptr(), ptr);
829 let ptr = &vec[1] as *const _;
830 let mut it = vec.into_iter();
832 let vec = it.collect::<Vec<_>>();
833 assert_eq!(vec, [2, 3]);
834 assert!(ptr != vec.as_ptr());
838 fn overaligned_allocations() {
841 let mut v = vec![Foo(273)];
844 assert!(v[0].0 == 273);
845 assert!(v.as_ptr() as usize & 0xff == 0);
847 assert!(v[0].0 == 273);
848 assert!(v.as_ptr() as usize & 0xff == 0);
853 fn drain_filter_empty() {
854 let mut vec: Vec<i32> = vec![];
857 let mut iter = vec.drain_filter(|_| true);
858 assert_eq!(iter.size_hint(), (0, Some(0)));
859 assert_eq!(iter.next(), None);
860 assert_eq!(iter.size_hint(), (0, Some(0)));
861 assert_eq!(iter.next(), None);
862 assert_eq!(iter.size_hint(), (0, Some(0)));
864 assert_eq!(vec.len(), 0);
865 assert_eq!(vec, vec![]);
869 fn drain_filter_zst() {
870 let mut vec = vec![(), (), (), (), ()];
871 let initial_len = vec.len();
874 let mut iter = vec.drain_filter(|_| true);
875 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
876 while let Some(_) = iter.next() {
878 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
880 assert_eq!(iter.size_hint(), (0, Some(0)));
881 assert_eq!(iter.next(), None);
882 assert_eq!(iter.size_hint(), (0, Some(0)));
885 assert_eq!(count, initial_len);
886 assert_eq!(vec.len(), 0);
887 assert_eq!(vec, vec![]);
891 fn drain_filter_false() {
892 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
894 let initial_len = vec.len();
897 let mut iter = vec.drain_filter(|_| false);
898 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
899 for _ in iter.by_ref() {
902 assert_eq!(iter.size_hint(), (0, Some(0)));
903 assert_eq!(iter.next(), None);
904 assert_eq!(iter.size_hint(), (0, Some(0)));
907 assert_eq!(count, 0);
908 assert_eq!(vec.len(), initial_len);
909 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
913 fn drain_filter_true() {
914 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
916 let initial_len = vec.len();
919 let mut iter = vec.drain_filter(|_| true);
920 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
921 while let Some(_) = iter.next() {
923 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
925 assert_eq!(iter.size_hint(), (0, Some(0)));
926 assert_eq!(iter.next(), None);
927 assert_eq!(iter.size_hint(), (0, Some(0)));
930 assert_eq!(count, initial_len);
931 assert_eq!(vec.len(), 0);
932 assert_eq!(vec, vec![]);
936 fn drain_filter_complex() {
938 // [+xxx++++++xxxxx++++x+x++]
940 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
944 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
945 assert_eq!(removed.len(), 10);
946 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
948 assert_eq!(vec.len(), 14);
949 assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
953 // [xxx++++++xxxxx++++x+x++]
955 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
958 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
959 assert_eq!(removed.len(), 10);
960 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
962 assert_eq!(vec.len(), 13);
963 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
967 // [xxx++++++xxxxx++++x+x]
969 vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36];
971 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
972 assert_eq!(removed.len(), 10);
973 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
975 assert_eq!(vec.len(), 11);
976 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
980 // [xxxxxxxxxx+++++++++++]
981 let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
983 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
984 assert_eq!(removed.len(), 10);
985 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
987 assert_eq!(vec.len(), 10);
988 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
992 // [+++++++++++xxxxxxxxxx]
993 let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
995 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
996 assert_eq!(removed.len(), 10);
997 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
999 assert_eq!(vec.len(), 10);
1000 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1004 // FIXME: re-enable emscripten once it can unwind again
1006 #[cfg(not(target_os = "emscripten"))]
1007 fn drain_filter_consumed_panic() {
1009 use std::sync::Mutex;
1013 drop_counts: Rc<Mutex<Vec<usize>>>,
1016 impl Drop for Check {
1017 fn drop(&mut self) {
1018 self.drop_counts.lock().unwrap()[self.index] += 1;
1019 println!("drop: {}", self.index);
1023 let check_count = 10;
1024 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1025 let mut data: Vec<Check> = (0..check_count)
1026 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1029 let _ = std::panic::catch_unwind(move || {
1030 let filter = |c: &mut Check| {
1032 panic!("panic at index: {}", c.index);
1034 // Verify that if the filter could panic again on another element
1035 // that it would not cause a double panic and all elements of the
1036 // vec would still be dropped exactly once.
1038 panic!("panic at index: {}", c.index);
1042 let drain = data.drain_filter(filter);
1044 // NOTE: The DrainFilter is explicitly consumed
1045 drain.for_each(drop);
1048 let drop_counts = drop_counts.lock().unwrap();
1049 assert_eq!(check_count, drop_counts.len());
1051 for (index, count) in drop_counts.iter().cloned().enumerate() {
1052 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1056 // FIXME: Re-enable emscripten once it can catch panics
1058 #[cfg(not(target_os = "emscripten"))]
1059 fn drain_filter_unconsumed_panic() {
1061 use std::sync::Mutex;
1065 drop_counts: Rc<Mutex<Vec<usize>>>,
1068 impl Drop for Check {
1069 fn drop(&mut self) {
1070 self.drop_counts.lock().unwrap()[self.index] += 1;
1071 println!("drop: {}", self.index);
1075 let check_count = 10;
1076 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1077 let mut data: Vec<Check> = (0..check_count)
1078 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1081 let _ = std::panic::catch_unwind(move || {
1082 let filter = |c: &mut Check| {
1084 panic!("panic at index: {}", c.index);
1086 // Verify that if the filter could panic again on another element
1087 // that it would not cause a double panic and all elements of the
1088 // vec would still be dropped exactly once.
1090 panic!("panic at index: {}", c.index);
1094 let _drain = data.drain_filter(filter);
1096 // NOTE: The DrainFilter is dropped without being consumed
1099 let drop_counts = drop_counts.lock().unwrap();
1100 assert_eq!(check_count, drop_counts.len());
1102 for (index, count) in drop_counts.iter().cloned().enumerate() {
1103 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1108 fn drain_filter_unconsumed() {
1109 let mut vec = vec![1, 2, 3, 4];
1110 let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1112 assert_eq!(vec, [2, 4]);
1116 fn test_reserve_exact() {
1117 // This is all the same as test_reserve
1119 let mut v = Vec::new();
1120 assert_eq!(v.capacity(), 0);
1123 assert!(v.capacity() >= 2);
1129 assert!(v.capacity() >= 16);
1130 v.reserve_exact(16);
1131 assert!(v.capacity() >= 32);
1135 v.reserve_exact(16);
1136 assert!(v.capacity() >= 33)
1140 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1141 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1142 fn test_try_reserve() {
1143 // These are the interesting cases:
1144 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1145 // * > isize::MAX should always fail
1146 // * On 16/32-bit should CapacityOverflow
1147 // * On 64-bit should OOM
1148 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1149 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1151 const MAX_CAP: usize = isize::MAX as usize;
1152 const MAX_USIZE: usize = usize::MAX;
1154 // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1155 // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1156 // Any platform that succeeds for these requests is technically broken with
1157 // ptr::offset because LLVM is the worst.
1158 let guards_against_isize = size_of::<usize>() < 8;
1161 // Note: basic stuff is checked by test_reserve
1162 let mut empty_bytes: Vec<u8> = Vec::new();
1164 // Check isize::MAX doesn't count as an overflow
1165 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1166 panic!("isize::MAX shouldn't trigger an overflow!");
1168 // Play it again, frank! (just to be sure)
1169 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1170 panic!("isize::MAX shouldn't trigger an overflow!");
1173 if guards_against_isize {
1174 // Check isize::MAX + 1 does count as overflow
1175 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
1177 panic!("isize::MAX + 1 should trigger an overflow!")
1180 // Check usize::MAX does count as overflow
1181 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
1183 panic!("usize::MAX should trigger an overflow!")
1186 // Check isize::MAX + 1 is an OOM
1187 if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_CAP + 1) {
1189 panic!("isize::MAX + 1 should trigger an OOM!")
1192 // Check usize::MAX is an OOM
1193 if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE) {
1195 panic!("usize::MAX should trigger an OOM!")
1201 // Same basic idea, but with non-zero len
1202 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1204 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1205 panic!("isize::MAX shouldn't trigger an overflow!");
1207 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1208 panic!("isize::MAX shouldn't trigger an overflow!");
1210 if guards_against_isize {
1211 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
1213 panic!("isize::MAX + 1 should trigger an overflow!");
1216 if let Err(AllocError { .. }) = ten_bytes.try_reserve(MAX_CAP - 9) {
1218 panic!("isize::MAX + 1 should trigger an OOM!")
1221 // Should always overflow in the add-to-len
1222 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
1224 panic!("usize::MAX should trigger an overflow!")
1229 // Same basic idea, but with interesting type size
1230 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1232 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) {
1233 panic!("isize::MAX shouldn't trigger an overflow!");
1235 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) {
1236 panic!("isize::MAX shouldn't trigger an overflow!");
1238 if guards_against_isize {
1239 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) {
1241 panic!("isize::MAX + 1 should trigger an overflow!");
1244 if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) {
1246 panic!("isize::MAX + 1 should trigger an OOM!")
1249 // Should fail in the mul-by-size
1250 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
1252 panic!("usize::MAX should trigger an overflow!");
1258 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1259 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1260 fn test_try_reserve_exact() {
1261 // This is exactly the same as test_try_reserve with the method changed.
1262 // See that test for comments.
1264 const MAX_CAP: usize = isize::MAX as usize;
1265 const MAX_USIZE: usize = usize::MAX;
1267 let guards_against_isize = size_of::<usize>() < 8;
1270 let mut empty_bytes: Vec<u8> = Vec::new();
1272 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1273 panic!("isize::MAX shouldn't trigger an overflow!");
1275 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1276 panic!("isize::MAX shouldn't trigger an overflow!");
1279 if guards_against_isize {
1280 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1282 panic!("isize::MAX + 1 should trigger an overflow!")
1285 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1287 panic!("usize::MAX should trigger an overflow!")
1290 if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1292 panic!("isize::MAX + 1 should trigger an OOM!")
1295 if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1297 panic!("usize::MAX should trigger an OOM!")
1303 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1305 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1306 panic!("isize::MAX shouldn't trigger an overflow!");
1308 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1309 panic!("isize::MAX shouldn't trigger an overflow!");
1311 if guards_against_isize {
1312 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1314 panic!("isize::MAX + 1 should trigger an overflow!");
1317 if let Err(AllocError { .. }) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1319 panic!("isize::MAX + 1 should trigger an OOM!")
1322 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
1324 panic!("usize::MAX should trigger an overflow!")
1329 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1331 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) {
1332 panic!("isize::MAX shouldn't trigger an overflow!");
1334 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) {
1335 panic!("isize::MAX shouldn't trigger an overflow!");
1337 if guards_against_isize {
1338 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) {
1340 panic!("isize::MAX + 1 should trigger an overflow!");
1343 if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) {
1345 panic!("isize::MAX + 1 should trigger an OOM!")
1348 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
1350 panic!("usize::MAX should trigger an overflow!")
1356 fn test_stable_pointers() {
1357 /// Pull an element from the iterator, then drop it.
1358 /// Useful to cover both the `next` and `drop` paths of an iterator.
1359 fn next_then_drop<I: Iterator>(mut i: I) {
1364 // Test that, if we reserved enough space, adding and removing elements does not
1365 // invalidate references into the vector (such as `v0`). This test also
1366 // runs in Miri, which would detect such problems.
1367 let mut v = Vec::with_capacity(128);
1370 // Laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1372 let v0 = unsafe { &mut *(v0 as *mut _) };
1373 // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1375 // Pushing/inserting and popping/removing
1379 assert_eq!(*v0, 13);
1382 assert_eq!(*v0, 13);
1385 assert_eq!(v.len(), 2);
1386 v.swap_remove(1); // swap_remove the last element
1387 assert_eq!(*v0, 13);
1390 v.append(&mut vec![27, 19]);
1391 assert_eq!(*v0, 13);
1394 v.extend_from_slice(&[1, 2]);
1395 v.extend(&[1, 2]); // `slice::Iter` (with `T: Copy`) specialization
1396 v.extend(vec![2, 3]); // `vec::IntoIter` specialization
1397 v.extend(std::iter::once(3)); // `TrustedLen` specialization
1398 v.extend(std::iter::empty::<i32>()); // `TrustedLen` specialization with empty iterator
1399 v.extend(std::iter::once(3).filter(|_| true)); // base case
1400 v.extend(std::iter::once(&3)); // `cloned` specialization
1401 assert_eq!(*v0, 13);
1405 assert_eq!(*v0, 13);
1408 v.resize_with(v.len() + 10, || 42);
1409 assert_eq!(*v0, 13);
1410 v.resize_with(2, || panic!());
1411 assert_eq!(*v0, 13);
1413 // No-op reservation
1415 v.reserve_exact(32);
1416 assert_eq!(*v0, 13);
1419 v.resize_with(10, || 42);
1420 next_then_drop(v.drain(5..));
1421 assert_eq!(*v0, 13);
1424 v.resize_with(10, || 42);
1425 next_then_drop(v.splice(5.., vec![1, 2, 3, 4, 5])); // empty tail after range
1426 assert_eq!(*v0, 13);
1427 next_then_drop(v.splice(5..8, vec![1])); // replacement is smaller than original range
1428 assert_eq!(*v0, 13);
1429 next_then_drop(v.splice(5..6, vec![1; 10].into_iter().filter(|_| true))); // lower bound not exact
1430 assert_eq!(*v0, 13);
1432 // Smoke test that would fire even outside Miri if an actual relocation happened.
1434 assert_eq!(v[0], 0);
1437 // https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
1440 // unsafe impl<T: ?Sized> IsZero for *mut T {
1441 // fn is_zero(&self) -> bool {
1442 // (*self).is_null()
1447 // … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
1448 // which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
1449 // That is, a fat pointer can be “null” without being made entirely of zero bits.
1451 fn vec_macro_repeating_null_raw_fat_pointer() {
1452 let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
1453 let vtable = dbg!(ptr_metadata(raw_dyn));
1454 let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
1455 assert!(null_raw_dyn.is_null());
1457 let vec = vec![null_raw_dyn; 1];
1458 dbg!(ptr_metadata(vec[0]));
1459 assert!(vec[0] == null_raw_dyn);
1461 // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
1463 fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
1464 unsafe { std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable }
1467 fn ptr_from_raw_parts(data: *mut (), vtable: *mut ()) -> *mut dyn Fn() {
1468 unsafe { std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr { data, vtable }) }
1478 // This test will likely fail if you change the capacities used in
1479 // `RawVec::grow_amortized`.
1481 fn test_push_growth_strategy() {
1482 // If the element size is 1, we jump from 0 to 8, then double.
1484 let mut v1: Vec<u8> = vec![];
1485 assert_eq!(v1.capacity(), 0);
1489 assert_eq!(v1.capacity(), 8);
1494 assert_eq!(v1.capacity(), 16);
1499 assert_eq!(v1.capacity(), 32);
1504 assert_eq!(v1.capacity(), 64);
1508 // If the element size is 2..=1024, we jump from 0 to 4, then double.
1510 let mut v2: Vec<u16> = vec![];
1511 let mut v1024: Vec<[u8; 1024]> = vec![];
1512 assert_eq!(v2.capacity(), 0);
1513 assert_eq!(v1024.capacity(), 0);
1517 v1024.push([0; 1024]);
1518 assert_eq!(v2.capacity(), 4);
1519 assert_eq!(v1024.capacity(), 4);
1524 v1024.push([0; 1024]);
1525 assert_eq!(v2.capacity(), 8);
1526 assert_eq!(v1024.capacity(), 8);
1531 v1024.push([0; 1024]);
1532 assert_eq!(v2.capacity(), 16);
1533 assert_eq!(v1024.capacity(), 16);
1538 v1024.push([0; 1024]);
1539 assert_eq!(v2.capacity(), 32);
1540 assert_eq!(v1024.capacity(), 32);
1545 v1024.push([0; 1024]);
1546 assert_eq!(v2.capacity(), 64);
1547 assert_eq!(v1024.capacity(), 64);
1551 // If the element size is > 1024, we jump from 0 to 1, then double.
1553 let mut v1025: Vec<[u8; 1025]> = vec![];
1554 assert_eq!(v1025.capacity(), 0);
1557 v1025.push([0; 1025]);
1558 assert_eq!(v1025.capacity(), 1);
1562 v1025.push([0; 1025]);
1563 assert_eq!(v1025.capacity(), 2);
1567 v1025.push([0; 1025]);
1568 assert_eq!(v1025.capacity(), 4);
1572 v1025.push([0; 1025]);
1573 assert_eq!(v1025.capacity(), 8);
1577 v1025.push([0; 1025]);
1578 assert_eq!(v1025.capacity(), 16);
1582 v1025.push([0; 1025]);
1583 assert_eq!(v1025.capacity(), 32);
1587 v1025.push([0; 1025]);
1588 assert_eq!(v1025.capacity(), 64);
1593 macro_rules! generate_assert_eq_vec_and_prim {
1594 ($name:ident<$B:ident>($type:ty)) => {
1595 fn $name<A: PartialEq<$B> + Debug, $B: Debug>(a: Vec<A>, b: $type) {
1602 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_slice <B>(&[B]) }
1603 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_array_3<B>([B; 3]) }
1606 fn partialeq_vec_and_prim() {
1607 assert_eq_vec_and_slice(vec![1, 2, 3], &[1, 2, 3]);
1608 assert_eq_vec_and_array_3(vec![1, 2, 3], [1, 2, 3]);
1611 macro_rules! assert_partial_eq_valid {
1612 ($a2:ident, $a3:ident; $b2:ident, $b3: ident) => {
1613 assert!($a2 == $b2);
1614 assert!($a2 != $b3);
1615 assert!($a3 != $b2);
1616 assert!($a3 == $b3);
1617 assert_eq!($a2, $b2);
1618 assert_ne!($a2, $b3);
1619 assert_ne!($a3, $b2);
1620 assert_eq!($a3, $b3);
1625 fn partialeq_vec_full() {
1626 let vec2: Vec<_> = vec![1, 2];
1627 let vec3: Vec<_> = vec![1, 2, 3];
1628 let slice2: &[_] = &[1, 2];
1629 let slice3: &[_] = &[1, 2, 3];
1630 let slicemut2: &[_] = &mut [1, 2];
1631 let slicemut3: &[_] = &mut [1, 2, 3];
1632 let array2: [_; 2] = [1, 2];
1633 let array3: [_; 3] = [1, 2, 3];
1634 let arrayref2: &[_; 2] = &[1, 2];
1635 let arrayref3: &[_; 3] = &[1, 2, 3];
1637 assert_partial_eq_valid!(vec2,vec3; vec2,vec3);
1638 assert_partial_eq_valid!(vec2,vec3; slice2,slice3);
1639 assert_partial_eq_valid!(vec2,vec3; slicemut2,slicemut3);
1640 assert_partial_eq_valid!(slice2,slice3; vec2,vec3);
1641 assert_partial_eq_valid!(slicemut2,slicemut3; vec2,vec3);
1642 assert_partial_eq_valid!(vec2,vec3; array2,array3);
1643 assert_partial_eq_valid!(vec2,vec3; arrayref2,arrayref3);