1 use std::assert_matches::assert_matches;
4 use std::collections::TryReserveErrorKind::*;
6 use std::iter::InPlaceIterable;
7 use std::mem::{size_of, swap};
8 use std::ops::Bound::*;
9 use std::panic::{catch_unwind, AssertUnwindSafe};
11 use std::sync::atomic::{AtomicU32, Ordering};
12 use std::vec::{Drain, IntoIter};
14 struct DropCounter<'a> {
18 impl Drop for DropCounter<'_> {
25 fn test_small_vec_struct() {
26 assert_eq!(size_of::<Vec<u8>>(), size_of::<usize>() * 3);
30 fn test_double_drop() {
36 let (mut count_x, mut count_y) = (0, 0);
38 let mut tv = TwoVec { x: Vec::new(), y: Vec::new() };
39 tv.x.push(DropCounter { count: &mut count_x });
40 tv.y.push(DropCounter { count: &mut count_y });
42 // If Vec had a drop flag, here is where it would be zeroed.
43 // Instead, it should rely on its internal state to prevent
44 // doing anything significant when dropped multiple times.
47 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
50 assert_eq!(count_x, 1);
51 assert_eq!(count_y, 1);
56 let mut v = Vec::new();
57 assert_eq!(v.capacity(), 0);
60 assert!(v.capacity() >= 2);
66 assert!(v.capacity() >= 16);
68 assert!(v.capacity() >= 32);
73 assert!(v.capacity() >= 33)
77 fn test_zst_capacity() {
78 assert_eq!(Vec::<()>::new().capacity(), usize::MAX);
83 let v: Vec<isize> = vec![10, 20];
88 assert_eq!(v[x + 1], 20);
91 assert_eq!(v[x - 1], 10);
96 let vec1: Vec<isize> = vec![];
97 assert_eq!("[]", format!("{:?}", vec1));
99 let vec2 = vec![0, 1];
100 assert_eq!("[0, 1]", format!("{:?}", vec2));
102 let slice: &[isize] = &[4, 5];
103 assert_eq!("[4, 5]", format!("{:?}", slice));
112 assert_eq!(v, [1, 2]);
114 assert_eq!(v, [1, 2, 3]);
119 let mut v = Vec::new();
120 let mut w = Vec::new();
139 v.extend(w.clone()); // specializes to `append`
140 assert!(v.iter().eq(w.iter().chain(w.iter())));
143 #[derive(PartialEq, Debug)]
146 let mut a = Vec::new();
147 let b = vec![Foo, Foo];
150 assert_eq!(a, &[Foo, Foo]);
155 let mut x = Vec::new();
156 let y = vec![DropCounter { count: &mut count_x }];
159 assert_eq!(count_x, 1);
163 fn test_extend_from_slice() {
164 let a: Vec<isize> = vec![1, 2, 3, 4, 5];
165 let b: Vec<isize> = vec![6, 7, 8, 9, 0];
167 let mut v: Vec<isize> = a;
169 v.extend_from_slice(&b);
171 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]);
175 fn test_extend_ref() {
176 let mut v = vec![1, 2];
177 v.extend(&[3, 4, 5]);
179 assert_eq!(v.len(), 5);
180 assert_eq!(v, [1, 2, 3, 4, 5]);
185 assert_eq!(v.len(), 7);
186 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
190 fn test_slice_from_ref() {
191 let values = vec![1, 2, 3, 4, 5];
192 let slice = &values[1..3];
194 assert_eq!(slice, [2, 3]);
198 fn test_slice_from_mut() {
199 let mut values = vec![1, 2, 3, 4, 5];
201 let slice = &mut values[2..];
202 assert!(slice == [3, 4, 5]);
208 assert!(values == [1, 2, 5, 6, 7]);
212 fn test_slice_to_mut() {
213 let mut values = vec![1, 2, 3, 4, 5];
215 let slice = &mut values[..2];
216 assert!(slice == [1, 2]);
222 assert!(values == [2, 3, 3, 4, 5]);
226 fn test_split_at_mut() {
227 let mut values = vec![1, 2, 3, 4, 5];
229 let (left, right) = values.split_at_mut(2);
231 let left: &[_] = left;
232 assert!(&left[..left.len()] == &[1, 2]);
239 let right: &[_] = right;
240 assert!(&right[..right.len()] == &[3, 4, 5]);
247 assert_eq!(values, [2, 3, 5, 6, 7]);
252 let v: Vec<i32> = vec![];
253 let w = vec![1, 2, 3];
255 assert_eq!(v, v.clone());
259 // they should be disjoint in memory.
260 assert!(w.as_ptr() != z.as_ptr())
264 fn test_clone_from() {
266 let three: Vec<Box<_>> = vec![box 1, box 2, box 3];
267 let two: Vec<Box<_>> = vec![box 4, box 5];
269 v.clone_from(&three);
270 assert_eq!(v, three);
273 v.clone_from(&three);
274 assert_eq!(v, three);
281 v.clone_from(&three);
287 let mut vec = vec![1, 2, 3, 4];
288 vec.retain(|&x| x % 2 == 0);
289 assert_eq!(vec, [2, 4]);
293 fn test_retain_pred_panic_with_hole() {
294 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
295 catch_unwind(AssertUnwindSafe(|| {
296 let mut v = v.clone();
297 v.retain(|r| match **r {
305 // Everything is dropped when predicate panicked.
306 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
310 fn test_retain_pred_panic_no_hole() {
311 let v = (0..5).map(Rc::new).collect::<Vec<_>>();
312 catch_unwind(AssertUnwindSafe(|| {
313 let mut v = v.clone();
314 v.retain(|r| match **r {
320 // Everything is dropped when predicate panicked.
321 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
325 fn test_retain_drop_panic() {
326 struct Wrap(Rc<i32>);
336 let v = (0..5).map(|x| Rc::new(x)).collect::<Vec<_>>();
337 catch_unwind(AssertUnwindSafe(|| {
338 let mut v = v.iter().map(|r| Wrap(r.clone())).collect::<Vec<_>>();
339 v.retain(|w| match *w.0 {
343 3 => false, // Drop panic.
348 // Other elements are dropped when `drop` of one element panicked.
349 // The panicked wrapper also has its Rc dropped.
350 assert!(v.iter().all(|r| Rc::strong_count(r) == 1));
355 fn case(a: Vec<i32>, b: Vec<i32>) {
360 case(vec![], vec![]);
361 case(vec![1], vec![1]);
362 case(vec![1, 1], vec![1]);
363 case(vec![1, 2, 3], vec![1, 2, 3]);
364 case(vec![1, 1, 2, 3], vec![1, 2, 3]);
365 case(vec![1, 2, 2, 3], vec![1, 2, 3]);
366 case(vec![1, 2, 3, 3], vec![1, 2, 3]);
367 case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
371 fn test_dedup_by_key() {
372 fn case(a: Vec<i32>, b: Vec<i32>) {
374 v.dedup_by_key(|i| *i / 10);
377 case(vec![], vec![]);
378 case(vec![10], vec![10]);
379 case(vec![10, 11], vec![10]);
380 case(vec![10, 20, 30], vec![10, 20, 30]);
381 case(vec![10, 11, 20, 30], vec![10, 20, 30]);
382 case(vec![10, 20, 21, 30], vec![10, 20, 30]);
383 case(vec![10, 20, 30, 31], vec![10, 20, 30]);
384 case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
389 let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
390 vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
392 assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
394 let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
395 vec.dedup_by(|a, b| {
402 assert_eq!(vec, [("foo", 3), ("bar", 12)]);
406 fn test_dedup_unique() {
407 let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
409 let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
411 let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
413 // If the boxed pointers were leaked or otherwise misused, valgrind
414 // and/or rt should raise errors.
418 fn zero_sized_values() {
419 let mut v = Vec::new();
420 assert_eq!(v.len(), 0);
422 assert_eq!(v.len(), 1);
424 assert_eq!(v.len(), 2);
425 assert_eq!(v.pop(), Some(()));
426 assert_eq!(v.pop(), Some(()));
427 assert_eq!(v.pop(), None);
429 assert_eq!(v.iter().count(), 0);
431 assert_eq!(v.iter().count(), 1);
433 assert_eq!(v.iter().count(), 2);
437 assert_eq!(v.iter_mut().count(), 2);
439 assert_eq!(v.iter_mut().count(), 3);
441 assert_eq!(v.iter_mut().count(), 4);
443 for &mut () in &mut v {}
447 assert_eq!(v.iter_mut().count(), 0);
451 fn test_partition() {
452 assert_eq!(vec![].into_iter().partition(|x: &i32| *x < 3), (vec![], vec![]));
453 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 4), (vec![1, 2, 3], vec![]));
454 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 2), (vec![1], vec![2, 3]));
455 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 0), (vec![], vec![1, 2, 3]));
459 fn test_zip_unzip() {
460 let z1 = vec![(1, 4), (2, 5), (3, 6)];
462 let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
464 assert_eq!((1, 4), (left[0], right[0]));
465 assert_eq!((2, 5), (left[1], right[1]));
466 assert_eq!((3, 6), (left[2], right[2]));
471 let x: &[isize] = &[1, 2, 3, 4, 5];
472 let cmp: &[isize] = &[1, 2, 3, 4, 5];
473 assert_eq!(&x[..], cmp);
474 let cmp: &[isize] = &[3, 4, 5];
475 assert_eq!(&x[2..], cmp);
476 let cmp: &[isize] = &[1, 2, 3];
477 assert_eq!(&x[..3], cmp);
478 let cmp: &[isize] = &[2, 3, 4];
479 assert_eq!(&x[1..4], cmp);
481 let x: Vec<isize> = vec![1, 2, 3, 4, 5];
482 let cmp: &[isize] = &[1, 2, 3, 4, 5];
483 assert_eq!(&x[..], cmp);
484 let cmp: &[isize] = &[3, 4, 5];
485 assert_eq!(&x[2..], cmp);
486 let cmp: &[isize] = &[1, 2, 3];
487 assert_eq!(&x[..3], cmp);
488 let cmp: &[isize] = &[2, 3, 4];
489 assert_eq!(&x[1..4], cmp);
493 fn test_vec_truncate_drop() {
494 static mut DROPS: u32 = 0;
504 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
505 assert_eq!(unsafe { DROPS }, 0);
507 assert_eq!(unsafe { DROPS }, 2);
509 assert_eq!(unsafe { DROPS }, 5);
514 fn test_vec_truncate_fail() {
516 impl Drop for BadElem {
518 let BadElem(ref mut x) = *self;
520 panic!("BadElem panic: 0xbadbeef")
525 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
531 let vec = vec![1, 2, 3];
532 assert!(vec[1] == 2);
537 fn test_index_out_of_bounds() {
538 let vec = vec![1, 2, 3];
544 fn test_slice_out_of_bounds_1() {
545 let x = vec![1, 2, 3, 4, 5];
551 fn test_slice_out_of_bounds_2() {
552 let x = vec![1, 2, 3, 4, 5];
558 fn test_slice_out_of_bounds_3() {
559 let x = vec![1, 2, 3, 4, 5];
565 fn test_slice_out_of_bounds_4() {
566 let x = vec![1, 2, 3, 4, 5];
572 fn test_slice_out_of_bounds_5() {
573 let x = vec![1, 2, 3, 4, 5];
579 fn test_swap_remove_empty() {
580 let mut vec = Vec::<i32>::new();
585 fn test_move_items() {
586 let vec = vec![1, 2, 3];
587 let mut vec2 = vec![];
591 assert_eq!(vec2, [1, 2, 3]);
595 fn test_move_items_reverse() {
596 let vec = vec![1, 2, 3];
597 let mut vec2 = vec![];
598 for i in vec.into_iter().rev() {
601 assert_eq!(vec2, [3, 2, 1]);
605 fn test_move_items_zero_sized() {
606 let vec = vec![(), (), ()];
607 let mut vec2 = vec![];
611 assert_eq!(vec2, [(), (), ()]);
615 fn test_drain_empty_vec() {
616 let mut vec: Vec<i32> = vec![];
617 let mut vec2: Vec<i32> = vec![];
618 for i in vec.drain(..) {
621 assert!(vec.is_empty());
622 assert!(vec2.is_empty());
626 fn test_drain_items() {
627 let mut vec = vec![1, 2, 3];
628 let mut vec2 = vec![];
629 for i in vec.drain(..) {
633 assert_eq!(vec2, [1, 2, 3]);
637 fn test_drain_items_reverse() {
638 let mut vec = vec![1, 2, 3];
639 let mut vec2 = vec![];
640 for i in vec.drain(..).rev() {
644 assert_eq!(vec2, [3, 2, 1]);
648 fn test_drain_items_zero_sized() {
649 let mut vec = vec![(), (), ()];
650 let mut vec2 = vec![];
651 for i in vec.drain(..) {
655 assert_eq!(vec2, [(), (), ()]);
660 fn test_drain_out_of_bounds() {
661 let mut v = vec![1, 2, 3, 4, 5];
666 fn test_drain_range() {
667 let mut v = vec![1, 2, 3, 4, 5];
668 for _ in v.drain(4..) {}
669 assert_eq!(v, &[1, 2, 3, 4]);
671 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
672 for _ in v.drain(1..4) {}
673 assert_eq!(v, &[1.to_string(), 5.to_string()]);
675 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
676 for _ in v.drain(1..4).rev() {}
677 assert_eq!(v, &[1.to_string(), 5.to_string()]);
679 let mut v: Vec<_> = vec![(); 5];
680 for _ in v.drain(1..4).rev() {}
681 assert_eq!(v, &[(), ()]);
685 fn test_drain_inclusive_range() {
686 let mut v = vec!['a', 'b', 'c', 'd', 'e'];
687 for _ in v.drain(1..=3) {}
688 assert_eq!(v, &['a', 'e']);
690 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
691 for _ in v.drain(1..=5) {}
692 assert_eq!(v, &["0".to_string()]);
694 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
695 for _ in v.drain(0..=5) {}
696 assert_eq!(v, Vec::<String>::new());
698 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
699 for _ in v.drain(0..=3) {}
700 assert_eq!(v, &["4".to_string(), "5".to_string()]);
702 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
703 for _ in v.drain(..=0) {}
704 assert_eq!(v, &["1".to_string()]);
708 fn test_drain_max_vec_size() {
709 let mut v = Vec::<()>::with_capacity(usize::MAX);
711 v.set_len(usize::MAX);
713 for _ in v.drain(usize::MAX - 1..) {}
714 assert_eq!(v.len(), usize::MAX - 1);
716 let mut v = Vec::<()>::with_capacity(usize::MAX);
718 v.set_len(usize::MAX);
720 for _ in v.drain(usize::MAX - 1..=usize::MAX - 1) {}
721 assert_eq!(v.len(), usize::MAX - 1);
726 fn test_drain_index_overflow() {
727 let mut v = Vec::<()>::with_capacity(usize::MAX);
729 v.set_len(usize::MAX);
731 v.drain(0..=usize::MAX);
736 fn test_drain_inclusive_out_of_bounds() {
737 let mut v = vec![1, 2, 3, 4, 5];
743 fn test_drain_start_overflow() {
744 let mut v = vec![1, 2, 3];
745 v.drain((Excluded(usize::MAX), Included(0)));
750 fn test_drain_end_overflow() {
751 let mut v = vec![1, 2, 3];
752 v.drain((Included(0), Included(usize::MAX)));
756 fn test_drain_leak() {
757 static mut DROPS: i32 = 0;
759 #[derive(Debug, PartialEq)]
769 panic!("panic in `drop`");
784 catch_unwind(AssertUnwindSafe(|| {
789 assert_eq!(unsafe { DROPS }, 4);
790 assert_eq!(v, vec![D(0, false), D(1, false), D(6, false),]);
795 let mut v = vec![1, 2, 3, 4, 5];
796 let a = [10, 11, 12];
798 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
799 v.splice(1..3, Some(20));
800 assert_eq!(v, &[1, 20, 11, 12, 5]);
804 fn test_splice_inclusive_range() {
805 let mut v = vec![1, 2, 3, 4, 5];
806 let a = [10, 11, 12];
807 let t1: Vec<_> = v.splice(2..=3, a).collect();
808 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
809 assert_eq!(t1, &[3, 4]);
810 let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
811 assert_eq!(v, &[1, 20, 11, 12, 5]);
812 assert_eq!(t2, &[2, 10]);
817 fn test_splice_out_of_bounds() {
818 let mut v = vec![1, 2, 3, 4, 5];
819 let a = [10, 11, 12];
825 fn test_splice_inclusive_out_of_bounds() {
826 let mut v = vec![1, 2, 3, 4, 5];
827 let a = [10, 11, 12];
832 fn test_splice_items_zero_sized() {
833 let mut vec = vec![(), (), ()];
835 let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
836 assert_eq!(vec, &[(), ()]);
837 assert_eq!(t, &[()]);
841 fn test_splice_unbounded() {
842 let mut vec = vec![1, 2, 3, 4, 5];
843 let t: Vec<_> = vec.splice(.., None).collect();
844 assert_eq!(vec, &[]);
845 assert_eq!(t, &[1, 2, 3, 4, 5]);
849 fn test_splice_forget() {
850 let mut v = vec![1, 2, 3, 4, 5];
851 let a = [10, 11, 12];
852 std::mem::forget(v.splice(2..4, a));
853 assert_eq!(v, &[1, 2]);
857 fn test_into_boxed_slice() {
858 let xs = vec![1, 2, 3];
859 let ys = xs.into_boxed_slice();
860 assert_eq!(&*ys, [1, 2, 3]);
865 let mut vec = vec![1, 2, 3];
866 let mut vec2 = vec![4, 5, 6];
867 vec.append(&mut vec2);
868 assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
869 assert_eq!(vec2, []);
873 fn test_split_off() {
874 let mut vec = vec![1, 2, 3, 4, 5, 6];
875 let orig_capacity = vec.capacity();
876 let vec2 = vec.split_off(4);
877 assert_eq!(vec, [1, 2, 3, 4]);
878 assert_eq!(vec2, [5, 6]);
879 assert_eq!(vec.capacity(), orig_capacity);
883 fn test_split_off_take_all() {
884 let mut vec = vec![1, 2, 3, 4, 5, 6];
885 let orig_ptr = vec.as_ptr();
886 let orig_capacity = vec.capacity();
887 let vec2 = vec.split_off(0);
889 assert_eq!(vec2, [1, 2, 3, 4, 5, 6]);
890 assert_eq!(vec.capacity(), orig_capacity);
891 assert_eq!(vec2.as_ptr(), orig_ptr);
895 fn test_into_iter_as_slice() {
896 let vec = vec!['a', 'b', 'c'];
897 let mut into_iter = vec.into_iter();
898 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
899 let _ = into_iter.next().unwrap();
900 assert_eq!(into_iter.as_slice(), &['b', 'c']);
901 let _ = into_iter.next().unwrap();
902 let _ = into_iter.next().unwrap();
903 assert_eq!(into_iter.as_slice(), &[]);
907 fn test_into_iter_as_mut_slice() {
908 let vec = vec!['a', 'b', 'c'];
909 let mut into_iter = vec.into_iter();
910 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
911 into_iter.as_mut_slice()[0] = 'x';
912 into_iter.as_mut_slice()[1] = 'y';
913 assert_eq!(into_iter.next().unwrap(), 'x');
914 assert_eq!(into_iter.as_slice(), &['y', 'c']);
918 fn test_into_iter_debug() {
919 let vec = vec!['a', 'b', 'c'];
920 let into_iter = vec.into_iter();
921 let debug = format!("{:?}", into_iter);
922 assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
926 fn test_into_iter_count() {
927 assert_eq!(vec![1, 2, 3].into_iter().count(), 3);
931 fn test_into_iter_clone() {
932 fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
933 let v: Vec<i32> = it.collect();
934 assert_eq!(&v[..], slice);
936 let mut it = vec![1, 2, 3].into_iter();
937 iter_equal(it.clone(), &[1, 2, 3]);
938 assert_eq!(it.next(), Some(1));
939 let mut it = it.rev();
940 iter_equal(it.clone(), &[3, 2]);
941 assert_eq!(it.next(), Some(3));
942 iter_equal(it.clone(), &[2]);
943 assert_eq!(it.next(), Some(2));
944 iter_equal(it.clone(), &[]);
945 assert_eq!(it.next(), None);
949 fn test_into_iter_leak() {
950 static mut DROPS: i32 = 0;
961 panic!("panic in `drop`");
966 let v = vec![D(false), D(true), D(false)];
968 catch_unwind(move || drop(v.into_iter())).ok();
970 assert_eq!(unsafe { DROPS }, 3);
974 fn test_into_iter_advance_by() {
975 let mut i = vec![1, 2, 3, 4, 5].into_iter();
976 i.advance_by(0).unwrap();
977 i.advance_back_by(0).unwrap();
978 assert_eq!(i.as_slice(), [1, 2, 3, 4, 5]);
980 i.advance_by(1).unwrap();
981 i.advance_back_by(1).unwrap();
982 assert_eq!(i.as_slice(), [2, 3, 4]);
984 assert_eq!(i.advance_back_by(usize::MAX), Err(3));
986 assert_eq!(i.advance_by(usize::MAX), Err(0));
988 i.advance_by(0).unwrap();
989 i.advance_back_by(0).unwrap();
991 assert_eq!(i.len(), 0);
995 fn test_from_iter_specialization() {
996 let src: Vec<usize> = vec![0usize; 1];
997 let srcptr = src.as_ptr();
998 let sink = src.into_iter().collect::<Vec<_>>();
999 let sinkptr = sink.as_ptr();
1000 assert_eq!(srcptr, sinkptr);
1004 fn test_from_iter_partially_drained_in_place_specialization() {
1005 let src: Vec<usize> = vec![0usize; 10];
1006 let srcptr = src.as_ptr();
1007 let mut iter = src.into_iter();
1010 let sink = iter.collect::<Vec<_>>();
1011 let sinkptr = sink.as_ptr();
1012 assert_eq!(srcptr, sinkptr);
1016 fn test_from_iter_specialization_with_iterator_adapters() {
1017 fn assert_in_place_trait<T: InPlaceIterable>(_: &T) {}
1018 let src: Vec<usize> = vec![0usize; 256];
1019 let srcptr = src.as_ptr();
1024 .zip(std::iter::repeat(1usize))
1025 .map(|(a, b)| a + b)
1026 .map_while(Option::Some)
1028 .map(|e| if e != usize::MAX { Ok(std::num::NonZeroUsize::new(e)) } else { Err(()) });
1029 assert_in_place_trait(&iter);
1030 let sink = iter.collect::<Result<Vec<_>, _>>().unwrap();
1031 let sinkptr = sink.as_ptr();
1032 assert_eq!(srcptr, sinkptr as *const usize);
1036 fn test_from_iter_specialization_head_tail_drop() {
1037 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1038 let src: Vec<_> = drop_count.iter().cloned().collect();
1039 let srcptr = src.as_ptr();
1040 let iter = src.into_iter();
1041 let sink: Vec<_> = iter.skip(1).take(1).collect();
1042 let sinkptr = sink.as_ptr();
1043 assert_eq!(srcptr, sinkptr, "specialization was applied");
1044 assert_eq!(Rc::strong_count(&drop_count[0]), 1, "front was dropped");
1045 assert_eq!(Rc::strong_count(&drop_count[1]), 2, "one element was collected");
1046 assert_eq!(Rc::strong_count(&drop_count[2]), 1, "tail was dropped");
1047 assert_eq!(sink.len(), 1);
1051 fn test_from_iter_specialization_panic_during_iteration_drops() {
1052 let drop_count: Vec<_> = (0..=2).map(|_| Rc::new(())).collect();
1053 let src: Vec<_> = drop_count.iter().cloned().collect();
1054 let iter = src.into_iter();
1056 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1059 .filter_map(|(i, e)| {
1061 std::panic!("aborting iteration");
1065 .collect::<Vec<_>>();
1069 drop_count.iter().map(Rc::strong_count).all(|count| count == 1),
1070 "all items were dropped once"
1075 fn test_from_iter_specialization_panic_during_drop_leaks() {
1076 static mut DROP_COUNTER: usize = 0;
1080 DroppedTwice(Box<i32>),
1084 impl Drop for Droppable {
1085 fn drop(&mut self) {
1087 Droppable::DroppedTwice(_) => {
1091 println!("Dropping!")
1093 Droppable::PanicOnDrop => {
1094 if !std::thread::panicking() {
1102 let mut to_free: *mut Droppable = core::ptr::null_mut();
1105 let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
1106 let mut v = vec![Droppable::DroppedTwice(Box::new(123)), Droppable::PanicOnDrop];
1107 to_free = v.as_mut_ptr();
1109 let _ = v.into_iter().take(0).collect::<Vec<_>>();
1112 assert_eq!(unsafe { DROP_COUNTER }, 1);
1113 // clean up the leak to keep miri happy
1115 drop(Vec::from_raw_parts(to_free, 0, cap));
1119 // regression test for issue #85322. Peekable previously implemented InPlaceIterable,
1120 // but due to an interaction with IntoIter's current Clone implementation it failed to uphold
1123 fn test_collect_after_iterator_clone() {
1125 let mut i = v.into_iter().map(|i| i + 1).peekable();
1127 let v = i.clone().collect::<Vec<_>>();
1128 assert_eq!(v, [1, 1, 1, 1, 1]);
1129 assert!(v.len() <= v.capacity());
1132 fn test_cow_from() {
1133 let borrowed: &[_] = &["borrowed", "(slice)"];
1134 let owned = vec!["owned", "(vec)"];
1135 match (Cow::from(owned.clone()), Cow::from(borrowed)) {
1136 (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
1137 _ => panic!("invalid `Cow::from`"),
1142 fn test_from_cow() {
1143 let borrowed: &[_] = &["borrowed", "(slice)"];
1144 let owned = vec!["owned", "(vec)"];
1145 assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
1146 assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
1150 fn assert_covariance() {
1151 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1154 fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
1160 fn from_into_inner() {
1161 let vec = vec![1, 2, 3];
1162 let ptr = vec.as_ptr();
1163 let vec = vec.into_iter().collect::<Vec<_>>();
1164 assert_eq!(vec, [1, 2, 3]);
1165 assert_eq!(vec.as_ptr(), ptr);
1167 let ptr = &vec[1] as *const _;
1168 let mut it = vec.into_iter();
1170 let vec = it.collect::<Vec<_>>();
1171 assert_eq!(vec, [2, 3]);
1172 assert!(ptr != vec.as_ptr());
1176 fn overaligned_allocations() {
1179 let mut v = vec![Foo(273)];
1180 for i in 0..0x1000 {
1182 assert!(v[0].0 == 273);
1183 assert!(v.as_ptr() as usize & 0xff == 0);
1185 assert!(v[0].0 == 273);
1186 assert!(v.as_ptr() as usize & 0xff == 0);
1191 fn drain_filter_empty() {
1192 let mut vec: Vec<i32> = vec![];
1195 let mut iter = vec.drain_filter(|_| true);
1196 assert_eq!(iter.size_hint(), (0, Some(0)));
1197 assert_eq!(iter.next(), None);
1198 assert_eq!(iter.size_hint(), (0, Some(0)));
1199 assert_eq!(iter.next(), None);
1200 assert_eq!(iter.size_hint(), (0, Some(0)));
1202 assert_eq!(vec.len(), 0);
1203 assert_eq!(vec, vec![]);
1207 fn drain_filter_zst() {
1208 let mut vec = vec![(), (), (), (), ()];
1209 let initial_len = vec.len();
1212 let mut iter = vec.drain_filter(|_| true);
1213 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1214 while let Some(_) = iter.next() {
1216 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1218 assert_eq!(iter.size_hint(), (0, Some(0)));
1219 assert_eq!(iter.next(), None);
1220 assert_eq!(iter.size_hint(), (0, Some(0)));
1223 assert_eq!(count, initial_len);
1224 assert_eq!(vec.len(), 0);
1225 assert_eq!(vec, vec![]);
1229 fn drain_filter_false() {
1230 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1232 let initial_len = vec.len();
1235 let mut iter = vec.drain_filter(|_| false);
1236 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1237 for _ in iter.by_ref() {
1240 assert_eq!(iter.size_hint(), (0, Some(0)));
1241 assert_eq!(iter.next(), None);
1242 assert_eq!(iter.size_hint(), (0, Some(0)));
1245 assert_eq!(count, 0);
1246 assert_eq!(vec.len(), initial_len);
1247 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1251 fn drain_filter_true() {
1252 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1254 let initial_len = vec.len();
1257 let mut iter = vec.drain_filter(|_| true);
1258 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
1259 while let Some(_) = iter.next() {
1261 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
1263 assert_eq!(iter.size_hint(), (0, Some(0)));
1264 assert_eq!(iter.next(), None);
1265 assert_eq!(iter.size_hint(), (0, Some(0)));
1268 assert_eq!(count, initial_len);
1269 assert_eq!(vec.len(), 0);
1270 assert_eq!(vec, vec![]);
1274 fn drain_filter_complex() {
1276 // [+xxx++++++xxxxx++++x+x++]
1278 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
1282 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1283 assert_eq!(removed.len(), 10);
1284 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1286 assert_eq!(vec.len(), 14);
1287 assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1291 // [xxx++++++xxxxx++++x+x++]
1293 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
1296 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1297 assert_eq!(removed.len(), 10);
1298 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1300 assert_eq!(vec.len(), 13);
1301 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
1305 // [xxx++++++xxxxx++++x+x]
1307 vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36];
1309 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1310 assert_eq!(removed.len(), 10);
1311 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
1313 assert_eq!(vec.len(), 11);
1314 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
1318 // [xxxxxxxxxx+++++++++++]
1319 let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
1321 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1322 assert_eq!(removed.len(), 10);
1323 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1325 assert_eq!(vec.len(), 10);
1326 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1330 // [+++++++++++xxxxxxxxxx]
1331 let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
1333 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
1334 assert_eq!(removed.len(), 10);
1335 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
1337 assert_eq!(vec.len(), 10);
1338 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1342 // FIXME: re-enable emscripten once it can unwind again
1344 #[cfg(not(target_os = "emscripten"))]
1345 fn drain_filter_consumed_panic() {
1347 use std::sync::Mutex;
1351 drop_counts: Rc<Mutex<Vec<usize>>>,
1354 impl Drop for Check {
1355 fn drop(&mut self) {
1356 self.drop_counts.lock().unwrap()[self.index] += 1;
1357 println!("drop: {}", self.index);
1361 let check_count = 10;
1362 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1363 let mut data: Vec<Check> = (0..check_count)
1364 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1367 let _ = std::panic::catch_unwind(move || {
1368 let filter = |c: &mut Check| {
1370 panic!("panic at index: {}", c.index);
1372 // Verify that if the filter could panic again on another element
1373 // that it would not cause a double panic and all elements of the
1374 // vec would still be dropped exactly once.
1376 panic!("panic at index: {}", c.index);
1380 let drain = data.drain_filter(filter);
1382 // NOTE: The DrainFilter is explicitly consumed
1383 drain.for_each(drop);
1386 let drop_counts = drop_counts.lock().unwrap();
1387 assert_eq!(check_count, drop_counts.len());
1389 for (index, count) in drop_counts.iter().cloned().enumerate() {
1390 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1394 // FIXME: Re-enable emscripten once it can catch panics
1396 #[cfg(not(target_os = "emscripten"))]
1397 fn drain_filter_unconsumed_panic() {
1399 use std::sync::Mutex;
1403 drop_counts: Rc<Mutex<Vec<usize>>>,
1406 impl Drop for Check {
1407 fn drop(&mut self) {
1408 self.drop_counts.lock().unwrap()[self.index] += 1;
1409 println!("drop: {}", self.index);
1413 let check_count = 10;
1414 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1415 let mut data: Vec<Check> = (0..check_count)
1416 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1419 let _ = std::panic::catch_unwind(move || {
1420 let filter = |c: &mut Check| {
1422 panic!("panic at index: {}", c.index);
1424 // Verify that if the filter could panic again on another element
1425 // that it would not cause a double panic and all elements of the
1426 // vec would still be dropped exactly once.
1428 panic!("panic at index: {}", c.index);
1432 let _drain = data.drain_filter(filter);
1434 // NOTE: The DrainFilter is dropped without being consumed
1437 let drop_counts = drop_counts.lock().unwrap();
1438 assert_eq!(check_count, drop_counts.len());
1440 for (index, count) in drop_counts.iter().cloned().enumerate() {
1441 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1446 fn drain_filter_unconsumed() {
1447 let mut vec = vec![1, 2, 3, 4];
1448 let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1450 assert_eq!(vec, [2, 4]);
1454 fn test_reserve_exact() {
1455 // This is all the same as test_reserve
1457 let mut v = Vec::new();
1458 assert_eq!(v.capacity(), 0);
1461 assert!(v.capacity() >= 2);
1467 assert!(v.capacity() >= 16);
1468 v.reserve_exact(16);
1469 assert!(v.capacity() >= 32);
1473 v.reserve_exact(16);
1474 assert!(v.capacity() >= 33)
1478 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1479 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1480 fn test_try_reserve() {
1481 // These are the interesting cases:
1482 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1483 // * > isize::MAX should always fail
1484 // * On 16/32-bit should CapacityOverflow
1485 // * On 64-bit should OOM
1486 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1487 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1489 const MAX_CAP: usize = isize::MAX as usize;
1490 const MAX_USIZE: usize = usize::MAX;
1492 // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1493 // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1494 // Any platform that succeeds for these requests is technically broken with
1495 // ptr::offset because LLVM is the worst.
1496 let guards_against_isize = usize::BITS < 64;
1499 // Note: basic stuff is checked by test_reserve
1500 let mut empty_bytes: Vec<u8> = Vec::new();
1502 // Check isize::MAX doesn't count as an overflow
1503 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1504 panic!("isize::MAX shouldn't trigger an overflow!");
1506 // Play it again, frank! (just to be sure)
1507 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1508 panic!("isize::MAX shouldn't trigger an overflow!");
1511 if guards_against_isize {
1512 // Check isize::MAX + 1 does count as overflow
1514 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1515 Err(CapacityOverflow),
1516 "isize::MAX + 1 should trigger an overflow!"
1519 // Check usize::MAX does count as overflow
1521 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1522 Err(CapacityOverflow),
1523 "usize::MAX should trigger an overflow!"
1526 // Check isize::MAX + 1 is an OOM
1528 empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1529 Err(AllocError { .. }),
1530 "isize::MAX + 1 should trigger an OOM!"
1533 // Check usize::MAX is an OOM
1535 empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1536 Err(AllocError { .. }),
1537 "usize::MAX should trigger an OOM!"
1543 // Same basic idea, but with non-zero len
1544 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1546 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1547 panic!("isize::MAX shouldn't trigger an overflow!");
1549 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1550 panic!("isize::MAX shouldn't trigger an overflow!");
1552 if guards_against_isize {
1554 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1555 Err(CapacityOverflow),
1556 "isize::MAX + 1 should trigger an overflow!"
1560 ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1561 Err(AllocError { .. }),
1562 "isize::MAX + 1 should trigger an OOM!"
1565 // Should always overflow in the add-to-len
1567 ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1568 Err(CapacityOverflow),
1569 "usize::MAX should trigger an overflow!"
1574 // Same basic idea, but with interesting type size
1575 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1577 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1579 panic!("isize::MAX shouldn't trigger an overflow!");
1581 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1583 panic!("isize::MAX shouldn't trigger an overflow!");
1585 if guards_against_isize {
1587 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1588 Err(CapacityOverflow),
1589 "isize::MAX + 1 should trigger an overflow!"
1593 ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1594 Err(AllocError { .. }),
1595 "isize::MAX + 1 should trigger an OOM!"
1598 // Should fail in the mul-by-size
1600 ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1601 Err(CapacityOverflow),
1602 "usize::MAX should trigger an overflow!"
1608 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1609 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1610 fn test_try_reserve_exact() {
1611 // This is exactly the same as test_try_reserve with the method changed.
1612 // See that test for comments.
1614 const MAX_CAP: usize = isize::MAX as usize;
1615 const MAX_USIZE: usize = usize::MAX;
1617 let guards_against_isize = size_of::<usize>() < 8;
1620 let mut empty_bytes: Vec<u8> = Vec::new();
1622 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1624 panic!("isize::MAX shouldn't trigger an overflow!");
1626 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1628 panic!("isize::MAX shouldn't trigger an overflow!");
1631 if guards_against_isize {
1633 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1634 Err(CapacityOverflow),
1635 "isize::MAX + 1 should trigger an overflow!"
1639 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1640 Err(CapacityOverflow),
1641 "usize::MAX should trigger an overflow!"
1645 empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1646 Err(AllocError { .. }),
1647 "isize::MAX + 1 should trigger an OOM!"
1651 empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1652 Err(AllocError { .. }),
1653 "usize::MAX should trigger an OOM!"
1659 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1661 if let Err(CapacityOverflow) =
1662 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1664 panic!("isize::MAX shouldn't trigger an overflow!");
1666 if let Err(CapacityOverflow) =
1667 ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1669 panic!("isize::MAX shouldn't trigger an overflow!");
1671 if guards_against_isize {
1673 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1674 Err(CapacityOverflow),
1675 "isize::MAX + 1 should trigger an overflow!"
1679 ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1680 Err(AllocError { .. }),
1681 "isize::MAX + 1 should trigger an OOM!"
1685 ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1686 Err(CapacityOverflow),
1687 "usize::MAX should trigger an overflow!"
1692 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1694 if let Err(CapacityOverflow) =
1695 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1697 panic!("isize::MAX shouldn't trigger an overflow!");
1699 if let Err(CapacityOverflow) =
1700 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1702 panic!("isize::MAX shouldn't trigger an overflow!");
1704 if guards_against_isize {
1706 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1707 Err(CapacityOverflow),
1708 "isize::MAX + 1 should trigger an overflow!"
1712 ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1713 Err(AllocError { .. }),
1714 "isize::MAX + 1 should trigger an OOM!"
1718 ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1719 Err(CapacityOverflow),
1720 "usize::MAX should trigger an overflow!"
1726 fn test_stable_pointers() {
1727 /// Pull an element from the iterator, then drop it.
1728 /// Useful to cover both the `next` and `drop` paths of an iterator.
1729 fn next_then_drop<I: Iterator>(mut i: I) {
1734 // Test that, if we reserved enough space, adding and removing elements does not
1735 // invalidate references into the vector (such as `v0`). This test also
1736 // runs in Miri, which would detect such problems.
1737 // Note that this test does *not* constitute a stable guarantee that all these functions do not
1738 // reallocate! Only what is explicitly documented at
1739 // <https://doc.rust-lang.org/nightly/std/vec/struct.Vec.html#guarantees> is stably guaranteed.
1740 let mut v = Vec::with_capacity(128);
1743 // Laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1745 let v0 = unsafe { &mut *(v0 as *mut _) };
1746 // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1748 // Pushing/inserting and popping/removing
1752 assert_eq!(*v0, 13);
1755 assert_eq!(*v0, 13);
1758 assert_eq!(v.len(), 2);
1759 v.swap_remove(1); // swap_remove the last element
1760 assert_eq!(*v0, 13);
1763 v.append(&mut vec![27, 19]);
1764 assert_eq!(*v0, 13);
1767 v.extend_from_slice(&[1, 2]);
1768 v.extend(&[1, 2]); // `slice::Iter` (with `T: Copy`) specialization
1769 v.extend(vec![2, 3]); // `vec::IntoIter` specialization
1770 v.extend(std::iter::once(3)); // `TrustedLen` specialization
1771 v.extend(std::iter::empty::<i32>()); // `TrustedLen` specialization with empty iterator
1772 v.extend(std::iter::once(3).filter(|_| true)); // base case
1773 v.extend(std::iter::once(&3)); // `cloned` specialization
1774 assert_eq!(*v0, 13);
1778 assert_eq!(*v0, 13);
1781 v.resize_with(v.len() + 10, || 42);
1782 assert_eq!(*v0, 13);
1783 v.resize_with(2, || panic!());
1784 assert_eq!(*v0, 13);
1786 // No-op reservation
1788 v.reserve_exact(32);
1789 assert_eq!(*v0, 13);
1792 v.resize_with(10, || 42);
1793 next_then_drop(v.drain(5..));
1794 assert_eq!(*v0, 13);
1797 v.resize_with(10, || 42);
1798 next_then_drop(v.splice(5.., vec![1, 2, 3, 4, 5])); // empty tail after range
1799 assert_eq!(*v0, 13);
1800 next_then_drop(v.splice(5..8, vec![1])); // replacement is smaller than original range
1801 assert_eq!(*v0, 13);
1802 next_then_drop(v.splice(5..6, vec![1; 10].into_iter().filter(|_| true))); // lower bound not exact
1803 assert_eq!(*v0, 13);
1805 // spare_capacity_mut
1806 v.spare_capacity_mut();
1807 assert_eq!(*v0, 13);
1809 // Smoke test that would fire even outside Miri if an actual relocation happened.
1811 assert_eq!(v[0], 0);
1814 // https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
1817 // unsafe impl<T: ?Sized> IsZero for *mut T {
1818 // fn is_zero(&self) -> bool {
1819 // (*self).is_null()
1824 // … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
1825 // which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
1826 // That is, a fat pointer can be “null” without being made entirely of zero bits.
1828 fn vec_macro_repeating_null_raw_fat_pointer() {
1829 let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
1830 let vtable = dbg!(ptr_metadata(raw_dyn));
1831 let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
1832 assert!(null_raw_dyn.is_null());
1834 let vec = vec![null_raw_dyn; 1];
1835 dbg!(ptr_metadata(vec[0]));
1836 assert!(vec[0] == null_raw_dyn);
1838 // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
1840 fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
1841 unsafe { std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable }
1844 fn ptr_from_raw_parts(data: *mut (), vtable: *mut ()) -> *mut dyn Fn() {
1845 unsafe { std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr { data, vtable }) }
1855 // This test will likely fail if you change the capacities used in
1856 // `RawVec::grow_amortized`.
1858 fn test_push_growth_strategy() {
1859 // If the element size is 1, we jump from 0 to 8, then double.
1861 let mut v1: Vec<u8> = vec![];
1862 assert_eq!(v1.capacity(), 0);
1866 assert_eq!(v1.capacity(), 8);
1871 assert_eq!(v1.capacity(), 16);
1876 assert_eq!(v1.capacity(), 32);
1881 assert_eq!(v1.capacity(), 64);
1885 // If the element size is 2..=1024, we jump from 0 to 4, then double.
1887 let mut v2: Vec<u16> = vec![];
1888 let mut v1024: Vec<[u8; 1024]> = vec![];
1889 assert_eq!(v2.capacity(), 0);
1890 assert_eq!(v1024.capacity(), 0);
1894 v1024.push([0; 1024]);
1895 assert_eq!(v2.capacity(), 4);
1896 assert_eq!(v1024.capacity(), 4);
1901 v1024.push([0; 1024]);
1902 assert_eq!(v2.capacity(), 8);
1903 assert_eq!(v1024.capacity(), 8);
1908 v1024.push([0; 1024]);
1909 assert_eq!(v2.capacity(), 16);
1910 assert_eq!(v1024.capacity(), 16);
1915 v1024.push([0; 1024]);
1916 assert_eq!(v2.capacity(), 32);
1917 assert_eq!(v1024.capacity(), 32);
1922 v1024.push([0; 1024]);
1923 assert_eq!(v2.capacity(), 64);
1924 assert_eq!(v1024.capacity(), 64);
1928 // If the element size is > 1024, we jump from 0 to 1, then double.
1930 let mut v1025: Vec<[u8; 1025]> = vec![];
1931 assert_eq!(v1025.capacity(), 0);
1934 v1025.push([0; 1025]);
1935 assert_eq!(v1025.capacity(), 1);
1939 v1025.push([0; 1025]);
1940 assert_eq!(v1025.capacity(), 2);
1944 v1025.push([0; 1025]);
1945 assert_eq!(v1025.capacity(), 4);
1949 v1025.push([0; 1025]);
1950 assert_eq!(v1025.capacity(), 8);
1954 v1025.push([0; 1025]);
1955 assert_eq!(v1025.capacity(), 16);
1959 v1025.push([0; 1025]);
1960 assert_eq!(v1025.capacity(), 32);
1964 v1025.push([0; 1025]);
1965 assert_eq!(v1025.capacity(), 64);
1970 macro_rules! generate_assert_eq_vec_and_prim {
1971 ($name:ident<$B:ident>($type:ty)) => {
1972 fn $name<A: PartialEq<$B> + Debug, $B: Debug>(a: Vec<A>, b: $type) {
1979 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_slice <B>(&[B]) }
1980 generate_assert_eq_vec_and_prim! { assert_eq_vec_and_array_3<B>([B; 3]) }
1983 fn partialeq_vec_and_prim() {
1984 assert_eq_vec_and_slice(vec![1, 2, 3], &[1, 2, 3]);
1985 assert_eq_vec_and_array_3(vec![1, 2, 3], [1, 2, 3]);
1988 macro_rules! assert_partial_eq_valid {
1989 ($a2:expr, $a3:expr; $b2:expr, $b3: expr) => {
1990 assert!($a2 == $b2);
1991 assert!($a2 != $b3);
1992 assert!($a3 != $b2);
1993 assert!($a3 == $b3);
1994 assert_eq!($a2, $b2);
1995 assert_ne!($a2, $b3);
1996 assert_ne!($a3, $b2);
1997 assert_eq!($a3, $b3);
2002 fn partialeq_vec_full() {
2003 let vec2: Vec<_> = vec![1, 2];
2004 let vec3: Vec<_> = vec![1, 2, 3];
2005 let slice2: &[_] = &[1, 2];
2006 let slice3: &[_] = &[1, 2, 3];
2007 let slicemut2: &[_] = &mut [1, 2];
2008 let slicemut3: &[_] = &mut [1, 2, 3];
2009 let array2: [_; 2] = [1, 2];
2010 let array3: [_; 3] = [1, 2, 3];
2011 let arrayref2: &[_; 2] = &[1, 2];
2012 let arrayref3: &[_; 3] = &[1, 2, 3];
2014 assert_partial_eq_valid!(vec2,vec3; vec2,vec3);
2015 assert_partial_eq_valid!(vec2,vec3; slice2,slice3);
2016 assert_partial_eq_valid!(vec2,vec3; slicemut2,slicemut3);
2017 assert_partial_eq_valid!(slice2,slice3; vec2,vec3);
2018 assert_partial_eq_valid!(slicemut2,slicemut3; vec2,vec3);
2019 assert_partial_eq_valid!(vec2,vec3; array2,array3);
2020 assert_partial_eq_valid!(vec2,vec3; arrayref2,arrayref3);
2021 assert_partial_eq_valid!(vec2,vec3; arrayref2[..],arrayref3[..]);
2025 fn test_vec_cycle() {
2028 v: Vec<Cell<Option<&'a C<'a>>>>,
2037 let mut c1 = C::new();
2038 let mut c2 = C::new();
2039 let mut c3 = C::new();
2042 c1.v.push(Cell::new(None));
2043 c1.v.push(Cell::new(None));
2045 c2.v.push(Cell::new(None));
2046 c2.v.push(Cell::new(None));
2048 c3.v.push(Cell::new(None));
2049 c3.v.push(Cell::new(None));
2052 c1.v[0].set(Some(&c2));
2053 c1.v[1].set(Some(&c3));
2055 c2.v[0].set(Some(&c2));
2056 c2.v[1].set(Some(&c3));
2058 c3.v[0].set(Some(&c1));
2059 c3.v[1].set(Some(&c2));
2063 fn test_vec_cycle_wrapped() {
2065 v: Vec<Cell<Option<&'a C<'a>>>>,
2073 fn new() -> Refs<'a> {
2074 Refs { v: Vec::new() }
2080 C { refs: Refs::new() }
2084 let mut c1 = C::new();
2085 let mut c2 = C::new();
2086 let mut c3 = C::new();
2088 c1.refs.v.push(Cell::new(None));
2089 c1.refs.v.push(Cell::new(None));
2090 c2.refs.v.push(Cell::new(None));
2091 c2.refs.v.push(Cell::new(None));
2092 c3.refs.v.push(Cell::new(None));
2093 c3.refs.v.push(Cell::new(None));
2095 c1.refs.v[0].set(Some(&c2));
2096 c1.refs.v[1].set(Some(&c3));
2097 c2.refs.v[0].set(Some(&c2));
2098 c2.refs.v[1].set(Some(&c3));
2099 c3.refs.v[0].set(Some(&c1));
2100 c3.refs.v[1].set(Some(&c2));
2104 fn test_zero_sized_vec_push() {
2108 let mut tester = Vec::with_capacity(len);
2109 assert_eq!(tester.len(), 0);
2110 assert!(tester.capacity() >= len);
2114 assert_eq!(tester.len(), len);
2115 assert_eq!(tester.iter().count(), len);
2121 fn test_vec_macro_repeat() {
2122 assert_eq!(vec![1; 3], vec![1, 1, 1]);
2123 assert_eq!(vec![1; 2], vec![1, 1]);
2124 assert_eq!(vec![1; 1], vec![1]);
2125 assert_eq!(vec![1; 0], vec![]);
2127 // from_elem syntax (see RFC 832)
2128 let el = Box::new(1);
2130 assert_eq!(vec![el; n], vec![Box::new(1), Box::new(1), Box::new(1)]);
2134 fn test_vec_swap() {
2135 let mut a: Vec<isize> = vec![0, 1, 2, 3, 4, 5, 6];
2137 assert_eq!(a[2], 4);
2138 assert_eq!(a[4], 2);
2140 swap(&mut n, &mut a[0]);
2141 assert_eq!(a[0], 42);
2146 fn test_extend_from_within_spec() {
2150 impl Clone for CopyOnly {
2151 fn clone(&self) -> Self {
2152 panic!("extend_from_within must use specialization on copy");
2156 vec![CopyOnly, CopyOnly].extend_from_within(..);
2160 fn test_extend_from_within_clone() {
2161 let mut v = vec![String::from("sssss"), String::from("12334567890"), String::from("c")];
2162 v.extend_from_within(1..);
2164 assert_eq!(v, ["sssss", "12334567890", "c", "12334567890", "c"]);
2168 fn test_extend_from_within_complete_rande() {
2169 let mut v = vec![0, 1, 2, 3];
2170 v.extend_from_within(..);
2172 assert_eq!(v, [0, 1, 2, 3, 0, 1, 2, 3]);
2176 fn test_extend_from_within_empty_rande() {
2177 let mut v = vec![0, 1, 2, 3];
2178 v.extend_from_within(1..1);
2180 assert_eq!(v, [0, 1, 2, 3]);
2185 fn test_extend_from_within_out_of_rande() {
2186 let mut v = vec![0, 1];
2187 v.extend_from_within(..3);
2191 fn test_extend_from_within_zst() {
2192 let mut v = vec![(); 8];
2193 v.extend_from_within(3..7);
2195 assert_eq!(v, [(); 12]);
2199 fn test_extend_from_within_empty_vec() {
2200 let mut v = Vec::<i32>::new();
2201 v.extend_from_within(..);
2207 fn test_extend_from_within() {
2208 let mut v = vec![String::from("a"), String::from("b"), String::from("c")];
2209 v.extend_from_within(1..=2);
2210 v.extend_from_within(..=1);
2212 assert_eq!(v, ["a", "b", "c", "b", "c", "a", "b"]);
2216 fn test_vec_dedup_by() {
2217 let mut vec: Vec<i32> = vec![1, -1, 2, 3, 1, -5, 5, -2, 2];
2219 vec.dedup_by(|a, b| a.abs() == b.abs());
2221 assert_eq!(vec, [1, 2, 3, 1, -5, -2]);
2225 fn test_vec_dedup_empty() {
2226 let mut vec: Vec<i32> = Vec::new();
2230 assert_eq!(vec, []);
2234 fn test_vec_dedup_one() {
2235 let mut vec = vec![12i32];
2239 assert_eq!(vec, [12]);
2243 fn test_vec_dedup_multiple_ident() {
2244 let mut vec = vec![12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11];
2248 assert_eq!(vec, [12, 11]);
2252 fn test_vec_dedup_partialeq() {
2254 struct Foo(i32, i32);
2256 impl PartialEq for Foo {
2257 fn eq(&self, other: &Foo) -> bool {
2262 let mut vec = vec![Foo(0, 1), Foo(0, 5), Foo(1, 7), Foo(1, 9)];
2265 assert_eq!(vec, [Foo(0, 1), Foo(1, 7)]);
2269 fn test_vec_dedup() {
2270 let mut vec: Vec<bool> = Vec::with_capacity(8);
2271 let mut template = vec.clone();
2273 for x in 0u8..255u8 {
2277 let iter = (0..8).map(move |bit| (x >> bit) & 1 == 1);
2279 template.extend_from_slice(&vec);
2281 let (dedup, _) = template.partition_dedup();
2284 assert_eq!(vec, dedup);
2289 fn test_vec_dedup_panicking() {
2292 drop_counter: &'a Cell<u32>,
2297 impl<'a> PartialEq for Panic<'a> {
2298 fn eq(&self, other: &Self) -> bool {
2299 self.value == other.value
2303 impl<'a> Drop for Panic<'a> {
2304 fn drop(&mut self) {
2305 self.drop_counter.set(self.drop_counter.get() + 1);
2306 if !std::thread::panicking() {
2307 assert!(self.index != 4);
2312 let drop_counter = &Cell::new(0);
2314 Panic { drop_counter, value: false, index: 0 },
2315 Panic { drop_counter, value: false, index: 5 },
2316 Panic { drop_counter, value: true, index: 6 },
2317 Panic { drop_counter, value: true, index: 7 },
2320 Panic { drop_counter, value: false, index: 0 },
2321 // these elements get deduplicated
2322 Panic { drop_counter, value: false, index: 1 },
2323 Panic { drop_counter, value: false, index: 2 },
2324 Panic { drop_counter, value: false, index: 3 },
2325 Panic { drop_counter, value: false, index: 4 },
2326 // here it panics while dropping the item with index==4
2327 Panic { drop_counter, value: false, index: 5 },
2328 Panic { drop_counter, value: true, index: 6 },
2329 Panic { drop_counter, value: true, index: 7 },
2332 let _ = catch_unwind(AssertUnwindSafe(|| vec.dedup())).unwrap_err();
2334 assert_eq!(drop_counter.get(), 4);
2336 let ok = vec.iter().zip(expected.iter()).all(|(x, y)| x.index == y.index);
2339 panic!("expected: {:?}\ngot: {:?}\n", expected, vec);
2343 // Regression test for issue #82533
2345 fn test_extend_from_within_panicing_clone() {
2347 drop_count: &'dc AtomicU32,
2351 impl Clone for Panic<'_> {
2352 fn clone(&self) -> Self {
2354 panic!("panic! at the clone");
2361 impl Drop for Panic<'_> {
2362 fn drop(&mut self) {
2363 self.drop_count.fetch_add(1, Ordering::SeqCst);
2367 let count = core::sync::atomic::AtomicU32::new(0);
2369 Panic { drop_count: &count, aaaaa: false },
2370 Panic { drop_count: &count, aaaaa: true },
2371 Panic { drop_count: &count, aaaaa: false },
2374 // This should clone&append one Panic{..} at the end, and then panic while
2375 // cloning second Panic{..}. This means that `Panic::drop` should be called
2376 // 4 times (3 for items already in vector, 1 for just appended).
2378 // Previously just appended item was leaked, making drop_count = 3, instead of 4.
2379 std::panic::catch_unwind(move || vec.extend_from_within(..)).unwrap_err();
2381 assert_eq!(count.load(Ordering::SeqCst), 4);