2 use std::collections::TryReserveError::*;
4 use std::panic::{catch_unwind, AssertUnwindSafe};
5 use std::vec::{Drain, IntoIter};
7 struct DropCounter<'a> {
11 impl Drop for DropCounter<'_> {
18 fn test_small_vec_struct() {
19 assert!(size_of::<Vec<u8>>() == size_of::<usize>() * 3);
23 fn test_double_drop() {
29 let (mut count_x, mut count_y) = (0, 0);
31 let mut tv = TwoVec { x: Vec::new(), y: Vec::new() };
32 tv.x.push(DropCounter { count: &mut count_x });
33 tv.y.push(DropCounter { count: &mut count_y });
35 // If Vec had a drop flag, here is where it would be zeroed.
36 // Instead, it should rely on its internal state to prevent
37 // doing anything significant when dropped multiple times.
40 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
43 assert_eq!(count_x, 1);
44 assert_eq!(count_y, 1);
49 let mut v = Vec::new();
50 assert_eq!(v.capacity(), 0);
53 assert!(v.capacity() >= 2);
59 assert!(v.capacity() >= 16);
61 assert!(v.capacity() >= 32);
66 assert!(v.capacity() >= 33)
70 fn test_zst_capacity() {
71 assert_eq!(Vec::<()>::new().capacity(), usize::max_value());
76 let mut v = Vec::new();
77 let mut w = Vec::new();
96 v.extend(w.clone()); // specializes to `append`
97 assert!(v.iter().eq(w.iter().chain(w.iter())));
100 #[derive(PartialEq, Debug)]
103 let mut a = Vec::new();
104 let b = vec![Foo, Foo];
107 assert_eq!(a, &[Foo, Foo]);
112 let mut x = Vec::new();
113 let y = vec![DropCounter { count: &mut count_x }];
116 assert_eq!(count_x, 1);
120 fn test_extend_ref() {
121 let mut v = vec![1, 2];
122 v.extend(&[3, 4, 5]);
124 assert_eq!(v.len(), 5);
125 assert_eq!(v, [1, 2, 3, 4, 5]);
130 assert_eq!(v.len(), 7);
131 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
135 fn test_remove_item() {
136 let mut v = vec![1, 2, 3];
139 assert_eq!(v.len(), 2);
140 assert_eq!(v, [2, 3]);
142 let mut w = vec![1, 2, 3];
145 assert_eq!(w.len(), 3);
150 fn test_slice_from_mut() {
151 let mut values = vec![1, 2, 3, 4, 5];
153 let slice = &mut values[2..];
154 assert!(slice == [3, 4, 5]);
160 assert!(values == [1, 2, 5, 6, 7]);
164 fn test_slice_to_mut() {
165 let mut values = vec![1, 2, 3, 4, 5];
167 let slice = &mut values[..2];
168 assert!(slice == [1, 2]);
174 assert!(values == [2, 3, 3, 4, 5]);
178 fn test_split_at_mut() {
179 let mut values = vec![1, 2, 3, 4, 5];
181 let (left, right) = values.split_at_mut(2);
183 let left: &[_] = left;
184 assert!(&left[..left.len()] == &[1, 2]);
191 let right: &[_] = right;
192 assert!(&right[..right.len()] == &[3, 4, 5]);
199 assert_eq!(values, [2, 3, 5, 6, 7]);
204 let v: Vec<i32> = vec![];
205 let w = vec![1, 2, 3];
207 assert_eq!(v, v.clone());
211 // they should be disjoint in memory.
212 assert!(w.as_ptr() != z.as_ptr())
216 fn test_clone_from() {
218 let three: Vec<Box<_>> = vec![box 1, box 2, box 3];
219 let two: Vec<Box<_>> = vec![box 4, box 5];
221 v.clone_from(&three);
222 assert_eq!(v, three);
225 v.clone_from(&three);
226 assert_eq!(v, three);
233 v.clone_from(&three);
239 let mut vec = vec![1, 2, 3, 4];
240 vec.retain(|&x| x % 2 == 0);
241 assert_eq!(vec, [2, 4]);
246 fn case(a: Vec<i32>, b: Vec<i32>) {
251 case(vec![], vec![]);
252 case(vec![1], vec![1]);
253 case(vec![1, 1], vec![1]);
254 case(vec![1, 2, 3], vec![1, 2, 3]);
255 case(vec![1, 1, 2, 3], vec![1, 2, 3]);
256 case(vec![1, 2, 2, 3], vec![1, 2, 3]);
257 case(vec![1, 2, 3, 3], vec![1, 2, 3]);
258 case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
262 fn test_dedup_by_key() {
263 fn case(a: Vec<i32>, b: Vec<i32>) {
265 v.dedup_by_key(|i| *i / 10);
268 case(vec![], vec![]);
269 case(vec![10], vec![10]);
270 case(vec![10, 11], vec![10]);
271 case(vec![10, 20, 30], vec![10, 20, 30]);
272 case(vec![10, 11, 20, 30], vec![10, 20, 30]);
273 case(vec![10, 20, 21, 30], vec![10, 20, 30]);
274 case(vec![10, 20, 30, 31], vec![10, 20, 30]);
275 case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
280 let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
281 vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
283 assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
285 let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
286 vec.dedup_by(|a, b| {
293 assert_eq!(vec, [("foo", 3), ("bar", 12)]);
297 fn test_dedup_unique() {
298 let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
300 let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
302 let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
304 // If the boxed pointers were leaked or otherwise misused, valgrind
305 // and/or rt should raise errors.
309 fn zero_sized_values() {
310 let mut v = Vec::new();
311 assert_eq!(v.len(), 0);
313 assert_eq!(v.len(), 1);
315 assert_eq!(v.len(), 2);
316 assert_eq!(v.pop(), Some(()));
317 assert_eq!(v.pop(), Some(()));
318 assert_eq!(v.pop(), None);
320 assert_eq!(v.iter().count(), 0);
322 assert_eq!(v.iter().count(), 1);
324 assert_eq!(v.iter().count(), 2);
328 assert_eq!(v.iter_mut().count(), 2);
330 assert_eq!(v.iter_mut().count(), 3);
332 assert_eq!(v.iter_mut().count(), 4);
334 for &mut () in &mut v {}
338 assert_eq!(v.iter_mut().count(), 0);
342 fn test_partition() {
343 assert_eq!(vec![].into_iter().partition(|x: &i32| *x < 3), (vec![], vec![]));
344 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 4), (vec![1, 2, 3], vec![]));
345 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 2), (vec![1], vec![2, 3]));
346 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 0), (vec![], vec![1, 2, 3]));
350 fn test_zip_unzip() {
351 let z1 = vec![(1, 4), (2, 5), (3, 6)];
353 let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
355 assert_eq!((1, 4), (left[0], right[0]));
356 assert_eq!((2, 5), (left[1], right[1]));
357 assert_eq!((3, 6), (left[2], right[2]));
361 fn test_vec_truncate_drop() {
362 static mut DROPS: u32 = 0;
372 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
373 assert_eq!(unsafe { DROPS }, 0);
375 assert_eq!(unsafe { DROPS }, 2);
377 assert_eq!(unsafe { DROPS }, 5);
382 fn test_vec_truncate_fail() {
384 impl Drop for BadElem {
386 let BadElem(ref mut x) = *self;
388 panic!("BadElem panic: 0xbadbeef")
393 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
399 let vec = vec![1, 2, 3];
400 assert!(vec[1] == 2);
405 fn test_index_out_of_bounds() {
406 let vec = vec![1, 2, 3];
412 fn test_slice_out_of_bounds_1() {
413 let x = vec![1, 2, 3, 4, 5];
419 fn test_slice_out_of_bounds_2() {
420 let x = vec![1, 2, 3, 4, 5];
426 fn test_slice_out_of_bounds_3() {
427 let x = vec![1, 2, 3, 4, 5];
433 fn test_slice_out_of_bounds_4() {
434 let x = vec![1, 2, 3, 4, 5];
440 fn test_slice_out_of_bounds_5() {
441 let x = vec![1, 2, 3, 4, 5];
447 fn test_swap_remove_empty() {
448 let mut vec = Vec::<i32>::new();
453 fn test_move_items() {
454 let vec = vec![1, 2, 3];
455 let mut vec2 = vec![];
459 assert_eq!(vec2, [1, 2, 3]);
463 fn test_move_items_reverse() {
464 let vec = vec![1, 2, 3];
465 let mut vec2 = vec![];
466 for i in vec.into_iter().rev() {
469 assert_eq!(vec2, [3, 2, 1]);
473 fn test_move_items_zero_sized() {
474 let vec = vec![(), (), ()];
475 let mut vec2 = vec![];
479 assert_eq!(vec2, [(), (), ()]);
483 fn test_drain_items() {
484 let mut vec = vec![1, 2, 3];
485 let mut vec2 = vec![];
486 for i in vec.drain(..) {
490 assert_eq!(vec2, [1, 2, 3]);
494 fn test_drain_items_reverse() {
495 let mut vec = vec![1, 2, 3];
496 let mut vec2 = vec![];
497 for i in vec.drain(..).rev() {
501 assert_eq!(vec2, [3, 2, 1]);
505 fn test_drain_items_zero_sized() {
506 let mut vec = vec![(), (), ()];
507 let mut vec2 = vec![];
508 for i in vec.drain(..) {
512 assert_eq!(vec2, [(), (), ()]);
517 fn test_drain_out_of_bounds() {
518 let mut v = vec![1, 2, 3, 4, 5];
523 fn test_drain_range() {
524 let mut v = vec![1, 2, 3, 4, 5];
525 for _ in v.drain(4..) {}
526 assert_eq!(v, &[1, 2, 3, 4]);
528 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
529 for _ in v.drain(1..4) {}
530 assert_eq!(v, &[1.to_string(), 5.to_string()]);
532 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
533 for _ in v.drain(1..4).rev() {}
534 assert_eq!(v, &[1.to_string(), 5.to_string()]);
536 let mut v: Vec<_> = vec![(); 5];
537 for _ in v.drain(1..4).rev() {}
538 assert_eq!(v, &[(), ()]);
542 fn test_drain_inclusive_range() {
543 let mut v = vec!['a', 'b', 'c', 'd', 'e'];
544 for _ in v.drain(1..=3) {}
545 assert_eq!(v, &['a', 'e']);
547 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
548 for _ in v.drain(1..=5) {}
549 assert_eq!(v, &["0".to_string()]);
551 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
552 for _ in v.drain(0..=5) {}
553 assert_eq!(v, Vec::<String>::new());
555 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
556 for _ in v.drain(0..=3) {}
557 assert_eq!(v, &["4".to_string(), "5".to_string()]);
559 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
560 for _ in v.drain(..=0) {}
561 assert_eq!(v, &["1".to_string()]);
565 fn test_drain_max_vec_size() {
566 let mut v = Vec::<()>::with_capacity(usize::max_value());
568 v.set_len(usize::max_value());
570 for _ in v.drain(usize::max_value() - 1..) {}
571 assert_eq!(v.len(), usize::max_value() - 1);
573 let mut v = Vec::<()>::with_capacity(usize::max_value());
575 v.set_len(usize::max_value());
577 for _ in v.drain(usize::max_value() - 1..=usize::max_value() - 1) {}
578 assert_eq!(v.len(), usize::max_value() - 1);
583 fn test_drain_inclusive_out_of_bounds() {
584 let mut v = vec![1, 2, 3, 4, 5];
589 fn test_drain_leak() {
590 static mut DROPS: i32 = 0;
592 #[derive(Debug, PartialEq)]
602 panic!("panic in `drop`");
617 catch_unwind(AssertUnwindSafe(|| {
622 assert_eq!(unsafe { DROPS }, 4);
623 assert_eq!(v, vec![D(0, false), D(1, false), D(6, false),]);
628 let mut v = vec![1, 2, 3, 4, 5];
629 let a = [10, 11, 12];
630 v.splice(2..4, a.iter().cloned());
631 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
632 v.splice(1..3, Some(20));
633 assert_eq!(v, &[1, 20, 11, 12, 5]);
637 fn test_splice_inclusive_range() {
638 let mut v = vec![1, 2, 3, 4, 5];
639 let a = [10, 11, 12];
640 let t1: Vec<_> = v.splice(2..=3, a.iter().cloned()).collect();
641 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
642 assert_eq!(t1, &[3, 4]);
643 let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
644 assert_eq!(v, &[1, 20, 11, 12, 5]);
645 assert_eq!(t2, &[2, 10]);
650 fn test_splice_out_of_bounds() {
651 let mut v = vec![1, 2, 3, 4, 5];
652 let a = [10, 11, 12];
653 v.splice(5..6, a.iter().cloned());
658 fn test_splice_inclusive_out_of_bounds() {
659 let mut v = vec![1, 2, 3, 4, 5];
660 let a = [10, 11, 12];
661 v.splice(5..=5, a.iter().cloned());
665 fn test_splice_items_zero_sized() {
666 let mut vec = vec![(), (), ()];
668 let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
669 assert_eq!(vec, &[(), ()]);
670 assert_eq!(t, &[()]);
674 fn test_splice_unbounded() {
675 let mut vec = vec![1, 2, 3, 4, 5];
676 let t: Vec<_> = vec.splice(.., None).collect();
677 assert_eq!(vec, &[]);
678 assert_eq!(t, &[1, 2, 3, 4, 5]);
682 fn test_splice_forget() {
683 let mut v = vec![1, 2, 3, 4, 5];
684 let a = [10, 11, 12];
685 std::mem::forget(v.splice(2..4, a.iter().cloned()));
686 assert_eq!(v, &[1, 2]);
690 fn test_into_boxed_slice() {
691 let xs = vec![1, 2, 3];
692 let ys = xs.into_boxed_slice();
693 assert_eq!(&*ys, [1, 2, 3]);
698 let mut vec = vec![1, 2, 3];
699 let mut vec2 = vec![4, 5, 6];
700 vec.append(&mut vec2);
701 assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
702 assert_eq!(vec2, []);
706 fn test_split_off() {
707 let mut vec = vec![1, 2, 3, 4, 5, 6];
708 let vec2 = vec.split_off(4);
709 assert_eq!(vec, [1, 2, 3, 4]);
710 assert_eq!(vec2, [5, 6]);
714 fn test_into_iter_as_slice() {
715 let vec = vec!['a', 'b', 'c'];
716 let mut into_iter = vec.into_iter();
717 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
718 let _ = into_iter.next().unwrap();
719 assert_eq!(into_iter.as_slice(), &['b', 'c']);
720 let _ = into_iter.next().unwrap();
721 let _ = into_iter.next().unwrap();
722 assert_eq!(into_iter.as_slice(), &[]);
726 fn test_into_iter_as_mut_slice() {
727 let vec = vec!['a', 'b', 'c'];
728 let mut into_iter = vec.into_iter();
729 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
730 into_iter.as_mut_slice()[0] = 'x';
731 into_iter.as_mut_slice()[1] = 'y';
732 assert_eq!(into_iter.next().unwrap(), 'x');
733 assert_eq!(into_iter.as_slice(), &['y', 'c']);
737 fn test_into_iter_debug() {
738 let vec = vec!['a', 'b', 'c'];
739 let into_iter = vec.into_iter();
740 let debug = format!("{:?}", into_iter);
741 assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
745 fn test_into_iter_count() {
746 assert_eq!(vec![1, 2, 3].into_iter().count(), 3);
750 fn test_into_iter_clone() {
751 fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
752 let v: Vec<i32> = it.collect();
753 assert_eq!(&v[..], slice);
755 let mut it = vec![1, 2, 3].into_iter();
756 iter_equal(it.clone(), &[1, 2, 3]);
757 assert_eq!(it.next(), Some(1));
758 let mut it = it.rev();
759 iter_equal(it.clone(), &[3, 2]);
760 assert_eq!(it.next(), Some(3));
761 iter_equal(it.clone(), &[2]);
762 assert_eq!(it.next(), Some(2));
763 iter_equal(it.clone(), &[]);
764 assert_eq!(it.next(), None);
768 fn test_into_iter_leak() {
769 static mut DROPS: i32 = 0;
780 panic!("panic in `drop`");
785 let v = vec![D(false), D(true), D(false)];
787 catch_unwind(move || drop(v.into_iter())).ok();
789 assert_eq!(unsafe { DROPS }, 3);
794 let borrowed: &[_] = &["borrowed", "(slice)"];
795 let owned = vec!["owned", "(vec)"];
796 match (Cow::from(owned.clone()), Cow::from(borrowed)) {
797 (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
798 _ => panic!("invalid `Cow::from`"),
804 let borrowed: &[_] = &["borrowed", "(slice)"];
805 let owned = vec!["owned", "(vec)"];
806 assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
807 assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
811 fn assert_covariance() {
812 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
815 fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
821 fn from_into_inner() {
822 let vec = vec![1, 2, 3];
823 let ptr = vec.as_ptr();
824 let vec = vec.into_iter().collect::<Vec<_>>();
825 assert_eq!(vec, [1, 2, 3]);
826 assert_eq!(vec.as_ptr(), ptr);
828 let ptr = &vec[1] as *const _;
829 let mut it = vec.into_iter();
831 let vec = it.collect::<Vec<_>>();
832 assert_eq!(vec, [2, 3]);
833 assert!(ptr != vec.as_ptr());
837 fn overaligned_allocations() {
840 let mut v = vec![Foo(273)];
843 assert!(v[0].0 == 273);
844 assert!(v.as_ptr() as usize & 0xff == 0);
846 assert!(v[0].0 == 273);
847 assert!(v.as_ptr() as usize & 0xff == 0);
852 fn drain_filter_empty() {
853 let mut vec: Vec<i32> = vec![];
856 let mut iter = vec.drain_filter(|_| true);
857 assert_eq!(iter.size_hint(), (0, Some(0)));
858 assert_eq!(iter.next(), None);
859 assert_eq!(iter.size_hint(), (0, Some(0)));
860 assert_eq!(iter.next(), None);
861 assert_eq!(iter.size_hint(), (0, Some(0)));
863 assert_eq!(vec.len(), 0);
864 assert_eq!(vec, vec![]);
868 fn drain_filter_zst() {
869 let mut vec = vec![(), (), (), (), ()];
870 let initial_len = vec.len();
873 let mut iter = vec.drain_filter(|_| true);
874 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
875 while let Some(_) = iter.next() {
877 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
879 assert_eq!(iter.size_hint(), (0, Some(0)));
880 assert_eq!(iter.next(), None);
881 assert_eq!(iter.size_hint(), (0, Some(0)));
884 assert_eq!(count, initial_len);
885 assert_eq!(vec.len(), 0);
886 assert_eq!(vec, vec![]);
890 fn drain_filter_false() {
891 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
893 let initial_len = vec.len();
896 let mut iter = vec.drain_filter(|_| false);
897 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
898 for _ in iter.by_ref() {
901 assert_eq!(iter.size_hint(), (0, Some(0)));
902 assert_eq!(iter.next(), None);
903 assert_eq!(iter.size_hint(), (0, Some(0)));
906 assert_eq!(count, 0);
907 assert_eq!(vec.len(), initial_len);
908 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
912 fn drain_filter_true() {
913 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
915 let initial_len = vec.len();
918 let mut iter = vec.drain_filter(|_| true);
919 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
920 while let Some(_) = iter.next() {
922 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
924 assert_eq!(iter.size_hint(), (0, Some(0)));
925 assert_eq!(iter.next(), None);
926 assert_eq!(iter.size_hint(), (0, Some(0)));
929 assert_eq!(count, initial_len);
930 assert_eq!(vec.len(), 0);
931 assert_eq!(vec, vec![]);
935 fn drain_filter_complex() {
937 // [+xxx++++++xxxxx++++x+x++]
939 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
943 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
944 assert_eq!(removed.len(), 10);
945 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
947 assert_eq!(vec.len(), 14);
948 assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
952 // [xxx++++++xxxxx++++x+x++]
954 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
957 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
958 assert_eq!(removed.len(), 10);
959 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
961 assert_eq!(vec.len(), 13);
962 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
966 // [xxx++++++xxxxx++++x+x]
968 vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36];
970 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
971 assert_eq!(removed.len(), 10);
972 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
974 assert_eq!(vec.len(), 11);
975 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
979 // [xxxxxxxxxx+++++++++++]
980 let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
982 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
983 assert_eq!(removed.len(), 10);
984 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
986 assert_eq!(vec.len(), 10);
987 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
991 // [+++++++++++xxxxxxxxxx]
992 let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
994 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
995 assert_eq!(removed.len(), 10);
996 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
998 assert_eq!(vec.len(), 10);
999 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
1003 // FIXME: re-enable emscripten once it can unwind again
1005 #[cfg(not(target_os = "emscripten"))]
1006 fn drain_filter_consumed_panic() {
1008 use std::sync::Mutex;
1012 drop_counts: Rc<Mutex<Vec<usize>>>,
1015 impl Drop for Check {
1016 fn drop(&mut self) {
1017 self.drop_counts.lock().unwrap()[self.index] += 1;
1018 println!("drop: {}", self.index);
1022 let check_count = 10;
1023 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1024 let mut data: Vec<Check> = (0..check_count)
1025 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1028 let _ = std::panic::catch_unwind(move || {
1029 let filter = |c: &mut Check| {
1031 panic!("panic at index: {}", c.index);
1033 // Verify that if the filter could panic again on another element
1034 // that it would not cause a double panic and all elements of the
1035 // vec would still be dropped exactly once.
1037 panic!("panic at index: {}", c.index);
1041 let drain = data.drain_filter(filter);
1043 // NOTE: The DrainFilter is explicitly consumed
1044 drain.for_each(drop);
1047 let drop_counts = drop_counts.lock().unwrap();
1048 assert_eq!(check_count, drop_counts.len());
1050 for (index, count) in drop_counts.iter().cloned().enumerate() {
1051 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1055 // FIXME: Re-enable emscripten once it can catch panics
1057 #[cfg(not(target_os = "emscripten"))]
1058 fn drain_filter_unconsumed_panic() {
1060 use std::sync::Mutex;
1064 drop_counts: Rc<Mutex<Vec<usize>>>,
1067 impl Drop for Check {
1068 fn drop(&mut self) {
1069 self.drop_counts.lock().unwrap()[self.index] += 1;
1070 println!("drop: {}", self.index);
1074 let check_count = 10;
1075 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1076 let mut data: Vec<Check> = (0..check_count)
1077 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1080 let _ = std::panic::catch_unwind(move || {
1081 let filter = |c: &mut Check| {
1083 panic!("panic at index: {}", c.index);
1085 // Verify that if the filter could panic again on another element
1086 // that it would not cause a double panic and all elements of the
1087 // vec would still be dropped exactly once.
1089 panic!("panic at index: {}", c.index);
1093 let _drain = data.drain_filter(filter);
1095 // NOTE: The DrainFilter is dropped without being consumed
1098 let drop_counts = drop_counts.lock().unwrap();
1099 assert_eq!(check_count, drop_counts.len());
1101 for (index, count) in drop_counts.iter().cloned().enumerate() {
1102 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1107 fn drain_filter_unconsumed() {
1108 let mut vec = vec![1, 2, 3, 4];
1109 let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1111 assert_eq!(vec, [2, 4]);
1115 fn test_reserve_exact() {
1116 // This is all the same as test_reserve
1118 let mut v = Vec::new();
1119 assert_eq!(v.capacity(), 0);
1122 assert!(v.capacity() >= 2);
1128 assert!(v.capacity() >= 16);
1129 v.reserve_exact(16);
1130 assert!(v.capacity() >= 32);
1134 v.reserve_exact(16);
1135 assert!(v.capacity() >= 33)
1139 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1140 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1141 fn test_try_reserve() {
1142 // These are the interesting cases:
1143 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1144 // * > isize::MAX should always fail
1145 // * On 16/32-bit should CapacityOverflow
1146 // * On 64-bit should OOM
1147 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1148 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1150 const MAX_CAP: usize = isize::MAX as usize;
1151 const MAX_USIZE: usize = usize::MAX;
1153 // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1154 // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1155 // Any platform that succeeds for these requests is technically broken with
1156 // ptr::offset because LLVM is the worst.
1157 let guards_against_isize = size_of::<usize>() < 8;
1160 // Note: basic stuff is checked by test_reserve
1161 let mut empty_bytes: Vec<u8> = Vec::new();
1163 // Check isize::MAX doesn't count as an overflow
1164 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1165 panic!("isize::MAX shouldn't trigger an overflow!");
1167 // Play it again, frank! (just to be sure)
1168 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1169 panic!("isize::MAX shouldn't trigger an overflow!");
1172 if guards_against_isize {
1173 // Check isize::MAX + 1 does count as overflow
1174 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
1176 panic!("isize::MAX + 1 should trigger an overflow!")
1179 // Check usize::MAX does count as overflow
1180 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
1182 panic!("usize::MAX should trigger an overflow!")
1185 // Check isize::MAX + 1 is an OOM
1186 if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_CAP + 1) {
1188 panic!("isize::MAX + 1 should trigger an OOM!")
1191 // Check usize::MAX is an OOM
1192 if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE) {
1194 panic!("usize::MAX should trigger an OOM!")
1200 // Same basic idea, but with non-zero len
1201 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1203 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1204 panic!("isize::MAX shouldn't trigger an overflow!");
1206 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1207 panic!("isize::MAX shouldn't trigger an overflow!");
1209 if guards_against_isize {
1210 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
1212 panic!("isize::MAX + 1 should trigger an overflow!");
1215 if let Err(AllocError { .. }) = ten_bytes.try_reserve(MAX_CAP - 9) {
1217 panic!("isize::MAX + 1 should trigger an OOM!")
1220 // Should always overflow in the add-to-len
1221 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
1223 panic!("usize::MAX should trigger an overflow!")
1228 // Same basic idea, but with interesting type size
1229 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1231 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) {
1232 panic!("isize::MAX shouldn't trigger an overflow!");
1234 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) {
1235 panic!("isize::MAX shouldn't trigger an overflow!");
1237 if guards_against_isize {
1238 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) {
1240 panic!("isize::MAX + 1 should trigger an overflow!");
1243 if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) {
1245 panic!("isize::MAX + 1 should trigger an OOM!")
1248 // Should fail in the mul-by-size
1249 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
1251 panic!("usize::MAX should trigger an overflow!");
1257 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1258 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1259 fn test_try_reserve_exact() {
1260 // This is exactly the same as test_try_reserve with the method changed.
1261 // See that test for comments.
1263 const MAX_CAP: usize = isize::MAX as usize;
1264 const MAX_USIZE: usize = usize::MAX;
1266 let guards_against_isize = size_of::<usize>() < 8;
1269 let mut empty_bytes: Vec<u8> = Vec::new();
1271 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1272 panic!("isize::MAX shouldn't trigger an overflow!");
1274 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1275 panic!("isize::MAX shouldn't trigger an overflow!");
1278 if guards_against_isize {
1279 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1281 panic!("isize::MAX + 1 should trigger an overflow!")
1284 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1286 panic!("usize::MAX should trigger an overflow!")
1289 if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1291 panic!("isize::MAX + 1 should trigger an OOM!")
1294 if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1296 panic!("usize::MAX should trigger an OOM!")
1302 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1304 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1305 panic!("isize::MAX shouldn't trigger an overflow!");
1307 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1308 panic!("isize::MAX shouldn't trigger an overflow!");
1310 if guards_against_isize {
1311 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1313 panic!("isize::MAX + 1 should trigger an overflow!");
1316 if let Err(AllocError { .. }) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1318 panic!("isize::MAX + 1 should trigger an OOM!")
1321 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
1323 panic!("usize::MAX should trigger an overflow!")
1328 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1330 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) {
1331 panic!("isize::MAX shouldn't trigger an overflow!");
1333 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) {
1334 panic!("isize::MAX shouldn't trigger an overflow!");
1336 if guards_against_isize {
1337 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) {
1339 panic!("isize::MAX + 1 should trigger an overflow!");
1342 if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) {
1344 panic!("isize::MAX + 1 should trigger an OOM!")
1347 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
1349 panic!("usize::MAX should trigger an overflow!")
1355 fn test_stable_pointers() {
1356 /// Pull an element from the iterator, then drop it.
1357 /// Useful to cover both the `next` and `drop` paths of an iterator.
1358 fn next_then_drop<I: Iterator>(mut i: I) {
1363 // Test that, if we reserved enough space, adding and removing elements does not
1364 // invalidate references into the vector (such as `v0`). This test also
1365 // runs in Miri, which would detect such problems.
1366 let mut v = Vec::with_capacity(128);
1369 // Laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1371 let v0 = unsafe { &mut *(v0 as *mut _) };
1372 // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1374 // Pushing/inserting and popping/removing
1378 assert_eq!(*v0, 13);
1381 assert_eq!(*v0, 13);
1384 assert_eq!(v.len(), 2);
1385 v.swap_remove(1); // swap_remove the last element
1386 assert_eq!(*v0, 13);
1389 v.append(&mut vec![27, 19]);
1390 assert_eq!(*v0, 13);
1393 v.extend_from_slice(&[1, 2]);
1394 v.extend(&[1, 2]); // `slice::Iter` (with `T: Copy`) specialization
1395 v.extend(vec![2, 3]); // `vec::IntoIter` specialization
1396 v.extend(std::iter::once(3)); // `TrustedLen` specialization
1397 v.extend(std::iter::empty::<i32>()); // `TrustedLen` specialization with empty iterator
1398 v.extend(std::iter::once(3).filter(|_| true)); // base case
1399 v.extend(std::iter::once(&3)); // `cloned` specialization
1400 assert_eq!(*v0, 13);
1404 assert_eq!(*v0, 13);
1407 v.resize_with(v.len() + 10, || 42);
1408 assert_eq!(*v0, 13);
1409 v.resize_with(2, || panic!());
1410 assert_eq!(*v0, 13);
1412 // No-op reservation
1414 v.reserve_exact(32);
1415 assert_eq!(*v0, 13);
1418 v.resize_with(10, || 42);
1419 next_then_drop(v.drain(5..));
1420 assert_eq!(*v0, 13);
1423 v.resize_with(10, || 42);
1424 next_then_drop(v.splice(5.., vec![1, 2, 3, 4, 5])); // empty tail after range
1425 assert_eq!(*v0, 13);
1426 next_then_drop(v.splice(5..8, vec![1])); // replacement is smaller than original range
1427 assert_eq!(*v0, 13);
1428 next_then_drop(v.splice(5..6, vec![1; 10].into_iter().filter(|_| true))); // lower bound not exact
1429 assert_eq!(*v0, 13);
1431 // Smoke test that would fire even outside Miri if an actual relocation happened.
1433 assert_eq!(v[0], 0);
1436 // https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
1439 // unsafe impl<T: ?Sized> IsZero for *mut T {
1440 // fn is_zero(&self) -> bool {
1441 // (*self).is_null()
1446 // … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
1447 // which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
1448 // That is, a fat pointer can be “null” without being made entirely of zero bits.
1450 fn vec_macro_repeating_null_raw_fat_pointer() {
1451 let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
1452 let vtable = dbg!(ptr_metadata(raw_dyn));
1453 let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
1454 assert!(null_raw_dyn.is_null());
1456 let vec = vec![null_raw_dyn; 1];
1457 dbg!(ptr_metadata(vec[0]));
1458 assert!(vec[0] == null_raw_dyn);
1460 // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
1462 fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
1463 unsafe { std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable }
1466 fn ptr_from_raw_parts(data: *mut (), vtable: *mut ()) -> *mut dyn Fn() {
1467 unsafe { std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr { data, vtable }) }
1477 // This test will likely fail if you change the capacities used in
1478 // `RawVec::grow_amortized`.
1480 fn test_push_growth_strategy() {
1481 // If the element size is 1, we jump from 0 to 8, then double.
1483 let mut v1: Vec<u8> = vec![];
1484 assert_eq!(v1.capacity(), 0);
1488 assert_eq!(v1.capacity(), 8);
1493 assert_eq!(v1.capacity(), 16);
1498 assert_eq!(v1.capacity(), 32);
1503 assert_eq!(v1.capacity(), 64);
1507 // If the element size is 2..=1024, we jump from 0 to 4, then double.
1509 let mut v2: Vec<u16> = vec![];
1510 let mut v1024: Vec<[u8; 1024]> = vec![];
1511 assert_eq!(v2.capacity(), 0);
1512 assert_eq!(v1024.capacity(), 0);
1516 v1024.push([0; 1024]);
1517 assert_eq!(v2.capacity(), 4);
1518 assert_eq!(v1024.capacity(), 4);
1523 v1024.push([0; 1024]);
1524 assert_eq!(v2.capacity(), 8);
1525 assert_eq!(v1024.capacity(), 8);
1530 v1024.push([0; 1024]);
1531 assert_eq!(v2.capacity(), 16);
1532 assert_eq!(v1024.capacity(), 16);
1537 v1024.push([0; 1024]);
1538 assert_eq!(v2.capacity(), 32);
1539 assert_eq!(v1024.capacity(), 32);
1544 v1024.push([0; 1024]);
1545 assert_eq!(v2.capacity(), 64);
1546 assert_eq!(v1024.capacity(), 64);
1550 // If the element size is > 1024, we jump from 0 to 1, then double.
1552 let mut v1025: Vec<[u8; 1025]> = vec![];
1553 assert_eq!(v1025.capacity(), 0);
1556 v1025.push([0; 1025]);
1557 assert_eq!(v1025.capacity(), 1);
1561 v1025.push([0; 1025]);
1562 assert_eq!(v1025.capacity(), 2);
1566 v1025.push([0; 1025]);
1567 assert_eq!(v1025.capacity(), 4);
1571 v1025.push([0; 1025]);
1572 assert_eq!(v1025.capacity(), 8);
1576 v1025.push([0; 1025]);
1577 assert_eq!(v1025.capacity(), 16);
1581 v1025.push([0; 1025]);
1582 assert_eq!(v1025.capacity(), 32);
1586 v1025.push([0; 1025]);
1587 assert_eq!(v1025.capacity(), 64);