1 use core::alloc::{Allocator, Layout};
2 use core::ptr::NonNull;
3 use std::alloc::System;
4 use std::assert_matches::assert_matches;
7 use std::collections::TryReserveErrorKind::*;
9 use std::iter::InPlaceIterable;
10 use std::mem::{size_of, swap};
11 use std::ops::Bound::*;
12 use std::panic::{catch_unwind, AssertUnwindSafe};
14 use std::sync::atomic::{AtomicU32, Ordering};
15 use std::vec::{Drain, IntoIter};
17 struct DropCounter<'a> {
21 impl Drop for DropCounter<'_> {
28 fn test_small_vec_struct() {
29 assert_eq!(size_of::<Vec<u8>>(), size_of::<usize>() * 3);
33 fn test_double_drop() {
39 let (mut count_x, mut count_y) = (0, 0);
41 let mut tv = TwoVec { x: Vec::new(), y: Vec::new() };
42 tv.x.push(DropCounter { count: &mut count_x });
43 tv.y.push(DropCounter { count: &mut count_y });
45 // If Vec had a drop flag, here is where it would be zeroed.
46 // Instead, it should rely on its internal state to prevent
47 // doing anything significant when dropped multiple times.
50 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
53 assert_eq!(count_x, 1);
54 assert_eq!(count_y, 1);
59 let mut v = Vec::new();
60 assert_eq!(v.capacity(), 0);
63 assert!(v.capacity() >= 2);
69 assert!(v.capacity() >= 16);
71 assert!(v.capacity() >= 32);
76 assert!(v.capacity() >= 33)
80 fn test_zst_capacity() {
81 assert_eq!(Vec::<()>::new().capacity(), usize::MAX);
86 let v: Vec<isize> = vec![10, 20];
91 assert_eq!(v[x + 1], 20);
94 assert_eq!(v[x - 1], 10);
99 let vec1: Vec<isize> = vec![];
100 assert_eq!("[]", format!("{:?}", vec1));
102 let vec2 = vec![0, 1];
103 assert_eq!("[0, 1]", format!("{:?}", vec2));
105 let slice: &[isize] = &[4, 5];
106 assert_eq!("[4, 5]", format!("{slice:?}"));
115 assert_eq!(v, [1, 2]);
117 assert_eq!(v, [1, 2, 3]);
122 let mut v = Vec::new();
123 let mut w = Vec::new();
142 v.extend(w.clone()); // specializes to `append`
143 assert!(v.iter().eq(w.iter().chain(w.iter())));
146 #[derive(PartialEq, Debug)]
149 let mut a = Vec::new();
150 let b = vec![Foo, Foo];
153 assert_eq!(a, &[Foo, Foo]);
158 let mut x = Vec::new();
159 let y = vec![DropCounter { count: &mut count_x }];
162 assert_eq!(count_x, 1);
166 fn test_extend_from_slice() {
167 let a: Vec<isize> = vec![1, 2, 3, 4, 5];
168 let b: Vec<isize> = vec![6, 7, 8, 9, 0];
170 let mut v: Vec<isize> = a;
172 v.extend_from_slice(&b);
174 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
178 fn test_extend_ref() {
179 let mut v = vec![1, 2];
180 v.extend(&[3, 4, 5]);
182 assert_eq!(v.len(), 5);
183 assert_eq!(v, [1, 2, 3, 4, 5]);
188 assert_eq!(v.len(), 7);
189 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
193 fn test_slice_from_ref() {
194 let values = vec![1, 2, 3, 4, 5];
195 let slice = &values[1..3];
197 assert_eq!(slice, [2, 3]);
201 fn test_slice_from_mut() {
202 let mut values = vec![1, 2, 3, 4, 5];
204 let slice = &mut values[2..];
205 assert!(slice == [3, 4, 5]);
211 assert!(values == [1, 2, 5, 6, 7]);
215 fn test_slice_to_mut() {
216 let mut values = vec![1, 2, 3, 4, 5];
218 let slice = &mut values[..2];
219 assert!(slice == [1, 2]);
225 assert!(values == [2, 3, 3, 4, 5]);
229 fn test_split_at_mut() {
230 let mut values = vec![1, 2, 3, 4, 5];
232 let (left, right) = values.split_at_mut(2);
234 let left: &[_] = left;
235 assert!(&left[..left.len()] == &[1, 2]);
242 let right: &[_] = right;
243 assert!(&right[..right.len()] == &[3, 4, 5]);
250 assert_eq!(values, [2, 3, 5, 6, 7]);
255 let v: Vec<i32> = vec![];
256 let w = vec![1, 2, 3];
258 assert_eq!(v, v.clone());
262 // they should be disjoint in memory.
263 assert!(w.as_ptr() != z.as_ptr())
267 fn test_clone_from() {
269 let three: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(3)];
270 let two: Vec<Box<_>> = vec![Box::new(4), Box::new(5)];
272 v.clone_from(&three);
273 assert_eq!(v, three);
276 v.clone_from(&three);
277 assert_eq!(v, three);
284 v.clone_from(&three);
290 let mut vec = vec![1, 2, 3, 4];
291 vec.retain(|&x| x % 2 == 0);
292 assert_eq!(vec, [2, 4]);
296 fn test_retain_pred_panic_with_hole() {
297 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
298 catch_unwind(AssertUnwindSafe(|| {
299 let mut v = v.clone();
300 v.retain(|r| match **r {
308 // Everything is dropped when predicate panicked.
309 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
313 fn test_retain_pred_panic_no_hole() {
314 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
315 catch_unwind(AssertUnwindSafe(|| {
316 let mut v = v.clone();
317 v.retain(|r| match **r {
323 // Everything is dropped when predicate panicked.
324 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
328 fn test_retain_drop_panic() {
329 struct Wrap(Rc<i32>);
339 let v = (0..5).map(|x| Rc::new(x)).collect::<Vec<_>>();
340 catch_unwind(AssertUnwindSafe(|| {
341 let mut v = v.iter().map(|r| Wrap(r.clone())).collect::<Vec<_>>();
342 v.retain(|w| match *w.0 {
346 3 => false, // Drop panic.
351 // Other elements are dropped when `drop` of one element panicked.
352 // The panicked wrapper also has its Rc dropped.
353 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
358 fn case(a: Vec<i32>, b: Vec<i32>) {
363 case(vec![], vec![]);
364 case(vec![1], vec![1]);
365 case(vec![1, 1], vec![1]);
366 case(vec![1, 2, 3], vec![1, 2, 3]);
367 case(vec![1, 1, 2, 3], vec![1, 2, 3]);
368 case(vec![1, 2, 2, 3], vec![1, 2, 3]);
369 case(vec![1, 2, 3, 3], vec![1, 2, 3]);
370 case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
374 fn test_dedup_by_key() {
375 fn case(a: Vec<i32>, b: Vec<i32>) {
377 v.dedup_by_key(|i| *i / 10);
380 case(vec![], vec![]);
381 case(vec![10], vec![10]);
382 case(vec![10, 11], vec![10]);
383 case(vec![10, 20, 30], vec![10, 20, 30]);
384 case(vec![10, 11, 20, 30], vec![10, 20, 30]);
385 case(vec![10, 20, 21, 30], vec![10, 20, 30]);
386 case(vec![10, 20, 30, 31], vec![10, 20, 30]);
387 case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
392 let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
393 vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
395 assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
397 let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
398 vec.dedup_by(|a, b| {
405 assert_eq!(vec, [("foo", 3), ("bar", 12)]);
409 fn test_dedup_unique() {
410 let mut v0: Vec<Box<_>> = vec![Box::new(1), Box::new(1), Box::new(2), Box::new(3)];
412 let mut v1: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(2), Box::new(3)];
414 let mut v2: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(3), Box::new(3)];
416 // If the boxed pointers were leaked or otherwise misused, valgrind
417 // and/or rt should raise errors.
421 fn zero_sized_values() {
422 let mut v = Vec::new();
423 assert_eq!(v.len(), 0);
425 assert_eq!(v.len(), 1);
427 assert_eq!(v.len(), 2);
428 assert_eq!(v.pop(), Some(()));
429 assert_eq!(v.pop(), Some(()));
430 assert_eq!(v.pop(), None);
432 assert_eq!(v.iter().count(), 0);
434 assert_eq!(v.iter().count(), 1);
436 assert_eq!(v.iter().count(), 2);
440 assert_eq!(v.iter_mut().count(), 2);
442 assert_eq!(v.iter_mut().count(), 3);
444 assert_eq!(v.iter_mut().count(), 4);
446 for &mut () in &mut v {}
450 assert_eq!(v.iter_mut().count(), 0);
454 fn test_partition() {
455 assert_eq!([].into_iter().partition(|x: &i32| *x < 3), (vec![], vec![]));
456 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 4), (vec![1, 2, 3], vec![]));
457 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 2), (vec![1], vec![2, 3]));
458 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 0), (vec![], vec![1, 2, 3]));
462 fn test_zip_unzip() {
463 let z1 = vec![(1, 4), (2, 5), (3, 6)];
465 let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
467 assert_eq!((1, 4), (left[0], right[0]));
468 assert_eq!((2, 5), (left[1], right[1]));
469 assert_eq!((3, 6), (left[2], right[2]));
474 let x: &[isize] = &[1, 2, 3, 4, 5];
475 let cmp: &[isize] = &[1, 2, 3, 4, 5];
476 assert_eq!(&x[..], cmp);
477 let cmp: &[isize] = &[3, 4, 5];
478 assert_eq!(&x[2..], cmp);
479 let cmp: &[isize] = &[1, 2, 3];
480 assert_eq!(&x[..3], cmp);
481 let cmp: &[isize] = &[2, 3, 4];
482 assert_eq!(&x[1..4], cmp);
484 let x: Vec<isize> = vec![1, 2, 3, 4, 5];
485 let cmp: &[isize] = &[1, 2, 3, 4, 5];
486 assert_eq!(&x[..], cmp);
487 let cmp: &[isize] = &[3, 4, 5];
488 assert_eq!(&x[2..], cmp);
489 let cmp: &[isize] = &[1, 2, 3];
490 assert_eq!(&x[..3], cmp);
491 let cmp: &[isize] = &[2, 3, 4];
492 assert_eq!(&x[1..4], cmp);
496 fn test_vec_truncate_drop() {
497 static mut DROPS: u32 = 0;
507 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
508 assert_eq!(unsafe { DROPS }, 0);
510 assert_eq!(unsafe { DROPS }, 2);
512 assert_eq!(unsafe { DROPS }, 5);
517 fn test_vec_truncate_fail() {
519 impl Drop for BadElem {
521 let BadElem(ref mut x) = *self;
523 panic!("BadElem panic: 0xbadbeef")
528 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
534 let vec = vec![1, 2, 3];
535 assert!(vec[1] == 2);
540 fn test_index_out_of_bounds() {
541 let vec = vec![1, 2, 3];
547 fn test_slice_out_of_bounds_1() {
548 let x = vec![1, 2, 3, 4, 5];
554 fn test_slice_out_of_bounds_2() {
555 let x = vec![1, 2, 3, 4, 5];
561 fn test_slice_out_of_bounds_3() {
562 let x = vec![1, 2, 3, 4, 5];
568 fn test_slice_out_of_bounds_4() {
569 let x = vec![1, 2, 3, 4, 5];
575 fn test_slice_out_of_bounds_5() {
576 let x = vec![1, 2, 3, 4, 5];
582 fn test_swap_remove_empty() {
583 let mut vec = Vec::<i32>::new();
588 fn test_move_items() {
589 let vec = vec![1, 2, 3];
590 let mut vec2 = vec![];
594 assert_eq!(vec2, [1, 2, 3]);
598 fn test_move_items_reverse() {
599 let vec = vec![1, 2, 3];
600 let mut vec2 = vec![];
601 for i in vec.into_iter().rev() {
604 assert_eq!(vec2, [3, 2, 1]);
608 fn test_move_items_zero_sized() {
609 let vec = vec![(), (), ()];
610 let mut vec2 = vec![];
614 assert_eq!(vec2, [(), (), ()]);
618 fn test_drain_empty_vec() {
619 let mut vec: Vec<i32> = vec![];
620 let mut vec2: Vec<i32> = vec![];
621 for i in vec.drain(..) {
624 assert!(vec.is_empty());
625 assert!(vec2.is_empty());
629 fn test_drain_items() {
630 let mut vec = vec![1, 2, 3];
631 let mut vec2 = vec![];
632 for i in vec.drain(..) {
636 assert_eq!(vec2, [1, 2, 3]);
640 fn test_drain_items_reverse() {
641 let mut vec = vec![1, 2, 3];
642 let mut vec2 = vec![];
643 for i in vec.drain(..).rev() {
647 assert_eq!(vec2, [3, 2, 1]);
651 fn test_drain_items_zero_sized() {
652 let mut vec = vec![(), (), ()];
653 let mut vec2 = vec![];
654 for i in vec.drain(..) {
658 assert_eq!(vec2, [(), (), ()]);
663 fn test_drain_out_of_bounds() {
664 let mut v = vec![1, 2, 3, 4, 5];
669 fn test_drain_range() {
670 let mut v = vec![1, 2, 3, 4, 5];
671 for _ in v.drain(4..) {}
672 assert_eq!(v, &[1, 2, 3, 4]);
674 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
675 for _ in v.drain(1..4) {}
676 assert_eq!(v, &[1.to_string(), 5.to_string()]);
678 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
679 for _ in v.drain(1..4).rev() {}
680 assert_eq!(v, &[1.to_string(), 5.to_string()]);
682 let mut v: Vec<_> = vec![(); 5];
683 for _ in v.drain(1..4).rev() {}
684 assert_eq!(v, &[(), ()]);
688 fn test_drain_inclusive_range() {
689 let mut v = vec!['a', 'b', 'c', 'd', 'e'];
690 for _ in v.drain(1..=3) {}
691 assert_eq!(v, &['a', 'e']);
693 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
694 for _ in v.drain(1..=5) {}
695 assert_eq!(v, &["0".to_string()]);
697 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
698 for _ in v.drain(0..=5) {}
699 assert_eq!(v, Vec::<String>::new());
701 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
702 for _ in v.drain(0..=3) {}
703 assert_eq!(v, &["4".to_string(), "5".to_string()]);
705 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
706 for _ in v.drain(..=0) {}
707 assert_eq!(v, &["1".to_string()]);
711 fn test_drain_max_vec_size() {
712 let mut v = Vec::<()>::with_capacity(usize::MAX);
714 v.set_len(usize::MAX);
716 for _ in v.drain(usize::MAX - 1..) {}
717 assert_eq!(v.len(), usize::MAX - 1);
719 let mut v = Vec::<()>::with_capacity(usize::MAX);
721 v.set_len(usize::MAX);
723 for _ in v.drain(usize::MAX - 1..=usize::MAX - 1) {}
724 assert_eq!(v.len(), usize::MAX - 1);
729 fn test_drain_index_overflow() {
730 let mut v = Vec::<()>::with_capacity(usize::MAX);
732 v.set_len(usize::MAX);
734 v.drain(0..=usize::MAX);
739 fn test_drain_inclusive_out_of_bounds() {
740 let mut v = vec![1, 2, 3, 4, 5];
746 fn test_drain_start_overflow() {
747 let mut v = vec![1, 2, 3];
748 v.drain((Excluded(usize::MAX), Included(0)));
753 fn test_drain_end_overflow() {
754 let mut v = vec![1, 2, 3];
755 v.drain((Included(0), Included(usize::MAX)));
759 fn test_drain_leak() {
760 static mut DROPS: i32 = 0;
762 #[derive(Debug, PartialEq)]
772 panic!("panic in `drop`");
787 catch_unwind(AssertUnwindSafe(|| {
792 assert_eq!(unsafe { DROPS }, 4);
793 assert_eq!(v, vec![D(0, false), D(1, false), D(6, false),]);
798 let mut v = vec![1, 2, 3, 4, 5];
799 let a = [10, 11, 12];
801 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
802 v.splice(1..3, Some(20));
803 assert_eq!(v, &[1, 20, 11, 12, 5]);
807 fn test_splice_inclusive_range() {
808 let mut v = vec![1, 2, 3, 4, 5];
809 let a = [10, 11, 12];
810 let t1: Vec<_> = v.splice(2..=3, a).collect();
811 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
812 assert_eq!(t1, &[3, 4]);
813 let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
814 assert_eq!(v, &[1, 20, 11, 12, 5]);
815 assert_eq!(t2, &[2, 10]);
820 fn test_splice_out_of_bounds() {
821 let mut v = vec![1, 2, 3, 4, 5];
822 let a = [10, 11, 12];
828 fn test_splice_inclusive_out_of_bounds() {
829 let mut v = vec![1, 2, 3, 4, 5];
830 let a = [10, 11, 12];
835 fn test_splice_items_zero_sized() {
836 let mut vec = vec![(), (), ()];
838 let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
839 assert_eq!(vec, &[(), ()]);
840 assert_eq!(t, &[()]);
844 fn test_splice_unbounded() {
845 let mut vec = vec![1, 2, 3, 4, 5];
846 let t: Vec<_> = vec.splice(.., None).collect();
847 assert_eq!(vec, &[]);
848 assert_eq!(t, &[1, 2, 3, 4, 5]);
852 fn test_splice_forget() {
853 let mut v = vec![1, 2, 3, 4, 5];
854 let a = [10, 11, 12];
855 std::mem::forget(v.splice(2..4, a));
856 assert_eq!(v, &[1, 2]);
860 fn test_into_boxed_slice() {
861 let xs = vec![1, 2, 3];
862 let ys = xs.into_boxed_slice();
863 assert_eq!(&*ys, [1, 2, 3]);
868 let mut vec = vec![1, 2, 3];
869 let mut vec2 = vec![4, 5, 6];
870 vec.append(&mut vec2);
871 assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
872 assert_eq!(vec2, []);
876 fn test_split_off() {
877 let mut vec = vec![1, 2, 3, 4, 5, 6];
878 let orig_capacity = vec.capacity();
879 let vec2 = vec.split_off(4);
880 assert_eq!(vec, [1, 2, 3, 4]);
881 assert_eq!(vec2, [5, 6]);
882 assert_eq!(vec.capacity(), orig_capacity);
886 fn test_split_off_take_all() {
887 let mut vec = vec![1, 2, 3, 4, 5, 6];
888 let orig_ptr = vec.as_ptr();
889 let orig_capacity = vec.capacity();
890 let vec2 = vec.split_off(0);
892 assert_eq!(vec2, [1, 2, 3, 4, 5, 6]);
893 assert_eq!(vec.capacity(), orig_capacity);
894 assert_eq!(vec2.as_ptr(), orig_ptr);
898 fn test_into_iter_as_slice() {
899 let vec = vec!['a', 'b', 'c'];
900 let mut into_iter = vec.into_iter();
901 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
902 let _ = into_iter.next().unwrap();
903 assert_eq!(into_iter.as_slice(), &['b', 'c']);
904 let _ = into_iter.next().unwrap();
905 let _ = into_iter.next().unwrap();
906 assert_eq!(into_iter.as_slice(), &[]);
910 fn test_into_iter_as_mut_slice() {
911 let vec = vec!['a', 'b', 'c'];
912 let mut into_iter = vec.into_iter();
913 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
914 into_iter.as_mut_slice()[0] = 'x';
915 into_iter.as_mut_slice()[1] = 'y';
916 assert_eq!(into_iter.next().unwrap(), 'x');
917 assert_eq!(into_iter.as_slice(), &['y', 'c']);
921 fn test_into_iter_debug() {
922 let vec = vec!['a', 'b', 'c'];
923 let into_iter = vec.into_iter();
924 let debug = format!("{into_iter:?}");
925 assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
929 fn test_into_iter_count() {
930 assert_eq!([1, 2, 3].into_iter().count(), 3);
934 fn test_into_iter_clone() {
935 fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
936 let v: Vec<i32> = it.collect();
937 assert_eq!(&v[..], slice);
939 let mut it = [1, 2, 3].into_iter();
940 iter_equal(it.clone(), &[1, 2, 3]);
941 assert_eq!(it.next(), Some(1));
942 let mut it = it.rev();
943 iter_equal(it.clone(), &[3, 2]);
944 assert_eq!(it.next(), Some(3));
945 iter_equal(it.clone(), &[2]);
946 assert_eq!(it.next(), Some(2));
947 iter_equal(it.clone(), &[]);
948 assert_eq!(it.next(), None);
952 fn test_into_iter_leak() {
953 static mut DROPS: i32 = 0;
964 panic!("panic in `drop`");
969 let v = vec![D(false), D(true), D(false)];
971 catch_unwind(move || drop(v.into_iter())).ok();
973 assert_eq!(unsafe { DROPS }, 3);
977 fn test_into_iter_advance_by() {
978 let mut i = [1, 2, 3, 4, 5].into_iter();
979 i.advance_by(0).unwrap();
980 i.advance_back_by(0).unwrap();
981 assert_eq!(i.as_slice(), [1, 2, 3, 4, 5]);
983 i.advance_by(1).unwrap();
984 i.advance_back_by(1).unwrap();
985 assert_eq!(i.as_slice(), [2, 3, 4]);
987 assert_eq!(i.advance_back_by(usize::MAX), Err(3));
989 assert_eq!(i.advance_by(usize::MAX), Err(0));
991 i.advance_by(0).unwrap();
992 i.advance_back_by(0).unwrap();
994 assert_eq!(i.len(), 0);
998 fn test_into_iter_drop_allocator() {
999 struct ReferenceCountedAllocator<'a>(DropCounter<'a>);
1001 unsafe impl Allocator for ReferenceCountedAllocator<'_> {
1002 fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, core::alloc::AllocError> {
1003 System.allocate(layout)
1006 unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
1007 System.deallocate(ptr, layout)
1011 let mut drop_count = 0;
1013 let allocator = ReferenceCountedAllocator(DropCounter { count: &mut drop_count });
1014 let _ = Vec::<u32, _>::new_in(allocator);
1015 assert_eq!(drop_count, 1);
1017 let allocator = ReferenceCountedAllocator(DropCounter { count: &mut drop_count });
1018 let _ = Vec::<u32, _>::new_in(allocator).into_iter();
1019 assert_eq!(drop_count, 2);
1023 fn test_from_iter_specialization() {
1024 let src: Vec<usize> = vec![0usize; 1];
1025 let srcptr = src.as_ptr();
1026 let sink = src.into_iter().collect::<Vec<_>>();
1027 let sinkptr = sink.as_ptr();
1028 assert_eq!(srcptr, sinkptr);
1032 fn test_from_iter_partially_drained_in_place_specialization() {
1033 let src: Vec<usize> = vec![0usize; 10];
1034 let srcptr = src.as_ptr();
1035 let mut iter = src.into_iter();
1038 let sink = iter.collect::<Vec<_>>();
1039 let sinkptr = sink.as_ptr();
1040 assert_eq!(srcptr, sinkptr);
1044 fn test_from_iter_specialization_with_iterator_adapters() {
1045 fn assert_in_place_trait<T: InPlaceIterable>(_: &T) {}
1046 let src: Vec<usize> = vec![0usize; 256];
1047 let srcptr = src.as_ptr();
1052 .zip(std::iter::repeat(1usize))
1053 .map(|(a, b)| a + b)
1054 .map_while(Option::Some)
1056 .map(|e| if e != usize::MAX { Ok(std::num::NonZeroUsize::new(e)) } else { Err(()) });
1057 assert_in_place_trait(&iter);
1058 let sink = iter.collect::<Result<Vec<_>, _>>().unwrap();
1059 let sinkptr = sink.as_ptr();
1060 assert_eq!(srcptr, sinkptr as *const usize);
1064 fn test_from_iter_specialization_head_tail_drop() {
1065 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1066 let src: Vec<_> = drop_count.iter().cloned().collect();
1067 let srcptr = src.as_ptr();
1068 let iter = src.into_iter();
1069 let sink: Vec<_> = iter.skip(1).take(1).collect();
1070 let sinkptr = sink.as_ptr();
1071 assert_eq!(srcptr, sinkptr, "specialization was applied");
1072 assert_eq!(Rc::strong_count(&drop_count[0]), 1, "front was dropped");
1073 assert_eq!(Rc::strong_count(&drop_count[1]), 2, "one element was collected");
1074 assert_eq!(Rc::strong_count(&drop_count[2]), 1, "tail was dropped");
1075 assert_eq!(sink.len(), 1);
1079 fn test_from_iter_specialization_panic_during_iteration_drops() {
1080 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1081 let src: Vec<_> = drop_count.iter().cloned().collect();
1082 let iter = src.into_iter();
1084 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1087 .filter_map(|(i, e)| {
1089 std::panic!("aborting iteration");
1093 .collect::<Vec<_>>();
1097 drop_count.iter().map(Rc::strong_count).all(|count| count == 1),
1098 "all items were dropped once"
1103 fn test_from_iter_specialization_panic_during_drop_leaks() {
1104 static mut DROP_COUNTER: usize = 0;
1108 DroppedTwice(Box<i32>),
1112 impl Drop for Droppable {
1113 fn drop(&mut self) {
1115 Droppable::DroppedTwice(_) => {
1119 println!("Dropping!")
1121 Droppable::PanicOnDrop => {
1122 if !std::thread::panicking() {
1130 let mut to_free: *mut Droppable = core::ptr::null_mut();
1133 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1134 let mut v = vec![Droppable::DroppedTwice(Box::new(123)), Droppable::PanicOnDrop];
1135 to_free = v.as_mut_ptr();
1137 let _ = v.into_iter().take(0).collect::<Vec<_>>();
1140 assert_eq!(unsafe { DROP_COUNTER }, 1);
1141 // clean up the leak to keep miri happy
1143 drop(Vec::from_raw_parts(to_free, 0, cap));
1147 // regression test for issue #85322. Peekable previously implemented InPlaceIterable,
1148 // but due to an interaction with IntoIter's current Clone implementation it failed to uphold
1151 fn test_collect_after_iterator_clone() {
1153 let mut i = v.into_iter().map(|i| i + 1).peekable();
1155 let v = i.clone().collect::<Vec<_>>();
1156 assert_eq!(v, [1, 1, 1, 1, 1]);
1157 assert!(v.len() <= v.capacity());
1160 fn test_cow_from() {
1161 let borrowed: &[_] = &["borrowed", "(slice)"];
1162 let owned = vec!["owned", "(vec)"];
1163 match (Cow::from(owned.clone()), Cow::from(borrowed)) {
1164 (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
1165 _ => panic!("invalid `Cow::from`"),
1170 fn test_from_cow() {
1171 let borrowed: &[_] = &["borrowed", "(slice)"];
1172 let owned = vec!["owned", "(vec)"];
1173 assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
1174 assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
1178 fn assert_covariance() {
1179 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1182 fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
1188 fn from_into_inner() {
1189 let vec = vec![1, 2, 3];
1190 let ptr = vec.as_ptr();
1191 let vec = vec.into_iter().collect::<Vec<_>>();
1192 assert_eq!(vec, [1, 2, 3]);
1193 assert_eq!(vec.as_ptr(), ptr);
1195 let ptr = &vec[1] as *const _;
1196 let mut it = vec.into_iter();
1198 let vec = it.collect::<Vec<_>>();
1199 assert_eq!(vec, [2, 3]);
1200 assert!(ptr != vec.as_ptr());
1204 fn overaligned_allocations() {
1207 let mut v = vec![Foo(273)];
1208 for i in 0..0x1000 {
1210 assert!(v[0].0 == 273);
1211 assert!(v.as_ptr() as usize & 0xff == 0);
1213 assert!(v[0].0 == 273);
1214 assert!(v.as_ptr() as usize & 0xff == 0);
1219 fn drain_filter_empty() {
1220 let mut vec: Vec<i32> = vec![];
1223 let mut iter = vec.drain_filter(|_| true);
1224 assert_eq!(iter.size_hint(), (0, Some(0)));
1225 assert_eq!(iter.next(), None);
1226 assert_eq!(iter.size_hint(), (0, Some(0)));
1227 assert_eq!(iter.next(), None);
1228 assert_eq!(iter.size_hint(), (0, Some(0)));
1230 assert_eq!(vec.len(), 0);
1231 assert_eq!(vec, vec![]);
1235 fn drain_filter_zst() {
1236 let mut vec = vec![(), (), (), (), ()];
1237 let initial_len = vec.len();
1240 let mut iter = vec.drain_filter(|_| true);
1241 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1242 while let Some(_) = iter.next() {
1244 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1246 assert_eq!(iter.size_hint(), (0, Some(0)));
1247 assert_eq!(iter.next(), None);
1248 assert_eq!(iter.size_hint(), (0, Some(0)));
1251 assert_eq!(count, initial_len);
1252 assert_eq!(vec.len(), 0);
1253 assert_eq!(vec, vec![]);
1257 fn drain_filter_false() {
1258 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1260 let initial_len = vec.len();
1263 let mut iter = vec.drain_filter(|_| false);
1264 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1265 for _ in iter.by_ref() {
1268 assert_eq!(iter.size_hint(), (0, Some(0)));
1269 assert_eq!(iter.next(), None);
1270 assert_eq!(iter.size_hint(), (0, Some(0)));
1273 assert_eq!(count, 0);
1274 assert_eq!(vec.len(), initial_len);
1275 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1279 fn drain_filter_true() {
1280 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1282 let initial_len = vec.len();
1285 let mut iter = vec.drain_filter(|_| true);
1286 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1287 while let Some(_) = iter.next() {
1289 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1291 assert_eq!(iter.size_hint(), (0, Some(0)));
1292 assert_eq!(iter.next(), None);
1293 assert_eq!(iter.size_hint(), (0, Some(0)));
1296 assert_eq!(count, initial_len);
1297 assert_eq!(vec.len(), 0);
1298 assert_eq!(vec, vec![]);
1302 fn drain_filter_complex() {
1304 // [+xxx++++++xxxxx++++x+x++]
1306 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
1310 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1311 assert_eq!(removed.len(), 10);
1312 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1314 assert_eq!(vec.len(), 14);
1315 assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1319 // [xxx++++++xxxxx++++x+x++]
1321 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
1324 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1325 assert_eq!(removed.len(), 10);
1326 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1328 assert_eq!(vec.len(), 13);
1329 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1333 // [xxx++++++xxxxx++++x+x]
1335 vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36];
1337 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1338 assert_eq!(removed.len(), 10);
1339 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1341 assert_eq!(vec.len(), 11);
1342 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
1346 // [xxxxxxxxxx+++++++++++]
1347 let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
1349 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1350 assert_eq!(removed.len(), 10);
1351 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1353 assert_eq!(vec.len(), 10);
1354 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1358 // [+++++++++++xxxxxxxxxx]
1359 let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
1361 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1362 assert_eq!(removed.len(), 10);
1363 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1365 assert_eq!(vec.len(), 10);
1366 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1370 // FIXME: re-enable emscripten once it can unwind again
1372 #[cfg(not(target_os = "emscripten"))]
1373 fn drain_filter_consumed_panic() {
1375 use std::sync::Mutex;
1379 drop_counts: Rc<Mutex<Vec<usize>>>,
1382 impl Drop for Check {
1383 fn drop(&mut self) {
1384 self.drop_counts.lock().unwrap()[self.index] += 1;
1385 println!("drop: {}", self.index);
1389 let check_count = 10;
1390 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1391 let mut data: Vec<Check> = (0..check_count)
1392 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1395 let _ = std::panic::catch_unwind(move || {
1396 let filter = |c: &mut Check| {
1398 panic!("panic at index: {}", c.index);
1400 // Verify that if the filter could panic again on another element
1401 // that it would not cause a double panic and all elements of the
1402 // vec would still be dropped exactly once.
1404 panic!("panic at index: {}", c.index);
1408 let drain = data.drain_filter(filter);
1410 // NOTE: The DrainFilter is explicitly consumed
1411 drain.for_each(drop);
1414 let drop_counts = drop_counts.lock().unwrap();
1415 assert_eq!(check_count, drop_counts.len());
1417 for (index, count) in drop_counts.iter().cloned().enumerate() {
1418 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1422 // FIXME: Re-enable emscripten once it can catch panics
1424 #[cfg(not(target_os = "emscripten"))]
1425 fn drain_filter_unconsumed_panic() {
1427 use std::sync::Mutex;
1431 drop_counts: Rc<Mutex<Vec<usize>>>,
1434 impl Drop for Check {
1435 fn drop(&mut self) {
1436 self.drop_counts.lock().unwrap()[self.index] += 1;
1437 println!("drop: {}", self.index);
1441 let check_count = 10;
1442 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1443 let mut data: Vec<Check> = (0..check_count)
1444 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1447 let _ = std::panic::catch_unwind(move || {
1448 let filter = |c: &mut Check| {
1450 panic!("panic at index: {}", c.index);
1452 // Verify that if the filter could panic again on another element
1453 // that it would not cause a double panic and all elements of the
1454 // vec would still be dropped exactly once.
1456 panic!("panic at index: {}", c.index);
1460 let _drain = data.drain_filter(filter);
1462 // NOTE: The DrainFilter is dropped without being consumed
1465 let drop_counts = drop_counts.lock().unwrap();
1466 assert_eq!(check_count, drop_counts.len());
1468 for (index, count) in drop_counts.iter().cloned().enumerate() {
1469 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1474 fn drain_filter_unconsumed() {
1475 let mut vec = vec![1, 2, 3, 4];
1476 let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1478 assert_eq!(vec, [2, 4]);
1482 fn test_reserve_exact() {
1483 // This is all the same as test_reserve
1485 let mut v = Vec::new();
1486 assert_eq!(v.capacity(), 0);
1489 assert!(v.capacity() >= 2);
1495 assert!(v.capacity() >= 16);
1496 v.reserve_exact(16);
1497 assert!(v.capacity() >= 32);
1501 v.reserve_exact(16);
1502 assert!(v.capacity() >= 33)
1506 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1507 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1508 fn test_try_reserve() {
1509 // These are the interesting cases:
1510 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1511 // * > isize::MAX should always fail
1512 // * On 16/32-bit should CapacityOverflow
1513 // * On 64-bit should OOM
1514 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1515 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1517 const MAX_CAP: usize = isize::MAX as usize;
1518 const MAX_USIZE: usize = usize::MAX;
1520 // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1521 // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1522 // Any platform that succeeds for these requests is technically broken with
1523 // ptr::offset because LLVM is the worst.
1524 let guards_against_isize = usize::BITS < 64;
1527 // Note: basic stuff is checked by test_reserve
1528 let mut empty_bytes: Vec<u8> = Vec::new();
1530 // Check isize::MAX doesn't count as an overflow
1531 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1532 panic!("isize::MAX shouldn't trigger an overflow!");
1534 // Play it again, frank! (just to be sure)
1535 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1536 panic!("isize::MAX shouldn't trigger an overflow!");
1539 if guards_against_isize {
1540 // Check isize::MAX + 1 does count as overflow
1542 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1543 Err(CapacityOverflow),
1544 "isize::MAX + 1 should trigger an overflow!"
1547 // Check usize::MAX does count as overflow
1549 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1550 Err(CapacityOverflow),
1551 "usize::MAX should trigger an overflow!"
1554 // Check isize::MAX + 1 is an OOM
1556 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1557 Err(AllocError { .. }),
1558 "isize::MAX + 1 should trigger an OOM!"
1561 // Check usize::MAX is an OOM
1563 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1564 Err(AllocError { .. }),
1565 "usize::MAX should trigger an OOM!"
1571 // Same basic idea, but with non-zero len
1572 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1574 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1575 panic!("isize::MAX shouldn't trigger an overflow!");
1577 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1578 panic!("isize::MAX shouldn't trigger an overflow!");
1580 if guards_against_isize {
1582 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1583 Err(CapacityOverflow),
1584 "isize::MAX + 1 should trigger an overflow!"
1588 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1589 Err(AllocError { .. }),
1590 "isize::MAX + 1 should trigger an OOM!"
1593 // Should always overflow in the add-to-len
1595 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1596 Err(CapacityOverflow),
1597 "usize::MAX should trigger an overflow!"
1602 // Same basic idea, but with interesting type size
1603 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1605 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1607 panic!("isize::MAX shouldn't trigger an overflow!");
1609 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1611 panic!("isize::MAX shouldn't trigger an overflow!");
1613 if guards_against_isize {
1615 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1616 Err(CapacityOverflow),
1617 "isize::MAX + 1 should trigger an overflow!"
1621 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1622 Err(AllocError { .. }),
1623 "isize::MAX + 1 should trigger an OOM!"
1626 // Should fail in the mul-by-size
1628 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1629 Err(CapacityOverflow),
1630 "usize::MAX should trigger an overflow!"
1636 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1637 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1638 fn test_try_reserve_exact() {
1639 // This is exactly the same as test_try_reserve with the method changed.
1640 // See that test for comments.
1642 const MAX_CAP: usize = isize::MAX as usize;
1643 const MAX_USIZE: usize = usize::MAX;
1645 let guards_against_isize = size_of::<usize>() < 8;
1648 let mut empty_bytes: Vec<u8> = Vec::new();
1650 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1652 panic!("isize::MAX shouldn't trigger an overflow!");
1654 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1656 panic!("isize::MAX shouldn't trigger an overflow!");
1659 if guards_against_isize {
1661 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1662 Err(CapacityOverflow),
1663 "isize::MAX + 1 should trigger an overflow!"
1667 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1668 Err(CapacityOverflow),
1669 "usize::MAX should trigger an overflow!"
1673 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1674 Err(AllocError { .. }),
1675 "isize::MAX + 1 should trigger an OOM!"
1679 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1680 Err(AllocError { .. }),
1681 "usize::MAX should trigger an OOM!"
1687 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1689 if let Err(CapacityOverflow) =
1690 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1692 panic!("isize::MAX shouldn't trigger an overflow!");
1694 if let Err(CapacityOverflow) =
1695 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1697 panic!("isize::MAX shouldn't trigger an overflow!");
1699 if guards_against_isize {
1701 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1702 Err(CapacityOverflow),
1703 "isize::MAX + 1 should trigger an overflow!"
1707 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1708 Err(AllocError { .. }),
1709 "isize::MAX + 1 should trigger an OOM!"
1713 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1714 Err(CapacityOverflow),
1715 "usize::MAX should trigger an overflow!"
1720 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1722 if let Err(CapacityOverflow) =
1723 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1725 panic!("isize::MAX shouldn't trigger an overflow!");
1727 if let Err(CapacityOverflow) =
1728 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1730 panic!("isize::MAX shouldn't trigger an overflow!");
1732 if guards_against_isize {
1734 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1735 Err(CapacityOverflow),
1736 "isize::MAX + 1 should trigger an overflow!"
1740 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1741 Err(AllocError { .. }),
1742 "isize::MAX + 1 should trigger an OOM!"
1746 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1747 Err(CapacityOverflow),
1748 "usize::MAX should trigger an overflow!"
1754 fn test_stable_pointers() {
1755 /// Pull an element from the iterator, then drop it.
1756 /// Useful to cover both the `next` and `drop` paths of an iterator.
1757 fn next_then_drop<I: Iterator>(mut i: I) {
1762 // Test that, if we reserved enough space, adding and removing elements does not
1763 // invalidate references into the vector (such as `v0`). This test also
1764 // runs in Miri, which would detect such problems.
1765 // Note that this test does *not* constitute a stable guarantee that all these functions do not
1766 // reallocate! Only what is explicitly documented at
1767 // <https://doc.rust-lang.org/nightly/std/vec/struct.Vec.html#guarantees> is stably guaranteed.
1768 let mut v = Vec::with_capacity(128);
1771 // Laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1773 let v0 = unsafe { &mut *(v0 as *mut _) };
1774 // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1776 // Pushing/inserting and popping/removing
1780 assert_eq!(*v0, 13);
1783 assert_eq!(*v0, 13);
1786 assert_eq!(v.len(), 2);
1787 v.swap_remove(1); // swap_remove the last element
1788 assert_eq!(*v0, 13);
1791 v.append(&mut vec![27, 19]);
1792 assert_eq!(*v0, 13);
1795 v.extend_from_slice(&[1, 2]);
1796 v.extend(&[1, 2]); // `slice::Iter` (with `T: Copy`) specialization
1797 v.extend(vec![2, 3]); // `vec::IntoIter` specialization
1798 v.extend(std::iter::once(3)); // `TrustedLen` specialization
1799 v.extend(std::iter::empty::<i32>()); // `TrustedLen` specialization with empty iterator
1800 v.extend(std::iter::once(3).filter(|_| true)); // base case
1801 v.extend(std::iter::once(&3)); // `cloned` specialization
1802 assert_eq!(*v0, 13);
1806 assert_eq!(*v0, 13);
1809 v.resize_with(v.len() + 10, || 42);
1810 assert_eq!(*v0, 13);
1811 v.resize_with(2, || panic!());
1812 assert_eq!(*v0, 13);
1814 // No-op reservation
1816 v.reserve_exact(32);
1817 assert_eq!(*v0, 13);
1820 v.resize_with(10, || 42);
1821 next_then_drop(v.drain(5..));
1822 assert_eq!(*v0, 13);
1825 v.resize_with(10, || 42);
1826 next_then_drop(v.splice(5.., vec![1, 2, 3, 4, 5])); // empty tail after range
1827 assert_eq!(*v0, 13);
1828 next_then_drop(v.splice(5..8, vec![1])); // replacement is smaller than original range
1829 assert_eq!(*v0, 13);
1830 next_then_drop(v.splice(5..6, [1; 10].into_iter().filter(|_| true))); // lower bound not exact
1831 assert_eq!(*v0, 13);
1833 // spare_capacity_mut
1834 v.spare_capacity_mut();
1835 assert_eq!(*v0, 13);
1837 // Smoke test that would fire even outside Miri if an actual relocation happened.
1839 assert_eq!(v[0], 0);
1842 // https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
1845 // unsafe impl<T: ?Sized> IsZero for *mut T {
1846 // fn is_zero(&self) -> bool {
1847 // (*self).is_null()
1852 // … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
1853 // which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
1854 // That is, a fat pointer can be “null” without being made entirely of zero bits.
1856 fn vec_macro_repeating_null_raw_fat_pointer() {
1857 let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
1858 let vtable = dbg!(ptr_metadata(raw_dyn));
1859 let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
1860 assert!(null_raw_dyn.is_null());
1862 let vec = vec![null_raw_dyn; 1];
1863 dbg!(ptr_metadata(vec[0]));
1864 assert!(vec[0] == null_raw_dyn);
1866 // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
1868 fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
1869 unsafe { std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable }
1872 fn ptr_from_raw_parts(data: *mut (), vtable: *mut ()) -> *mut dyn Fn() {
1873 unsafe { std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr { data, vtable }) }
1883 // This test will likely fail if you change the capacities used in
1884 // `RawVec::grow_amortized`.
1886 fn test_push_growth_strategy() {
1887 // If the element size is 1, we jump from 0 to 8, then double.
1889 let mut v1: Vec<u8> = vec![];
1890 assert_eq!(v1.capacity(), 0);
1894 assert_eq!(v1.capacity(), 8);
1899 assert_eq!(v1.capacity(), 16);
1904 assert_eq!(v1.capacity(), 32);
1909 assert_eq!(v1.capacity(), 64);
1913 // If the element size is 2..=1024, we jump from 0 to 4, then double.
1915 let mut v2: Vec<u16> = vec![];
1916 let mut v1024: Vec<[u8; 1024]> = vec![];
1917 assert_eq!(v2.capacity(), 0);
1918 assert_eq!(v1024.capacity(), 0);
1922 v1024.push([0; 1024]);
1923 assert_eq!(v2.capacity(), 4);
1924 assert_eq!(v1024.capacity(), 4);
1929 v1024.push([0; 1024]);
1930 assert_eq!(v2.capacity(), 8);
1931 assert_eq!(v1024.capacity(), 8);
1936 v1024.push([0; 1024]);
1937 assert_eq!(v2.capacity(), 16);
1938 assert_eq!(v1024.capacity(), 16);
1943 v1024.push([0; 1024]);
1944 assert_eq!(v2.capacity(), 32);
1945 assert_eq!(v1024.capacity(), 32);
1950 v1024.push([0; 1024]);
1951 assert_eq!(v2.capacity(), 64);
1952 assert_eq!(v1024.capacity(), 64);
1956 // If the element size is > 1024, we jump from 0 to 1, then double.
1958 let mut v1025: Vec<[u8; 1025]> = vec![];
1959 assert_eq!(v1025.capacity(), 0);
1962 v1025.push([0; 1025]);
1963 assert_eq!(v1025.capacity(), 1);
1967 v1025.push([0; 1025]);
1968 assert_eq!(v1025.capacity(), 2);
1972 v1025.push([0; 1025]);
1973 assert_eq!(v1025.capacity(), 4);
1977 v1025.push([0; 1025]);
1978 assert_eq!(v1025.capacity(), 8);
1982 v1025.push([0; 1025]);
1983 assert_eq!(v1025.capacity(), 16);
1987 v1025.push([0; 1025]);
1988 assert_eq!(v1025.capacity(), 32);
1992 v1025.push([0; 1025]);
1993 assert_eq!(v1025.capacity(), 64);
1998 macro_rules! generate_assert_eq_vec_and_prim {
1999 ($name:ident<$B:ident>($type:ty)) => {
2000 fn $name<A: PartialEq<$B> + Debug, $B: Debug>(a: Vec<A>, b: $type) {
2007 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_slice <B>(&[B]) }
2008 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_array_3<B>([B; 3]) }
2011 fn partialeq_vec_and_prim() {
2012 assert_eq_vec_and_slice(vec![1, 2, 3], &[1, 2, 3]);
2013 assert_eq_vec_and_array_3(vec![1, 2, 3], [1, 2, 3]);
2016 macro_rules! assert_partial_eq_valid {
2017 ($a2:expr, $a3:expr; $b2:expr, $b3: expr) => {
2018 assert!($a2 == $b2);
2019 assert!($a2 != $b3);
2020 assert!($a3 != $b2);
2021 assert!($a3 == $b3);
2022 assert_eq!($a2, $b2);
2023 assert_ne!($a2, $b3);
2024 assert_ne!($a3, $b2);
2025 assert_eq!($a3, $b3);
2030 fn partialeq_vec_full() {
2031 let vec2: Vec<_> = vec![1, 2];
2032 let vec3: Vec<_> = vec![1, 2, 3];
2033 let slice2: &[_] = &[1, 2];
2034 let slice3: &[_] = &[1, 2, 3];
2035 let slicemut2: &[_] = &mut [1, 2];
2036 let slicemut3: &[_] = &mut [1, 2, 3];
2037 let array2: [_; 2] = [1, 2];
2038 let array3: [_; 3] = [1, 2, 3];
2039 let arrayref2: &[_; 2] = &[1, 2];
2040 let arrayref3: &[_; 3] = &[1, 2, 3];
2042 assert_partial_eq_valid!(vec2,vec3; vec2,vec3);
2043 assert_partial_eq_valid!(vec2,vec3; slice2,slice3);
2044 assert_partial_eq_valid!(vec2,vec3; slicemut2,slicemut3);
2045 assert_partial_eq_valid!(slice2,slice3; vec2,vec3);
2046 assert_partial_eq_valid!(slicemut2,slicemut3; vec2,vec3);
2047 assert_partial_eq_valid!(vec2,vec3; array2,array3);
2048 assert_partial_eq_valid!(vec2,vec3; arrayref2,arrayref3);
2049 assert_partial_eq_valid!(vec2,vec3; arrayref2[..],arrayref3[..]);
2053 fn test_vec_cycle() {
2056 v: Vec<Cell<Option<&'a C<'a>>>>,
2065 let mut c1 = C::new();
2066 let mut c2 = C::new();
2067 let mut c3 = C::new();
2070 c1.v.push(Cell::new(None));
2071 c1.v.push(Cell::new(None));
2073 c2.v.push(Cell::new(None));
2074 c2.v.push(Cell::new(None));
2076 c3.v.push(Cell::new(None));
2077 c3.v.push(Cell::new(None));
2080 c1.v[0].set(Some(&c2));
2081 c1.v[1].set(Some(&c3));
2083 c2.v[0].set(Some(&c2));
2084 c2.v[1].set(Some(&c3));
2086 c3.v[0].set(Some(&c1));
2087 c3.v[1].set(Some(&c2));
2091 fn test_vec_cycle_wrapped() {
2093 v: Vec<Cell<Option<&'a C<'a>>>>,
2101 fn new() -> Refs<'a> {
2102 Refs { v: Vec::new() }
2108 C { refs: Refs::new() }
2112 let mut c1 = C::new();
2113 let mut c2 = C::new();
2114 let mut c3 = C::new();
2116 c1.refs.v.push(Cell::new(None));
2117 c1.refs.v.push(Cell::new(None));
2118 c2.refs.v.push(Cell::new(None));
2119 c2.refs.v.push(Cell::new(None));
2120 c3.refs.v.push(Cell::new(None));
2121 c3.refs.v.push(Cell::new(None));
2123 c1.refs.v[0].set(Some(&c2));
2124 c1.refs.v[1].set(Some(&c3));
2125 c2.refs.v[0].set(Some(&c2));
2126 c2.refs.v[1].set(Some(&c3));
2127 c3.refs.v[0].set(Some(&c1));
2128 c3.refs.v[1].set(Some(&c2));
2132 fn test_zero_sized_vec_push() {
2136 let mut tester = Vec::with_capacity(len);
2137 assert_eq!(tester.len(), 0);
2138 assert!(tester.capacity() >= len);
2142 assert_eq!(tester.len(), len);
2143 assert_eq!(tester.iter().count(), len);
2149 fn test_vec_macro_repeat() {
2150 assert_eq!(vec![1; 3], vec![1, 1, 1]);
2151 assert_eq!(vec![1; 2], vec![1, 1]);
2152 assert_eq!(vec![1; 1], vec![1]);
2153 assert_eq!(vec![1; 0], vec![]);
2155 // from_elem syntax (see RFC 832)
2156 let el = Box::new(1);
2158 assert_eq!(vec![el; n], vec![Box::new(1), Box::new(1), Box::new(1)]);
2162 fn test_vec_swap() {
2163 let mut a: Vec<isize> = vec![0, 1, 2, 3, 4, 5, 6];
2165 assert_eq!(a[2], 4);
2166 assert_eq!(a[4], 2);
2168 swap(&mut n, &mut a[0]);
2169 assert_eq!(a[0], 42);
2174 fn test_extend_from_within_spec() {
2178 impl Clone for CopyOnly {
2179 fn clone(&self) -> Self {
2180 panic!("extend_from_within must use specialization on copy");
2184 vec![CopyOnly, CopyOnly].extend_from_within(..);
2188 fn test_extend_from_within_clone() {
2189 let mut v = vec![String::from("sssss"), String::from("12334567890"), String::from("c")];
2190 v.extend_from_within(1..);
2192 assert_eq!(v, ["sssss", "12334567890", "c", "12334567890", "c"]);
2196 fn test_extend_from_within_complete_rande() {
2197 let mut v = vec![0, 1, 2, 3];
2198 v.extend_from_within(..);
2200 assert_eq!(v, [0, 1, 2, 3, 0, 1, 2, 3]);
2204 fn test_extend_from_within_empty_rande() {
2205 let mut v = vec![0, 1, 2, 3];
2206 v.extend_from_within(1..1);
2208 assert_eq!(v, [0, 1, 2, 3]);
2213 fn test_extend_from_within_out_of_rande() {
2214 let mut v = vec![0, 1];
2215 v.extend_from_within(..3);
2219 fn test_extend_from_within_zst() {
2220 let mut v = vec![(); 8];
2221 v.extend_from_within(3..7);
2223 assert_eq!(v, [(); 12]);
2227 fn test_extend_from_within_empty_vec() {
2228 let mut v = Vec::<i32>::new();
2229 v.extend_from_within(..);
2235 fn test_extend_from_within() {
2236 let mut v = vec![String::from("a"), String::from("b"), String::from("c")];
2237 v.extend_from_within(1..=2);
2238 v.extend_from_within(..=1);
2240 assert_eq!(v, ["a", "b", "c", "b", "c", "a", "b"]);
2244 fn test_vec_dedup_by() {
2245 let mut vec: Vec<i32> = vec![1, -1, 2, 3, 1, -5, 5, -2, 2];
2247 vec.dedup_by(|a, b| a.abs() == b.abs());
2249 assert_eq!(vec, [1, 2, 3, 1, -5, -2]);
2253 fn test_vec_dedup_empty() {
2254 let mut vec: Vec<i32> = Vec::new();
2258 assert_eq!(vec, []);
2262 fn test_vec_dedup_one() {
2263 let mut vec = vec![12i32];
2267 assert_eq!(vec, [12]);
2271 fn test_vec_dedup_multiple_ident() {
2272 let mut vec = vec![12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11];
2276 assert_eq!(vec, [12, 11]);
2280 fn test_vec_dedup_partialeq() {
2282 struct Foo(i32, i32);
2284 impl PartialEq for Foo {
2285 fn eq(&self, other: &Foo) -> bool {
2290 let mut vec = vec![Foo(0, 1), Foo(0, 5), Foo(1, 7), Foo(1, 9)];
2293 assert_eq!(vec, [Foo(0, 1), Foo(1, 7)]);
2297 fn test_vec_dedup() {
2298 let mut vec: Vec<bool> = Vec::with_capacity(8);
2299 let mut template = vec.clone();
2301 for x in 0u8..255u8 {
2305 let iter = (0..8).map(move |bit| (x >> bit) & 1 == 1);
2307 template.extend_from_slice(&vec);
2309 let (dedup, _) = template.partition_dedup();
2312 assert_eq!(vec, dedup);
2317 fn test_vec_dedup_panicking() {
2320 drop_counter: &'a Cell<u32>,
2325 impl<'a> PartialEq for Panic<'a> {
2326 fn eq(&self, other: &Self) -> bool {
2327 self.value == other.value
2331 impl<'a> Drop for Panic<'a> {
2332 fn drop(&mut self) {
2333 self.drop_counter.set(self.drop_counter.get() + 1);
2334 if !std::thread::panicking() {
2335 assert!(self.index != 4);
2340 let drop_counter = &Cell::new(0);
2342 Panic { drop_counter, value: false, index: 0 },
2343 Panic { drop_counter, value: false, index: 5 },
2344 Panic { drop_counter, value: true, index: 6 },
2345 Panic { drop_counter, value: true, index: 7 },
2348 Panic { drop_counter, value: false, index: 0 },
2349 // these elements get deduplicated
2350 Panic { drop_counter, value: false, index: 1 },
2351 Panic { drop_counter, value: false, index: 2 },
2352 Panic { drop_counter, value: false, index: 3 },
2353 Panic { drop_counter, value: false, index: 4 },
2354 // here it panics while dropping the item with index==4
2355 Panic { drop_counter, value: false, index: 5 },
2356 Panic { drop_counter, value: true, index: 6 },
2357 Panic { drop_counter, value: true, index: 7 },
2360 let _ = catch_unwind(AssertUnwindSafe(|| vec.dedup())).unwrap_err();
2362 assert_eq!(drop_counter.get(), 4);
2364 let ok = vec.iter().zip(expected.iter()).all(|(x, y)| x.index == y.index);
2367 panic!("expected: {expected:?}\ngot: {vec:?}\n");
2371 // Regression test for issue #82533
2373 fn test_extend_from_within_panicing_clone() {
2375 drop_count: &'dc AtomicU32,
2379 impl Clone for Panic<'_> {
2380 fn clone(&self) -> Self {
2382 panic!("panic! at the clone");
2389 impl Drop for Panic<'_> {
2390 fn drop(&mut self) {
2391 self.drop_count.fetch_add(1, Ordering::SeqCst);
2395 let count = core::sync::atomic::AtomicU32::new(0);
2397 Panic { drop_count: &count, aaaaa: false },
2398 Panic { drop_count: &count, aaaaa: true },
2399 Panic { drop_count: &count, aaaaa: false },
2402 // This should clone&append one Panic{..} at the end, and then panic while
2403 // cloning second Panic{..}. This means that `Panic::drop` should be called
2404 // 4 times (3 for items already in vector, 1 for just appended).
2406 // Previously just appended item was leaked, making drop_count = 3, instead of 4.
2407 std::panic::catch_unwind(move || vec.extend_from_within(..)).unwrap_err();
2409 assert_eq!(count.load(Ordering::SeqCst), 4);
2413 #[should_panic = "vec len overflow"]
2414 fn test_into_flattened_size_overflow() {
2415 let v = vec![[(); usize::MAX]; 2];
2416 let _ = v.into_flattened();