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::*;
11 use std::iter::InPlaceIterable;
13 use std::mem::{size_of, swap};
14 use std::ops::Bound::*;
15 use std::panic::{catch_unwind, AssertUnwindSafe};
17 use std::sync::atomic::{AtomicU32, Ordering};
18 use std::vec::{Drain, IntoIter};
20 struct DropCounter<'a> {
24 impl Drop for DropCounter<'_> {
31 fn test_small_vec_struct() {
32 assert_eq!(size_of::<Vec<u8>>(), size_of::<usize>() * 3);
36 fn test_double_drop() {
42 let (mut count_x, mut count_y) = (0, 0);
44 let mut tv = TwoVec { x: Vec::new(), y: Vec::new() };
45 tv.x.push(DropCounter { count: &mut count_x });
46 tv.y.push(DropCounter { count: &mut count_y });
48 // If Vec had a drop flag, here is where it would be zeroed.
49 // Instead, it should rely on its internal state to prevent
50 // doing anything significant when dropped multiple times.
53 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
56 assert_eq!(count_x, 1);
57 assert_eq!(count_y, 1);
62 let mut v = Vec::new();
63 assert_eq!(v.capacity(), 0);
66 assert!(v.capacity() >= 2);
72 assert!(v.capacity() >= 16);
74 assert!(v.capacity() >= 32);
79 assert!(v.capacity() >= 33)
83 fn test_zst_capacity() {
84 assert_eq!(Vec::<()>::new().capacity(), usize::MAX);
89 let v: Vec<isize> = vec![10, 20];
94 assert_eq!(v[x + 1], 20);
97 assert_eq!(v[x - 1], 10);
101 fn test_debug_fmt() {
102 let vec1: Vec<isize> = vec![];
103 assert_eq!("[]", format!("{:?}", vec1));
105 let vec2 = vec![0, 1];
106 assert_eq!("[0, 1]", format!("{:?}", vec2));
108 let slice: &[isize] = &[4, 5];
109 assert_eq!("[4, 5]", format!("{slice:?}"));
118 assert_eq!(v, [1, 2]);
120 assert_eq!(v, [1, 2, 3]);
125 let mut v = Vec::new();
126 let mut w = Vec::new();
145 v.extend(w.clone()); // specializes to `append`
146 assert!(v.iter().eq(w.iter().chain(w.iter())));
149 #[derive(PartialEq, Debug)]
152 let mut a = Vec::new();
153 let b = vec![Foo, Foo];
156 assert_eq!(a, &[Foo, Foo]);
161 let mut x = Vec::new();
162 let y = vec![DropCounter { count: &mut count_x }];
165 assert_eq!(count_x, 1);
169 fn test_extend_from_slice() {
170 let a: Vec<isize> = vec![1, 2, 3, 4, 5];
171 let b: Vec<isize> = vec![6, 7, 8, 9, 0];
173 let mut v: Vec<isize> = a;
175 v.extend_from_slice(&b);
177 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
181 fn test_extend_ref() {
182 let mut v = vec![1, 2];
183 v.extend(&[3, 4, 5]);
185 assert_eq!(v.len(), 5);
186 assert_eq!(v, [1, 2, 3, 4, 5]);
191 assert_eq!(v.len(), 7);
192 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
196 fn test_slice_from_ref() {
197 let values = vec![1, 2, 3, 4, 5];
198 let slice = &values[1..3];
200 assert_eq!(slice, [2, 3]);
204 fn test_slice_from_mut() {
205 let mut values = vec![1, 2, 3, 4, 5];
207 let slice = &mut values[2..];
208 assert!(slice == [3, 4, 5]);
214 assert!(values == [1, 2, 5, 6, 7]);
218 fn test_slice_to_mut() {
219 let mut values = vec![1, 2, 3, 4, 5];
221 let slice = &mut values[..2];
222 assert!(slice == [1, 2]);
228 assert!(values == [2, 3, 3, 4, 5]);
232 fn test_split_at_mut() {
233 let mut values = vec![1, 2, 3, 4, 5];
235 let (left, right) = values.split_at_mut(2);
237 let left: &[_] = left;
238 assert!(&left[..left.len()] == &[1, 2]);
245 let right: &[_] = right;
246 assert!(&right[..right.len()] == &[3, 4, 5]);
253 assert_eq!(values, [2, 3, 5, 6, 7]);
258 let v: Vec<i32> = vec![];
259 let w = vec![1, 2, 3];
261 assert_eq!(v, v.clone());
265 // they should be disjoint in memory.
266 assert!(w.as_ptr() != z.as_ptr())
270 fn test_clone_from() {
272 let three: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(3)];
273 let two: Vec<Box<_>> = vec![Box::new(4), Box::new(5)];
275 v.clone_from(&three);
276 assert_eq!(v, three);
279 v.clone_from(&three);
280 assert_eq!(v, three);
287 v.clone_from(&three);
293 let mut vec = vec![1, 2, 3, 4];
294 vec.retain(|&x| x % 2 == 0);
295 assert_eq!(vec, [2, 4]);
299 fn test_retain_predicate_order() {
300 for to_keep in [true, false] {
301 let mut number_of_executions = 0;
302 let mut vec = vec![1, 2, 3, 4];
303 let mut next_expected = 1;
305 assert_eq!(next_expected, x);
307 number_of_executions += 1;
310 assert_eq!(number_of_executions, 4);
315 fn test_retain_pred_panic_with_hole() {
316 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
317 catch_unwind(AssertUnwindSafe(|| {
318 let mut v = v.clone();
319 v.retain(|r| match **r {
327 // Everything is dropped when predicate panicked.
328 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
332 fn test_retain_pred_panic_no_hole() {
333 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
334 catch_unwind(AssertUnwindSafe(|| {
335 let mut v = v.clone();
336 v.retain(|r| match **r {
342 // Everything is dropped when predicate panicked.
343 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
347 fn test_retain_drop_panic() {
348 struct Wrap(Rc<i32>);
358 let v = (0..5).map(|x| Rc::new(x)).collect::<Vec<_>>();
359 catch_unwind(AssertUnwindSafe(|| {
360 let mut v = v.iter().map(|r| Wrap(r.clone())).collect::<Vec<_>>();
361 v.retain(|w| match *w.0 {
365 3 => false, // Drop panic.
370 // Other elements are dropped when `drop` of one element panicked.
371 // The panicked wrapper also has its Rc dropped.
372 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
376 fn test_retain_maybeuninits() {
377 // This test aimed to be run under miri.
378 use core::mem::MaybeUninit;
379 let mut vec: Vec<_> = [1i32, 2, 3, 4].map(|v| MaybeUninit::new(vec![v])).into();
381 // SAFETY: Retain must visit every element of Vec in original order and exactly once.
382 // Our values is initialized at creation of Vec.
383 let v = unsafe { x.assume_init_ref()[0] };
387 // SAFETY: Value is initialized.
388 // Value wouldn't be dropped by `Vec::retain`
389 // because `MaybeUninit` doesn't drop content.
390 drop(unsafe { x.assume_init_read() });
393 let vec: Vec<i32> = vec
396 // SAFETY: All values dropped in retain predicate must be removed by `Vec::retain`.
397 // Remaining values are initialized.
401 assert_eq!(vec, [2, 4]);
406 fn case(a: Vec<i32>, b: Vec<i32>) {
411 case(vec![], vec![]);
412 case(vec![1], vec![1]);
413 case(vec![1, 1], vec![1]);
414 case(vec![1, 2, 3], vec![1, 2, 3]);
415 case(vec![1, 1, 2, 3], vec![1, 2, 3]);
416 case(vec![1, 2, 2, 3], vec![1, 2, 3]);
417 case(vec![1, 2, 3, 3], vec![1, 2, 3]);
418 case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
422 fn test_dedup_by_key() {
423 fn case(a: Vec<i32>, b: Vec<i32>) {
425 v.dedup_by_key(|i| *i / 10);
428 case(vec![], vec![]);
429 case(vec![10], vec![10]);
430 case(vec![10, 11], vec![10]);
431 case(vec![10, 20, 30], vec![10, 20, 30]);
432 case(vec![10, 11, 20, 30], vec![10, 20, 30]);
433 case(vec![10, 20, 21, 30], vec![10, 20, 30]);
434 case(vec![10, 20, 30, 31], vec![10, 20, 30]);
435 case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
440 let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
441 vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
443 assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
445 let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
446 vec.dedup_by(|a, b| {
453 assert_eq!(vec, [("foo", 3), ("bar", 12)]);
457 fn test_dedup_unique() {
458 let mut v0: Vec<Box<_>> = vec![Box::new(1), Box::new(1), Box::new(2), Box::new(3)];
460 let mut v1: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(2), Box::new(3)];
462 let mut v2: Vec<Box<_>> = vec![Box::new(1), Box::new(2), Box::new(3), Box::new(3)];
464 // If the boxed pointers were leaked or otherwise misused, valgrind
465 // and/or rt should raise errors.
469 fn zero_sized_values() {
470 let mut v = Vec::new();
471 assert_eq!(v.len(), 0);
473 assert_eq!(v.len(), 1);
475 assert_eq!(v.len(), 2);
476 assert_eq!(v.pop(), Some(()));
477 assert_eq!(v.pop(), Some(()));
478 assert_eq!(v.pop(), None);
480 assert_eq!(v.iter().count(), 0);
482 assert_eq!(v.iter().count(), 1);
484 assert_eq!(v.iter().count(), 2);
488 assert_eq!(v.iter_mut().count(), 2);
490 assert_eq!(v.iter_mut().count(), 3);
492 assert_eq!(v.iter_mut().count(), 4);
494 for &mut () in &mut v {}
498 assert_eq!(v.iter_mut().count(), 0);
502 fn test_partition() {
503 assert_eq!([].into_iter().partition(|x: &i32| *x < 3), (vec![], vec![]));
504 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 4), (vec![1, 2, 3], vec![]));
505 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 2), (vec![1], vec![2, 3]));
506 assert_eq!([1, 2, 3].into_iter().partition(|x| *x < 0), (vec![], vec![1, 2, 3]));
510 fn test_zip_unzip() {
511 let z1 = vec![(1, 4), (2, 5), (3, 6)];
513 let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
515 assert_eq!((1, 4), (left[0], right[0]));
516 assert_eq!((2, 5), (left[1], right[1]));
517 assert_eq!((3, 6), (left[2], right[2]));
522 let x: &[isize] = &[1, 2, 3, 4, 5];
523 let cmp: &[isize] = &[1, 2, 3, 4, 5];
524 assert_eq!(&x[..], cmp);
525 let cmp: &[isize] = &[3, 4, 5];
526 assert_eq!(&x[2..], cmp);
527 let cmp: &[isize] = &[1, 2, 3];
528 assert_eq!(&x[..3], cmp);
529 let cmp: &[isize] = &[2, 3, 4];
530 assert_eq!(&x[1..4], cmp);
532 let x: Vec<isize> = vec![1, 2, 3, 4, 5];
533 let cmp: &[isize] = &[1, 2, 3, 4, 5];
534 assert_eq!(&x[..], cmp);
535 let cmp: &[isize] = &[3, 4, 5];
536 assert_eq!(&x[2..], cmp);
537 let cmp: &[isize] = &[1, 2, 3];
538 assert_eq!(&x[..3], cmp);
539 let cmp: &[isize] = &[2, 3, 4];
540 assert_eq!(&x[1..4], cmp);
544 fn test_vec_truncate_drop() {
545 static mut DROPS: u32 = 0;
555 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
556 assert_eq!(unsafe { DROPS }, 0);
558 assert_eq!(unsafe { DROPS }, 2);
560 assert_eq!(unsafe { DROPS }, 5);
565 fn test_vec_truncate_fail() {
567 impl Drop for BadElem {
569 let BadElem(ref mut x) = *self;
571 panic!("BadElem panic: 0xbadbeef")
576 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
582 let vec = vec![1, 2, 3];
583 assert!(vec[1] == 2);
588 fn test_index_out_of_bounds() {
589 let vec = vec![1, 2, 3];
595 fn test_slice_out_of_bounds_1() {
596 let x = vec![1, 2, 3, 4, 5];
602 fn test_slice_out_of_bounds_2() {
603 let x = vec![1, 2, 3, 4, 5];
609 fn test_slice_out_of_bounds_3() {
610 let x = vec![1, 2, 3, 4, 5];
616 fn test_slice_out_of_bounds_4() {
617 let x = vec![1, 2, 3, 4, 5];
623 fn test_slice_out_of_bounds_5() {
624 let x = vec![1, 2, 3, 4, 5];
630 fn test_swap_remove_empty() {
631 let mut vec = Vec::<i32>::new();
636 fn test_move_items() {
637 let vec = vec![1, 2, 3];
638 let mut vec2 = vec![];
642 assert_eq!(vec2, [1, 2, 3]);
646 fn test_move_items_reverse() {
647 let vec = vec![1, 2, 3];
648 let mut vec2 = vec![];
649 for i in vec.into_iter().rev() {
652 assert_eq!(vec2, [3, 2, 1]);
656 fn test_move_items_zero_sized() {
657 let vec = vec![(), (), ()];
658 let mut vec2 = vec![];
662 assert_eq!(vec2, [(), (), ()]);
666 fn test_drain_empty_vec() {
667 let mut vec: Vec<i32> = vec![];
668 let mut vec2: Vec<i32> = vec![];
669 for i in vec.drain(..) {
672 assert!(vec.is_empty());
673 assert!(vec2.is_empty());
677 fn test_drain_items() {
678 let mut vec = vec![1, 2, 3];
679 let mut vec2 = vec![];
680 for i in vec.drain(..) {
684 assert_eq!(vec2, [1, 2, 3]);
688 fn test_drain_items_reverse() {
689 let mut vec = vec![1, 2, 3];
690 let mut vec2 = vec![];
691 for i in vec.drain(..).rev() {
695 assert_eq!(vec2, [3, 2, 1]);
699 fn test_drain_items_zero_sized() {
700 let mut vec = vec![(), (), ()];
701 let mut vec2 = vec![];
702 for i in vec.drain(..) {
706 assert_eq!(vec2, [(), (), ()]);
711 fn test_drain_out_of_bounds() {
712 let mut v = vec![1, 2, 3, 4, 5];
717 fn test_drain_range() {
718 let mut v = vec![1, 2, 3, 4, 5];
719 for _ in v.drain(4..) {}
720 assert_eq!(v, &[1, 2, 3, 4]);
722 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
723 for _ in v.drain(1..4) {}
724 assert_eq!(v, &[1.to_string(), 5.to_string()]);
726 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
727 for _ in v.drain(1..4).rev() {}
728 assert_eq!(v, &[1.to_string(), 5.to_string()]);
730 let mut v: Vec<_> = vec![(); 5];
731 for _ in v.drain(1..4).rev() {}
732 assert_eq!(v, &[(), ()]);
736 fn test_drain_inclusive_range() {
737 let mut v = vec!['a', 'b', 'c', 'd', 'e'];
738 for _ in v.drain(1..=3) {}
739 assert_eq!(v, &['a', 'e']);
741 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
742 for _ in v.drain(1..=5) {}
743 assert_eq!(v, &["0".to_string()]);
745 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
746 for _ in v.drain(0..=5) {}
747 assert_eq!(v, Vec::<String>::new());
749 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
750 for _ in v.drain(0..=3) {}
751 assert_eq!(v, &["4".to_string(), "5".to_string()]);
753 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
754 for _ in v.drain(..=0) {}
755 assert_eq!(v, &["1".to_string()]);
759 fn test_drain_max_vec_size() {
760 let mut v = Vec::<()>::with_capacity(usize::MAX);
762 v.set_len(usize::MAX);
764 for _ in v.drain(usize::MAX - 1..) {}
765 assert_eq!(v.len(), usize::MAX - 1);
767 let mut v = Vec::<()>::with_capacity(usize::MAX);
769 v.set_len(usize::MAX);
771 for _ in v.drain(usize::MAX - 1..=usize::MAX - 1) {}
772 assert_eq!(v.len(), usize::MAX - 1);
777 fn test_drain_index_overflow() {
778 let mut v = Vec::<()>::with_capacity(usize::MAX);
780 v.set_len(usize::MAX);
782 v.drain(0..=usize::MAX);
787 fn test_drain_inclusive_out_of_bounds() {
788 let mut v = vec![1, 2, 3, 4, 5];
794 fn test_drain_start_overflow() {
795 let mut v = vec![1, 2, 3];
796 v.drain((Excluded(usize::MAX), Included(0)));
801 fn test_drain_end_overflow() {
802 let mut v = vec![1, 2, 3];
803 v.drain((Included(0), Included(usize::MAX)));
807 fn test_drain_leak() {
808 static mut DROPS: i32 = 0;
810 #[derive(Debug, PartialEq)]
820 panic!("panic in `drop`");
835 catch_unwind(AssertUnwindSafe(|| {
840 assert_eq!(unsafe { DROPS }, 4);
841 assert_eq!(v, vec![D(0, false), D(1, false), D(6, false),]);
845 fn test_drain_keep_rest() {
846 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
847 let mut drain = v.drain(1..6);
848 assert_eq!(drain.next(), Some(1));
849 assert_eq!(drain.next_back(), Some(5));
850 assert_eq!(drain.next(), Some(2));
853 assert_eq!(v, &[0, 3, 4, 6]);
857 fn test_drain_keep_rest_all() {
858 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
859 v.drain(1..6).keep_rest();
860 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6]);
864 fn test_drain_keep_rest_none() {
865 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
866 let mut drain = v.drain(1..6);
868 drain.by_ref().for_each(drop);
871 assert_eq!(v, &[0, 6]);
876 let mut v = vec![1, 2, 3, 4, 5];
877 let a = [10, 11, 12];
879 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
880 v.splice(1..3, Some(20));
881 assert_eq!(v, &[1, 20, 11, 12, 5]);
885 fn test_splice_inclusive_range() {
886 let mut v = vec![1, 2, 3, 4, 5];
887 let a = [10, 11, 12];
888 let t1: Vec<_> = v.splice(2..=3, a).collect();
889 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
890 assert_eq!(t1, &[3, 4]);
891 let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
892 assert_eq!(v, &[1, 20, 11, 12, 5]);
893 assert_eq!(t2, &[2, 10]);
898 fn test_splice_out_of_bounds() {
899 let mut v = vec![1, 2, 3, 4, 5];
900 let a = [10, 11, 12];
906 fn test_splice_inclusive_out_of_bounds() {
907 let mut v = vec![1, 2, 3, 4, 5];
908 let a = [10, 11, 12];
913 fn test_splice_items_zero_sized() {
914 let mut vec = vec![(), (), ()];
916 let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
917 assert_eq!(vec, &[(), ()]);
918 assert_eq!(t, &[()]);
922 fn test_splice_unbounded() {
923 let mut vec = vec![1, 2, 3, 4, 5];
924 let t: Vec<_> = vec.splice(.., None).collect();
925 assert_eq!(vec, &[]);
926 assert_eq!(t, &[1, 2, 3, 4, 5]);
930 fn test_splice_forget() {
931 let mut v = vec![1, 2, 3, 4, 5];
932 let a = [10, 11, 12];
933 std::mem::forget(v.splice(2..4, a));
934 assert_eq!(v, &[1, 2]);
938 fn test_into_boxed_slice() {
939 let xs = vec![1, 2, 3];
940 let ys = xs.into_boxed_slice();
941 assert_eq!(&*ys, [1, 2, 3]);
946 let mut vec = vec![1, 2, 3];
947 let mut vec2 = vec![4, 5, 6];
948 vec.append(&mut vec2);
949 assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
950 assert_eq!(vec2, []);
954 fn test_split_off() {
955 let mut vec = vec![1, 2, 3, 4, 5, 6];
956 let orig_capacity = vec.capacity();
957 let vec2 = vec.split_off(4);
958 assert_eq!(vec, [1, 2, 3, 4]);
959 assert_eq!(vec2, [5, 6]);
960 assert_eq!(vec.capacity(), orig_capacity);
964 fn test_split_off_take_all() {
965 let mut vec = vec![1, 2, 3, 4, 5, 6];
966 let orig_ptr = vec.as_ptr();
967 let orig_capacity = vec.capacity();
968 let vec2 = vec.split_off(0);
970 assert_eq!(vec2, [1, 2, 3, 4, 5, 6]);
971 assert_eq!(vec.capacity(), orig_capacity);
972 assert_eq!(vec2.as_ptr(), orig_ptr);
976 fn test_into_iter_as_slice() {
977 let vec = vec!['a', 'b', 'c'];
978 let mut into_iter = vec.into_iter();
979 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
980 let _ = into_iter.next().unwrap();
981 assert_eq!(into_iter.as_slice(), &['b', 'c']);
982 let _ = into_iter.next().unwrap();
983 let _ = into_iter.next().unwrap();
984 assert_eq!(into_iter.as_slice(), &[]);
988 fn test_into_iter_as_mut_slice() {
989 let vec = vec!['a', 'b', 'c'];
990 let mut into_iter = vec.into_iter();
991 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
992 into_iter.as_mut_slice()[0] = 'x';
993 into_iter.as_mut_slice()[1] = 'y';
994 assert_eq!(into_iter.next().unwrap(), 'x');
995 assert_eq!(into_iter.as_slice(), &['y', 'c']);
999 fn test_into_iter_debug() {
1000 let vec = vec!['a', 'b', 'c'];
1001 let into_iter = vec.into_iter();
1002 let debug = format!("{into_iter:?}");
1003 assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
1007 fn test_into_iter_count() {
1008 assert_eq!([1, 2, 3].into_iter().count(), 3);
1012 fn test_into_iter_next_chunk() {
1013 let mut iter = b"lorem".to_vec().into_iter();
1015 assert_eq!(iter.next_chunk().unwrap(), [b'l', b'o']); // N is inferred as 2
1016 assert_eq!(iter.next_chunk().unwrap(), [b'r', b'e', b'm']); // N is inferred as 3
1017 assert_eq!(iter.next_chunk::<4>().unwrap_err().as_slice(), &[]); // N is explicitly 4
1021 fn test_into_iter_clone() {
1022 fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
1023 let v: Vec<i32> = it.collect();
1024 assert_eq!(&v[..], slice);
1026 let mut it = [1, 2, 3].into_iter();
1027 iter_equal(it.clone(), &[1, 2, 3]);
1028 assert_eq!(it.next(), Some(1));
1029 let mut it = it.rev();
1030 iter_equal(it.clone(), &[3, 2]);
1031 assert_eq!(it.next(), Some(3));
1032 iter_equal(it.clone(), &[2]);
1033 assert_eq!(it.next(), Some(2));
1034 iter_equal(it.clone(), &[]);
1035 assert_eq!(it.next(), None);
1039 fn test_into_iter_leak() {
1040 static mut DROPS: i32 = 0;
1045 fn drop(&mut self) {
1051 panic!("panic in `drop`");
1056 let v = vec![D(false), D(true), D(false)];
1058 catch_unwind(move || drop(v.into_iter())).ok();
1060 assert_eq!(unsafe { DROPS }, 3);
1064 fn test_into_iter_advance_by() {
1065 let mut i = [1, 2, 3, 4, 5].into_iter();
1066 i.advance_by(0).unwrap();
1067 i.advance_back_by(0).unwrap();
1068 assert_eq!(i.as_slice(), [1, 2, 3, 4, 5]);
1070 i.advance_by(1).unwrap();
1071 i.advance_back_by(1).unwrap();
1072 assert_eq!(i.as_slice(), [2, 3, 4]);
1074 assert_eq!(i.advance_back_by(usize::MAX), Err(3));
1076 assert_eq!(i.advance_by(usize::MAX), Err(0));
1078 i.advance_by(0).unwrap();
1079 i.advance_back_by(0).unwrap();
1081 assert_eq!(i.len(), 0);
1085 fn test_into_iter_drop_allocator() {
1086 struct ReferenceCountedAllocator<'a>(DropCounter<'a>);
1088 unsafe impl Allocator for ReferenceCountedAllocator<'_> {
1089 fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, core::alloc::AllocError> {
1090 System.allocate(layout)
1093 unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
1094 // Safety: Invariants passed to caller.
1095 unsafe { System.deallocate(ptr, layout) }
1099 let mut drop_count = 0;
1101 let allocator = ReferenceCountedAllocator(DropCounter { count: &mut drop_count });
1102 let _ = Vec::<u32, _>::new_in(allocator);
1103 assert_eq!(drop_count, 1);
1105 let allocator = ReferenceCountedAllocator(DropCounter { count: &mut drop_count });
1106 let _ = Vec::<u32, _>::new_in(allocator).into_iter();
1107 assert_eq!(drop_count, 2);
1111 fn test_into_iter_zst() {
1112 #[derive(Debug, Clone)]
1113 struct AlignedZstWithDrop([u64; 0]);
1114 impl Drop for AlignedZstWithDrop {
1115 fn drop(&mut self) {
1116 let addr = self as *mut _ as usize;
1117 assert!(hint::black_box(addr) % mem::align_of::<u64>() == 0);
1121 const C: AlignedZstWithDrop = AlignedZstWithDrop([0u64; 0]);
1123 for _ in vec![C].into_iter() {}
1124 for _ in vec![C; 5].into_iter().rev() {}
1126 let mut it = vec![C, C].into_iter();
1127 it.advance_by(1).unwrap();
1130 let mut it = vec![C, C].into_iter();
1131 it.next_chunk::<1>().unwrap();
1134 let mut it = vec![C, C].into_iter();
1135 it.next_chunk::<4>().unwrap_err();
1140 fn test_from_iter_specialization() {
1141 let src: Vec<usize> = vec![0usize; 1];
1142 let srcptr = src.as_ptr();
1143 let sink = src.into_iter().collect::<Vec<_>>();
1144 let sinkptr = sink.as_ptr();
1145 assert_eq!(srcptr, sinkptr);
1149 fn test_from_iter_partially_drained_in_place_specialization() {
1150 let src: Vec<usize> = vec![0usize; 10];
1151 let srcptr = src.as_ptr();
1152 let mut iter = src.into_iter();
1155 let sink = iter.collect::<Vec<_>>();
1156 let sinkptr = sink.as_ptr();
1157 assert_eq!(srcptr, sinkptr);
1161 fn test_from_iter_specialization_with_iterator_adapters() {
1162 fn assert_in_place_trait<T: InPlaceIterable>(_: &T) {}
1163 let src: Vec<usize> = vec![0usize; 256];
1164 let srcptr = src.as_ptr();
1169 .zip(std::iter::repeat(1usize))
1170 .map(|(a, b)| a + b)
1171 .map_while(Option::Some)
1173 .map(|e| if e != usize::MAX { Ok(std::num::NonZeroUsize::new(e)) } else { Err(()) });
1174 assert_in_place_trait(&iter);
1175 let sink = iter.collect::<Result<Vec<_>, _>>().unwrap();
1176 let sinkptr = sink.as_ptr();
1177 assert_eq!(srcptr, sinkptr as *const usize);
1181 fn test_from_iter_specialization_head_tail_drop() {
1182 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1183 let src: Vec<_> = drop_count.iter().cloned().collect();
1184 let srcptr = src.as_ptr();
1185 let iter = src.into_iter();
1186 let sink: Vec<_> = iter.skip(1).take(1).collect();
1187 let sinkptr = sink.as_ptr();
1188 assert_eq!(srcptr, sinkptr, "specialization was applied");
1189 assert_eq!(Rc::strong_count(&drop_count[0]), 1, "front was dropped");
1190 assert_eq!(Rc::strong_count(&drop_count[1]), 2, "one element was collected");
1191 assert_eq!(Rc::strong_count(&drop_count[2]), 1, "tail was dropped");
1192 assert_eq!(sink.len(), 1);
1196 fn test_from_iter_specialization_panic_during_iteration_drops() {
1197 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1198 let src: Vec<_> = drop_count.iter().cloned().collect();
1199 let iter = src.into_iter();
1201 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1204 .filter_map(|(i, e)| {
1206 std::panic!("aborting iteration");
1210 .collect::<Vec<_>>();
1214 drop_count.iter().map(Rc::strong_count).all(|count| count == 1),
1215 "all items were dropped once"
1220 fn test_from_iter_specialization_panic_during_drop_doesnt_leak() {
1221 static mut DROP_COUNTER_OLD: [usize; 5] = [0; 5];
1222 static mut DROP_COUNTER_NEW: [usize; 2] = [0; 2];
1228 fn drop(&mut self) {
1230 DROP_COUNTER_OLD[self.0] += 1;
1237 println!("Dropped Old: {}", self.0);
1245 fn drop(&mut self) {
1247 DROP_COUNTER_NEW[self.0] += 1;
1250 println!("Dropped New: {}", self.0);
1254 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1255 let v = vec![Old(0), Old(1), Old(2), Old(3), Old(4)];
1256 let _ = v.into_iter().map(|x| New(x.0)).take(2).collect::<Vec<_>>();
1259 assert_eq!(unsafe { DROP_COUNTER_OLD[0] }, 1);
1260 assert_eq!(unsafe { DROP_COUNTER_OLD[1] }, 1);
1261 assert_eq!(unsafe { DROP_COUNTER_OLD[2] }, 1);
1262 assert_eq!(unsafe { DROP_COUNTER_OLD[3] }, 1);
1263 assert_eq!(unsafe { DROP_COUNTER_OLD[4] }, 1);
1265 assert_eq!(unsafe { DROP_COUNTER_NEW[0] }, 1);
1266 assert_eq!(unsafe { DROP_COUNTER_NEW[1] }, 1);
1269 // regression test for issue #85322. Peekable previously implemented InPlaceIterable,
1270 // but due to an interaction with IntoIter's current Clone implementation it failed to uphold
1273 fn test_collect_after_iterator_clone() {
1275 let mut i = v.into_iter().map(|i| i + 1).peekable();
1277 let v = i.clone().collect::<Vec<_>>();
1278 assert_eq!(v, [1, 1, 1, 1, 1]);
1279 assert!(v.len() <= v.capacity());
1282 fn test_cow_from() {
1283 let borrowed: &[_] = &["borrowed", "(slice)"];
1284 let owned = vec!["owned", "(vec)"];
1285 match (Cow::from(owned.clone()), Cow::from(borrowed)) {
1286 (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
1287 _ => panic!("invalid `Cow::from`"),
1292 fn test_from_cow() {
1293 let borrowed: &[_] = &["borrowed", "(slice)"];
1294 let owned = vec!["owned", "(vec)"];
1295 assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
1296 assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
1300 fn assert_covariance() {
1301 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1304 fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
1310 fn from_into_inner() {
1311 let vec = vec![1, 2, 3];
1312 let ptr = vec.as_ptr();
1313 let vec = vec.into_iter().collect::<Vec<_>>();
1314 assert_eq!(vec, [1, 2, 3]);
1315 assert_eq!(vec.as_ptr(), ptr);
1317 let ptr = &vec[1] as *const _;
1318 let mut it = vec.into_iter();
1320 let vec = it.collect::<Vec<_>>();
1321 assert_eq!(vec, [2, 3]);
1322 assert!(ptr != vec.as_ptr());
1326 fn overaligned_allocations() {
1329 let mut v = vec![Foo(273)];
1330 for i in 0..0x1000 {
1332 assert!(v[0].0 == 273);
1333 assert!(v.as_ptr() as usize & 0xff == 0);
1335 assert!(v[0].0 == 273);
1336 assert!(v.as_ptr() as usize & 0xff == 0);
1341 fn drain_filter_empty() {
1342 let mut vec: Vec<i32> = vec![];
1345 let mut iter = vec.drain_filter(|_| true);
1346 assert_eq!(iter.size_hint(), (0, Some(0)));
1347 assert_eq!(iter.next(), None);
1348 assert_eq!(iter.size_hint(), (0, Some(0)));
1349 assert_eq!(iter.next(), None);
1350 assert_eq!(iter.size_hint(), (0, Some(0)));
1352 assert_eq!(vec.len(), 0);
1353 assert_eq!(vec, vec![]);
1357 fn drain_filter_zst() {
1358 let mut vec = vec![(), (), (), (), ()];
1359 let initial_len = vec.len();
1362 let mut iter = vec.drain_filter(|_| true);
1363 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1364 while let Some(_) = iter.next() {
1366 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1368 assert_eq!(iter.size_hint(), (0, Some(0)));
1369 assert_eq!(iter.next(), None);
1370 assert_eq!(iter.size_hint(), (0, Some(0)));
1373 assert_eq!(count, initial_len);
1374 assert_eq!(vec.len(), 0);
1375 assert_eq!(vec, vec![]);
1379 fn drain_filter_false() {
1380 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1382 let initial_len = vec.len();
1385 let mut iter = vec.drain_filter(|_| false);
1386 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1387 for _ in iter.by_ref() {
1390 assert_eq!(iter.size_hint(), (0, Some(0)));
1391 assert_eq!(iter.next(), None);
1392 assert_eq!(iter.size_hint(), (0, Some(0)));
1395 assert_eq!(count, 0);
1396 assert_eq!(vec.len(), initial_len);
1397 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1401 fn drain_filter_true() {
1402 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1404 let initial_len = vec.len();
1407 let mut iter = vec.drain_filter(|_| true);
1408 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1409 while let Some(_) = iter.next() {
1411 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1413 assert_eq!(iter.size_hint(), (0, Some(0)));
1414 assert_eq!(iter.next(), None);
1415 assert_eq!(iter.size_hint(), (0, Some(0)));
1418 assert_eq!(count, initial_len);
1419 assert_eq!(vec.len(), 0);
1420 assert_eq!(vec, vec![]);
1424 fn drain_filter_complex() {
1426 // [+xxx++++++xxxxx++++x+x++]
1428 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
1432 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1433 assert_eq!(removed.len(), 10);
1434 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1436 assert_eq!(vec.len(), 14);
1437 assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1441 // [xxx++++++xxxxx++++x+x++]
1443 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
1446 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1447 assert_eq!(removed.len(), 10);
1448 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1450 assert_eq!(vec.len(), 13);
1451 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1455 // [xxx++++++xxxxx++++x+x]
1457 vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36];
1459 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1460 assert_eq!(removed.len(), 10);
1461 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1463 assert_eq!(vec.len(), 11);
1464 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
1468 // [xxxxxxxxxx+++++++++++]
1469 let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
1471 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1472 assert_eq!(removed.len(), 10);
1473 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1475 assert_eq!(vec.len(), 10);
1476 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1480 // [+++++++++++xxxxxxxxxx]
1481 let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
1483 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1484 assert_eq!(removed.len(), 10);
1485 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1487 assert_eq!(vec.len(), 10);
1488 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1492 // FIXME: re-enable emscripten once it can unwind again
1494 #[cfg(not(target_os = "emscripten"))]
1495 fn drain_filter_consumed_panic() {
1497 use std::sync::Mutex;
1501 drop_counts: Rc<Mutex<Vec<usize>>>,
1504 impl Drop for Check {
1505 fn drop(&mut self) {
1506 self.drop_counts.lock().unwrap()[self.index] += 1;
1507 println!("drop: {}", self.index);
1511 let check_count = 10;
1512 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1513 let mut data: Vec<Check> = (0..check_count)
1514 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1517 let _ = std::panic::catch_unwind(move || {
1518 let filter = |c: &mut Check| {
1520 panic!("panic at index: {}", c.index);
1522 // Verify that if the filter could panic again on another element
1523 // that it would not cause a double panic and all elements of the
1524 // vec would still be dropped exactly once.
1526 panic!("panic at index: {}", c.index);
1530 let drain = data.drain_filter(filter);
1532 // NOTE: The DrainFilter is explicitly consumed
1533 drain.for_each(drop);
1536 let drop_counts = drop_counts.lock().unwrap();
1537 assert_eq!(check_count, drop_counts.len());
1539 for (index, count) in drop_counts.iter().cloned().enumerate() {
1540 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1544 // FIXME: Re-enable emscripten once it can catch panics
1546 #[cfg(not(target_os = "emscripten"))]
1547 fn drain_filter_unconsumed_panic() {
1549 use std::sync::Mutex;
1553 drop_counts: Rc<Mutex<Vec<usize>>>,
1556 impl Drop for Check {
1557 fn drop(&mut self) {
1558 self.drop_counts.lock().unwrap()[self.index] += 1;
1559 println!("drop: {}", self.index);
1563 let check_count = 10;
1564 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1565 let mut data: Vec<Check> = (0..check_count)
1566 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1569 let _ = std::panic::catch_unwind(move || {
1570 let filter = |c: &mut Check| {
1572 panic!("panic at index: {}", c.index);
1574 // Verify that if the filter could panic again on another element
1575 // that it would not cause a double panic and all elements of the
1576 // vec would still be dropped exactly once.
1578 panic!("panic at index: {}", c.index);
1582 let _drain = data.drain_filter(filter);
1584 // NOTE: The DrainFilter is dropped without being consumed
1587 let drop_counts = drop_counts.lock().unwrap();
1588 assert_eq!(check_count, drop_counts.len());
1590 for (index, count) in drop_counts.iter().cloned().enumerate() {
1591 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1596 fn drain_filter_unconsumed() {
1597 let mut vec = vec![1, 2, 3, 4];
1598 let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1600 assert_eq!(vec, [2, 4]);
1604 fn test_drain_filter_keep_rest() {
1605 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
1606 let mut drain = v.drain_filter(|&mut x| x % 2 == 0);
1607 assert_eq!(drain.next(), Some(0));
1608 assert_eq!(drain.next(), Some(2));
1611 assert_eq!(v, &[1, 3, 4, 5, 6]);
1615 fn test_drain_filter_keep_rest_all() {
1616 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
1617 v.drain_filter(|_| true).keep_rest();
1618 assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6]);
1622 fn test_drain_filter_keep_rest_none() {
1623 let mut v = vec![0, 1, 2, 3, 4, 5, 6];
1624 let mut drain = v.drain_filter(|_| true);
1626 drain.by_ref().for_each(drop);
1633 fn test_reserve_exact() {
1634 // This is all the same as test_reserve
1636 let mut v = Vec::new();
1637 assert_eq!(v.capacity(), 0);
1640 assert!(v.capacity() >= 2);
1646 assert!(v.capacity() >= 16);
1647 v.reserve_exact(16);
1648 assert!(v.capacity() >= 32);
1652 v.reserve_exact(16);
1653 assert!(v.capacity() >= 33)
1657 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1658 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1659 fn test_try_reserve() {
1660 // These are the interesting cases:
1661 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1662 // * > isize::MAX should always fail
1663 // * On 16/32-bit should CapacityOverflow
1664 // * On 64-bit should OOM
1665 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1666 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1668 const MAX_CAP: usize = isize::MAX as usize;
1669 const MAX_USIZE: usize = usize::MAX;
1672 // Note: basic stuff is checked by test_reserve
1673 let mut empty_bytes: Vec<u8> = Vec::new();
1675 // Check isize::MAX doesn't count as an overflow
1676 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1677 panic!("isize::MAX shouldn't trigger an overflow!");
1679 // Play it again, frank! (just to be sure)
1680 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1681 panic!("isize::MAX shouldn't trigger an overflow!");
1684 // Check isize::MAX + 1 does count as overflow
1686 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1687 Err(CapacityOverflow),
1688 "isize::MAX + 1 should trigger an overflow!"
1691 // Check usize::MAX does count as overflow
1693 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1694 Err(CapacityOverflow),
1695 "usize::MAX should trigger an overflow!"
1700 // Same basic idea, but with non-zero len
1701 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1703 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1704 panic!("isize::MAX shouldn't trigger an overflow!");
1706 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1707 panic!("isize::MAX shouldn't trigger an overflow!");
1711 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1712 Err(CapacityOverflow),
1713 "isize::MAX + 1 should trigger an overflow!"
1716 // Should always overflow in the add-to-len
1718 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1719 Err(CapacityOverflow),
1720 "usize::MAX should trigger an overflow!"
1725 // Same basic idea, but with interesting type size
1726 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1728 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1730 panic!("isize::MAX shouldn't trigger an overflow!");
1732 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1734 panic!("isize::MAX shouldn't trigger an overflow!");
1738 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1739 Err(CapacityOverflow),
1740 "isize::MAX + 1 should trigger an overflow!"
1743 // Should fail in the mul-by-size
1745 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1746 Err(CapacityOverflow),
1747 "usize::MAX should trigger an overflow!"
1753 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1754 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1755 fn test_try_reserve_exact() {
1756 // This is exactly the same as test_try_reserve with the method changed.
1757 // See that test for comments.
1759 const MAX_CAP: usize = isize::MAX as usize;
1760 const MAX_USIZE: usize = usize::MAX;
1763 let mut empty_bytes: Vec<u8> = Vec::new();
1765 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1767 panic!("isize::MAX shouldn't trigger an overflow!");
1769 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1771 panic!("isize::MAX shouldn't trigger an overflow!");
1775 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1776 Err(CapacityOverflow),
1777 "isize::MAX + 1 should trigger an overflow!"
1781 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1782 Err(CapacityOverflow),
1783 "usize::MAX should trigger an overflow!"
1788 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1790 if let Err(CapacityOverflow) =
1791 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1793 panic!("isize::MAX shouldn't trigger an overflow!");
1795 if let Err(CapacityOverflow) =
1796 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1798 panic!("isize::MAX shouldn't trigger an overflow!");
1802 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1803 Err(CapacityOverflow),
1804 "isize::MAX + 1 should trigger an overflow!"
1808 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1809 Err(CapacityOverflow),
1810 "usize::MAX should trigger an overflow!"
1815 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1817 if let Err(CapacityOverflow) =
1818 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1820 panic!("isize::MAX shouldn't trigger an overflow!");
1822 if let Err(CapacityOverflow) =
1823 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1825 panic!("isize::MAX shouldn't trigger an overflow!");
1829 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1830 Err(CapacityOverflow),
1831 "isize::MAX + 1 should trigger an overflow!"
1835 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1836 Err(CapacityOverflow),
1837 "usize::MAX should trigger an overflow!"
1843 fn test_stable_pointers() {
1844 /// Pull an element from the iterator, then drop it.
1845 /// Useful to cover both the `next` and `drop` paths of an iterator.
1846 fn next_then_drop<I: Iterator>(mut i: I) {
1851 // Test that, if we reserved enough space, adding and removing elements does not
1852 // invalidate references into the vector (such as `v0`). This test also
1853 // runs in Miri, which would detect such problems.
1854 // Note that this test does *not* constitute a stable guarantee that all these functions do not
1855 // reallocate! Only what is explicitly documented at
1856 // <https://doc.rust-lang.org/nightly/std/vec/struct.Vec.html#guarantees> is stably guaranteed.
1857 let mut v = Vec::with_capacity(128);
1860 // Laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1862 let v0 = unsafe { &mut *(v0 as *mut _) };
1863 // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1865 // Pushing/inserting and popping/removing
1869 assert_eq!(*v0, 13);
1872 assert_eq!(*v0, 13);
1875 assert_eq!(v.len(), 2);
1876 v.swap_remove(1); // swap_remove the last element
1877 assert_eq!(*v0, 13);
1880 v.append(&mut vec![27, 19]);
1881 assert_eq!(*v0, 13);
1884 v.extend_from_slice(&[1, 2]);
1885 v.extend(&[1, 2]); // `slice::Iter` (with `T: Copy`) specialization
1886 v.extend(vec![2, 3]); // `vec::IntoIter` specialization
1887 v.extend(std::iter::once(3)); // `TrustedLen` specialization
1888 v.extend(std::iter::empty::<i32>()); // `TrustedLen` specialization with empty iterator
1889 v.extend(std::iter::once(3).filter(|_| true)); // base case
1890 v.extend(std::iter::once(&3)); // `cloned` specialization
1891 assert_eq!(*v0, 13);
1895 assert_eq!(*v0, 13);
1898 v.resize_with(v.len() + 10, || 42);
1899 assert_eq!(*v0, 13);
1900 v.resize_with(2, || panic!());
1901 assert_eq!(*v0, 13);
1903 // No-op reservation
1905 v.reserve_exact(32);
1906 assert_eq!(*v0, 13);
1909 v.resize_with(10, || 42);
1910 next_then_drop(v.drain(5..));
1911 assert_eq!(*v0, 13);
1914 v.resize_with(10, || 42);
1915 next_then_drop(v.splice(5.., vec![1, 2, 3, 4, 5])); // empty tail after range
1916 assert_eq!(*v0, 13);
1917 next_then_drop(v.splice(5..8, vec![1])); // replacement is smaller than original range
1918 assert_eq!(*v0, 13);
1919 next_then_drop(v.splice(5..6, [1; 10].into_iter().filter(|_| true))); // lower bound not exact
1920 assert_eq!(*v0, 13);
1922 // spare_capacity_mut
1923 v.spare_capacity_mut();
1924 assert_eq!(*v0, 13);
1926 // Smoke test that would fire even outside Miri if an actual relocation happened.
1928 assert_eq!(v[0], 0);
1931 // https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
1934 // unsafe impl<T: ?Sized> IsZero for *mut T {
1935 // fn is_zero(&self) -> bool {
1936 // (*self).is_null()
1941 // … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
1942 // which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
1943 // That is, a fat pointer can be “null” without being made entirely of zero bits.
1945 fn vec_macro_repeating_null_raw_fat_pointer() {
1946 let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
1947 let vtable = dbg!(ptr_metadata(raw_dyn));
1948 let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
1949 assert!(null_raw_dyn.is_null());
1951 let vec = vec![null_raw_dyn; 1];
1952 dbg!(ptr_metadata(vec[0]));
1953 assert!(vec[0] == null_raw_dyn);
1955 // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
1957 fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
1958 unsafe { std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable }
1961 fn ptr_from_raw_parts(data: *mut (), vtable: *mut ()) -> *mut dyn Fn() {
1962 unsafe { std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr { data, vtable }) }
1972 // This test will likely fail if you change the capacities used in
1973 // `RawVec::grow_amortized`.
1975 fn test_push_growth_strategy() {
1976 // If the element size is 1, we jump from 0 to 8, then double.
1978 let mut v1: Vec<u8> = vec![];
1979 assert_eq!(v1.capacity(), 0);
1983 assert_eq!(v1.capacity(), 8);
1988 assert_eq!(v1.capacity(), 16);
1993 assert_eq!(v1.capacity(), 32);
1998 assert_eq!(v1.capacity(), 64);
2002 // If the element size is 2..=1024, we jump from 0 to 4, then double.
2004 let mut v2: Vec<u16> = vec![];
2005 let mut v1024: Vec<[u8; 1024]> = vec![];
2006 assert_eq!(v2.capacity(), 0);
2007 assert_eq!(v1024.capacity(), 0);
2011 v1024.push([0; 1024]);
2012 assert_eq!(v2.capacity(), 4);
2013 assert_eq!(v1024.capacity(), 4);
2018 v1024.push([0; 1024]);
2019 assert_eq!(v2.capacity(), 8);
2020 assert_eq!(v1024.capacity(), 8);
2025 v1024.push([0; 1024]);
2026 assert_eq!(v2.capacity(), 16);
2027 assert_eq!(v1024.capacity(), 16);
2032 v1024.push([0; 1024]);
2033 assert_eq!(v2.capacity(), 32);
2034 assert_eq!(v1024.capacity(), 32);
2039 v1024.push([0; 1024]);
2040 assert_eq!(v2.capacity(), 64);
2041 assert_eq!(v1024.capacity(), 64);
2045 // If the element size is > 1024, we jump from 0 to 1, then double.
2047 let mut v1025: Vec<[u8; 1025]> = vec![];
2048 assert_eq!(v1025.capacity(), 0);
2051 v1025.push([0; 1025]);
2052 assert_eq!(v1025.capacity(), 1);
2056 v1025.push([0; 1025]);
2057 assert_eq!(v1025.capacity(), 2);
2061 v1025.push([0; 1025]);
2062 assert_eq!(v1025.capacity(), 4);
2066 v1025.push([0; 1025]);
2067 assert_eq!(v1025.capacity(), 8);
2071 v1025.push([0; 1025]);
2072 assert_eq!(v1025.capacity(), 16);
2076 v1025.push([0; 1025]);
2077 assert_eq!(v1025.capacity(), 32);
2081 v1025.push([0; 1025]);
2082 assert_eq!(v1025.capacity(), 64);
2087 macro_rules! generate_assert_eq_vec_and_prim {
2088 ($name:ident<$B:ident>($type:ty)) => {
2089 fn $name<A: PartialEq<$B> + Debug, $B: Debug>(a: Vec<A>, b: $type) {
2096 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_slice <B>(&[B]) }
2097 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_array_3<B>([B; 3]) }
2100 fn partialeq_vec_and_prim() {
2101 assert_eq_vec_and_slice(vec![1, 2, 3], &[1, 2, 3]);
2102 assert_eq_vec_and_array_3(vec![1, 2, 3], [1, 2, 3]);
2105 macro_rules! assert_partial_eq_valid {
2106 ($a2:expr, $a3:expr; $b2:expr, $b3: expr) => {
2107 assert!($a2 == $b2);
2108 assert!($a2 != $b3);
2109 assert!($a3 != $b2);
2110 assert!($a3 == $b3);
2111 assert_eq!($a2, $b2);
2112 assert_ne!($a2, $b3);
2113 assert_ne!($a3, $b2);
2114 assert_eq!($a3, $b3);
2119 fn partialeq_vec_full() {
2120 let vec2: Vec<_> = vec![1, 2];
2121 let vec3: Vec<_> = vec![1, 2, 3];
2122 let slice2: &[_] = &[1, 2];
2123 let slice3: &[_] = &[1, 2, 3];
2124 let slicemut2: &[_] = &mut [1, 2];
2125 let slicemut3: &[_] = &mut [1, 2, 3];
2126 let array2: [_; 2] = [1, 2];
2127 let array3: [_; 3] = [1, 2, 3];
2128 let arrayref2: &[_; 2] = &[1, 2];
2129 let arrayref3: &[_; 3] = &[1, 2, 3];
2131 assert_partial_eq_valid!(vec2,vec3; vec2,vec3);
2132 assert_partial_eq_valid!(vec2,vec3; slice2,slice3);
2133 assert_partial_eq_valid!(vec2,vec3; slicemut2,slicemut3);
2134 assert_partial_eq_valid!(slice2,slice3; vec2,vec3);
2135 assert_partial_eq_valid!(slicemut2,slicemut3; vec2,vec3);
2136 assert_partial_eq_valid!(vec2,vec3; array2,array3);
2137 assert_partial_eq_valid!(vec2,vec3; arrayref2,arrayref3);
2138 assert_partial_eq_valid!(vec2,vec3; arrayref2[..],arrayref3[..]);
2142 fn test_vec_cycle() {
2145 v: Vec<Cell<Option<&'a C<'a>>>>,
2154 let mut c1 = C::new();
2155 let mut c2 = C::new();
2156 let mut c3 = C::new();
2159 c1.v.push(Cell::new(None));
2160 c1.v.push(Cell::new(None));
2162 c2.v.push(Cell::new(None));
2163 c2.v.push(Cell::new(None));
2165 c3.v.push(Cell::new(None));
2166 c3.v.push(Cell::new(None));
2169 c1.v[0].set(Some(&c2));
2170 c1.v[1].set(Some(&c3));
2172 c2.v[0].set(Some(&c2));
2173 c2.v[1].set(Some(&c3));
2175 c3.v[0].set(Some(&c1));
2176 c3.v[1].set(Some(&c2));
2180 fn test_vec_cycle_wrapped() {
2182 v: Vec<Cell<Option<&'a C<'a>>>>,
2190 fn new() -> Refs<'a> {
2191 Refs { v: Vec::new() }
2197 C { refs: Refs::new() }
2201 let mut c1 = C::new();
2202 let mut c2 = C::new();
2203 let mut c3 = C::new();
2205 c1.refs.v.push(Cell::new(None));
2206 c1.refs.v.push(Cell::new(None));
2207 c2.refs.v.push(Cell::new(None));
2208 c2.refs.v.push(Cell::new(None));
2209 c3.refs.v.push(Cell::new(None));
2210 c3.refs.v.push(Cell::new(None));
2212 c1.refs.v[0].set(Some(&c2));
2213 c1.refs.v[1].set(Some(&c3));
2214 c2.refs.v[0].set(Some(&c2));
2215 c2.refs.v[1].set(Some(&c3));
2216 c3.refs.v[0].set(Some(&c1));
2217 c3.refs.v[1].set(Some(&c2));
2221 fn test_zero_sized_capacity() {
2222 for len in [0, 1, 2, 4, 8, 16, 32, 64, 128, 256] {
2223 let v = Vec::<()>::with_capacity(len);
2224 assert_eq!(v.len(), 0);
2225 assert_eq!(v.capacity(), usize::MAX);
2230 fn test_zero_sized_vec_push() {
2234 let mut tester = Vec::with_capacity(len);
2235 assert_eq!(tester.len(), 0);
2236 assert!(tester.capacity() >= len);
2240 assert_eq!(tester.len(), len);
2241 assert_eq!(tester.iter().count(), len);
2247 fn test_vec_macro_repeat() {
2248 assert_eq!(vec![1; 3], vec![1, 1, 1]);
2249 assert_eq!(vec![1; 2], vec![1, 1]);
2250 assert_eq!(vec![1; 1], vec![1]);
2251 assert_eq!(vec![1; 0], vec![]);
2253 // from_elem syntax (see RFC 832)
2254 let el = Box::new(1);
2256 assert_eq!(vec![el; n], vec![Box::new(1), Box::new(1), Box::new(1)]);
2260 fn test_vec_swap() {
2261 let mut a: Vec<isize> = vec![0, 1, 2, 3, 4, 5, 6];
2263 assert_eq!(a[2], 4);
2264 assert_eq!(a[4], 2);
2266 swap(&mut n, &mut a[0]);
2267 assert_eq!(a[0], 42);
2272 fn test_extend_from_within_spec() {
2276 impl Clone for CopyOnly {
2277 fn clone(&self) -> Self {
2278 panic!("extend_from_within must use specialization on copy");
2282 vec![CopyOnly, CopyOnly].extend_from_within(..);
2286 fn test_extend_from_within_clone() {
2287 let mut v = vec![String::from("sssss"), String::from("12334567890"), String::from("c")];
2288 v.extend_from_within(1..);
2290 assert_eq!(v, ["sssss", "12334567890", "c", "12334567890", "c"]);
2294 fn test_extend_from_within_complete_rande() {
2295 let mut v = vec![0, 1, 2, 3];
2296 v.extend_from_within(..);
2298 assert_eq!(v, [0, 1, 2, 3, 0, 1, 2, 3]);
2302 fn test_extend_from_within_empty_rande() {
2303 let mut v = vec![0, 1, 2, 3];
2304 v.extend_from_within(1..1);
2306 assert_eq!(v, [0, 1, 2, 3]);
2311 fn test_extend_from_within_out_of_rande() {
2312 let mut v = vec![0, 1];
2313 v.extend_from_within(..3);
2317 fn test_extend_from_within_zst() {
2318 let mut v = vec![(); 8];
2319 v.extend_from_within(3..7);
2321 assert_eq!(v, [(); 12]);
2325 fn test_extend_from_within_empty_vec() {
2326 let mut v = Vec::<i32>::new();
2327 v.extend_from_within(..);
2333 fn test_extend_from_within() {
2334 let mut v = vec![String::from("a"), String::from("b"), String::from("c")];
2335 v.extend_from_within(1..=2);
2336 v.extend_from_within(..=1);
2338 assert_eq!(v, ["a", "b", "c", "b", "c", "a", "b"]);
2342 fn test_vec_dedup_by() {
2343 let mut vec: Vec<i32> = vec![1, -1, 2, 3, 1, -5, 5, -2, 2];
2345 vec.dedup_by(|a, b| a.abs() == b.abs());
2347 assert_eq!(vec, [1, 2, 3, 1, -5, -2]);
2351 fn test_vec_dedup_empty() {
2352 let mut vec: Vec<i32> = Vec::new();
2356 assert_eq!(vec, []);
2360 fn test_vec_dedup_one() {
2361 let mut vec = vec![12i32];
2365 assert_eq!(vec, [12]);
2369 fn test_vec_dedup_multiple_ident() {
2370 let mut vec = vec![12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11];
2374 assert_eq!(vec, [12, 11]);
2378 fn test_vec_dedup_partialeq() {
2380 struct Foo(i32, i32);
2382 impl PartialEq for Foo {
2383 fn eq(&self, other: &Foo) -> bool {
2388 let mut vec = vec![Foo(0, 1), Foo(0, 5), Foo(1, 7), Foo(1, 9)];
2391 assert_eq!(vec, [Foo(0, 1), Foo(1, 7)]);
2395 fn test_vec_dedup() {
2396 let mut vec: Vec<bool> = Vec::with_capacity(8);
2397 let mut template = vec.clone();
2399 for x in 0u8..255u8 {
2403 let iter = (0..8).map(move |bit| (x >> bit) & 1 == 1);
2405 template.extend_from_slice(&vec);
2407 let (dedup, _) = template.partition_dedup();
2410 assert_eq!(vec, dedup);
2415 fn test_vec_dedup_panicking() {
2418 drop_counter: &'a Cell<u32>,
2423 impl<'a> PartialEq for Panic<'a> {
2424 fn eq(&self, other: &Self) -> bool {
2425 self.value == other.value
2429 impl<'a> Drop for Panic<'a> {
2430 fn drop(&mut self) {
2431 self.drop_counter.set(self.drop_counter.get() + 1);
2432 if !std::thread::panicking() {
2433 assert!(self.index != 4);
2438 let drop_counter = &Cell::new(0);
2440 Panic { drop_counter, value: false, index: 0 },
2441 Panic { drop_counter, value: false, index: 5 },
2442 Panic { drop_counter, value: true, index: 6 },
2443 Panic { drop_counter, value: true, index: 7 },
2446 Panic { drop_counter, value: false, index: 0 },
2447 // these elements get deduplicated
2448 Panic { drop_counter, value: false, index: 1 },
2449 Panic { drop_counter, value: false, index: 2 },
2450 Panic { drop_counter, value: false, index: 3 },
2451 Panic { drop_counter, value: false, index: 4 },
2452 // here it panics while dropping the item with index==4
2453 Panic { drop_counter, value: false, index: 5 },
2454 Panic { drop_counter, value: true, index: 6 },
2455 Panic { drop_counter, value: true, index: 7 },
2458 let _ = catch_unwind(AssertUnwindSafe(|| vec.dedup())).unwrap_err();
2460 assert_eq!(drop_counter.get(), 4);
2462 let ok = vec.iter().zip(expected.iter()).all(|(x, y)| x.index == y.index);
2465 panic!("expected: {expected:?}\ngot: {vec:?}\n");
2469 // Regression test for issue #82533
2471 fn test_extend_from_within_panicing_clone() {
2473 drop_count: &'dc AtomicU32,
2477 impl Clone for Panic<'_> {
2478 fn clone(&self) -> Self {
2480 panic!("panic! at the clone");
2487 impl Drop for Panic<'_> {
2488 fn drop(&mut self) {
2489 self.drop_count.fetch_add(1, Ordering::SeqCst);
2493 let count = core::sync::atomic::AtomicU32::new(0);
2495 Panic { drop_count: &count, aaaaa: false },
2496 Panic { drop_count: &count, aaaaa: true },
2497 Panic { drop_count: &count, aaaaa: false },
2500 // This should clone&append one Panic{..} at the end, and then panic while
2501 // cloning second Panic{..}. This means that `Panic::drop` should be called
2502 // 4 times (3 for items already in vector, 1 for just appended).
2504 // Previously just appended item was leaked, making drop_count = 3, instead of 4.
2505 std::panic::catch_unwind(move || vec.extend_from_within(..)).unwrap_err();
2507 assert_eq!(count.load(Ordering::SeqCst), 4);
2511 #[should_panic = "vec len overflow"]
2512 fn test_into_flattened_size_overflow() {
2513 let v = vec![[(); usize::MAX]; 2];
2514 let _ = v.into_flattened();