library/alloc/tests/slice.rs

   1 use std::cell::Cell;
   2 use std::cmp::Ordering::{self, Equal, Greater, Less};
   3 use std::convert::identity;
   4 use std::fmt;
   5 use std::mem;
   6 use std::panic;
   7 use std::rc::Rc;
   8 use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};
   9
  10 use rand::distributions::Standard;
  11 use rand::seq::SliceRandom;
  12 use rand::{thread_rng, Rng, RngCore};
  13
  14 fn square(n: usize) -> usize {
  15     n * n
  16 }
  17
  18 fn is_odd(n: &usize) -> bool {
  19     *n % 2 == 1
  20 }
  21
  22 #[test]
  23 fn test_from_fn() {
  24     // Test on-stack from_fn.
  25     let mut v: Vec<_> = (0..3).map(square).collect();
  26     {
  27         let v = v;
  28         assert_eq!(v.len(), 3);
  29         assert_eq!(v[0], 0);
  30         assert_eq!(v[1], 1);
  31         assert_eq!(v[2], 4);
  32     }
  33
  34     // Test on-heap from_fn.
  35     v = (0..5).map(square).collect();
  36     {
  37         let v = v;
  38         assert_eq!(v.len(), 5);
  39         assert_eq!(v[0], 0);
  40         assert_eq!(v[1], 1);
  41         assert_eq!(v[2], 4);
  42         assert_eq!(v[3], 9);
  43         assert_eq!(v[4], 16);
  44     }
  45 }
  46
  47 #[test]
  48 fn test_from_elem() {
  49     // Test on-stack from_elem.
  50     let mut v = vec![10, 10];
  51     {
  52         let v = v;
  53         assert_eq!(v.len(), 2);
  54         assert_eq!(v[0], 10);
  55         assert_eq!(v[1], 10);
  56     }
  57
  58     // Test on-heap from_elem.
  59     v = vec![20; 6];
  60     {
  61         let v = &v[..];
  62         assert_eq!(v[0], 20);
  63         assert_eq!(v[1], 20);
  64         assert_eq!(v[2], 20);
  65         assert_eq!(v[3], 20);
  66         assert_eq!(v[4], 20);
  67         assert_eq!(v[5], 20);
  68     }
  69 }
  70
  71 #[test]
  72 fn test_is_empty() {
  73     let xs: [i32; 0] = [];
  74     assert!(xs.is_empty());
  75     assert!(![0].is_empty());
  76 }
  77
  78 #[test]
  79 fn test_len_divzero() {
  80     type Z = [i8; 0];
  81     let v0: &[Z] = &[];
  82     let v1: &[Z] = &[[]];
  83     let v2: &[Z] = &[[], []];
  84     assert_eq!(mem::size_of::<Z>(), 0);
  85     assert_eq!(v0.len(), 0);
  86     assert_eq!(v1.len(), 1);
  87     assert_eq!(v2.len(), 2);
  88 }
  89
  90 #[test]
  91 fn test_get() {
  92     let mut a = vec![11];
  93     assert_eq!(a.get(1), None);
  94     a = vec![11, 12];
  95     assert_eq!(a.get(1).unwrap(), &12);
  96     a = vec![11, 12, 13];
  97     assert_eq!(a.get(1).unwrap(), &12);
  98 }
  99
 100 #[test]
 101 fn test_first() {
 102     let mut a = vec![];
 103     assert_eq!(a.first(), None);
 104     a = vec![11];
 105     assert_eq!(a.first().unwrap(), &11);
 106     a = vec![11, 12];
 107     assert_eq!(a.first().unwrap(), &11);
 108 }
 109
 110 #[test]
 111 fn test_first_mut() {
 112     let mut a = vec![];
 113     assert_eq!(a.first_mut(), None);
 114     a = vec![11];
 115     assert_eq!(*a.first_mut().unwrap(), 11);
 116     a = vec![11, 12];
 117     assert_eq!(*a.first_mut().unwrap(), 11);
 118 }
 119
 120 #[test]
 121 fn test_split_first() {
 122     let mut a = vec![11];
 123     let b: &[i32] = &[];
 124     assert!(b.split_first().is_none());
 125     assert_eq!(a.split_first(), Some((&11, b)));
 126     a = vec![11, 12];
 127     let b: &[i32] = &[12];
 128     assert_eq!(a.split_first(), Some((&11, b)));
 129 }
 130
 131 #[test]
 132 fn test_split_first_mut() {
 133     let mut a = vec![11];
 134     let b: &mut [i32] = &mut [];
 135     assert!(b.split_first_mut().is_none());
 136     assert!(a.split_first_mut() == Some((&mut 11, b)));
 137     a = vec![11, 12];
 138     let b: &mut [_] = &mut [12];
 139     assert!(a.split_first_mut() == Some((&mut 11, b)));
 140 }
 141
 142 #[test]
 143 fn test_split_last() {
 144     let mut a = vec![11];
 145     let b: &[i32] = &[];
 146     assert!(b.split_last().is_none());
 147     assert_eq!(a.split_last(), Some((&11, b)));
 148     a = vec![11, 12];
 149     let b: &[_] = &[11];
 150     assert_eq!(a.split_last(), Some((&12, b)));
 151 }
 152
 153 #[test]
 154 fn test_split_last_mut() {
 155     let mut a = vec![11];
 156     let b: &mut [i32] = &mut [];
 157     assert!(b.split_last_mut().is_none());
 158     assert!(a.split_last_mut() == Some((&mut 11, b)));
 159
 160     a = vec![11, 12];
 161     let b: &mut [_] = &mut [11];
 162     assert!(a.split_last_mut() == Some((&mut 12, b)));
 163 }
 164
 165 #[test]
 166 fn test_last() {
 167     let mut a = vec![];
 168     assert_eq!(a.last(), None);
 169     a = vec![11];
 170     assert_eq!(a.last().unwrap(), &11);
 171     a = vec![11, 12];
 172     assert_eq!(a.last().unwrap(), &12);
 173 }
 174
 175 #[test]
 176 fn test_last_mut() {
 177     let mut a = vec![];
 178     assert_eq!(a.last_mut(), None);
 179     a = vec![11];
 180     assert_eq!(*a.last_mut().unwrap(), 11);
 181     a = vec![11, 12];
 182     assert_eq!(*a.last_mut().unwrap(), 12);
 183 }
 184
 185 #[test]
 186 fn test_slice() {
 187     // Test fixed length vector.
 188     let vec_fixed = [1, 2, 3, 4];
 189     let v_a = vec_fixed[1..vec_fixed.len()].to_vec();
 190     assert_eq!(v_a.len(), 3);
 191
 192     assert_eq!(v_a[0], 2);
 193     assert_eq!(v_a[1], 3);
 194     assert_eq!(v_a[2], 4);
 195
 196     // Test on stack.
 197     let vec_stack: &[_] = &[1, 2, 3];
 198     let v_b = vec_stack[1..3].to_vec();
 199     assert_eq!(v_b.len(), 2);
 200
 201     assert_eq!(v_b[0], 2);
 202     assert_eq!(v_b[1], 3);
 203
 204     // Test `Box<[T]>`
 205     let vec_unique = vec![1, 2, 3, 4, 5, 6];
 206     let v_d = vec_unique[1..6].to_vec();
 207     assert_eq!(v_d.len(), 5);
 208
 209     assert_eq!(v_d[0], 2);
 210     assert_eq!(v_d[1], 3);
 211     assert_eq!(v_d[2], 4);
 212     assert_eq!(v_d[3], 5);
 213     assert_eq!(v_d[4], 6);
 214 }
 215
 216 #[test]
 217 fn test_slice_from() {
 218     let vec: &[_] = &[1, 2, 3, 4];
 219     assert_eq!(&vec[..], vec);
 220     let b: &[_] = &[3, 4];
 221     assert_eq!(&vec[2..], b);
 222     let b: &[_] = &[];
 223     assert_eq!(&vec[4..], b);
 224 }
 225
 226 #[test]
 227 fn test_slice_to() {
 228     let vec: &[_] = &[1, 2, 3, 4];
 229     assert_eq!(&vec[..4], vec);
 230     let b: &[_] = &[1, 2];
 231     assert_eq!(&vec[..2], b);
 232     let b: &[_] = &[];
 233     assert_eq!(&vec[..0], b);
 234 }
 235
 236 #[test]
 237 fn test_pop() {
 238     let mut v = vec![5];
 239     let e = v.pop();
 240     assert_eq!(v.len(), 0);
 241     assert_eq!(e, Some(5));
 242     let f = v.pop();
 243     assert_eq!(f, None);
 244     let g = v.pop();
 245     assert_eq!(g, None);
 246 }
 247
 248 #[test]
 249 fn test_swap_remove() {
 250     let mut v = vec![1, 2, 3, 4, 5];
 251     let mut e = v.swap_remove(0);
 252     assert_eq!(e, 1);
 253     assert_eq!(v, [5, 2, 3, 4]);
 254     e = v.swap_remove(3);
 255     assert_eq!(e, 4);
 256     assert_eq!(v, [5, 2, 3]);
 257 }
 258
 259 #[test]
 260 #[should_panic]
 261 fn test_swap_remove_fail() {
 262     let mut v = vec![1];
 263     let _ = v.swap_remove(0);
 264     let _ = v.swap_remove(0);
 265 }
 266
 267 #[test]
 268 fn test_swap_remove_noncopyable() {
 269     // Tests that we don't accidentally run destructors twice.
 270     let mut v: Vec<Box<_>> = Vec::new();
 271     v.push(Box::new(0));
 272     v.push(Box::new(0));
 273     v.push(Box::new(0));
 274     let mut _e = v.swap_remove(0);
 275     assert_eq!(v.len(), 2);
 276     _e = v.swap_remove(1);
 277     assert_eq!(v.len(), 1);
 278     _e = v.swap_remove(0);
 279     assert_eq!(v.len(), 0);
 280 }
 281
 282 #[test]
 283 fn test_push() {
 284     // Test on-stack push().
 285     let mut v = vec![];
 286     v.push(1);
 287     assert_eq!(v.len(), 1);
 288     assert_eq!(v[0], 1);
 289
 290     // Test on-heap push().
 291     v.push(2);
 292     assert_eq!(v.len(), 2);
 293     assert_eq!(v[0], 1);
 294     assert_eq!(v[1], 2);
 295 }
 296
 297 #[test]
 298 fn test_truncate() {
 299     let mut v: Vec<Box<_>> = vec![Box::new(6), Box::new(5), Box::new(4)];
 300     v.truncate(1);
 301     let v = v;
 302     assert_eq!(v.len(), 1);
 303     assert_eq!(*(v[0]), 6);
 304     // If the unsafe block didn't drop things properly, we blow up here.
 305 }
 306
 307 #[test]
 308 fn test_clear() {
 309     let mut v: Vec<Box<_>> = vec![Box::new(6), Box::new(5), Box::new(4)];
 310     v.clear();
 311     assert_eq!(v.len(), 0);
 312     // If the unsafe block didn't drop things properly, we blow up here.
 313 }
 314
 315 #[test]
 316 fn test_retain() {
 317     let mut v = vec![1, 2, 3, 4, 5];
 318     v.retain(is_odd);
 319     assert_eq!(v, [1, 3, 5]);
 320 }
 321
 322 #[test]
 323 fn test_binary_search() {
 324     assert_eq!([1, 2, 3, 4, 5].binary_search(&5).ok(), Some(4));
 325     assert_eq!([1, 2, 3, 4, 5].binary_search(&4).ok(), Some(3));
 326     assert_eq!([1, 2, 3, 4, 5].binary_search(&3).ok(), Some(2));
 327     assert_eq!([1, 2, 3, 4, 5].binary_search(&2).ok(), Some(1));
 328     assert_eq!([1, 2, 3, 4, 5].binary_search(&1).ok(), Some(0));
 329
 330     assert_eq!([2, 4, 6, 8, 10].binary_search(&1).ok(), None);
 331     assert_eq!([2, 4, 6, 8, 10].binary_search(&5).ok(), None);
 332     assert_eq!([2, 4, 6, 8, 10].binary_search(&4).ok(), Some(1));
 333     assert_eq!([2, 4, 6, 8, 10].binary_search(&10).ok(), Some(4));
 334
 335     assert_eq!([2, 4, 6, 8].binary_search(&1).ok(), None);
 336     assert_eq!([2, 4, 6, 8].binary_search(&5).ok(), None);
 337     assert_eq!([2, 4, 6, 8].binary_search(&4).ok(), Some(1));
 338     assert_eq!([2, 4, 6, 8].binary_search(&8).ok(), Some(3));
 339
 340     assert_eq!([2, 4, 6].binary_search(&1).ok(), None);
 341     assert_eq!([2, 4, 6].binary_search(&5).ok(), None);
 342     assert_eq!([2, 4, 6].binary_search(&4).ok(), Some(1));
 343     assert_eq!([2, 4, 6].binary_search(&6).ok(), Some(2));
 344
 345     assert_eq!([2, 4].binary_search(&1).ok(), None);
 346     assert_eq!([2, 4].binary_search(&5).ok(), None);
 347     assert_eq!([2, 4].binary_search(&2).ok(), Some(0));
 348     assert_eq!([2, 4].binary_search(&4).ok(), Some(1));
 349
 350     assert_eq!([2].binary_search(&1).ok(), None);
 351     assert_eq!([2].binary_search(&5).ok(), None);
 352     assert_eq!([2].binary_search(&2).ok(), Some(0));
 353
 354     assert_eq!([].binary_search(&1).ok(), None);
 355     assert_eq!([].binary_search(&5).ok(), None);
 356
 357     assert!([1, 1, 1, 1, 1].binary_search(&1).ok() != None);
 358     assert!([1, 1, 1, 1, 2].binary_search(&1).ok() != None);
 359     assert!([1, 1, 1, 2, 2].binary_search(&1).ok() != None);
 360     assert!([1, 1, 2, 2, 2].binary_search(&1).ok() != None);
 361     assert_eq!([1, 2, 2, 2, 2].binary_search(&1).ok(), Some(0));
 362
 363     assert_eq!([1, 2, 3, 4, 5].binary_search(&6).ok(), None);
 364     assert_eq!([1, 2, 3, 4, 5].binary_search(&0).ok(), None);
 365 }
 366
 367 #[test]
 368 fn test_reverse() {
 369     let mut v = vec![10, 20];
 370     assert_eq!(v[0], 10);
 371     assert_eq!(v[1], 20);
 372     v.reverse();
 373     assert_eq!(v[0], 20);
 374     assert_eq!(v[1], 10);
 375
 376     let mut v3 = Vec::<i32>::new();
 377     v3.reverse();
 378     assert!(v3.is_empty());
 379
 380     // check the 1-byte-types path
 381     let mut v = (-50..51i8).collect::<Vec<_>>();
 382     v.reverse();
 383     assert_eq!(v, (-50..51i8).rev().collect::<Vec<_>>());
 384
 385     // check the 2-byte-types path
 386     let mut v = (-50..51i16).collect::<Vec<_>>();
 387     v.reverse();
 388     assert_eq!(v, (-50..51i16).rev().collect::<Vec<_>>());
 389 }
 390
 391 #[test]
 392 #[cfg_attr(miri, ignore)] // Miri is too slow
 393 fn test_sort() {
 394     let mut rng = thread_rng();
 395
 396     for len in (2..25).chain(500..510) {
 397         for &modulus in &[5, 10, 100, 1000] {
 398             for _ in 0..10 {
 399                 let orig: Vec<_> =
 400                     rng.sample_iter::<i32, _>(&Standard).map(|x| x % modulus).take(len).collect();
 401
 402                 // Sort in default order.
 403                 let mut v = orig.clone();
 404                 v.sort();
 405                 assert!(v.windows(2).all(|w| w[0] <= w[1]));
 406
 407                 // Sort in ascending order.
 408                 let mut v = orig.clone();
 409                 v.sort_by(|a, b| a.cmp(b));
 410                 assert!(v.windows(2).all(|w| w[0] <= w[1]));
 411
 412                 // Sort in descending order.
 413                 let mut v = orig.clone();
 414                 v.sort_by(|a, b| b.cmp(a));
 415                 assert!(v.windows(2).all(|w| w[0] >= w[1]));
 416
 417                 // Sort in lexicographic order.
 418                 let mut v1 = orig.clone();
 419                 let mut v2 = orig.clone();
 420                 v1.sort_by_key(|x| x.to_string());
 421                 v2.sort_by_cached_key(|x| x.to_string());
 422                 assert!(v1.windows(2).all(|w| w[0].to_string() <= w[1].to_string()));
 423                 assert!(v1 == v2);
 424
 425                 // Sort with many pre-sorted runs.
 426                 let mut v = orig.clone();
 427                 v.sort();
 428                 v.reverse();
 429                 for _ in 0..5 {
 430                     let a = rng.gen::<usize>() % len;
 431                     let b = rng.gen::<usize>() % len;
 432                     if a < b {
 433                         v[a..b].reverse();
 434                     } else {
 435                         v.swap(a, b);
 436                     }
 437                 }
 438                 v.sort();
 439                 assert!(v.windows(2).all(|w| w[0] <= w[1]));
 440             }
 441         }
 442     }
 443
 444     // Sort using a completely random comparison function.
 445     // This will reorder the elements *somehow*, but won't panic.
 446     let mut v = [0; 500];
 447     for i in 0..v.len() {
 448         v[i] = i as i32;
 449     }
 450     v.sort_by(|_, _| *[Less, Equal, Greater].choose(&mut rng).unwrap());
 451     v.sort();
 452     for i in 0..v.len() {
 453         assert_eq!(v[i], i as i32);
 454     }
 455
 456     // Should not panic.
 457     [0i32; 0].sort();
 458     [(); 10].sort();
 459     [(); 100].sort();
 460
 461     let mut v = [0xDEADBEEFu64];
 462     v.sort();
 463     assert!(v == [0xDEADBEEF]);
 464 }
 465
 466 #[test]
 467 fn test_sort_stability() {
 468     // Miri is too slow
 469     let large_range = if cfg!(miri) { 0..0 } else { 500..510 };
 470     let rounds = if cfg!(miri) { 1 } else { 10 };
 471
 472     for len in (2..25).chain(large_range) {
 473         for _ in 0..rounds {
 474             let mut counts = [0; 10];
 475
 476             // create a vector like [(6, 1), (5, 1), (6, 2), ...],
 477             // where the first item of each tuple is random, but
 478             // the second item represents which occurrence of that
 479             // number this element is, i.e., the second elements
 480             // will occur in sorted order.
 481             let orig: Vec<_> = (0..len)
 482                 .map(|_| {
 483                     let n = thread_rng().gen::<usize>() % 10;
 484                     counts[n] += 1;
 485                     (n, counts[n])
 486                 })
 487                 .collect();
 488
 489             let mut v = orig.clone();
 490             // Only sort on the first element, so an unstable sort
 491             // may mix up the counts.
 492             v.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 493
 494             // This comparison includes the count (the second item
 495             // of the tuple), so elements with equal first items
 496             // will need to be ordered with increasing
 497             // counts... i.e., exactly asserting that this sort is
 498             // stable.
 499             assert!(v.windows(2).all(|w| w[0] <= w[1]));
 500
 501             let mut v = orig.clone();
 502             v.sort_by_cached_key(|&(x, _)| x);
 503             assert!(v.windows(2).all(|w| w[0] <= w[1]));
 504         }
 505     }
 506 }
 507
 508 #[test]
 509 fn test_rotate_left() {
 510     let expected: Vec<_> = (0..13).collect();
 511     let mut v = Vec::new();
 512
 513     // no-ops
 514     v.clone_from(&expected);
 515     v.rotate_left(0);
 516     assert_eq!(v, expected);
 517     v.rotate_left(expected.len());
 518     assert_eq!(v, expected);
 519     let mut zst_array = [(), (), ()];
 520     zst_array.rotate_left(2);
 521
 522     // happy path
 523     v = (5..13).chain(0..5).collect();
 524     v.rotate_left(8);
 525     assert_eq!(v, expected);
 526
 527     let expected: Vec<_> = (0..1000).collect();
 528
 529     // small rotations in large slice, uses ptr::copy
 530     v = (2..1000).chain(0..2).collect();
 531     v.rotate_left(998);
 532     assert_eq!(v, expected);
 533     v = (998..1000).chain(0..998).collect();
 534     v.rotate_left(2);
 535     assert_eq!(v, expected);
 536
 537     // non-small prime rotation, has a few rounds of swapping
 538     v = (389..1000).chain(0..389).collect();
 539     v.rotate_left(1000 - 389);
 540     assert_eq!(v, expected);
 541 }
 542
 543 #[test]
 544 fn test_rotate_right() {
 545     let expected: Vec<_> = (0..13).collect();
 546     let mut v = Vec::new();
 547
 548     // no-ops
 549     v.clone_from(&expected);
 550     v.rotate_right(0);
 551     assert_eq!(v, expected);
 552     v.rotate_right(expected.len());
 553     assert_eq!(v, expected);
 554     let mut zst_array = [(), (), ()];
 555     zst_array.rotate_right(2);
 556
 557     // happy path
 558     v = (5..13).chain(0..5).collect();
 559     v.rotate_right(5);
 560     assert_eq!(v, expected);
 561
 562     let expected: Vec<_> = (0..1000).collect();
 563
 564     // small rotations in large slice, uses ptr::copy
 565     v = (2..1000).chain(0..2).collect();
 566     v.rotate_right(2);
 567     assert_eq!(v, expected);
 568     v = (998..1000).chain(0..998).collect();
 569     v.rotate_right(998);
 570     assert_eq!(v, expected);
 571
 572     // non-small prime rotation, has a few rounds of swapping
 573     v = (389..1000).chain(0..389).collect();
 574     v.rotate_right(389);
 575     assert_eq!(v, expected);
 576 }
 577
 578 #[test]
 579 fn test_concat() {
 580     let v: [Vec<i32>; 0] = [];
 581     let c = v.concat();
 582     assert_eq!(c, []);
 583     let d = [vec![1], vec![2, 3]].concat();
 584     assert_eq!(d, [1, 2, 3]);
 585
 586     let v: &[&[_]] = &[&[1], &[2, 3]];
 587     assert_eq!(v.join(&0), [1, 0, 2, 3]);
 588     let v: &[&[_]] = &[&[1], &[2], &[3]];
 589     assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
 590 }
 591
 592 #[test]
 593 fn test_join() {
 594     let v: [Vec<i32>; 0] = [];
 595     assert_eq!(v.join(&0), []);
 596     assert_eq!([vec![1], vec![2, 3]].join(&0), [1, 0, 2, 3]);
 597     assert_eq!([vec![1], vec![2], vec![3]].join(&0), [1, 0, 2, 0, 3]);
 598
 599     let v: [&[_]; 2] = [&[1], &[2, 3]];
 600     assert_eq!(v.join(&0), [1, 0, 2, 3]);
 601     let v: [&[_]; 3] = [&[1], &[2], &[3]];
 602     assert_eq!(v.join(&0), [1, 0, 2, 0, 3]);
 603 }
 604
 605 #[test]
 606 fn test_join_nocopy() {
 607     let v: [String; 0] = [];
 608     assert_eq!(v.join(","), "");
 609     assert_eq!(["a".to_string(), "ab".into()].join(","), "a,ab");
 610     assert_eq!(["a".to_string(), "ab".into(), "abc".into()].join(","), "a,ab,abc");
 611     assert_eq!(["a".to_string(), "ab".into(), "".into()].join(","), "a,ab,");
 612 }
 613
 614 #[test]
 615 fn test_insert() {
 616     let mut a = vec![1, 2, 4];
 617     a.insert(2, 3);
 618     assert_eq!(a, [1, 2, 3, 4]);
 619
 620     let mut a = vec![1, 2, 3];
 621     a.insert(0, 0);
 622     assert_eq!(a, [0, 1, 2, 3]);
 623
 624     let mut a = vec![1, 2, 3];
 625     a.insert(3, 4);
 626     assert_eq!(a, [1, 2, 3, 4]);
 627
 628     let mut a = vec![];
 629     a.insert(0, 1);
 630     assert_eq!(a, [1]);
 631 }
 632
 633 #[test]
 634 #[should_panic]
 635 fn test_insert_oob() {
 636     let mut a = vec![1, 2, 3];
 637     a.insert(4, 5);
 638 }
 639
 640 #[test]
 641 fn test_remove() {
 642     let mut a = vec![1, 2, 3, 4];
 643
 644     assert_eq!(a.remove(2), 3);
 645     assert_eq!(a, [1, 2, 4]);
 646
 647     assert_eq!(a.remove(2), 4);
 648     assert_eq!(a, [1, 2]);
 649
 650     assert_eq!(a.remove(0), 1);
 651     assert_eq!(a, [2]);
 652
 653     assert_eq!(a.remove(0), 2);
 654     assert_eq!(a, []);
 655 }
 656
 657 #[test]
 658 #[should_panic]
 659 fn test_remove_fail() {
 660     let mut a = vec![1];
 661     let _ = a.remove(0);
 662     let _ = a.remove(0);
 663 }
 664
 665 #[test]
 666 fn test_capacity() {
 667     let mut v = vec![0];
 668     v.reserve_exact(10);
 669     assert!(v.capacity() >= 11);
 670 }
 671
 672 #[test]
 673 fn test_slice_2() {
 674     let v = vec![1, 2, 3, 4, 5];
 675     let v = &v[1..3];
 676     assert_eq!(v.len(), 2);
 677     assert_eq!(v[0], 2);
 678     assert_eq!(v[1], 3);
 679 }
 680
 681 macro_rules! assert_order {
 682     (Greater, $a:expr, $b:expr) => {
 683         assert_eq!($a.cmp($b), Greater);
 684         assert!($a > $b);
 685     };
 686     (Less, $a:expr, $b:expr) => {
 687         assert_eq!($a.cmp($b), Less);
 688         assert!($a < $b);
 689     };
 690     (Equal, $a:expr, $b:expr) => {
 691         assert_eq!($a.cmp($b), Equal);
 692         assert_eq!($a, $b);
 693     };
 694 }
 695
 696 #[test]
 697 fn test_total_ord_u8() {
 698     let c = &[1u8, 2, 3];
 699     assert_order!(Greater, &[1u8, 2, 3, 4][..], &c[..]);
 700     let c = &[1u8, 2, 3, 4];
 701     assert_order!(Less, &[1u8, 2, 3][..], &c[..]);
 702     let c = &[1u8, 2, 3, 6];
 703     assert_order!(Equal, &[1u8, 2, 3, 6][..], &c[..]);
 704     let c = &[1u8, 2, 3, 4, 5, 6];
 705     assert_order!(Less, &[1u8, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
 706     let c = &[1u8, 2, 3, 4];
 707     assert_order!(Greater, &[2u8, 2][..], &c[..]);
 708 }
 709
 710 #[test]
 711 fn test_total_ord_i32() {
 712     let c = &[1, 2, 3];
 713     assert_order!(Greater, &[1, 2, 3, 4][..], &c[..]);
 714     let c = &[1, 2, 3, 4];
 715     assert_order!(Less, &[1, 2, 3][..], &c[..]);
 716     let c = &[1, 2, 3, 6];
 717     assert_order!(Equal, &[1, 2, 3, 6][..], &c[..]);
 718     let c = &[1, 2, 3, 4, 5, 6];
 719     assert_order!(Less, &[1, 2, 3, 4, 5, 5, 5, 5][..], &c[..]);
 720     let c = &[1, 2, 3, 4];
 721     assert_order!(Greater, &[2, 2][..], &c[..]);
 722 }
 723
 724 #[test]
 725 fn test_iterator() {
 726     let xs = [1, 2, 5, 10, 11];
 727     let mut it = xs.iter();
 728     assert_eq!(it.size_hint(), (5, Some(5)));
 729     assert_eq!(it.next().unwrap(), &1);
 730     assert_eq!(it.size_hint(), (4, Some(4)));
 731     assert_eq!(it.next().unwrap(), &2);
 732     assert_eq!(it.size_hint(), (3, Some(3)));
 733     assert_eq!(it.next().unwrap(), &5);
 734     assert_eq!(it.size_hint(), (2, Some(2)));
 735     assert_eq!(it.next().unwrap(), &10);
 736     assert_eq!(it.size_hint(), (1, Some(1)));
 737     assert_eq!(it.next().unwrap(), &11);
 738     assert_eq!(it.size_hint(), (0, Some(0)));
 739     assert!(it.next().is_none());
 740 }
 741
 742 #[test]
 743 fn test_iter_size_hints() {
 744     let mut xs = [1, 2, 5, 10, 11];
 745     assert_eq!(xs.iter().size_hint(), (5, Some(5)));
 746     assert_eq!(xs.iter_mut().size_hint(), (5, Some(5)));
 747 }
 748
 749 #[test]
 750 fn test_iter_as_slice() {
 751     let xs = [1, 2, 5, 10, 11];
 752     let mut iter = xs.iter();
 753     assert_eq!(iter.as_slice(), &[1, 2, 5, 10, 11]);
 754     iter.next();
 755     assert_eq!(iter.as_slice(), &[2, 5, 10, 11]);
 756 }
 757
 758 #[test]
 759 fn test_iter_as_ref() {
 760     let xs = [1, 2, 5, 10, 11];
 761     let mut iter = xs.iter();
 762     assert_eq!(iter.as_ref(), &[1, 2, 5, 10, 11]);
 763     iter.next();
 764     assert_eq!(iter.as_ref(), &[2, 5, 10, 11]);
 765 }
 766
 767 #[test]
 768 fn test_iter_clone() {
 769     let xs = [1, 2, 5];
 770     let mut it = xs.iter();
 771     it.next();
 772     let mut jt = it.clone();
 773     assert_eq!(it.next(), jt.next());
 774     assert_eq!(it.next(), jt.next());
 775     assert_eq!(it.next(), jt.next());
 776 }
 777
 778 #[test]
 779 fn test_iter_is_empty() {
 780     let xs = [1, 2, 5, 10, 11];
 781     for i in 0..xs.len() {
 782         for j in i..xs.len() {
 783             assert_eq!(xs[i..j].iter().is_empty(), xs[i..j].is_empty());
 784         }
 785     }
 786 }
 787
 788 #[test]
 789 fn test_mut_iterator() {
 790     let mut xs = [1, 2, 3, 4, 5];
 791     for x in &mut xs {
 792         *x += 1;
 793     }
 794     assert!(xs == [2, 3, 4, 5, 6])
 795 }
 796
 797 #[test]
 798 fn test_rev_iterator() {
 799     let xs = [1, 2, 5, 10, 11];
 800     let ys = [11, 10, 5, 2, 1];
 801     let mut i = 0;
 802     for &x in xs.iter().rev() {
 803         assert_eq!(x, ys[i]);
 804         i += 1;
 805     }
 806     assert_eq!(i, 5);
 807 }
 808
 809 #[test]
 810 fn test_mut_rev_iterator() {
 811     let mut xs = [1, 2, 3, 4, 5];
 812     for (i, x) in xs.iter_mut().rev().enumerate() {
 813         *x += i;
 814     }
 815     assert!(xs == [5, 5, 5, 5, 5])
 816 }
 817
 818 #[test]
 819 fn test_move_iterator() {
 820     let xs = vec![1, 2, 3, 4, 5];
 821     assert_eq!(xs.into_iter().fold(0, |a: usize, b: usize| 10 * a + b), 12345);
 822 }
 823
 824 #[test]
 825 fn test_move_rev_iterator() {
 826     let xs = vec![1, 2, 3, 4, 5];
 827     assert_eq!(xs.into_iter().rev().fold(0, |a: usize, b: usize| 10 * a + b), 54321);
 828 }
 829
 830 #[test]
 831 fn test_splitator() {
 832     let xs = &[1, 2, 3, 4, 5];
 833
 834     let splits: &[&[_]] = &[&[1], &[3], &[5]];
 835     assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 836     let splits: &[&[_]] = &[&[], &[2, 3, 4, 5]];
 837     assert_eq!(xs.split(|x| *x == 1).collect::<Vec<_>>(), splits);
 838     let splits: &[&[_]] = &[&[1, 2, 3, 4], &[]];
 839     assert_eq!(xs.split(|x| *x == 5).collect::<Vec<_>>(), splits);
 840     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 841     assert_eq!(xs.split(|x| *x == 10).collect::<Vec<_>>(), splits);
 842     let splits: &[&[_]] = &[&[], &[], &[], &[], &[], &[]];
 843     assert_eq!(xs.split(|_| true).collect::<Vec<&[i32]>>(), splits);
 844
 845     let xs: &[i32] = &[];
 846     let splits: &[&[i32]] = &[&[]];
 847     assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[i32]>>(), splits);
 848 }
 849
 850 #[test]
 851 fn test_splitator_inclusive() {
 852     let xs = &[1, 2, 3, 4, 5];
 853
 854     let splits: &[&[_]] = &[&[1, 2], &[3, 4], &[5]];
 855     assert_eq!(xs.split_inclusive(|x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 856     let splits: &[&[_]] = &[&[1], &[2, 3, 4, 5]];
 857     assert_eq!(xs.split_inclusive(|x| *x == 1).collect::<Vec<_>>(), splits);
 858     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 859     assert_eq!(xs.split_inclusive(|x| *x == 5).collect::<Vec<_>>(), splits);
 860     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 861     assert_eq!(xs.split_inclusive(|x| *x == 10).collect::<Vec<_>>(), splits);
 862     let splits: &[&[_]] = &[&[1], &[2], &[3], &[4], &[5]];
 863     assert_eq!(xs.split_inclusive(|_| true).collect::<Vec<&[i32]>>(), splits);
 864
 865     let xs: &[i32] = &[];
 866     let splits: &[&[i32]] = &[];
 867     assert_eq!(xs.split_inclusive(|x| *x == 5).collect::<Vec<&[i32]>>(), splits);
 868 }
 869
 870 #[test]
 871 fn test_splitator_inclusive_reverse() {
 872     let xs = &[1, 2, 3, 4, 5];
 873
 874     let splits: &[&[_]] = &[&[5], &[3, 4], &[1, 2]];
 875     assert_eq!(xs.split_inclusive(|x| *x % 2 == 0).rev().collect::<Vec<_>>(), splits);
 876     let splits: &[&[_]] = &[&[2, 3, 4, 5], &[1]];
 877     assert_eq!(xs.split_inclusive(|x| *x == 1).rev().collect::<Vec<_>>(), splits);
 878     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 879     assert_eq!(xs.split_inclusive(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
 880     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 881     assert_eq!(xs.split_inclusive(|x| *x == 10).rev().collect::<Vec<_>>(), splits);
 882     let splits: &[&[_]] = &[&[5], &[4], &[3], &[2], &[1]];
 883     assert_eq!(xs.split_inclusive(|_| true).rev().collect::<Vec<_>>(), splits);
 884
 885     let xs: &[i32] = &[];
 886     let splits: &[&[i32]] = &[];
 887     assert_eq!(xs.split_inclusive(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
 888 }
 889
 890 #[test]
 891 fn test_splitator_mut_inclusive() {
 892     let xs = &mut [1, 2, 3, 4, 5];
 893
 894     let splits: &[&[_]] = &[&[1, 2], &[3, 4], &[5]];
 895     assert_eq!(xs.split_inclusive_mut(|x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 896     let splits: &[&[_]] = &[&[1], &[2, 3, 4, 5]];
 897     assert_eq!(xs.split_inclusive_mut(|x| *x == 1).collect::<Vec<_>>(), splits);
 898     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 899     assert_eq!(xs.split_inclusive_mut(|x| *x == 5).collect::<Vec<_>>(), splits);
 900     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 901     assert_eq!(xs.split_inclusive_mut(|x| *x == 10).collect::<Vec<_>>(), splits);
 902     let splits: &[&[_]] = &[&[1], &[2], &[3], &[4], &[5]];
 903     assert_eq!(xs.split_inclusive_mut(|_| true).collect::<Vec<_>>(), splits);
 904
 905     let xs: &mut [i32] = &mut [];
 906     let splits: &[&[i32]] = &[];
 907     assert_eq!(xs.split_inclusive_mut(|x| *x == 5).collect::<Vec<_>>(), splits);
 908 }
 909
 910 #[test]
 911 fn test_splitator_mut_inclusive_reverse() {
 912     let xs = &mut [1, 2, 3, 4, 5];
 913
 914     let splits: &[&[_]] = &[&[5], &[3, 4], &[1, 2]];
 915     assert_eq!(xs.split_inclusive_mut(|x| *x % 2 == 0).rev().collect::<Vec<_>>(), splits);
 916     let splits: &[&[_]] = &[&[2, 3, 4, 5], &[1]];
 917     assert_eq!(xs.split_inclusive_mut(|x| *x == 1).rev().collect::<Vec<_>>(), splits);
 918     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 919     assert_eq!(xs.split_inclusive_mut(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
 920     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 921     assert_eq!(xs.split_inclusive_mut(|x| *x == 10).rev().collect::<Vec<_>>(), splits);
 922     let splits: &[&[_]] = &[&[5], &[4], &[3], &[2], &[1]];
 923     assert_eq!(xs.split_inclusive_mut(|_| true).rev().collect::<Vec<_>>(), splits);
 924
 925     let xs: &mut [i32] = &mut [];
 926     let splits: &[&[i32]] = &[];
 927     assert_eq!(xs.split_inclusive_mut(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
 928 }
 929
 930 #[test]
 931 fn test_splitnator() {
 932     let xs = &[1, 2, 3, 4, 5];
 933
 934     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 935     assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 936     let splits: &[&[_]] = &[&[1], &[3, 4, 5]];
 937     assert_eq!(xs.splitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 938     let splits: &[&[_]] = &[&[], &[], &[], &[4, 5]];
 939     assert_eq!(xs.splitn(4, |_| true).collect::<Vec<_>>(), splits);
 940
 941     let xs: &[i32] = &[];
 942     let splits: &[&[i32]] = &[&[]];
 943     assert_eq!(xs.splitn(2, |x| *x == 5).collect::<Vec<_>>(), splits);
 944 }
 945
 946 #[test]
 947 fn test_splitnator_mut() {
 948     let xs = &mut [1, 2, 3, 4, 5];
 949
 950     let splits: &[&mut [_]] = &[&mut [1, 2, 3, 4, 5]];
 951     assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 952     let splits: &[&mut [_]] = &[&mut [1], &mut [3, 4, 5]];
 953     assert_eq!(xs.splitn_mut(2, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 954     let splits: &[&mut [_]] = &[&mut [], &mut [], &mut [], &mut [4, 5]];
 955     assert_eq!(xs.splitn_mut(4, |_| true).collect::<Vec<_>>(), splits);
 956
 957     let xs: &mut [i32] = &mut [];
 958     let splits: &[&mut [i32]] = &[&mut []];
 959     assert_eq!(xs.splitn_mut(2, |x| *x == 5).collect::<Vec<_>>(), splits);
 960 }
 961
 962 #[test]
 963 fn test_rsplitator() {
 964     let xs = &[1, 2, 3, 4, 5];
 965
 966     let splits: &[&[_]] = &[&[5], &[3], &[1]];
 967     assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<_>>(), splits);
 968     let splits: &[&[_]] = &[&[2, 3, 4, 5], &[]];
 969     assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<_>>(), splits);
 970     let splits: &[&[_]] = &[&[], &[1, 2, 3, 4]];
 971     assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<_>>(), splits);
 972     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 973     assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<_>>(), splits);
 974
 975     let xs: &[i32] = &[];
 976     let splits: &[&[i32]] = &[&[]];
 977     assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[i32]>>(), splits);
 978 }
 979
 980 #[test]
 981 fn test_rsplitnator() {
 982     let xs = &[1, 2, 3, 4, 5];
 983
 984     let splits: &[&[_]] = &[&[1, 2, 3, 4, 5]];
 985     assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 986     let splits: &[&[_]] = &[&[5], &[1, 2, 3]];
 987     assert_eq!(xs.rsplitn(2, |x| *x % 2 == 0).collect::<Vec<_>>(), splits);
 988     let splits: &[&[_]] = &[&[], &[], &[], &[1, 2]];
 989     assert_eq!(xs.rsplitn(4, |_| true).collect::<Vec<_>>(), splits);
 990
 991     let xs: &[i32] = &[];
 992     let splits: &[&[i32]] = &[&[]];
 993     assert_eq!(xs.rsplitn(2, |x| *x == 5).collect::<Vec<&[i32]>>(), splits);
 994     assert!(xs.rsplitn(0, |x| *x % 2 == 0).next().is_none());
 995 }
 996
 997 #[test]
 998 fn test_split_iterators_size_hint() {
 999     #[derive(Copy, Clone)]
1000     enum Bounds {
1001         Lower,
1002         Upper,
1003     }
1004     fn assert_tight_size_hints(mut it: impl Iterator, which: Bounds, ctx: impl fmt::Display) {
1005         match which {
1006             Bounds::Lower => {
1007                 let mut lower_bounds = vec![it.size_hint().0];
1008                 while let Some(_) = it.next() {
1009                     lower_bounds.push(it.size_hint().0);
1010                 }
1011                 let target: Vec<_> = (0..lower_bounds.len()).rev().collect();
1012                 assert_eq!(lower_bounds, target, "lower bounds incorrect or not tight: {}", ctx);
1013             }
1014             Bounds::Upper => {
1015                 let mut upper_bounds = vec![it.size_hint().1];
1016                 while let Some(_) = it.next() {
1017                     upper_bounds.push(it.size_hint().1);
1018                 }
1019                 let target: Vec<_> = (0..upper_bounds.len()).map(Some).rev().collect();
1020                 assert_eq!(upper_bounds, target, "upper bounds incorrect or not tight: {}", ctx);
1021             }
1022         }
1023     }
1024
1025     for len in 0..=2 {
1026         let mut v: Vec<u8> = (0..len).collect();
1027
1028         // p: predicate, b: bound selection
1029         for (p, b) in [
1030             // with a predicate always returning false, the split*-iterators
1031             // become maximally short, so the size_hint lower bounds are tight
1032             ((|_| false) as fn(&_) -> _, Bounds::Lower),
1033             // with a predicate always returning true, the split*-iterators
1034             // become maximally long, so the size_hint upper bounds are tight
1035             ((|_| true) as fn(&_) -> _, Bounds::Upper),
1036         ] {
1037             use assert_tight_size_hints as a;
1038             use format_args as f;
1039
1040             a(v.split(p), b, "split");
1041             a(v.split_mut(p), b, "split_mut");
1042             a(v.split_inclusive(p), b, "split_inclusive");
1043             a(v.split_inclusive_mut(p), b, "split_inclusive_mut");
1044             a(v.rsplit(p), b, "rsplit");
1045             a(v.rsplit_mut(p), b, "rsplit_mut");
1046
1047             for n in 0..=3 {
1048                 a(v.splitn(n, p), b, f!("splitn, n = {n}"));
1049                 a(v.splitn_mut(n, p), b, f!("splitn_mut, n = {n}"));
1050                 a(v.rsplitn(n, p), b, f!("rsplitn, n = {n}"));
1051                 a(v.rsplitn_mut(n, p), b, f!("rsplitn_mut, n = {n}"));
1052             }
1053         }
1054     }
1055 }
1056
1057 #[test]
1058 fn test_windowsator() {
1059     let v = &[1, 2, 3, 4];
1060
1061     let wins: &[&[_]] = &[&[1, 2], &[2, 3], &[3, 4]];
1062     assert_eq!(v.windows(2).collect::<Vec<_>>(), wins);
1063
1064     let wins: &[&[_]] = &[&[1, 2, 3], &[2, 3, 4]];
1065     assert_eq!(v.windows(3).collect::<Vec<_>>(), wins);
1066     assert!(v.windows(6).next().is_none());
1067
1068     let wins: &[&[_]] = &[&[3, 4], &[2, 3], &[1, 2]];
1069     assert_eq!(v.windows(2).rev().collect::<Vec<&[_]>>(), wins);
1070 }
1071
1072 #[test]
1073 #[should_panic]
1074 fn test_windowsator_0() {
1075     let v = &[1, 2, 3, 4];
1076     let _it = v.windows(0);
1077 }
1078
1079 #[test]
1080 fn test_chunksator() {
1081     let v = &[1, 2, 3, 4, 5];
1082
1083     assert_eq!(v.chunks(2).len(), 3);
1084
1085     let chunks: &[&[_]] = &[&[1, 2], &[3, 4], &[5]];
1086     assert_eq!(v.chunks(2).collect::<Vec<_>>(), chunks);
1087     let chunks: &[&[_]] = &[&[1, 2, 3], &[4, 5]];
1088     assert_eq!(v.chunks(3).collect::<Vec<_>>(), chunks);
1089     let chunks: &[&[_]] = &[&[1, 2, 3, 4, 5]];
1090     assert_eq!(v.chunks(6).collect::<Vec<_>>(), chunks);
1091
1092     let chunks: &[&[_]] = &[&[5], &[3, 4], &[1, 2]];
1093     assert_eq!(v.chunks(2).rev().collect::<Vec<_>>(), chunks);
1094 }
1095
1096 #[test]
1097 #[should_panic]
1098 fn test_chunksator_0() {
1099     let v = &[1, 2, 3, 4];
1100     let _it = v.chunks(0);
1101 }
1102
1103 #[test]
1104 fn test_chunks_exactator() {
1105     let v = &[1, 2, 3, 4, 5];
1106
1107     assert_eq!(v.chunks_exact(2).len(), 2);
1108
1109     let chunks: &[&[_]] = &[&[1, 2], &[3, 4]];
1110     assert_eq!(v.chunks_exact(2).collect::<Vec<_>>(), chunks);
1111     let chunks: &[&[_]] = &[&[1, 2, 3]];
1112     assert_eq!(v.chunks_exact(3).collect::<Vec<_>>(), chunks);
1113     let chunks: &[&[_]] = &[];
1114     assert_eq!(v.chunks_exact(6).collect::<Vec<_>>(), chunks);
1115
1116     let chunks: &[&[_]] = &[&[3, 4], &[1, 2]];
1117     assert_eq!(v.chunks_exact(2).rev().collect::<Vec<_>>(), chunks);
1118 }
1119
1120 #[test]
1121 #[should_panic]
1122 fn test_chunks_exactator_0() {
1123     let v = &[1, 2, 3, 4];
1124     let _it = v.chunks_exact(0);
1125 }
1126
1127 #[test]
1128 fn test_rchunksator() {
1129     let v = &[1, 2, 3, 4, 5];
1130
1131     assert_eq!(v.rchunks(2).len(), 3);
1132
1133     let chunks: &[&[_]] = &[&[4, 5], &[2, 3], &[1]];
1134     assert_eq!(v.rchunks(2).collect::<Vec<_>>(), chunks);
1135     let chunks: &[&[_]] = &[&[3, 4, 5], &[1, 2]];
1136     assert_eq!(v.rchunks(3).collect::<Vec<_>>(), chunks);
1137     let chunks: &[&[_]] = &[&[1, 2, 3, 4, 5]];
1138     assert_eq!(v.rchunks(6).collect::<Vec<_>>(), chunks);
1139
1140     let chunks: &[&[_]] = &[&[1], &[2, 3], &[4, 5]];
1141     assert_eq!(v.rchunks(2).rev().collect::<Vec<_>>(), chunks);
1142 }
1143
1144 #[test]
1145 #[should_panic]
1146 fn test_rchunksator_0() {
1147     let v = &[1, 2, 3, 4];
1148     let _it = v.rchunks(0);
1149 }
1150
1151 #[test]
1152 fn test_rchunks_exactator() {
1153     let v = &[1, 2, 3, 4, 5];
1154
1155     assert_eq!(v.rchunks_exact(2).len(), 2);
1156
1157     let chunks: &[&[_]] = &[&[4, 5], &[2, 3]];
1158     assert_eq!(v.rchunks_exact(2).collect::<Vec<_>>(), chunks);
1159     let chunks: &[&[_]] = &[&[3, 4, 5]];
1160     assert_eq!(v.rchunks_exact(3).collect::<Vec<_>>(), chunks);
1161     let chunks: &[&[_]] = &[];
1162     assert_eq!(v.rchunks_exact(6).collect::<Vec<_>>(), chunks);
1163
1164     let chunks: &[&[_]] = &[&[2, 3], &[4, 5]];
1165     assert_eq!(v.rchunks_exact(2).rev().collect::<Vec<_>>(), chunks);
1166 }
1167
1168 #[test]
1169 #[should_panic]
1170 fn test_rchunks_exactator_0() {
1171     let v = &[1, 2, 3, 4];
1172     let _it = v.rchunks_exact(0);
1173 }
1174
1175 #[test]
1176 fn test_reverse_part() {
1177     let mut values = [1, 2, 3, 4, 5];
1178     values[1..4].reverse();
1179     assert!(values == [1, 4, 3, 2, 5]);
1180 }
1181
1182 #[test]
1183 fn test_show() {
1184     macro_rules! test_show_vec {
1185         ($x:expr, $x_str:expr) => {{
1186             let (x, x_str) = ($x, $x_str);
1187             assert_eq!(format!("{x:?}"), x_str);
1188             assert_eq!(format!("{x:?}"), x_str);
1189         }};
1190     }
1191     let empty = Vec::<i32>::new();
1192     test_show_vec!(empty, "[]");
1193     test_show_vec!(vec![1], "[1]");
1194     test_show_vec!(vec![1, 2, 3], "[1, 2, 3]");
1195     test_show_vec!(vec![vec![], vec![1], vec![1, 1]], "[[], [1], [1, 1]]");
1196
1197     let empty_mut: &mut [i32] = &mut [];
1198     test_show_vec!(empty_mut, "[]");
1199     let v = &mut [1];
1200     test_show_vec!(v, "[1]");
1201     let v = &mut [1, 2, 3];
1202     test_show_vec!(v, "[1, 2, 3]");
1203     let v: &mut [&mut [_]] = &mut [&mut [], &mut [1], &mut [1, 1]];
1204     test_show_vec!(v, "[[], [1], [1, 1]]");
1205 }
1206
1207 #[test]
1208 fn test_vec_default() {
1209     macro_rules! t {
1210         ($ty:ty) => {{
1211             let v: $ty = Default::default();
1212             assert!(v.is_empty());
1213         }};
1214     }
1215
1216     t!(&[i32]);
1217     t!(Vec<i32>);
1218 }
1219
1220 #[test]
1221 #[should_panic]
1222 fn test_overflow_does_not_cause_segfault() {
1223     let mut v = vec![];
1224     v.reserve_exact(!0);
1225     v.push(1);
1226     v.push(2);
1227 }
1228
1229 #[test]
1230 #[should_panic]
1231 fn test_overflow_does_not_cause_segfault_managed() {
1232     let mut v = vec![Rc::new(1)];
1233     v.reserve_exact(!0);
1234     v.push(Rc::new(2));
1235 }
1236
1237 #[test]
1238 fn test_mut_split_at() {
1239     let mut values = [1, 2, 3, 4, 5];
1240     {
1241         let (left, right) = values.split_at_mut(2);
1242         {
1243             let left: &[_] = left;
1244             assert!(left[..left.len()] == [1, 2]);
1245         }
1246         for p in left {
1247             *p += 1;
1248         }
1249
1250         {
1251             let right: &[_] = right;
1252             assert!(right[..right.len()] == [3, 4, 5]);
1253         }
1254         for p in right {
1255             *p += 2;
1256         }
1257     }
1258
1259     assert!(values == [2, 3, 5, 6, 7]);
1260 }
1261
1262 #[derive(Clone, PartialEq)]
1263 struct Foo;
1264
1265 #[test]
1266 fn test_iter_zero_sized() {
1267     let mut v = vec![Foo, Foo, Foo];
1268     assert_eq!(v.len(), 3);
1269     let mut cnt = 0;
1270
1271     for f in &v {
1272         assert!(*f == Foo);
1273         cnt += 1;
1274     }
1275     assert_eq!(cnt, 3);
1276
1277     for f in &v[1..3] {
1278         assert!(*f == Foo);
1279         cnt += 1;
1280     }
1281     assert_eq!(cnt, 5);
1282
1283     for f in &mut v {
1284         assert!(*f == Foo);
1285         cnt += 1;
1286     }
1287     assert_eq!(cnt, 8);
1288
1289     for f in v {
1290         assert!(f == Foo);
1291         cnt += 1;
1292     }
1293     assert_eq!(cnt, 11);
1294
1295     let xs: [Foo; 3] = [Foo, Foo, Foo];
1296     cnt = 0;
1297     for f in &xs {
1298         assert!(*f == Foo);
1299         cnt += 1;
1300     }
1301     assert!(cnt == 3);
1302 }
1303
1304 #[test]
1305 fn test_shrink_to_fit() {
1306     let mut xs = vec![0, 1, 2, 3];
1307     for i in 4..100 {
1308         xs.push(i)
1309     }
1310     assert_eq!(xs.capacity(), 128);
1311     xs.shrink_to_fit();
1312     assert_eq!(xs.capacity(), 100);
1313     assert_eq!(xs, (0..100).collect::<Vec<_>>());
1314 }
1315
1316 #[test]
1317 fn test_starts_with() {
1318     assert!(b"foobar".starts_with(b"foo"));
1319     assert!(!b"foobar".starts_with(b"oob"));
1320     assert!(!b"foobar".starts_with(b"bar"));
1321     assert!(!b"foo".starts_with(b"foobar"));
1322     assert!(!b"bar".starts_with(b"foobar"));
1323     assert!(b"foobar".starts_with(b"foobar"));
1324     let empty: &[u8] = &[];
1325     assert!(empty.starts_with(empty));
1326     assert!(!empty.starts_with(b"foo"));
1327     assert!(b"foobar".starts_with(empty));
1328 }
1329
1330 #[test]
1331 fn test_ends_with() {
1332     assert!(b"foobar".ends_with(b"bar"));
1333     assert!(!b"foobar".ends_with(b"oba"));
1334     assert!(!b"foobar".ends_with(b"foo"));
1335     assert!(!b"foo".ends_with(b"foobar"));
1336     assert!(!b"bar".ends_with(b"foobar"));
1337     assert!(b"foobar".ends_with(b"foobar"));
1338     let empty: &[u8] = &[];
1339     assert!(empty.ends_with(empty));
1340     assert!(!empty.ends_with(b"foo"));
1341     assert!(b"foobar".ends_with(empty));
1342 }
1343
1344 #[test]
1345 fn test_mut_splitator() {
1346     let mut xs = [0, 1, 0, 2, 3, 0, 0, 4, 5, 0];
1347     assert_eq!(xs.split_mut(|x| *x == 0).count(), 6);
1348     for slice in xs.split_mut(|x| *x == 0) {
1349         slice.reverse();
1350     }
1351     assert!(xs == [0, 1, 0, 3, 2, 0, 0, 5, 4, 0]);
1352
1353     let mut xs = [0, 1, 0, 2, 3, 0, 0, 4, 5, 0, 6, 7];
1354     for slice in xs.split_mut(|x| *x == 0).take(5) {
1355         slice.reverse();
1356     }
1357     assert!(xs == [0, 1, 0, 3, 2, 0, 0, 5, 4, 0, 6, 7]);
1358 }
1359
1360 #[test]
1361 fn test_mut_splitator_rev() {
1362     let mut xs = [1, 2, 0, 3, 4, 0, 0, 5, 6, 0];
1363     for slice in xs.split_mut(|x| *x == 0).rev().take(4) {
1364         slice.reverse();
1365     }
1366     assert!(xs == [1, 2, 0, 4, 3, 0, 0, 6, 5, 0]);
1367 }
1368
1369 #[test]
1370 fn test_get_mut() {
1371     let mut v = [0, 1, 2];
1372     assert_eq!(v.get_mut(3), None);
1373     v.get_mut(1).map(|e| *e = 7);
1374     assert_eq!(v[1], 7);
1375     let mut x = 2;
1376     assert_eq!(v.get_mut(2), Some(&mut x));
1377 }
1378
1379 #[test]
1380 fn test_mut_chunks() {
1381     let mut v = [0, 1, 2, 3, 4, 5, 6];
1382     assert_eq!(v.chunks_mut(3).len(), 3);
1383     for (i, chunk) in v.chunks_mut(3).enumerate() {
1384         for x in chunk {
1385             *x = i as u8;
1386         }
1387     }
1388     let result = [0, 0, 0, 1, 1, 1, 2];
1389     assert_eq!(v, result);
1390 }
1391
1392 #[test]
1393 fn test_mut_chunks_rev() {
1394     let mut v = [0, 1, 2, 3, 4, 5, 6];
1395     for (i, chunk) in v.chunks_mut(3).rev().enumerate() {
1396         for x in chunk {
1397             *x = i as u8;
1398         }
1399     }
1400     let result = [2, 2, 2, 1, 1, 1, 0];
1401     assert_eq!(v, result);
1402 }
1403
1404 #[test]
1405 #[should_panic]
1406 fn test_mut_chunks_0() {
1407     let mut v = [1, 2, 3, 4];
1408     let _it = v.chunks_mut(0);
1409 }
1410
1411 #[test]
1412 fn test_mut_chunks_exact() {
1413     let mut v = [0, 1, 2, 3, 4, 5, 6];
1414     assert_eq!(v.chunks_exact_mut(3).len(), 2);
1415     for (i, chunk) in v.chunks_exact_mut(3).enumerate() {
1416         for x in chunk {
1417             *x = i as u8;
1418         }
1419     }
1420     let result = [0, 0, 0, 1, 1, 1, 6];
1421     assert_eq!(v, result);
1422 }
1423
1424 #[test]
1425 fn test_mut_chunks_exact_rev() {
1426     let mut v = [0, 1, 2, 3, 4, 5, 6];
1427     for (i, chunk) in v.chunks_exact_mut(3).rev().enumerate() {
1428         for x in chunk {
1429             *x = i as u8;
1430         }
1431     }
1432     let result = [1, 1, 1, 0, 0, 0, 6];
1433     assert_eq!(v, result);
1434 }
1435
1436 #[test]
1437 #[should_panic]
1438 fn test_mut_chunks_exact_0() {
1439     let mut v = [1, 2, 3, 4];
1440     let _it = v.chunks_exact_mut(0);
1441 }
1442
1443 #[test]
1444 fn test_mut_rchunks() {
1445     let mut v = [0, 1, 2, 3, 4, 5, 6];
1446     assert_eq!(v.rchunks_mut(3).len(), 3);
1447     for (i, chunk) in v.rchunks_mut(3).enumerate() {
1448         for x in chunk {
1449             *x = i as u8;
1450         }
1451     }
1452     let result = [2, 1, 1, 1, 0, 0, 0];
1453     assert_eq!(v, result);
1454 }
1455
1456 #[test]
1457 fn test_mut_rchunks_rev() {
1458     let mut v = [0, 1, 2, 3, 4, 5, 6];
1459     for (i, chunk) in v.rchunks_mut(3).rev().enumerate() {
1460         for x in chunk {
1461             *x = i as u8;
1462         }
1463     }
1464     let result = [0, 1, 1, 1, 2, 2, 2];
1465     assert_eq!(v, result);
1466 }
1467
1468 #[test]
1469 #[should_panic]
1470 fn test_mut_rchunks_0() {
1471     let mut v = [1, 2, 3, 4];
1472     let _it = v.rchunks_mut(0);
1473 }
1474
1475 #[test]
1476 fn test_mut_rchunks_exact() {
1477     let mut v = [0, 1, 2, 3, 4, 5, 6];
1478     assert_eq!(v.rchunks_exact_mut(3).len(), 2);
1479     for (i, chunk) in v.rchunks_exact_mut(3).enumerate() {
1480         for x in chunk {
1481             *x = i as u8;
1482         }
1483     }
1484     let result = [0, 1, 1, 1, 0, 0, 0];
1485     assert_eq!(v, result);
1486 }
1487
1488 #[test]
1489 fn test_mut_rchunks_exact_rev() {
1490     let mut v = [0, 1, 2, 3, 4, 5, 6];
1491     for (i, chunk) in v.rchunks_exact_mut(3).rev().enumerate() {
1492         for x in chunk {
1493             *x = i as u8;
1494         }
1495     }
1496     let result = [0, 0, 0, 0, 1, 1, 1];
1497     assert_eq!(v, result);
1498 }
1499
1500 #[test]
1501 #[should_panic]
1502 fn test_mut_rchunks_exact_0() {
1503     let mut v = [1, 2, 3, 4];
1504     let _it = v.rchunks_exact_mut(0);
1505 }
1506
1507 #[test]
1508 fn test_mut_last() {
1509     let mut x = [1, 2, 3, 4, 5];
1510     let h = x.last_mut();
1511     assert_eq!(*h.unwrap(), 5);
1512
1513     let y: &mut [i32] = &mut [];
1514     assert!(y.last_mut().is_none());
1515 }
1516
1517 #[test]
1518 fn test_to_vec() {
1519     let xs: Box<_> = Box::new([1, 2, 3]);
1520     let ys = xs.to_vec();
1521     assert_eq!(ys, [1, 2, 3]);
1522 }
1523
1524 #[test]
1525 fn test_in_place_iterator_specialization() {
1526     let src: Box<[usize]> = Box::new([1, 2, 3]);
1527     let src_ptr = src.as_ptr();
1528     let sink: Box<_> = src.into_vec().into_iter().map(std::convert::identity).collect();
1529     let sink_ptr = sink.as_ptr();
1530     assert_eq!(src_ptr, sink_ptr);
1531 }
1532
1533 #[test]
1534 fn test_box_slice_clone() {
1535     let data = vec![vec![0, 1], vec![0], vec![1]];
1536     let data2 = data.clone().into_boxed_slice().clone().to_vec();
1537
1538     assert_eq!(data, data2);
1539 }
1540
1541 #[test]
1542 #[allow(unused_must_use)] // here, we care about the side effects of `.clone()`
1543 #[cfg_attr(target_os = "emscripten", ignore)]
1544 fn test_box_slice_clone_panics() {
1545     use std::sync::atomic::{AtomicUsize, Ordering};
1546     use std::sync::Arc;
1547
1548     struct Canary {
1549         count: Arc<AtomicUsize>,
1550         panics: bool,
1551     }
1552
1553     impl Drop for Canary {
1554         fn drop(&mut self) {
1555             self.count.fetch_add(1, Ordering::SeqCst);
1556         }
1557     }
1558
1559     impl Clone for Canary {
1560         fn clone(&self) -> Self {
1561             if self.panics {
1562                 panic!()
1563             }
1564
1565             Canary { count: self.count.clone(), panics: self.panics }
1566         }
1567     }
1568
1569     let drop_count = Arc::new(AtomicUsize::new(0));
1570     let canary = Canary { count: drop_count.clone(), panics: false };
1571     let panic = Canary { count: drop_count.clone(), panics: true };
1572
1573     std::panic::catch_unwind(move || {
1574         // When xs is dropped, +5.
1575         let xs =
1576             vec![canary.clone(), canary.clone(), canary.clone(), panic, canary].into_boxed_slice();
1577
1578         // When panic is cloned, +3.
1579         xs.clone();
1580     })
1581     .unwrap_err();
1582
1583     // Total = 8
1584     assert_eq!(drop_count.load(Ordering::SeqCst), 8);
1585 }
1586
1587 #[test]
1588 fn test_copy_from_slice() {
1589     let src = [0, 1, 2, 3, 4, 5];
1590     let mut dst = [0; 6];
1591     dst.copy_from_slice(&src);
1592     assert_eq!(src, dst)
1593 }
1594
1595 #[test]
1596 #[should_panic(expected = "source slice length (4) does not match destination slice length (5)")]
1597 fn test_copy_from_slice_dst_longer() {
1598     let src = [0, 1, 2, 3];
1599     let mut dst = [0; 5];
1600     dst.copy_from_slice(&src);
1601 }
1602
1603 #[test]
1604 #[should_panic(expected = "source slice length (4) does not match destination slice length (3)")]
1605 fn test_copy_from_slice_dst_shorter() {
1606     let src = [0, 1, 2, 3];
1607     let mut dst = [0; 3];
1608     dst.copy_from_slice(&src);
1609 }
1610
1611 const MAX_LEN: usize = 80;
1612
1613 static DROP_COUNTS: [AtomicUsize; MAX_LEN] = [
1614     // FIXME(RFC 1109): AtomicUsize is not Copy.
1615     AtomicUsize::new(0),
1616     AtomicUsize::new(0),
1617     AtomicUsize::new(0),
1618     AtomicUsize::new(0),
1619     AtomicUsize::new(0),
1620     AtomicUsize::new(0),
1621     AtomicUsize::new(0),
1622     AtomicUsize::new(0),
1623     AtomicUsize::new(0),
1624     AtomicUsize::new(0),
1625     AtomicUsize::new(0),
1626     AtomicUsize::new(0),
1627     AtomicUsize::new(0),
1628     AtomicUsize::new(0),
1629     AtomicUsize::new(0),
1630     AtomicUsize::new(0),
1631     AtomicUsize::new(0),
1632     AtomicUsize::new(0),
1633     AtomicUsize::new(0),
1634     AtomicUsize::new(0),
1635     AtomicUsize::new(0),
1636     AtomicUsize::new(0),
1637     AtomicUsize::new(0),
1638     AtomicUsize::new(0),
1639     AtomicUsize::new(0),
1640     AtomicUsize::new(0),
1641     AtomicUsize::new(0),
1642     AtomicUsize::new(0),
1643     AtomicUsize::new(0),
1644     AtomicUsize::new(0),
1645     AtomicUsize::new(0),
1646     AtomicUsize::new(0),
1647     AtomicUsize::new(0),
1648     AtomicUsize::new(0),
1649     AtomicUsize::new(0),
1650     AtomicUsize::new(0),
1651     AtomicUsize::new(0),
1652     AtomicUsize::new(0),
1653     AtomicUsize::new(0),
1654     AtomicUsize::new(0),
1655     AtomicUsize::new(0),
1656     AtomicUsize::new(0),
1657     AtomicUsize::new(0),
1658     AtomicUsize::new(0),
1659     AtomicUsize::new(0),
1660     AtomicUsize::new(0),
1661     AtomicUsize::new(0),
1662     AtomicUsize::new(0),
1663     AtomicUsize::new(0),
1664     AtomicUsize::new(0),
1665     AtomicUsize::new(0),
1666     AtomicUsize::new(0),
1667     AtomicUsize::new(0),
1668     AtomicUsize::new(0),
1669     AtomicUsize::new(0),
1670     AtomicUsize::new(0),
1671     AtomicUsize::new(0),
1672     AtomicUsize::new(0),
1673     AtomicUsize::new(0),
1674     AtomicUsize::new(0),
1675     AtomicUsize::new(0),
1676     AtomicUsize::new(0),
1677     AtomicUsize::new(0),
1678     AtomicUsize::new(0),
1679     AtomicUsize::new(0),
1680     AtomicUsize::new(0),
1681     AtomicUsize::new(0),
1682     AtomicUsize::new(0),
1683     AtomicUsize::new(0),
1684     AtomicUsize::new(0),
1685     AtomicUsize::new(0),
1686     AtomicUsize::new(0),
1687     AtomicUsize::new(0),
1688     AtomicUsize::new(0),
1689     AtomicUsize::new(0),
1690     AtomicUsize::new(0),
1691     AtomicUsize::new(0),
1692     AtomicUsize::new(0),
1693     AtomicUsize::new(0),
1694     AtomicUsize::new(0),
1695 ];
1696
1697 static VERSIONS: AtomicUsize = AtomicUsize::new(0);
1698
1699 #[derive(Clone, Eq)]
1700 struct DropCounter {
1701     x: u32,
1702     id: usize,
1703     version: Cell<usize>,
1704 }
1705
1706 impl PartialEq for DropCounter {
1707     fn eq(&self, other: &Self) -> bool {
1708         self.partial_cmp(other) == Some(Ordering::Equal)
1709     }
1710 }
1711
1712 impl PartialOrd for DropCounter {
1713     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1714         self.version.set(self.version.get() + 1);
1715         other.version.set(other.version.get() + 1);
1716         VERSIONS.fetch_add(2, Relaxed);
1717         self.x.partial_cmp(&other.x)
1718     }
1719 }
1720
1721 impl Ord for DropCounter {
1722     fn cmp(&self, other: &Self) -> Ordering {
1723         self.partial_cmp(other).unwrap()
1724     }
1725 }
1726
1727 impl Drop for DropCounter {
1728     fn drop(&mut self) {
1729         DROP_COUNTS[self.id].fetch_add(1, Relaxed);
1730         VERSIONS.fetch_sub(self.version.get(), Relaxed);
1731     }
1732 }
1733
1734 macro_rules! test {
1735     ($input:ident, $func:ident) => {
1736         let len = $input.len();
1737
1738         // Work out the total number of comparisons required to sort
1739         // this array...
1740         let mut count = 0usize;
1741         $input.to_owned().$func(|a, b| {
1742             count += 1;
1743             a.cmp(b)
1744         });
1745
1746         // ... and then panic on each and every single one.
1747         for panic_countdown in 0..count {
1748             // Refresh the counters.
1749             VERSIONS.store(0, Relaxed);
1750             for i in 0..len {
1751                 DROP_COUNTS[i].store(0, Relaxed);
1752             }
1753
1754             let v = $input.to_owned();
1755             let _ = std::panic::catch_unwind(move || {
1756                 let mut v = v;
1757                 let mut panic_countdown = panic_countdown;
1758                 v.$func(|a, b| {
1759                     if panic_countdown == 0 {
1760                         SILENCE_PANIC.with(|s| s.set(true));
1761                         panic!();
1762                     }
1763                     panic_countdown -= 1;
1764                     a.cmp(b)
1765                 })
1766             });
1767
1768             // Check that the number of things dropped is exactly
1769             // what we expect (i.e., the contents of `v`).
1770             for (i, c) in DROP_COUNTS.iter().enumerate().take(len) {
1771                 let count = c.load(Relaxed);
1772                 assert!(count == 1, "found drop count == {} for i == {}, len == {}", count, i, len);
1773             }
1774
1775             // Check that the most recent versions of values were dropped.
1776             assert_eq!(VERSIONS.load(Relaxed), 0);
1777         }
1778     };
1779 }
1780
1781 thread_local!(static SILENCE_PANIC: Cell<bool> = Cell::new(false));
1782
1783 #[test]
1784 #[cfg_attr(target_os = "emscripten", ignore)] // no threads
1785 fn panic_safe() {
1786     panic::update_hook(move |prev, info| {
1787         if !SILENCE_PANIC.with(|s| s.get()) {
1788             prev(info);
1789         }
1790     });
1791
1792     let mut rng = thread_rng();
1793
1794     // Miri is too slow (but still need to `chain` to make the types match)
1795     let lens = if cfg!(miri) { (1..10).chain(0..0) } else { (1..20).chain(70..MAX_LEN) };
1796     let moduli: &[u32] = if cfg!(miri) { &[5] } else { &[5, 20, 50] };
1797
1798     for len in lens {
1799         for &modulus in moduli {
1800             for &has_runs in &[false, true] {
1801                 let mut input = (0..len)
1802                     .map(|id| DropCounter {
1803                         x: rng.next_u32() % modulus,
1804                         id: id,
1805                         version: Cell::new(0),
1806                     })
1807                     .collect::<Vec<_>>();
1808
1809                 if has_runs {
1810                     for c in &mut input {
1811                         c.x = c.id as u32;
1812                     }
1813
1814                     for _ in 0..5 {
1815                         let a = rng.gen::<usize>() % len;
1816                         let b = rng.gen::<usize>() % len;
1817                         if a < b {
1818                             input[a..b].reverse();
1819                         } else {
1820                             input.swap(a, b);
1821                         }
1822                     }
1823                 }
1824
1825                 test!(input, sort_by);
1826                 test!(input, sort_unstable_by);
1827             }
1828         }
1829     }
1830
1831     // Set default panic hook again.
1832     drop(panic::take_hook());
1833 }
1834
1835 #[test]
1836 fn repeat_generic_slice() {
1837     assert_eq!([1, 2].repeat(2), vec![1, 2, 1, 2]);
1838     assert_eq!([1, 2, 3, 4].repeat(0), vec![]);
1839     assert_eq!([1, 2, 3, 4].repeat(1), vec![1, 2, 3, 4]);
1840     assert_eq!([1, 2, 3, 4].repeat(3), vec![1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]);
1841 }
1842
1843 #[test]
1844 #[allow(unreachable_patterns)]
1845 fn subslice_patterns() {
1846     // This test comprehensively checks the passing static and dynamic semantics
1847     // of subslice patterns `..`, `x @ ..`, `ref x @ ..`, and `ref mut @ ..`
1848     // in slice patterns `[$($pat), $(,)?]` .
1849
1850     #[derive(PartialEq, Debug, Clone)]
1851     struct N(u8);
1852
1853     macro_rules! n {
1854         ($($e:expr),* $(,)?) => {
1855             [$(N($e)),*]
1856         }
1857     }
1858
1859     macro_rules! c {
1860         ($inp:expr, $typ:ty, $out:expr $(,)?) => {
1861             assert_eq!($out, identity::<$typ>($inp))
1862         };
1863     }
1864
1865     macro_rules! m {
1866         ($e:expr, $p:pat => $b:expr) => {
1867             match $e {
1868                 $p => $b,
1869                 _ => panic!(),
1870             }
1871         };
1872     }
1873
1874     // == Slices ==
1875
1876     // Matching slices using `ref` patterns:
1877     let mut v = vec![N(0), N(1), N(2), N(3), N(4)];
1878     let mut vc = (0..=4).collect::<Vec<u8>>();
1879
1880     let [..] = v[..]; // Always matches.
1881     m!(v[..], [N(0), ref sub @ .., N(4)] => c!(sub, &[N], n![1, 2, 3]));
1882     m!(v[..], [N(0), ref sub @ ..] => c!(sub, &[N], n![1, 2, 3, 4]));
1883     m!(v[..], [ref sub @ .., N(4)] => c!(sub, &[N], n![0, 1, 2, 3]));
1884     m!(v[..], [ref sub @ .., _, _, _, _, _] => c!(sub, &[N], &n![] as &[N]));
1885     m!(v[..], [_, _, _, _, _, ref sub @ ..] => c!(sub, &[N], &n![] as &[N]));
1886     m!(vc[..], [x, .., y] => c!((x, y), (u8, u8), (0, 4)));
1887
1888     // Matching slices using `ref mut` patterns:
1889     let [..] = v[..]; // Always matches.
1890     m!(v[..], [N(0), ref mut sub @ .., N(4)] => c!(sub, &mut [N], n![1, 2, 3]));
1891     m!(v[..], [N(0), ref mut sub @ ..] => c!(sub, &mut [N], n![1, 2, 3, 4]));
1892     m!(v[..], [ref mut sub @ .., N(4)] => c!(sub, &mut [N], n![0, 1, 2, 3]));
1893     m!(v[..], [ref mut sub @ .., _, _, _, _, _] => c!(sub, &mut [N], &mut n![] as &mut [N]));
1894     m!(v[..], [_, _, _, _, _, ref mut sub @ ..] => c!(sub, &mut [N], &mut n![] as &mut [N]));
1895     m!(vc[..], [x, .., y] => c!((x, y), (u8, u8), (0, 4)));
1896
1897     // Matching slices using default binding modes (&):
1898     let [..] = &v[..]; // Always matches.
1899     m!(&v[..], [N(0), sub @ .., N(4)] => c!(sub, &[N], n![1, 2, 3]));
1900     m!(&v[..], [N(0), sub @ ..] => c!(sub, &[N], n![1, 2, 3, 4]));
1901     m!(&v[..], [sub @ .., N(4)] => c!(sub, &[N], n![0, 1, 2, 3]));
1902     m!(&v[..], [sub @ .., _, _, _, _, _] => c!(sub, &[N], &n![] as &[N]));
1903     m!(&v[..], [_, _, _, _, _, sub @ ..] => c!(sub, &[N], &n![] as &[N]));
1904     m!(&vc[..], [x, .., y] => c!((x, y), (&u8, &u8), (&0, &4)));
1905
1906     // Matching slices using default binding modes (&mut):
1907     let [..] = &mut v[..]; // Always matches.
1908     m!(&mut v[..], [N(0), sub @ .., N(4)] => c!(sub, &mut [N], n![1, 2, 3]));
1909     m!(&mut v[..], [N(0), sub @ ..] => c!(sub, &mut [N], n![1, 2, 3, 4]));
1910     m!(&mut v[..], [sub @ .., N(4)] => c!(sub, &mut [N], n![0, 1, 2, 3]));
1911     m!(&mut v[..], [sub @ .., _, _, _, _, _] => c!(sub, &mut [N], &mut n![] as &mut [N]));
1912     m!(&mut v[..], [_, _, _, _, _, sub @ ..] => c!(sub, &mut [N], &mut n![] as &mut [N]));
1913     m!(&mut vc[..], [x, .., y] => c!((x, y), (&mut u8, &mut u8), (&mut 0, &mut 4)));
1914
1915     // == Arrays ==
1916     let mut v = n![0, 1, 2, 3, 4];
1917     let vc = [0, 1, 2, 3, 4];
1918
1919     // Matching arrays by value:
1920     m!(v.clone(), [N(0), sub @ .., N(4)] => c!(sub, [N; 3], n![1, 2, 3]));
1921     m!(v.clone(), [N(0), sub @ ..] => c!(sub, [N; 4], n![1, 2, 3, 4]));
1922     m!(v.clone(), [sub @ .., N(4)] => c!(sub, [N; 4], n![0, 1, 2, 3]));
1923     m!(v.clone(), [sub @ .., _, _, _, _, _] => c!(sub, [N; 0], n![] as [N; 0]));
1924     m!(v.clone(), [_, _, _, _, _, sub @ ..] => c!(sub, [N; 0], n![] as [N; 0]));
1925     m!(v.clone(), [x, .., y] => c!((x, y), (N, N), (N(0), N(4))));
1926     m!(v.clone(), [..] => ());
1927
1928     // Matching arrays by ref patterns:
1929     m!(v, [N(0), ref sub @ .., N(4)] => c!(sub, &[N; 3], &n![1, 2, 3]));
1930     m!(v, [N(0), ref sub @ ..] => c!(sub, &[N; 4], &n![1, 2, 3, 4]));
1931     m!(v, [ref sub @ .., N(4)] => c!(sub, &[N; 4], &n![0, 1, 2, 3]));
1932     m!(v, [ref sub @ .., _, _, _, _, _] => c!(sub, &[N; 0], &n![] as &[N; 0]));
1933     m!(v, [_, _, _, _, _, ref sub @ ..] => c!(sub, &[N; 0], &n![] as &[N; 0]));
1934     m!(vc, [x, .., y] => c!((x, y), (u8, u8), (0, 4)));
1935
1936     // Matching arrays by ref mut patterns:
1937     m!(v, [N(0), ref mut sub @ .., N(4)] => c!(sub, &mut [N; 3], &mut n![1, 2, 3]));
1938     m!(v, [N(0), ref mut sub @ ..] => c!(sub, &mut [N; 4], &mut n![1, 2, 3, 4]));
1939     m!(v, [ref mut sub @ .., N(4)] => c!(sub, &mut [N; 4], &mut n![0, 1, 2, 3]));
1940     m!(v, [ref mut sub @ .., _, _, _, _, _] => c!(sub, &mut [N; 0], &mut n![] as &mut [N; 0]));
1941     m!(v, [_, _, _, _, _, ref mut sub @ ..] => c!(sub, &mut [N; 0], &mut n![] as &mut [N; 0]));
1942
1943     // Matching arrays by default binding modes (&):
1944     m!(&v, [N(0), sub @ .., N(4)] => c!(sub, &[N; 3], &n![1, 2, 3]));
1945     m!(&v, [N(0), sub @ ..] => c!(sub, &[N; 4], &n![1, 2, 3, 4]));
1946     m!(&v, [sub @ .., N(4)] => c!(sub, &[N; 4], &n![0, 1, 2, 3]));
1947     m!(&v, [sub @ .., _, _, _, _, _] => c!(sub, &[N; 0], &n![] as &[N; 0]));
1948     m!(&v, [_, _, _, _, _, sub @ ..] => c!(sub, &[N; 0], &n![] as &[N; 0]));
1949     m!(&v, [..] => ());
1950     m!(&v, [x, .., y] => c!((x, y), (&N, &N), (&N(0), &N(4))));
1951
1952     // Matching arrays by default binding modes (&mut):
1953     m!(&mut v, [N(0), sub @ .., N(4)] => c!(sub, &mut [N; 3], &mut n![1, 2, 3]));
1954     m!(&mut v, [N(0), sub @ ..] => c!(sub, &mut [N; 4], &mut n![1, 2, 3, 4]));
1955     m!(&mut v, [sub @ .., N(4)] => c!(sub, &mut [N; 4], &mut n![0, 1, 2, 3]));
1956     m!(&mut v, [sub @ .., _, _, _, _, _] => c!(sub, &mut [N; 0], &mut n![] as &[N; 0]));
1957     m!(&mut v, [_, _, _, _, _, sub @ ..] => c!(sub, &mut [N; 0], &mut n![] as &[N; 0]));
1958     m!(&mut v, [..] => ());
1959     m!(&mut v, [x, .., y] => c!((x, y), (&mut N, &mut N), (&mut N(0), &mut N(4))));
1960 }
1961
1962 #[test]
1963 fn test_group_by() {
1964     let slice = &[1, 1, 1, 3, 3, 2, 2, 2, 1, 0];
1965
1966     let mut iter = slice.group_by(|a, b| a == b);
1967     assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
1968     assert_eq!(iter.next(), Some(&[3, 3][..]));
1969     assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
1970     assert_eq!(iter.next(), Some(&[1][..]));
1971     assert_eq!(iter.next(), Some(&[0][..]));
1972     assert_eq!(iter.next(), None);
1973
1974     let mut iter = slice.group_by(|a, b| a == b);
1975     assert_eq!(iter.next_back(), Some(&[0][..]));
1976     assert_eq!(iter.next_back(), Some(&[1][..]));
1977     assert_eq!(iter.next_back(), Some(&[2, 2, 2][..]));
1978     assert_eq!(iter.next_back(), Some(&[3, 3][..]));
1979     assert_eq!(iter.next_back(), Some(&[1, 1, 1][..]));
1980     assert_eq!(iter.next_back(), None);
1981
1982     let mut iter = slice.group_by(|a, b| a == b);
1983     assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
1984     assert_eq!(iter.next_back(), Some(&[0][..]));
1985     assert_eq!(iter.next(), Some(&[3, 3][..]));
1986     assert_eq!(iter.next_back(), Some(&[1][..]));
1987     assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
1988     assert_eq!(iter.next_back(), None);
1989 }
1990
1991 #[test]
1992 fn test_group_by_mut() {
1993     let slice = &mut [1, 1, 1, 3, 3, 2, 2, 2, 1, 0];
1994
1995     let mut iter = slice.group_by_mut(|a, b| a == b);
1996     assert_eq!(iter.next(), Some(&mut [1, 1, 1][..]));
1997     assert_eq!(iter.next(), Some(&mut [3, 3][..]));
1998     assert_eq!(iter.next(), Some(&mut [2, 2, 2][..]));
1999     assert_eq!(iter.next(), Some(&mut [1][..]));
2000     assert_eq!(iter.next(), Some(&mut [0][..]));
2001     assert_eq!(iter.next(), None);
2002
2003     let mut iter = slice.group_by_mut(|a, b| a == b);
2004     assert_eq!(iter.next_back(), Some(&mut [0][..]));
2005     assert_eq!(iter.next_back(), Some(&mut [1][..]));
2006     assert_eq!(iter.next_back(), Some(&mut [2, 2, 2][..]));
2007     assert_eq!(iter.next_back(), Some(&mut [3, 3][..]));
2008     assert_eq!(iter.next_back(), Some(&mut [1, 1, 1][..]));
2009     assert_eq!(iter.next_back(), None);
2010
2011     let mut iter = slice.group_by_mut(|a, b| a == b);
2012     assert_eq!(iter.next(), Some(&mut [1, 1, 1][..]));
2013     assert_eq!(iter.next_back(), Some(&mut [0][..]));
2014     assert_eq!(iter.next(), Some(&mut [3, 3][..]));
2015     assert_eq!(iter.next_back(), Some(&mut [1][..]));
2016     assert_eq!(iter.next(), Some(&mut [2, 2, 2][..]));
2017     assert_eq!(iter.next_back(), None);
2018 }