1 use core::alloc::{Allocator, Layout};
2 use core::iter::IntoIterator;
3 use core::ptr::NonNull;
4 use std::alloc::System;
5 use std::assert_matches::assert_matches;
8 use std::collections::TryReserveErrorKind::*;
10 use std::iter::InPlaceIterable;
11 use std::mem::{size_of, swap};
12 use std::ops::Bound::*;
13 use std::panic::{catch_unwind, AssertUnwindSafe};
15 use std::sync::atomic::{AtomicU32, Ordering};
16 use std::vec::{Drain, IntoIter};
18 struct DropCounter<'a> {
22 impl Drop for DropCounter<'_> {
29 fn test_small_vec_struct() {
30 assert_eq!(size_of::<Vec<u8>>(), size_of::<usize>() * 3);
34 fn test_double_drop() {
40 let (mut count_x, mut count_y) = (0, 0);
42 let mut tv = TwoVec { x: Vec::new(), y: Vec::new() };
43 tv.x.push(DropCounter { count: &mut count_x });
44 tv.y.push(DropCounter { count: &mut count_y });
46 // If Vec had a drop flag, here is where it would be zeroed.
47 // Instead, it should rely on its internal state to prevent
48 // doing anything significant when dropped multiple times.
51 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
54 assert_eq!(count_x, 1);
55 assert_eq!(count_y, 1);
60 let mut v = Vec::new();
61 assert_eq!(v.capacity(), 0);
64 assert!(v.capacity() >= 2);
70 assert!(v.capacity() >= 16);
72 assert!(v.capacity() >= 32);
77 assert!(v.capacity() >= 33)
81 fn test_zst_capacity() {
82 assert_eq!(Vec::<()>::new().capacity(), usize::MAX);
87 let v: Vec<isize> = vec![10, 20];
92 assert_eq!(v[x + 1], 20);
95 assert_eq!(v[x - 1], 10);
100 let vec1: Vec<isize> = vec![];
101 assert_eq!("[]", format!("{:?}", vec1));
103 let vec2 = vec![0, 1];
104 assert_eq!("[0, 1]", format!("{:?}", vec2));
106 let slice: &[isize] = &[4, 5];
107 assert_eq!("[4, 5]", format!("{slice:?}"));
116 assert_eq!(v, [1, 2]);
118 assert_eq!(v, [1, 2, 3]);
123 let mut v = Vec::new();
124 let mut w = Vec::new();
143 v.extend(w.clone()); // specializes to `append`
144 assert!(v.iter().eq(w.iter().chain(w.iter())));
147 #[derive(PartialEq, Debug)]
150 let mut a = Vec::new();
151 let b = vec![Foo, Foo];
154 assert_eq!(a, &[Foo, Foo]);
159 let mut x = Vec::new();
160 let y = vec![DropCounter { count: &mut count_x }];
163 assert_eq!(count_x, 1);
167 fn test_extend_from_slice() {
168 let a: Vec<isize> = vec![1, 2, 3, 4, 5];
169 let b: Vec<isize> = vec![6, 7, 8, 9, 0];
171 let mut v: Vec<isize> = a;
173 v.extend_from_slice(&b);
175 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
179 fn test_extend_ref() {
180 let mut v = vec![1, 2];
181 v.extend(&[3, 4, 5]);
183 assert_eq!(v.len(), 5);
184 assert_eq!(v, [1, 2, 3, 4, 5]);
189 assert_eq!(v.len(), 7);
190 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
194 fn test_slice_from_ref() {
195 let values = vec![1, 2, 3, 4, 5];
196 let slice = &values[1..3];
198 assert_eq!(slice, [2, 3]);
202 fn test_slice_from_mut() {
203 let mut values = vec![1, 2, 3, 4, 5];
205 let slice = &mut values[2..];
206 assert!(slice == [3, 4, 5]);
212 assert!(values == [1, 2, 5, 6, 7]);
216 fn test_slice_to_mut() {
217 let mut values = vec![1, 2, 3, 4, 5];
219 let slice = &mut values[..2];
220 assert!(slice == [1, 2]);
226 assert!(values == [2, 3, 3, 4, 5]);
230 fn test_split_at_mut() {
231 let mut values = vec![1, 2, 3, 4, 5];
233 let (left, right) = values.split_at_mut(2);
235 let left: &[_] = left;
236 assert!(&left[..left.len()] == &[1, 2]);
243 let right: &[_] = right;
244 assert!(&right[..right.len()] == &[3, 4, 5]);
251 assert_eq!(values, [2, 3, 5, 6, 7]);
256 let v: Vec<i32> = vec![];
257 let w = vec![1, 2, 3];
259 assert_eq!(v, v.clone());
263 // they should be disjoint in memory.
264 assert!(w.as_ptr() != z.as_ptr())
268 fn test_clone_from() {
270 let three: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(3)];
271 let two: Vec<Box<_>> = vec![Box::new(4), Box::new(5)];
273 v.clone_from(&three);
274 assert_eq!(v, three);
277 v.clone_from(&three);
278 assert_eq!(v, three);
285 v.clone_from(&three);
291 let mut vec = vec![1, 2, 3, 4];
292 vec.retain(|&x| x % 2 == 0);
293 assert_eq!(vec, [2, 4]);
297 fn test_retain_predicate_order() {
298 for to_keep in [true, false] {
299 let mut number_of_executions = 0;
300 let mut vec = vec![1, 2, 3, 4];
301 let mut next_expected = 1;
303 assert_eq!(next_expected, x);
305 number_of_executions += 1;
308 assert_eq!(number_of_executions, 4);
313 fn test_retain_pred_panic_with_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 {
325 // Everything is dropped when predicate panicked.
326 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
330 fn test_retain_pred_panic_no_hole() {
331 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
332 catch_unwind(AssertUnwindSafe(|| {
333 let mut v = v.clone();
334 v.retain(|r| match **r {
340 // Everything is dropped when predicate panicked.
341 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
345 fn test_retain_drop_panic() {
346 struct Wrap(Rc<i32>);
356 let v = (0..5).map(|x| Rc::new(x)).collect::<Vec<_>>();
357 catch_unwind(AssertUnwindSafe(|| {
358 let mut v = v.iter().map(|r| Wrap(r.clone())).collect::<Vec<_>>();
359 v.retain(|w| match *w.0 {
363 3 => false, // Drop panic.
368 // Other elements are dropped when `drop` of one element panicked.
369 // The panicked wrapper also has its Rc dropped.
370 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
374 fn test_retain_maybeuninits() {
375 // This test aimed to be run under miri.
376 use core::mem::MaybeUninit;
377 let mut vec: Vec<_> = [1i32, 2, 3, 4].map(|v| MaybeUninit::new(vec![v])).into();
379 // SAFETY: Retain must visit every element of Vec in original order and exactly once.
380 // Our values is initialized at creation of Vec.
381 let v = unsafe { x.assume_init_ref()[0] };
385 // SAFETY: Value is initialized.
386 // Value wouldn't be dropped by `Vec::retain`
387 // because `MaybeUninit` doesn't drop content.
388 drop(unsafe { x.assume_init_read() });
391 let vec: Vec<i32> = vec
394 // SAFETY: All values dropped in retain predicate must be removed by `Vec::retain`.
395 // Remaining values are initialized.
399 assert_eq!(vec, [2, 4]);
404 fn case(a: Vec<i32>, b: Vec<i32>) {
409 case(vec![], vec![]);
410 case(vec![1], vec![1]);
411 case(vec![1, 1], vec![1]);
412 case(vec![1, 2, 3], vec![1, 2, 3]);
413 case(vec![1, 1, 2, 3], vec![1, 2, 3]);
414 case(vec![1, 2, 2, 3], vec![1, 2, 3]);
415 case(vec![1, 2, 3, 3], vec![1, 2, 3]);
416 case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
420 fn test_dedup_by_key() {
421 fn case(a: Vec<i32>, b: Vec<i32>) {
423 v.dedup_by_key(|i| *i / 10);
426 case(vec![], vec![]);
427 case(vec![10], vec![10]);
428 case(vec![10, 11], vec![10]);
429 case(vec![10, 20, 30], vec![10, 20, 30]);
430 case(vec![10, 11, 20, 30], vec![10, 20, 30]);
431 case(vec![10, 20, 21, 30], vec![10, 20, 30]);
432 case(vec![10, 20, 30, 31], vec![10, 20, 30]);
433 case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
438 let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
439 vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
441 assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
443 let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
444 vec.dedup_by(|a, b| {
451 assert_eq!(vec, [("foo", 3), ("bar", 12)]);
455 fn test_dedup_unique() {
456 let mut v0: Vec<Box<_>> = vec![Box::new(1), Box::new(1), Box::new(2), Box::new(3)];
458 let mut v1: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(2), Box::new(3)];
460 let mut v2: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(3), Box::new(3)];
462 // If the boxed pointers were leaked or otherwise misused, valgrind
463 // and/or rt should raise errors.
467 fn zero_sized_values() {
468 let mut v = Vec::new();
469 assert_eq!(v.len(), 0);
471 assert_eq!(v.len(), 1);
473 assert_eq!(v.len(), 2);
474 assert_eq!(v.pop(), Some(()));
475 assert_eq!(v.pop(), Some(()));
476 assert_eq!(v.pop(), None);
478 assert_eq!(v.iter().count(), 0);
480 assert_eq!(v.iter().count(), 1);
482 assert_eq!(v.iter().count(), 2);
486 assert_eq!(v.iter_mut().count(), 2);
488 assert_eq!(v.iter_mut().count(), 3);
490 assert_eq!(v.iter_mut().count(), 4);
492 for &mut () in &mut v {}
496 assert_eq!(v.iter_mut().count(), 0);
500 fn test_partition() {
501 assert_eq!([].into_iter().partition(|x: &i32| *x < 3), (vec![], vec![]));
502 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 4), (vec![1, 2, 3], vec![]));
503 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 2), (vec![1], vec![2, 3]));
504 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 0), (vec![], vec![1, 2, 3]));
508 fn test_zip_unzip() {
509 let z1 = vec![(1, 4), (2, 5), (3, 6)];
511 let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
513 assert_eq!((1, 4), (left[0], right[0]));
514 assert_eq!((2, 5), (left[1], right[1]));
515 assert_eq!((3, 6), (left[2], right[2]));
520 let x: &[isize] = &[1, 2, 3, 4, 5];
521 let cmp: &[isize] = &[1, 2, 3, 4, 5];
522 assert_eq!(&x[..], cmp);
523 let cmp: &[isize] = &[3, 4, 5];
524 assert_eq!(&x[2..], cmp);
525 let cmp: &[isize] = &[1, 2, 3];
526 assert_eq!(&x[..3], cmp);
527 let cmp: &[isize] = &[2, 3, 4];
528 assert_eq!(&x[1..4], cmp);
530 let x: Vec<isize> = vec![1, 2, 3, 4, 5];
531 let cmp: &[isize] = &[1, 2, 3, 4, 5];
532 assert_eq!(&x[..], cmp);
533 let cmp: &[isize] = &[3, 4, 5];
534 assert_eq!(&x[2..], cmp);
535 let cmp: &[isize] = &[1, 2, 3];
536 assert_eq!(&x[..3], cmp);
537 let cmp: &[isize] = &[2, 3, 4];
538 assert_eq!(&x[1..4], cmp);
542 fn test_vec_truncate_drop() {
543 static mut DROPS: u32 = 0;
553 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
554 assert_eq!(unsafe { DROPS }, 0);
556 assert_eq!(unsafe { DROPS }, 2);
558 assert_eq!(unsafe { DROPS }, 5);
563 fn test_vec_truncate_fail() {
565 impl Drop for BadElem {
567 let BadElem(ref mut x) = *self;
569 panic!("BadElem panic: 0xbadbeef")
574 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
580 let vec = vec![1, 2, 3];
581 assert!(vec[1] == 2);
586 fn test_index_out_of_bounds() {
587 let vec = vec![1, 2, 3];
593 fn test_slice_out_of_bounds_1() {
594 let x = vec![1, 2, 3, 4, 5];
600 fn test_slice_out_of_bounds_2() {
601 let x = vec![1, 2, 3, 4, 5];
607 fn test_slice_out_of_bounds_3() {
608 let x = vec![1, 2, 3, 4, 5];
614 fn test_slice_out_of_bounds_4() {
615 let x = vec![1, 2, 3, 4, 5];
621 fn test_slice_out_of_bounds_5() {
622 let x = vec![1, 2, 3, 4, 5];
628 fn test_swap_remove_empty() {
629 let mut vec = Vec::<i32>::new();
634 fn test_move_items() {
635 let vec = vec![1, 2, 3];
636 let mut vec2 = vec![];
640 assert_eq!(vec2, [1, 2, 3]);
644 fn test_move_items_reverse() {
645 let vec = vec![1, 2, 3];
646 let mut vec2 = vec![];
647 for i in vec.into_iter().rev() {
650 assert_eq!(vec2, [3, 2, 1]);
654 fn test_move_items_zero_sized() {
655 let vec = vec![(), (), ()];
656 let mut vec2 = vec![];
660 assert_eq!(vec2, [(), (), ()]);
664 fn test_drain_empty_vec() {
665 let mut vec: Vec<i32> = vec![];
666 let mut vec2: Vec<i32> = vec![];
667 for i in vec.drain(..) {
670 assert!(vec.is_empty());
671 assert!(vec2.is_empty());
675 fn test_drain_items() {
676 let mut vec = vec![1, 2, 3];
677 let mut vec2 = vec![];
678 for i in vec.drain(..) {
682 assert_eq!(vec2, [1, 2, 3]);
686 fn test_drain_items_reverse() {
687 let mut vec = vec![1, 2, 3];
688 let mut vec2 = vec![];
689 for i in vec.drain(..).rev() {
693 assert_eq!(vec2, [3, 2, 1]);
697 fn test_drain_items_zero_sized() {
698 let mut vec = vec![(), (), ()];
699 let mut vec2 = vec![];
700 for i in vec.drain(..) {
704 assert_eq!(vec2, [(), (), ()]);
709 fn test_drain_out_of_bounds() {
710 let mut v = vec![1, 2, 3, 4, 5];
715 fn test_drain_range() {
716 let mut v = vec![1, 2, 3, 4, 5];
717 for _ in v.drain(4..) {}
718 assert_eq!(v, &[1, 2, 3, 4]);
720 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
721 for _ in v.drain(1..4) {}
722 assert_eq!(v, &[1.to_string(), 5.to_string()]);
724 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
725 for _ in v.drain(1..4).rev() {}
726 assert_eq!(v, &[1.to_string(), 5.to_string()]);
728 let mut v: Vec<_> = vec![(); 5];
729 for _ in v.drain(1..4).rev() {}
730 assert_eq!(v, &[(), ()]);
734 fn test_drain_inclusive_range() {
735 let mut v = vec!['a', 'b', 'c', 'd', 'e'];
736 for _ in v.drain(1..=3) {}
737 assert_eq!(v, &['a', 'e']);
739 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
740 for _ in v.drain(1..=5) {}
741 assert_eq!(v, &["0".to_string()]);
743 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
744 for _ in v.drain(0..=5) {}
745 assert_eq!(v, Vec::<String>::new());
747 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
748 for _ in v.drain(0..=3) {}
749 assert_eq!(v, &["4".to_string(), "5".to_string()]);
751 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
752 for _ in v.drain(..=0) {}
753 assert_eq!(v, &["1".to_string()]);
757 fn test_drain_max_vec_size() {
758 let mut v = Vec::<()>::with_capacity(usize::MAX);
760 v.set_len(usize::MAX);
762 for _ in v.drain(usize::MAX - 1..) {}
763 assert_eq!(v.len(), usize::MAX - 1);
765 let mut v = Vec::<()>::with_capacity(usize::MAX);
767 v.set_len(usize::MAX);
769 for _ in v.drain(usize::MAX - 1..=usize::MAX - 1) {}
770 assert_eq!(v.len(), usize::MAX - 1);
775 fn test_drain_index_overflow() {
776 let mut v = Vec::<()>::with_capacity(usize::MAX);
778 v.set_len(usize::MAX);
780 v.drain(0..=usize::MAX);
785 fn test_drain_inclusive_out_of_bounds() {
786 let mut v = vec![1, 2, 3, 4, 5];
792 fn test_drain_start_overflow() {
793 let mut v = vec![1, 2, 3];
794 v.drain((Excluded(usize::MAX), Included(0)));
799 fn test_drain_end_overflow() {
800 let mut v = vec![1, 2, 3];
801 v.drain((Included(0), Included(usize::MAX)));
805 fn test_drain_leak() {
806 static mut DROPS: i32 = 0;
808 #[derive(Debug, PartialEq)]
818 panic!("panic in `drop`");
833 catch_unwind(AssertUnwindSafe(|| {
838 assert_eq!(unsafe { DROPS }, 4);
839 assert_eq!(v, vec![D(0, false), D(1, false), D(6, false),]);
843 fn test_drain_keep_rest() {
844 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
845 let mut drain = v.drain(1..6);
846 assert_eq!(drain.next(), Some(1));
847 assert_eq!(drain.next_back(), Some(5));
848 assert_eq!(drain.next(), Some(2));
851 assert_eq!(v, &[0, 3, 4, 6]);
855 fn test_drain_keep_rest_all() {
856 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
857 v.drain(1..6).keep_rest();
858 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6]);
862 fn test_drain_keep_rest_none() {
863 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
864 let mut drain = v.drain(1..6);
866 drain.by_ref().for_each(drop);
869 assert_eq!(v, &[0, 6]);
874 let mut v = vec![1, 2, 3, 4, 5];
875 let a = [10, 11, 12];
877 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
878 v.splice(1..3, Some(20));
879 assert_eq!(v, &[1, 20, 11, 12, 5]);
883 fn test_splice_inclusive_range() {
884 let mut v = vec![1, 2, 3, 4, 5];
885 let a = [10, 11, 12];
886 let t1: Vec<_> = v.splice(2..=3, a).collect();
887 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
888 assert_eq!(t1, &[3, 4]);
889 let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
890 assert_eq!(v, &[1, 20, 11, 12, 5]);
891 assert_eq!(t2, &[2, 10]);
896 fn test_splice_out_of_bounds() {
897 let mut v = vec![1, 2, 3, 4, 5];
898 let a = [10, 11, 12];
904 fn test_splice_inclusive_out_of_bounds() {
905 let mut v = vec![1, 2, 3, 4, 5];
906 let a = [10, 11, 12];
911 fn test_splice_items_zero_sized() {
912 let mut vec = vec![(), (), ()];
914 let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
915 assert_eq!(vec, &[(), ()]);
916 assert_eq!(t, &[()]);
920 fn test_splice_unbounded() {
921 let mut vec = vec![1, 2, 3, 4, 5];
922 let t: Vec<_> = vec.splice(.., None).collect();
923 assert_eq!(vec, &[]);
924 assert_eq!(t, &[1, 2, 3, 4, 5]);
928 fn test_splice_forget() {
929 let mut v = vec![1, 2, 3, 4, 5];
930 let a = [10, 11, 12];
931 std::mem::forget(v.splice(2..4, a));
932 assert_eq!(v, &[1, 2]);
936 fn test_into_boxed_slice() {
937 let xs = vec![1, 2, 3];
938 let ys = xs.into_boxed_slice();
939 assert_eq!(&*ys, [1, 2, 3]);
944 let mut vec = vec![1, 2, 3];
945 let mut vec2 = vec![4, 5, 6];
946 vec.append(&mut vec2);
947 assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
948 assert_eq!(vec2, []);
952 fn test_split_off() {
953 let mut vec = vec![1, 2, 3, 4, 5, 6];
954 let orig_capacity = vec.capacity();
955 let vec2 = vec.split_off(4);
956 assert_eq!(vec, [1, 2, 3, 4]);
957 assert_eq!(vec2, [5, 6]);
958 assert_eq!(vec.capacity(), orig_capacity);
962 fn test_split_off_take_all() {
963 let mut vec = vec![1, 2, 3, 4, 5, 6];
964 let orig_ptr = vec.as_ptr();
965 let orig_capacity = vec.capacity();
966 let vec2 = vec.split_off(0);
968 assert_eq!(vec2, [1, 2, 3, 4, 5, 6]);
969 assert_eq!(vec.capacity(), orig_capacity);
970 assert_eq!(vec2.as_ptr(), orig_ptr);
974 fn test_into_iter_as_slice() {
975 let vec = vec!['a', 'b', 'c'];
976 let mut into_iter = vec.into_iter();
977 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
978 let _ = into_iter.next().unwrap();
979 assert_eq!(into_iter.as_slice(), &['b', 'c']);
980 let _ = into_iter.next().unwrap();
981 let _ = into_iter.next().unwrap();
982 assert_eq!(into_iter.as_slice(), &[]);
986 fn test_into_iter_as_mut_slice() {
987 let vec = vec!['a', 'b', 'c'];
988 let mut into_iter = vec.into_iter();
989 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
990 into_iter.as_mut_slice()[0] = 'x';
991 into_iter.as_mut_slice()[1] = 'y';
992 assert_eq!(into_iter.next().unwrap(), 'x');
993 assert_eq!(into_iter.as_slice(), &['y', 'c']);
997 fn test_into_iter_debug() {
998 let vec = vec!['a', 'b', 'c'];
999 let into_iter = vec.into_iter();
1000 let debug = format!("{into_iter:?}");
1001 assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
1005 fn test_into_iter_count() {
1006 assert_eq!([1, 2, 3].into_iter().count(), 3);
1010 fn test_into_iter_next_chunk() {
1011 let mut iter = b"lorem".to_vec().into_iter();
1013 assert_eq!(iter.next_chunk().unwrap(), [b'l', b'o']); // N is inferred as 2
1014 assert_eq!(iter.next_chunk().unwrap(), [b'r', b'e', b'm']); // N is inferred as 3
1015 assert_eq!(iter.next_chunk::<4>().unwrap_err().as_slice(), &[]); // N is explicitly 4
1019 fn test_into_iter_clone() {
1020 fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
1021 let v: Vec<i32> = it.collect();
1022 assert_eq!(&v[..], slice);
1024 let mut it = [1, 2, 3].into_iter();
1025 iter_equal(it.clone(), &[1, 2, 3]);
1026 assert_eq!(it.next(), Some(1));
1027 let mut it = it.rev();
1028 iter_equal(it.clone(), &[3, 2]);
1029 assert_eq!(it.next(), Some(3));
1030 iter_equal(it.clone(), &[2]);
1031 assert_eq!(it.next(), Some(2));
1032 iter_equal(it.clone(), &[]);
1033 assert_eq!(it.next(), None);
1037 fn test_into_iter_leak() {
1038 static mut DROPS: i32 = 0;
1043 fn drop(&mut self) {
1049 panic!("panic in `drop`");
1054 let v = vec![D(false), D(true), D(false)];
1056 catch_unwind(move || drop(v.into_iter())).ok();
1058 assert_eq!(unsafe { DROPS }, 3);
1062 fn test_into_iter_advance_by() {
1063 let mut i = [1, 2, 3, 4, 5].into_iter();
1064 i.advance_by(0).unwrap();
1065 i.advance_back_by(0).unwrap();
1066 assert_eq!(i.as_slice(), [1, 2, 3, 4, 5]);
1068 i.advance_by(1).unwrap();
1069 i.advance_back_by(1).unwrap();
1070 assert_eq!(i.as_slice(), [2, 3, 4]);
1072 assert_eq!(i.advance_back_by(usize::MAX), Err(3));
1074 assert_eq!(i.advance_by(usize::MAX), Err(0));
1076 i.advance_by(0).unwrap();
1077 i.advance_back_by(0).unwrap();
1079 assert_eq!(i.len(), 0);
1083 fn test_into_iter_drop_allocator() {
1084 struct ReferenceCountedAllocator<'a>(DropCounter<'a>);
1086 unsafe impl Allocator for ReferenceCountedAllocator<'_> {
1087 fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, core::alloc::AllocError> {
1088 System.allocate(layout)
1091 unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
1092 System.deallocate(ptr, layout)
1096 let mut drop_count = 0;
1098 let allocator = ReferenceCountedAllocator(DropCounter { count: &mut drop_count });
1099 let _ = Vec::<u32, _>::new_in(allocator);
1100 assert_eq!(drop_count, 1);
1102 let allocator = ReferenceCountedAllocator(DropCounter { count: &mut drop_count });
1103 let _ = Vec::<u32, _>::new_in(allocator).into_iter();
1104 assert_eq!(drop_count, 2);
1108 fn test_into_iter_zst() {
1109 for _ in vec![[0u64; 0]].into_iter() {}
1110 for _ in vec![[0u64; 0]; 5].into_iter().rev() {}
1114 fn test_from_iter_specialization() {
1115 let src: Vec<usize> = vec![0usize; 1];
1116 let srcptr = src.as_ptr();
1117 let sink = src.into_iter().collect::<Vec<_>>();
1118 let sinkptr = sink.as_ptr();
1119 assert_eq!(srcptr, sinkptr);
1123 fn test_from_iter_partially_drained_in_place_specialization() {
1124 let src: Vec<usize> = vec![0usize; 10];
1125 let srcptr = src.as_ptr();
1126 let mut iter = src.into_iter();
1129 let sink = iter.collect::<Vec<_>>();
1130 let sinkptr = sink.as_ptr();
1131 assert_eq!(srcptr, sinkptr);
1135 fn test_from_iter_specialization_with_iterator_adapters() {
1136 fn assert_in_place_trait<T: InPlaceIterable>(_: &T) {}
1137 let src: Vec<usize> = vec![0usize; 256];
1138 let srcptr = src.as_ptr();
1143 .zip(std::iter::repeat(1usize))
1144 .map(|(a, b)| a + b)
1145 .map_while(Option::Some)
1147 .map(|e| if e != usize::MAX { Ok(std::num::NonZeroUsize::new(e)) } else { Err(()) });
1148 assert_in_place_trait(&iter);
1149 let sink = iter.collect::<Result<Vec<_>, _>>().unwrap();
1150 let sinkptr = sink.as_ptr();
1151 assert_eq!(srcptr, sinkptr as *const usize);
1155 fn test_from_iter_specialization_head_tail_drop() {
1156 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1157 let src: Vec<_> = drop_count.iter().cloned().collect();
1158 let srcptr = src.as_ptr();
1159 let iter = src.into_iter();
1160 let sink: Vec<_> = iter.skip(1).take(1).collect();
1161 let sinkptr = sink.as_ptr();
1162 assert_eq!(srcptr, sinkptr, "specialization was applied");
1163 assert_eq!(Rc::strong_count(&drop_count[0]), 1, "front was dropped");
1164 assert_eq!(Rc::strong_count(&drop_count[1]), 2, "one element was collected");
1165 assert_eq!(Rc::strong_count(&drop_count[2]), 1, "tail was dropped");
1166 assert_eq!(sink.len(), 1);
1170 fn test_from_iter_specialization_panic_during_iteration_drops() {
1171 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1172 let src: Vec<_> = drop_count.iter().cloned().collect();
1173 let iter = src.into_iter();
1175 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1178 .filter_map(|(i, e)| {
1180 std::panic!("aborting iteration");
1184 .collect::<Vec<_>>();
1188 drop_count.iter().map(Rc::strong_count).all(|count| count == 1),
1189 "all items were dropped once"
1194 fn test_from_iter_specialization_panic_during_drop_leaks() {
1195 static mut DROP_COUNTER: usize = 0;
1199 DroppedTwice(Box<i32>),
1203 impl Drop for Droppable {
1204 fn drop(&mut self) {
1206 Droppable::DroppedTwice(_) => {
1210 println!("Dropping!")
1212 Droppable::PanicOnDrop => {
1213 if !std::thread::panicking() {
1221 let mut to_free: *mut Droppable = core::ptr::null_mut();
1224 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1225 let mut v = vec![Droppable::DroppedTwice(Box::new(123)), Droppable::PanicOnDrop];
1226 to_free = v.as_mut_ptr();
1228 let _ = v.into_iter().take(0).collect::<Vec<_>>();
1231 assert_eq!(unsafe { DROP_COUNTER }, 1);
1232 // clean up the leak to keep miri happy
1234 drop(Vec::from_raw_parts(to_free, 0, cap));
1238 // regression test for issue #85322. Peekable previously implemented InPlaceIterable,
1239 // but due to an interaction with IntoIter's current Clone implementation it failed to uphold
1242 fn test_collect_after_iterator_clone() {
1244 let mut i = v.into_iter().map(|i| i + 1).peekable();
1246 let v = i.clone().collect::<Vec<_>>();
1247 assert_eq!(v, [1, 1, 1, 1, 1]);
1248 assert!(v.len() <= v.capacity());
1251 fn test_cow_from() {
1252 let borrowed: &[_] = &["borrowed", "(slice)"];
1253 let owned = vec!["owned", "(vec)"];
1254 match (Cow::from(owned.clone()), Cow::from(borrowed)) {
1255 (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
1256 _ => panic!("invalid `Cow::from`"),
1261 fn test_from_cow() {
1262 let borrowed: &[_] = &["borrowed", "(slice)"];
1263 let owned = vec!["owned", "(vec)"];
1264 assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
1265 assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
1269 fn assert_covariance() {
1270 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1273 fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
1279 fn from_into_inner() {
1280 let vec = vec![1, 2, 3];
1281 let ptr = vec.as_ptr();
1282 let vec = vec.into_iter().collect::<Vec<_>>();
1283 assert_eq!(vec, [1, 2, 3]);
1284 assert_eq!(vec.as_ptr(), ptr);
1286 let ptr = &vec[1] as *const _;
1287 let mut it = vec.into_iter();
1289 let vec = it.collect::<Vec<_>>();
1290 assert_eq!(vec, [2, 3]);
1291 assert!(ptr != vec.as_ptr());
1295 fn overaligned_allocations() {
1298 let mut v = vec![Foo(273)];
1299 for i in 0..0x1000 {
1301 assert!(v[0].0 == 273);
1302 assert!(v.as_ptr() as usize & 0xff == 0);
1304 assert!(v[0].0 == 273);
1305 assert!(v.as_ptr() as usize & 0xff == 0);
1310 fn drain_filter_empty() {
1311 let mut vec: Vec<i32> = vec![];
1314 let mut iter = vec.drain_filter(|_| true);
1315 assert_eq!(iter.size_hint(), (0, Some(0)));
1316 assert_eq!(iter.next(), None);
1317 assert_eq!(iter.size_hint(), (0, Some(0)));
1318 assert_eq!(iter.next(), None);
1319 assert_eq!(iter.size_hint(), (0, Some(0)));
1321 assert_eq!(vec.len(), 0);
1322 assert_eq!(vec, vec![]);
1326 fn drain_filter_zst() {
1327 let mut vec = vec![(), (), (), (), ()];
1328 let initial_len = vec.len();
1331 let mut iter = vec.drain_filter(|_| true);
1332 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1333 while let Some(_) = iter.next() {
1335 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1337 assert_eq!(iter.size_hint(), (0, Some(0)));
1338 assert_eq!(iter.next(), None);
1339 assert_eq!(iter.size_hint(), (0, Some(0)));
1342 assert_eq!(count, initial_len);
1343 assert_eq!(vec.len(), 0);
1344 assert_eq!(vec, vec![]);
1348 fn drain_filter_false() {
1349 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1351 let initial_len = vec.len();
1354 let mut iter = vec.drain_filter(|_| false);
1355 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1356 for _ in iter.by_ref() {
1359 assert_eq!(iter.size_hint(), (0, Some(0)));
1360 assert_eq!(iter.next(), None);
1361 assert_eq!(iter.size_hint(), (0, Some(0)));
1364 assert_eq!(count, 0);
1365 assert_eq!(vec.len(), initial_len);
1366 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1370 fn drain_filter_true() {
1371 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1373 let initial_len = vec.len();
1376 let mut iter = vec.drain_filter(|_| true);
1377 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1378 while let Some(_) = iter.next() {
1380 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1382 assert_eq!(iter.size_hint(), (0, Some(0)));
1383 assert_eq!(iter.next(), None);
1384 assert_eq!(iter.size_hint(), (0, Some(0)));
1387 assert_eq!(count, initial_len);
1388 assert_eq!(vec.len(), 0);
1389 assert_eq!(vec, vec![]);
1393 fn drain_filter_complex() {
1395 // [+xxx++++++xxxxx++++x+x++]
1397 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
1401 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1402 assert_eq!(removed.len(), 10);
1403 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1405 assert_eq!(vec.len(), 14);
1406 assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1410 // [xxx++++++xxxxx++++x+x++]
1412 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
1415 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1416 assert_eq!(removed.len(), 10);
1417 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1419 assert_eq!(vec.len(), 13);
1420 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1424 // [xxx++++++xxxxx++++x+x]
1426 vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36];
1428 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1429 assert_eq!(removed.len(), 10);
1430 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1432 assert_eq!(vec.len(), 11);
1433 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
1437 // [xxxxxxxxxx+++++++++++]
1438 let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
1440 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1441 assert_eq!(removed.len(), 10);
1442 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1444 assert_eq!(vec.len(), 10);
1445 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1449 // [+++++++++++xxxxxxxxxx]
1450 let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
1452 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1453 assert_eq!(removed.len(), 10);
1454 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1456 assert_eq!(vec.len(), 10);
1457 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1461 // FIXME: re-enable emscripten once it can unwind again
1463 #[cfg(not(target_os = "emscripten"))]
1464 fn drain_filter_consumed_panic() {
1466 use std::sync::Mutex;
1470 drop_counts: Rc<Mutex<Vec<usize>>>,
1473 impl Drop for Check {
1474 fn drop(&mut self) {
1475 self.drop_counts.lock().unwrap()[self.index] += 1;
1476 println!("drop: {}", self.index);
1480 let check_count = 10;
1481 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1482 let mut data: Vec<Check> = (0..check_count)
1483 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1486 let _ = std::panic::catch_unwind(move || {
1487 let filter = |c: &mut Check| {
1489 panic!("panic at index: {}", c.index);
1491 // Verify that if the filter could panic again on another element
1492 // that it would not cause a double panic and all elements of the
1493 // vec would still be dropped exactly once.
1495 panic!("panic at index: {}", c.index);
1499 let drain = data.drain_filter(filter);
1501 // NOTE: The DrainFilter is explicitly consumed
1502 drain.for_each(drop);
1505 let drop_counts = drop_counts.lock().unwrap();
1506 assert_eq!(check_count, drop_counts.len());
1508 for (index, count) in drop_counts.iter().cloned().enumerate() {
1509 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1513 // FIXME: Re-enable emscripten once it can catch panics
1515 #[cfg(not(target_os = "emscripten"))]
1516 fn drain_filter_unconsumed_panic() {
1518 use std::sync::Mutex;
1522 drop_counts: Rc<Mutex<Vec<usize>>>,
1525 impl Drop for Check {
1526 fn drop(&mut self) {
1527 self.drop_counts.lock().unwrap()[self.index] += 1;
1528 println!("drop: {}", self.index);
1532 let check_count = 10;
1533 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1534 let mut data: Vec<Check> = (0..check_count)
1535 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1538 let _ = std::panic::catch_unwind(move || {
1539 let filter = |c: &mut Check| {
1541 panic!("panic at index: {}", c.index);
1543 // Verify that if the filter could panic again on another element
1544 // that it would not cause a double panic and all elements of the
1545 // vec would still be dropped exactly once.
1547 panic!("panic at index: {}", c.index);
1551 let _drain = data.drain_filter(filter);
1553 // NOTE: The DrainFilter is dropped without being consumed
1556 let drop_counts = drop_counts.lock().unwrap();
1557 assert_eq!(check_count, drop_counts.len());
1559 for (index, count) in drop_counts.iter().cloned().enumerate() {
1560 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1565 fn drain_filter_unconsumed() {
1566 let mut vec = vec![1, 2, 3, 4];
1567 let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1569 assert_eq!(vec, [2, 4]);
1573 fn test_drain_filter_keep_rest() {
1574 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
1575 let mut drain = v.drain_filter(|&mut x| x % 2 == 0);
1576 assert_eq!(drain.next(), Some(0));
1577 assert_eq!(drain.next(), Some(2));
1580 assert_eq!(v, &[1, 3, 4, 5, 6]);
1584 fn test_drain_filter_keep_rest_all() {
1585 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
1586 v.drain_filter(|_| true).keep_rest();
1587 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6]);
1591 fn test_drain_filter_keep_rest_none() {
1592 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
1593 let mut drain = v.drain_filter(|_| true);
1595 drain.by_ref().for_each(drop);
1602 fn test_reserve_exact() {
1603 // This is all the same as test_reserve
1605 let mut v = Vec::new();
1606 assert_eq!(v.capacity(), 0);
1609 assert!(v.capacity() >= 2);
1615 assert!(v.capacity() >= 16);
1616 v.reserve_exact(16);
1617 assert!(v.capacity() >= 32);
1621 v.reserve_exact(16);
1622 assert!(v.capacity() >= 33)
1626 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1627 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1628 fn test_try_reserve() {
1629 // These are the interesting cases:
1630 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1631 // * > isize::MAX should always fail
1632 // * On 16/32-bit should CapacityOverflow
1633 // * On 64-bit should OOM
1634 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1635 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1637 const MAX_CAP: usize = isize::MAX as usize;
1638 const MAX_USIZE: usize = usize::MAX;
1641 // Note: basic stuff is checked by test_reserve
1642 let mut empty_bytes: Vec<u8> = Vec::new();
1644 // Check isize::MAX doesn't count as an overflow
1645 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1646 panic!("isize::MAX shouldn't trigger an overflow!");
1648 // Play it again, frank! (just to be sure)
1649 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1650 panic!("isize::MAX shouldn't trigger an overflow!");
1653 // Check isize::MAX + 1 does count as overflow
1655 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1656 Err(CapacityOverflow),
1657 "isize::MAX + 1 should trigger an overflow!"
1660 // Check usize::MAX does count as overflow
1662 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1663 Err(CapacityOverflow),
1664 "usize::MAX should trigger an overflow!"
1669 // Same basic idea, but with non-zero len
1670 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1672 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1673 panic!("isize::MAX shouldn't trigger an overflow!");
1675 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1676 panic!("isize::MAX shouldn't trigger an overflow!");
1680 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1681 Err(CapacityOverflow),
1682 "isize::MAX + 1 should trigger an overflow!"
1685 // Should always overflow in the add-to-len
1687 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1688 Err(CapacityOverflow),
1689 "usize::MAX should trigger an overflow!"
1694 // Same basic idea, but with interesting type size
1695 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1697 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1699 panic!("isize::MAX shouldn't trigger an overflow!");
1701 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1703 panic!("isize::MAX shouldn't trigger an overflow!");
1707 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1708 Err(CapacityOverflow),
1709 "isize::MAX + 1 should trigger an overflow!"
1712 // Should fail in the mul-by-size
1714 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1715 Err(CapacityOverflow),
1716 "usize::MAX should trigger an overflow!"
1722 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1723 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1724 fn test_try_reserve_exact() {
1725 // This is exactly the same as test_try_reserve with the method changed.
1726 // See that test for comments.
1728 const MAX_CAP: usize = isize::MAX as usize;
1729 const MAX_USIZE: usize = usize::MAX;
1732 let mut empty_bytes: Vec<u8> = Vec::new();
1734 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1736 panic!("isize::MAX shouldn't trigger an overflow!");
1738 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1740 panic!("isize::MAX shouldn't trigger an overflow!");
1744 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1745 Err(CapacityOverflow),
1746 "isize::MAX + 1 should trigger an overflow!"
1750 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1751 Err(CapacityOverflow),
1752 "usize::MAX should trigger an overflow!"
1757 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1759 if let Err(CapacityOverflow) =
1760 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1762 panic!("isize::MAX shouldn't trigger an overflow!");
1764 if let Err(CapacityOverflow) =
1765 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1767 panic!("isize::MAX shouldn't trigger an overflow!");
1771 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1772 Err(CapacityOverflow),
1773 "isize::MAX + 1 should trigger an overflow!"
1777 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1778 Err(CapacityOverflow),
1779 "usize::MAX should trigger an overflow!"
1784 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1786 if let Err(CapacityOverflow) =
1787 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1789 panic!("isize::MAX shouldn't trigger an overflow!");
1791 if let Err(CapacityOverflow) =
1792 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1794 panic!("isize::MAX shouldn't trigger an overflow!");
1798 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1799 Err(CapacityOverflow),
1800 "isize::MAX + 1 should trigger an overflow!"
1804 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1805 Err(CapacityOverflow),
1806 "usize::MAX should trigger an overflow!"
1812 fn test_stable_pointers() {
1813 /// Pull an element from the iterator, then drop it.
1814 /// Useful to cover both the `next` and `drop` paths of an iterator.
1815 fn next_then_drop<I: Iterator>(mut i: I) {
1820 // Test that, if we reserved enough space, adding and removing elements does not
1821 // invalidate references into the vector (such as `v0`). This test also
1822 // runs in Miri, which would detect such problems.
1823 // Note that this test does *not* constitute a stable guarantee that all these functions do not
1824 // reallocate! Only what is explicitly documented at
1825 // <https://doc.rust-lang.org/nightly/std/vec/struct.Vec.html#guarantees> is stably guaranteed.
1826 let mut v = Vec::with_capacity(128);
1829 // Laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1831 let v0 = unsafe { &mut *(v0 as *mut _) };
1832 // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1834 // Pushing/inserting and popping/removing
1838 assert_eq!(*v0, 13);
1841 assert_eq!(*v0, 13);
1844 assert_eq!(v.len(), 2);
1845 v.swap_remove(1); // swap_remove the last element
1846 assert_eq!(*v0, 13);
1849 v.append(&mut vec![27, 19]);
1850 assert_eq!(*v0, 13);
1853 v.extend_from_slice(&[1, 2]);
1854 v.extend(&[1, 2]); // `slice::Iter` (with `T: Copy`) specialization
1855 v.extend(vec![2, 3]); // `vec::IntoIter` specialization
1856 v.extend(std::iter::once(3)); // `TrustedLen` specialization
1857 v.extend(std::iter::empty::<i32>()); // `TrustedLen` specialization with empty iterator
1858 v.extend(std::iter::once(3).filter(|_| true)); // base case
1859 v.extend(std::iter::once(&3)); // `cloned` specialization
1860 assert_eq!(*v0, 13);
1864 assert_eq!(*v0, 13);
1867 v.resize_with(v.len() + 10, || 42);
1868 assert_eq!(*v0, 13);
1869 v.resize_with(2, || panic!());
1870 assert_eq!(*v0, 13);
1872 // No-op reservation
1874 v.reserve_exact(32);
1875 assert_eq!(*v0, 13);
1878 v.resize_with(10, || 42);
1879 next_then_drop(v.drain(5..));
1880 assert_eq!(*v0, 13);
1883 v.resize_with(10, || 42);
1884 next_then_drop(v.splice(5.., vec![1, 2, 3, 4, 5])); // empty tail after range
1885 assert_eq!(*v0, 13);
1886 next_then_drop(v.splice(5..8, vec![1])); // replacement is smaller than original range
1887 assert_eq!(*v0, 13);
1888 next_then_drop(v.splice(5..6, [1; 10].into_iter().filter(|_| true))); // lower bound not exact
1889 assert_eq!(*v0, 13);
1891 // spare_capacity_mut
1892 v.spare_capacity_mut();
1893 assert_eq!(*v0, 13);
1895 // Smoke test that would fire even outside Miri if an actual relocation happened.
1897 assert_eq!(v[0], 0);
1900 // https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
1903 // unsafe impl<T: ?Sized> IsZero for *mut T {
1904 // fn is_zero(&self) -> bool {
1905 // (*self).is_null()
1910 // … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
1911 // which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
1912 // That is, a fat pointer can be “null” without being made entirely of zero bits.
1914 fn vec_macro_repeating_null_raw_fat_pointer() {
1915 let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
1916 let vtable = dbg!(ptr_metadata(raw_dyn));
1917 let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
1918 assert!(null_raw_dyn.is_null());
1920 let vec = vec![null_raw_dyn; 1];
1921 dbg!(ptr_metadata(vec[0]));
1922 assert!(vec[0] == null_raw_dyn);
1924 // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
1926 fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
1927 unsafe { std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable }
1930 fn ptr_from_raw_parts(data: *mut (), vtable: *mut ()) -> *mut dyn Fn() {
1931 unsafe { std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr { data, vtable }) }
1941 // This test will likely fail if you change the capacities used in
1942 // `RawVec::grow_amortized`.
1944 fn test_push_growth_strategy() {
1945 // If the element size is 1, we jump from 0 to 8, then double.
1947 let mut v1: Vec<u8> = vec![];
1948 assert_eq!(v1.capacity(), 0);
1952 assert_eq!(v1.capacity(), 8);
1957 assert_eq!(v1.capacity(), 16);
1962 assert_eq!(v1.capacity(), 32);
1967 assert_eq!(v1.capacity(), 64);
1971 // If the element size is 2..=1024, we jump from 0 to 4, then double.
1973 let mut v2: Vec<u16> = vec![];
1974 let mut v1024: Vec<[u8; 1024]> = vec![];
1975 assert_eq!(v2.capacity(), 0);
1976 assert_eq!(v1024.capacity(), 0);
1980 v1024.push([0; 1024]);
1981 assert_eq!(v2.capacity(), 4);
1982 assert_eq!(v1024.capacity(), 4);
1987 v1024.push([0; 1024]);
1988 assert_eq!(v2.capacity(), 8);
1989 assert_eq!(v1024.capacity(), 8);
1994 v1024.push([0; 1024]);
1995 assert_eq!(v2.capacity(), 16);
1996 assert_eq!(v1024.capacity(), 16);
2001 v1024.push([0; 1024]);
2002 assert_eq!(v2.capacity(), 32);
2003 assert_eq!(v1024.capacity(), 32);
2008 v1024.push([0; 1024]);
2009 assert_eq!(v2.capacity(), 64);
2010 assert_eq!(v1024.capacity(), 64);
2014 // If the element size is > 1024, we jump from 0 to 1, then double.
2016 let mut v1025: Vec<[u8; 1025]> = vec![];
2017 assert_eq!(v1025.capacity(), 0);
2020 v1025.push([0; 1025]);
2021 assert_eq!(v1025.capacity(), 1);
2025 v1025.push([0; 1025]);
2026 assert_eq!(v1025.capacity(), 2);
2030 v1025.push([0; 1025]);
2031 assert_eq!(v1025.capacity(), 4);
2035 v1025.push([0; 1025]);
2036 assert_eq!(v1025.capacity(), 8);
2040 v1025.push([0; 1025]);
2041 assert_eq!(v1025.capacity(), 16);
2045 v1025.push([0; 1025]);
2046 assert_eq!(v1025.capacity(), 32);
2050 v1025.push([0; 1025]);
2051 assert_eq!(v1025.capacity(), 64);
2056 macro_rules! generate_assert_eq_vec_and_prim {
2057 ($name:ident<$B:ident>($type:ty)) => {
2058 fn $name<A: PartialEq<$B> + Debug, $B: Debug>(a: Vec<A>, b: $type) {
2065 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_slice <B>(&[B]) }
2066 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_array_3<B>([B; 3]) }
2069 fn partialeq_vec_and_prim() {
2070 assert_eq_vec_and_slice(vec![1, 2, 3], &[1, 2, 3]);
2071 assert_eq_vec_and_array_3(vec![1, 2, 3], [1, 2, 3]);
2074 macro_rules! assert_partial_eq_valid {
2075 ($a2:expr, $a3:expr; $b2:expr, $b3: expr) => {
2076 assert!($a2 == $b2);
2077 assert!($a2 != $b3);
2078 assert!($a3 != $b2);
2079 assert!($a3 == $b3);
2080 assert_eq!($a2, $b2);
2081 assert_ne!($a2, $b3);
2082 assert_ne!($a3, $b2);
2083 assert_eq!($a3, $b3);
2088 fn partialeq_vec_full() {
2089 let vec2: Vec<_> = vec![1, 2];
2090 let vec3: Vec<_> = vec![1, 2, 3];
2091 let slice2: &[_] = &[1, 2];
2092 let slice3: &[_] = &[1, 2, 3];
2093 let slicemut2: &[_] = &mut [1, 2];
2094 let slicemut3: &[_] = &mut [1, 2, 3];
2095 let array2: [_; 2] = [1, 2];
2096 let array3: [_; 3] = [1, 2, 3];
2097 let arrayref2: &[_; 2] = &[1, 2];
2098 let arrayref3: &[_; 3] = &[1, 2, 3];
2100 assert_partial_eq_valid!(vec2,vec3; vec2,vec3);
2101 assert_partial_eq_valid!(vec2,vec3; slice2,slice3);
2102 assert_partial_eq_valid!(vec2,vec3; slicemut2,slicemut3);
2103 assert_partial_eq_valid!(slice2,slice3; vec2,vec3);
2104 assert_partial_eq_valid!(slicemut2,slicemut3; vec2,vec3);
2105 assert_partial_eq_valid!(vec2,vec3; array2,array3);
2106 assert_partial_eq_valid!(vec2,vec3; arrayref2,arrayref3);
2107 assert_partial_eq_valid!(vec2,vec3; arrayref2[..],arrayref3[..]);
2111 fn test_vec_cycle() {
2114 v: Vec<Cell<Option<&'a C<'a>>>>,
2123 let mut c1 = C::new();
2124 let mut c2 = C::new();
2125 let mut c3 = C::new();
2128 c1.v.push(Cell::new(None));
2129 c1.v.push(Cell::new(None));
2131 c2.v.push(Cell::new(None));
2132 c2.v.push(Cell::new(None));
2134 c3.v.push(Cell::new(None));
2135 c3.v.push(Cell::new(None));
2138 c1.v[0].set(Some(&c2));
2139 c1.v[1].set(Some(&c3));
2141 c2.v[0].set(Some(&c2));
2142 c2.v[1].set(Some(&c3));
2144 c3.v[0].set(Some(&c1));
2145 c3.v[1].set(Some(&c2));
2149 fn test_vec_cycle_wrapped() {
2151 v: Vec<Cell<Option<&'a C<'a>>>>,
2159 fn new() -> Refs<'a> {
2160 Refs { v: Vec::new() }
2166 C { refs: Refs::new() }
2170 let mut c1 = C::new();
2171 let mut c2 = C::new();
2172 let mut c3 = C::new();
2174 c1.refs.v.push(Cell::new(None));
2175 c1.refs.v.push(Cell::new(None));
2176 c2.refs.v.push(Cell::new(None));
2177 c2.refs.v.push(Cell::new(None));
2178 c3.refs.v.push(Cell::new(None));
2179 c3.refs.v.push(Cell::new(None));
2181 c1.refs.v[0].set(Some(&c2));
2182 c1.refs.v[1].set(Some(&c3));
2183 c2.refs.v[0].set(Some(&c2));
2184 c2.refs.v[1].set(Some(&c3));
2185 c3.refs.v[0].set(Some(&c1));
2186 c3.refs.v[1].set(Some(&c2));
2190 fn test_zero_sized_capacity() {
2191 for len in [0, 1, 2, 4, 8, 16, 32, 64, 128, 256] {
2192 let v = Vec::<()>::with_capacity(len);
2193 assert_eq!(v.len(), 0);
2194 assert_eq!(v.capacity(), usize::MAX);
2199 fn test_zero_sized_vec_push() {
2203 let mut tester = Vec::with_capacity(len);
2204 assert_eq!(tester.len(), 0);
2205 assert!(tester.capacity() >= len);
2209 assert_eq!(tester.len(), len);
2210 assert_eq!(tester.iter().count(), len);
2216 fn test_vec_macro_repeat() {
2217 assert_eq!(vec![1; 3], vec![1, 1, 1]);
2218 assert_eq!(vec![1; 2], vec![1, 1]);
2219 assert_eq!(vec![1; 1], vec![1]);
2220 assert_eq!(vec![1; 0], vec![]);
2222 // from_elem syntax (see RFC 832)
2223 let el = Box::new(1);
2225 assert_eq!(vec![el; n], vec![Box::new(1), Box::new(1), Box::new(1)]);
2229 fn test_vec_swap() {
2230 let mut a: Vec<isize> = vec![0, 1, 2, 3, 4, 5, 6];
2232 assert_eq!(a[2], 4);
2233 assert_eq!(a[4], 2);
2235 swap(&mut n, &mut a[0]);
2236 assert_eq!(a[0], 42);
2241 fn test_extend_from_within_spec() {
2245 impl Clone for CopyOnly {
2246 fn clone(&self) -> Self {
2247 panic!("extend_from_within must use specialization on copy");
2251 vec![CopyOnly, CopyOnly].extend_from_within(..);
2255 fn test_extend_from_within_clone() {
2256 let mut v = vec![String::from("sssss"), String::from("12334567890"), String::from("c")];
2257 v.extend_from_within(1..);
2259 assert_eq!(v, ["sssss", "12334567890", "c", "12334567890", "c"]);
2263 fn test_extend_from_within_complete_rande() {
2264 let mut v = vec![0, 1, 2, 3];
2265 v.extend_from_within(..);
2267 assert_eq!(v, [0, 1, 2, 3, 0, 1, 2, 3]);
2271 fn test_extend_from_within_empty_rande() {
2272 let mut v = vec![0, 1, 2, 3];
2273 v.extend_from_within(1..1);
2275 assert_eq!(v, [0, 1, 2, 3]);
2280 fn test_extend_from_within_out_of_rande() {
2281 let mut v = vec![0, 1];
2282 v.extend_from_within(..3);
2286 fn test_extend_from_within_zst() {
2287 let mut v = vec![(); 8];
2288 v.extend_from_within(3..7);
2290 assert_eq!(v, [(); 12]);
2294 fn test_extend_from_within_empty_vec() {
2295 let mut v = Vec::<i32>::new();
2296 v.extend_from_within(..);
2302 fn test_extend_from_within() {
2303 let mut v = vec![String::from("a"), String::from("b"), String::from("c")];
2304 v.extend_from_within(1..=2);
2305 v.extend_from_within(..=1);
2307 assert_eq!(v, ["a", "b", "c", "b", "c", "a", "b"]);
2311 fn test_vec_dedup_by() {
2312 let mut vec: Vec<i32> = vec![1, -1, 2, 3, 1, -5, 5, -2, 2];
2314 vec.dedup_by(|a, b| a.abs() == b.abs());
2316 assert_eq!(vec, [1, 2, 3, 1, -5, -2]);
2320 fn test_vec_dedup_empty() {
2321 let mut vec: Vec<i32> = Vec::new();
2325 assert_eq!(vec, []);
2329 fn test_vec_dedup_one() {
2330 let mut vec = vec![12i32];
2334 assert_eq!(vec, [12]);
2338 fn test_vec_dedup_multiple_ident() {
2339 let mut vec = vec![12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11];
2343 assert_eq!(vec, [12, 11]);
2347 fn test_vec_dedup_partialeq() {
2349 struct Foo(i32, i32);
2351 impl PartialEq for Foo {
2352 fn eq(&self, other: &Foo) -> bool {
2357 let mut vec = vec![Foo(0, 1), Foo(0, 5), Foo(1, 7), Foo(1, 9)];
2360 assert_eq!(vec, [Foo(0, 1), Foo(1, 7)]);
2364 fn test_vec_dedup() {
2365 let mut vec: Vec<bool> = Vec::with_capacity(8);
2366 let mut template = vec.clone();
2368 for x in 0u8..255u8 {
2372 let iter = (0..8).map(move |bit| (x >> bit) & 1 == 1);
2374 template.extend_from_slice(&vec);
2376 let (dedup, _) = template.partition_dedup();
2379 assert_eq!(vec, dedup);
2384 fn test_vec_dedup_panicking() {
2387 drop_counter: &'a Cell<u32>,
2392 impl<'a> PartialEq for Panic<'a> {
2393 fn eq(&self, other: &Self) -> bool {
2394 self.value == other.value
2398 impl<'a> Drop for Panic<'a> {
2399 fn drop(&mut self) {
2400 self.drop_counter.set(self.drop_counter.get() + 1);
2401 if !std::thread::panicking() {
2402 assert!(self.index != 4);
2407 let drop_counter = &Cell::new(0);
2409 Panic { drop_counter, value: false, index: 0 },
2410 Panic { drop_counter, value: false, index: 5 },
2411 Panic { drop_counter, value: true, index: 6 },
2412 Panic { drop_counter, value: true, index: 7 },
2415 Panic { drop_counter, value: false, index: 0 },
2416 // these elements get deduplicated
2417 Panic { drop_counter, value: false, index: 1 },
2418 Panic { drop_counter, value: false, index: 2 },
2419 Panic { drop_counter, value: false, index: 3 },
2420 Panic { drop_counter, value: false, index: 4 },
2421 // here it panics while dropping the item with index==4
2422 Panic { drop_counter, value: false, index: 5 },
2423 Panic { drop_counter, value: true, index: 6 },
2424 Panic { drop_counter, value: true, index: 7 },
2427 let _ = catch_unwind(AssertUnwindSafe(|| vec.dedup())).unwrap_err();
2429 assert_eq!(drop_counter.get(), 4);
2431 let ok = vec.iter().zip(expected.iter()).all(|(x, y)| x.index == y.index);
2434 panic!("expected: {expected:?}\ngot: {vec:?}\n");
2438 // Regression test for issue #82533
2440 fn test_extend_from_within_panicing_clone() {
2442 drop_count: &'dc AtomicU32,
2446 impl Clone for Panic<'_> {
2447 fn clone(&self) -> Self {
2449 panic!("panic! at the clone");
2456 impl Drop for Panic<'_> {
2457 fn drop(&mut self) {
2458 self.drop_count.fetch_add(1, Ordering::SeqCst);
2462 let count = core::sync::atomic::AtomicU32::new(0);
2464 Panic { drop_count: &count, aaaaa: false },
2465 Panic { drop_count: &count, aaaaa: true },
2466 Panic { drop_count: &count, aaaaa: false },
2469 // This should clone&append one Panic{..} at the end, and then panic while
2470 // cloning second Panic{..}. This means that `Panic::drop` should be called
2471 // 4 times (3 for items already in vector, 1 for just appended).
2473 // Previously just appended item was leaked, making drop_count = 3, instead of 4.
2474 std::panic::catch_unwind(move || vec.extend_from_within(..)).unwrap_err();
2476 assert_eq!(count.load(Ordering::SeqCst), 4);
2480 #[should_panic = "vec len overflow"]
2481 fn test_into_flattened_size_overflow() {
2482 let v = vec![[(); usize::MAX]; 2];
2483 let _ = v.into_flattened();