src/liballoc/tests/vec.rs

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