src/liballoc/tests/vec.rs

   1 #![cfg(not(miri))]
   2
   3 use std::borrow::Cow;
   4 use std::mem::size_of;
   5 use std::{usize, isize};
   6 use std::vec::{Drain, IntoIter};
   7 use std::collections::CollectionAllocErr::*;
   8
   9 struct DropCounter<'a> {
  10     count: &'a mut u32,
  11 }
  12
  13 impl Drop for DropCounter<'_> {
  14     fn drop(&mut self) {
  15         *self.count += 1;
  16     }
  17 }
  18
  19 #[test]
  20 fn test_small_vec_struct() {
  21     assert!(size_of::<Vec<u8>>() == size_of::<usize>() * 3);
  22 }
  23
  24 #[test]
  25 fn test_double_drop() {
  26     struct TwoVec<T> {
  27         x: Vec<T>,
  28         y: Vec<T>,
  29     }
  30
  31     let (mut count_x, mut count_y) = (0, 0);
  32     {
  33         let mut tv = TwoVec {
  34             x: Vec::new(),
  35             y: Vec::new(),
  36         };
  37         tv.x.push(DropCounter { count: &mut count_x });
  38         tv.y.push(DropCounter { count: &mut count_y });
  39
  40         // If Vec had a drop flag, here is where it would be zeroed.
  41         // Instead, it should rely on its internal state to prevent
  42         // doing anything significant when dropped multiple times.
  43         drop(tv.x);
  44
  45         // Here tv goes out of scope, tv.y should be dropped, but not tv.x.
  46     }
  47
  48     assert_eq!(count_x, 1);
  49     assert_eq!(count_y, 1);
  50 }
  51
  52 #[test]
  53 fn test_reserve() {
  54     let mut v = Vec::new();
  55     assert_eq!(v.capacity(), 0);
  56
  57     v.reserve(2);
  58     assert!(v.capacity() >= 2);
  59
  60     for i in 0..16 {
  61         v.push(i);
  62     }
  63
  64     assert!(v.capacity() >= 16);
  65     v.reserve(16);
  66     assert!(v.capacity() >= 32);
  67
  68     v.push(16);
  69
  70     v.reserve(16);
  71     assert!(v.capacity() >= 33)
  72 }
  73
  74 #[test]
  75 fn test_zst_capacity() {
  76     assert_eq!(Vec::<()>::new().capacity(), usize::max_value());
  77 }
  78
  79 #[test]
  80 fn test_extend() {
  81     let mut v = Vec::new();
  82     let mut w = Vec::new();
  83
  84     v.extend(w.clone());
  85     assert_eq!(v, &[]);
  86
  87     v.extend(0..3);
  88     for i in 0..3 {
  89         w.push(i)
  90     }
  91
  92     assert_eq!(v, w);
  93
  94     v.extend(3..10);
  95     for i in 3..10 {
  96         w.push(i)
  97     }
  98
  99     assert_eq!(v, w);
 100
 101     v.extend(w.clone()); // specializes to `append`
 102     assert!(v.iter().eq(w.iter().chain(w.iter())));
 103
 104     // Zero sized types
 105     #[derive(PartialEq, Debug)]
 106     struct Foo;
 107
 108     let mut a = Vec::new();
 109     let b = vec![Foo, Foo];
 110
 111     a.extend(b);
 112     assert_eq!(a, &[Foo, Foo]);
 113
 114     // Double drop
 115     let mut count_x = 0;
 116     {
 117         let mut x = Vec::new();
 118         let y = vec![DropCounter { count: &mut count_x }];
 119         x.extend(y);
 120     }
 121     assert_eq!(count_x, 1);
 122 }
 123
 124 #[test]
 125 fn test_extend_ref() {
 126     let mut v = vec![1, 2];
 127     v.extend(&[3, 4, 5]);
 128
 129     assert_eq!(v.len(), 5);
 130     assert_eq!(v, [1, 2, 3, 4, 5]);
 131
 132     let w = vec![6, 7];
 133     v.extend(&w);
 134
 135     assert_eq!(v.len(), 7);
 136     assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
 137 }
 138
 139 #[test]
 140 fn test_slice_from_mut() {
 141     let mut values = vec![1, 2, 3, 4, 5];
 142     {
 143         let slice = &mut values[2..];
 144         assert!(slice == [3, 4, 5]);
 145         for p in slice {
 146             *p += 2;
 147         }
 148     }
 149
 150     assert!(values == [1, 2, 5, 6, 7]);
 151 }
 152
 153 #[test]
 154 fn test_slice_to_mut() {
 155     let mut values = vec![1, 2, 3, 4, 5];
 156     {
 157         let slice = &mut values[..2];
 158         assert!(slice == [1, 2]);
 159         for p in slice {
 160             *p += 1;
 161         }
 162     }
 163
 164     assert!(values == [2, 3, 3, 4, 5]);
 165 }
 166
 167 #[test]
 168 fn test_split_at_mut() {
 169     let mut values = vec![1, 2, 3, 4, 5];
 170     {
 171         let (left, right) = values.split_at_mut(2);
 172         {
 173             let left: &[_] = left;
 174             assert!(&left[..left.len()] == &[1, 2]);
 175         }
 176         for p in left {
 177             *p += 1;
 178         }
 179
 180         {
 181             let right: &[_] = right;
 182             assert!(&right[..right.len()] == &[3, 4, 5]);
 183         }
 184         for p in right {
 185             *p += 2;
 186         }
 187     }
 188
 189     assert_eq!(values, [2, 3, 5, 6, 7]);
 190 }
 191
 192 #[test]
 193 fn test_clone() {
 194     let v: Vec<i32> = vec![];
 195     let w = vec![1, 2, 3];
 196
 197     assert_eq!(v, v.clone());
 198
 199     let z = w.clone();
 200     assert_eq!(w, z);
 201     // they should be disjoint in memory.
 202     assert!(w.as_ptr() != z.as_ptr())
 203 }
 204
 205 #[test]
 206 fn test_clone_from() {
 207     let mut v = vec![];
 208     let three: Vec<Box<_>> = vec![box 1, box 2, box 3];
 209     let two: Vec<Box<_>> = vec![box 4, box 5];
 210     // zero, long
 211     v.clone_from(&three);
 212     assert_eq!(v, three);
 213
 214     // equal
 215     v.clone_from(&three);
 216     assert_eq!(v, three);
 217
 218     // long, short
 219     v.clone_from(&two);
 220     assert_eq!(v, two);
 221
 222     // short, long
 223     v.clone_from(&three);
 224     assert_eq!(v, three)
 225 }
 226
 227 #[test]
 228 fn test_retain() {
 229     let mut vec = vec![1, 2, 3, 4];
 230     vec.retain(|&x| x % 2 == 0);
 231     assert_eq!(vec, [2, 4]);
 232 }
 233
 234 #[test]
 235 fn test_dedup() {
 236     fn case(a: Vec<i32>, b: Vec<i32>) {
 237         let mut v = a;
 238         v.dedup();
 239         assert_eq!(v, b);
 240     }
 241     case(vec![], vec![]);
 242     case(vec![1], vec![1]);
 243     case(vec![1, 1], vec![1]);
 244     case(vec![1, 2, 3], vec![1, 2, 3]);
 245     case(vec![1, 1, 2, 3], vec![1, 2, 3]);
 246     case(vec![1, 2, 2, 3], vec![1, 2, 3]);
 247     case(vec![1, 2, 3, 3], vec![1, 2, 3]);
 248     case(vec![1, 1, 2, 2, 2, 3, 3], vec![1, 2, 3]);
 249 }
 250
 251 #[test]
 252 fn test_dedup_by_key() {
 253     fn case(a: Vec<i32>, b: Vec<i32>) {
 254         let mut v = a;
 255         v.dedup_by_key(|i| *i / 10);
 256         assert_eq!(v, b);
 257     }
 258     case(vec![], vec![]);
 259     case(vec![10], vec![10]);
 260     case(vec![10, 11], vec![10]);
 261     case(vec![10, 20, 30], vec![10, 20, 30]);
 262     case(vec![10, 11, 20, 30], vec![10, 20, 30]);
 263     case(vec![10, 20, 21, 30], vec![10, 20, 30]);
 264     case(vec![10, 20, 30, 31], vec![10, 20, 30]);
 265     case(vec![10, 11, 20, 21, 22, 30, 31], vec![10, 20, 30]);
 266 }
 267
 268 #[test]
 269 fn test_dedup_by() {
 270     let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"];
 271     vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
 272
 273     assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
 274
 275     let mut vec = vec![("foo", 1), ("foo", 2), ("bar", 3), ("bar", 4), ("bar", 5)];
 276     vec.dedup_by(|a, b| a.0 == b.0 && { b.1 += a.1; true });
 277
 278     assert_eq!(vec, [("foo", 3), ("bar", 12)]);
 279 }
 280
 281 #[test]
 282 fn test_dedup_unique() {
 283     let mut v0: Vec<Box<_>> = vec![box 1, box 1, box 2, box 3];
 284     v0.dedup();
 285     let mut v1: Vec<Box<_>> = vec![box 1, box 2, box 2, box 3];
 286     v1.dedup();
 287     let mut v2: Vec<Box<_>> = vec![box 1, box 2, box 3, box 3];
 288     v2.dedup();
 289     // If the boxed pointers were leaked or otherwise misused, valgrind
 290     // and/or rt should raise errors.
 291 }
 292
 293 #[test]
 294 fn zero_sized_values() {
 295     let mut v = Vec::new();
 296     assert_eq!(v.len(), 0);
 297     v.push(());
 298     assert_eq!(v.len(), 1);
 299     v.push(());
 300     assert_eq!(v.len(), 2);
 301     assert_eq!(v.pop(), Some(()));
 302     assert_eq!(v.pop(), Some(()));
 303     assert_eq!(v.pop(), None);
 304
 305     assert_eq!(v.iter().count(), 0);
 306     v.push(());
 307     assert_eq!(v.iter().count(), 1);
 308     v.push(());
 309     assert_eq!(v.iter().count(), 2);
 310
 311     for &() in &v {}
 312
 313     assert_eq!(v.iter_mut().count(), 2);
 314     v.push(());
 315     assert_eq!(v.iter_mut().count(), 3);
 316     v.push(());
 317     assert_eq!(v.iter_mut().count(), 4);
 318
 319     for &mut () in &mut v {}
 320     unsafe {
 321         v.set_len(0);
 322     }
 323     assert_eq!(v.iter_mut().count(), 0);
 324 }
 325
 326 #[test]
 327 fn test_partition() {
 328     assert_eq!(vec![].into_iter().partition(|x: &i32| *x < 3),
 329                (vec![], vec![]));
 330     assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 4),
 331                (vec![1, 2, 3], vec![]));
 332     assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 2),
 333                (vec![1], vec![2, 3]));
 334     assert_eq!(vec![1, 2, 3].into_iter().partition(|x| *x < 0),
 335                (vec![], vec![1, 2, 3]));
 336 }
 337
 338 #[test]
 339 fn test_zip_unzip() {
 340     let z1 = vec![(1, 4), (2, 5), (3, 6)];
 341
 342     let (left, right): (Vec<_>, Vec<_>) = z1.iter().cloned().unzip();
 343
 344     assert_eq!((1, 4), (left[0], right[0]));
 345     assert_eq!((2, 5), (left[1], right[1]));
 346     assert_eq!((3, 6), (left[2], right[2]));
 347 }
 348
 349 #[test]
 350 fn test_vec_truncate_drop() {
 351     static mut DROPS: u32 = 0;
 352     struct Elem(i32);
 353     impl Drop for Elem {
 354         fn drop(&mut self) {
 355             unsafe {
 356                 DROPS += 1;
 357             }
 358         }
 359     }
 360
 361     let mut v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
 362     assert_eq!(unsafe { DROPS }, 0);
 363     v.truncate(3);
 364     assert_eq!(unsafe { DROPS }, 2);
 365     v.truncate(0);
 366     assert_eq!(unsafe { DROPS }, 5);
 367 }
 368
 369 #[test]
 370 #[should_panic]
 371 fn test_vec_truncate_fail() {
 372     struct BadElem(i32);
 373     impl Drop for BadElem {
 374         fn drop(&mut self) {
 375             let BadElem(ref mut x) = *self;
 376             if *x == 0xbadbeef {
 377                 panic!("BadElem panic: 0xbadbeef")
 378             }
 379         }
 380     }
 381
 382     let mut v = vec![BadElem(1), BadElem(2), BadElem(0xbadbeef), BadElem(4)];
 383     v.truncate(0);
 384 }
 385
 386 #[test]
 387 fn test_index() {
 388     let vec = vec![1, 2, 3];
 389     assert!(vec[1] == 2);
 390 }
 391
 392 #[test]
 393 #[should_panic]
 394 fn test_index_out_of_bounds() {
 395     let vec = vec![1, 2, 3];
 396     let _ = vec[3];
 397 }
 398
 399 #[test]
 400 #[should_panic]
 401 fn test_slice_out_of_bounds_1() {
 402     let x = vec![1, 2, 3, 4, 5];
 403     &x[!0..];
 404 }
 405
 406 #[test]
 407 #[should_panic]
 408 fn test_slice_out_of_bounds_2() {
 409     let x = vec![1, 2, 3, 4, 5];
 410     &x[..6];
 411 }
 412
 413 #[test]
 414 #[should_panic]
 415 fn test_slice_out_of_bounds_3() {
 416     let x = vec![1, 2, 3, 4, 5];
 417     &x[!0..4];
 418 }
 419
 420 #[test]
 421 #[should_panic]
 422 fn test_slice_out_of_bounds_4() {
 423     let x = vec![1, 2, 3, 4, 5];
 424     &x[1..6];
 425 }
 426
 427 #[test]
 428 #[should_panic]
 429 fn test_slice_out_of_bounds_5() {
 430     let x = vec![1, 2, 3, 4, 5];
 431     &x[3..2];
 432 }
 433
 434 #[test]
 435 #[should_panic]
 436 fn test_swap_remove_empty() {
 437     let mut vec = Vec::<i32>::new();
 438     vec.swap_remove(0);
 439 }
 440
 441 #[test]
 442 fn test_move_items() {
 443     let vec = vec![1, 2, 3];
 444     let mut vec2 = vec![];
 445     for i in vec {
 446         vec2.push(i);
 447     }
 448     assert_eq!(vec2, [1, 2, 3]);
 449 }
 450
 451 #[test]
 452 fn test_move_items_reverse() {
 453     let vec = vec![1, 2, 3];
 454     let mut vec2 = vec![];
 455     for i in vec.into_iter().rev() {
 456         vec2.push(i);
 457     }
 458     assert_eq!(vec2, [3, 2, 1]);
 459 }
 460
 461 #[test]
 462 fn test_move_items_zero_sized() {
 463     let vec = vec![(), (), ()];
 464     let mut vec2 = vec![];
 465     for i in vec {
 466         vec2.push(i);
 467     }
 468     assert_eq!(vec2, [(), (), ()]);
 469 }
 470
 471 #[test]
 472 fn test_drain_items() {
 473     let mut vec = vec![1, 2, 3];
 474     let mut vec2 = vec![];
 475     for i in vec.drain(..) {
 476         vec2.push(i);
 477     }
 478     assert_eq!(vec, []);
 479     assert_eq!(vec2, [1, 2, 3]);
 480 }
 481
 482 #[test]
 483 fn test_drain_items_reverse() {
 484     let mut vec = vec![1, 2, 3];
 485     let mut vec2 = vec![];
 486     for i in vec.drain(..).rev() {
 487         vec2.push(i);
 488     }
 489     assert_eq!(vec, []);
 490     assert_eq!(vec2, [3, 2, 1]);
 491 }
 492
 493 #[test]
 494 fn test_drain_items_zero_sized() {
 495     let mut vec = vec![(), (), ()];
 496     let mut vec2 = vec![];
 497     for i in vec.drain(..) {
 498         vec2.push(i);
 499     }
 500     assert_eq!(vec, []);
 501     assert_eq!(vec2, [(), (), ()]);
 502 }
 503
 504 #[test]
 505 #[should_panic]
 506 fn test_drain_out_of_bounds() {
 507     let mut v = vec![1, 2, 3, 4, 5];
 508     v.drain(5..6);
 509 }
 510
 511 #[test]
 512 fn test_drain_range() {
 513     let mut v = vec![1, 2, 3, 4, 5];
 514     for _ in v.drain(4..) {
 515     }
 516     assert_eq!(v, &[1, 2, 3, 4]);
 517
 518     let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
 519     for _ in v.drain(1..4) {
 520     }
 521     assert_eq!(v, &[1.to_string(), 5.to_string()]);
 522
 523     let mut v: Vec<_> = (1..6).map(|x| x.to_string()).collect();
 524     for _ in v.drain(1..4).rev() {
 525     }
 526     assert_eq!(v, &[1.to_string(), 5.to_string()]);
 527
 528     let mut v: Vec<_> = vec![(); 5];
 529     for _ in v.drain(1..4).rev() {
 530     }
 531     assert_eq!(v, &[(), ()]);
 532 }
 533
 534 #[test]
 535 fn test_drain_inclusive_range() {
 536     let mut v = vec!['a', 'b', 'c', 'd', 'e'];
 537     for _ in v.drain(1..=3) {
 538     }
 539     assert_eq!(v, &['a', 'e']);
 540
 541     let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
 542     for _ in v.drain(1..=5) {
 543     }
 544     assert_eq!(v, &["0".to_string()]);
 545
 546     let mut v: Vec<String> = (0..=5).map(|x| x.to_string()).collect();
 547     for _ in v.drain(0..=5) {
 548     }
 549     assert_eq!(v, Vec::<String>::new());
 550
 551     let mut v: Vec<_> = (0..=5).map(|x| x.to_string()).collect();
 552     for _ in v.drain(0..=3) {
 553     }
 554     assert_eq!(v, &["4".to_string(), "5".to_string()]);
 555
 556     let mut v: Vec<_> = (0..=1).map(|x| x.to_string()).collect();
 557     for _ in v.drain(..=0) {
 558     }
 559     assert_eq!(v, &["1".to_string()]);
 560 }
 561
 562 #[test]
 563 fn test_drain_max_vec_size() {
 564     let mut v = Vec::<()>::with_capacity(usize::max_value());
 565     unsafe { v.set_len(usize::max_value()); }
 566     for _ in v.drain(usize::max_value() - 1..) {
 567     }
 568     assert_eq!(v.len(), usize::max_value() - 1);
 569
 570     let mut v = Vec::<()>::with_capacity(usize::max_value());
 571     unsafe { v.set_len(usize::max_value()); }
 572     for _ in v.drain(usize::max_value() - 1..=usize::max_value() - 1) {
 573     }
 574     assert_eq!(v.len(), usize::max_value() - 1);
 575 }
 576
 577 #[test]
 578 #[should_panic]
 579 fn test_drain_inclusive_out_of_bounds() {
 580     let mut v = vec![1, 2, 3, 4, 5];
 581     v.drain(5..=5);
 582 }
 583
 584 #[test]
 585 fn test_splice() {
 586     let mut v = vec![1, 2, 3, 4, 5];
 587     let a = [10, 11, 12];
 588     v.splice(2..4, a.iter().cloned());
 589     assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
 590     v.splice(1..3, Some(20));
 591     assert_eq!(v, &[1, 20, 11, 12, 5]);
 592 }
 593
 594 #[test]
 595 fn test_splice_inclusive_range() {
 596     let mut v = vec![1, 2, 3, 4, 5];
 597     let a = [10, 11, 12];
 598     let t1: Vec<_> = v.splice(2..=3, a.iter().cloned()).collect();
 599     assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
 600     assert_eq!(t1, &[3, 4]);
 601     let t2: Vec<_> = v.splice(1..=2, Some(20)).collect();
 602     assert_eq!(v, &[1, 20, 11, 12, 5]);
 603     assert_eq!(t2, &[2, 10]);
 604 }
 605
 606 #[test]
 607 #[should_panic]
 608 fn test_splice_out_of_bounds() {
 609     let mut v = vec![1, 2, 3, 4, 5];
 610     let a = [10, 11, 12];
 611     v.splice(5..6, a.iter().cloned());
 612 }
 613
 614 #[test]
 615 #[should_panic]
 616 fn test_splice_inclusive_out_of_bounds() {
 617     let mut v = vec![1, 2, 3, 4, 5];
 618     let a = [10, 11, 12];
 619     v.splice(5..=5, a.iter().cloned());
 620 }
 621
 622 #[test]
 623 fn test_splice_items_zero_sized() {
 624     let mut vec = vec![(), (), ()];
 625     let vec2 = vec![];
 626     let t: Vec<_> = vec.splice(1..2, vec2.iter().cloned()).collect();
 627     assert_eq!(vec, &[(), ()]);
 628     assert_eq!(t, &[()]);
 629 }
 630
 631 #[test]
 632 fn test_splice_unbounded() {
 633     let mut vec = vec![1, 2, 3, 4, 5];
 634     let t: Vec<_> = vec.splice(.., None).collect();
 635     assert_eq!(vec, &[]);
 636     assert_eq!(t, &[1, 2, 3, 4, 5]);
 637 }
 638
 639 #[test]
 640 fn test_splice_forget() {
 641     let mut v = vec![1, 2, 3, 4, 5];
 642     let a = [10, 11, 12];
 643     std::mem::forget(v.splice(2..4, a.iter().cloned()));
 644     assert_eq!(v, &[1, 2]);
 645 }
 646
 647 #[test]
 648 fn test_into_boxed_slice() {
 649     let xs = vec![1, 2, 3];
 650     let ys = xs.into_boxed_slice();
 651     assert_eq!(&*ys, [1, 2, 3]);
 652 }
 653
 654 #[test]
 655 fn test_append() {
 656     let mut vec = vec![1, 2, 3];
 657     let mut vec2 = vec![4, 5, 6];
 658     vec.append(&mut vec2);
 659     assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
 660     assert_eq!(vec2, []);
 661 }
 662
 663 #[test]
 664 fn test_split_off() {
 665     let mut vec = vec![1, 2, 3, 4, 5, 6];
 666     let vec2 = vec.split_off(4);
 667     assert_eq!(vec, [1, 2, 3, 4]);
 668     assert_eq!(vec2, [5, 6]);
 669 }
 670
 671 #[test]
 672 fn test_into_iter_as_slice() {
 673     let vec = vec!['a', 'b', 'c'];
 674     let mut into_iter = vec.into_iter();
 675     assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
 676     let _ = into_iter.next().unwrap();
 677     assert_eq!(into_iter.as_slice(), &['b', 'c']);
 678     let _ = into_iter.next().unwrap();
 679     let _ = into_iter.next().unwrap();
 680     assert_eq!(into_iter.as_slice(), &[]);
 681 }
 682
 683 #[test]
 684 fn test_into_iter_as_mut_slice() {
 685     let vec = vec!['a', 'b', 'c'];
 686     let mut into_iter = vec.into_iter();
 687     assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
 688     into_iter.as_mut_slice()[0] = 'x';
 689     into_iter.as_mut_slice()[1] = 'y';
 690     assert_eq!(into_iter.next().unwrap(), 'x');
 691     assert_eq!(into_iter.as_slice(), &['y', 'c']);
 692 }
 693
 694 #[test]
 695 fn test_into_iter_debug() {
 696     let vec = vec!['a', 'b', 'c'];
 697     let into_iter = vec.into_iter();
 698     let debug = format!("{:?}", into_iter);
 699     assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
 700 }
 701
 702 #[test]
 703 fn test_into_iter_count() {
 704     assert_eq!(vec![1, 2, 3].into_iter().count(), 3);
 705 }
 706
 707 #[test]
 708 fn test_into_iter_clone() {
 709     fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
 710         let v: Vec<i32> = it.collect();
 711         assert_eq!(&v[..], slice);
 712     }
 713     let mut it = vec![1, 2, 3].into_iter();
 714     iter_equal(it.clone(), &[1, 2, 3]);
 715     assert_eq!(it.next(), Some(1));
 716     let mut it = it.rev();
 717     iter_equal(it.clone(), &[3, 2]);
 718     assert_eq!(it.next(), Some(3));
 719     iter_equal(it.clone(), &[2]);
 720     assert_eq!(it.next(), Some(2));
 721     iter_equal(it.clone(), &[]);
 722     assert_eq!(it.next(), None);
 723 }
 724
 725 #[test]
 726 fn test_cow_from() {
 727     let borrowed: &[_] = &["borrowed", "(slice)"];
 728     let owned = vec!["owned", "(vec)"];
 729     match (Cow::from(owned.clone()), Cow::from(borrowed)) {
 730         (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed),
 731         _ => panic!("invalid `Cow::from`"),
 732     }
 733 }
 734
 735 #[test]
 736 fn test_from_cow() {
 737     let borrowed: &[_] = &["borrowed", "(slice)"];
 738     let owned = vec!["owned", "(vec)"];
 739     assert_eq!(Vec::from(Cow::Borrowed(borrowed)), vec!["borrowed", "(slice)"]);
 740     assert_eq!(Vec::from(Cow::Owned(owned)), vec!["owned", "(vec)"]);
 741 }
 742
 743 #[allow(dead_code)]
 744 fn assert_covariance() {
 745     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 746         d
 747     }
 748     fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
 749         i
 750     }
 751 }
 752
 753 #[test]
 754 fn from_into_inner() {
 755     let vec = vec![1, 2, 3];
 756     let ptr = vec.as_ptr();
 757     let vec = vec.into_iter().collect::<Vec<_>>();
 758     assert_eq!(vec, [1, 2, 3]);
 759     assert_eq!(vec.as_ptr(), ptr);
 760
 761     let ptr = &vec[1] as *const _;
 762     let mut it = vec.into_iter();
 763     it.next().unwrap();
 764     let vec = it.collect::<Vec<_>>();
 765     assert_eq!(vec, [2, 3]);
 766     assert!(ptr != vec.as_ptr());
 767 }
 768
 769 #[test]
 770 fn overaligned_allocations() {
 771     #[repr(align(256))]
 772     struct Foo(usize);
 773     let mut v = vec![Foo(273)];
 774     for i in 0..0x1000 {
 775         v.reserve_exact(i);
 776         assert!(v[0].0 == 273);
 777         assert!(v.as_ptr() as usize & 0xff == 0);
 778         v.shrink_to_fit();
 779         assert!(v[0].0 == 273);
 780         assert!(v.as_ptr() as usize & 0xff == 0);
 781     }
 782 }
 783
 784 #[test]
 785 fn drain_filter_empty() {
 786     let mut vec: Vec<i32> = vec![];
 787
 788     {
 789         let mut iter = vec.drain_filter(|_| true);
 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         assert_eq!(iter.next(), None);
 794         assert_eq!(iter.size_hint(), (0, Some(0)));
 795     }
 796     assert_eq!(vec.len(), 0);
 797     assert_eq!(vec, vec![]);
 798 }
 799
 800 #[test]
 801 fn drain_filter_zst() {
 802     let mut vec = vec![(), (), (), (), ()];
 803     let initial_len = vec.len();
 804     let mut count = 0;
 805     {
 806         let mut iter = vec.drain_filter(|_| true);
 807         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 808         while let Some(_) = iter.next() {
 809             count += 1;
 810             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 811         }
 812         assert_eq!(iter.size_hint(), (0, Some(0)));
 813         assert_eq!(iter.next(), None);
 814         assert_eq!(iter.size_hint(), (0, Some(0)));
 815     }
 816
 817     assert_eq!(count, initial_len);
 818     assert_eq!(vec.len(), 0);
 819     assert_eq!(vec, vec![]);
 820 }
 821
 822 #[test]
 823 fn drain_filter_false() {
 824     let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 825
 826     let initial_len = vec.len();
 827     let mut count = 0;
 828     {
 829         let mut iter = vec.drain_filter(|_| false);
 830         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 831         for _ in iter.by_ref() {
 832             count += 1;
 833         }
 834         assert_eq!(iter.size_hint(), (0, Some(0)));
 835         assert_eq!(iter.next(), None);
 836         assert_eq!(iter.size_hint(), (0, Some(0)));
 837     }
 838
 839     assert_eq!(count, 0);
 840     assert_eq!(vec.len(), initial_len);
 841     assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 842 }
 843
 844 #[test]
 845 fn drain_filter_true() {
 846     let mut vec = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 847
 848     let initial_len = vec.len();
 849     let mut count = 0;
 850     {
 851         let mut iter = vec.drain_filter(|_| true);
 852         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 853         while let Some(_) = iter.next() {
 854             count += 1;
 855             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 856         }
 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     }
 861
 862     assert_eq!(count, initial_len);
 863     assert_eq!(vec.len(), 0);
 864     assert_eq!(vec, vec![]);
 865 }
 866
 867 #[test]
 868 fn drain_filter_complex() {
 869
 870     {   //                [+xxx++++++xxxxx++++x+x++]
 871         let mut vec = vec![1,
 872                            2, 4, 6,
 873                            7, 9, 11, 13, 15, 17,
 874                            18, 20, 22, 24, 26,
 875                            27, 29, 31, 33,
 876                            34,
 877                            35,
 878                            36,
 879                            37, 39];
 880
 881         let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 882         assert_eq!(removed.len(), 10);
 883         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 884
 885         assert_eq!(vec.len(), 14);
 886         assert_eq!(vec, vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
 887     }
 888
 889     {   //                [xxx++++++xxxxx++++x+x++]
 890         let mut vec = vec![2, 4, 6,
 891                            7, 9, 11, 13, 15, 17,
 892                            18, 20, 22, 24, 26,
 893                            27, 29, 31, 33,
 894                            34,
 895                            35,
 896                            36,
 897                            37, 39];
 898
 899         let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 900         assert_eq!(removed.len(), 10);
 901         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 902
 903         assert_eq!(vec.len(), 13);
 904         assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
 905     }
 906
 907     {   //                [xxx++++++xxxxx++++x+x]
 908         let mut vec = vec![2, 4, 6,
 909                            7, 9, 11, 13, 15, 17,
 910                            18, 20, 22, 24, 26,
 911                            27, 29, 31, 33,
 912                            34,
 913                            35,
 914                            36];
 915
 916         let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 917         assert_eq!(removed.len(), 10);
 918         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 919
 920         assert_eq!(vec.len(), 11);
 921         assert_eq!(vec, vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
 922     }
 923
 924     {   //                [xxxxxxxxxx+++++++++++]
 925         let mut vec = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
 926                            1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
 927
 928         let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 929         assert_eq!(removed.len(), 10);
 930         assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
 931
 932         assert_eq!(vec.len(), 10);
 933         assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 934     }
 935
 936     {   //                [+++++++++++xxxxxxxxxx]
 937         let mut vec = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
 938                            2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
 939
 940         let removed = vec.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 941         assert_eq!(removed.len(), 10);
 942         assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
 943
 944         assert_eq!(vec.len(), 10);
 945         assert_eq!(vec, vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 946     }
 947 }
 948
 949 #[test]
 950 fn test_reserve_exact() {
 951     // This is all the same as test_reserve
 952
 953     let mut v = Vec::new();
 954     assert_eq!(v.capacity(), 0);
 955
 956     v.reserve_exact(2);
 957     assert!(v.capacity() >= 2);
 958
 959     for i in 0..16 {
 960         v.push(i);
 961     }
 962
 963     assert!(v.capacity() >= 16);
 964     v.reserve_exact(16);
 965     assert!(v.capacity() >= 32);
 966
 967     v.push(16);
 968
 969     v.reserve_exact(16);
 970     assert!(v.capacity() >= 33)
 971 }
 972
 973 #[test]
 974 fn test_try_reserve() {
 975
 976     // These are the interesting cases:
 977     // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
 978     // * > isize::MAX should always fail
 979     //    * On 16/32-bit should CapacityOverflow
 980     //    * On 64-bit should OOM
 981     // * overflow may trigger when adding `len` to `cap` (in number of elements)
 982     // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
 983
 984     const MAX_CAP: usize = isize::MAX as usize;
 985     const MAX_USIZE: usize = usize::MAX;
 986
 987     // On 16/32-bit, we check that allocations don't exceed isize::MAX,
 988     // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
 989     // Any platform that succeeds for these requests is technically broken with
 990     // ptr::offset because LLVM is the worst.
 991     let guards_against_isize = size_of::<usize>() < 8;
 992
 993     {
 994         // Note: basic stuff is checked by test_reserve
 995         let mut empty_bytes: Vec<u8> = Vec::new();
 996
 997         // Check isize::MAX doesn't count as an overflow
 998         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
 999             panic!("isize::MAX shouldn't trigger an overflow!");
1000         }
1001         // Play it again, frank! (just to be sure)
1002         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1003             panic!("isize::MAX shouldn't trigger an overflow!");
1004         }
1005
1006         if guards_against_isize {
1007             // Check isize::MAX + 1 does count as overflow
1008             if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
1009             } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1010
1011             // Check usize::MAX does count as overflow
1012             if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
1013             } else { panic!("usize::MAX should trigger an overflow!") }
1014         } else {
1015             // Check isize::MAX + 1 is an OOM
1016             if let Err(AllocErr) = empty_bytes.try_reserve(MAX_CAP + 1) {
1017             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1018
1019             // Check usize::MAX is an OOM
1020             if let Err(AllocErr) = empty_bytes.try_reserve(MAX_USIZE) {
1021             } else { panic!("usize::MAX should trigger an OOM!") }
1022         }
1023     }
1024
1025
1026     {
1027         // Same basic idea, but with non-zero len
1028         let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1029
1030         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1031             panic!("isize::MAX shouldn't trigger an overflow!");
1032         }
1033         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1034             panic!("isize::MAX shouldn't trigger an overflow!");
1035         }
1036         if guards_against_isize {
1037             if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
1038             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1039         } else {
1040             if let Err(AllocErr) = ten_bytes.try_reserve(MAX_CAP - 9) {
1041             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1042         }
1043         // Should always overflow in the add-to-len
1044         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
1045         } else { panic!("usize::MAX should trigger an overflow!") }
1046     }
1047
1048
1049     {
1050         // Same basic idea, but with interesting type size
1051         let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1052
1053         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1054             panic!("isize::MAX shouldn't trigger an overflow!");
1055         }
1056         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1057             panic!("isize::MAX shouldn't trigger an overflow!");
1058         }
1059         if guards_against_isize {
1060             if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1061             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1062         } else {
1063             if let Err(AllocErr) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1064             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1065         }
1066         // Should fail in the mul-by-size
1067         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
1068         } else {
1069             panic!("usize::MAX should trigger an overflow!");
1070         }
1071     }
1072
1073 }
1074
1075 #[test]
1076 fn test_try_reserve_exact() {
1077
1078     // This is exactly the same as test_try_reserve with the method changed.
1079     // See that test for comments.
1080
1081     const MAX_CAP: usize = isize::MAX as usize;
1082     const MAX_USIZE: usize = usize::MAX;
1083
1084     let guards_against_isize = size_of::<usize>() < 8;
1085
1086     {
1087         let mut empty_bytes: Vec<u8> = Vec::new();
1088
1089         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1090             panic!("isize::MAX shouldn't trigger an overflow!");
1091         }
1092         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1093             panic!("isize::MAX shouldn't trigger an overflow!");
1094         }
1095
1096         if guards_against_isize {
1097             if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1098             } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1099
1100             if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1101             } else { panic!("usize::MAX should trigger an overflow!") }
1102         } else {
1103             if let Err(AllocErr) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1104             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1105
1106             if let Err(AllocErr) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1107             } else { panic!("usize::MAX should trigger an OOM!") }
1108         }
1109     }
1110
1111
1112     {
1113         let mut ten_bytes: Vec<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1114
1115         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1116             panic!("isize::MAX shouldn't trigger an overflow!");
1117         }
1118         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1119             panic!("isize::MAX shouldn't trigger an overflow!");
1120         }
1121         if guards_against_isize {
1122             if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1123             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1124         } else {
1125             if let Err(AllocErr) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1126             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1127         }
1128         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
1129         } else { panic!("usize::MAX should trigger an overflow!") }
1130     }
1131
1132
1133     {
1134         let mut ten_u32s: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1135
1136         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1137             panic!("isize::MAX shouldn't trigger an overflow!");
1138         }
1139         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1140             panic!("isize::MAX shouldn't trigger an overflow!");
1141         }
1142         if guards_against_isize {
1143             if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1144             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1145         } else {
1146             if let Err(AllocErr) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1147             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1148         }
1149         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
1150         } else { panic!("usize::MAX should trigger an overflow!") }
1151     }
1152
1153 }