3 use std::{usize, isize};
4 use std::vec::{Drain, IntoIter};
5 use std::collections::TryReserveError::*;
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);
35 tv.x.push(DropCounter { count: &mut count_x });
36 tv.y.push(DropCounter { count: &mut count_y });
38 // If Vec had a drop flag, here is where it would be zeroed.
39 // Instead, it should rely on its internal state to prevent
40 // doing anything significant when dropped multiple times.
43 // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
46 assert_eq!(count_x, 1);
47 assert_eq!(count_y, 1);
52 let mut v = Vec::new();
53 assert_eq!(v.capacity(), 0);
56 assert!(v.capacity() >= 2);
62 assert!(v.capacity() >= 16);
64 assert!(v.capacity() >= 32);
69 assert!(v.capacity() >= 33)
73 fn test_zst_capacity() {
74 assert_eq!(Vec::<()>::new().capacity(), usize::max_value());
79 let mut v = Vec::new();
80 let mut w = Vec::new();
99 v.extend(w.clone()); // specializes to `append`
100 assert!(v.iter().eq(w.iter().chain(w.iter())));
103 #[derive(PartialEq, Debug)]
106 let mut a = Vec::new();
107 let b = vec![Foo, Foo];
110 assert_eq!(a, &[Foo, Foo]);
115 let mut x = Vec::new();
116 let y = vec![DropCounter { count: &mut count_x }];
119 assert_eq!(count_x, 1);
123 fn test_extend_ref() {
124 let mut v = vec![1, 2];
125 v.extend(&[3, 4, 5]);
127 assert_eq!(v.len(), 5);
128 assert_eq!(v, [1, 2, 3, 4, 5]);
133 assert_eq!(v.len(), 7);
134 assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
138 fn test_slice_from_mut() {
139 let mut values = vec![1, 2, 3, 4, 5];
141 let slice = &mut values[2..];
142 assert!(slice == [3, 4, 5]);
148 assert!(values == [1, 2, 5, 6, 7]);
152 fn test_slice_to_mut() {
153 let mut values = vec![1, 2, 3, 4, 5];
155 let slice = &mut values[..2];
156 assert!(slice == [1, 2]);
162 assert!(values == [2, 3, 3, 4, 5]);
166 fn test_split_at_mut() {
167 let mut values = vec![1, 2, 3, 4, 5];
169 let (left, right) = values.split_at_mut(2);
171 let left: &[_] = left;
172 assert!(&left[..left.len()] == &[1, 2]);
179 let right: &[_] = right;
180 assert!(&right[..right.len()] == &[3, 4, 5]);
187 assert_eq!(values, [2, 3, 5, 6, 7]);
192 let v: Vec<i32> = vec![];
193 let w = vec![1, 2, 3];
195 assert_eq!(v, v.clone());
199 // they should be disjoint in memory.
200 assert!(w.as_ptr() != z.as_ptr())
204 fn test_clone_from() {
206 let three: Vec<Box<_>> = vec![box 1, box 2, box 3];
207 let two: Vec<Box<_>> = vec![box 4, box 5];
209 v.clone_from(&three);
210 assert_eq!(v, three);
213 v.clone_from(&three);
214 assert_eq!(v, three);
221 v.clone_from(&three);
227 let mut vec = vec![1, 2, 3, 4];
228 vec.retain(|&x| x % 2 == 0);
229 assert_eq!(vec, [2, 4]);
234 fn case(a: Vec<i32>, b: Vec<i32>) {
239 case(vec![], vec![]);
240 case(vec![1], vec![1]);
241 case(vec![1, 1], vec![1]);
242 case(vec![1, 2, 3], vec![1, 2, 3]);
243 case(vec![1, 1, 2, 3], vec![1, 2, 3]);
244 case(vec![1, 2, 2, 3], vec![1, 2, 3]);
245 case(vec![1, 2, 3, 3], vec![1, 2, 3]);
246 case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
250 fn test_dedup_by_key() {
251 fn case(a: Vec<i32>, b: Vec<i32>) {
253 v.dedup_by_key(|i| *i / 10);
256 case(vec![], vec![]);
257 case(vec![10], vec![10]);
258 case(vec![10, 11], vec![10]);
259 case(vec![10, 20, 30], vec![10, 20, 30]);
260 case(vec![10, 11, 20, 30], vec![10, 20, 30]);
261 case(vec![10, 20, 21, 30], vec![10, 20, 30]);
262 case(vec![10, 20, 30, 31], vec![10, 20, 30]);
263 case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
268 let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
269 vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
271 assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
273 let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
274 vec.dedup_by(|a, b| a.0 == b.0 && { b.1 += a.1; true });
276 assert_eq!(vec, [("foo", 3), ("bar", 12)]);
280 fn test_dedup_unique() {
281 let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
283 let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
285 let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
287 // If the boxed pointers were leaked or otherwise misused, valgrind
288 // and/or rt should raise errors.
292 fn zero_sized_values() {
293 let mut v = Vec::new();
294 assert_eq!(v.len(), 0);
296 assert_eq!(v.len(), 1);
298 assert_eq!(v.len(), 2);
299 assert_eq!(v.pop(), Some(()));
300 assert_eq!(v.pop(), Some(()));
301 assert_eq!(v.pop(), None);
303 assert_eq!(v.iter().count(), 0);
305 assert_eq!(v.iter().count(), 1);
307 assert_eq!(v.iter().count(), 2);
311 assert_eq!(v.iter_mut().count(), 2);
313 assert_eq!(v.iter_mut().count(), 3);
315 assert_eq!(v.iter_mut().count(), 4);
317 for &mut () in &mut v {}
321 assert_eq!(v.iter_mut().count(), 0);
325 fn test_partition() {
326 assert_eq!(vec![].into_iter().partition(|x: &i32| *x < 3),
328 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 4),
329 (vec![1, 2, 3], vec![]));
330 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 2),
331 (vec![1], vec![2, 3]));
332 assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 0),
333 (vec![], vec![1, 2, 3]));
337 fn test_zip_unzip() {
338 let z1 = vec![(1, 4), (2, 5), (3, 6)];
340 let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
342 assert_eq!((1, 4), (left[0], right[0]));
343 assert_eq!((2, 5), (left[1], right[1]));
344 assert_eq!((3, 6), (left[2], right[2]));
348 fn test_vec_truncate_drop() {
349 static mut DROPS: u32 = 0;
359 let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
360 assert_eq!(unsafe { DROPS }, 0);
362 assert_eq!(unsafe { DROPS }, 2);
364 assert_eq!(unsafe { DROPS }, 5);
369 fn test_vec_truncate_fail() {
371 impl Drop for BadElem {
373 let BadElem(ref mut x) = *self;
375 panic!("BadElem panic: 0xbadbeef")
380 let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
386 let vec = vec![1, 2, 3];
387 assert!(vec[1] == 2);
392 fn test_index_out_of_bounds() {
393 let vec = vec![1, 2, 3];
399 fn test_slice_out_of_bounds_1() {
400 let x = vec![1, 2, 3, 4, 5];
406 fn test_slice_out_of_bounds_2() {
407 let x = vec![1, 2, 3, 4, 5];
413 fn test_slice_out_of_bounds_3() {
414 let x = vec![1, 2, 3, 4, 5];
420 fn test_slice_out_of_bounds_4() {
421 let x = vec![1, 2, 3, 4, 5];
427 fn test_slice_out_of_bounds_5() {
428 let x = vec![1, 2, 3, 4, 5];
434 fn test_swap_remove_empty() {
435 let mut vec = Vec::<i32>::new();
440 fn test_move_items() {
441 let vec = vec![1, 2, 3];
442 let mut vec2 = vec![];
446 assert_eq!(vec2, [1, 2, 3]);
450 fn test_move_items_reverse() {
451 let vec = vec![1, 2, 3];
452 let mut vec2 = vec![];
453 for i in vec.into_iter().rev() {
456 assert_eq!(vec2, [3, 2, 1]);
460 fn test_move_items_zero_sized() {
461 let vec = vec![(), (), ()];
462 let mut vec2 = vec![];
466 assert_eq!(vec2, [(), (), ()]);
470 fn test_drain_items() {
471 let mut vec = vec![1, 2, 3];
472 let mut vec2 = vec![];
473 for i in vec.drain(..) {
477 assert_eq!(vec2, [1, 2, 3]);
481 fn test_drain_items_reverse() {
482 let mut vec = vec![1, 2, 3];
483 let mut vec2 = vec![];
484 for i in vec.drain(..).rev() {
488 assert_eq!(vec2, [3, 2, 1]);
492 fn test_drain_items_zero_sized() {
493 let mut vec = vec![(), (), ()];
494 let mut vec2 = vec![];
495 for i in vec.drain(..) {
499 assert_eq!(vec2, [(), (), ()]);
504 fn test_drain_out_of_bounds() {
505 let mut v = vec![1, 2, 3, 4, 5];
510 fn test_drain_range() {
511 let mut v = vec![1, 2, 3, 4, 5];
512 for _ in v.drain(4..) {
514 assert_eq!(v, &[1, 2, 3, 4]);
516 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
517 for _ in v.drain(1..4) {
519 assert_eq!(v, &[1.to_string(), 5.to_string()]);
521 let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
522 for _ in v.drain(1..4).rev() {
524 assert_eq!(v, &[1.to_string(), 5.to_string()]);
526 let mut v: Vec<_> = vec![(); 5];
527 for _ in v.drain(1..4).rev() {
529 assert_eq!(v, &[(), ()]);
533 fn test_drain_inclusive_range() {
534 let mut v = vec!['a', 'b', 'c', 'd', 'e'];
535 for _ in v.drain(1..=3) {
537 assert_eq!(v, &['a', 'e']);
539 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
540 for _ in v.drain(1..=5) {
542 assert_eq!(v, &["0".to_string()]);
544 let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
545 for _ in v.drain(0..=5) {
547 assert_eq!(v, Vec::<String>::new());
549 let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
550 for _ in v.drain(0..=3) {
552 assert_eq!(v, &["4".to_string(), "5".to_string()]);
554 let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
555 for _ in v.drain(..=0) {
557 assert_eq!(v, &["1".to_string()]);
561 fn test_drain_max_vec_size() {
562 let mut v = Vec::<()>::with_capacity(usize::max_value());
563 unsafe { v.set_len(usize::max_value()); }
564 for _ in v.drain(usize::max_value() - 1..) {
566 assert_eq!(v.len(), usize::max_value() - 1);
568 let mut v = Vec::<()>::with_capacity(usize::max_value());
569 unsafe { v.set_len(usize::max_value()); }
570 for _ in v.drain(usize::max_value() - 1..=usize::max_value() - 1) {
572 assert_eq!(v.len(), usize::max_value() - 1);
577 fn test_drain_inclusive_out_of_bounds() {
578 let mut v = vec![1, 2, 3, 4, 5];
584 let mut v = vec![1, 2, 3, 4, 5];
585 let a = [10, 11, 12];
586 v.splice(2..4, a.iter().cloned());
587 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
588 v.splice(1..3, Some(20));
589 assert_eq!(v, &[1, 20, 11, 12, 5]);
593 fn test_splice_inclusive_range() {
594 let mut v = vec![1, 2, 3, 4, 5];
595 let a = [10, 11, 12];
596 let t1: Vec<_> = v.splice(2..=3, a.iter().cloned()).collect();
597 assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
598 assert_eq!(t1, &[3, 4]);
599 let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
600 assert_eq!(v, &[1, 20, 11, 12, 5]);
601 assert_eq!(t2, &[2, 10]);
606 fn test_splice_out_of_bounds() {
607 let mut v = vec![1, 2, 3, 4, 5];
608 let a = [10, 11, 12];
609 v.splice(5..6, a.iter().cloned());
614 fn test_splice_inclusive_out_of_bounds() {
615 let mut v = vec![1, 2, 3, 4, 5];
616 let a = [10, 11, 12];
617 v.splice(5..=5, a.iter().cloned());
621 fn test_splice_items_zero_sized() {
622 let mut vec = vec![(), (), ()];
624 let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
625 assert_eq!(vec, &[(), ()]);
626 assert_eq!(t, &[()]);
630 fn test_splice_unbounded() {
631 let mut vec = vec![1, 2, 3, 4, 5];
632 let t: Vec<_> = vec.splice(.., None).collect();
633 assert_eq!(vec, &[]);
634 assert_eq!(t, &[1, 2, 3, 4, 5]);
638 fn test_splice_forget() {
639 let mut v = vec![1, 2, 3, 4, 5];
640 let a = [10, 11, 12];
641 std::mem::forget(v.splice(2..4, a.iter().cloned()));
642 assert_eq!(v, &[1, 2]);
646 fn test_into_boxed_slice() {
647 let xs = vec![1, 2, 3];
648 let ys = xs.into_boxed_slice();
649 assert_eq!(&*ys, [1, 2, 3]);
654 let mut vec = vec![1, 2, 3];
655 let mut vec2 = vec![4, 5, 6];
656 vec.append(&mut vec2);
657 assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
658 assert_eq!(vec2, []);
662 fn test_split_off() {
663 let mut vec = vec![1, 2, 3, 4, 5, 6];
664 let vec2 = vec.split_off(4);
665 assert_eq!(vec, [1, 2, 3, 4]);
666 assert_eq!(vec2, [5, 6]);
670 fn test_into_iter_as_slice() {
671 let vec = vec!['a', 'b', 'c'];
672 let mut into_iter = vec.into_iter();
673 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
674 let _ = into_iter.next().unwrap();
675 assert_eq!(into_iter.as_slice(), &['b', 'c']);
676 let _ = into_iter.next().unwrap();
677 let _ = into_iter.next().unwrap();
678 assert_eq!(into_iter.as_slice(), &[]);
682 fn test_into_iter_as_mut_slice() {
683 let vec = vec!['a', 'b', 'c'];
684 let mut into_iter = vec.into_iter();
685 assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
686 into_iter.as_mut_slice()[0] = 'x';
687 into_iter.as_mut_slice()[1] = 'y';
688 assert_eq!(into_iter.next().unwrap(), 'x');
689 assert_eq!(into_iter.as_slice(), &['y', 'c']);
693 fn test_into_iter_debug() {
694 let vec = vec!['a', 'b', 'c'];
695 let into_iter = vec.into_iter();
696 let debug = format!("{:?}", into_iter);
697 assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
701 fn test_into_iter_count() {
702 assert_eq!(vec![1, 2, 3].into_iter().count(), 3);
706 fn test_into_iter_clone() {
707 fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
708 let v: Vec<i32> = it.collect();
709 assert_eq!(&v[..], slice);
711 let mut it = vec![1, 2, 3].into_iter();
712 iter_equal(it.clone(), &[1, 2, 3]);
713 assert_eq!(it.next(), Some(1));
714 let mut it = it.rev();
715 iter_equal(it.clone(), &[3, 2]);
716 assert_eq!(it.next(), Some(3));
717 iter_equal(it.clone(), &[2]);
718 assert_eq!(it.next(), Some(2));
719 iter_equal(it.clone(), &[]);
720 assert_eq!(it.next(), None);
725 let borrowed: &[_] = &["borrowed", "(slice)"];
726 let owned = vec!["owned", "(vec)"];
727 match (Cow::from(owned.clone()), Cow::from(borrowed)) {
728 (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
729 _ => panic!("invalid `Cow::from`"),
735 let borrowed: &[_] = &["borrowed", "(slice)"];
736 let owned = vec!["owned", "(vec)"];
737 assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
738 assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
742 fn assert_covariance() {
743 fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
746 fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
752 fn from_into_inner() {
753 let vec = vec![1, 2, 3];
754 let ptr = vec.as_ptr();
755 let vec = vec.into_iter().collect::<Vec<_>>();
756 assert_eq!(vec, [1, 2, 3]);
757 assert_eq!(vec.as_ptr(), ptr);
759 let ptr = &vec[1] as *const _;
760 let mut it = vec.into_iter();
762 let vec = it.collect::<Vec<_>>();
763 assert_eq!(vec, [2, 3]);
764 assert!(ptr != vec.as_ptr());
768 fn overaligned_allocations() {
771 let mut v = vec![Foo(273)];
774 assert!(v[0].0 == 273);
775 assert!(v.as_ptr() as usize & 0xff == 0);
777 assert!(v[0].0 == 273);
778 assert!(v.as_ptr() as usize & 0xff == 0);
783 fn drain_filter_empty() {
784 let mut vec: Vec<i32> = vec![];
787 let mut iter = vec.drain_filter(|_| true);
788 assert_eq!(iter.size_hint(), (0, Some(0)));
789 assert_eq!(iter.next(), None);
790 assert_eq!(iter.size_hint(), (0, Some(0)));
791 assert_eq!(iter.next(), None);
792 assert_eq!(iter.size_hint(), (0, Some(0)));
794 assert_eq!(vec.len(), 0);
795 assert_eq!(vec, vec![]);
799 fn drain_filter_zst() {
800 let mut vec = vec![(), (), (), (), ()];
801 let initial_len = vec.len();
804 let mut iter = vec.drain_filter(|_| true);
805 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
806 while let Some(_) = iter.next() {
808 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
810 assert_eq!(iter.size_hint(), (0, Some(0)));
811 assert_eq!(iter.next(), None);
812 assert_eq!(iter.size_hint(), (0, Some(0)));
815 assert_eq!(count, initial_len);
816 assert_eq!(vec.len(), 0);
817 assert_eq!(vec, vec![]);
821 fn drain_filter_false() {
822 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
824 let initial_len = vec.len();
827 let mut iter = vec.drain_filter(|_| false);
828 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
829 for _ in iter.by_ref() {
832 assert_eq!(iter.size_hint(), (0, Some(0)));
833 assert_eq!(iter.next(), None);
834 assert_eq!(iter.size_hint(), (0, Some(0)));
837 assert_eq!(count, 0);
838 assert_eq!(vec.len(), initial_len);
839 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
843 fn drain_filter_true() {
844 let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
846 let initial_len = vec.len();
849 let mut iter = vec.drain_filter(|_| true);
850 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
851 while let Some(_) = iter.next() {
853 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
855 assert_eq!(iter.size_hint(), (0, Some(0)));
856 assert_eq!(iter.next(), None);
857 assert_eq!(iter.size_hint(), (0, Some(0)));
860 assert_eq!(count, initial_len);
861 assert_eq!(vec.len(), 0);
862 assert_eq!(vec, vec![]);
866 fn drain_filter_complex() {
868 { // [+xxx++++++xxxxx++++x+x++]
869 let mut vec = vec![1,
871 7, 9, 11, 13, 15, 17,
879 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
880 assert_eq!(removed.len(), 10);
881 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
883 assert_eq!(vec.len(), 14);
884 assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
887 { // [xxx++++++xxxxx++++x+x++]
888 let mut vec = vec![2, 4, 6,
889 7, 9, 11, 13, 15, 17,
897 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
898 assert_eq!(removed.len(), 10);
899 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
901 assert_eq!(vec.len(), 13);
902 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
905 { // [xxx++++++xxxxx++++x+x]
906 let mut vec = vec![2, 4, 6,
907 7, 9, 11, 13, 15, 17,
914 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
915 assert_eq!(removed.len(), 10);
916 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
918 assert_eq!(vec.len(), 11);
919 assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
922 { // [xxxxxxxxxx+++++++++++]
923 let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
924 1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
926 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
927 assert_eq!(removed.len(), 10);
928 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
930 assert_eq!(vec.len(), 10);
931 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
934 { // [+++++++++++xxxxxxxxxx]
935 let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
936 2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
938 let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
939 assert_eq!(removed.len(), 10);
940 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
942 assert_eq!(vec.len(), 10);
943 assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
947 // FIXME: re-enable emscripten once it can unwind again
949 #[cfg(not(target_os = "emscripten"))]
950 fn drain_filter_consumed_panic() {
952 use std::sync::Mutex;
956 drop_counts: Rc<Mutex<Vec<usize>>>,
959 impl Drop for Check {
961 self.drop_counts.lock().unwrap()[self.index] += 1;
962 println!("drop: {}", self.index);
966 let check_count = 10;
967 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
968 let mut data: Vec<Check> = (0..check_count)
969 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
972 let _ = std::panic::catch_unwind(move || {
973 let filter = |c: &mut Check| {
975 panic!("panic at index: {}", c.index);
977 // Verify that if the filter could panic again on another element
978 // that it would not cause a double panic and all elements of the
979 // vec would still be dropped exactly once.
981 panic!("panic at index: {}", c.index);
985 let drain = data.drain_filter(filter);
987 // NOTE: The DrainFilter is explicitly consumed
988 drain.for_each(drop);
991 let drop_counts = drop_counts.lock().unwrap();
992 assert_eq!(check_count, drop_counts.len());
994 for (index, count) in drop_counts.iter().cloned().enumerate() {
995 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
999 // FIXME: Re-enable emscripten once it can catch panics
1001 #[cfg(not(target_os = "emscripten"))]
1002 fn drain_filter_unconsumed_panic() {
1004 use std::sync::Mutex;
1008 drop_counts: Rc<Mutex<Vec<usize>>>,
1011 impl Drop for Check {
1012 fn drop(&mut self) {
1013 self.drop_counts.lock().unwrap()[self.index] += 1;
1014 println!("drop: {}", self.index);
1018 let check_count = 10;
1019 let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1020 let mut data: Vec<Check> = (0..check_count)
1021 .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1024 let _ = std::panic::catch_unwind(move || {
1025 let filter = |c: &mut Check| {
1027 panic!("panic at index: {}", c.index);
1029 // Verify that if the filter could panic again on another element
1030 // that it would not cause a double panic and all elements of the
1031 // vec would still be dropped exactly once.
1033 panic!("panic at index: {}", c.index);
1037 let _drain = data.drain_filter(filter);
1039 // NOTE: The DrainFilter is dropped without being consumed
1042 let drop_counts = drop_counts.lock().unwrap();
1043 assert_eq!(check_count, drop_counts.len());
1045 for (index, count) in drop_counts.iter().cloned().enumerate() {
1046 assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1051 fn drain_filter_unconsumed() {
1052 let mut vec = vec![1, 2, 3, 4];
1053 let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1055 assert_eq!(vec, [2, 4]);
1059 fn test_reserve_exact() {
1060 // This is all the same as test_reserve
1062 let mut v = Vec::new();
1063 assert_eq!(v.capacity(), 0);
1066 assert!(v.capacity() >= 2);
1072 assert!(v.capacity() >= 16);
1073 v.reserve_exact(16);
1074 assert!(v.capacity() >= 32);
1078 v.reserve_exact(16);
1079 assert!(v.capacity() >= 33)
1083 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1084 fn test_try_reserve() {
1086 // These are the interesting cases:
1087 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1088 // * > isize::MAX should always fail
1089 // * On 16/32-bit should CapacityOverflow
1090 // * On 64-bit should OOM
1091 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1092 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1094 const MAX_CAP: usize = isize::MAX as usize;
1095 const MAX_USIZE: usize = usize::MAX;
1097 // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1098 // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1099 // Any platform that succeeds for these requests is technically broken with
1100 // ptr::offset because LLVM is the worst.
1101 let guards_against_isize = size_of::<usize>() < 8;
1104 // Note: basic stuff is checked by test_reserve
1105 let mut empty_bytes: Vec<u8> = Vec::new();
1107 // Check isize::MAX doesn't count as an overflow
1108 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1109 panic!("isize::MAX shouldn't trigger an overflow!");
1111 // Play it again, frank! (just to be sure)
1112 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1113 panic!("isize::MAX shouldn't trigger an overflow!");
1116 if guards_against_isize {
1117 // Check isize::MAX + 1 does count as overflow
1118 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
1119 } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1121 // Check usize::MAX does count as overflow
1122 if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
1123 } else { panic!("usize::MAX should trigger an overflow!") }
1125 // Check isize::MAX + 1 is an OOM
1126 if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_CAP + 1) {
1127 } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1129 // Check usize::MAX is an OOM
1130 if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE) {
1131 } else { panic!("usize::MAX should trigger an OOM!") }
1137 // Same basic idea, but with non-zero len
1138 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1140 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1141 panic!("isize::MAX shouldn't trigger an overflow!");
1143 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1144 panic!("isize::MAX shouldn't trigger an overflow!");
1146 if guards_against_isize {
1147 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
1148 } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1150 if let Err(AllocError { .. }) = ten_bytes.try_reserve(MAX_CAP - 9) {
1151 } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1153 // Should always overflow in the add-to-len
1154 if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
1155 } else { panic!("usize::MAX should trigger an overflow!") }
1160 // Same basic idea, but with interesting type size
1161 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1163 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1164 panic!("isize::MAX shouldn't trigger an overflow!");
1166 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1167 panic!("isize::MAX shouldn't trigger an overflow!");
1169 if guards_against_isize {
1170 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1171 } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1173 if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1174 } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1176 // Should fail in the mul-by-size
1177 if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
1179 panic!("usize::MAX should trigger an overflow!");
1186 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1187 fn test_try_reserve_exact() {
1189 // This is exactly the same as test_try_reserve with the method changed.
1190 // See that test for comments.
1192 const MAX_CAP: usize = isize::MAX as usize;
1193 const MAX_USIZE: usize = usize::MAX;
1195 let guards_against_isize = size_of::<usize>() < 8;
1198 let mut empty_bytes: Vec<u8> = Vec::new();
1200 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1201 panic!("isize::MAX shouldn't trigger an overflow!");
1203 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1204 panic!("isize::MAX shouldn't trigger an overflow!");
1207 if guards_against_isize {
1208 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1209 } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1211 if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1212 } else { panic!("usize::MAX should trigger an overflow!") }
1214 if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1215 } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1217 if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1218 } else { panic!("usize::MAX should trigger an OOM!") }
1224 let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1226 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1227 panic!("isize::MAX shouldn't trigger an overflow!");
1229 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1230 panic!("isize::MAX shouldn't trigger an overflow!");
1232 if guards_against_isize {
1233 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1234 } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1236 if let Err(AllocError { .. }) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1237 } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1239 if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
1240 } else { panic!("usize::MAX should trigger an overflow!") }
1245 let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1247 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1248 panic!("isize::MAX shouldn't trigger an overflow!");
1250 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1251 panic!("isize::MAX shouldn't trigger an overflow!");
1253 if guards_against_isize {
1254 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1255 } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1257 if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1258 } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1260 if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
1261 } else { panic!("usize::MAX should trigger an overflow!") }
1267 fn test_stable_push_pop() {
1268 // Test that, if we reserved enough space, adding and removing elements does not
1269 // invalidate references into the vector (such as `v0`). This test also
1270 // runs in Miri, which would detect such problems.
1271 let mut v = Vec::with_capacity(10);
1274 // laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1275 let v0 = unsafe { &*(&v[0] as *const _) };
1277 // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1281 assert_eq!(*v0, 13);
1284 assert_eq!(*v0, 13);
1287 // https://github.com/rust-lang/rust/pull/49496 introduced specialization based on:
1290 // unsafe impl<T: ?Sized> IsZero for *mut T {
1291 // fn is_zero(&self) -> bool {
1292 // (*self).is_null()
1297 // … to call `RawVec::with_capacity_zeroed` for creating `Vec<*mut T>`,
1298 // which is incorrect for fat pointers since `<*mut T>::is_null` only looks at the data component.
1299 // That is, a fat pointer can be “null” without being made entirely of zero bits.
1301 fn vec_macro_repeating_null_raw_fat_pointer() {
1302 let raw_dyn = &mut (|| ()) as &mut dyn Fn() as *mut dyn Fn();
1303 let vtable = dbg!(ptr_metadata(raw_dyn));
1304 let null_raw_dyn = ptr_from_raw_parts(std::ptr::null_mut(), vtable);
1305 assert!(null_raw_dyn.is_null());
1307 let vec = vec![null_raw_dyn; 1];
1308 dbg!(ptr_metadata(vec[0]));
1309 assert!(vec[0] == null_raw_dyn);
1311 // Polyfill for https://github.com/rust-lang/rfcs/pull/2580
1313 fn ptr_metadata(ptr: *mut dyn Fn()) -> *mut () {
1315 std::mem::transmute::<*mut dyn Fn(), DynRepr>(ptr).vtable
1319 fn ptr_from_raw_parts(data: *mut (), vtable: *mut()) -> *mut dyn Fn() {
1321 std::mem::transmute::<DynRepr, *mut dyn Fn()>(DynRepr {