src/liballoc/tests/vec.rs

   1 use std::borrow::Cow;
   2 use std::mem::size_of;
   3 use std::{usize, isize};
   4 use std::vec::{Drain, IntoIter};
   5 use std::collections::TryReserveError::*;
   6
   7 struct DropCounter<'a> {
   8     count: &'a mut u32,
   9 }
  10
  11 impl Drop for DropCounter<'_> {
  12     fn drop(&mut self) {
  13         *self.count += 1;
  14     }
  15 }
  16
  17 #[test]
  18 fn test_small_vec_struct() {
  19     assert!(size_of::<Vec<u8>>() == size_of::<usize>() * 3);
  20 }
  21
  22 #[test]
  23 fn test_double_drop() {
  24     struct TwoVec<T> {
  25         x: Vec<T>,
  26         y: Vec<T>,
  27     }
  28
  29     let (mut count_x, mut count_y) = (0, 0);
  30     {
  31         let mut tv = TwoVec {
  32             x: Vec::new(),
  33             y: Vec::new(),
  34         };
  35         tv.x.push(DropCounter { count: &mut count_x });
  36         tv.y.push(DropCounter { count: &mut count_y });
  37
  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.
  41         drop(tv.x);
  42
  43         // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
  44     }
  45
  46     assert_eq!(count_x, 1);
  47     assert_eq!(count_y, 1);
  48 }
  49
  50 #[test]
  51 fn test_reserve() {
  52     let mut v = Vec::new();
  53     assert_eq!(v.capacity(), 0);
  54
  55     v.reserve(2);
  56     assert!(v.capacity() >= 2);
  57
  58     for i in 0..16 {
  59         v.push(i);
  60     }
  61
  62     assert!(v.capacity() >= 16);
  63     v.reserve(16);
  64     assert!(v.capacity() >= 32);
  65
  66     v.push(16);
  67
  68     v.reserve(16);
  69     assert!(v.capacity() >= 33)
  70 }
  71
  72 #[test]
  73 fn test_zst_capacity() {
  74     assert_eq!(Vec::<()>::new().capacity(), usize::max_value());
  75 }
  76
  77 #[test]
  78 fn test_extend() {
  79     let mut v = Vec::new();
  80     let mut w = Vec::new();
  81
  82     v.extend(w.clone());
  83     assert_eq!(v, &[]);
  84
  85     v.extend(0..3);
  86     for i in 0..3 {
  87         w.push(i)
  88     }
  89
  90     assert_eq!(v, w);
  91
  92     v.extend(3..10);
  93     for i in 3..10 {
  94         w.push(i)
  95     }
  96
  97     assert_eq!(v, w);
  98
  99     v.extend(w.clone()); // specializes to `append`
 100     assert!(v.iter().eq(w.iter().chain(w.iter())));
 101
 102     // Zero sized types
 103     #[derive(PartialEq, Debug)]
 104     struct Foo;
 105
 106     let mut a = Vec::new();
 107     let b = vec![Foo, Foo];
 108
 109     a.extend(b);
 110     assert_eq!(a, &[Foo, Foo]);
 111
 112     // Double drop
 113     let mut count_x = 0;
 114     {
 115         let mut x = Vec::new();
 116         let y = vec![DropCounter { count: &mut count_x }];
 117         x.extend(y);
 118     }
 119     assert_eq!(count_x, 1);
 120 }
 121
 122 #[test]
 123 fn test_extend_ref() {
 124     let mut v = vec![1, 2];
 125     v.extend(&[3, 4, 5]);
 126
 127     assert_eq!(v.len(), 5);
 128     assert_eq!(v, [1, 2, 3, 4, 5]);
 129
 130     let w = vec![6, 7];
 131     v.extend(&w);
 132
 133     assert_eq!(v.len(), 7);
 134     assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
 135 }
 136
 137 #[test]
 138 fn test_slice_from_mut() {
 139     let mut values = vec![1, 2, 3, 4, 5];
 140     {
 141         let slice = &mut values[2..];
 142         assert!(slice == [3, 4, 5]);
 143         for p in slice {
 144             *p += 2;
 145         }
 146     }
 147
 148     assert!(values == [1, 2, 5, 6, 7]);
 149 }
 150
 151 #[test]
 152 fn test_slice_to_mut() {
 153     let mut values = vec![1, 2, 3, 4, 5];
 154     {
 155         let slice = &mut values[..2];
 156         assert!(slice == [1, 2]);
 157         for p in slice {
 158             *p += 1;
 159         }
 160     }
 161
 162     assert!(values == [2, 3, 3, 4, 5]);
 163 }
 164
 165 #[test]
 166 fn test_split_at_mut() {
 167     let mut values = vec![1, 2, 3, 4, 5];
 168     {
 169         let (left, right) = values.split_at_mut(2);
 170         {
 171             let left: &[_] = left;
 172             assert!(&left[..left.len()] == &[1, 2]);
 173         }
 174         for p in left {
 175             *p += 1;
 176         }
 177
 178         {
 179             let right: &[_] = right;
 180             assert!(&right[..right.len()] == &[3, 4, 5]);
 181         }
 182         for p in right {
 183             *p += 2;
 184         }
 185     }
 186
 187     assert_eq!(values, [2, 3, 5, 6, 7]);
 188 }
 189
 190 #[test]
 191 fn test_clone() {
 192     let v: Vec<i32> = vec![];
 193     let w = vec![1, 2, 3];
 194
 195     assert_eq!(v, v.clone());
 196
 197     let z = w.clone();
 198     assert_eq!(w, z);
 199     // they should be disjoint in memory.
 200     assert!(w.as_ptr() != z.as_ptr())
 201 }
 202
 203 #[test]
 204 fn test_clone_from() {
 205     let mut v = vec![];
 206     let three: Vec<Box<_>> = vec![box 1, box 2, box 3];
 207     let two: Vec<Box<_>> = vec![box 4, box 5];
 208     // zero, long
 209     v.clone_from(&three);
 210     assert_eq!(v, three);
 211
 212     // equal
 213     v.clone_from(&three);
 214     assert_eq!(v, three);
 215
 216     // long, short
 217     v.clone_from(&two);
 218     assert_eq!(v, two);
 219
 220     // short, long
 221     v.clone_from(&three);
 222     assert_eq!(v, three)
 223 }
 224
 225 #[test]
 226 fn test_retain() {
 227     let mut vec = vec![1, 2, 3, 4];
 228     vec.retain(|&x| x % 2 == 0);
 229     assert_eq!(vec, [2, 4]);
 230 }
 231
 232 #[test]
 233 fn test_dedup() {
 234     fn case(a: Vec<i32>, b: Vec<i32>) {
 235         let mut v = a;
 236         v.dedup();
 237         assert_eq!(v, b);
 238     }
 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]);
 247 }
 248
 249 #[test]
 250 fn test_dedup_by_key() {
 251     fn case(a: Vec<i32>, b: Vec<i32>) {
 252         let mut v = a;
 253         v.dedup_by_key(|i| *i / 10);
 254         assert_eq!(v, b);
 255     }
 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]);
 264 }
 265
 266 #[test]
 267 fn test_dedup_by() {
 268     let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
 269     vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
 270
 271     assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
 272
 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 });
 275
 276     assert_eq!(vec, [("foo", 3), ("bar", 12)]);
 277 }
 278
 279 #[test]
 280 fn test_dedup_unique() {
 281     let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
 282     v0.dedup();
 283     let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
 284     v1.dedup();
 285     let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
 286     v2.dedup();
 287     // If the boxed pointers were leaked or otherwise misused, valgrind
 288     // and/or rt should raise errors.
 289 }
 290
 291 #[test]
 292 fn zero_sized_values() {
 293     let mut v = Vec::new();
 294     assert_eq!(v.len(), 0);
 295     v.push(());
 296     assert_eq!(v.len(), 1);
 297     v.push(());
 298     assert_eq!(v.len(), 2);
 299     assert_eq!(v.pop(), Some(()));
 300     assert_eq!(v.pop(), Some(()));
 301     assert_eq!(v.pop(), None);
 302
 303     assert_eq!(v.iter().count(), 0);
 304     v.push(());
 305     assert_eq!(v.iter().count(), 1);
 306     v.push(());
 307     assert_eq!(v.iter().count(), 2);
 308
 309     for &() in &v {}
 310
 311     assert_eq!(v.iter_mut().count(), 2);
 312     v.push(());
 313     assert_eq!(v.iter_mut().count(), 3);
 314     v.push(());
 315     assert_eq!(v.iter_mut().count(), 4);
 316
 317     for &mut () in &mut v {}
 318     unsafe {
 319         v.set_len(0);
 320     }
 321     assert_eq!(v.iter_mut().count(), 0);
 322 }
 323
 324 #[test]
 325 fn test_partition() {
 326     assert_eq!(vec![].into_iter().partition(|x: &i32| *x < 3),
 327                (vec![], vec![]));
 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]));
 334 }
 335
 336 #[test]
 337 fn test_zip_unzip() {
 338     let z1 = vec![(1, 4), (2, 5), (3, 6)];
 339
 340     let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
 341
 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]));
 345 }
 346
 347 #[test]
 348 fn test_vec_truncate_drop() {
 349     static mut DROPS: u32 = 0;
 350     struct Elem(i32);
 351     impl Drop for Elem {
 352         fn drop(&mut self) {
 353             unsafe {
 354                 DROPS += 1;
 355             }
 356         }
 357     }
 358
 359     let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
 360     assert_eq!(unsafe { DROPS }, 0);
 361     v.truncate(3);
 362     assert_eq!(unsafe { DROPS }, 2);
 363     v.truncate(0);
 364     assert_eq!(unsafe { DROPS }, 5);
 365 }
 366
 367 #[test]
 368 #[should_panic]
 369 fn test_vec_truncate_fail() {
 370     struct BadElem(i32);
 371     impl Drop for BadElem {
 372         fn drop(&mut self) {
 373             let BadElem(ref mut x) = *self;
 374             if *x == 0xbadbeef {
 375                 panic!("BadElem panic: 0xbadbeef")
 376             }
 377         }
 378     }
 379
 380     let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
 381     v.truncate(0);
 382 }
 383
 384 #[test]
 385 fn test_index() {
 386     let vec = vec![1, 2, 3];
 387     assert!(vec[1] == 2);
 388 }
 389
 390 #[test]
 391 #[should_panic]
 392 fn test_index_out_of_bounds() {
 393     let vec = vec![1, 2, 3];
 394     let _ = vec[3];
 395 }
 396
 397 #[test]
 398 #[should_panic]
 399 fn test_slice_out_of_bounds_1() {
 400     let x = vec![1, 2, 3, 4, 5];
 401     &x[!0..];
 402 }
 403
 404 #[test]
 405 #[should_panic]
 406 fn test_slice_out_of_bounds_2() {
 407     let x = vec![1, 2, 3, 4, 5];
 408     &x[..6];
 409 }
 410
 411 #[test]
 412 #[should_panic]
 413 fn test_slice_out_of_bounds_3() {
 414     let x = vec![1, 2, 3, 4, 5];
 415     &x[!0..4];
 416 }
 417
 418 #[test]
 419 #[should_panic]
 420 fn test_slice_out_of_bounds_4() {
 421     let x = vec![1, 2, 3, 4, 5];
 422     &x[1..6];
 423 }
 424
 425 #[test]
 426 #[should_panic]
 427 fn test_slice_out_of_bounds_5() {
 428     let x = vec![1, 2, 3, 4, 5];
 429     &x[3..2];
 430 }
 431
 432 #[test]
 433 #[should_panic]
 434 fn test_swap_remove_empty() {
 435     let mut vec = Vec::<i32>::new();
 436     vec.swap_remove(0);
 437 }
 438
 439 #[test]
 440 fn test_move_items() {
 441     let vec = vec![1, 2, 3];
 442     let mut vec2 = vec![];
 443     for i in vec {
 444         vec2.push(i);
 445     }
 446     assert_eq!(vec2, [1, 2, 3]);
 447 }
 448
 449 #[test]
 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() {
 454         vec2.push(i);
 455     }
 456     assert_eq!(vec2, [3, 2, 1]);
 457 }
 458
 459 #[test]
 460 fn test_move_items_zero_sized() {
 461     let vec = vec![(), (), ()];
 462     let mut vec2 = vec![];
 463     for i in vec {
 464         vec2.push(i);
 465     }
 466     assert_eq!(vec2, [(), (), ()]);
 467 }
 468
 469 #[test]
 470 fn test_drain_items() {
 471     let mut vec = vec![1, 2, 3];
 472     let mut vec2 = vec![];
 473     for i in vec.drain(..) {
 474         vec2.push(i);
 475     }
 476     assert_eq!(vec, []);
 477     assert_eq!(vec2, [1, 2, 3]);
 478 }
 479
 480 #[test]
 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() {
 485         vec2.push(i);
 486     }
 487     assert_eq!(vec, []);
 488     assert_eq!(vec2, [3, 2, 1]);
 489 }
 490
 491 #[test]
 492 fn test_drain_items_zero_sized() {
 493     let mut vec = vec![(), (), ()];
 494     let mut vec2 = vec![];
 495     for i in vec.drain(..) {
 496         vec2.push(i);
 497     }
 498     assert_eq!(vec, []);
 499     assert_eq!(vec2, [(), (), ()]);
 500 }
 501
 502 #[test]
 503 #[should_panic]
 504 fn test_drain_out_of_bounds() {
 505     let mut v = vec![1, 2, 3, 4, 5];
 506     v.drain(5..6);
 507 }
 508
 509 #[test]
 510 fn test_drain_range() {
 511     let mut v = vec![1, 2, 3, 4, 5];
 512     for _ in v.drain(4..) {
 513     }
 514     assert_eq!(v, &[1, 2, 3, 4]);
 515
 516     let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
 517     for _ in v.drain(1..4) {
 518     }
 519     assert_eq!(v, &[1.to_string(), 5.to_string()]);
 520
 521     let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
 522     for _ in v.drain(1..4).rev() {
 523     }
 524     assert_eq!(v, &[1.to_string(), 5.to_string()]);
 525
 526     let mut v: Vec<_> = vec![(); 5];
 527     for _ in v.drain(1..4).rev() {
 528     }
 529     assert_eq!(v, &[(), ()]);
 530 }
 531
 532 #[test]
 533 fn test_drain_inclusive_range() {
 534     let mut v = vec!['a', 'b', 'c', 'd', 'e'];
 535     for _ in v.drain(1..=3) {
 536     }
 537     assert_eq!(v, &['a', 'e']);
 538
 539     let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
 540     for _ in v.drain(1..=5) {
 541     }
 542     assert_eq!(v, &["0".to_string()]);
 543
 544     let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
 545     for _ in v.drain(0..=5) {
 546     }
 547     assert_eq!(v, Vec::<String>::new());
 548
 549     let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
 550     for _ in v.drain(0..=3) {
 551     }
 552     assert_eq!(v, &["4".to_string(), "5".to_string()]);
 553
 554     let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
 555     for _ in v.drain(..=0) {
 556     }
 557     assert_eq!(v, &["1".to_string()]);
 558 }
 559
 560 #[test]
 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..) {
 565     }
 566     assert_eq!(v.len(), usize::max_value() - 1);
 567
 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) {
 571     }
 572     assert_eq!(v.len(), usize::max_value() - 1);
 573 }
 574
 575 #[test]
 576 #[should_panic]
 577 fn test_drain_inclusive_out_of_bounds() {
 578     let mut v = vec![1, 2, 3, 4, 5];
 579     v.drain(5..=5);
 580 }
 581
 582 #[test]
 583 fn test_splice() {
 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]);
 590 }
 591
 592 #[test]
 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]);
 602 }
 603
 604 #[test]
 605 #[should_panic]
 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());
 610 }
 611
 612 #[test]
 613 #[should_panic]
 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());
 618 }
 619
 620 #[test]
 621 fn test_splice_items_zero_sized() {
 622     let mut vec = vec![(), (), ()];
 623     let vec2 = vec![];
 624     let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
 625     assert_eq!(vec, &[(), ()]);
 626     assert_eq!(t, &[()]);
 627 }
 628
 629 #[test]
 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]);
 635 }
 636
 637 #[test]
 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]);
 643 }
 644
 645 #[test]
 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]);
 650 }
 651
 652 #[test]
 653 fn test_append() {
 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, []);
 659 }
 660
 661 #[test]
 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]);
 667 }
 668
 669 #[test]
 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(), &[]);
 679 }
 680
 681 #[test]
 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']);
 690 }
 691
 692 #[test]
 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'])");
 698 }
 699
 700 #[test]
 701 fn test_into_iter_count() {
 702     assert_eq!(vec![1, 2, 3].into_iter().count(), 3);
 703 }
 704
 705 #[test]
 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);
 710     }
 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);
 721 }
 722
 723 #[test]
 724 fn test_cow_from() {
 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`"),
 730     }
 731 }
 732
 733 #[test]
 734 fn test_from_cow() {
 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)"]);
 739 }
 740
 741 #[allow(dead_code)]
 742 fn assert_covariance() {
 743     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 744         d
 745     }
 746     fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
 747         i
 748     }
 749 }
 750
 751 #[test]
 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);
 758
 759     let ptr = &vec[1] as *const _;
 760     let mut it = vec.into_iter();
 761     it.next().unwrap();
 762     let vec = it.collect::<Vec<_>>();
 763     assert_eq!(vec, [2, 3]);
 764     assert!(ptr != vec.as_ptr());
 765 }
 766
 767 #[test]
 768 fn overaligned_allocations() {
 769     #[repr(align(256))]
 770     struct Foo(usize);
 771     let mut v = vec![Foo(273)];
 772     for i in 0..0x1000 {
 773         v.reserve_exact(i);
 774         assert!(v[0].0 == 273);
 775         assert!(v.as_ptr() as usize & 0xff == 0);
 776         v.shrink_to_fit();
 777         assert!(v[0].0 == 273);
 778         assert!(v.as_ptr() as usize & 0xff == 0);
 779     }
 780 }
 781
 782 #[test]
 783 fn drain_filter_empty() {
 784     let mut vec: Vec<i32> = vec![];
 785
 786     {
 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)));
 793     }
 794     assert_eq!(vec.len(), 0);
 795     assert_eq!(vec, vec![]);
 796 }
 797
 798 #[test]
 799 fn drain_filter_zst() {
 800     let mut vec = vec![(), (), (), (), ()];
 801     let initial_len = vec.len();
 802     let mut count = 0;
 803     {
 804         let mut iter = vec.drain_filter(|_| true);
 805         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 806         while let Some(_) = iter.next() {
 807             count += 1;
 808             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 809         }
 810         assert_eq!(iter.size_hint(), (0, Some(0)));
 811         assert_eq!(iter.next(), None);
 812         assert_eq!(iter.size_hint(), (0, Some(0)));
 813     }
 814
 815     assert_eq!(count, initial_len);
 816     assert_eq!(vec.len(), 0);
 817     assert_eq!(vec, vec![]);
 818 }
 819
 820 #[test]
 821 fn drain_filter_false() {
 822     let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 823
 824     let initial_len = vec.len();
 825     let mut count = 0;
 826     {
 827         let mut iter = vec.drain_filter(|_| false);
 828         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 829         for _ in iter.by_ref() {
 830             count += 1;
 831         }
 832         assert_eq!(iter.size_hint(), (0, Some(0)));
 833         assert_eq!(iter.next(), None);
 834         assert_eq!(iter.size_hint(), (0, Some(0)));
 835     }
 836
 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]);
 840 }
 841
 842 #[test]
 843 fn drain_filter_true() {
 844     let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 845
 846     let initial_len = vec.len();
 847     let mut count = 0;
 848     {
 849         let mut iter = vec.drain_filter(|_| true);
 850         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 851         while let Some(_) = iter.next() {
 852             count += 1;
 853             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 854         }
 855         assert_eq!(iter.size_hint(), (0, Some(0)));
 856         assert_eq!(iter.next(), None);
 857         assert_eq!(iter.size_hint(), (0, Some(0)));
 858     }
 859
 860     assert_eq!(count, initial_len);
 861     assert_eq!(vec.len(), 0);
 862     assert_eq!(vec, vec![]);
 863 }
 864
 865 #[test]
 866 fn drain_filter_complex() {
 867
 868     {   //                [+xxx++++++xxxxx++++x+x++]
 869         let mut vec = vec![1,
 870                            2, 4, 6,
 871                            7, 9, 11, 13, 15, 17,
 872                            18, 20, 22, 24, 26,
 873                            27, 29, 31, 33,
 874                            34,
 875                            35,
 876                            36,
 877                            37, 39];
 878
 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]);
 882
 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]);
 885     }
 886
 887     {   //                [xxx++++++xxxxx++++x+x++]
 888         let mut vec = vec![2, 4, 6,
 889                            7, 9, 11, 13, 15, 17,
 890                            18, 20, 22, 24, 26,
 891                            27, 29, 31, 33,
 892                            34,
 893                            35,
 894                            36,
 895                            37, 39];
 896
 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]);
 900
 901         assert_eq!(vec.len(), 13);
 902         assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
 903     }
 904
 905     {   //                [xxx++++++xxxxx++++x+x]
 906         let mut vec = vec![2, 4, 6,
 907                            7, 9, 11, 13, 15, 17,
 908                            18, 20, 22, 24, 26,
 909                            27, 29, 31, 33,
 910                            34,
 911                            35,
 912                            36];
 913
 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]);
 917
 918         assert_eq!(vec.len(), 11);
 919         assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
 920     }
 921
 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];
 925
 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]);
 929
 930         assert_eq!(vec.len(), 10);
 931         assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 932     }
 933
 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];
 937
 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]);
 941
 942         assert_eq!(vec.len(), 10);
 943         assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 944     }
 945 }
 946
 947 #[test]
 948 #[cfg(not(miri))] // Miri does not support catching panics
 949 fn drain_filter_consumed_panic() {
 950     use std::rc::Rc;
 951     use std::sync::Mutex;
 952
 953     struct Check {
 954         index: usize,
 955         drop_counts: Rc<Mutex<Vec<usize>>>,
 956     };
 957
 958     impl Drop for Check {
 959         fn drop(&mut self) {
 960             self.drop_counts.lock().unwrap()[self.index] += 1;
 961             println!("drop: {}", self.index);
 962         }
 963     }
 964
 965     let check_count = 10;
 966     let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
 967     let mut data: Vec<Check> = (0..check_count)
 968         .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
 969         .collect();
 970
 971     let _ = std::panic::catch_unwind(move || {
 972         let filter = |c: &mut Check| {
 973             if c.index == 2 {
 974                 panic!("panic at index: {}", c.index);
 975             }
 976             // Verify that if the filter could panic again on another element
 977             // that it would not cause a double panic and all elements of the
 978             // vec would still be dropped exactly once.
 979             if c.index == 4 {
 980                 panic!("panic at index: {}", c.index);
 981             }
 982             c.index < 6
 983         };
 984         let drain = data.drain_filter(filter);
 985
 986         // NOTE: The DrainFilter is explictly consumed
 987         drain.for_each(drop);
 988     });
 989
 990     let drop_counts = drop_counts.lock().unwrap();
 991     assert_eq!(check_count, drop_counts.len());
 992
 993     for (index, count) in drop_counts.iter().cloned().enumerate() {
 994         assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
 995     }
 996 }
 997
 998 #[test]
 999 #[cfg(not(miri))] // Miri does not support catching panics
1000 fn drain_filter_unconsumed_panic() {
1001     use std::rc::Rc;
1002     use std::sync::Mutex;
1003
1004     struct Check {
1005         index: usize,
1006         drop_counts: Rc<Mutex<Vec<usize>>>,
1007     };
1008
1009     impl Drop for Check {
1010         fn drop(&mut self) {
1011             self.drop_counts.lock().unwrap()[self.index] += 1;
1012             println!("drop: {}", self.index);
1013         }
1014     }
1015
1016     let check_count = 10;
1017     let drop_counts = Rc::new(Mutex::new(vec![0_usize; check_count]));
1018     let mut data: Vec<Check> = (0..check_count)
1019         .map(|index| Check { index, drop_counts: Rc::clone(&drop_counts) })
1020         .collect();
1021
1022     let _ = std::panic::catch_unwind(move || {
1023         let filter = |c: &mut Check| {
1024             if c.index == 2 {
1025                 panic!("panic at index: {}", c.index);
1026             }
1027             // Verify that if the filter could panic again on another element
1028             // that it would not cause a double panic and all elements of the
1029             // vec would still be dropped exactly once.
1030             if c.index == 4 {
1031                 panic!("panic at index: {}", c.index);
1032             }
1033             c.index < 6
1034         };
1035         let _drain = data.drain_filter(filter);
1036
1037         // NOTE: The DrainFilter is dropped without being consumed
1038     });
1039
1040     let drop_counts = drop_counts.lock().unwrap();
1041     assert_eq!(check_count, drop_counts.len());
1042
1043     for (index, count) in drop_counts.iter().cloned().enumerate() {
1044         assert_eq!(1, count, "unexpected drop count at index: {} (count: {})", index, count);
1045     }
1046 }
1047
1048 #[test]
1049 fn drain_filter_unconsumed() {
1050     let mut vec = vec![1, 2, 3, 4];
1051     let drain = vec.drain_filter(|&mut x| x % 2 != 0);
1052     drop(drain);
1053     assert_eq!(vec, [2, 4]);
1054 }
1055
1056 #[test]
1057 fn test_reserve_exact() {
1058     // This is all the same as test_reserve
1059
1060     let mut v = Vec::new();
1061     assert_eq!(v.capacity(), 0);
1062
1063     v.reserve_exact(2);
1064     assert!(v.capacity() >= 2);
1065
1066     for i in 0..16 {
1067         v.push(i);
1068     }
1069
1070     assert!(v.capacity() >= 16);
1071     v.reserve_exact(16);
1072     assert!(v.capacity() >= 32);
1073
1074     v.push(16);
1075
1076     v.reserve_exact(16);
1077     assert!(v.capacity() >= 33)
1078 }
1079
1080 #[test]
1081 #[cfg(not(miri))] // Miri does not support signalling OOM
1082 fn test_try_reserve() {
1083
1084     // These are the interesting cases:
1085     // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1086     // * > isize::MAX should always fail
1087     //    * On 16/32-bit should CapacityOverflow
1088     //    * On 64-bit should OOM
1089     // * overflow may trigger when adding `len` to `cap` (in number of elements)
1090     // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1091
1092     const MAX_CAP: usize = isize::MAX as usize;
1093     const MAX_USIZE: usize = usize::MAX;
1094
1095     // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1096     // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1097     // Any platform that succeeds for these requests is technically broken with
1098     // ptr::offset because LLVM is the worst.
1099     let guards_against_isize = size_of::<usize>() < 8;
1100
1101     {
1102         // Note: basic stuff is checked by test_reserve
1103         let mut empty_bytes: Vec<u8> = Vec::new();
1104
1105         // Check isize::MAX doesn't count as an overflow
1106         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1107             panic!("isize::MAX shouldn't trigger an overflow!");
1108         }
1109         // Play it again, frank! (just to be sure)
1110         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1111             panic!("isize::MAX shouldn't trigger an overflow!");
1112         }
1113
1114         if guards_against_isize {
1115             // Check isize::MAX + 1 does count as overflow
1116             if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
1117             } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1118
1119             // Check usize::MAX does count as overflow
1120             if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
1121             } else { panic!("usize::MAX should trigger an overflow!") }
1122         } else {
1123             // Check isize::MAX + 1 is an OOM
1124             if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_CAP + 1) {
1125             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1126
1127             // Check usize::MAX is an OOM
1128             if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE) {
1129             } else { panic!("usize::MAX should trigger an OOM!") }
1130         }
1131     }
1132
1133
1134     {
1135         // Same basic idea, but with non-zero len
1136         let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1137
1138         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1139             panic!("isize::MAX shouldn't trigger an overflow!");
1140         }
1141         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1142             panic!("isize::MAX shouldn't trigger an overflow!");
1143         }
1144         if guards_against_isize {
1145             if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
1146             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1147         } else {
1148             if let Err(AllocError { .. }) = ten_bytes.try_reserve(MAX_CAP - 9) {
1149             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1150         }
1151         // Should always overflow in the add-to-len
1152         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
1153         } else { panic!("usize::MAX should trigger an overflow!") }
1154     }
1155
1156
1157     {
1158         // Same basic idea, but with interesting type size
1159         let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1160
1161         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1162             panic!("isize::MAX shouldn't trigger an overflow!");
1163         }
1164         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1165             panic!("isize::MAX shouldn't trigger an overflow!");
1166         }
1167         if guards_against_isize {
1168             if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1169             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1170         } else {
1171             if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1172             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1173         }
1174         // Should fail in the mul-by-size
1175         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
1176         } else {
1177             panic!("usize::MAX should trigger an overflow!");
1178         }
1179     }
1180
1181 }
1182
1183 #[test]
1184 #[cfg(not(miri))] // Miri does not support signalling OOM
1185 fn test_try_reserve_exact() {
1186
1187     // This is exactly the same as test_try_reserve with the method changed.
1188     // See that test for comments.
1189
1190     const MAX_CAP: usize = isize::MAX as usize;
1191     const MAX_USIZE: usize = usize::MAX;
1192
1193     let guards_against_isize = size_of::<usize>() < 8;
1194
1195     {
1196         let mut empty_bytes: Vec<u8> = Vec::new();
1197
1198         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1199             panic!("isize::MAX shouldn't trigger an overflow!");
1200         }
1201         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1202             panic!("isize::MAX shouldn't trigger an overflow!");
1203         }
1204
1205         if guards_against_isize {
1206             if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1207             } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1208
1209             if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1210             } else { panic!("usize::MAX should trigger an overflow!") }
1211         } else {
1212             if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1213             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1214
1215             if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1216             } else { panic!("usize::MAX should trigger an OOM!") }
1217         }
1218     }
1219
1220
1221     {
1222         let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1223
1224         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1225             panic!("isize::MAX shouldn't trigger an overflow!");
1226         }
1227         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1228             panic!("isize::MAX shouldn't trigger an overflow!");
1229         }
1230         if guards_against_isize {
1231             if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1232             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1233         } else {
1234             if let Err(AllocError { .. }) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1235             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1236         }
1237         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
1238         } else { panic!("usize::MAX should trigger an overflow!") }
1239     }
1240
1241
1242     {
1243         let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1244
1245         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1246             panic!("isize::MAX shouldn't trigger an overflow!");
1247         }
1248         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1249             panic!("isize::MAX shouldn't trigger an overflow!");
1250         }
1251         if guards_against_isize {
1252             if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1253             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1254         } else {
1255             if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1256             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1257         }
1258         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
1259         } else { panic!("usize::MAX should trigger an overflow!") }
1260     }
1261
1262 }
1263
1264 #[test]
1265 fn test_stable_push_pop() {
1266     // Test that, if we reserved enough space, adding and removing elements does not
1267     // invalidate references into the vector (such as `v0`).  This test also
1268     // runs in Miri, which would detect such problems.
1269     let mut v = Vec::with_capacity(10);
1270     v.push(13);
1271
1272     // laundering the lifetime -- we take care that `v` does not reallocate, so that's okay.
1273     let v0 = unsafe { &*(&v[0] as *const _) };
1274
1275     // Now do a bunch of things and occasionally use `v0` again to assert it is still valid.
1276     v.push(1);
1277     v.push(2);
1278     v.insert(1, 1);
1279     assert_eq!(*v0, 13);
1280     v.remove(1);
1281     v.pop().unwrap();
1282     assert_eq!(*v0, 13);
1283 }